第六章 树和二叉树
一、选择题
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
《数据结构》复习题-第6章-树和二叉树
