参考教材：数据结构教程（Java语言描述) 作者：李春葆
1 . 容易 （3分）现有一"遗传”关系，设x是y的父亲，则x可以把他的属性遗传给y。表示该遗传关系最适合的数据结构为______。
A. 数组
B. 树
C. 图
D. 线性表
2 . 容易 （3分）一棵高度为h、结点个数为n的m（m≥3）次树中，其分支数是______。
A. nh
B. n+h
C. n-1
D. h-1
3 . 容易 （3分）若一棵3次树中有2个度为3的结点，1个度为2的结点，2个度为1的结点，该树一共有______ 个结点。
A. 5
B. 8
C. 10
D. 11
4 . 容易 （3分）一棵度为5、结点个数为n的树采用孩子链存储结构时，其中空指针的个数是______。
A. 5n
B. 4n+1
C. 4n
D. 4n-1
5 . 容易 （3分）以下关于二叉树的说法中正确的是______。
A. 二叉树中每个结点的度均为2
B. 二叉树中至少有一个结点的度为2
C. 二叉树中每个结点的度可以小于2
D. 二叉树中至少有一个结点
6 . 容易 （3分）若一棵有n个结点的二叉树，其中所有分支结点的度均为k，该树中的叶子结点个数是______。
A. n(k-1)/k
B. n-k
C. (n+1)/k
D. (nk-n+1)/k
7 . 容易 （3分）若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为______。
A. 9
B. 11
C. 15
D. 不确定
8 . 容易 （3分）具有10个叶子结点的二叉树中有______ 个度为2的结点。
A. 8
B. 9
C. 10
D. 11
9 . 容易 （3分）一棵二叉树中有7个叶子结点和5个单分支结点，其总共有______ 个结点。
A. 16
B. 18
C. 12
D. 31
10 . 容易 （3分）一棵二叉树中有35个结点，其中所有结点的度之和是______。
A. 35
B. 16
C. 33
D. 34
11 . 容易 （3分）高度为5的二叉树至多有______ 个结点。
A. 16
B. 32
C. 31
D. 10
12 . 容易 （3分）高度为5的二叉树至少有______ 个结点。
A. 5
B. 6
C. 7
D. 31
13 . 容易 （3分）二叉树第i层上至多有______ 个结点。
A. 2i
B. 2i-1
C. 2i-1-1
D. 2i-1
14 . 容易 （4分）一个具有1025个结点的二叉树的高h为______。
A. 11
B. 10
C. 11～1025
D. 12～1024
15 . 容易 （4分）一棵完全二叉树中有501个叶子结点，则至少有______ 个结点。
A. 501
B. 502
C. 1001
D. 1002
16 . 容易 （4分）一棵完全二叉树中有501个叶子结点，则至多有______ 个结点。
A. 501
B. 502
C. 1001
D. 1002
17 . 容易 （4分）一棵高度为8的完全二叉树至少有______ 叶子结点。
A. 63
B. 64
C. 127
D. 128
18 . 容易 （4分）棵高度为8的完全二叉树至多有______ 叶子结点。
A. 63
B. 64
C. 127
D. 128
19 . 容易 （4分）一棵满二叉树中127个结点，其中叶子结点的个数是______。
A. 63
B. 64
C. 65
D. 不确定
20 . 容易 （4分）一棵满二叉树共有64个叶子结点，则其结点个数为______。
A. 64
B. 65
C. 127
D. 128
21 . 容易 （4分）设森林F中有3棵树，第一、第二和第三棵树的结点个数分别为9、8和7，则与森林F对应的二叉树根结点的右子树上的结点个数是______。
A. 16
B. 15
C. 7
D. 17
22 . 容易 （4分）如果一棵二叉树B是由一棵树T转换而来的二叉树，那么T中结点的先根序列对应B的______ 序列。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
23 . 容易 （4分）设一棵二叉树B是由森林T转换而来的，若T中有n个非叶子结点，则二叉树B中无右孩子的结点个数为______。
A. n-1
B. n
C. n+1
D. n+2
24 . 容易 （3分）某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是______。
A. 空或只有一个结点
B. 完全二叉树
C. 二叉排序树
D. 高度等于其结点数
25 . 容易 （3分）一棵二叉树的先序序列为ABCDEFG，它的中序序列可能是______。
A. CABDEFG
B. ABCDEFG
C. DACEFBG
D. ADCFEGB
26 . 容易 （3分）一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为______。
A. CBEFDA
B. FEDCBA
C. CBEDFA
D. 不确定
27 . 容易 （3分）由含n个结点的二叉树线索化后有______ 个线索（不计头结点）。
A. 2n
B. n+1
C. n-1
D. 2n-1
28 . 容易 （3分）若x是中序线索二叉树中一个有左孩子的结点，且不是根结点，则x的前驱结点为______。
A. x的双亲结点
B. x的右子树中最左下结点
C. x的左子树中最右下结点
D. x的左子树中最右下结点
29 . 容易 （3分）一棵哈夫曼树中共有199个结点，它用于多少个字符的编码______。
A. 99
B. 100
C. 101
D. 199
30 . 容易 （3分）根据使用频率为5个字符设计的哈夫曼编码不可能是______。
A. 000，001，010，011，1
B. 0000，0001，001，01，1
C. 000，001，01，10，11
D. 00，100，101，110，111