数据结构考试题库(含答案) .pdfVIP

数据结构考试题库（含答案）

树和⼆叉树

⼀、选择题

1．已知⼀算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为()

A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE

【北京航空航天⼤学1999⼀、3（2分)】

2．算术表达式a+b*（c+d/e）转为后缀表达式后为（）【中⼭⼤学1999⼀、5】

A．ab+cde/*

B．abcde/+*+

C．abcde/*++

D3.设有⼀表⽰算术表达式的⼆叉树（见下图），

它所表⽰的算术表达式是（）【南京理⼯⼤学1999⼀、20（2分）】A.A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)C.

(A*B+C)/(D*E+（F-G）)D.A*B+C/D*E+F-G

4.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶⼦数为（）

A．5

B．6

C．7

D．8

【南京理⼯⼤学2000⼀、8（1.5分）】

5.在下述结论中，正确的是（）【南京理⼯⼤学1999⼀、4（1分）】

①只有⼀个结点的⼆叉树的度为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．条件不⾜，⽆法确定【南京理⼯⼤学2000⼀、17（1.5分）】

7.树是结点的有限集合，它（(1）)根结点，记为T。其余结点分成为m（m0）个(（2）)的集合T1，T2，…，Ｔm，每个

集合⼜都是树，此时结点T称为Ti的⽗结点，Ti称为T的⼦结点（1≤i≤m）。⼀个结点的⼦结点个数称为该结点的(（3）)。

⼆叉树与树是两个不同的概念，⼆叉树也是结点的有限集合，它(（4）)根结点。可以把树的根结点的层数定义为1，其他结点

的层数等于其⽗结点所在层数加上1。令T是⼀棵⼆叉树，Ki和Kj是T中⼦结点数⼩于2的结点中的任意两个，它们所在的层

数分别为λKi和λKj，当关系式│λKi-λKj│≤1⼀定成⽴时，则称T为⼀棵（(5)）。供选择的答案：

（1）(4)A.有0个或1个B.有0个或多个C.有且只有⼀个D.有1个或1个以上

（2）A.互不相交B.允许相交C.允许叶结点相交D.允许树枝结点相交

（3）A.权B.维数C.次数D.序

（5）A.丰满树B.查找树C.平衡树D.完全树【上海海运学院1999⼆、2(5分）】

8．若⼀棵⼆叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）

A．9

B．11

C．15

D．不确定【北京⼯商⼤学2001⼀.7(3分)】

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对应的⼆叉树根结点的右⼦树上

的结点个数是（）。【北⽅交通⼤学2001⼀、16（2分）】

A．M1

B．M1+M2

C．M3

D．M2+M3

11．具有10个叶结点的⼆叉树中有（）个度为2的结点，【北京航空航天⼤学2000⼀、5（2分)】

A．8

B．9

C．10

D．ll

12．⼀棵完全⼆叉树上有1001个结点，其中叶⼦结点的个数是（）【西安交通⼤学1996三、2(3分)】

A．250

B．500

C．254

D．505

E．以上答案都不对

13.设给定权值总数有n个，其哈夫曼树的结点总数为()【福州⼤学1998⼀、5(2分)】

A．不确定B．2nC．2n+1D．2n-1

14.有n个叶⼦的哈夫曼树的结点总数为（）。【青岛⼤学2002⼆、1（2分）】

A．不确定B．2nC．2n+1D．2n-1

15．若度为m的哈夫曼树中，其叶结点个数为n，则⾮叶结点的个数为（）。【中