1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 11及答案解析(总分：60.00，做题时间：90 分钟)一、填空题(总题数：24，分数：48.00)1.二叉树按某种顺序线索化后，任一结点均有指向前驱和后继的线索，这种说法是正确的么?_【南京理工大学 2005 二、9(1 分)】（分数：2.00）_2.线索二元树的左线索指向其_，右线索指向其_。【哈尔滨工业大学 2000 二、3 (2分)】（分数：2.00）_3.将一棵树转换成二叉树后，根结点没有_子树。【电子科技大学 2005 二、2(1 分)】（分数：2.00）_4.哈夫曼树是_。【北京理工大学 200l 七、4(2)】【长沙铁道
2、学院 1998 二、3(2 分)】（分数：2.00）_5.若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是_。【西 安电子科技大学 2001 软件一、3(2 分)】【厦门大学 2002 六、2(4 分)】【中南大学 2005 二、8(2 分)】（分数：2.00）_6.有数据 WG=7，19，2，6，32，3，21，10)，则所建 Huffman 树的树高是(1)，带权路径长度 wPL 为(2)。【南京理工大学 1999 三、6(4 分)】（分数：2.00）_7.有一份电文中共使用 6 个字符：a，b，C，d，e，f 它们的出现频率依次为 2，3，4，7，8，9，试构造一
3、棵哈夫曼树，则其加权路径长度 WPL 为(1)，字符 C 的编码是(2)。【中国矿业大学 2000 一、7(3 分)】（分数：2.00）_8.设字符 a，b，c，d,e，f 的使用频度分别为 3，4，9，12，15，20，则 b，d 的哈夫曼编码分别为_，_。【大连理工大学 2005 一、5(2 分)】（分数：2.00）_9.设 no 为哈夫曼树的叶子结点数目，则该哈夫曼树共有_个结点。 【西安电子科技大学 1999软件一、2(2 分)】（分数：2.00）_10.将二叉树 6f 中每一个结点的左右子树互换的 C 语言算法如下，其中 ADDQ(Q，bt)，DELQ(Q)，EMPTY(Q)分别为进
4、队、出队和判别队列是否为空的函数，请填写算法中空白之处，完成其功能。【北京科技大学2000 二(10 分)】 typedef struct node int data；struct node*ichild，*rchild；)btnode； void EXCHANGE(btnode*bt) btnode*p，*q； if(bt) ADDQ(Q（分数：2.00）_11.下面是求二又树高度的类 Pascal(注：编者略)及类 C 写的递归算法，试补充完整。【说明】二叉树的两指针域为 lchild 与 rchild，算法中 P 为二叉树的根，lh 和砌分别为以 P 为根的二叉树的左子树和右子树的高，h
5、l 为以 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) ;else hi=(7) ; else hi=(8)； return hi； 【南京理工大学 1997 三、8(1 5 分)】（分数：2.00）_12.二叉树中序遍历的非递归算法。 Status Inorder(BiTree T) InitStatck(S); push(S，T); while( (1) while(getto
6、p(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 二、2(15 分)】（分数：2.00）_14.设一棵二叉树的结点定义为 struct BinTreeNode ElemType data；BinTreeNode*leftchild，*rightchild；)现采用输入广义表表示建立二叉树。具体规定如下： (1)树的根结点作为由子树构
7、成的表的表名放在表的最前面。 (2)每个结点的左子树和右子树用逗号隔开。若仅有右子树没有左子树，逗号不能省略。 (3)在整个广义表表示输入的结尾加上一个特殊的符号(例如“#”)表示输入结束。例如，对于如右图所示的二叉树，其广义表表示为 A(B(G)，E(G)，C(F)。此算法的基本思路是：依次从保存广义表的字符串 ls 中输入每个字符。若遇到的是字母(假设以字母作为结点的值)，则表示是结点的值，应为它建立一个新的结点，并把该结点作为左子女(当 k=1)或右子女(当 k=2)链接到其双亲结点上。若遇到的是左括号“(”，则表明子表的开始，将 k 置为 1；若遇到的是右括号“)”，则表明子表结束。若
8、遇到的是逗号“，”，则表示以左子女为根的子树处理完毕，应接着处理以右子女为根的子树，将 k 置为 2。在算法中使用了一个栈 s，在进入子表之前，将根结点指针进栈，以便括号内的子女链接之用。在子表处理结束时退栈。相关的栈操作如下： （分数：2.00）_15.下列是先序遍历二叉树的非递归子程序，请阅读子程序(C 语言与 Pascal 语言过程功能完全相同，任选其一)，填充空格，使其成为完整的算法。 （分数：2.00）_16.由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程
9、序中所缺的语句。 #define MAX 100 typedef struct Node char info；struct Node*llink，*rlink；)TNODE； char predMAX，inodMAX; main(int argc，int*argv) TNODE*rootj if(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(ptr=NULL)return
10、； postorder(ptr-iiink)； postorder(ptr 一rlink)； printf(“c”，ptr 一info); 【中科院计算所 2000 三(10 分)】（分数：2.00）_17.说明下列程序功能，用图示给出子程序 crt_pre 的结果，并给出输出结果。 #include“malloc.h” #include“stdioh” typedef struct BinNode chardata; struct BinNode*ich，*rch；)BinNode，*Bintree； struct chtp(int len；char ch100；)S； struct que
11、ue 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) qelemqrear+=p; qelemqrear+：0； while(qfront!=qrear) t=qelemcqfront+； if(t)w+； if(t 一ic
12、h)qelemqrear+=t 一ich; if(t 一rch)qelemqrear+：=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+)schi=ci； crt_pre( num=unknown(bt)； printf(“n w=dn”，num); 【北京交通大学 2006 六、1(8 分)】（分数：2.00）_18.以下程序是求二叉树深度
13、的递归算法，请填空完善之。 int depth(bitree 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】（分数：2.00）_19.下面是中序线索树的遍历算法，树有头结点且由指针 thr 指向。树的结点有五个域，分别为：数据域data，左、右孩子域 lchild，rchild，左、右标志域 ltag，rtag。规定标志域为 1 是线索，0 是指向孩子的指针
14、。请在空格处添上适当内容，每个空格只填一个语句。inorderthread(thr) (p=thr 一Ichild； while(1) while(2) p=(3)； printf(p 一data)； while(4) p=p 一rchild；printf(p 一data)；) p=(5)； 【中国海洋大学 2007 五(10分)】（分数：2.00）_20.如下的算法分别是后序线索二叉树求给定结点 node 的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为(1flag，left，data，right，rflag)，其中：1flag=0，left 指向其左孩
15、子，lflag=1，left 指向其前驱；rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。 prior(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 分)】（分数：2.00）_21.已知一棵二叉树是以二叉链表的形式存储的，其结点结构说明如下： struct nodeint data; 结点的数据
16、场 struct node*left； 给出结点的左儿子的地址 struct node*right； 给出结点的右儿子的地址) 请在(1)、(2)二题的_处进行填空，完成题目要求的功能。注意，每空只能填 一个语句，多填为 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 分)】（分数：2.00）_
17、22.一棵树以孩子兄弟表示法存储，递归算法 numberofleaf 计算并返回根为，的树中叶子结点的个数(NULL 代表空指针)。 typedef struct nodestruct node*firstchild，*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 分)】（分数：2.00）_23
18、.以下是用类 C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶子结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的 Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈 stack，栈顶指针为 top，P、t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，以完整算法。 void leafchain(BiTree stacktop=bt； while(top) (t=stacktop;top 一一；if(!t 一Lchild!t 一Rchild)(1)； (2); (3); els
19、eif(4) )top+；stacktop=(5)； if(6) )top+；stacktop=(7)； (8) ； (9) ； 【同济大学 2003 三(18 分)】（分数：2.00）_24.阅读下列算法，说明程序功能，并用图示输出执行后的结果。 #include #include #define n 7 typedef 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
20、*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； unknown(p，J，a); 【北京交通大学 2005 六、2(8 分)】（分数：2.00）_二、综合题(总题数：6，分数：12.00)25.证明任一结点个数为 n 的二叉树的高度至少为 O(logn)。 【浙江大学 2000 四(5 分)】（分数：2.00）_26.有 n 个结点的二叉树的最大高度、最
21、小高度分别是多少?【清华大学 2008 二、1】（分数：2.00）_27.有 n 个结点并且其高度为 n 的二叉树的数目是多少?【西安电子科技大学 2000 计算机应用一、3(5 分)】（分数：2.00）_28.若一棵二叉树中有 24 个叶结点，有 28 个仅有一个孩子的结点，则该二叉树中总共有多少个结点?【厦门大学 2006 二、1(203 分)】（分数：2.00）_29.任意一个有 n 个结点的二叉树，已知它有 m 个叶子结点，试证明非叶子结点有(m 一 1)个度为 2，其余度为 1。【西安电子科技大学 2001 计算机应用二、3(5 分)】（分数：2.00）_30.已知 A1N是一棵顺序
22、存储的完全二叉树，如何求出 Ai和 Aj的最近的共同祖先?【中国人民大学 2001 二、5(4 分)】（分数：2.00）_计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 11答案解析(总分：60.00，做题时间：90 分钟)一、填空题(总题数：24，分数：48.00)1.二叉树按某种顺序线索化后，任一结点均有指向前驱和后继的线索，这种说法是正确的么?_【南京理工大学 2005 二、9(1 分)】（分数：2.00）_正确答案：(正确答案：说法错误。只有空指针处才能加线索，左指针指向前驱(遍历的第一个结点无前驱)，右指针指向后继(遍历的最后一个结点无后继)。)解析：2.线索二元树的左线索
23、指向其_，右线索指向其_。【哈尔滨工业大学 2000 二、3 (2分)】（分数：2.00）_正确答案：(正确答案：(1)前驱 (2)后继)解析：3.将一棵树转换成二叉树后，根结点没有_子树。【电子科技大学 2005 二、2(1 分)】（分数：2.00）_正确答案：(正确答案：右)解析：4.哈夫曼树是_。【北京理工大学 200l 七、4(2)】【长沙铁道学院 1998 二、3(2 分)】（分数：2.00）_正确答案：(正确答案：带权路径长度最小的二叉树，又称最优二叉树)解析：5.若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是_。【西 安电子科技大学 2001 软件一、3
24、(2 分)】【厦门大学 2002 六、2(4 分)】【中南大学 2005 二、8(2 分)】（分数：2.00）_正确答案：(正确答案：69)解析：6.有数据 WG=7，19，2，6，32，3，21，10)，则所建 Huffman 树的树高是(1)，带权路径长度 wPL 为(2)。【南京理工大学 1999 三、6(4 分)】（分数：2.00）_正确答案：(正确答案：(1)6 (2)261(计算式：(2+3)*5+(6+7+10)*4+(19+21+32)*2=261)解析：7.有一份电文中共使用 6 个字符：a，b，C，d，e，f 它们的出现频率依次为 2，3，4，7，8，9，试构造一棵哈夫曼树
25、，则其加权路径长度 WPL 为(1)，字符 C 的编码是(2)。【中国矿业大学 2000 一、7(3 分)】（分数：2.00）_正确答案：(正确答案：(1)80 (2)001(不唯一)解析：8.设字符 a，b，c，d,e，f 的使用频度分别为 3，4，9，12，15，20，则 b，d 的哈夫曼编码分别为_，_。【大连理工大学 2005 一、5(2 分)】（分数：2.00）_正确答案：(正确答案：1001，00。按任何结点的左子女小于右子女构造哈夫曼树。)解析：9.设 no 为哈夫曼树的叶子结点数目，则该哈夫曼树共有_个结点。 【西安电子科技大学 1999软件一、2(2 分)】（分数：2.00）
26、_正确答案：(正确答案：2n 0 一 1)解析：10.将二叉树 6f 中每一个结点的左右子树互换的 C 语言算法如下，其中 ADDQ(Q，bt)，DELQ(Q)，EMPTY(Q)分别为进队、出队和判别队列是否为空的函数，请填写算法中空白之处，完成其功能。【北京科技大学2000 二(10 分)】 typedef struct node int data；struct node*ichild，*rchild；)btnode； void EXCHANGE(btnode*bt) btnode*p，*q； if(bt) ADDQ(Q（分数：2.00）_正确答案：(正确答案：(1)ADDQ(Q,P 一lc
27、hild)(2)ADDQ(Q，P 一rchild) (3)p-rchild(4)p-lchild (5)P 一lchild)解析：11.下面是求二又树高度的类 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=(
28、5) ； if(1hrh)hi=(6) ;else hi=(7) ; else hi=(8)； return hi； 【南京理工大学 1997 三、8(1 5 分)】（分数：2.00）_正确答案：(正确答案：(1)P (2)0 (3)height(p 一lchild) (4)0 (5)height(p 一rchild) (6)m+1 (7)r11+1 (8)0)解析：12.二叉树中序遍历的非递归算法。 Status Inorder(BiTree T) InitStatck(S); push(S，T); while( (1) while(gettop(S，P) tree stack500，int
29、 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 二、2(15 分)】（分数：2.00）_正确答案：(正确答案：(1)stacktp=t (2)p=stacktp 一 (3)P (4)+tp)解析：14.设一棵二叉树的结点定义为 struct BinTreeNode ElemType data；BinTreeNode*leftchild，*rightchild；)现采用输入广义表
30、表示建立二叉树。具体规定如下： (1)树的根结点作为由子树构成的表的表名放在表的最前面。 (2)每个结点的左子树和右子树用逗号隔开。若仅有右子树没有左子树，逗号不能省略。 (3)在整个广义表表示输入的结尾加上一个特殊的符号(例如“#”)表示输入结束。例如，对于如右图所示的二叉树，其广义表表示为 A(B(G)，E(G)，C(F)。此算法的基本思路是：依次从保存广义表的字符串 ls 中输入每个字符。若遇到的是字母(假设以字母作为结点的值)，则表示是结点的值，应为它建立一个新的结点，并把该结点作为左子女(当 k=1)或右子女(当 k=2)链接到其双亲结点上。若遇到的是左括号“(”，则表明子表的开始，
31、将 k 置为 1；若遇到的是右括号“)”，则表明子表结束。若遇到的是逗号“，”，则表示以左子女为根的子树处理完毕，应接着处理以右子女为根的子树，将 k 置为 2。在算法中使用了一个栈 s，在进入子表之前，将根结点指针进栈，以便括号内的子女链接之用。在子表处理结束时退栈。相关的栈操作如下： （分数：2.00）_正确答案：(正确答案：(I)Push(s，p) (2)k=2 (3)p-data=eh (4)BT=p(5)insch)解析：15.下列是先序遍历二叉树的非递归子程序，请阅读子程序(C 语言与 Pascal 语言过程功能完全相同，任选其一)，填充空格，使其成为完整的算法。 （分数：2.00
32、）_正确答案：(正确答案：(1)top+ (2)stacktop=p 一rchild (3)top+ (4)stacktop=p 一lchild)解析：16.由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序中所缺的语句。 #define MAX 100 typedef struct Node char info；struct Node*llink，*rlink；)TNODE； char predMAX，inodMAX; main(int argc，int*argv)
33、 TNODE*rootj if(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(ptr=NULL)return； postorder(ptr-iiink)； postorder(ptr 一rlink)； printf(“c”，ptr 一info); 【中科院计算所 2000 三(10 分)】（分数：2.00）_正确答案：(正确答案：(1)*ppos根结点 (2)rpos=i
34、pos (3)rpos-ipos (4)ipos (5)ppos+1)解析：17.说明下列程序功能，用图示给出子程序 crt_pre 的结果，并给出输出结果。 #include“malloc.h” #include“stdioh” typedef struct BinNode chardata; struct BinNode*ich，*rch；)BinNode，*Bintree； struct chtp(int len；char ch100；)S； struct queue struct BinNode*elem100；int front，rear；)q； struct BinNode*bt；
35、 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) qelemqrear+=p; qelemqrear+：0； while(qfront!=qrear) t=qelemcqfront+； if(t)w+； if(t 一ich)qelemqrear+=t 一ich; if(t 一rch)qelemqrear+：=t 一rch； else(if(qfront!=qrear)qelemq
