1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 9 及答案与解析一、填空题1 二叉树按某种顺序线索化后，任一结点均有指向前驱和后继的线索，这种说法是正确的么?_【南京理工大学 2005 二、9(1 分)】2 线索二元树的左线索指向其_，右线索指向其_。【哈尔滨工业大学 2000 二、3 (2 分) 】3 将一棵树转换成二叉树后，根结点没有_子树。【电子科技大学 2005二、2(1 分) 】4 哈夫曼树是_。【北京理工大学 200l 七、 4(2)】【长沙铁道学院 1998二、3(2 分) 】5 若以4 ，5 ，6，7，8 作为叶子结点的权值构造哈夫曼树，则其带权路径长度是_。【西 安
2、电子科技大学 2001 软件一、3(2 分)】【厦门大学 2002 六、2(4 分)】【中南大学 2005 二、8(2 分) 】6 有数据 WG=7，19，2 ，6，32，3，21，10)，则所建 Huffman 树的树高是(1) ，带权路径长度 wPL 为(2) 。【南京理工大学 1999 三、6(4 分)】7 有一份电文中共使用 6 个字符：a，b，C，d，e，f 它们的出现频率依次为2，3，4，7，8，9，试构造一棵哈夫曼树，则其加权路径长度 WPL 为(1)，字符 C的编码是(2)。 【中国矿业大学 2000 一、7(3 分) 】8 设字符 a， b，c ，d,e，f 的使用频度分别为
3、 3，4，9，12，15，20，则 b，d 的哈夫曼编码分别为_，_。【大连理工大学 2005 一、5(2 分)】9 设 no 为哈夫曼树的叶子结点数目，则该哈夫曼树共有_个结点。 【西安电子科技大学 1999 软件一、2(2 分)】10 将二叉树 6f 中每一个结点的左右子树互换的 C 语言算法如下，其中ADDQ(Q，bt)，DELQ(Q)，EMPTY(Q)分别为进队、出队和判别队列是否为空的函数，请填写算法中空白之处，完成其功能。【北京科技大学 2000 二(10 分)】typedef struct nodeint data；struct node*ichild，*rchild；)btno
4、de；void EXCHANGE(btnode*bt)btnode*p，*q；if(bt)ADDQ(Q11 下面是求二又树高度的类 Pascal(注：编者略)及类 C 写的递归算法，试补充完整。【说明】二叉树的两指针域为 lchild 与 rchild，算法中 P 为二叉树的根，lh 和砌分别为以 P 为根的二叉树的左子树和右子树的高，hl 为以 P 为根的二叉树的高，hi 最后返回。height(p)if(1)if(p 一Ichild=null)lh=(2) ；else lh=(3) ；if(p 一rchiid=null)rh=(4) ；else rh=(5) ；if(1hrh)hi=(6)
5、 ;else hi=(7) ;else hi=(8)；return hi；【南京理工大学 1997 三、8(1 5 分)】12 二叉树中序遍历的非递归算法。Status Inorder(BiTree T)InitStatck(S); push(S，T);while( (1)while(gettop(S，P) tree stack500，int tp=0 ；(1)while(tp=0)(2)if(3) )r=p-ichild；p 一ichild=p-rchild；p 一rchild=r；stack(4) =p 一ichild；stack+tp=p 一rchiid ；【中科院自动化研究所 1994
6、 二、2(15 分)】14 设一棵二叉树的结点定义为 struct BinTreeNodeElemType data；BinTreeNode*leftchild ，*rightchild ；)现采用输入广义表表示建立二叉树。具体规定如下：(1)树的根结点作为由子树构成的表的表名放在表的最前面。(2)每个结点的左子树和右子树用逗号隔开。若仅有右子树没有左子树，逗号不能省略。(3)在整个广义表表示输入的结尾加上一个特殊的符号(例如“#”) 表示输入结束。例如，对于如右图所示的二叉树，其广义表表示为 A(B(G)，E(G)，C(F) 。此算法的基本思路是：依次从保存广义表的字符串 ls 中输入每个字
7、符。若遇到的是字母(假设以字母作为结点的值)，则表示是结点的值，应为它建立一个新的结点，并把该结点作为左子女(当 k=1)或右子女 (当 k=2)链接到其双亲结点上。若遇到的是左括号“(”，则表明子表的开始，将 k 置为 1；若遇到的是右括号“)” ，则表明子表结束。若遇到的是逗号“ ，” ，则表示以左子女为根的子树处理完毕，应接着处理以右子女为根的子树，将 k 置为 2。在算法中使用了一个栈 s，在进入子表之前，将根结点指针进栈，以便括号内的子女链接之用。在子表处理结束时退栈。相关的栈操作如下： MakeEmpty(s) 置空栈 Push(s，p) 元素 p 进栈 Pop(s) 退栈 Top
8、(s) 存取栈顶元素的函数下面给出了建立二叉树的算法，其中有 5 个语句缺失，请阅读此算法并把缺失的语句补上。(每空 3 分) Void creatBinTree(BinTreeNode * istream ins(1s)； 把串 1s 定义为输入字符串流对象 ins； char ch; insch； 从 ins 顺序读入一个字符 while(ch!=#) 逐个字符处理，直到遇到.#.为止 swich(ch) case (：(1); k=1; break; case )：pop(s); break； case , ：(2) ; break; default ：p=newBinTreeNode
9、(3) ； p 一leftchild=NULL；p 一rightchild=NULL； if(BT=NULL)(4); else if(k=1)top(s)一1eftchild=p； elsetop(s)一rightchild=p； (5) ； 【清华大学 2001 六(15 分)】15 下列是先序遍历二叉树的非递归子程序，请阅读子程序(C 语言与 Pascal 语言过程功能完全相同，任选其一)，填充空格，使其成为完整的算法。【同济大学 2001 三(10 分)】16 由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用
10、二叉链表表示的二叉树并打印出后序遍历序列，请写出程序中所缺的语句。#define MAX 100typedef struct Nodechar info；struct Node*llink，*rlink；)TNODE ；char predMAX，inodMAX;main(int argc，int*argv)TNODE*rootjif(argcinfo=(1) ;for(2) ； rposllink=restore(ppos+1，(4) ，k)；ptr-rlink=restore(5) +k，rpos+l，n 一 1 一 k);return ptr；postorder(TNODE*ptr)if(
11、ptr=NULL)return；postorder(ptr-iiink)；postorder(ptr 一rlink) ；printf(“c”，ptr 一info);【中科院计算所 2000 三(10 分)】17 说明下列程序功能，用图示给出子程序 crt_pre 的结果，并给出输出结果。#include“malloc.h”#include“stdioh”typedef struct BinNodechardata; struct BinNode*ich，*rch；)BinNode ， *Bintree；struct chtp(int len；char ch100；)S；struct queue
12、struct BinNode*elem100；int front，rear ；)q；struct BinNode*bt； int ii=0;void crt_pre(Bintree*t)char c; c=schii； ii=ii+1；if(c=) *t=0；else*t=(BinNode*)malloc(sizeof(BinNode);(*t)一data=c ；crt_pre( crt_pre(if(p)q elemqrear+=p; qelemqrear+：0；while(qfront!=qrear)t=qelemcqfront+；if(t)w+；if(t 一ich)qelemqrear+
13、=t 一ich;if(t 一rch)qelemq rear+ ：=t 一rch；else(if(qfront!=qrear)qelemqrear+=0;if(wmax)max=w;w=0：return max；main()char c=“abdeh.cfi.g!”);int i=0，num；for(i=0，s.1en=0 ；ci!=!; i+，S1en+)s chi=ci；crt_pre(num=unknown(bt)；printf(“n w=dn” ，num);【北京交通大学 2006 六、1(8 分)】18 以下程序是求二叉树深度的递归算法，请填空完善之。int depth(bitree
14、bt) *bt 为根结点的指针 9(int hl，hr ；if(bt=NULL) return (1) ；hl=height(bt 一ichild) ；hr=height(bt 一rchiid);if(2)(3);return(hr+1)；【西南交通大学 2000 一、11】19 下面是中序线索树的遍历算法，树有头结点且由指针 thr 指向。树的结点有五个域，分别为：数据域 data，左、右孩子域 lchild，rchild，左、右标志域ltag，rtag。规定标志域为 1 是线索，0 是指向孩子的指针。请在空格处添上适当内容，每个空格只填一个语句。inorderthread(thr)(p=t
15、hr 一Ichild ；while(1)while(2)p=(3)；printf(p 一data)；while(4)p=p 一rchild；printf(p 一data)；)p=(5)；【中国海洋大学 2007 五(10 分)】20 如下的算法分别是后序线索二叉树求给定结点 node 的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为(1flag，left，data，right， rflag)，其中：1flag=0，left 指向其左孩子，lflag=1，left指向其前驱；rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。p
16、rior(node， x)if(node!=null)if(1) )*x=node 一right；else*x=node 一left ;next(bt，node，x) *bt 是二叉树的树根*(2) ；if(node!=bt(4)；while(*x=node)；*x=t；【南京航空航天大学 1996 十(8 分)】21 已知一棵二叉树是以二叉链表的形式存储的，其结点结构说明如下：struct nodeint data; 结点的数据场struct node*left； 给出结点的左儿子的地址struct node*right； 给出结点的右儿子的地址)请在(1)、(2)二题的_ 处进行填空，完成
17、题目要求的功能。注意，每空只能填一个语句，多填为 0 分。(1)求出以 T 为根的二叉树或子树的结点个数。int Size(struct node*T)if()return 0 ； else 一；(2)求出以 T 为根的二叉树或子树的高度。注：高度定义为树的总的层次数。int height(struct node*T)if(T=NULL)；else ；)【上海交通大学 2004 三(10 分)】22 一棵树以孩子兄弟表示法存储，递归算法 numberofleaf 计算并返回根为，的树中叶子结点的个数(NULL 代表空指针) 。typedef struct nodestruct node*fir
18、stchild，*nextbrother；);D；int numberofleaf(JD*r)int hum；if(r=NULL)*num=0；else if(r-firstchild=NULL) num=(1)+numberofleaf(r 一nextbrother)；else (2) ；return(num)；【大连理工大学 2003 三、1(5 分)】23 以下是用类 C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶子结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的 Lchild域作为前链域，指向结点的直接前驱，结点的 Rchild 域作为后链域，指向结点的直接
19、后继。算法中，使用一个顺序栈 stack，栈顶指针为 top，P、t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，以完整算法。void leafchain(BiTree stacktop=bt；while(top)(t=stacktop;top 一一；if(!t 一Lchild!t 一Rchild)(1) ； (2); (3);elseif(4) )top+；stacktop=(5)； if(6) )top+；stacktop=(7)； (8) ； (9) ； 【同济大学 2003 三(18 分)】24 阅读下列算法，说明程序功能，并用图示输出执行后的结果。#includ
20、e#include#define n 7typedef struct Nodechar data；struct Node*Lc，*Rc；)Node，*BiNode；void unknowm(BiNode t，int i，char*a)t=(Node*)malloc(sizeof(Node)；t 一data=ai ；if(2*iLc，2*i ，a) ；else t 一Lc=NULL ；if(2*i+1Rc ， 2*i+1， a)；else t 一Rc=NULL；)void main()char a7; a1a；a2=。b；a3=c; a4=d;a5=e；a6=f；BiNode P；int j=1
21、 ；unknown(p，J，a);【北京交通大学 2005 六、2(8 分)】二、综合题25 证明任一结点个数为 n 的二叉树的高度至少为 O(logn)。 【浙江大学 2000 四(5分)】26 有 n 个结点的二叉树的最大高度、最小高度分别是多少?【清华大学 2008 二、1】27 有 n 个结点并且其高度为 n 的二叉树的数目是多少?【西安电子科技大学 2000计算机应用一、3(5 分) 】28 若一棵二叉树中有 24 个叶结点，有 28 个仅有一个孩子的结点，则该二叉树中总共有多少个结点? 【厦门大学 2006 二、1(203 分)】29 任意一个有 n 个结点的二叉树，已知它有 m
22、个叶子结点，试证明非叶子结点有(m 一 1)个度为 2，其余度为 1。【西安电子科技大学 2001 计算机应用二、3(5 分)】30 已知 A1N 是一棵顺序存储的完全二叉树，如何求出 Ai和 Aj的最近的共同祖先?【 中国人民大学 2001 二、5(4 分) 】计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 9 答案与解析一、填空题1 【正确答案】 说法错误。只有空指针处才能加线索，左指针指向前驱(遍历的第一个结点无前驱)，右指针指向后继(遍历的最后一个结点无后继)。2 【正确答案】 (1)前驱 (2) 后继3 【正确答案】 右4 【正确答案】 带权路径长度最小的二叉树，又称最优二
23、叉树5 【正确答案】 696 【正确答案】 (1)6 (2)261(计算式：(2+3)*5+(6+7+10)*4+(19+21+32)*2=261)7 【正确答案】 (1)80 (2)001(不唯一)8 【正确答案】 1001，00。按任何结点的左子女小于右子女构造哈夫曼树。9 【正确答案】 2n 0 一 110 【正确答案】 (1)ADDQ(Q,P 一lchild)(2)ADDQ(Q，P 一rchild) (3)p-rchild(4)p-lchild (5)P 一lchild11 【正确答案】 (1)P (2)0 (3)height(p 一lchild) (4)0 (5)height(p 一
24、rchild) (6)m+1 (7)r11+1 (8)012 【正确答案】 (1)lstackempty(s) (2)p-lchild (3)p-data (4)p-rchild13 【正确答案】 (1)stacktp=t (2)p=stacktp 一 (3)P (4)+tp14 【正确答案】 (I)Push(s，p) (2)k=2 (3)p-data=eh (4)BT=p(5)insch15 【正确答案】 (1)top+ (2)stacktop=p 一rchild (3)top+ (4)stacktop=p 一lchild16 【正确答案】 (1)*ppos根结点 (2)rpos=ipos
25、(3)rpos-ipos (4)ipos (5)ppos+117 【正确答案】 子程序 cn_pre 建立了一棵二叉树，算法求二叉树的宽度，输出4。18 【正确答案】 (1)0 (2)hlhr (3)retum(hl+1)19 【正确答案】 (1)p!-thr (2)p-ltag=0 (3)p=p 一lchild (4)p-rchild!=thr height(T 一right)+1)22 【正确答案】 (1)1 (2)num=numberofleaf(r-firstchild)+numberofleaf(rnextbrother)23 【正确答案】 (1)p-Rchild=t (2)t-Lc
26、hild=p (3)p=t (4)t-Rchild!=null (5)t-Rchild(6)t 一 Lchild!=null (7)t-Lchild (8)p-Rchild=head (9)head-Lchild=p24 【正确答案】 本算法是由二叉树的顺序存储结构生成二叉链表的程序，二叉树按完全二叉树存储，数组定义了 7 个元素，下标从 l 开始，a1(即字母 a)是二叉树的根结点。输出结果略。需要指出，程序中给了 6 个结点数据，数据从下标 1 开始存放。在判断有无左右子女时，不应包括 n=7(下标为 7)的情况。应改为(2 *in)和(2*+in)。二、综合题25 【正确答案】 最低高度
27、二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设 n 个结点的二叉树的最低高度是 h，则 n 应满足 2h-1n2h 一 1 关系式。解此不等式，并考虑 h 是整数，则有 h=logn+1，即任一结点个数为 n 的二叉树的高度至少为 O(logn)。26 【正确答案】 最大高度是 n，这是一棵单枝树；最小高度是logn+1。27 【正确答案】 2 n-1。本题等价于高度为 n 的满二叉树有多少叶子结点，从根结点到各叶子结点的单枝树是不同的二叉树。28 【正确答案】 75。有两个孩子的结点个数 n2=n01=23。29 【正确答案】 证明：设度为 1 和 2 的结
28、点数是 n1 和 n2，则二叉树结点数 n 为：n=m+n1+n2 (1)由于二叉树根结点没有分支所指，度为 1 和 2 的结点各有 1 个和 2 个分支，度为 0的结点没有分支，故二叉树的结点数 n 与分支数 B 有如下关系：n=B+1=n1+2*n2+1 (2)由(1)和(2)，得 n2=m-1。即 n 个结点的二叉树，若叶子结点数是 m，则非叶子结点中有(m 一 1)个度为 2，其余度为 1。30 【正确答案】 根据顺序存储的完全二又树的性质，编号为 i(本题中 i 从 1 开始)的非根结点的双亲的编号是i2，故 Ai和 Aj的最近公共祖先可如下求出：while(i2!=j2)if(ij) i=i2 ； else j=j2 ；退出 while 后，若 i2=0 ，则最近公共祖先为根结点，否则最近公共祖先是 i2。
