目录
一、二叉树
二、堆
三、遍历二叉树
一、二叉树
-
某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）。
A. 不存在这样的二叉树
B. 200
C. 198
D. 199
-
下列数据结构中，不适合采用顺序存储结构的是（ ）。
A. 非完全二叉树
B. 堆
C. 队列
D. 栈
-
在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）。
A. n
B. n + 1
C. n - 1
D. n / 2
-
一棵完全二叉树的节点数位为 531 个，那么这棵树的高度为（ ）。
A. 11
B. 10
C. 8
D. 12
-
一个具有 767 个节点的完全二叉树，其叶子节点个数为（）。
A. 383
B. 384
C. 385
D. 386
答案：
由二叉树的性质
可知，该二叉树中的叶子结点数为 200。
对于一般二叉树来说，采用顺序存储结构会造成空间的极大浪费。
对于完全二叉树，如果有度为 1 的结点，则只可能有一个，那么由
可知，该完全二叉树中有一个度为 1 的结点，叶子结点个数则为 n。
根据完全二叉树的性质 h = ⌈
⌉可知，这棵完全二叉树的高度为 10。
和第 3 题类似，，所以该完全二叉树中，度为 1 的结点个数为 0，叶子结点个数则为 384。
二、堆
-
下列关键字序列为堆的是（）。
A. { 100, 60, 70, 50, 32, 65 }
B. { 60, 70, 65, 50, 32, 100 }
C. { 65, 100, 70, 32, 50, 60 } D. { 70, 65, 100, 32, 50, 60 }
E. { 32, 50, 100, 70, 65, 60 }
F. { 50, 100, 70, 65, 60, 32 }
-
已知小根堆为 { 8, 15, 10, 21, 34, 16, 12 }，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次 数是（）。
A. 1
B. 2
C. 3
D. 4
-
一组记录排序码为 { 5, 11, 7, 2, 3, 17 }，则利用堆排序方法建立的初始堆为（）。
A. { 11, 5, 7, 2, 3, 17 }
B. { 11, 5, 7, 2, 17, 3 }
C. { 17, 11, 7, 2, 3, 5 }
D. { 17, 11, 7, 5, 3, 2 }
E. { 17, 7, 11, 3, 5, 2 }
F. { 17, 7, 11, 3, 2, 5 }
-
最小堆 { 0, 3, 2, 5, 7, 4, 6, 8 }，在删除堆顶元素 0 之后，其结果是（）。
A. { 3, 2, 5, 7, 4, 6, 8 }
B. { 2, 3, 5, 7, 4, 6, 8 }
C. { 2, 3, 4, 5, 7, 8, 6 }
D. { 2, 3, 4, 5, 6, 7, 8 }
答案：
A 是大根堆。
将堆顶元素 8 和堆中最后一个元素 12 交换并删除堆顶元素 8 后，向下调整重新建堆。
首先比较 12 的左右孩子，然后用较小的关键字和 12 进行比较，由于 12 > 10，所以交换这两个元素，然后接着向下调整。因为此时以 12 为根的子树没有右孩子，所以 12 只需要和其左孩子进行比较，由于 12 < 16，所以不需要再调整了。整个过程中，关键字之间的比较次数为 3 次。
答案为 C。
答案为 C。
三、遍历二叉树
-
某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH。该完全二叉树的前序序列为（ ）。
A. ABDHECFG
B. ABCDEFGH
C. HDBEAFCG
D. HDEBFGCA
-
二叉树的先序序列和中序序列分别为 EFHIGJK 和 HFIEJKG，则二叉树根结点为（）。
A. E
B. F
C. G
D. H
-
设一课二叉树的中序遍历序列为 BADCE，后序遍历序列为 BDECA，则二叉树前序遍历序列为（）。
A. ADBCE
B. DECAB
C. DEBAC
D. ABCDE
-
某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列 为（）。
A. FEDCBA
B. CBAFED
C. DEFCBA
D. ABCDE
答案：
因为该二叉树是完全二叉树，所以可以根据层序序列唯一地确定这棵二叉树，并且该完全二叉树的前序序列为 ABDHECFG。
二叉树先序序列中的第一个结点 E 一定是根结点。
可以由二叉树的先序序列和后序序列唯一地确定这棵二叉树，并且该二叉树的前序遍历序列为 ABCDE。
和第 3 题类似，该二叉树的层序序列为 FEDCBA
