计算机专业基础综合数据结构（树与二叉树）模拟试卷2

计算机专业基础综合数据结构（树与二叉树）模拟试卷2

单选题

1.设树T的度为4，其中度为1、2、3和4的结点个数分别为4、1、1、1，则T中的叶子数为( )。(D)

A. 10

B. 11

C. 9

D. 7

解析：根据题中条件可知，1×4+2×1+3+4+1=4+1+1+1+n₀，由此可以得出：n₀=1×4+2×1+3+4+1一(4+1+1+1)=14—7=7.

2.用下列元素序列(22，8，62，35，48)构造平衡二叉树，当插入( )时，会出现不平衡的现象。(C)

A. 22

B. 35

C. 48

D. 62

解析：由题中所给的结点序列构造二叉排序树的过程如下图：

3.下面的算法实现了将二叉树中每一个结点的左右子树互换。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)；

}

}

}(C)

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)

解析：

4.已知有一棵二叉树，其高度为n，并且有且只有n个结点，那么二叉树的树形有( )种。(D)

A. nlog₂n

B. 2ⁿ⁺¹

C. 2n一1

D. 2^n-1

解析：由题可得，每层有一个结点，从根结点往下，每个结点都有做左孩子右孩子两种情况，由概率知识可得，二叉树共有2^n-1种树形。

5.已知二叉排序树如下图所示，下列序列构造此二叉排序树不正确的是( )。

(C)

A. (105，85，90，65，120，110，138)

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)

解析：将各选项中对应的二叉排序树画出即可得到答案。

6.已知某平衡二叉树含有在15个结点，25为其中的一个结点，如果在此平衡二叉树上查找关键字为25的结点，下列比较的次序合理的是( )。(C)

A. 29，35

B. 35，45，25

C. 45，15，35，25

D. 60，30，50，40，38，36

解析：设N_k表示深度为h的平衡二叉树中含有的最少结点数，有：N₀=0，N₁=1，N₂=2，…，N_k=N_k-1+N_k-2+1，N₃=4，N₄=7，N₅=12，N₆=20＞15。也就是说，高度为6的平衡二叉树最少有20个结点，因此15个结点的平衡二叉树的高度为5，而最小叶子结点的层数为3，所以选项D错误。而A和B的查找过程不能构成二叉排序树，因此A、B错误。

7.利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素30要进行元素间的比较次数是( )。(B)

A. 4

B. 5

C. 6

D. 7

解析：利用逐点插入法建立二叉排序树是从空树开始，通过查找，将每个结点作为一个叶子插入。按题目中数据的输入次序建立的二叉排序树如下图所示，查找元素30的比较次数为5次。

8.构建一个哈夫曼树，如果给定权值的个数为n，那么哈夫曼树的结点总数为( )。(D)

A. 不确定

B. 2n

C. 2n+1

D. 2n-1

解析：哈夫曼树中只有度为0和度为2的结点，即N=n₀+n₂，而根据二叉树的性质：n₀=n₂+1，可知n₀=n，那么n₂=n一1，N=n+n一1=2n—1.

9.已知某哈夫曼树的度为m，其中叶结点个数为n，那么非叶结点的个数为( )。

本文档预览：3000字符，共11688字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载