《数据结构》复习题-第6章-树和二叉树 - 下载本文

第六章 树和二叉树

一、选择题

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

【北京航空航天大学 1999 一、3 (2分)】

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分)】

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 16. 有关二叉树下列说法正确的是( )【南京理工大学 2000 一、11 (1.5分)】

A.二叉树的度为2 B.一棵二叉树的度可以小于2 C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为

2

17.二叉树的第I层上最多含有结点数为( ) 【中山大学1998二、7 (2分)】【北京理工大学 2001 六、5(2分)】 A.2I B. 2I-1-1 C. 2I-1 D.2I -1 18. 一个具有1025个结点的二叉树的高h为( )【南京理工大学 1999 一、19 (2分)】

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

A.2h B.2h-1 C.2h+1 D.h+1 【南京理工大学2001一、11(1.5分)】

22.深度为h的满m叉树的第k层有( )个结点。(1=

A.mk-1 B.mk-1 C.mh-1 D.mh-1

24.高度为 K的二叉树最大的结点数为( )。【山东大学 2001 二、3 (1分)】

A.2k B.2k-1 C.2k -1 D.2k-1-1

28.对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,可采用( )次序的遍历实现编号。【北京理工大学 2000 一、

A.先序 B. 中序 C. 后序 D. 从根开始按层次遍历 31.在下列存储形式中,哪一个不是树的存储形式?( )【北方交通大学 2001 一、23 (2分)】

A.双亲表示法 B.孩子链表表示法 C.孩子兄弟表示法 D.顺序存储表示法

33.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为( )。

A.CBEFDA B. FEDCBA C. CBEDFA D.不定 【浙江大学 1999 四、2 ( 4分)】

37.二叉树的先序遍历和中序遍历如下: 先序遍历:EFHIGJK;中序遍历:

HFIEJKG 。该二叉树根的右子树的根是:【北方交通大学 2001 一、21(2分)】

A、 E B、 F C、 G D、 H 40.下面的说法中正确的是( ).

(1)任何一棵二叉树的叶子结点在三种遍历中的相对次序不变; (2)按二叉树定义,具有三个结点的二叉树共有6种。

A.(1)(2) B.(1) C.(2) D.(1)、(2)都错 【南京理工大学 2001 一、10 (1.5分)】

41.对于前序遍历与中序遍历结果相同的二叉树为(1);

对于前序遍历和后序遍历结果相同的二叉树为(2)。【中科院计算所 1999 一、4 (4分)】

A.一般二叉树 B.只有根结点的二叉树 C.根结点无左孩子的二叉树

D.根结点无右孩子的二叉树 E.所有结点只有左子数的二叉树 F.所有结点只有右子树的二叉树 42.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足( )

【南开大学 2000 一、2】

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

50. 引入二叉线索树的目的是( )

A.加快查找结点的前驱或后继的速度 B.为了能在二叉树中方便的进行插入与删除

C.为了能方便的找到双亲 D.使二叉树的遍历结果唯一【南京理工大学1998 一、5 (2分)】

52.n个结点的线索二叉树上含有的线索数为( )

A.2n B.n-l

C.n+l D.n 【中山大学 1998 二、8 (2分)】 62.下述编码中哪一个不是前缀码( )。【中科院计算所 2000 一、2 (2分)】

A.(00,01,10,11) B.(0,1,00,11) C.(0,10,110,111) D.(1,01,000,001)

(5)找出所有满足下列条件的二叉树:

1)它们在先序遍历和中序遍历时,得到的结点访问序列相同; 2)它们在后序遍历和中序遍历时,得到的结点访问序列相同; 3)它们在先序遍历和后序遍历时,得到的结点访问序列相同;【东南

大学2000一、4(6分)】

44.将下列由三棵树组成的森林转换为二叉树。(只要求给出转换结果) A D G B C E H I J K L M N O F 【南京航空航天大学 1998 一、 (10分)】 P 46.设一棵二叉树的先序、中序遍历序列分别为

先序遍历序列: A B D F C E G H 中序遍历序列: B F D A G E H C

(1)画出这棵二叉树。

(2)画出这棵二叉树的后序线索树。 (3)将这棵二叉树转换成对应的树(或森林)。【南京航空航天大学 1997 二、

(1)一棵二叉树的先序、中序和后序序列分别如下,其中有一部分为显示出来。试求出空格处的内容,并画出该二叉树。

先序序列: _ B F I C E H G 中序序列:D K F I A E J C

后序序列: K F B H J G A 【西安电子科技大学2000计应用 五、2 (5分)】

类似本题的另外叙述有: (1)设有正文MNOPPPOPMMPOPOPPOPNP,字符集为M,N,O,P,设计一套二进制编码,使得上述正文的编码最短。【首都经贸大学 1998 一、5 (4分)】 (1)构造相应的huffman树: (2) 计算它的带权路径长度: (3)写出它的huffman编码:

分)】 (10