数据结构第六章习题课

1、下图所示的4棵二叉树中，不是完全二叉树的是（）

2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（）。

A 、正确

B 、错误

C 、不一定

3、已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是（）。

A 、acbed

B 、decab

C 、deabc

D 、cedba

4、如果T2是由有序树T 转换而来的二叉树，那么T 中结点的后序就是T2中结点的（）。

A 、前序

B 、中序

C 、后序

D 、层次序

5、深度为5的二叉树至多有（）个结点。

A 、16

B 、32

C 、31

D 、10

6、在一个非空二叉树的中序遍历序列中，根结点的右边（）。

A 、只有右子树上的所有结点

B 、只有右子树上的部分结点

C 、只有左子树上的部分结点

D 、只有左子树上的所有结点

7、树最适合用来表示（）。

A 、有序数据元素

B 、无序数据元素

C 、元素之间具有分支层次关系的数据

D 、元素之间无联系的数据。

8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。

A 、不发生改变

B 、发生改变

C 、不能确定

D 、以上都不对

9、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。

A 、二叉链表

B 、广义表存储结构

C 、三叉链表

D 、顺序存储结构

10、对一个满二叉树，m 个树叶，n 个结点，深度为h ，则（）。

A 、n=m+h

B 、h+m=2n

C 、m=h-1

D 、n=2h -1

11、设n ，m 为二叉树上的两个结点，在中序遍历时，n 在m 前的条件是（）。

A 、n 在m 右方

B 、n 是m 祖先

C 、n 在m 左方

D 、n 是m 子孙

12．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-

，

A

B

C D

其前缀形式为( )

A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 13.设有一表示算术表达式的二叉树（见右图），

它所表示的算术表达式是（）

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

14.在下述结论中，正确的是（）

①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A ．①②③

B ．②③④

C ．②④

D ．①④

15.设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（）

A ．m-n

B ．m-n-1

C ．n+1

D ．条件不足，无法确定

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

A ．9

B ．11

C ．15

D ．不确定

17．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）

A ． 250

B ．500

C ．254

D ．505

E ．以上答案都不对

18. 一个具有1025个结点的二叉树的高h 为（）

A ．11

B ．10

C ．11至1025之间

D ．10至1024之间

19．深度为h 的满m 叉树的第k 层有（）个结点。(1=

A ．m k-1

B ．m k -1

C ．m h-1

D ．m h -1

20.利用二叉链表存储树，则根结点的右指针是（）。

A ．指向最左孩子

B ．指向最右孩子

C ．空

D ．非空

21．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。

A ．先序 B. 中序 C. 后序 D. 从根开始按层次遍历

22．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。

A ．前序

B ．中序

C ．后序

D ．按层次

23．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）

A．所有的结点均无左孩子B．所有的结点均无右孩子

C．只有一个叶子结点D．是任意一棵二叉树

24. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( )

A.X的双亲

B.X的右子树中最左的结点

C.X的左子树中最右结点

D.X的左子树中最右叶结点

25.线索二叉树是一种（）结构。

A．逻辑B．逻辑和存储C．物理D．线性

26．n个结点的线索二叉树上含有的线索数为（）

A．2n B．n－l C．n＋l D．n

27．下面几个符号串编码集合中，不是前缀编码的是（）。

A．{0,10,110,1111} B．{11,10,001,101,0001}

C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc}

28.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为（）

A．A[2i](2i=

29、高度为h的完全二叉树至少有多少个结点?至多有多少个结点?

解：高度为h的完全二叉树至少有2h-1个结点，至多有2h-1个结点(也就是满二叉树)。

30、在什么样的情况下，等长编码是最优的前缀码?

答：在每个字符的使用概率相同的情况下，也即在哈夫曼树中每片叶子的权重相等的时候，等长编码是最优的前缀码。

31.假设在树中，结点x是结点y的双亲时,用(x,y)来表示树边。已知一棵树边的集合为{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用图表示出此树，并回答下列问题：

(1)哪个是根结点? (2)哪些是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先?

(5)哪些是g的孩子? (6)哪些是e的子孙? (7)哪些是e的兄弟?哪些是f的兄弟?

(8)结点b和n的层次各是多少? (9)树的深度是多少? (10)以结点c为根的子树的深度是多少? (11) 树的度数是多少?

答：这是测试我们对树的基本概念的掌握情况。

a是根结点；mndfjkl是叶结点；c是g的双亲；c,a是g的祖先；

j,k是g的孩子；imn是e的子孙；d是e的兄弟，g,h是f的兄弟；

b的层次是2，n的层次是5；树的深度是5；以c为根的子树深度是3；

树的度数是3。

32、试找出分别满足下面条件的所有二叉树：

(1)前序序列和中序序列相同；(2)中序序列和后序序列相同；

(3)前序序列和后序序列相同；(4)前序、中序、后序序列均相同。

答：

(1) 前序序列和中序序列相同的二叉树是：没有左子树的二叉树(右单支树)。

(2) 中序序列和后序序列相同的二叉树是：没有右子树的二叉树(左单支树)。

(3) 前序序列和后序序列相同的二叉树是：只有根结点的二叉树。

(4) 前序、中序、后序序列均相同的二叉树：只有根结点的二叉树。

33、对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。解：A

/ \

BC

/ \ \

D E F

/ \ /

GHI

\

J

34、对下图所示的森林：

(1)求各树的前序序列和后序序列；

(2)求森林的前序序列和后序序列；

(3)将此森林转换为相应的二叉树；

(4)给出(a)所示树的以双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代?

解：

(1) (a)的前序序列：ABCDEF 后序序列：BDEFCA

(b)的前序序列：GHIJK 后序序列：IJKHG

(c)的前序序列：LMPQRNO 后序序列：QRPMNOL

(2) 此森林的前序序列：ABCDEFGHIJKLMPQRNO

此森林的后序序列：BDEFCAIJKHGQRPMNOL

(3)略

(4)略

35．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为。