1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 2及答案解析(总分：90.00，做题时间：90 分钟)一、单项选择题(总题数：30，分数：60.00)1.一棵二又树的前序遍历序列为 1234567，它的中序遍历序列可能是_。【北京工业大学 2001 年】（分数：2.00）A.3124567B.1234567C.4135627D.14365722.已知一棵二叉树的前序遍历结果为 123456，中序遍历结果为 321546，则后序遍历的结果为_。【哈尔滨工程大学 2001 年】（分数：2.00）A.325641B.654321C.325461D.不定3.己知某二叉树的后序遍历序列是 da
2、bec，中序遍历序列是 debac，它的前序遍历序列是_。【山东大学 2001 年】（分数：2.00）A.acbedB.decabC.deabcD.cedba4.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是_。【北京交通大学 2005 年】（分数：2.00）A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩予D.任一结点无右孩子5.某二叉树结点的中序序列为 BDAECF，后序序列为 DBEFCA，则该二叉树对应的森林包括_棵树。【中南大学 2003 年】（分数：2.00）A.1B.2C.3D.46.若唯一的确定一棵二叉树，只需要知道该二叉树的_。【北京交通大学 2004 年】
3、（分数：2.00）A.先序序列B.中序序列C.中序和后序序列D.先序和后序序列7.在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序_。【北京交通大学2001 年】（分数：2.00）A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同8.引入二叉线索树的目的是_。【南京理工大学 1998 年】（分数：2.00）A.加快查找结点的前驱或后继的速度B.为了能在二叉树中方便地进行插入与删除C.为了能方便地找到双亲D.使二叉树的遍历结果唯一9.二叉树在线索化后，仍不能有效求解的问题是_。【北京交通大学 2003 年】（分数：2.00）A.先序线索二
4、叉树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前驱D.后序线索二叉树中求后序后继10.若 x 是二叉中序线索树中一个有左孩子的结点，且 X 不为根，则 x 的前驱为_。【南京理工大学1996 年】（分数：2.00）A.X 的双亲B.X 的右子树中最左结点C.X 的左子树中最右结点D.X 的左了树中最右叶结点11.n 个结点的线索二叉树上含有的线索数为_。【中山大学 1998 年】（分数：2.00）A.2nB.n-1C.n+1D.n12._的遍历仍需要栈的支持。【中南大学 2001 年】（分数：2.00）A.前序线索树B.中序线索树C.后序线索树D.所有线索树13.在二
5、叉排序树中进行查找的效率与_有关。【北京航空航天大学 2004 年】（分数：2.00）A.二叉排序树的深度B.二叉排序树的结点的个数C.被查找结点的度D.二叉排序树的存储结构14.对一棵二叉排序树进行_遍历得到的结点序列是个有序序列。【湖南大学 2001 年】（分数：2.00）A.前序B.中序C.后序D.层次15.对于二叉排序树，下面的说法_是正确的。【华南理工大学 2006 年】（分数：2.00）A.二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合B.对二叉排序树进行层次遍历可得到有序序列C.用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大D
6、.在二叉排序树中进行查找，关键字的比较次数不超过结点数的 1216.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是_。【合肥工业大学2000 年】（分数：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)17.设二叉排序树中关键字由 11000 的整数构成，现要查找关键字为 363 的结点，下述关键字序列中，不可能是在二叉排序树上查找的序列是_。【北京交通大学 2005 年】（分数：2.00）
7、A.2，252，401，398，330，344，397，363B.924，220，911，244，898，258，362，363C.925，202，911，240，912，245，363D.2，399，387，219，266，382，381，278，36318.构造一棵具有 n 个结点的二叉排序树，最理想情况下的深度为_。【华中科技大学 2007 年】（分数：2.00）A.n2B.nC.log 2 (n+1)D.log 2 (n+1)19.从空树开始，依次插入元素 52、26、14、32、71、60、93、58、24 和 41 后构成了一棵二叉排序树。在该树查找 60 要进行比较次数为_。【广
8、东工业大学 2003 年】（分数：2.00）A.3B.4C.5D.620.含有 20 个结点的平衡二叉树的最大深度为_。【北京交通大学 2004 年】（分数：2.00）A.4B.5C.6D.721.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为 0、右孩子的平衡因子为 1，则应作_型调整以使其平衡。【北京交通大学 2005 年】（分数：2.00）A.LLB.LRC.RLD.RR22.已知一棵深度为 k 的平衡二叉树，其每个非叶子结点的平衡因子均为 0，则该树共有结点总数为_。【北京交通大学 2006 年】（分数：2.00）A.2 k-1 一
9、 1B.2 k-1 +1C.2 k 1D.2 k 十 123.在下列存储形式中，哪一个不是树的存储形式?_。【北京交通大学 2001 年】（分数：2.00）A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法24.设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 p，p 的右子树结点个数为 n，森林 F 中第一棵树的结点个数是_。【南京理工大学 2000 年】（分数：2.00）A.mnB.mn 一 1C.n+1D.条件不足，无法确定25.森林 T=(T1，T2，Tm)转化为二叉树 BT 的过程为：若 m=0，则 BT 为空；若 m0，则_。【太原科技大学 2006
10、年】（分数：2.00）A.将中间子树 Tmid(mid=(1 十 m)2)的根作为 BT 的根；将(T1，T2，Tmid1)转换为 BT 的左子树：将(Tmid 十，Tm)转换为 BT 的右子树B.将子树 T1 的根作为 BT 的根；将 T1 的子树森林转换成 BT 的左子树；将(T2，T3，Tm)转换成 BT 的右子树C.将子树 T1 的根作为 BT 的根；将 T1 的左子树森林转换成 BT 的左子树：将 T1 的右子树森林转换为 BT的右子树；其他依次类推D.将森林 T 的根作为 BT 的根；将(T1，T2，Tm)转化为该根下的结点，得到一棵树，然后将这棵树再转化为二叉树 BT26.在有
11、n 个叶予结点的赫夫曼树中，非叶子结点的总数为_。【中南大学 2003 年】（分数：2.00）A.n-1B.nC.2n 一 1D.2n27.有 n 个叶子的赫夫曼树的结点总数为_。【青岛大学 2002 年】（分数：2.00）A.不确定B.2nC.2n+1D.2n128.一棵赫大曼树共有 215 个结点，对其进行赫夫曼编码，共能得到_个不同的码字。【北京邮电大学2005 年】（分数：2.00）A.107B.108C.214D.21529.下列编码中_不是前缀码。【湖南大学 2003 年】（分数：2.00）A.00，01，10，11B.0，1，00，11C.0，10，110，111D.10，110
12、，1110，111130.给定整数集合3，5，6，9，12，与之对应的赫夫曼树是_。【华南理工大学 2007 年】（分数：2.00）A.B.C.D.二、综合题(总题数：15，分数：30.00)31.一棵二叉树以二叉链表来表示，求其指定的某一层 k(k1)上的叶予结点的个数。【上海大学 1999 年】（分数：2.00）_32.设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组 preLn和midL,n中，试遍写算法建立该二叉树的二叉链表。【南京航空航天大学 1999】（分数：2.00）_33.已知一具有 n 个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组 INL
13、,n和 POSTLn中(设该二叉树各结点的数据值均不相同)。请写一建立该二叉树的二叉链表结构的非递归算法。该二叉链表的链结点结构为(lchild，data，rchild)，其中 data 为数据域，lchild 与 rchild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用 NULL 表示)。【北京航空航天大学 2003年】（分数：2.00）_34.写出中序线索二叉树的线索化过程(已知二叉树 T)。【山东大学 2000 年】（分数：2.00）_35.已知一中序线索二叉树，写一算法完成对它的中序扫描。【山东大学 2001 年】（分数：2.00）_36.编写程序段，利
14、用中序全线索树求其中任意结点 p 的前序后继结点，结果仍用 p 指出。设线索树不带头结点，其中序序列第一个结点的左标志和最后一个结点的右标志皆为 0(非线索)，对应指针皆为空。【北京工业大学 2000 年】（分数：2.00）_37.写出在中序线索二叉树里查找指定结点在后序下的前驱结点的算法。【河海大学 1998 年】（分数：2.00）_38.已知中序线索二叉树 T 的右予树不空。设计算法，将 s 所指的结点作为 T 的右子树中的一个叶子结点插入进去，并使之成为 T 的右子树(中序序列)的第一个结点(同时要修改相应的线索关系)。【合肥工业大学 2001 年】（分数：2.00）_39.二叉树排序方
15、法如下：1)将第一个数据放在树根。2)将随后读入的数据与树根中的数据相比较，若比树根大，则置于右子树，反之则置于左子树，建成一棵二叉树。3)利用中序遍历打印排序结果。4)试用PASCAL 或 C 语言编写二叉树的排序程序。【浙江大学 1995 年】（分数：2.00）_40.编程求以孩予一兄弟表示法存储的森林的叶了结点数。要求描述结构。【北京工业大学 2000 年】【北京交通大学 2007】（分数：2.00）_41.以孩予一兄弟链表为存储结构，请设计递归和非递归算法求树的深度。【北方交通大学 1999 年】（分数：2.00）_42.将由图 3-2 所示的三棵树组成的森林转换为二叉树。(只要求给出
16、转换结果)【南京航空航天大学 1998年】 （分数：2.00）_43.已知一个森林的先序序列和后序序列如下，请构造出该森林。1)先序序列：ABCDEFGHIJKLMNO。2)后序序列：CDEBFHIJGAMLONK。【合肥工业大学 2000 年】（分数：2.00）_44.假定用于通信的电文仅有 8 个字母 C1，C2，C8 组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这 8 个字母设计赫夫曼编码。【上海海事大学 1998 年】（分数：2.00）_45.给定集合15，3，14，2，6，9，16，17。1)用口表示外部结点，用。表示内部结点，构造相应的Huff
17、man 树。2)计算它的带权路径长度。3)写出它的 Huffman 编码。【山东大学 1998 年】（分数：2.00）_计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 2答案解析(总分：90.00，做题时间：90 分钟)一、单项选择题(总题数：30，分数：60.00)1.一棵二又树的前序遍历序列为 1234567，它的中序遍历序列可能是_。【北京工业大学 2001 年】（分数：2.00）A.3124567B.1234567 C.4135627D.1436572解析：解析：考杏二叉树的遍历序列。由题可得 1 为根结点，并且 2 为 1 的孩子结点。对于 A 选项，3 应为 1 的左孩子
18、，前序遍历序列应为 13，不符。对于 B 选项，当 2 为 1 的右孩子，3 为 2 的右孩子时满足题目要求。对于 C 选项，类似 A 选项，前序遍历序列应该为 14。对于 D 选项，若 1 为中序第一个字母，则所有结点在 1 的右子树中，右子树根结点为 2，而 34 在 2 的左子树中，567 在 2 的右子树中才可满足前序序列，与中序遍历序列不符。2.已知一棵二叉树的前序遍历结果为 123456，中序遍历结果为 321546，则后序遍历的结果为_。【哈尔滨工程大学 2001 年】（分数：2.00）A.325641 B.654321C.325461D.不定解析：解析：考查由二叉树前序遍历序列
19、和中序遍历序列建造二叉树的方法。因为前序序列中 1 开头，所以根结点为 1。由中序序列可知 1 的左子树中含有 23，右子树中含有 456。再根据前序序列可知，2 为 3的父结点，4 为 56 的父结点。又由中序序列可知 3 为 2 的左孩子，5 为 4 的左孩子，6 为 4 的右孩子。画出二叉树如图 33 所示，可知后序遍历的结果。3.己知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是_。【山东大学 2001 年】（分数：2.00）A.acbedB.decabC.deabcD.cedba 解析：解析：考查由后序遍历序列和中序遍历序列建立二叉树的方法。类似
20、上题的方法，后序序列最后一个为根结点。所以 C 为根结点，根据中序序列得知 deba 都在 c 的左子树内。然后由后序序列可知 e 为 c左子树的根结点，由中序序列可知 d 为 e 的左孩予，ba 为 e 的右子树。再次分析可知 a 为 b 的右孩子。过程如图 3-4 所示。4.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是_。【北京交通大学 2005 年】（分数：2.00）A.空或只有一个结点B.高度等于其结点数 C.任一结点无左孩予D.任一结点无右孩子解析：解析：考查根据二叉树的遍历序列推导树形。由题可得，非空树的先序和后序相反，即“根左右”与“左右根”顺序相反，因此树只有根结点，
21、或者根结点只有左子树或右子树，依此类推，其子树有同样的性质，任意结点只能有一个孩子，才能满足先序序列和后序序列正好相反。树形应该为一个长链，所以选 B。5.某二叉树结点的中序序列为 BDAECF，后序序列为 DBEFCA，则该二叉树对应的森林包括_棵树。【中南大学 2003 年】（分数：2.00）A.1B.2C.3 D.4解析：解析：考查根据遍历序列推导树形以及森林的二叉树表示。根据中序以及后序序列推导树形如图35 所示。该二叉树表示一个有三棵树的森林，其根结点分别为 A、C、F。6.若唯一的确定一棵二叉树，只需要知道该二叉树的_。【北京交通大学 2004 年】（分数：2.00）A.先序序列B
22、.中序序列C.中序和后序序列 D.先序和后序序列解析：解析：考查确定二叉树所需的序列。前序序列和中序序列或后序序列和中序序列可唯一确定一棵二叉树。由前序序列和后序序列不能唯一确定一棵二叉树。7.在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序_。【北京交通大学2001 年】（分数：2.00）A.都不相同B.完全相同 C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同解析：解析：考查二叉树遍历中叶子结点的先后顺序。由于左子树的访问始终在右子树之前，所以不管采用何种遍历方式，所有叶子结点被访问的前后顺序是不变的。8.引入二叉线索树的目的是_。【南京理工大学 199
23、8 年】（分数：2.00）A.加快查找结点的前驱或后继的速度 B.为了能在二叉树中方便地进行插入与删除C.为了能方便地找到双亲D.使二叉树的遍历结果唯一解析：解析：考查引入二又线索树的目的。为充分利用二叉树的空链域，且加快查找结点的前驱或后继速度，故引入了二叉线索树。9.二叉树在线索化后，仍不能有效求解的问题是_。【北京交通大学 2003 年】（分数：2.00）A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前驱D.后序线索二叉树中求后序后继 解析：解析：考查线索化不能解决的问题。后序线索二叉树中不能有效解决求后序后继的问题。10.若 x 是二叉中序线索树
24、中一个有左孩子的结点，且 X 不为根，则 x 的前驱为_。【南京理工大学1996 年】（分数：2.00）A.X 的双亲B.X 的右子树中最左结点C.X 的左子树中最右结点 D.X 的左了树中最右叶结点解析：解析：考杳二叉树的中序线索化过程。二叉中序线索树中，某结点若有左孩子，则按照中序“左根右”的顺序，该结点的前驱结点为左子树中最右的一个结点。11.n 个结点的线索二叉树上含有的线索数为_。【中山大学 1998 年】（分数：2.00）A.2nB.n-1C.n+1 D.n解析：解析：考查线索二叉树的线索数。n 个结点共有链域指针 2n 个，其中，除根结点外，每一个结点都被一个指针指向。剩余的链域
25、建立线索，共 2n(n1)=n+1 个线索。12._的遍历仍需要栈的支持。【中南大学 2001 年】（分数：2.00）A.前序线索树B.中序线索树C.后序线索树 D.所有线索树解析：解析：考查各种顺序遍历是否需要栈。不需要栈的支持仍可遍历则有：结点的左子树不为空时，它的前驱是其父结点或者左子树的结点；结点的右子树不为空时，它的后继是其父结点或者右子树的结点。显然，前序和中序线索树都满足这个条件，而后序线索树不满足。13.在二叉排序树中进行查找的效率与_有关。【北京航空航天大学 2004 年】（分数：2.00）A.二叉排序树的深度 B.二叉排序树的结点的个数C.被查找结点的度D.二叉排序树的存储
26、结构解析：解析：考查二叉排序树查找效率的决定因素。二叉排序树查找算法的平均查找长度，主要取决于树的高度。14.对一棵二叉排序树进行_遍历得到的结点序列是个有序序列。【湖南大学 2001 年】（分数：2.00）A.前序B.中序 C.后序D.层次解析：解析：考查二叉排序树的性质。对二叉排序树进行中序遍历是可以得到一个有序序列的。15.对于二叉排序树，下面的说法_是正确的。【华南理工大学 2006 年】（分数：2.00）A.二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合B.对二叉排序树进行层次遍历可得到有序序列C.用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排
27、序树的深度最大 D.在二叉排序树中进行查找，关键字的比较次数不超过结点数的 12解析：解析：考查二又排序树的相关性质。二叉排序树插入新结点时不会引起树的分裂组合。对二叉排序树进行中序遍历可得到有序序列。当插入的关键字有序时，二叉排序树会形成一个长链，此时深度最大。在此种情况下进行查找，有可能需要比较每个结点的关键字，超过结点数的 12。16.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是_。【合肥工业大学2000 年】（分数：2.00）A.(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90)C.(100，60，80，9
28、0，120，110，130) D.(100，80，60，90，120，130，110)解析：解析：考查二叉排序树的构造过程。按照二又排序树的构造方法，不难得到 A、B、D 序列的构造结果相同。17.设二叉排序树中关键字由 11000 的整数构成，现要查找关键字为 363 的结点，下述关键字序列中，不可能是在二叉排序树上查找的序列是_。【北京交通大学 2005 年】（分数：2.00）A.2，252，401，398，330，344，397，363B.924，220，911，244，898，258，362，363C.925，202，911，240，912，245，363 D.2，399，387，21
29、9，266，382，381，278，363解析：解析：考查二叉排序树的查找。在二叉排序树上查找时，先与根结点值进行比较，若相同，则查找结束，否则根据比较结果，沿着左子树或右子树向下继续查找。根据二叉排序树的定义，有左子树结点值根结点值右子树结点值。C 序列中，比较 911 关键字后，应转向其左子树比较 240，左子树中不应出现比 911 更大的数值，但是 240 竟有一个右孩子结点值为 912，所以不可能是正确的序列。18.构造一棵具有 n 个结点的二叉排序树，最理想情况下的深度为_。【华中科技大学 2007 年】（分数：2.00）A.n2B.nC.log 2 (n+1)D.log 2 (n+
30、1) 解析：解析：考查二叉排序树的最小深度。当二叉排序树的叶子结点全部都在相邻的两层内时，深度最小。理想情况是从第一层到倒数第二层为满二叉树。类比完全二叉树，可得深度为log 2 (n+1)。19.从空树开始，依次插入元素 52、26、14、32、71、60、93、58、24 和 41 后构成了一棵二叉排序树。在该树查找 60 要进行比较次数为_。【广东工业大学 2003 年】（分数：2.00）A.3 B.4C.5D.6解析：解析：考查二叉排序树的建立和查找。以第一个元素为根结点，依次将元素插入到排序树当中。进行查找时，先与根结点比较，然后根据比较结果，继续在左子树或者右子树上进行查找。20.
31、含有 20 个结点的平衡二叉树的最大深度为_。【北京交通大学 2004 年】（分数：2.00）A.4B.5C.6 D.7解析：解析：考查给定结点数的平衡二叉树的最大深度。平衡二叉树结点数的递推公式为：N 0 =0，N 1 =1，N 2 =2，N h =1+N h-1 +N h-2 (h 为平衡二叉树高度，N h 为构造此高度的平衡二叉树所需最少结点数)。通过递推公式可得，构造 5 层平衡二叉树至少需要 12 个结点，构造 6 层至少需要 20 个结点。21.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为 0、右孩子的平衡因子为 1，则应作_
32、型调整以使其平衡。【北京交通大学 2005 年】（分数：2.00）A.LLB.LRC.RL D.RR解析：解析：考查平衡二叉树的插入。左孩子的平衡因子为 0，右孩子的平衡因子为 1，说明不平衡是因为在右子树的左子树上插入结点引起的，应作 RL 调整。22.已知一棵深度为 k 的平衡二叉树，其每个非叶子结点的平衡因子均为 0，则该树共有结点总数为_。【北京交通大学 2006 年】（分数：2.00）A.2 k-1 一 1B.2 k-1 +1C.2 k 1 D.2 k 十 1解析：解析：考查特殊的平衡二叉树结点数的计算。每个非叶子结点的平衡因予为 0，说明该平衡二叉树为满二叉树，所以结点总数为 2
33、k 一 1。23.在下列存储形式中，哪一个不是树的存储形式?_。【北京交通大学 2001 年】（分数：2.00）A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法 解析：解析：考查树的存储形式。A、B、C 为树常用的存储形式。顺序存储表示法可以用来存储二叉树，但是不可用来存储树。24.设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 p，p 的右子树结点个数为 n，森林 F 中第一棵树的结点个数是_。【南京理工大学 2000 年】（分数：2.00）A.mn B.mn 一 1C.n+1D.条件不足，无法确定解析：解析：考查森林对应的二叉树。森林转换成二叉树时采用孩子
34、一兄弟表示法，根结点及其左子树为森林中的第一棵树，右子树为其他树。所以第一棵树的结点个数为 m-n。25.森林 T=(T1，T2，Tm)转化为二叉树 BT 的过程为：若 m=0，则 BT 为空；若 m0，则_。【太原科技大学 2006 年】（分数：2.00）A.将中间子树 Tmid(mid=(1 十 m)2)的根作为 BT 的根；将(T1，T2，Tmid1)转换为 BT 的左子树：将(Tmid 十，Tm)转换为 BT 的右子树B.将子树 T1 的根作为 BT 的根；将 T1 的子树森林转换成 BT 的左子树；将(T2，T3，Tm)转换成 BT 的右子树 C.将子树 T1 的根作为 BT 的根；
35、将 T1 的左子树森林转换成 BT 的左子树：将 T1 的右子树森林转换为 BT的右子树；其他依次类推D.将森林 T 的根作为 BT 的根；将(T1，T2，Tm)转化为该根下的结点，得到一棵树，然后将这棵树再转化为二叉树 BT解析：解析：考查森林转化成二叉树的过程。将森林中每棵树的根结点看成是兄弟结点的关系，再按照“左孩子右兄弟”的规则来进行转化。26.在有 n 个叶予结点的赫夫曼树中，非叶子结点的总数为_。【中南大学 2003 年】（分数：2.00）A.n-1 B.nC.2n 一 1D.2n解析：解析：考查赫夫曼树非叶子结点的计算。赫夫曼树是二叉树。非空二叉树上叶子结点数等十度为 2的结点数
36、加 1。赫大曼树中度为 1 的结点个数为 0。所以叶子结点数一 1 即为非叶子结点数。27.有 n 个叶子的赫夫曼树的结点总数为_。【青岛大学 2002 年】（分数：2.00）A.不确定B.2nC.2n+1D.2n1 解析：解析：考查赫夫曼树结点总数的计算。根据“非空二叉树上叶子结点数等于度为 2 的结点数加 1”，度为 2 的结点数为 n 一 1，结点总数为 2n1。28.一棵赫大曼树共有 215 个结点，对其进行赫夫曼编码，共能得到_个不同的码字。【北京邮电大学2005 年】（分数：2.00）A.107B.108 C.214D.215解析：解析：考查赫夫曼树叶子结点数的计算。根据上题结论，
37、叶子结点数为(215+1)2=108，所以共有108 个不同的码字。29.下列编码中_不是前缀码。【湖南大学 2003 年】（分数：2.00）A.00，01，10，11B.0，1，00，11 C.0，10，110，111D.10，110，1110，1111解析：解析：考查前缀码的定义。如果没有一个编码是另一个编码的前缀，称这样的编码为前缀编码。B选项中，0 是 00 的前缀，1 是 11 的前缀。30.给定整数集合3，5，6，9，12，与之对应的赫夫曼树是_。【华南理工大学 2007 年】（分数：2.00）A.B.C. D.解析：解析：考查赫夫曼树的构造方法。先是 3 和 5 构造为一棵子树，
38、其根权值为 8；接着该子树与 6 构成一棵新子树，根权值为 14；然后 9 与 12 构造为一棵子树;最后两棵子树共同构造为一棵赫夫曼树。二、综合题(总题数：15，分数：30.00)31.一棵二叉树以二叉链表来表示，求其指定的某一层 k(k1)上的叶予结点的个数。【上海大学 1999 年】（分数：2.00）_正确答案：(正确答案：算法的基本设计思想：采用队列结构按层次遍历，遍历 K 层时记录叶子结点个数。算法的代码： int LeafKlevel(BiTree bt，int k) 求二叉树 bt 的第 k(k1)层上叶子结点个数 if(bt=NULL 1 I kichild!p-rchild)
39、 1ear+； 叶子结点 if(p 一1chiid) Q+rear：p 一lchiid， 左子女入队 if(p 一rchiid) Q+rear=p 一rchiid； 右子女入队 if(front=last) level+； 二叉树同层最右结点已处理，层数增 1 last=rear； last 移到指向下层最右一元素 if(1evelk) 层数大于 k 后退出运行 return leaf； while LeafKLevel)解析：32.设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组 preLn和midL,n中，试遍写算法建立该二叉树的二叉链表。【南京航空航天大学 19
40、99】（分数：2.00）_正确答案：(正确答案：算法的基本设计思想：采用递归算法，取前序序列第一个结点为根，递归建立左、右子树。算法的代码： void PreInCreat(BiTree root，ElemType pre，ElemType mid，int 1l，int hl，int 12，int h2) 根据二叉树前序序列 pre 和中序序列 mid 建立二叉树 11、h1、12、h2 是序列第一和最后元素的下标 root=(BiTree)malloc(SiZeof(BiNode);申请结点 root 一data=pre11； pre11是根结点 for(i=12；ilchild=NULL;
41、 无左子树 else 递归建立左子树 PreInCreat(root 一lchiid，pre，mid，11+l，11+(i 一 12)，12，i 一 1)， if(i=h2) root 一rchild=NULL； 无右子树 else 递归建立右子树 PreInCreat(root 一rchild，pre，mid，11+(i 一 12)+1，h1，i+1，h2)； PreInCreat)解析：33.已知一具有 n 个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组 INL,n和 POSTLn中(设该二叉树各结点的数据值均不相同)。请写一建立该二叉树的二叉链表结构的非递归算法。该二叉链表的链
42、结点结构为(lchild，data，rchild)，其中 data 为数据域，lchild 与 rchild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用 NULL 表示)。【北京航空航天大学 2003年】（分数：2.00）_正确答案：(正确答案：算法的基本设计思想：开始时考查整个中序序列和后序序列，将中序序列和后序序列的起始信息封装到结构体中，入栈。当栈不为空时，循环执行操作：取出栈顶元素，按照结构体所指示出的两段序列，将元素的结点赋值为后序序列的最后一个结点；若此结点有左子树，挂接左孩子并将左子树的中序和后序信息封装入栈；若有右子树，挂接右孩子并将右子树中序和
43、后序信息入栈。直到栈空为止。算法的代码： typedef Struct int 11 l h1 t 12，h2； BiTree t; node； void InPostCreat(ElemType IN，ElemType POST，int 1，int hl，int 12，int h2) 由二叉树的中序序列 IN和后序序列 POST建立二叉树，11、h1 和 12、h2 分别 是中序序列和后序序列第一和最后元素的下标，初始调用时，11=12=1、hl=h2=n node S，P； s 是栈，容量足够大 BiTree bt=(BiTree)mellOC(SiZeof(BiNode)； int top=0，i； P11=11; 初始化 Ph1=h1； P12=12; Ph2=h2； Pt=bt； S+top=P; while(top0) p=stop 一
