【考研类试卷】树与二叉树及答案解析.doc

《【考研类试卷】树与二叉树及答案解析.doc》由会员分享，可在线阅读，更多相关《【考研类试卷】树与二叉树及答案解析.doc（22页珍藏版）》请在麦多课文档分享上搜索。

1、树与二叉树及答案解析(总分：228.00，做题时间：90 分钟)一、单项选择题(总题数：24，分数：48.00)1.具有 10 个叶结点的二叉树中有( )个度为 2 的结点。（分数：2.00）A.8B.9C.10D.112.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是( )。（分数：2.00）A.(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90)C.(100，60，80，90，120，110，130)D.(100，80，60，90，120，130，110)3.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数

2、是( )。（分数：2.00）A.不确定B.0C.1D.24.中缀表达式 D/C“A+B*ED*F 的前缀表达式为( )。（分数：2.00）A.-+/DCA*BE*DFB.DCA/BE*+DF*-C.-CA+/D*BE*DFD.-+/DC*ABE*DF5.设 F 是一个森林，B 是由 F 变换得的二叉树。若 F 中有 n 个非终端结点，则 B 中右指针域为空的结点有( )个。（分数：2.00）A.n-1B.nC.n+1D.n+26.一棵二叉树的前序遍历序列为 ABCDEFG，它的中序遍历序列可能是( )。（分数：2.00）A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG7.

3、在一棵三元树中度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数为 2 个，则度为 0 的结点数为( )个。（分数：2.00）A.4B.5C.6D.78.设有一表示算术表达式的二叉树(见图)，它所表示的算术表达式是( )。（分数：2.00）A.B.C.D.9.已知一棵二叉树先序遍历结果为 ABDEFG，中序遍历结果为 BAEDGF，则后序遍历结果为( )。（分数：2.00）A.BCDEFAB.BFDECAC.BEGFDAD.BEFGDA10.设某哈夫曼树中有 199 个结点，则该哈夫曼树中有( )个叶子结点。（分数：2.00）A.99B.100C.101D.1021

4、1.设某棵二叉树的高度为 10，则该二叉树上的叶子结点最多有( )。（分数：2.00）A.20B.255C.511D.102312.当一棵有 n 个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A1n中时，数组中第 i 个结点的左孩子为( )。（分数：2.00）A.A 2i(2i-n)B.A2i+1(2i+1-n)C.Ai/2D.无法确定13.下列所示各图中是中序线索化二叉树的是( )。（分数：2.00）A.B.C.D.14.设一棵 m 叉树中有 N，个度数为 1 的结点，N 2个度数为 2 的结点，N m个度数为 m 的结点，则该树中共有( )个叶子结点。（分数：2.00）

5、A.B.C.D.15.由权值分别为 3，8，6，2，5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。（分数：2.00）A.24B.48C.72D.5316.若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是( )。（分数：2.00）A.9B.11C.15D.不确定17.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足( )。（分数：2.00）A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树18.一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是( )。（分数：2.00）A

6、.250B.500C.501D.50519.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足( )。（分数：2.00）A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树20.设某棵三叉树中有 40 个结点，则该三叉树的最小高度为( )。（分数：2.00）A.3B.4C.5D.621.下列二叉树中，不平衡的二叉树是( )。（分数：2.00）A.B.C.D.22.下面几个符号串编码集合中，不是前缀编码的是( )。（分数：2.00）A.0，10，110，1111B.11，10，001，101，0001C.00，010，0110，1000D

7、.b，c，aa，ac，aba，abb，abc23.设树 T 的度为 4，其中度为 1，2，3 和 4 的结点个数分别为 4，2，1，1，则 T 中的叶子数为( )。（分数：2.00）A.5B.6C.7D.824.一个具有 1025 个结点的二叉树的高 h 为( )。（分数：2.00）A.11B.10C.11 至 1025 之间D.10 至 1024 之间二、综合应用题(总题数：18，分数：180.00)25.要求二叉树按二叉链表形式存储，并且：(1)写一个建立二叉树的算法。(2)写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为 K，具有 N 个结点的二叉树的每个结点都与深

8、度为 K 的满二叉树中编号从 1 至 N 的结点一一对应。（分数：10.00）_26.设某二叉树的前序遍历序列为：ABCDEFGGI，中序遍历序列为：BCAEDGHFI(1)试画出该二叉树；(2)写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。(3)设具有四个结点的二叉树的前序遍历序列为 abcd；S 为长度等于 4 的由 a，b，c，d 排列构成的字符序列，若任取 S 作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树?为什么?试列出具有 4个结点二叉树的全部形态及相应的中序遍历序列。（分数：10.00）_27.对任何一棵二叉树，如果终端结点数为 n0，度为 2

9、 的结点数为 n2，则一定有 n0=n2+1。（分数：10.00）_28.试问中序序列及后序序列是否能唯一地建立二叉树?若不能，则说明理由；若能，则对中序序列)BEAFGC 和后序序列 DEBGFCA 构造二叉树。（分数：10.00）_29.已知一棵二叉树的中序序列和后序序列如下：中序：GLDHBEIACJFK 后序：LGHDIEBJKFCA(1)给出这棵二叉树；(2)转换为对应的森林；(3)画出该森林的带右链的先根次序表示法：（分数：10.00）_30.对下面的 3 阶 B 树，依次执行下列操作，画出各步操作的结果。(1)插入 90 (2)插入 25 (3)插入 45 (4)删除 60 (5

10、)删除 80（分数：10.00）_31.自由树(即无环连通图)T=(V，E)的直径是树中所有点对间最短路径长度的最大值，即 T 的直径定义为MAX d(u，v)，这里 d(u，v)表示顶点 u 到顶点 v 的最短路径长度(路径长度为路径中所含的边数)。试写一算法求 T 的直径，并分析算法的时间复杂度(时间复杂度越小得分越高)。（分数：10.00）_32.设二叉树的存储结构如下：LINK0 0 2 3 7 5 8 0 10 1 INFOJ H F D B A C E G IRLINK0 0 0 9 4 0 0 0 0 0其中，T 为树根结点的指针，LLINK、RLINK 分别指向结点的左右子女，

11、INFO 为其数据域，请完成下列各题：(1)画出二叉树 T 的逻辑结构。(2)写出按前序、中序和后序周游二叉树 T 得到的结点序列。(3)画出二叉树 T 的后序线索树。（分数：10.00）_33.设 T 是一棵二叉树，除叶子结点外，其他结点的度数皆为 2，若 T 中有 6 个叶结点，试问：(1)T 树的最大深度 Kmax 一?最小可能深度 Kmin=?(2)T 树中共有多少非叶结点?(3)若叶结点的权值分别为 1，2，3，4，5，6。请构造一棵哈夫曼树，并计算该哈夫曼树的带权路径长度wpl。（分数：10.00）_34.二叉树结点的平衡因子(bf)定义为该结点的左子树高度与右子树高度之差。设二叉

12、树结点结构为：(1child，data，bf，rchild)，1child，rchild 是左右儿子指针；data 是数据元素；bf 是平衡因子，编写递归算法计算二叉树中各个结点的平衡因子。（分数：10.00）_35.依次输入表(30，15，28，20，24，10，12，68，35，50，46，55)中的元素，生成一棵二叉排序树。(1)试画出生成之后的二叉排序树；(2)对该二叉排序树作中序遍历，试写出遍历序列；(3)假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。（分数：10.00）_36.已知深度为 h 的二叉树采用顺序存储结构已存放于数组 BT1:2h一 1中，请写一非递归算

13、法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild，data，rchild)，根结点所在链结点的指针由 T 给出。（分数：10.00）_37.设一棵二叉树的先序、中序遍历序列分别为 A B D F C E G H、B F D A G E H C(1)画出这棵二叉树。(2)画出这棵二叉树的后序线索树。(3)将这棵二叉树转换成对应的树(或森林)。（分数：10.00）_38.数据结构 DEAP 的定义如下：DEAP 是一棵完全二叉树，它或者是一棵空树，或者满足下列特性：(1)树根不包含元素。(2)其左子树是一小堆(MINHEAP)，其右子树是一大堆(MAXHEAP)。(3)若右

14、子树非空，设 i 是左子树的任一结点，j 是右子树中与 i 相应的结点，若这样的 j 结点不存在，则取 j 为右子树中与 i 的父结点相应的结点；结点 i 的关键字总值是小于或等于结点 j 的关键字值。一个 DEAP 的例子如右图所示，与结点 15 相对应的结点为 20，与结点 19 相对应的结点为 25。（分数：10.00）_39.将下列由三棵树组成的森林转换为二叉树。(只要求给出转换结果)（分数：10.00）_40.设一组记录的关键字按以下次序进行插入：4、5、7、2、1、3、6，构造生成一棵平衡二叉树的过程。（分数：10.00）_41.二叉链表为存储结构，写出二叉树宽度的算法。所谓宽度，

15、是指二叉树的各层上，具有结点数最多的那一层上的结点总数。（分数：10.00）_42.假设在二叉树中值为 x 的结点不多于一个，试编写算法输出值为 x 的结点的所有祖先。（分数：10.00）_树与二叉树答案解析(总分：228.00，做题时间：90 分钟)一、单项选择题(总题数：24，分数：48.00)1.具有 10 个叶结点的二叉树中有( )个度为 2 的结点。（分数：2.00）A.8B.9 C.10D.11解析：对任何一棵二叉树，如果终端结点数为 n。，度为 2 的结点数为 n：，则一定有 n0=n2+1。所以n2=n0-1=9。2.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不

16、同的是( )。（分数：2.00）A.(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90)C.(100，60，80，90，120，110，130) D.(100，80，60，90，120，130，110)解析：1二叉排序树定义：二叉排序树是一棵二叉树，它或者为空，或者具有如下性质：1任一非终端结点若有左孩子，则该结点的关键字值大于其左孩子结点的关键字值；2任一非终端结点若有右孩子，则该结点的关键字值小于其右孩子结点的关键字值。是一种常用的动态查找表，上面首先给出了它的非递归形式。二叉排序树也可以用递归的形式定义，即二叉排序树是一棵树，它或者

17、为空，或者具有如下性质：1若它的左子树非空，则其左子树所有结点的关键字值均小于其根结点的关键字值；2若它的右子树非空，则其右子树所有结点的关键字值均大于其根结点的关键字值；3它的左右子树都是二叉排序树。2构造二叉排序树：一个无序序列可以通过构造一棵二叉排序树，然后再对这棵二叉树进行中序遍历，即可以变成有序序列。构造树的过程即为对无序序列进行排序的过程。例如：设查找的关键字的序列为45，24，53，45，12，90，则生成二叉排序树的过程为：*特别说明：结点个数和取值都相同的表构成的二叉排序树树形可能不相同。其树形由结点的输入顺序决定。3.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数

18、是( )。（分数：2.00）A.不确定B.0C.1D.2 解析：左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共 2 个空链域。4.中缀表达式 D/C“A+B*ED*F 的前缀表达式为( )。（分数：2.00）A.-+/DCA*BE*DF B.DCA/BE*+DF*-C.-CA+/D*BE*DFD.-+/DC*ABE*DF解析：第一步：加括号 D/(CA)+B*E-D*F(D/(CA)+B*E-D*F(D/(CA)+(B*E)-D*F(D/(CA)+(B*E)-(D*F)(D/(CA)+(B*E)-(D*F)(D/(C-A)+(B*E)-(D*F)

19、第二步：从最内层括号中的运算符开始前移，取代距其最近的左括号*第三步：将所有右括号去掉，得到前缀表达式：-+/DCA*BE*DF5.设 F 是一个森林，B 是由 F 变换得的二叉树。若 F 中有 n 个非终端结点，则 B 中右指针域为空的结点有( )个。（分数：2.00）A.n-1B.nC.n+1 D.n+2解析：Lchild LTag Data RTag Rchlid增加两个指示域 Ltag 和 Rtag，并分别定义如下：LTag：取值为 0 时，作用不变(指向左孩子)，取值为 1 时，指示当前结点的前驱结点；RTag：取值为 0 时，作月不变(指向右孩子)，取值为 1 时，指示当前结点的后

20、继结点；数据结构为：typedef enum：PointerTagLink，Thread)；Link：指针，值为 0；Thread：线索，值为 1typedef struct BiThrNodeTElemType data；struct BiThrNode*lchild，*rchild； 指向左孩子和右孩子PointerTag LTag，Rrrag； 左、右标志，它们的取值决定了 ichild、rchild 的指向含义BiThrNode，*BiThrTree；以上述结构构成的二叉链表称为线索链表。线索链表中指向前驱结点和后继结点的指针，称为线索。加上线索的二叉树称为线索二叉树(Threaded

21、 Binary Tree)。对二叉树按照某种次序遍历从而使其变为线索二叉树的过程叫做线索化。例如：将下面的二叉树 T 线索化，要求按照中序遍历次序确定结点的前驱和后继。解答：1二叉树 T 的中序遍历结果是：DBEAC；2将空链改为线索。*重要说明：1增加了一个头结点，该头结点的左指针指向二叉树的根结点 A，右指针指向最后一个结点；2第一个结点 D 的前驱可设定为头结点，最后一个结点 C 的后继也可设定为头结点。后继结点的查找方法：若结点的右链标志为 1(说明该结点是叶子结点)，则右链域指向的就是结点的直接后继；若结点的右链标志为 0(说明该结点不是叶子结点)，则遍历其右子树是最先访问的结点(右

22、子树的最左下结点)即是其直接后继。前驱结点的查找方法：若结点的左链标志为 1(说明该结点是叶子结点)，则左链域指向的结点就是结点的直接前驱；若结点的左链标志为 0(说明该结点不是叶子结点)，则遍历其左子树时最后访问的一个结点(左子树最右下的结点)为其前驱。森林转化为二叉树后，只有相应的左子树，而没有右子树，所以右指针域为空的结点个数为 n+1。6.一棵二叉树的前序遍历序列为 ABCDEFG，它的中序遍历序列可能是( )。（分数：2.00）A.CABDEFGB.ABCDEFG C.DACEFBGD.ADCFEG解析：解析见 3。7.在一棵三元树中度为 3 的结点数为 2 个，度为 2 的结点数为

23、 1 个，度为 1 的结点数为 2 个，则度为 0 的结点数为( )个。（分数：2.00）A.4 B.5C.6D.7解析：解析见 2。8.设有一表示算术表达式的二叉树(见图)，它所表示的算术表达式是( )。（分数：2.00）A.B.C. D.解析：即求中缀表达式的值，解析见 10。9.已知一棵二叉树先序遍历结果为 ABDEFG，中序遍历结果为 BAEDGF，则后序遍历结果为( )。（分数：2.00）A.BCDEFAB.BFDECAC.BEGFDA D.BEFGDA解析：1根据前序遍历 ABDEFG 知，根结点一定是 A；根据中序遍历 BAEDGF，得：A 的左侧全部为左子树结点(B)，A 的右

24、侧全部为右子树结点(EDGF)，于是有：*因为左子树只有一个结点，故不必再分析，否则将分析左子树。下面直接分析右子树。2对右子树的所有结点来说，其前序遍历是 DEFG，因此右子树的根结点是 D；根据中序遍历 EDGF，得：D 的左侧为 E 结点(构成 D 的左子树结点集合)，D 的右侧为 G、F 结点(构成 D 的右子树结点集合)，于是有：*D 的左子树只有 E，故不必再分析，否则将分析 D 的左子树。下面直接分析 D 的右子树。3对 D 的右子树的所有结点来说，其前序遍历是 FG，因此 D 的右子树的根结点是 F；根据中序遍历 GF，得：F 得左侧为 G 结点，右侧无结点。即 F 只有左子树

25、，没有右子树。于是有：*4对得到的树进行后序遍历，得到 BEGFDA。10.设某哈夫曼树中有 199 个结点，则该哈夫曼树中有( )个叶子结点。（分数：2.00）A.99B.100 C.101D.102解析：具有 n 个叶结点的 Huffman 树共有结点数为：2*n-1=199，得 n=100。11.设某棵二叉树的高度为 10，则该二叉树上的叶子结点最多有( )。（分数：2.00）A.20B.255C.511D.1023 解析：一棵深度为 k，结点个数为 2k-1 的二叉树称为满二叉树。满二叉树是深度为 k 的结点数目最多的二叉树。12.当一棵有 n 个结点的二叉树按层次从上到下，同层次从左

26、到右将数据存放在一维数组 A1n中时，数组中第 i 个结点的左孩子为( )。（分数：2.00）A.A 2i(2i-n)B.A2i+1(2i+1-n)C.Ai/2D.无法确定 解析：如果 2i+1=n，则左孩子为 A2i+1，否则就没有左孩子。所以无法确定。13.下列所示各图中是中序线索化二叉树的是( )。（分数：2.00）A.B.C.D. 解析：结点结构为：Lchild LTag Data RTag RchlidLTag：取值为 0 时，作用不变(指向左孩子)，取值为 1 时，指示当前结点的前驱结点；RTag：取值为 0 时，作用不变(指向右孩子)，取值为 1 时，指示当前结点的后继结点。14

27、.设一棵 m 叉树中有 N，个度数为 1 的结点，N 2个度数为 2 的结点，N m个度数为 m 的结点，则该树中共有( )个叶子结点。（分数：2.00）A. B.C.D.解析：N=N 0+N1+Nm；N=N1+2N2+mNm；所以 N0=N2+2N3+(m-1)Nm=*15.由权值分别为 3，8，6，2，5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。（分数：2.00）A.24B.48C.72D.53 解析：*生成的哈夫曼树如上图所示，路径长度为：3*(2+3)+2*(8+5+6)=53。16.若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个

28、数是( )。（分数：2.00）A.9B.11 C.15D.不确定解析：对任何一棵二叉树，如果终端结点数为 n。，度为 2 的结点数为 n2，则一定有 n0=n2+1。所以n0=10+1=11，而与 n1无关。17.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足( )。（分数：2.00）A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点 D.是任意一棵二叉树解析：前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A 和 B 均对，单支树的特点是只有一个叶子结点，故 C 是最合适的，选 C。A 或 B 都不全。18.一

29、棵完全二叉树上有 1001 个结点，其中叶子结点的个数是( )。（分数：2.00）A.250B.500C.501 D.505解析：由二叉树结点的公式：n=n 0+n1+n2=n0+n1+(n0-1)-2n0+n1-1，因为 n=1001，所以 1002=2n0+n1，在完全二叉树树中，n 1只能取 0 或 1，在本题中只能取 0，故 n=501，因此选 C。19.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足( )。（分数：2.00）A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点 D.是任意一棵二叉树解析：前序序列是“根左右”，后序序列是“左右根

30、”，若要这两个序列相反，只有单支树，所以本题的A 和 B 均对，单支树的特点是只有一个叶子结点，故 C 是最合适的，选 C。20.设某棵三叉树中有 40 个结点，则该三叉树的最小高度为( )。（分数：2.00）A.3B.4C.5 D.6解析：由完全二叉树原理可以知道，完全三叉树如有 n 个叶结点，则高度为 log 3n+1。21.下列二叉树中，不平衡的二叉树是( )。（分数：2.00）A.B.C. D.解析：平衡二叉树的特点为：左、右子树深度之差的绝对值不大于 1。22.下面几个符号串编码集合中，不是前缀编码的是( )。（分数：2.00）A.0，10，110，1111B.11，10，001，1

31、01，0001 C.00，010，0110，1000D.b，c，aa，ac，aba，abb，abc解析：构造出 Huffman 树后，左向分支标志为“0”，右向分支标志为”1”，则从根结点到叶结点之间的路径上分支字符组成的编码即为 Huffman 编码，该编码必为前缀编码。任何一个字符的编码都不是另一个字符的编码的前缀。例如，0、10、110、111 即为前缀编码。10 可以成为 101 的前缀，所以 B 不是前缀编码。23.设树 T 的度为 4，其中度为 1，2，3 和 4 的结点个数分别为 4，2，1，1，则 T 中的叶子数为( )。（分数：2.00）A.5B.6C.7 D.8解析：n=n

32、 0+n1+n2+n3+n4；n=1*4+2*2+3*1+4*1；所以 n0=7。24.一个具有 1025 个结点的二叉树的高 h 为( )。（分数：2.00）A.11B.10C.11 至 1025 之间 D.10 至 1024 之间解析：最小值为完全二叉树的情况，深度为 k，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树一一对应时，称为完全二叉树。深度为 k 的完全二叉树结点个数范围：最小结点数：2k-1，解得结果为 11；单节点二叉树时值最大为 1025。二、综合应用题(总题数：18，分数：180.00)25.要求二叉树按二叉链表形式存储，并且：(1)写一个建立二叉树

33、的算法。(2)写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为 K，具有 N 个结点的二叉树的每个结点都与深度为 K 的满二叉树中编号从 1 至 N 的结点一一对应。（分数：10.00）_正确答案：(二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。判断时易犯的错误是证明其左子树和右子树都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。BiTree creat() 建立二叉树的二叉链表形式的存储结构ElemTvpe x；BiTree bt；scan(“%d”，&x

34、)； 本题假定结点数据域为整型if(x=0)bt=null；else if(X0)bt-(BiNode*)malloc(sizeo(BiNode)；bt-data-x；bt-lchild-creat()；bt-rchild=creat()；else error(“输入错误”)；return(bt)；结束 BiTreeint JudgeComplete(BiTree bt)N 断二叉树是否是完全二叉树，如是，返回 1，否则，返回 0int tag=0；BiTree p=bt，Q； Q 是队列，元素是二叉树结点指针，容量足够大if(p=null)return(1)；QueueInit(Q)；Que

35、ueIn(Q，p)； 初始化队列，根结点指针入队while(!QueueEmpty(Q)p=QueueOut(Q)； 出队if(p-ichild&!tag)QueueIn(Q，p-lchild)； 左孩子入队else(if(p-lchild)return 0； 前边已有结点为空，本结点不空else tag=1； 首次出现结点为空if(p-rchild&!tag)QueueIn(Q，p-rchild)； 右孩子入队else if(p-rchild)return 0；else tag=1；whilereturn 1；)解析：26.设某二叉树的前序遍历序列为：ABCDEFGGI，中序遍历序列为：BC

36、AEDGHFI(1)试画出该二叉树；(2)写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。(3)设具有四个结点的二叉树的前序遍历序列为 abcd；S 为长度等于 4 的由 a，b，c，d 排列构成的字符序列，若任取 S 作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树?为什么?试列出具有 4个结点二叉树的全部形态及相应的中序遍历序列。（分数：10.00）_正确答案：(1)解析：27.对任何一棵二叉树，如果终端结点数为 n0，度为 2 的结点数为 n2，则一定有 n0=n2+1。（分数：10.00）_正确答案：(证明 假设二叉树中度为 1 的结点个数为 n。，结点

37、总数为 n。因为二叉树中任何结点的度最大不超过 2，因此有：n=n0+n1+n2 (1)从另一个角度看，我们来研究二叉树的分支数。对所有结点来说，除了根结点，任何其余结点都有一个分支进入(指向)。不妨设 B(Branch)为二叉树的分支数，则有：B=n-1(分支数比结点数少 1) (2)而分支是由度为 1 的结点和度为 2 的结点贡献的：每个度为 1 的结点贡献 1 个分支，每个度为 2 的结点贡献 2 个分支。则有：B=n11+n22=n1+2n2。 (3)由(2)、(3)得n=n1+2n2+1 (4)由(1)、(4)得n0=n2+1由此得出结论：二叉树叶子结点个数总是比度为 2 的结点个数

38、多 1。)解析：28.试问中序序列及后序序列是否能唯一地建立二叉树?若不能，则说明理由；若能，则对中序序列)BEAFGC 和后序序列 DEBGFCA 构造二叉树。（分数：10.00）_正确答案：(证明 当 n=1 时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。设当 n=m-1 时结论成立，现证明当 n=m 时结论成立。设中序序列为 S1，S 2，S m，后序序列是 P1，P 2，P m。因后序序列最后一个元素 Pm是根，则在中序序列中可找到与 Pm相等的结点(设二叉树中各结点互不相同)S i(1im)，因中序序列是由中序遍历而得，所以 Si是根结点，S 1，S 2，S i-1是左

39、子树的中序序列，而 Si+1，S i+2，S m是右子树的中序序列。若 i=1，则 S1是根，这时二叉树的左子树为空，右子树的结点数是 m-1，则S 2，S 3，S m和P1，P 2，P m-1可以唯一确定右子树，从而也确定了二叉树。若 i=m，则 Sm是根，这时二叉树的右子树为空，左子树的结点数是 m-1，则S 1，S 2，S m-1和P1，P 2，P m-1唯一确定左子树，从而也确定了二叉树。最后，当 1im 时，s，把中序序列分成S 1，S 2，S i-1和S i+1，S i+2，S m。由于后序遍历是“左子树右子树根结点”，所以P 1，P 2，P i-1)和P i，P i+1，P m-

40、1是二叉树的左子树和右子树的后序遍历序列。因而由S 1，S 2，S i-1和P 1，P 2，P i-1可唯一确定二叉树的左子树，由S i+1，S i+2，Sm和Pi，P i+1，P m-1可唯一确定二叉树的右子树。由中序序列 DBEAFGC 和后序序列 DEBGFCA 构造的二叉树如下图：)解析：29.已知一棵二叉树的中序序列和后序序列如下：中序：GLDHBEIACJFK 后序：LGHDIEBJKFCA(1)给出这棵二叉树；(2)转换为对应的森林；(3)画出该森林的带右链的先根次序表示法：（分数：10.00）_正确答案：( )解析：30.对下面的 3 阶 B 树，依次执行下列操作，画出各步操作

41、的结果。(1)插入 90 (2)插入 25 (3)插入 45 (4)删除 60 (5)删除 80（分数：10.00）_正确答案：( )解析：31.自由树(即无环连通图)T=(V，E)的直径是树中所有点对间最短路径长度的最大值，即 T 的直径定义为MAX d(u，v)，这里 d(u，v)表示顶点 u 到顶点 v 的最短路径长度(路径长度为路径中所含的边数)。试写一算法求 T 的直径，并分析算法的时间复杂度(时间复杂度越小得分越高)。（分数：10.00）_正确答案：(求树的直径的时间复杂度可为 O(n)，O(n 2)和 O(n3)。解法一：先调用求所有点对见最短路径算法(每边权数为 1)如 FLOYD 算法，然后对指代矩阵求最大的COSTi，j作为直径。解法二：修改 Bfs 算法，使之遍历时，记录当前访问结点的深度(离根的边数)，用存在度为 1 的结点作起点调用 Bfs，求出其他非根结点的深度，在各次调用 Bps 算法中求最大深度，即为树的直径。时间O(n(n+e)=O(n2+ne)，这里 O(ne)是一次外部调用 Bfs 的运行时间，最多调用 Bfs 次数(指外部调用)不超过 O(n)(存储结构为邻接表