判断题
1.任何最小堆的前序遍历结果是有序的（从小到大）。
T
F
2.任何最小堆中从根结点到任一叶结点路径上的所有结点是有序的（从小到大）。
T
F
3.在有N个元素的最大堆中，随机访问任意键值的操作可以在O(logN)时间完成。
T
F
4.一棵有124个结点的完全二叉树，其叶结点个数是确定的。
T
F
5.完全二叉树中，若一个结点没有左孩子，则它必是树叶。
T
F
6.完全二叉树的存储结构通常采用顺序存储结构。
T
F
选择题
1.堆的形状是一棵：
A.二叉搜索树
B.满二叉树
C.非二叉树
D.完全二叉树
2.创建一个初始堆，含有N个记录，其时间复杂度是：
A.O(logN)
B.O(N)
C.O(NlogN)
D.O(N2)
3.哪种树，树中任何结点到根结点路径上的各结点值是有序的？
A.二叉搜索树
B.完全二叉树
C.堆
D.以上都不是
4.将6、4、3、5、8、9顺序插入初始为空的最大堆（大根堆）中，那么插入完成后堆顶的元素为：
A.3
B.5
C.6
D.9
5.下列的序列中，哪一组是堆？
A.37,99,45,33,66,10,22,13
B.99,45,66,13,37,10,22,33
C.99,66,45,33,37,10,22,13
D.99,66,22,33,37,13,45,10
6.已知关键字序列（5，8，12，19，28，20，15，22）是最小堆（小根堆），插入关键字3，调整后得到的最小堆是：
A.3，5，12，8，28，20，15，22，19
B.3，5，12，19，20，15，22，8，28
C.3，8，12，5，20，15，22，28，19
D.3，12，5，8，28，20，15，22，19
7.将10、12、1、14、6、5、8、15、3、9、7逐个按顺序插入到初始为空的最小堆（小根堆）中，然后连续执行两次删除最小元素操作（DeleteMin），此后堆顶的元素是什么？
A.5
B.6
C.7
D.9
堆的删除要注意需要把堆尾元素替换掉堆的根结点，然后下滤。
8.将 {28, 15, 42, 18, 22, 5, 40} 逐个按顺序插入到初始为空的最小堆（小根堆）中。则该树的前序遍历结果为：
A.5, 18, 15, 28, 22, 42, 40
B.5, 15, 18, 22, 28, 42, 40
C.5, 18, 28, 22, 15, 42, 40
D.5, 15, 28, 18, 22, 42, 40
9.设最小堆（小根堆）的层序遍历结果为{1, 3, 2, 5, 4, 7, 6}。用线性时间复杂度的算法将该堆调整为最大堆（大根堆），则该树的中序遍历结果为：
A.3, 5, 4, 2, 6, 1, 7
B.1, 4, 3, 7, 2, 6, 5
C.3, 5, 4, 7, 2, 6, 1
D.4, 1, 3, 7, 6, 2, 5
线性时间复杂度算法，指的是，从n/2的位置开始，建堆（下滤元素）。
10.在有n（>1）个元素的最大堆（大根堆）中，最小元的数组下标可以是：
A.1
B.⌊n/2⌋−1
C.⌊n/2⌋
D.⌊n/2⌋+2
最小元下标一定大于⌊n/2⌋。
11.在将数据序列（ 6, 1, 5, 9, 8, 4, 7 ）建成大根堆时，正确的序列变化过程是：
A.6,1,7,9,8,4,5 → 6,9,7,1,8,4,5 → 9,6,
7,1,8,4,5 → 9,8,7,1,6,4,5
B.6,9,5,1,8,4,7 → 6,9,7,1,8,4,5 → 9,6,7,1,8,4,
5 → 9,8,7,1,6,4,5
C.6,9,5,1,8,4,7 → 9,6,5,1,8,4,7 → 9,6,7,1,8,4,
5 → 9,8,7,1,6,4,5
D.6,1,7,9,8,4,5 → 7,1,6,9,8,4,5 → 7,9,6,1,8,4,
5 → 9,7,6,1,8,4,5 → 9,8,6,1,7,4,5
12.在一个有2333个元素的最小堆中，下列哪个下标不可能是最大元的位置？
A.1116
B.1167
C.2047
D.2232
13.在下述结论中，正确的是：
① 只有2个结点的树的度为1；
② 二叉树的度为2；
③ 二叉树的左右子树可任意交换；
④ 在最大堆（大顶堆）中，从根到任意其它结点的路径上的键值一定是按非递增有序排列的。
A.①④
B.②
C.①②③
D.②③④
14.以下各组序列不属于堆的是（）。
A.(100,85,98,77,80,60,82,40,20,10,66)
B.(10,20,40,60,66,77,80,82,85,98,100)
C.(100,85,40,77,80,60,66,98,82,10,20)
D.(100,98,85,82,80,77,66,60,40,20,10)
15.堆是满足一定条件的（）。
A.完全二叉树
B.队列
C.栈
D.线性表
16.下列四个序列中，属于堆的是（）。
A.（75,65,30,15,25,45,20,10）
B.（75,45,65,30,15,25,20,10）
C.（75,45,65,10,25,30,20,15）
D.（75,65,45,10,30,25,20,15）
17.设最小堆（小根堆）的层序遍历结果为{5, 18, 15, 28, 22, 42, 40}。用线性时间复杂度的算法将该堆调整为最大堆（大根堆），则该树的中序遍历结果为：
A.18, 28, 22, 15, 40, 5, 42
B.18, 28, 22, 42, 15, 40, 5
C.5, 22, 18, 42, 15, 40, 28
D.22, 5, 18, 42, 40, 15, 28
18.对最小堆（小顶堆）{1,3,2,6,7,5,4,15,14,12,9,10,11,13,8} 进行三次删除最小元的操作后，结果序列为：
A.4,5,6,7,8,9,10,11,12,13,14,15
B.4,6,5,13,7,10,8,15,14,12,9,11
C.4,6,5,12,7,10,8,15,14,9,13,11
D.4,5,6,12,7,10,8,15,14,13,9,11
19.用线性时间复杂度的算法将给定序列{ 28, 12, 5, 8, 19, 20, 15, 22 }调整为最大堆（大根堆），然后插入30。则结果序列为：
A.{ 5, 8, 28, 12, 19, 20, 15, 22, 30 }
B.{ 30, 28, 20, 22, 12, 5, 15, 8, 19 }
C.{ 30, 28, 22, 20, 19, 15, 12, 8, 5 }
D.{ 30, 28, 20, 22, 19, 5, 15, 8, 12 }
堆的插入算法：插入到最后面，然后上浮。