1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 12 及答案与解析一、综合题1 已知下列字符 A、B、C、D、E、F、G 的权值分别为 3、12、7、4、2、8，11，试填写出其对应哈夫曼树 HT 的存储结构的初态和终态。【北京工业大学 1998 五(10 分)】1 设 T 是一棵二叉树，除叶子结点外，其他结点的度数皆为 2，若 T 中有 6 个叶结点，试问：2 T 树的最大可能深度 Kmax=?最小可能深度 Kmin=?3 T 树中共有多少非叶结点?4 若叶结点的权值分别为 1，2，3，4，5，6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度 wp1。【北京邮电大学 1992
2、 一、3(153 分)】5 已知 4 个字符 A，E C，D 的哈夫曼编码分别是 1，01，000,001。下列 01 串是由以上 4 个字母构成的一段文本的哈夫曼编码：1001000011011010011010011请将上述 01 串还原为编码前的文本。以字符在文本中出现的次数为权值，求出这棵树的带权路径长度。【电子科技大学 2013 三、1(5 分)】6 什么是前缀编码? 举例说明如何利用二叉树来设计二进制的前缀编码。【中山大学 1999 三、1(3 分) 】二、设计题6 二叉树的带权路径长度(WPL) 是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树 T，采用二叉链表存储，结点结
3、构为： ，其中叶结点的 weight 域保存该结点的非负权值。设 root 为指向 T 的根结点的指针，请设计求 T 的 WPL 的算法，要求：7 给出算法的基本设计思想；8 使用 C 或 C+语言，给出二叉树结点的数据类型定义；9 根据设计思想，采用 C 或 C+语言描述算法，关键之处给出注释。【2014 年全国试题 41(13 分) 】10 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树 BT 中，写出计算该算术表达式值的算法。【东北大学 2000 三、2(10 分)】11 给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。【北京邮电大学 2001 五、3(
4、10 分)】12 设计一算法分别求出二元树的叶结点，度数为 l 的结点，度数为 2 的结点的个数。【哈尔滨工业大学 2002 八(8 分)】13 已知深度为 h 的二叉树，以一维数组 BT0 2h-2作为其存储结构，试编写一算法，求该二叉树中叶子结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相应的算法。【中南大学 2003 八(10 分)】14 假定用两个一维数组 LN和 RN作为有 N 个结点 1，2，N 的二元树的存储结构。Li和 Ri分别指示结点 i 的左儿子和右儿子；Li=O(Ri=0)表示 i 的左(右)儿子为空。试写一个算法，由 L 和 R 建立一个一
5、维数组 Tb，使 Ti存放结点i 的父亲；然后再写一个判别结点 U 是否为结点 V 的后代的算法。【哈尔滨工业大学 1999 七(14 分) 】【华南师范大学 2000 六(17 分)】15 要求二叉树按二叉链表形式存储。(1)写一个建立二叉树的算法。(2)写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为 K，具有 N 个结点的二叉树的每个结点都与深度为 K 的满二叉树中编号从 1 至的结点一一对应。此题以此定义为准。【西北大学 2000 六(12 分)】【哈尔滨工业大学 2000 十一(14 分) 】【南开大学 1997 四 (16 分)】【北京邮电大学 1994 九(
6、20分)】16 有 n 个结点的完全二叉树存放在一维数组 A1n中，试据此建立一棵用二叉链表表示的二叉树，根由 tree 指向。【南京理工大学 1998 七、1(6 分)】【同济大学2005 三、2(7 分) 】17 设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中。(注：按层从上到下，由左到右)。【中科院研究生院 2005 四(15 分)】18 已知深度为 h 的二叉树采用顺序存储结构已存放于数组 BT1：2 h 一 1】中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child，data，rchild)，根结点所在链结点的指针由 T 给出。【北
7、京师范大学 2005六、3(15 分)】【北京航空航天大学 1999 七(15 分)】19 二叉树的动态二叉链表结构中的每个结点有三个字段：dam，lchild，rchild。其中指针 lchild 和 rchild 的类型为 bike。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。所不同的是，lchild 和 rdhild 为 integer 型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为 0。例如，下面左图所示的二又树的静态二叉链表如右图所示。编写算法由二叉树的动态二叉链表构造出相应的静态二又链表 a
8、1n，并写出其调用形式和有关的类型描述。其中 n 为一个确定的整数。【合肥工业大学 2000 五、3(8 分)】20 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。(注：已知树中结点数)【清华大学 1994 七(15 分)】21 设一棵二叉树用二叉链表表示，求该树的高度。【南京航空航天大学 2004 二、2(12 分 )】【 北京理工大学 2000 四 3(4)】【北京轻工业学院 1997 一(15 分)】22 二叉树以链接形式(1eft ，data，right)存储，给出求二叉树宽度的算法，所谓宽度是二又树的各层上，具有结点数最多的那一层上的结点总数。
9、 【吉林大学 2006四(10 分 )】【 华南理工大学 2004 三、1(10 分) 】23 以孩子兄弟链表为存储结构，请设计递归和非递归算法求树的深度。【北方交通大学 1999 五(18 分) 】【南京航空航天大学 2000 九】24 设一棵二叉树的结点结构为(LLINK ，INFO，RLINK) ，ROOT 为指向该二叉树根结点的指针，p 和 g 分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR(RDOT，p，q，r)，该算法找到 p 和 q 的最近共同祖先结点 r。【吉林大学 2000 二、3(12 分) 】【中山大学 1994 六(15 分)】25 当一棵有 n(
10、0left，iv+1) ； 中序遍历左子树if(bt 一left=null&bt 一right=null) 判断该结点是否为叶子WPL+=(iv 一 1)*bt 一weight； 累加结点带权路径长度inorder(bt 一 right，Iv+1)； 中序遍历右子树10 【正确答案】 以后序遍历方式遍历算术表达式的二叉树可以得到后缀表达式，后缀表达式求值已在前面讲过。这里给出另一种算法。重新定义二叉树结点结构为(1eft，data，val ，fight) ，其中 left 和 fight 是左右子女的指针，data 是算法表达式中的字符，val 是子表达式的值。采用后序遍历，先分别求出左子树和
11、右子树表示的子表达式的值，最后计算出表达式的最后结果。算法如下：int PostEval(BiTree bt) 以后序遍历算法求以二叉树表示的算术表达式的值BiTree p=bt；int Iv，rv；if(p)(1v=PostEval(p 一lef)； 求左子树表示的子表达式的值rv=PostEval(p 一right)； 求右子树表示的子表达式的值if(!P 一left&!P 一right) 叶子结点将数据值存到 val 域中P 一val ： P 一data 一0； 数字字符转成整数存储else switch(p 一data) 求子表达式的值case+：P 一val=p 一left 一val
12、+p 一right 一val；break ；case 一：p 一Val=p 一left 一valP 一right 一val；break ；case *：p-val=p-left 一vai。P 一right 一val；break；case ：p 一Val=p 一1ef 七一valp 一right 一val；return(p-val)； 本算法中数值是以字符表示的，因此是一位数的算术运算。若是多位数(包括实数)，要做如下修改：在建立二叉树时进行拼数，一个数输入完毕再存入二叉树结点中；本算法中的 p 一val=p 一data 一 0，要改为 p 一Val=p 一data；lv 和 rv 的类型做相应
13、改变。拼数算法的核心语句段如下：case 0=0&Xx ； num 初始值为 00else 处理小数部分scale=10 0；cinx；while(x=0&xx； 11 【正确答案】 这是用二叉树表示符号算术表达式的逆问题，即将二叉树表示的表达式还原成原表达式。二叉树的中序遍历序列与原算术表达式基本相同，差别仅在于二叉树表示中消除了括号。将中序序列加上括号就恢复原貌。当根结点运算符优先级高于左子树(或右子树)根结点运算符时，就需要加括号。核心语句段如下：if(bt)(if(bt 一ichild!=null)fbracket：Precede(bt 一data，bt 一ichild 一data)
14、双亲与左子女运算符优先级if(bracket=1)printf()；InorderExp(bt 一ichild)； 输出左子女表示的算术表达式if(bracket=1)printf()； 加上右括号printf(bt 一data) ； 输出根结点if(bt 一rchild!=null) 输出右子树表示的算术表达式bracket=Precede(bt-data，bt 一rchild-data)if(bracket=1)printf(“C)； 右子女级别低，加括号InorderExp(bt-rchi id)；if(bracket=1)printf(“)”)；12 【正确答案】 结点计数可以在遍历中
15、解决。根据“访问根结点” 、“递归调用左子树”、“递归调用右子树 ”三者位置的不同，而有前序、后序和中序遍历。叶子结点是左右子女均无的结点，度为 1 的结点是只有一个子女的结点，度为 2 的结点是左右子女均有的结点。13 【正确答案】 按完全二叉树形式顺序存储二叉树时，无元素的位置要当作“虚结点”。根据本题 “二叉树中元素结点为非负整数 ”，可以设虚结点为负数。设结点序号为 i(根结点编号为 0)，则当 ih-1)2(最后一个分支结点)时，若其 2f+1 和 2i+2 位置为虚结点，则 i 为叶子结点；当 i(2h-1)2 时，若 i 位置不是虚结点，则必为叶子结点。核心语句段如下： for(
16、i=0；i k 一 1 if(i0)num+； 存储在数组后一半的元素是叶子结点14 【正确答案】 由指示结点 i 左儿子和右儿子的两个一维数组 Li和 Ri，建立指示结点 i 的双亲的一维数组 Ti，根据 T 数组，判断结点 U 是否是结点 V 后代的算法，转为判断结点 V 是否是结点 U 的祖先的问题。核心语句段如下：for(i=i ； ix； 本题假定结点数据域为整型if(x=0)bt=null； 空指针else if(x0)bt=new(BiNode)； 申请空间bt-data=x； bt-ichild=creat() ；bt-rchiId=creat()；else error(“输入
17、错误”)；return(bt)；判定是否是完全二叉树，可以使用队列，在遍历中利用完全二又树“若某结点无左子女就不应有右子女” 的原则进行判断。判断时易犯的错误是由左子树和右子树都是完全二叉树，推出整棵二叉树必是完全二叉树的错误结论。核心语句段如下：if(p=null)return(1)； p 是二叉树QueueInit(Q)；QueueIn(Q，p)； 初始化队列，根结点指针入队while(!QueueEmpty(Q)(p=Queueout(Q)； 出队if(p-ichild&!tag)QueueIn(Q，p-ichild)； 左子女入队else if(p 一 ichild)return 0；
18、 前边已有结点为空，本结点不空else tag=l； 首次出现结点为空if(p 一rchild&!tag)QueueIn(Q，P 一rchild) ； 右子女入队else if(p-rchiid)return 0；else tag=1 ； while16 【正确答案】 BiTree Creat(EiemType A，int i)初始调用时，i=iBiTree tree；if(idata=Ai；if(2*in)tree-ichild=null ；ease tree-Ichild=Creat(A，2*i)；if(2*i+1n)tree-rchild=null ；e18e tree-rchild=C
19、reat(A，2*i+1) ；return(tree)；17 【正确答案】 将以二叉链表存储的二叉树转为顺序存储结构，要按完全二叉树形式顺序存储，无元素的位置要当作“虚结点” 。一维数组 A 空间要足够大，开始将一维数组元素都初始化为虚结点。然后将二叉树的结点存入 A 的适当位置上。核心语句段如下：if(bt)fAi=bt 一data ； 初始调用时，i=1if(bt 一ichild)Creat(A ，2*i，bt-Ichiid)；if(bt-rchild)Creat(A，2*i+1，bt-rchild)；18 【正确答案】 设栈 S，元素结构是 (int hum，BiTree bt)，初始调
20、用 num=1；设n=2n 1。 top=1；S1=1，bt； while(i0) j=stop.num；t=Stop 一一.bt ； if(BTj!=#11#是虚结点 t=new(BiNode)；t-data=BTj； if(BTj*2+1!=#) S+top=j*2+1，bt 一rchild)； i=2*j； 19 【正确答案】 静态链表中结点是按动态二叉链表的前序遍历顺序存放的。首先对动态二叉链表的二叉树进行前序遍历，填写静态链表的“下标” 和 data 域，再对动态二叉链表的二叉树进行层次遍历，设队列 Q，填写静态链表的 lchild 域和rchild 域。20 【正确答案】 以双亲表
21、示法作树的存储结构，对每一结点，找其双亲，双亲的双亲，直至(根) 结点，就可求出每一结点的层次，取其结点的最大层次就是树的深度。核心语句段如下：int maxdepth=0；for(i=1；io)temp+； t=tnodesfparent ； 深度加 1，并取新的双亲if(tempmaxdepth) maxdepth=temp； 最大深度更新return(maxdepth)； 返回树的深度21 【正确答案】 二叉树是递归定义的，其运算最好采取递归方式。int Height(btre bt) 求二叉树 bt 的深度fint hl，hr ； hl 和 hr 分别是左子树和右子树的深度if(bt=
22、null)return(0)；else(hl=Height(bt 一ich)；hr=Height(bt 一rch)；if(h1hr)return(hl+1)； else return(hr+1) ；22 【正确答案】 求最大宽度可采用层次遍历的方法，记下各层结点数，取其最大宽度。Qrear=bt； 根结点入队列while(frontichild!=null) Q+rear=p 一Ichild ； 左子女入队if(p 一rchild!=null) Q+rear=p 一rchild； 右子女入队if(frontlast) 一层结束last=rear； last 指向下层最右元素if(tempmax
23、w)maxw=temp； 更新当前最大宽度，maxw 记最大宽度temp=0； 准备下层 ifwhile23 【正确答案】 由孩子兄弟链表表示的树高度的递归模型是：若树为空，高度为零；若第一子女为空，高度为 1 和兄弟子树高度的大者；否则，高度为第一子女树高度加 1 和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。递归算法的核心语句段如下：if(bt=null)return(0)；else if(1bt-firstchild)return(max(1，height(bt-nextsibling)；else(hc=height(bt 一firstchild)； 第一子女树高
24、hs=height(bt 一nextsibling)； 兄弟树高if(hc+lhs)return(hc+1)； else return(hs)； else非递归遍历求以孩子兄弟链表表示的树的深度的核心语句段如下：Qrear=t； Q 是以树中结点为元素的队列while(frontfirstchild)Q+rear=t 一firstchild；第一子女入队t=t 一nextsibling ； 同层兄弟指针后移if(frontlast) 本层结束，深度加 1(初始深度为 0)h+；last=rear； last 再移到指向当前层最右一个结点24 【正确答案】 本题到 22 题是在以二叉链表存储的二
25、叉树上找某结点的所有祖先，某两个结点的最近公共祖先，从根结点到某结点的路径，根结点到每个叶子结点以及最远叶子的路径等。均应采取后序非递归遍历。因为后序遍历最后访问根结点，当访问到某结点时，栈中所有元素均为该结点的祖先。这里只对 16 题进行分析。找 p 和 q 的最近共同祖先结点 r，不失一般性，设 P 在 q 的左边。后序遍历必然先遍历到结点 P，栈中元素均为 P 的祖先。将栈复制到另一辅助栈中。再继续遍历到结点 q 时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配(即相等)的元素就是结点 p 和 q 的最近公共祖先。其核心语句段如下：while(bt!=null top0)whil
26、e(bt!=nullbt!=p&bt!=q) 结点入栈S+top.t=bt ； stoptag=0 ；bt=bt 一ichild； 沿左分支向下if(bt=p)假定 P 在 q 的左侧，遇结点 P 时，栈中元素均为 P 的祖先结点for(i=1；i0 ； i 一 ) 将栈中元素到 sl 去匹配pp=si t；for(j=topl； j0；j-)if(sljt=pp)coutrchild ； 沿右分支向下遍历结束 while(bt!=null top0)return(null)；q、p 无公共祖先25 【正确答案】 二叉树顺序存储，是按完全二叉树的格式存储，利用完全二叉树双亲结点与子女结点编号间
27、的关系进行求解。设结点值为 x 和 y 的两个结点的下标分别是 i 和 j，求下标为 i 和 j 的双亲，双亲的双亲，等等，直至找到最近的公共祖先。while(i!=j) 直到 i=j 时，就是原来两个结点的最近的公共祖先if(ij)i=i2 ； 下标为 x 的结点的双亲结点的下标else j=j2 ； 下标为 Y 的结点的双亲结点的下标26 【正确答案】 二叉树的顺序存储一般按完全二叉树的顺序存储格式，双亲与子女结点下标间有确定关系。顺序存储结构的二叉树用结点下标大于 n(对于完全二叉树)或 0(对一般二叉树的“ 虚结点”)来判空。本题是完全二叉树，核心语句段如下：while(i0) 初始调
28、用时，i=1，top=0while(i0)i=stop 一一； 取出栈顶元素27 【正确答案】 另一种双亲表示法存储结构，结点结构是(dam,parent)。对每个结点，直接给出其双亲(的下标)，用正或负表示该结点是双亲的右子女或左子女，0表示该结点是根，无双亲。该类结构不适于直接进行前序遍历(即若直接前序遍历，算法要很复杂)，较好的办法是将这类结构转为结点及其左右子女的顺序存储结构。转换的核心语句段如下：for(i=1；i0) bttiparent rc=i ； 右子女else root=i； root 记住根结点的下标前序递归和非递归遍历上面已有，不再赘述。这类问题的求解方法值得注意。当给
29、定数据存储结构不合适时，可由已给结构来构造好的数据结构，以便于运算。像上面第 6 题也是这样，先根据 L 和 R 数组，构造一个结点的双亲的数组 T。28 【正确答案】 二叉树先序序列最后一个结点的特征是：从根开始的任何结点，若有右子树，则是右子树中最右下的叶子结点；若无右子树，仅有左子树，则是左子树最右下的叶子结点。核心语句段如下：while(p) 设 p 是二叉树根结点的指针f(p-rchild)p=p 一rchild ； 若右子树不空，沿右子树向下else if(p 一1child)p=p 一lchild； 右子树空，左子树不空，沿左子树向下else return(p)； p 即为所求2
30、9 【正确答案】 高度为 K 的二叉树，按顺序方式存储，要占用 2k 一 1 个存储单元，与实际结点个数 n 关系不大，对不是完全二叉树的二叉树，要增加“虚结点” ，使其在形态上成为完全二叉树。二叉树中最大序号的叶子结点是在顺序存储方式下编号最大的结点。核心语句段如下：while(btc=0)c 一一； 初值 c=2k 一 1，从后向前滤去虚结点找最大序号叶子 f=c2 ； c 的双亲结点 f while(f!=0) 从结点 c 的双亲结点直到根结点，路径上所有结点均为祖先结点 coutcbtf)；f=f2 ； 逆序输出，最老的祖先最后输出30 【正确答案】 将空指针(下面的 pre)域改成指
31、向双亲(或祖先)。核心语句段如下：while(t) t 初值是二叉树根结点的指针while(t)cohtdata ； 访问结点t 一pre=f； 指向双亲，初值 f=nullf=t；t=t 一lchild； 沿左侧向下t=f； 回退while(t&t 一rchild=null) t=t 一pre ； 回返if(t&t 一rchild)f=t 一pre； 避免从右侧返回时，再重复访问左侧t=t 一rchild； 右转31 【正确答案】 wh51e(p top0) p 是二叉树指针，top 是栈顶指针，初值为 0while(p)s+top=p；p=p 一lchild；) 沿左子树向下if(top)
32、0)p=stop 一；coutdata； p=p 一rchild；)退栈，访问，转右子树32 【正确答案】 二叉树用顺序方式存储，其遍历方法与用二叉链表方式存储类似。0 表示空指针。顺序存储方式下，要告诉根结点的下标。void InOrder(int i) 对顺序存储的二叉树进行中序遍历，i 是根结点的下标if(i!=0)InOrder(ariLc)； 中序遍历左子树coutaridata ； 访问根结点Inorder(ariRc)； 中序遍历右子树 结束 Inorder33 【正确答案】 设一队列 Q 和栈 S。将根结点入队。当队列不空，做如下操作：Q 出队；出队元素入栈 S；出队结点的非空左、右子女依次入队 Q。队列空后，弹出栈 S 中元素即为所求。
