计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编11

11

(总分：60.00，做题时间：90分钟)

一、 填空题(总题数：24，分数：48.00)

1.二叉树按某种顺序线索化后，任一结点均有指向前驱和后继的线索，这种说法是正确的么?__________【南京理工大学2005二、9(1分)】

__________________________________________________________________________________________ 正确答案：(正确答案：说法错误。只有空指针处才能加线索，左指针指向前驱(遍历的第一个结点无前驱)，右指针指向后继(遍历的最后一个结点无后继)。)

2.线索二元树的左线索指向其__________，右线索指向其__________。【哈尔滨工业大学2000二、3 (2分)】

__________________________________________________________________________________________ 正确答案：(正确答案：(1)前驱 (2)后继)

3.将一棵树转换成二叉树后，根结点没有__________子树。【电子科技大学2005二、2(1分)】 __________________________________________________________________________________________ 正确答案：(正确答案：右)

4.哈夫曼树是__________。【北京理工大学200l七、4(2)】【长沙铁道学院1998二、3(2分)】 __________________________________________________________________________________________ 正确答案：(正确答案：带权路径长度最小的二叉树，又称最优二叉树)

5.若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是__________。【西 安电子科技大学2001软件一、3(2分)】【厦门大学2002六、2(4分)】【中南大学2005二、8(2分)】 __________________________________________________________________________________________ 正确答案：(正确答案：69)

6.有数据WG={7，19，2，6，32，3，21，10)，则所建Huffman树的树高是(1)，带权路径长度wPL为(2)。【南京理工大学1999三、6(4分)】

__________________________________________________________________________________________ 正确答案：(正确答案：(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，试构造一棵哈夫曼树，则其加权路径长度WPL为(1)，字符C的编码是(2)。【中国矿业大学2000一、7(3分)】 __________________________________________________________________________________________ 正确答案：(正确答案：(1)80 (2)001(不唯一))

8.设字符a，b，c，d,e，f的使用频度分别为3，4，9，12，15，20，则b，d的哈夫曼编码分别为__________，__________。【大连理工大学2005一、5(2分)】

__________________________________________________________________________________________ 正确答案：(正确答案：1001，00。按任何结点的左子女小于右子女构造哈夫曼树。)

9.设no为哈夫曼树的叶子结点数目，则该哈夫曼树共有__________个结点。 【西安电子科技大学1999软件一、2(2分)】

__________________________________________________________________________________________ 正确答案：(正确答案：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

__________________________________________________________________________________________

正确答案：(正确答案：(1)ADDQ(Q,P一>lchild)(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=(5) ； if(1h>rh)hi=(6) ;else hi=(7) ; } else hi=(8)； return hi； }【南京理工大学1997三、8(1 5分)】

__________________________________________________________________________________________ 正确答案：(正确答案：(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)＆&P) push(s， (2) ) pop(s，p)； if(!stackempty(s)){ pop(S，p)；printf( (3))； push(s， (4))； }／／if }／／while return ok； }／／Inorder 说明： InitStack(s)：初始化一个栈S push(s，p)：将所指向的结点进s栈 pop(s，p)：s栈顶元素出栈 gettop(s，p)：取s栈顶元素 stackempty(s)：判栈s是否为空 【南京理工大学2006一(一)、2(每空1．5分)】

__________________________________________________________________________________________ 正确答案：(正确答案：(1)lstackempty(s) (2)p-lchild (3)p->data (4)p->rchild)

13.阅读下列程序说明和程序，填充程序中的__________。【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示(编者略)。本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为：(1)把根结点放入堆栈。(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。(3)重复(2)直到堆栈为空时为止。 typedef struct node *tree； struct node(int data；tree lchild，rchild；) exchange(t)tree t； (tree r，P; tree stack[500]，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分)】

__________________________________________________________________________________________ 正确答案：(正确答案：(1)stack[tp]=t (2)p=stack[tp一] (3)P (4)++tp)

14.设一棵二叉树的结点定义为 struct BinTreeNode{ ElemType data；BinTreeNode*leftchild，*rightchild；)现采用输入广义表表示建立二叉树。具体规定如下： (1)树的根结点作为由子树构成的表的表名放在表的最前面。 (2)每个结点的左子树和右子树用逗号隔开。若仅有右子树没有左子树，逗号不能省略。 (3)在整个广义表表示输入的结尾加上一个特殊的符号(例如“#”)表示输入结束。例如，对于如右图所示的二叉树，其广义表表示为A(B(G))，E(G)，C(F)。此算法的基本思路是：依次从保存广义表的字符串ls中输入每个字符。若遇到的是字母(假设以字母作为结点的值)，则表示是结点的值，应为它建立一个新的结点，并把该结点作为左子女(当k=1)或右子女(当k=2)链接到其双亲结点上。若遇到的是左括号“(”，则表明子表的开始，将k置为1；若遇到的是右括号“)”，则表明子表结束。若遇到的是逗号“，”，则表示以左子女为根的子树处理完毕，应接着处理以右子女为根的子树，将k置为2。在算法中使用了一个栈s，在进入子表之前，将根结点指针进栈，以便括号内的子女链接之用。在子表处理结束时退栈。相关的栈操作如下： MakeEmpty(s) 置空栈Push(s，p) 元素p进栈 Pop(s) 退栈 Top(s) 存取栈顶元

素的函数 下面给出了建立二叉树的算法，其中有5个语句缺失，请阅读此算法并把缺失的语句补上。(每空3分) Void creatBinTree(BinTreeNode *&BT， char 1s){ Stack s； MakeEmpty(s)； BT=NULL； ／／置空二叉树 BinTreeNode*p ； intk; istream ins(1s)； ／／把串1s定义为输入字符串流对象ins； char ch; ins>>ch； ／／从ins顺序读入一个字符 while(ch!=\"#\"){ ／／逐个字符处理，直到遇到.#.为止 swich(ch){ case \"(\"：(1); k=1; break; case \")\"：pop(s); break； case \：(2) ; break; default：p=newBinTreeNode (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分)】

__________________________________________________________________________________________ 正确答案：(正确答案：(I)Push(s，p) (2)k=2 (3)p->data=eh (4)BT=p(5)ins>>ch)

15.下列是先序遍历二叉树的非递归子程序，请阅读子程序(C语言与Pascal语言过程功能完全相同，任选其一)，填充空格，使其成为完整的算法。【同济大学2001三(10分)】

__________________________________________________________________________________________ 正确答案：(正确答案：(1)top++ (2)stack[top]=p一>rchild (3)top++ (4)stack[top]=p一>lchild) 16.由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序中所缺的语句。 #define MAX 100 typedef struct Node {char info；struct Node*llink，*rlink；)TNODE； char pred[MAX]，inod[MAX]; main(int argc，int**argv) {TNODE*rootj if(argc<=0)return NULL ; ptr->info=(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分)】 __________________________________________________________________________________________ 正确答案：(正确答案：(1)*ppos／／根结点 (2)rpos=ipos (3)rpos--ipos (4)ipos (5)ppos+1) 17.说明下列程序功能，用图示给出子程序crt_pre的结果，并给出输出结果。 #include“malloc.h” #include“stdio．h” typedef struct BinNode {chardata; struct BinNode*ich，*rch；)BinNode，*Bintree； struct chtp(int len；char ch[100]；)S； struct queue {struct BinNode*elem[100]；int front，rear；)q； struct BinNode*bt； int ii=0; void crt_pre(Bintree*t) {char c; c=s．ch[ii]； ii=ii+1； if(c==‘．’) *t=0； else{*t=(BinNode*)malloc(sizeof(BinNode)); (*t)一>data=c； crt_pre(&(*t)一>Ich); crt_pre(&(*t)一>rch)； }； } int unknown(BinNode*p) {BinNode*t ； int max=0，W=0；q．front=q．rear=0 ; if(p) {q．elem[q．rear++]=p; q．elem[q．rear++]：0； while(q．front!=q．rear) {t=q．elemcq．front++]； if(t){w++； if(t一>ich)q．elem[q．rear++]=t一>ich; if(t一>rch)q．elem[q．rear++]：=t一>rch； } else(if(q．front!=q．rear)q．elem[q．rear++]=0; if(w>max)max=w; w=0： } } } return max； } main() {char c[]={“abd..eh.cf．i.．g!”);int i=0，num； for(i=0，s.1en=0；c[i]!=‘!’; i++，S．1en++)s．ch[i]=c[i]； crt_pre(&bt); num=unknown(bt)； printf(“＼n w=％d＼n”，num); } 【北京交通大学2006六、1(8分)】

__________________________________________________________________________________________ 正确答案：(正确答案：子程序cn_pre建立了一棵二叉树，算法求二叉树的宽度，输出4。)

18.以下程序是求二叉树深度的递归算法，请填空完善之。 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】

__________________________________________________________________________________________ 正确答案：(正确答案：(1)0 (2)hl>hr (3)retum(hl+1))

19.下面是中序线索树的遍历算法，树有头结点且由指针thr指向。树的结点有五个域，分别为：数据域data，左、右孩子域lchild，rchild，左、右标志域ltag，rtag。规定标志域为1是线索，0是指向孩子的指针。请在空格处添上适当内容，每个空格只填一个语句。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分)】 __________________________________________________________________________________________ 正确答案：(正确答案：(1)p!--thr (2)p->ltag=0 (3)p=p一>lchild (4)p->rchild!=thr&&p一>rtag==1(5)p=p一>rchild)

20.如下的算法分别是后序线索二叉树求给定结点node的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为(1flag，left，data，right，rflag)，其中：1flag=0，left指向其左孩子，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＆&node!=null) if(node一>rflag)(3) ； else{do t=*x;(4)； while(*x==node)； *x=t； } }【南京航空航天大学1996十(8分)】

__________________________________________________________________________________________ 正确答案：(正确答案：(1)node->rflag==0 (2)*x=bt (3)*x=node->right (4)prior(t，x))

21.已知一棵二叉树是以二叉链表的形式存储的，其结点结构说明如下： struct node{int data; ／／结点的数据场 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分)】

__________________________________________________________________________________________ 正确答案：(正确答案：①T==null ②return(1+size(T一>left)+size(T一>right))③return(0)ireturn (height(T一>lefl)>height(T一>right)?height(T一>left)+1; height(T一>right)+1))

22.一棵树以孩子兄弟表示法存储，递归算法numberofleaf计算并返回根为，的树中叶子结点的个数(NULL代表空指针)。 typedef struct node{struct 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分)】

__________________________________________________________________________________________ 正确答案：(正确答案：(1)1 (2)num==numberofleaf(r->firstchild)+numberofleaf(r>nextbrother)) 23.以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶子结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，P、t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，以完整算法。 void leafchain(BiTree&bt) {p=(BiTree)malloc(sizeof(BiTNode))； if(!p){printf(“OVERFLOW＼n”；exit(1)；) head=p；top=1； if(bt) (top++; stack[top]=bt； while(top) (t=stack[top];top一一； if(!t一>Lchild＆＆!t一>Rchild){(1)； (2); (3);} else{if((4) ){top++；stack[top]=(5)； } if(6) ){top++；stack[top]=(7)； } } } (8) ； (9) ； } }【同济大学2003三(18分)】

__________________________________________________________________________________________ 正确答案：(正确答案：(1)p->Rchild=t (2)t->Lchild=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=p)

24.阅读下列算法，说明程序功能，并用图示输出执行后的结果。 #include #include #define n 7 typedef struct Node{char data；struct Node*Lc，*Rc；)Node，*BiNode； void unknowm(BiNode t，int i，char*a) {t=(Node*)malloc(sizeof(Node))； t一>data=a[i]； if(2*i<=n) unknown(t一>Lc，2*i，a)； else t一>Lc=NULL； if(2*i+1<=n) unknown(t一>Rc， 2*i+1， a)； else t一>Rc=NULL； ) void main() {char a[7]; a[1]．‘a’；a[2]=。b’；a[3]=\"c\"; a[4]=‘d’;a[5]=\"e\"；a[6]=‘f’； BiNode P；int j=1； unknown(p，J，a); } 【北京交通大学2005六、2(8分)】

__________________________________________________________________________________________ 正确答案：(正确答案：本算法是由二叉树的顺序存储结构生成二叉链表的程序，二叉树按完全二叉树存储，数组定义了7个元素，下标从l开始，a[1](即字母a)是二叉树的根结点。输出结果略。需要指出，程序中给了6个结点数据，数据从下标1开始存放。在判断有无左右子女时，不应包括n=7(下标为7)的情况。应改为(2 i＜n)和(2 +i＜n)。)

*

*

二、 综合题(总题数：6，分数：12.00)

25.证明任一结点个数为n的二叉树的高度至少为O(logn)。 【浙江大学2000四(5分)】

__________________________________________________________________________________________ 正确答案：(正确答案：最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设n个结点的二叉树的最低高度是h，则n应满足2 ≤n≤2 一1关系式。解此不等式，并考虑h是整数，则有h=[logn]+1，即任一结点个数为n的二叉树的高度至少为O(logn)。) 26.有n个结点的二叉树的最大高度、最小高度分别是多少?【清华大学2008二、1】

__________________________________________________________________________________________ 正确答案：(正确答案：最大高度是n，这是一棵单枝树；最小高度是[logn]+1。)

27.有n个结点并且其高度为n的二叉树的数目是多少?【西安电子科技大学2000计算机应用一、3(5分)】 __________________________________________________________________________________________

h-1

h

正确答案：(正确答案：2 。本题等价于高度为n的满二叉树有多少叶子结点，从根结点到各叶子结点的单枝树是不同的二叉树。)

28.若一棵二叉树中有24个叶结点，有28个仅有一个孩子的结点，则该二叉树中总共有多少个结点?【厦门大学2006二、1(20／3分)】

__________________________________________________________________________________________ 正确答案：(正确答案：75。有两个孩子的结点个数n2=n0—1=23。)

29.任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有(m一1)个度为2，其余度为1。【西安电子科技大学2001计算机应用二、3(5分)】

__________________________________________________________________________________________ 正确答案：(正确答案：证明：设度为1和2的结点数是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.已知A[1．．N]是一棵顺序存储的完全二叉树，如何求出A[i]和A[j]的最近的共同祖先?【中国人民大学2001二、5(4分)】

__________________________________________________________________________________________ 正确答案：(正确答案：根据顺序存储的完全二又树的性质，编号为i(本题中i从1开始)的非根结点的双亲的编号是[i／2]，故A[i]和A[j]的最近公共祖先可如下求出： while(i／2!=j／2) if(i>j) i=i／2 ； else j=j／2 ； 退出while后，若i／2=0，则最近公共祖先为根结点，否则最近公共祖先是i／2。)

n-1