数据结构考研分类复习真题 第十章 排序[63]

．已知关键字序列(KKK…Kn)是大根堆

() 试写出一算法将(KKK…KnKn)调整为大根堆

() 利用()的算法写一个建大根堆的算法【中科院软件所 七 (分)】

类似本题的另外叙述有

()设文件(RR…Rn)是一个堆Rn+是任意一个节点试设计一个算法该算法把Rn+添加到堆中并使添加后形成的文件仍是一个堆要求算法的时间复杂性为O(logn)【吉林大学 二 (分) 】

．辅助地址表的排序是不改变结点物理位置的排序辅助地址表实际上是一组指针用它来指出结点排序后的逻辑顺序地址设用K[]K[]…K[N]表示N个结点的值用T[]T[]…T[N]表示辅助地址表初始时T[i]:=i 在排序中凡需对结点交换就用它的地址来进行例如当N＝时对K()则有T()试编写实现辅助地址表排序(按非递减序)算法的语句序列【重庆大学 四 】

．关于堆排序方法完成如下工作

() 简述该方法的基本思想

() 写出堆排序算法

() 分析该算法的时间复杂度【西南财经大学 五】

类似本题的另外叙述有

()N个元素的序列满足什么条件才能称之为堆？用类PASCAL语言写出堆排序和算法【南开大学 七 (分)】

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