问答题(1999年中国科学院计算机技术研究所)

若有n个元素已构成一个小根堆,那么如果增加一个元素Kn+1,请用文字简要说明如何在log2n的时间内将其重新调整为一个堆。

答案解析

将Kn+1插入数组的第n+1个位置(即作为一个树叶插入),然后将其与双亲比较,若它大于其双亲则停止调整,否则将Kn+1与其父亲交换,重复地将Kn+1与新的双亲比较,算法终止于Kn+1大于等于其双其双亲...

查看完整答案

讨论

下列排序算法中,哪些时间复杂度不会超过nlogn【 】。

初始序列为1 8 6 2 5 4 7 3一组数采用堆排序,当建堆(小根堆)完毕时,堆所对应的二叉树中序遍历序列为【 】。

对长度为10的线性表进行冒泡排序,最坏情况下需要比较的次数为__________。

下列排序算法中,不稳定的是【 】。Ⅰ. 希尔排序Ⅱ. 归并排序Ⅲ. 快速排序Ⅳ. 堆排序Ⅴ. 基数排序

使用快速排序算法对数据进行升序排序, 若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的轴枢【】。

如果待排序序列中两个数据元素具有相同的值,在排序前后它们的位置发生颠倒,则称该排序算法是不稳定的,【 】就是不稳定的排序算法。

若要尽可能快地完成对实数数组的排序,且要求排序是稳定的,应该选【 】。

若需在O(log2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是【 】。

对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是:在插入第i个关键码ki时,其前面的 i-1 个关键码已排好序,因此令k与 ki-1、ki-2、…,依次比较,最多到 k1为止,找到插入位置并移动相关元素后将ki插入有序子序列的适当位置,完成本趟(即第 i-1 趟)排序。以下关于直接插入排序的叙述中,正确的是【 】 。

根据枢轴元素(或基准元素)划分序列而进行排序的是【 】。