1、计算机学科专业基础综合数据结构-树与二叉树(二)及答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：44，分数：44.00)1.在下面关于树的相关概念的叙述中，正确的是_。 A.只有一个结点的二叉树的度为 1 B.二叉树的度一定为 2 C.二叉树的左右子树可任意交换 D.深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树（分数：1.00）A.B.C.D.2.已知一算术表达式的中缀形式为 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、分数：1.00）A.B.C.D.3.算术表达式 a+b*(c+d/e)转为后缀表达式后为_。 A.ab+cde/* B.abcde/+*+ C.abcde/*+ D.abcde*/+（分数：1.00）A.B.C.D.4.某二叉树的先序遍历序列为 IJKLMNO，中序遍历序列为 JLKINMO，则后序遍历序列是_。 A.JLKMNOI B.LKNJOMI C.LKJNOMI D.LKNOJMI（分数：1.00）A.B.C.D.5.设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 P，P 的右子树结点个数为 n，森林 F 中第一棵树的结点个数是_。 A.m-n B.m-n-1 C.n+
3、1 D.条件不足，无法确定（分数：1.00）A.B.C.D.6.二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是_。 A.先序遍历二叉树 B.判断两个指定位置的结点是否在同一层上 C.层次遍历二叉树 D.根据结点的值查找其存储位置（分数：1.00）A.B.C.D.7.设某二叉树中只有度为 0 和度为 2 的结点，如果此二叉树的高度为 100，那么此二叉树中所包含的结点数最少为_。 A.188 B.200 C.199 D.201（分数：1.00）A.B.C.D.8.树是结点的有限集合，一棵树中有_根结点。 A.有 0 个或 1 个 B.有 0 个或多个 C.有且只有一个 D.有 1
4、 个或 1 个以上（分数：1.00）A.B.C.D.9.下列二叉排序树中，满足平衡二叉树定义的是_。 A B C D （分数：1.00）A.B.C.D.10.把树的根结点的层数定义为 1，其他结点的层数等于其父结点所在层数加上 1。设 T 是一棵二叉树，K i和 Kj是 T 中子结点数小于 2 的结点中的任意两个，它们所在的层数分别为 K i和 K j，当关系式|K i-K j|1 一定成立时，则称 T 为一棵_。 A.满二叉树 B.二叉查找树 C.平衡二叉树 D.完全二叉树（分数：1.00）A.B.C.D.11.设森林 F 中有三棵树，第一、第二、第三棵树的结点个数分别为 M1、M 2和 M
5、3。与森林 F 对应的二叉树根结点的右子树上的结点个数是_。 A.M1 B.M1+M2 C.M3 D.M2+M3（分数：1.00）A.B.C.D.12.若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是_。 A.10 B.11 C.16 D.不确定（分数：1.00）A.B.C.D.13.具有 10 个叶结点的二叉树中有_个度为 2 的结点。 A.8 B.9 C.10 D.11（分数：1.00）A.B.C.D.14.在一棵度为 3 的树中，度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数为 2 个，则度为 0 的结点数为_个
6、。 A.4 B.5 C.6 D.7（分数：1.00）A.B.C.D.15.已知一棵二叉树，共有 n 个结点，那么此二叉树的高度为_。Anlog 2nBlog 2nC （分数：1.00）A.B.C.D.16.已知一棵二叉树，第 m 层上最多含有结点数为_。 A.2m B.2m-1-1 C.2m-1 D.2m-1（分数：1.00）A.B.C.D.17.有关二叉树下列说法正确的是_。 A.二叉树就是度为 2 的树 B.一棵二叉树的度可以小于 2 C.二叉树中至少有一个结点的度为 2 D.二叉树中任何一个结点的度都为 2（分数：1.00）A.B.C.D.18.一棵二叉树的前序遍历序列为 ABCDEFG
7、，它的中序遍历序列可能是_。 A.CABDEFG B.ABCDEFG C.DACEFBG D.BAECFDG（分数：1.00）A.B.C.D.19.已知一个二叉树有 1025 个结点，那么由此推断二叉树的高 h 为_。 A.11 B.10 C.111025 D.101024（分数：1.00）A.B.C.D.20.一棵完全二叉树，共有 n 个结点，那么，其叶结点数共有_个。 A.n/2 B.n C.(n-1)/2 D.(n+1)/2（分数：1.00）A.B.C.D.21._的遍历仍需要栈的支持。 A.前序线索树 B.中序线索树 C.后序线索树 D.中序线索树和前序线索树（分数：1.00）A.B.
8、C.D.22.已知一棵二叉树高度为 h，在此二叉树中只有度为 0 和度为 2 的结点，那么这棵二叉树的结点个数最少为_。 A.2h B.2h-1 C.2h+1 D.h+1（分数：1.00）A.B.C.D.23.设树 T 的度为 4，其中度为 1、2、3 和 4 的结点个数分别为 4、1、1、1，则 T 中的叶子数为_。 A.10 B.11 C.9 D.7（分数：1.00）A.B.C.D.24.用下列元素序列(22，8，62，35，48)构造平衡二叉树，当插入_时，会出现不平衡的现象。 A.22 B.35 C.48 D.62（分数：1.00）A.B.C.D.25.下面的算法实现了将二叉树中每一个
9、结点的左右子树互换。addQ(Q，bt)为进队的函数，delQ(Q)为出队的函数，empty(Q)为判别队列是否为空的函数，空白处应填的内容是_。typedef struct nodeint data;struct node*lchild,*rchild;btnode;void exchange(btnode *bt)btnode *p, *q;if(bt)addQ(Q,bt);while(!EMPTY(Q)p=delQ(Q);q= p-rchild;p-rchild= p-lchild;(U U /U /U)=q;if(p-lchild)(U U /U /U);if(p-rchild)add
10、Q(Q, p-rchild); A.p-lchild,delQ(Q,p-lchild) B.p-rchild,delQ(Q,p-lchild) C.p-lchild,addQ(Q,p-lchild) D.p-rchild,addQ(Q,p-lchild)（分数：1.00）A.B.C.D.26.已知有一棵叉树，其高度为 n，并且有且只有 n 个结点，那么二叉树的树形有_种。 A.nlog2n B.2n+1 C.2n-1 D.2n-1（分数：1.00）A.B.C.D.27.已知二叉排序树如下图所示，下列序列构造此二叉排序树不正确的是_。（分数：1.00）A.B.C.D.28.已知某平衡二叉树含有在
11、 15 个结点，25 为其中的一个结点，如果在此平衡二叉树上查找关键字为 25的结点，下列比较的次序合理的是_。 A.29，35 B.35，45，25 C.45，15，35，25 D.60，30，50，40，38，36（分数：1.00）A.B.C.D.29.利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素 30 要进行元素间的比较次数是_。 A.4 B.5 C.6 D.7（分数：1.00）A.B.C.D.30.构建一个哈夫曼树，如果给定权值的个数为 n，那么哈夫曼树的结点总数为_ A.不确定 B.2n C.2n+1 D.2n-1
12、（分数：1.00）A.B.C.D.31.已知某哈夫曼树的度为 m，其中叶结点个数为 n，那么非叶结点的个数为_。 An-1 B C D （分数：1.00）A.B.C.D.32.一棵哈夫曼树共有 99 个结点，对其进行哈夫曼编码，共能得到_种不同的编码。 A.48 B.50 C.99 D.100（分数：1.00）A.B.C.D.33.一棵含有 n 个结点的 k 叉树，可能达到的最大深度为_，最小深度为_。 A.n-k+1，log kn+1 B.n，log kn+1 C.n，log kn-1 D.n-k+1，log kn+1（分数：1.00）A.B.C.D.34.已知一棵满二叉树的结点个数为 20
13、 到 40 之间的素数，此二叉树的叶子结点有_个。 A.23 B.29 C.16 D.32（分数：1.00）A.B.C.D.35.有_棵不同的二叉树，其结点的前序序列为 a1，a 3，a n。ABCD （分数：1.00）A.B.C.D.36.有 n 个叶结点的非满的完全二叉树的高度为_。 A.2n+1 B.2n-1 C.log22n+1 D.log22n-1（分数：1.00）A.B.C.D.37.在一棵二叉树中，单分支结点数为 30，双分支结点数为 15，则叶子结点数为_。 A.13 B.16 C.17 D.47（分数：1.00）A.B.C.D.38.判断线索二叉树中某结点*p 有左孩子的条件
14、是_。 A.p-lchild=NULL B.p-lchild=0 C.p-ltag=0 D.p-ltag=1（分数：1.00）A.B.C.D.39.在线索二叉树中，结点*p 没有左子树的充要条件是_。 A.p-lchild=NULL B.p-ltag=1 C.p-ltag=1 且 p-lchild=NULL D.以上都不对（分数：1.00）A.B.C.D.40.如果 T1 是由有序树 T 转换而来的二叉树，那么 T 中结点的前序遍历序列就是 T1 中结点的_遍历序列。 A.前序 B.中序 C.后序 D.层次序（分数：1.00）A.B.C.D.41.在图中所示的 4 棵二叉树中，_不是完全二叉树
15、。（分数：1.00）A.B.C.D.42.一棵二叉树如下图所示，其中序遍历序列为_。（分数：1.00）A.B.C.D.43.有 n 个叶子结点的哈夫曼树的结点总数为_。 A.不确定 B.2n C.2n+1 D.2n-1（分数：1.00）A.B.C.D.44.如图所示的 T2 是由森林 T1 转换而来的二叉树，那么森林 T1 有_个叶结点。（分数：1.00）A.B.C.D.二、B综合应用题/B(总题数：15，分数：56.00)45.6 知一个二叉树，用二叉链表形式存储，给出此二叉树建立过程算法(可不描述结构体)。（分数：3.00）_46.判别给定的二叉树是否是完全二叉树，并给出设计的算法(可不描
16、述结构体)。（分数：3.00）_47.以孩子一兄弟表示法存储的森林的叶子结点数(要求描述结构)。（分数：3.00）_48.已知一棵二叉树的前序序列为：A，B，D，G，J，E，H，C，F，I，K，L；中序序列为：D，J，G，B，E，H，A，C，K，I，L，F。 (1)写出该二叉树的后序序列。 (2)画出该二叉树。 (3)求该二叉树的高度以及该二叉树中度为 2、1、0 的结点个数。（分数：3.00）_49.有 n 个结点的二叉树，已知叶结点个数为 n0。(1)写出求度为 1 的结点的个数的 n1的计算公式。(2)若此树是深度为 k 的完全二叉树，写出 n 为最小的公式。(3)若二叉树中仅有度为 0
17、 和度为 2 的结点，写出求该二叉树结点个数 n 的公式。（分数：4.00）_50.已知一棵树的结点表示如下，其中各兄弟结点是依次出现的，画出对应的二叉树。 （分数：4.00）_51.在一棵表示有序集 S 的二叉搜索树(binary search tree)中，任意一条从根到叶结点的路径将 S 分为3 部分：在该路径左边结点中的元素组成的集合 S1；在该路径上的结点中的元素组成的集合 S2；在该路径右边结点中的元素组成的集合 S3。S=S 1S 2S 3。若对于任意的 aS 1，bS 2，cS 3，是否总有 abc?为什么?（分数：4.00）_52.假定用两个一维数组 LN和 RN作为有 N
18、个结点 1，2，N 的二叉树的存储结构。Li和 Ri分别指示结点 i 的左儿子和右儿子；Li=0(Ri=0)表示 i 的左(右)儿子为空。试写一个算法，由 L 和 R 建立一个一维数组 Tn，使 Ti存放结点 i 的父亲；然后再写一个判别结点 U 是否为结点 V 的后代的算法。（分数：4.00）_53.试找出分别满足下面条件的所有二叉树： (1)前序序列和中序序列相同。 (2)中序序列和后序序列相同。 (3)前序序列和后序序列相同。 (4)前序、中序、后序序列均相同。（分数：4.00）_54.假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树 BT 中，写出计算该算术表达式值的算法。（
19、分数：4.00）_55.画出如下图所示的二叉树所对应的森林。 （分数：4.00）_56.下述编码中，哪一组不是前缀码? 00，01，10，11，0，1，00，11，0，10，110，111（分数：4.00）_57.假设用于通信的电文由字符集a，b，c，d，e，f，g，h中的字母构成，这 8 个字母在电文中出现的概率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 (1)为这 8 个字母设计哈夫曼编码。 (2)若用三位二进制数(07)对这 8 个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?（分数：4.00）_58.
20、有 n 个结点的完全二叉树存放在一维数组 A1n中，试据此建立一棵用二叉链表表示的二叉树，根由 tree 指向。(可不定义结构体)（分数：4.00）_59.已知深度为 h 的二叉树采用顺序存储结构已存放于数组 BT12h-1中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild，data，rchild)，根结点所在链结点的指针由 T 给出。（分数：4.00）_计算机学科专业基础综合数据结构-树与二叉树(二)答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：44，分数：44.00)1.在下面关于树的相关概念的叙述中，正确的是_。
21、 A.只有一个结点的二叉树的度为 1 B.二叉树的度一定为 2 C.二叉树的左右子树可任意交换 D.深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树（分数：1.00）A.B.C.D. 解析：只有一个结点的二叉树的度为零。二叉树的度可以为 0、1、2；二叉树的左右子树不能任意交换。2.已知一算术表达式的中缀形式为 A+B+C-D/E，后缀形式为 ABC*+DE/-，其前缀形式为_。 A.-A+B*C/DE B.-A+B*CD/E C.-+*ABC/DE D.-+A*BC/DE（分数：1.00）A.B.C.D. 解析：根据题目给出的中缀和后缀表达式可以得到其算术表达式为：(A+B*C
22、)-D/E，前缀表达式：-+A*BC/DE。3.算术表达式 a+b*(c+d/e)转为后缀表达式后为_。 A.ab+cde/* B.abcde/+*+ C.abcde/*+ D.abcde*/+（分数：1.00）A.B. C.D.解析：根据表达式 a+b*(c+d/e)可知其后缀表达式为 abcde/+*+。4.某二叉树的先序遍历序列为 IJKLMNO，中序遍历序列为 JLKINMO，则后序遍历序列是_。 A.JLKMNOI B.LKNJOMI C.LKJNOMI D.LKNOJMI（分数：1.00）A.B.C. D.解析：由先序和中序遍历序列确定一棵二叉树，再给出这棵二叉树的后序遍历序列。
23、* 由此图可以确认后序遍历的序列为 LKJNOMI。5.设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 P，P 的右子树结点个数为 n，森林 F 中第一棵树的结点个数是_。 A.m-n B.m-n-1 C.n+1 D.条件不足，无法确定（分数：1.00）A. B.C.D.解析：F 对应的二叉树共有 m 个结点，右子树上 n 个，左子树上有(m-n-1)个，第一株树包括根和左子树，共(m-n)个。6.二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是_。 A.先序遍历二叉树 B.判断两个指定位置的结点是否在同一层上 C.层次遍历二叉树 D.根据结点的值查找其存储位置（分
24、数：1.00）A.B. C.D.解析：选项 A、C、D 运算的时间复杂度都是 O(n)，而选项 B 的运算的时间复杂度为 O(1)，因为对于指定位置 p 和 q 的两个结点，判断是否在同一层上，只需判断两者*是否成立。7.设某二叉树中只有度为 0 和度为 2 的结点，如果此二叉树的高度为 100，那么此二叉树中所包含的结点数最少为_。 A.188 B.200 C.199 D.201（分数：1.00）A.B.C. D.解析：除根结点层只有 1 个结点外，其他各层均有两个结点，结点总数=2(100-1)+1=199。8.树是结点的有限集合，一棵树中有_根结点。 A.有 0 个或 1 个 B.有 0
25、 个或多个 C.有且只有一个 D.有 1 个或 1 个以上（分数：1.00）A.B.C. D.解析：根据树的基本定义可知，每个树只能有且只有一个根结点。9.下列二叉排序树中，满足平衡二叉树定义的是_。 A B C D （分数：1.00）A.B. C.D.解析：考查平衡二叉树的定义。 根据平衡二叉树的定义有，任意结点的左右子树高度差的绝对值不超过1。而其余三个选项均可以找到不符合的结点。10.把树的根结点的层数定义为 1，其他结点的层数等于其父结点所在层数加上 1。设 T 是一棵二叉树，K i和 Kj是 T 中子结点数小于 2 的结点中的任意两个，它们所在的层数分别为 K i和 K j，当关系式
26、|K i-K j|1 一定成立时，则称 T 为一棵_。 A.满二叉树 B.二叉查找树 C.平衡二叉树 D.完全二叉树（分数：1.00）A.B.C. D.解析：此题干的叙述符合平衡二叉树的定义。11.设森林 F 中有三棵树，第一、第二、第三棵树的结点个数分别为 M1、M 2和 M3。与森林 F 对应的二叉树根结点的右子树上的结点个数是_。 A.M1 B.M1+M2 C.M3 D.M2+M3（分数：1.00）A.B.C.D. 解析：森林转换成对应的二叉树，第一棵树的根结点作为此二叉树的根结点，第一棵树除根结点外其他结点时此二叉树的左子树。二叉树的右子树为第二棵树和第二棵树构成的，因此结点数为 M2
27、+M3。12.若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是_。 A.10 B.11 C.16 D.不确定（分数：1.00）A.B. C.D.解析：根据二叉树的性质可知，度为 0 的结点个数比度为 2 结点个数多一个，即 n0=n2+1。13.具有 10 个叶结点的二叉树中有_个度为 2 的结点。 A.8 B.9 C.10 D.11（分数：1.00）A.B. C.D.解析：根据二叉树的性质 n0=n2+1，可知度为 2 的结点个数为 9。14.在一棵度为 3 的树中，度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数为
28、2 个，则度为 0 的结点数为_个。 A.4 B.5 C.6 D.7（分数：1.00）A.B.C. D.解析：一棵度为 3 的树，总结点数 n=n0+n1+n2+n3，而总分支总数为 n00+n12+n21+n32，由于分支总数加 1 为结点总数，可得出 n0=6。15.已知一棵二叉树，共有 n 个结点，那么此二叉树的高度为_。Anlog 2nBlog 2nC （分数：1.00）A.B.C.D. 解析：已知一棵二叉树共有 n 个结点，但二叉树的形式没有给出，因此，二叉树的高度不能确定。16.已知一棵二叉树，第 m 层上最多含有结点数为_。 A.2m B.2m-1-1 C.2m-1 D.2m-1
29、（分数：1.00）A.B.C. D.解析：根据二叉树的性质，二叉树的第 m 层上最多有 2m-1。17.有关二叉树下列说法正确的是_。 A.二叉树就是度为 2 的树 B.一棵二叉树的度可以小于 2 C.二叉树中至少有一个结点的度为 2 D.二叉树中任何一个结点的度都为 2（分数：1.00）A.B. C.D.解析：本题考查二叉树的概念。18.一棵二叉树的前序遍历序列为 ABCDEFG，它的中序遍历序列可能是_。 A.CABDEFG B.ABCDEFG C.DACEFBG D.BAECFDG（分数：1.00）A.B. C.D.解析：由题可得 A 为根结点，并且 B 为 A 的孩子结点。选项 A，C
30、 应为 A 的左孩子，其前序序列应为AC。选项 B，当 B 为 A 的右孩子，C 为 B 的右孩子时，满足题目要求。选项 C，类似选项 A，其前序序列应为 AD。选项 D，B 为 A 的左孩子，C 为 A 的右子树的根，E 为 C 的左子树，FDG 为 C 的右子树，其前序序列应为 ABEC。19.已知一个二叉树有 1025 个结点，那么由此推断二叉树的高 h 为_。 A.11 B.10 C.111025 D.101024（分数：1.00）A.B.C. D.解析：右完全二叉树中 10252 10，即最少需要 11 层，最多需要有 1025 层。20.一棵完全二叉树，共有 n 个结点，那么，其叶
31、结点数共有_个。 A.n/2 B.n C.(n-1)/2 D.(n+1)/2（分数：1.00）A.B.C.D. 解析：此问题可以利用二叉树及完全二叉树的性质来求解。 设 i、j、k 分别为度为 0、1、2 的结点数目，则 n=i+j+k。 根据二叉树的性质有 i=k+1，即 k=i-1，代入上式，得 n=2i+j-1，即 i=(n-j+1)/2。 由于完全二叉树中最多只有一个度为 1 的结点，同时考虑到 i 为整数， (1)当 j=0 时，此时 n=i+k=2k+1 为奇数，则 i=(n+1)/2： (2)当 j=1 时，此时 n=i+k+1=2k+2 为偶数，则 i=(n+1)/2 向下取整
32、。 所以选 D。21._的遍历仍需要栈的支持。 A.前序线索树 B.中序线索树 C.后序线索树 D.中序线索树和前序线索树（分数：1.00）A.B.C. D.解析：由于后序遍历先访问子树后访问根结点，从本质上要求运行栈中存放祖先的信息，即使对二叉树进行后序线索化，仍然不能脱离栈的支持对此二叉树进行遍历。22.已知一棵二叉树高度为 h，在此二叉树中只有度为 0 和度为 2 的结点，那么这棵二叉树的结点个数最少为_。 A.2h B.2h-1 C.2h+1 D.h+1（分数：1.00）A.B. C.D.解析：23.设树 T 的度为 4，其中度为 1、2、3 和 4 的结点个数分别为 4、1、1、1，
33、则 T 中的叶子数为_。 A.10 B.11 C.9 D.7（分数：1.00）A.B.C.D. 解析：根据题中条件可知，14+21+3+4+1=4+1+1+1+n 0，由此可以得出：n 0=14+21+3+4+1-(4+1+1+1)=14-7=7。24.用下列元素序列(22，8，62，35，48)构造平衡二叉树，当插入_时，会出现不平衡的现象。 A.22 B.35 C.48 D.62（分数：1.00）A.B.C. D.解析：由题中所给的结点序列构造二叉排序树的过程如下图： * 当插入 48 后，首次出现不平衡子树，虚线框内即为最小不平衡子树。25.下面的算法实现了将二叉树中每一个结点的左右子树
34、互换。addQ(Q，bt)为进队的函数，delQ(Q)为出队的函数，empty(Q)为判别队列是否为空的函数，空白处应填的内容是_。typedef struct nodeint data;struct node*lchild,*rchild;btnode;void exchange(btnode *bt)btnode *p, *q;if(bt)addQ(Q,bt);while(!EMPTY(Q)p=delQ(Q);q= p-rchild;p-rchild= p-lchild;(U U /U /U)=q;if(p-lchild)(U U /U /U);if(p-rchild)addQ(Q, p-
35、rchild); A.p-lchild,delQ(Q,p-lchild) B.p-rchild,delQ(Q,p-lchild) C.p-lchild,addQ(Q,p-lchild) D.p-rchild,addQ(Q,p-lchild)（分数：1.00）A.B.C. D.解析：26.已知有一棵叉树，其高度为 n，并且有且只有 n 个结点，那么二叉树的树形有_种。 A.nlog2n B.2n+1 C.2n-1 D.2n-1（分数：1.00）A.B.C.D. 解析：由题可得，每层有一个结点，从根结点往下，每个结点都有做左孩子右孩子两种情况，由概率知识可得，二叉树共有 2n-1种树形。27.已知
36、二叉排序树如下图所示，下列序列构造此二叉排序树不正确的是_。（分数：1.00）A.B.C. D.解析：将各选项中对应的二叉排序树画出即可得到答案。28.已知某平衡二叉树含有在 15 个结点，25 为其中的一个结点，如果在此平衡二叉树上查找关键字为 25的结点，下列比较的次序合理的是_。 A.29，35 B.35，45，25 C.45，15，35，25 D.60，30，50，40，38，36（分数：1.00）A.B.C. D.解析：设 Nh表示深度为 h 的平衡二叉树中含有的最少结点数，有：N 0=0，N 1=1，N 2=2，N h=Nh-1+Nh-2+1，N 3=4，N 4=7，N 5=12，
37、N 6=2015。也就是说，高度为 6 的平衡二叉树最少有 20 个结点，因此 15 个结点的平衡二叉树的高度为 5，而最小叶子结点的层数为 3，所以选项 D 错误。而 A 和 B 的查找过程不能构成二叉排序树，因此 A、B 错误。29.利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素 30 要进行元素间的比较次数是_。 A.4 B.5 C.6 D.7（分数：1.00）A.B. C.D.解析：利用逐点插入法建立二叉排序树是从空树开始，通过查找，将每个结点作为一个叶子插入。按题目中数据的输入次序建立的二叉排序树如下图所示，查找元素
38、 30 的比较次数为 5 次。 * *30.构建一个哈夫曼树，如果给定权值的个数为 n，那么哈夫曼树的结点总数为_ A.不确定 B.2n C.2n+1 D.2n-1（分数：1.00）A.B.C.D. 解析：哈夫曼树中只有度为 0 和度为 2 的结点，即 N=n0+n2，而根据二叉树的性质：n 0=n2+1，可知 n0=n，那么 n2=n-1，N=n+n-1=2n-1。31.已知某哈夫曼树的度为 m，其中叶结点个数为 n，那么非叶结点的个数为_。 An-1 B C D （分数：1.00）A.B.C. D.解析：度为 m 的结点个数为 nm叶子结点个数为 n，mn m+1=nm+n，mn m=nm
39、+n-1*nm=*。32.一棵哈夫曼树共有 99 个结点，对其进行哈夫曼编码，共能得到_种不同的编码。 A.48 B.50 C.99 D.100（分数：1.00）A.B. C.D.解析：本题考查哈夫曼树的性质。哈夫曼树中只有度为 2 和度为 0 的结点，哈夫曼编码是对哈夫曼树中的叶子结点编码。根据树的性质 N0=N2+1，故 N0=(N2+N0+1)/2=(99+1)/2=50，哈夫曼树共有 50 个叶子结点，所以共能得到 50 个不同的码字。33.一棵含有 n 个结点的 k 叉树，可能达到的最大深度为_，最小深度为_。 A.n-k+1，log kn+1 B.n，log kn+1 C.n，lo
40、g kn-1 D.n-k+1，log kn+1（分数：1.00）A. B.C.D.解析：当 k 叉树种只有一个层的分支数为 n，其他层的分指数均为 1 时，此时的树具有最大的深度为：n-k+1。当该 k 叉树为完全 k 叉树时，其深度最小。参照二叉树的性质可知，其深度为：log kn+1。34.已知一棵满二叉树的结点个数为 20 到 40 之间的素数，此二叉树的叶子结点有_个。 A.23 B.29 C.16 D.32（分数：1.00）A.B.C. D.解析：一棵深度为 h 的满二叉树的结点个数为 2h-1，则有 202 h-140，即 212 h41，h=5(总结点数=25-1=31，为素数)
41、。满二叉树中叶子结点均集中在最底层，所以结点个数=2 5-1=16 个。35.有_棵不同的二叉树，其结点的前序序列为 a1，a 3，a n。ABCD （分数：1.00）A. B.C.D.解析：这是一个变形的求 n 个结点的互不相似的二叉树个数问题，设 T(n)表示含 n 个结点的二叉树个数，T(0)=T(1)=1，T(2)=2，T(n)=T(n-1)T(0)+T(n-2)T(1)+T(0)T(n-1)，而递归方程的解为*。36.有 n 个叶结点的非满的完全二叉树的高度为_。 A.2n+1 B.2n-1 C.log22n+1 D.log22n-1（分数：1.00）A. B.C.D.解析：设 j、k 分别为度为 1、2 的结点数目，则结点总数 m=n+j+k；由于是非满的，所以必有 j=1，且n=k+1，因此有 m=2n。设树的高度为 h，具有 n 个结点的完全二叉树的深度为 l
