数据结构考研分类复习真题 第十章 答案[21]

()树形选择排序基本思想首先对n个待排序记录的关键字进行两两比较从中选出én/ù个较小者再两两比较直到选出关键字最小的记录为止此为一趟排序我们将一趟选出的关键字最小的记录称为冠军而亚军是从与冠军比较失败的记录中找出具体做法为输出冠军后将其叶子结点关键字改为最大值然后从该叶子结点开始和其左(或右)兄弟比较修改从叶子结点到根结点路径上各结点的关键字则根结点的关键字即为次小关键字如此下去可依次选出从小到大的全部关键字

() 树形选择排序与直接选择排序相比较其优点是从求第个元素开始从ni+个元素中不必进行ni次比较只比较ëlognû次比较次数远小于直接选择排序其缺点是辅助储存空间大

() 堆排序基本思想是堆是n个元素的序列先建堆即先选得一个关键字最大或最小的记录然后与序列中最后一个记录交换之后将序列中前n记录重新调整为堆(调堆的过程称为筛选)再将堆顶记录和当前堆序列的最后一个记录交换如此反复直至排序结束优点是在时间性能与树形选择排序属同一量级的同时堆排序只需要一个记录大小供交换用的辅助空间调堆时子女只和双亲比较避免了过多的辅助存储空间及和最大值的比较

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []