计算机专业基础综合数据结构（树与二叉树）-试卷2
(总分：64.00，做题时间：90分钟)
一、 单项选择题(总题数：23，分数：46.00)
1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00） __________________________________________________________________________________________ 解析：
2.设树T的度为4，其中度为1、2、3和4的结点个数分别为4、1、1、1，则T中的叶子数为( )。 （分数：2.00） A.10 B.11 C.9 D.7 √
解析：解析：根据题中条件可知，1×4+2×1+3+4+1=4+1+1+1+n 0 ，由此可以得出：n 0 =1×4+2×1+3+4+1一(4+1+1+1)=14—7=7.
3.用下列元素序列(22，8，62，35，48)构造平衡二叉树，当插入( )时，会出现不平衡的现象。 （分数：2.00） A.22 B.35 C.48 √ D.62
解析：解析：由题中所给的结点序列构造二叉排序树的过程如下图：子树，虚线框内即为最小不平衡子树。
4.下面的算法实现了将二叉树中每一个结点的左右子树互换。addQ(Q，bt)为进队的函数，delQ(Q)为出队的函数，empty(Q)为判别队列是否为空的函数，空白处应填的内容是( )。 typedef struct node{ int 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； ( (1) )=q； if(p->lchild) ( (2) )； if(p-＞rchild)addQ(Q，p-＞rchild)； } }} （分数：2.00）
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) 解析：
5.已知有一棵二叉树，其高度为n，并且有且只有n个结点，那么二叉树的树形有( )种。 （分数：2.00） A.nlog 2 n B.2 C.2n一1 D.2 √
解析：解析：由题可得，每层有一个结点，从根结点往下，每个结点都有做左孩子右孩子两种情况，由概率知识可得，二叉树共有2 种树形。
6.已知二叉排序树如下图所示，下列序列构造此二叉排序树不正确的是( )。（分数：2.00）
A.(105，85，90，65，120，110，138)
n-1
n-1n+1
当插入48后，首次出现不平衡
B.(105，120，1 10，138，85，65，90) C.(105，65，85，90，120，110，138) √ D.(105，85，65，90，120，138，110)
解析：解析：将各选项中对应的二叉排序树画出即可得到答案。
7.已知某平衡二叉树含有在15个结点，25为其中的一个结点，如果在此平衡二叉树上查找关键字为25的结点，下列比较的次序合理的是( )。 （分数：2.00） A.29，35 B.35，45，25
C.45，15，35，25 √ D.60，30，50，40，38，36
解析：解析：设N k 表示深度为h的平衡二叉树中含有的最少结点数，有：N 0 =0，N 1 =1，N 2 =2，…，N k =N k-1 +N k-2 +1，N 3 =4，N 4 =7，N 5 =12，N 6 =20＞15。也就是说，高度为6的平衡二叉树最少有20个结点，因此15个结点的平衡二叉树的高度为5，而最小叶子结点的层数为3，所以选项D错误。而A和B的查找过程不能构成二叉排序树，因此A、B错误。
8.利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素30要进行元素间的比较次数是( )。 （分数：2.00） A.4 B.5 √ C.6 D.7
解析：解析：利用逐点插入法建立二叉排序树是从空树开始，通过查找，将每个结点作为一个叶子插入。按题目中数据的输入次序建立的二叉排序树如下图所示，查找元素30的比较次数为5次。9.构建一个哈夫曼树，如果给定权值的个数为n，那么哈夫曼树的结点总数为( )。 （分数：2.00） A.不确定 B.2n C.2n+1 D.2n-1 √
解析：解析：哈夫曼树中只有度为0和度为2的结点，即N=n 0 +n 2 ，而根据二叉树的性质：n 0 =n 2 +1，可知n 0 =n，那么n 2 =n一1，N=n+n一1=2n—1.
10.已知某哈夫曼树的度为m，其中叶结点个数为n，那么非叶结点的个数为( )。（分数：2.00） A. B. C. √ D.
解析：解析：度为m的结点个数为n 叶子结点个数为n，m×n +1=n +n，m×n =n +n一1,n = m m m m m m 11.一棵哈夫曼树共有99个结点，对其进行哈夫曼编码，共能得到( )种不同的编码。 （分数：2.00） A.48 B.50 √ C.99 D.100
解析：解析：本题考查哈夫曼树的性质。哈夫曼树中只有度为2和度为0的结点，哈夫曼编码是对哈夫曼树中的叶子结点编码。根据树的性质N 0 =N 2 +1，故N 0 =(N 2 +N 0 +1)／2=(99+1)／2=50，哈夫曼树共有50个叶子结点，所以共能得到50个不同的码字。
12.一棵含有n个结点的k叉树，可能达到的最大深度为( )，最小深度为( )。 （分数：2.00）
A.n-k+1，log k n+1 √ B.n，log k n+1 C.n，log k n-1 D.n-k+1，log k n+1
解析：解析：当k叉树种只有一个层的分支数为n，其他层的分指数均为1时，此时的树具有最大的深度为：n一k+1。当该k叉树为完全k叉树时，其深度最小。参照二叉树的性质可知，其深度为：log n+1。 k 13.已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有( )个。 （分数：2.00） A.23 B.29 C.16 √ D.32
解析：解析：一棵深度为h的满二叉树的结点个数为2 一1，则有20≤2 一1≤40，即21≤2 ≤41，h=5(总结点数=2 一1=31，为素数)。满二叉树中叶子结点均集中在最底层，所以结点个数=2 =16个。 14.有( )棵不同的二叉树，其结点的前序序列为a 1 ，a 2 ，…，a n 。 （分数：2.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)，而递归方程的解为T(n)=（分数：2.00） A.2n+1 √ B.2n-1 C.log 2 2n+1 D.log 2 2n-1
解析：解析：设j、k分别为度为1、2的结点数目，则结点总数m=n+j+k；由于是非满的，所以必有j=1，且n=k+1，因此有m=2n。设树的高度为h，具有n个结点的完全二叉树的深度为log 2 n+1。本题中，树的结点个数为2n，有h=log 2 (2n)+1。所以，有n个叶结点的非满的完全二叉树的高度为log 2 (2n)+1。 16.在一棵二叉树中，单分支结点数为30，双分支结点数为15，则叶子结点数为( )。 （分数：2.00） A.15 B.16 √ C.17 D.4，
解析：解析：由二叉树的性质可知：n 0 =n 2 +1=16。 17.判断线索二叉树中某结点*p有左孩子的条件是( )。 （分数：2.00） A.p-＞lchild==NULL
. 5
5-1
h
k
h
15.有n个叶结点的非满的完全二叉树的高度为( )。
计算机专业基础综合数据结构(树与二叉树)-试卷2
