一、选择题
1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为
( )
A ．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE
2. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子
数为（ ）
A ．5 B．6 C．7 D．8
5. 在下述结论中，正确的是（ ）
①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意
交换;
④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A ．①②③ B．②③④ C．②④ D．①④
6. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n, 森林F
中第一棵树的结点个数是（ ）
A ．m-n B．m-n-1 C．n+1 D．条件不足，无法确定
8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A ．9 B．11 C．15 D．不确定
9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2
个，则度为0的结点数为（ ）个
A ．4 B．5 C．6 D．7 【哈尔滨工业大学 2001 二、2 （2
分）】
10．设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林
F 对应的二叉树根结点的右子树上的结点个数是（ ）。
A ．M1 B．M1+M2 C．M3 D．M2+M3
11．具有10个叶结点的二叉树中有（ ）个度为2的结点。
A ．8 B．9 C．10 D．ll
12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
A ． 250 B． 500 C．254 D．505 E．以上答案都不对
13. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )
A ．不确定 B．2n C．2n+1 D．2n-1
15．若度为m 的哈夫曼树中，其叶结点个数为n ，则非叶结点的个数为（ ）。
A ．n-1 B ．⎣n/m⎦-1 C ．⎡(n-1)/(m-1)⎤ D ． ⎡n/(m-1)⎤-1
E ．⎡(n+1)/(m+1)⎤-1
16. 有关二叉树下列说法正确的是（ ）
A ．二叉树的度为2 B．一棵二叉树的度可以小于2
C ．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
17．二叉树的第I 层上最多含有结点数为（ ）
I I-1I-1I A ．2 B． 2-1 C． 2 D．2 -1
18. 一个具有1025个结点的二叉树的高h 为（ ）
A ．11 B．10 C．11至1025之间 D．10至1024之间
19．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有( )结点
A ．2h B．2h-1 C．2h+1 D．h+1
20．对于有n 个结点的二叉树, 其高度为（ ）
A ．nlog 2n B．log 2n C．⎣log 2n ⎦|+1 D．不确定
21. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）
A ．⎣logn ⎦+1 B．logn+1 C．⎣logn ⎦ D．logn-1
22．深度为h 的满m 叉树的第k 层有（ ）个结点。(1=
k-1 k h-1h A ．m B．m -1 C．m D．m -1
23．在一棵高度为k 的满二叉树中，结点总数为（ ）
k-1 k k k A ．2B ．2C ．2-1 D．⎣log2⎦+1
24．高度为 K的二叉树最大的结点数为（ ）。
k k-1k k-1A ．2 B．2 C．2 -1 D．2-1
25. 一棵树高为K 的完全二叉树至少有（ ）个结点。
k k-1k-1k A ．2 –1 B. 2 –1 C. 2 D. 2
26. 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）
A ．4 B．5 C．6 D．7
27. 利用二叉链表存储树，则根结点的右指针是（ ）。
A ．指向最左孩子 B．指向最右孩子 C．空 D．非空
28．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。
A ．先序 B. 中序 C. 后序 D. 从根开始按层次遍历
29．树的后根遍历序列等同于该树对应的二叉树的( ).
A. 先序序列 B. 中序序列 C. 后序序列
30．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。
A ．前序 B．中序 C．后序 D．按层次
31．在下列存储形式中，哪一个不是树的存储形式？（ ）
A ．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法
32．一棵二叉树的前序遍历序列为ABCDEFG ，它的中序遍历序列可能是（ ）
A ．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG
33．已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果为（ ）。
A ．CBEFDA B． FEDCBA C． CBEDFA D．不定
39. 某二叉树T 有n 个结点，设按某种顺序对T 中的每个结点进行编号，编号为1，2，… ，n ，且有如下性质：T 中任一结点V ，其编号等于左子树上的最小编号减1，而V 的右子树的结点中，其最小编号等于V 左子树上结点的最大编号加1。这时是按( )编号的。
A. 中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序
42．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）
A ．所有的结点均无左孩子B ．所有的结点均无右孩子C ．只有一个叶子结点D ．是任意一棵二叉树
43．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）
A ．都不相同 B ．完全相同 C．先序和中序相同，而与后序不同
D．中序和后序相同，而与先序不同
44．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
A ．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树
45．在完全二叉树中，若一个结点是叶结点，则它没（ ）。
A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点
47. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( )
A ．不确定 B. 0 C. 1 D. 2
48. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。
A. 0 B. 1 C. 2 D. 不确定
49. 若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则x 的前驱为( )
A.X 的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点
51. 线索二叉树是一种（ ）结构。
A ． 逻辑 B． 逻辑和存储 C． 物理 D．线性
52．n 个结点的线索二叉树上含有的线索数为（ ）
A ．2n B．n －l C．n ＋l D．n
55. 设F 是一个森林，B 是由F 变换得的二叉树。若F 中有n 个非终端结点，则B 中右指针域为空的结点有（ ）个。
A ． n-1 B．n C． n+1 D． n+2
58．由3 个结点可以构造出多少种不同的二叉树？（ ）
A ．2 B．3 C．4 D．5
64. 当一棵有n 个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A[l..n]中时，数组中第i 个结点的左孩子为（ ）
A ．A[2i](2i=