发布时间 : 星期六 文章计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编13更新完毕开始阅读
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编
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分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：解析：
设T是一棵二叉树，除叶子结点外，其他结点的度数皆为2，若T中有6个叶结点，试问：（分数：6.00） (1).T树的最大可能深度Kmax=?最小可能深度Kmin=?（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：(1)T树的最大深度：Kmax=6(除根外，每层均是两个结点)。T树的最小深度Kmin=4(具有6个叶子的完全二叉树是其中的一种形态)。) 解析：
(2).T树中共有多少非叶结点?（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：非叶子结点数是5(n2=n0—1)。) 解析：
(3).若叶结点的权值分别为1，2，3，4，5，6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wp1。【北京邮电大学1992一、3(15／3分)】（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：哈夫曼树见右图，其带权路径长度wp1=51。从本题到97题都是哈夫曼树的
) 试题。学生在构造哈夫曼树时常犯的错误是，在选出当前两个最小权值的结点构造二叉树后，没有把刚构造出来的二叉树的根结点加入待构造的结点中，造成最终的“哈夫曼树”是向一个方向倾斜的。值得指出的是，多数教材对哈夫曼编码规则是：哈夫曼树的左分支为0，右分支为1，个别教材规定左分支为1，右分支为0。限于篇幅，不再给出答案。) 解析：
2.已知4个字符A，E C，D的哈夫曼编码分别是1，01，000,001。下列01串是由以上4个字母构成的一段文本的哈夫曼编码：1001000011011010011010011请将上述01串还原为编码前的文本。以字符在文本中出现的次数为权值，求出这棵树的带权路径长度。【电子科技大学2013三、1(5分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：WPL=(1+3)*3+4*2+5*1=25。) 解析：
3.什么是前缀编码?举例说明如何利用二叉树来设计二进制的前缀编码。【中山大学1999三、1(3分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：前缀码是一编码不是任何其他编码前缀的编码。例如，0和01就不是前缀码，因为编码0是编码01的前缀。顺便说明，仅从编码来看，0和01是前缀码，但因历史的原因，它不被称为
A出现5次，B出现4次，C出现1次，D出现3次带权路径长度
前缀码，而是把一编码不是另一编码前缀的编码称为前缀码。利用二叉树可以构造前缀码，例如，以A，B，C，D为叶子可构成二叉树，将左分支解释为0，右分支解释成1，从根结点到叶子结点的0、1串就是叶子的前缀码。用哈夫曼树可构造出最优二叉树，使编码长度最短，称为哈夫曼编码。) 解析：
二、 设计题(总题数：25，分数：54.00)
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为：，其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结
点的指针，请设计求T的WPL的算法，要求：（分数：6.00） (1).给出算法的基本设计思想；（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：设二叉树根结点的层次为1，在遍历二叉树的函数中增加层次参数，初始值为1。遍历二叉树，在访问结点时若是叶子结点，则求其带权路径长度，将所有叶子结点的带权路径长度相加，即得到二叉树的带权路径长度。 () 解析：
(2).使用C或C++语言，给出二叉树结点的数据类型定义；（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：ypedef struct node {int weight； ／／结点的权值，设为整型 struct node*left，*right； ／／指向结点左、右子女的指针 }BiNode，*BiTree；) 解析：
(3).根据设计思想，采用C或C++语言描述算法，关键之处给出注释。【2014年全国试题41(13分)】（分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：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分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：以后序遍历方式遍历算术表达式的二叉树可以得到后缀表达式，后缀表达式求值已在前面讲过。这里给出另一种算法。重新定义二叉树结点结构为(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一>data；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分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：这是用二叉树表示符号算术表达式的逆问题，即将二叉树表示的表达式还原成原表达式。二叉树的中序遍历序列与原算术表达式基本相同，差别仅在于二叉树表示中消除了括号。将中序序列加上括号就恢复原貌。当根结点运算符优先级高于左子树(或右子树)根结点运算符时，就需要加括号。核心语句段如下： 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一>rchild!=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分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：结点计数可以在遍历中解决。根据“访问根结点”、“递归调用左子树”、“递归调用右子树”三者位置的不同，而有前序、后序和中序遍历。叶子结点是左右子女均无的结点，度为1的结点是只有一个子女的结点，度为2的结点是左右子女均有的结点。) 解析：
7.已知深度为h的二叉树，以一维数组BT[0．．2 -2]作为其存储结构，试编写一算法，求该二叉树中叶子结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相应的算法。【中南大学2003八(10分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：按完全二叉树形式顺序存储二叉树时，无元素的位置要当作“虚结点”。根据本题“二叉树中元素结点为非负整数”，可以设虚结点为负数。设结点序号为i(根结点编号为0)，则当ih-1)／2(最后一个分支结点)时，若其2f+1和2i+2位置为虚结点，则i为叶子结点；当i≥(2 -1)／2时，若i位置不是虚结点，则必为叶子结点。核心语句段如下： for(i=0；i k一1 if(i0)num++； ／／存储在数组后一半的元素是叶子结点) 解析：
8.假定用两个一维数组L[N]和R[N]作为有N个结点1，2，…，N的二元树的存储结构。L[i]和R[i]分别指示结点i的左儿子和右儿子；L[i]=O(R[i]=0)表示i的左(右)儿子为空。试写一个算法，由L和R建立一个一维数组T[b]，使T[i]存放结点i的父亲；然后再写一个判别结点U是否为结点V的后代的算法。【哈尔滨工业大学1999七(14分)】【华南师范大学2000六(17分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：由指示结点i左儿子和右儿子的两个一维数组L[i]和R[i]，建立指示结点i的双亲的一维数组T[i]，根据T数组，判断结点U是否是结点V后代的算法，转为判断结点V是否是结点U的祖先的问题。核心语句段如下： for(i=i ； i<=N； i++)T[i]=0； ／／T数组初始化 for(i=1；i<=N；i++) if(L[i]!=0)T[L[i\\]\\]=i ； ／／结点i的左子女是L，则结点L的双亲是结点i for(i=1，i<=N；i++) if(R Ci]!=0)T[R[i\\]\\]=i ； ／／i的右子女是r，则r的双亲是i int parent=U； ／／判断U是否是v的后代 while(parent!=V&&parent!=0)parent=T[parent]； if(parent==V){cout<<“结点U是结点v的后代“<<<“结点u不是结点V的后代”< h h 解析： 9.要求二叉树按二叉链表形式存储。(1)写一个建立二叉树的算法。(2)写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至Ⅳ的结点一一对应。此题以此定义为准。【西北大学2000六(12分)】【哈尔滨工业大学2000十一(14分)】【南开大学1997四 (16分)】【北京邮电大学1994九(20分)】 （分数：2.00） __________________________________________________________________________________________ 正确答案：(正确答案：二叉树是递归定义的，以递归方式建立最简单。核心语句段如下： cin>>x； ／／本题假定结点数据域为整型 if(x==0)bt=null； ／／空指针 else if(x>0) {bt=new(BiNode)； ／／申请空间 bt->data=x； bt->ichild=creat()；bt->rchiId=creat()； } else error(“输入错误”)； 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； ／／前边已有结点为空，本结点不空 else tag=l； ／／首次出现结点为空 if(p一>rchild&&!tag)QueueIn(Q，P一>rchild)； ／／右子女入队 else if(p->rchiid)return 0；else tag=1 ； }／／while) 解析： 10.有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。【南京理工大学1998七、1(6分)】【同济大学2005三、2(7分)】 （分数：2.00） __________________________________________________________________________________________ 正确答案：(正确答案：BiTree Creat(EiemType A[]，int i)／／初始调用时，i=i {BiTree tree； if(i<=n){tree=new(BiNode)；tree一>data=A[i]； if(2*i>n)tree->ichild=null ； ease tree->Ichild=Creat(A，2*i)； if(2*i+1>n)tree->rchild=null ； e18e tree->rchild=Creat(A，2*i+1)； } return(tree)； }) 解析： 11.设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中。(注：按层从上到下，由左到右)。【中科院研究生院2005四(15分)】 （分数：2.00） __________________________________________________________________________________________ 正确答案：(正确答案：将以二叉链表存储的二叉树转为顺序存储结构，要按完全二叉树形式顺序存储，无元素的位置要当作“虚结点”。一维数组A空间要足够大，开始将一维数组元素都初始化为虚结点。然后将二叉树的结点存入A的适当位置上。核心语句段如下： if(bt) fA[i]=bt一>data； ／／初始调用时，i=1 if(bt一>ichild)Creat(A，2*i，bt->Ichiid)； if(bt->rchild)Creat(A，2*i+1，bt->rchild)； }) 解析： 12.已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1：2 一1】中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child，data，rchild)，根结点所在链结点的指针由T给出。【北京师范大学2005六、3(15分)】【北京航空航天大学1999七(15分)】 （分数：2.00） __________________________________________________________________________________________ 正确答案：(正确答案：设栈S，元素结构是(int hum，BiTree bt)，初始调用num=1；设n=2 －1。 top=1；S[1]={1，bt}； while(i<=n&&top>0) {j=s[top].num；t=S[top一一].bt； if(BT[j]!=‘#’11#是虚结点 {t=new(BiNode)；t->data=BT[j]； if(BT[j*2+1]!=‘#’) S[++top]={j*2+1，bt一>rchild)； i=2*j； } }) 解析： 13.二叉树的动态二叉链表结构中的每个结点有三个字段：dam，lchild，rchild。其中指针lchild和rchild的类型为bike。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。所不同的是，lchild和rdhild为integer型，分别用于存储左右孩子的下 n h