计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编13
(总分：66.00，做题时间：90分钟)
一、 综合题(总题数：4，分数：12.00)
1.已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。【北京工业大学1998五(10分)】
__________________________________________________________________________________________
正确答案：(正确答案：)
设T是一棵二叉树，除叶子结点外，其他结点的度数皆为2，若T中有6个叶结点，试问：（分数：6.00）
(1).T树的最大可能深度Kmax=?最小可能深度Kmin=?
二叉树定义__________________________________________________________________________________________
正确答案：(正确答案：(1)T树的最大深度：Kmax=6(除根外，每层均是两个结点)。T树的最小深度Kmin=4(具有6个叶子的完全二叉树是其中的一种形态)。)
(2).T树中共有多少非叶结点?
__________________________________________________________________________________________
正确答案：(正确答案：非叶子结点数是5(n2=n0—1)。)
(3).若叶结点的权值分别为1，2，3，4，5，6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wp1。【北京邮电大学1992一、3(15／3分)】
__________________________________________________________________________________________
正确答案：(正确答案：哈夫曼树见右图，其带权路径长度wp1=51。从本题到97题都是哈夫曼树的试题。学生在构造哈夫曼树时常犯的错误是，在选出当前两个最小权值的结点构造二叉树后，没有把刚构造出来的二叉树的根结点加入待构造的结点中，造成最终的“哈夫曼树”是向一个方向倾斜的。值得指出的是，多数教材对哈夫曼编码规则是：哈夫曼树的左分支为0，右分支为1，个别教材规定左分支为1，右分支为0。限于篇幅，不再给出答案。)
2.已知4个字符A，E C，D的哈夫曼编码分别是1，01，000,001。下列01串是由以上4个字母构成的一段文本的哈夫曼编码：1001000011011010011010011请将上述01串还原为编码前的文本。以字符在文本中出现的次数为权值，求出这棵树的带权路径长度。【电子科技大学2013三、1(5分)】
__________________________________________________________________________________________
正确答案：(正确答案：A出现5次，B出现4次，C出现1次，D出现3次带权路径长度WPL=(1+3)*3+4*2+5*1=25。)
3.什么是前缀编码?举例说明如何利用二叉树来设计二进制的前缀编码。【中山大学1999三、1(3分)】
__________________________________________________________________________________________
正确答案：(正确答案：前缀码是一编码不是任何其他编码前缀的编码。例如，0和01就不是前缀码，因为编码0是编码01的前缀。顺便说明，仅从编码来看，0和01是前缀码，但因历史的原因，它不被称为前缀码，而是把一编码不是另一编码前缀的编码称为前缀码。利用二叉
树可以构造前缀码，例如，以A，B，C，D为叶子可构成二叉树，将左分支解释为0，右分支解释成1，从根结点到叶子结点的0、1串就是叶子的前缀码。用哈夫曼树可构造出最优二叉树，使编码长度最短，称为哈夫曼编码。)
二、 设计题(总题数：25，分数：54.00)
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为：，其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求：（分数：6.00）
(1).给出算法的基本设计思想；
__________________________________________________________________________________________
正确答案：(正确答案：设二叉树根结点的层次为1，在遍历二叉树的函数中增加层次参数，初始值为1。遍历二叉树，在访问结点时若是叶子结点，则求其带权路径长度，将所有叶子结点的带权路径长度相加，即得到二叉树的带权路径长度。 ()
(2).使用C或C++语言，给出二叉树结点的数据类型定义；
__________________________________________________________________________________________
正确答案：(正确答案：ypedef struct node {int weight； ／／结点的权值，设为整型 struct node*left，*right； ／／指向结点左、右子女的指针 }BiNode，*BiTree；)
(3).根据设计思想，采用C或C++语言描述算法，关键之处给出注释。【2014年全国试题41(13分)】
__________________________________________________________________________________________
正确答案：(正确答案：int WPL：0； ／／带权路径长度初值为0，是全局变量 void inorder(BiTree bt，level Iv) ／／bt是二叉树，1v是结点的层次，初值为1，本算法求二叉树bt的带权路径长度 (if(bt) finorder(bt一>left，iv+1)； ／／中序遍历左子树 if(bt一>left==null&&bt一>right==null) ／／判断该结点是否为叶子 WPL+=(iv一1)*bt一>weight； ／／累加结点带权路径长度 inorder(bt一>right，Iv+1)； ／／中序遍历右子树 } })
4.假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。【东北大学2000三、2(10分)】
__________________________________________________________________________________________
正确答案：(正确答案：以后序遍历方式遍历算术表达式的二叉树可以得到后缀表达式，后缀表达式求值已在前面讲过。这里给出另一种算法。重新定义二叉树结点结构为(1eft，data，val，fight)，其中left和fight是左右子女的指针，data是算法表达式中的字符，val是子表达式的值。采用后序遍历，先分别求出左子树和右子树表示的子表达式的值，最后计算出表达式的最后结果。算法如下： 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+p一>right一>val；break； case ‘一’：p一>Val=p一>left一>val—P一>right一>val；break； case ‘*’：p->val=p->left一>vai。P一>right一>val；break； case ‘／’：p一>Val=p一>1ef七一>val／p一>right一>val； }return(p->val)； } } 本算法中数值是以字符表示的，因此是一位数的算术运算。若是多位数(包括实数)，要做如下修改：在建立二叉树时进行拼数，一个数输入完毕再存入二叉树结点中；本算法中的p一>val=p一>data一0，要改为p一>Val=p一>dat
a；lv和rv的类型做相应改变。拼数算法的核心语句段如下： case 0<=x=0&&X<=‘9’)lI X==．) ／／拼数 if(x!=‘.’) ／／处理整数 { num=num*10+(ord(x)-ord(‘0’))；cin>>x；} ／／num初始值为0．0 else ／／处理小数部分 {scale=10．0；cin>>x； while(x>=’0‘&&x<=。9’) {num=num+(ord(x)-ord(。0’)／scale； scale=scale*10；cin>>x； } })
5.给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。【北京邮电大学2001五、3(10分)】
__________________________________________________________________________________________
正确答案：(正确答案：这是用二叉树表示符号算术表达式的逆问题，即将二叉树表示的表达式还原成原表达式。二叉树的中序遍历序列与原算术表达式基本相同，差别仅在于二叉树表示中消除了括号。将中序序列加上括号就恢复原貌。当根结点运算符优先级高于左子树(或右子树)根结点运算符时，就需要加括号。核心语句段如下： if(bt) (if(bt一>ichild!=null) fbracket：Precede(bt一>data，bt一>ichild一>data) ／／双亲与左子女运算符优先级 if(bracket==1)printf(()； InorderExp(bt一>ichild)； ／／输出左子女表示的算术表达式 if(bracket==1)printf(‘)’)； ／／加上右括号 } printf(bt一>data)； ／／输出根结点 if(bt一>rchil
d!=null) ／／输出右子树表示的算术表达式 {bracket=Precede(bt->data，bt一>rchild->data) if(bracket==1)printf(“C)； ／／右子女级别低，加括号 InorderExp(bt->rchi id)； if(bracket==1)printf(“)”)； } })
6.设计一算法分别求出二元树的叶结点，度数为l的结点，度数为2的结点的个数。【哈尔滨工业大学2002八(8分)】
__________________________________________________________________________________________