在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（  ）。

● 对于 n（n≥0）个元素构成的线性序列 L，在 （60） 时适合采用链式存储结构

（60）

A. 需要频繁修改Ｌ中元素的值

B. 需要频繁地对Ｌ进行随机查找

C. 需要频繁地对Ｌ进行删除和插入操作

D. 要求 L 存储密度高

从供选择的答案中选出应填入下列叙述中()内的正确答案：

堆是一种有用的数据结构。例如关键码序列(A) 是一个堆。

堆排序是一种(B) 排序，它的一个基本问题是如何建堆，常用的建堆算法是1964年 Floyd提出的(C) 。对含n个元素的序列进行排序时，堆排序的时间复杂性是(D) ，所需的附加存储结点是(E)。

供选择的答案

A：①16，72，31，23，94，53

②94，53，31，72，16，53

③16，53，23，94，31，?2

④16，31，23，94，53，72

⑤94，11，53，23，16，72

B：①插入 ②选择 ③交换 ④基数 ⑤归并

C：①淘汰法 ②筛选法 ③递推法 ④LRU算法

D、E：①O(nlog2n) ②O(n) ③O(log2n)

④O(n2) ⑤O(1)

A、O(logn)

B、O(nlogn)

C、O(n)

D、O(n^2)

对n个元素进行堆排序时，最坏情况下的时间复杂度为(53)。

A．O(log2n)

B．O(n)

C．O(nlog2n)

D．O(n2)

对n个元素进行堆排序时，其空间复杂度为( )。

A．O(log2n)

B．O(n log2n)

C．O(n)

D．O(1)

对具有n个元素的有序序列进行二分查找时，(61)。

A．元素位置越靠近序列前端，查找该元素所需的比较次数越少

B．查找序列中任何一个元素所需要的比较次数不超过[log2(n+1)]

C．查找元素所需的比较次数与元素的位置无关

D．元素位置越靠近序列后端，查找该元素所需的比较次数越少

对于具有n个元素的一个数据序列，若只需要得到其中第A个元素之前的部分排序，最好采用(43)。

A．堆排序

B．希尔排序

C．快速排序

D．直接插入排序

A、O(log2n)

B、O(1)

C、O(n)

D、O(nlog2n)

堆排序是(54)类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。

A．插入

B．归并

C．基数

D．选择

对n个元素的序列进行冒泡排序时，最少的比较次数是【1】。