第6章+树和二叉树(习题)

2008信息与计算科学专业数据结构习题

第六章 树和二叉树

一、选择题

1．已知一算术表达式的中缀形式为 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．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ） A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++

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

A．5 B．6 C．7 D．8 4. 在下述结论中，正确的是（ ）

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

A．①②③ B．②③④ C．②④ D．①④

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

A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定

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

A．9 B．11 C．15 D．不确定

7．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个

A．4 B．5 C．6 D．7

8．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。

A．M1 B．M1+M2 C．M3 D．M2+M3 9．具有10个叶结点的二叉树中有（ ）个度为2的结点。 A．8 B．9 C．10 D．ll

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

56

2008信息与计算科学专业数据结构习题

A． 250 B． 500 C．254 D．505 E．以上答案都不对 11. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 12. 有n个叶子的哈夫曼树的结点总数为（ ）。

A．不确定 B．2n C．2n+1 D．2n-1 13. 有关二叉树下列说法正确的是（ ）

A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 14. 一个具有1025个结点的二叉树的高h为（ ）

A．11 B．10 C．11至1025之间 D．10至1024之间 15．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点

A．2h B．2h-1 C．2h+1 D．h+1

16. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ） A．?logn?+1 B．logn+1 C．?logn? D．logn-1 17．在一棵高度为k的满二叉树中，结点总数为（ ） A．2k-1 B．2k C．2k-1 D．?log2k?+1 18．高度为 K的二叉树最大的结点数为（ ）。 A．2k

B．2k-1 C．2k -1

D．2k-1-1

19. 一棵树高为K的完全二叉树至少有（ ）个结点 A．2k –1 B. 2k-1 –1 C. 2k-1 D. 2k

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

A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 21．树的后根遍历序列等同于该树对应的二叉树的( ).

A. 先序序列 B. 中序序列 C. 后序序列

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

A．前序 B．中序 C．后序 D．按层次

57

2008信息与计算科学专业数据结构习题

23．在下列存储形式中，哪一个不是树的存储形式？（ ）

A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 24．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。

A．CBEFDA B． FEDCBA C． CBEDFA D．不定

25. 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是： A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对

26. 上题的二叉树对应的森林包括多少棵树（ ） A．l B．2 C．3 D．概念上是错误的

27．二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是：

A、 E B、 F C、 G D、 H

28．将一棵树t 转换为孩子—兄弟链表表示的二叉树h，则t的后根序遍历是h 的（ ） A．前序遍历 B．中序遍历 C．后序遍历 D．层次遍历 29．下面的说法中正确的是（ ）.

（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变； （2）按二叉树定义，具有三个结点的二叉树共有6种。 A．(1)(2) B．(1) C．(2) D．(1)、(2)都错 30．对于前序遍历与中序遍历结果相同的二叉树为（1）; 对于前序遍历和后序遍历结果相同的二叉树为（2）。

A．一般二叉树 B．只有根结点的二叉树 C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树 E．所有结点只有左子数的二叉树 F．所有结点只有右子树的二叉树

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

A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是任意一棵二叉树

32．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ） A．都不相同 B．完全相同

58

2008信息与计算科学专业数据结构习题

C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 33．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树

34. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( ) A．不确定 B. 0 C. 1 D. 2

35. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。 A. 0 B. 1 C. 2 D. 不确定

36. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( ) A. X的双亲 B. X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点 37. 引入二叉线索树的目的是（ ）

A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 38．n个结点的线索二叉树上含有的线索数为（ ） A．2n B．n－l C．n＋l D．n

39. 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。

A． n-1 B．n C． n+1 D． n+2 40．由3 个结点可以构造出多少种不同的二叉树？（ ） A．2 B．3 C．4 D．5 41．下述编码中哪一个不是前缀码（ ）。 A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001）

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

A．A[2i](2i=

二、判断题

1. 二叉树是度为2的有序树。

59

2008信息与计算科学专业数据结构习题

2. 完全二叉树一定存在度为1的结点。 3. 对于有N个结点的二叉树，其高度为log2n。 4．深度为K的二叉树中结点总数≤2k-1。

5. 二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）。

6. 二叉树的遍历结果不是唯一的.

7. 二叉树的遍历只是为了在应用中找到一种线性次序。

8. 一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。 9. 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。

10. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。

11．对一棵二叉树进行层次遍历时，应借助于一个栈。 12．用树的前序遍历和中序遍历可以导出树的后序遍历。

13．采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。

14. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。

15． 中序遍历二叉链存储的二叉树时，一般要用堆栈；中序遍历检索二叉树时，也必须使用堆栈。

16．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列 17. 后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。 18．任何二叉树的后序线索树进行后序遍历时都必须用栈。 19．任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。 20．由一棵二叉树的前序序列和后序序列可以唯一确定它。 21．完全二叉树中，若一个结点没有左孩子，则它必是树叶。 22. 二叉树只能用二叉链表表示。

23. 一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i(2i< n)，右儿子是2i+1（2i+1

24. 给定一棵树，可以找到唯一的一棵二叉树与之对应。 25. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数。

60

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第6章+树和二叉树(习题)在线全文阅读。