软考中级
● 堆是一种有用的数据结构，堆排序是一种选择排序，它的一个基本问题是如何造堆，常用的建堆方法是 1964年Floyd提出的渗透法。采用此方法对 n个元素进行排序时，堆排序的时间复杂性是 （53） 。（53）A. O(nLog2n)B. O(n)C. O(Log2n)D. O(n2)
题目
● 堆是一种有用的数据结构，堆排序是一种选择排序，它的一个基本问题是如何造堆，常用的建堆方法是 1964年Floyd提出的渗透法。采用此方法对 n个元素进行排序时，堆排序的时间复杂性是 （53） 。
（53）
A. O(nLog2n)
B. O(n)
C. O(Log2n)
D. O(n2)
相似问题和答案
第1题：
第2题：
（ 5 ）堆排序是对直接选择排序的改进，在第一次选择出最小关键码的同时为以后的选择准备了条件。堆实质上是一棵 【 5 】 树结点的层次序列。
第3题：
第一趟 [ 11，19][4，5][7，13][2，10]
第二趟 [4，5，11，19][2，7，10，，13]
第三趟 [2，4，5，7，11，10，11，13](2)
第4题：
第5题：
堆是一种()排序。
A. 插入
B. 选择
C. 交换
D. 归并
第6题：
堆是一种有用的数据结构。下列关键码序列()是一个堆。
A.94，31，53，23，16，72
B.94，53，31，72，16，23
C.16，53，23，94，31，72
D.16，31，23，94，53，72
第7题：
堆排序是一种基于(35)的排序方法，(36)不是堆。
A．计数
B．插入
C．选择
D．归并
解析：堆排序是一种改进的选择排序方法。
对于n个元素的关键字序列{k1，k2，…，kn}，当且仅当满足下列关系时称其为堆：
若将此序列对应的一维数组(即以一维数组作为序列的存储结构)看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。
对于题目中给出的四个序列分别构造完全二叉树，如下图所示。
其中，(d)中的结点56，即不满足堆的定义。
第8题：
A. 39,41,57,80,47,46
B.39,41,46,80,47,57
C. 39,47,46,80,41,57
D.39,41,57,80,46,47
输出堆顶元素后,调整后的堆为回答（ ）。
A.41,47,46,80,57
B.41,57,46,80,47
C.41,57,80,47,46
D.41,80,46,47,57
参考答案：1.B
第9题：
从供选择的答案中选出应填入下列叙述中()内的正确答案：
堆是一种有用的数据结构。例如关键码序列(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：④ B：② C：② D：① E：⑤
第10题：
堆是一种特殊的数据结构，选项(55)是一个最大堆。堆排序是一种(56)排序，其时间复杂性为(57)。(58)是不稳定的排序算法。外排序是指(59)。
A．19，75，34，26，97，56
B．97，75，34，56，19，26
C．97，56，26，19，34，75
D．19，34，26，97，56，75