树与二叉树.doc
树与二叉树
(总分：228.00，做题时间：90分钟)
一、单项选择题(总题数：24，分数：48.00)
1.具有10个叶结点的二叉树中有( )个度为2的结点。
（分数：2.00）
A.8
B.9
C.10
D.11
2.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是( )。
（分数：2.00）
A.(100，80，90，60，120，110，130)
B.(100，120，110，130，80，60，90)
C.(100，60，80，90，120，110，130)
D.(100，80，60，90，120，130，110)
3.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。
（分数：2.00）
A.不确定
B.0
C.1
D.2
4.中缀表达式D/C“A+B*E—D*F的前缀表达式为( )。
（分数：2.00）
A.-+/D^CA*BE*DF
B.DCA^/BE*+DF*-
C.-C^A+/D*BE*DF
D.-+/D^C*ABE*DF
5.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有( )个。
（分数：2.00）
A.n-1
B.n
C.n+1
D.n+2
6.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是( )。
（分数：2.00）
A.CABDEFG
B.ABCDEFG
C.DACEFBG
D.ADCFEG
7.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为( )个。
（分数：2.00）
A.4
B.5
C.6
D.7二叉树定义
8.设有一表示算术表达式的二叉树(见图)，它所表示的算术表达式是( )。
2.00）
A.
B.
C.
D.
9.已知一棵二叉树先序遍历结果为ABDEFG，中序遍历结果为BAEDGF，则后序遍历结果为( )。
（分数：2.00）
A.BCDEFA
B.BFDECA
C.BEGFDA
D.BEFGDA
10.设某哈夫曼树中有199个结点，则该哈夫曼树中有( )个叶子结点。
（分数：2.00）
A.99
B.100
C.101
D.102
11.设某棵二叉树的高度为10，则该二叉树上的叶子结点最多有( )。
（分数：2.00）
A.20
B.255
C.511
D.1023
12.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组]中时，数组中第i个结点的左孩子为( )。
（分数：2.00）
A.A [2i](2i＜-n)
B.A[2i+1](2i+1＜-n)
C.A[i/2]
D.无法确定
13.下列所示各图中是中序线索化二叉树的是( )。
2.00）
A.
B.
D.
14.设一棵m叉树中有N，个度数为1的结点，N2个度数为2的结点，……，N m个度数为m的结点，则该树中共有( )个叶子结点。
2.00）
A.
B.
C.
D.
15.由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。
（分数：2.00）
A.24
B.48
C.72
D.53
16.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( )。
（分数：2.00）
A.9
B.11
C.15
D.不确定
17.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足( )。
（分数：2.00）
A.所有的结点均无左孩子
B.所有的结点均无右孩子
C.只有一个叶子结点
D.是任意一棵二叉树
18.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。
（分数：2.00）
A.250
B.500
C.501
D.505
19.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足( )。
（分数：2.00）
A.所有的结点均无左孩子
B.所有的结点均无右孩子
C.只有一个叶子结点
D.是任意一棵二叉树
20.设某棵三叉树中有40个结点，则该三叉树的最小高度为( )。
（分数：2.00）
A.3
C.5
D.6
21.下列二叉树中，不平衡的二叉树是( )。
2.00）
A.
B.
C.
D.
22.下面几个符号串编码集合中，不是前缀编码的是( )。
（分数：2.00）
A.0，10，110，1111
B.11，10，001，101，0001
C.00，010，0110，1000
D.b，c，aa，ac，aba，abb，abc
23.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数为( )。
（分数：2.00）
A.5
B.6
C.7
D.8
24.一个具有1025个结点的二叉树的高h为( )。
（分数：2.00）
A.11
B.10
C.11至1025之间
D.10至1024之间
二、综合应用题(总题数：18，分数：180.00)
25.要求二叉树按二叉链表形式存储，并且：
(1)写一个建立二叉树的算法。
(2)写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。
（分数：10.00）
__________________________________________________________________________________________ 26.设某二叉树的前序遍历序列为：ABCDEFGGI，中序遍历序列为：BCAEDGHFI
(1)试画出该二叉树；
(2)写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。
(3)设具有四个结点的二叉树的前序遍历序列为abcd；S为长度等于4的由a，b，c，d排列构成的字符序列，若任取S作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树?为什么?试列出具有4个结点二叉树的全部形态及相应的中序遍历序列。
（分数：10.00）
__________________________________________________________________________________________

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。