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

K到Kn是堆在Kn+加入后将KKn+调成堆设c=n+f=ëc/û若Kf<=Kc则调整完成否则Kf与Kc交换之后c=ff=ëc/û继续比较直到Kf<=Kc或f=即为根结点调整结束

()①child=child+; ②child/ ()不能调为大堆

()不需要因为建堆后R[]到R[n]是堆将R[]与R[n]交换后R[]到R[n]仍是堆故对R[]到R[n]只需从R[]往下筛选即可

() 堆是n个元素的序列堆可以看作是n个结点的完全二叉树而树型排序是n个元素作叶子结点的完全二叉树因此堆占用的空间小调堆时利用堆本身就可以存放输出的有序数据只需要一个记录大小供交换用的辅助空间排序后heap数组中的关键字序列与堆是大堆还是小堆有关若利用大堆则为升序若利用小堆则为降序

最高位优先(MSD)法先对最高位关键字K进行排序将序列分成若干子序列每个子序列中的记录都具有相同的K值然后分别就每个子序列对关键字K进行排序按K值不同再分成若干更小的子序列……依次重复直至最后对最低位关键字排序完成将所有子序列依次连接在一起成为一个有序子序列

最低位优先(LSD)法先对最低位关键字Kd进行排序然后对高一级关键字Kd进行排序依次重复直至对最高位关键字K排序后便成为一个有序序列进行排序时不必分成子序列对每个关键字都是整个序列参加排序但对Ki(<=i<d)排序时只能用稳定的排序方法另一方面按LSD进行排序时可以不通过关键字比较实现排序而是通过若干次分配和收集来实现排序

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