耿国华数据结构习题答案完整版 .pdf

《耿国华数据结构习题答案完整版 .pdf》由会员分享，可在线阅读，更多相关《耿国华数据结构习题答案完整版 .pdf（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章答案1.3 计算下列程序中x=x+1 的语句频度for(i=1;i=n;i+) for(j=1;j=i;j+) for(k=1;k=j;k+) x=x+1; 【解答】 x=x+1 的语句频度为：T(n)=1+(1+2)+（1+2+3 ）+ （ 1+2+ +n ）=n(n+1)(n+2)/6 1. 4 试编写算法， 求 pn(x)=a0+a1x+a2x2+ .+anxn的值 pn(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为ai(i=0,1,n) 、x 和 n,输出为 Pn(x0)。 算法的输入和输出

2、采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。【解答】（1）通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。（ 2）通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue() int i,n; float x,a,p; printf(“nn=”);scanf( “%f”,&n);p

3、rintf(“nx=”);scanf( “%f”,&x);for(i=0;in;i+) scanf( “%f ”,&ai); /*执行次数： n 次 */ p=a0; for(i=1;i=n;i+) p=p+ai*x; /*执行次数： n 次 */ x=x*x; printf(“%f”,p); 算法的时间复杂度：T(n)=O(n) 通过参数表中的参数显式传递float PolyValue(float a , float x, int n) float p,s; int i; p=x; s=a0; for(i=1;i=n;i+) s=s+ai*p; /*执行次数 :n 次*/ p=p*x; re

4、turn(p); 算法的时间复杂度：T(n)=O(n) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 42 页 - - - - - - - - - 第二章答案2.7试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表（a1,a2, ,an）逆置为 (an,an-1, ,a1)。【解答】（ 1）用一维数组作为存储结构void invert(SeqList *L, int *num) int j;ElemType tmp;for(j=0;jnext =

5、NULL) return; /*链表为空 */p=L-next; q=p-next; p-next=NULL; /* 摘下第一个结点，生成初始逆置表*/while(q!=NULL) /* 从第二个结点起依次头插入当前逆置表*/r=q-next;q-next=L-next;L-next=q;q=r;2.11将线性 表A=(a1,a2, am), B=(b1,b2, bn)合并成 线性表C, C=(a1,b1, am,bm,bm+1, .bn)当mn 时,线性表 A、B、C 以单链表作为存储结构，且 C 表利用 A 表和 B 表中的结点空间构成。注意： 单链表的长度值m 和 n 均未显式存储。【解

6、答】算法如下：LinkList merge(LinkList A, LinkList B, LinkList C) Node *pa, *qa, *pb, *qb, *p;pa=A-next; /*pa 表示 A 的当前结点 */pb=B-next; p=A; / *利用 p 来指向新连接的表的表尾，初始值指向表A 的头结点 */while(pa!=NULL & pb!=NULL) /*利用尾插法建立连接之后的链表*/ qa=pa-next; qb=qb-next;p-next=pa; /*交替选择表A 和表 B 中的结点连接到新链表中；*/p=pa;p-next=pb;p=pb; pa=qa

7、;pb=qb;if(pa!=NULL) p-next=pa; /*A 的长度大于B 的长度 */ if(pb!=NULL) p-next=pb; /*B 的长度大于A 的长度 */名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 42 页 - - - - - - - - - C=A; Return(C);第三章答案3.1 按 3.1(b) 所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：（1）如进站的车厢序列为123，则可能得到的出站车厢序列是什么？（2）如进站的车厢

8、序列为123456 ，能否得到 435612 和 135426 的出站序列，并说明原因（即写出以“S”表示进栈、 “X”表示出栈的栈序列操作）。【解答】（1）可能得到的出站车厢序列是：123、 132 、213、231、321。(2)不能得到435612 的出站序列。因为有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6)，此时按照“后进先出”的原则，出栈的顺序必须为X(2)X(1) 。能得到 135426 的出站序列。因为有 S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。3.3 给出栈的两种存储结构形式名称，在这两种栈

9、的存储结构中如何判别栈空与栈满？【解答】（1）顺序栈（top 用来存放栈顶元素的下标）判断栈 S 空：如果S-top=-1表示栈空。判断栈 S 满：如果 S-top=Stack_Size-1表示栈满。(2) 链栈（ top 为栈顶指针，指向当前栈顶元素前面的头结点）判断栈空：如果top-next=NULL表示栈空。判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。3 4 照四则运算加、减、乘、除和幂运算的优先惯例，画出对下列表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D+E F 【解答】3 5 写一个算法，判断依次读入的一个以为结束符的字母序列，是否形如序列1&

10、序列 2的字符序列。序列1 和序列 2 中都不含 & ，且序列2 是序列 1 的逆序列。例名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 42 页 - - - - - - - - - 如， a+b&b+a 是属于该模式的字符序列，而1+3&3 -1 则不是。【解答】算法如下：int IsHuiWen() Stack *S; Char ch,temp; InitStack(&S); Printf(“n 请输入字符序列：” ); Ch=getchar(); While( ch

11、!=&) /*序列 1 入栈 */ Push(&S,ch); ch=getchar(); do /*判断序列 2 是否是序列1 的逆序列 */ ch=getchar(); Pop(&S,&temp); if(ch!= temp) /*序列 2 不是序列1 的逆序列 */ re turn(FALSE); printf(“nNO ”); while(ch!= & !IsEmpty(&S) if(ch = = & IsEmpty(&S) return(TRUE); printf(“nYES ”); /*序列 2 是序列 1 的逆序列 */ else return(FALSE); printf(“nN

12、O ”); /*IsHuiWen()*/ 3.8 要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag, 以 tag 为 0 或 1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。【解答】入队算法：int EnterQueue(SeqQueue *Q, QueueElementType x) /*将元素 x 入队 */ if(Q-front=Q-front & tag=1) /*队满 */ return(FALSE); if(Q-front=Q-front & tag=0) /*x 入队前队空，x 入队后重新设置标志*/ tag=1; Q-elememtQ-r

13、ear=x; Q-rear=(Q-rear+1)%MAXSIZE; /*设置队尾指针*/ Return(TRUE); 出队算法：int DeleteQueue( SeqQueue *Q , QueueElementType *x) /* 删除队头元素，用x 返回其值 */ if(Q-front=Q-rear & tag=0) /*队空 */ return(FALSE); *x=Q-elementQ-front; Q-front=(Q-front+1)%MAXSIZE; /*重新设置队头指针*/ if(Q-front=Q-rear) tag=0; /*队头元素出队后队列为空，重新设置标志域*/

14、Return(TUUE); 编写求解Hanoi 问题的算法，并给出三个盘子搬动时的递归调用过程。【解答】算法：void hanoi (int n ,char x, char y, char z) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 42 页 - - - - - - - - - /*将塔座 X 上按直径由小到大且至上而下编号为1 到 n 的 n 个圆盘按规则搬到塔座Z上， Y 可用做辅助塔座*/ if(n = =1) move(x,1,z); else Hano

15、i(n-1,x,z,y); move(x, n, z); Hanoi(n-1, y,x,z); Hanoi(3,A,B,C)的递归调用过程：Hanoi(2,A,C,B): Hanoi(1,A,B,C) move(A-C) 1 号搬到 C Move(A-B) 2 号搬到 B Hanoi(1,C,A,B) move(C-B) 1 号搬到 B Move(A-C) 3 号搬到 C Hanoi(2,B,A,C) Hanoi(1,B,C,A) move(B-A) 1 号搬到 A Move(B-C) 2 号搬到 C Hanoi(1,A,B,C) move(A-C) 1 号搬到 C 第四章答案4.1 设 s=

16、I AM A STUDENT ，t= GOOD ， q=WORKER 。给出下列操作的结果：【解答】 StrLength(s)=14; SubString(sub1,s,1,7) sub1=I AM A ;SubString(sub2,s,7,1) sub2= ;StrIndex(s,4,A)=6;StrReplace(s,STUDENT ,q); s=I AM A WORKER ;StrCat(StrCat(sub1,t),StrCat(sub2,q) sub1=I AM A GOOD WORKER。4.2 编写算法，实现串的基本操作StrReplace(S,T,V)。【解答】算法如下：in

17、t strReplace(SString S,SString T, SString V) /*用串 V 替换 S 中的所有子串T */ int pos,i; pos=strIndex(S,1,T); /*求 S 中子串 T 第一次出现的位置*/ if(pos = = 0) return(0); while(pos!=0) /*用串 V 替换 S 中的所有子串T */ switch(T.len-V.len) case 0: /*串 T 的长度等于串V 的长度 */ for(i=0;ichpos+i=V.chi; case 0: /*串 T 的长度大于串V 的长度 */ for(i=pos+t.i

18、en;ilen;i-) /*将 S 中子串 T 后的所有字符S-chi-t.len+v.len=S-chi; 前移T.len-V.len个位置*/ for(i=0;ichpos+i=V.chi; S-len=S-len-T.len+V.len; case len-T.len+V.len)len-T.len+V.len;i=pos+T.len;i-) S-chi=S-chi-T.len+V.len; for(i=0;ichpos+i=V.chi; S-len=S-len-T.len+V.len; else /*替换后串长 MAXLEN, 但串 V 可以全部替换 */ if(pos+V.len=p

19、os+T.len; i-) S-chi=s-chi-T.len+V.len for(i=0;ichpos+i=V.chi; S-len=MAXLEN; else /*串 V 的部分字符要舍弃*/ for(i=0;ichi+pos=V.chi; S-len=MAXLEN; /*switch()*/ pos=StrIndex(S,pos+V.len,T); /*求 S 中下一个子串T 的位置*/ /*while()*/ return(1); /*StrReplace()*/ 附加题：用链式结构实现定位函数。【解答】typedef struct Node char data; struct Node

20、 *next; Node,*Lstring; int strIndex(Lstring S, int pos, Lstring T) /*从串 S 的 pos 序号起，串T 第一次出现的位置*/ Node *p, *q, *Ppos; int i=0 ，,j=0; if(T-next= =NULL | S-next = =NULL) return(0); p=S-next; q=T-next; while(p!=NULL & jnext; j+; if(j!=pos) return(0); while(p!=NULL & q!=NULL) Ppos=p; /*Ppos指向当前匹配的起始字符*/

21、 if(p-data = = q-data) p=p-next; q=q-next; else /*从 Ppos 指向字符的下一个字符起从新匹配*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 42 页 - - - - - - - - - p=Ppos-next; q=T-head-next; i+; if(q= =NULL) return(pos+i); /*匹配成功 */ else return(0); /*失败 */ 第 4章串习题1. 设 s=I AM A S

22、TUDENT, t= GOOD , q=WORKER 。给出下列操作的结果：StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s,A,4); StrReplace(s,STUDENT ,q); StrCat(StrCat(sub1,t), StrCat(sub2,q); 参考答案 StrLength(s)=14; sub1=I AM A_ ; sub2=_; StrIndex(s,A,4)=6; StrReplace(s,STUDENT ,q)=I AM A WORKER ; StrCat(StrCat(s

23、ub1,t), StrCat(sub2,q)=I AM A GOOD WORKER; 2. 编写算法，实现串的基本操作StrReplace(S,T,V)。3. 假设以块链结构表示串，块的大小为1，且附设头结点。试编写算法，实现串的下列基本操作：StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；StrCat(S,T)； SubString(Sub,S,pos,len)。说明 ：用单链表实现。4 叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。5 已知： S=”(xyz)*”,T=”(

24、x+z)*y”。试利用联接、求子串和置换等操作，将S 转换为T. 6 S 和 T 是用结点大小为1 的单链表存储的两个串，设计一个算法将串S 中首次与T匹配的子串逆置。7 S 是用结点大小为4 的单链表存储的串,分别编写算法在第k 个字符后插入串T， 及从第 k 个字符删除len 个字符。以下算法用定长顺序串：8 写下列算法：（1）将顺序串 r 中所有值为ch1 的字符换成ch2 的字符。（2）将顺序串 r 中所有字符按照相反的次序仍存放在r 中。（3）从顺序串 r 中删除其值等于ch 的所有字符。（4）从顺序串 r1 中第 index 个字符起求出首次与串r2 相同的子串的起始位置。（5）从

25、顺序串 r 中删除所有与串r1 相同的子串。9 写一个函数将顺序串s1 中的第 i 个字符到第j 个字符之间的字符用s2 串替换。提示 ： （1）用静态顺序串（2）先移位，后复制10写算法，实现顺序串的基本操作StrCompare(s,t)。11写算法，实现顺序串的基本操作StrReplace(&s,t,v)。提示 ：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 42 页 - - - - - - - - - （1）被替换子串 定位（相当于第9 题中 i）（2）被替换子串

26、 后面的字符 左移 或右移 （为 替换子串 准备房间）（3）替换子串 入住（复制）（4）重复上述，直到 ,第五章答案5.2 设有三对角矩阵Ann,将其三条对角线上的元素逐行的存于数组B1.3n-2 中，使得Bk=aij，求： （1）用 i,j 表示 k 的下标变换公式； （2）用 k 表示 i、j 的下标变换公式。【解答】（1）k=2(i-1)+j (2) i=k/3+1, j=k/3+k%3 （ 取整， %取余）5.4 在稀疏矩阵的快速转置算法5.2 中，将计算 positioncol的方法稍加改动，使算法只占用一个辅助向量空间。【解答】算法（一）FastTransposeTSMatrix(

27、TSMartrix A, TSMatrix *B) /*把矩阵 A 转置到 B 所指向的矩阵中去，矩阵用三元组表表示*/ int col,t,p,q; int positionMAXSIZE; B-len=A.len; B-n=A.m; B-m=A.n; if(B-len0) position1=1; for(t=1;t=A.len;t+) positionA.datat.col+1+; /*positioncol存放第 col-1 列非零元素的个数, 即利用 poscol来记录第col-1 列中非零元素的个数*/ /*求 col 列中第一个非零元素在B.data 的位置，存放在positio

28、ncol中*/ for(col=2;col=A.n;col+) positioncol=positioncol+positioncol-1; for(p=1;pdataq.row=A.datap.col; B-dataq.col=A.datap.row; B-dataq.e=A.datap.e; Positioncol+; 算法 (二) FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) int col,t,p,q; int positionMAXSIZE; B-len=A.len; B-n=A.m; B-m=A.n; if(B-len0) for(

29、col=1;col=A.n;col+) positioncol=0; for(t=1;t0;col-) t=t-positioncol; positioncol=t+1; for(p=1;pdataq.row=A.datap.col; B-dataq.col=A.datap.row; B-dataq.e=A.datap.e; Positioncol+; 5.6 画出下面广义表的两种存储结构图示：(a), b), ( ), d), (e, f) 【解答】第一种存储结构第二种存储结构名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名

30、师精心整理 - - - - - - - 第 9 页，共 42 页 - - - - - - - - - 5.7 求下列广义表运算的结果：（ 1）HEAD(a,b),(c,d); (a,b) （ 2）TAIL(a,b),(c,d); (c,d) （ 3）TAILHEAD(a,b),(c,d); (b) （ 4）HEADTAILHEAD(a,b),(c,d); b （ 5）TAILHEADTAIL(a,b),(c,d); (d) 第六章答案6 1 分别画出具有3 个结点的树和3 个结点的二叉树的所有不同形态。【解答】具有 3 个结点的树具有 3 个结点的二叉树6.3 已知一棵度为k 的树中有n1个度

31、为 1 的结点， n2个度为 2 的结点， ，nk个度为 k的结点，则该树中有多少个叶子结点？【解答】设树中结点总数为n,则 n=n0 + n1 + + nk 树中分支数目为B,则 B=n1 + 2n2 + 3n3+ + knk因为除根结点外，每个结点均对应一个进入它的分支，所以有n= B + 1 即 n0 + n1 + + nk = n1 + 2n2 + 3n3+ + knk + 1 由上式可得叶子结点数为：n0 = n2 + 2n3+ + (k-1)nk + 1 6.5 已知二叉树有50 个叶子结点，则该二叉树的总结点数至少应有多少个？【解答】 n0表示叶子结点数，n2表示度为2 的结点数

32、，则n0 = n2+1 所以 n2= n0 1=49 ，当二叉树中没有度为1 的结点时，总结点数n=n0+n2=996.6 试分别找出满足以下条件的所有二叉树: (1) 前序序列与中序序列相同; (2) 中序序列与后序序列相同; (3) 前序序列与后序序列相同。【解答】(1) 前序与中序相同：空树或缺左子树的单支树；(2) 中序与后序相同：空树或缺右子树的单支树；(3) 前序与后序相同：空树或只有根结点的二叉树。6.9 假设通讯的电文仅由8 个字母组成，字母在电文中出现的频率分别为：0.07 ， 0.19，0.02 ，0.06 ，0.32 ，0.03，0.21 ，0.10 请为这 8 个字母设

33、计哈夫曼编码。【解答】构造哈夫曼树如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 42 页 - - - - - - - - - 哈夫曼编码为：I1：11111I5：1100I2：11110I6： 10I3：1110 I7： 01I4：1101 I8： 00 6.11 画出如下图所示树对应的二叉树。【解答】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1

34、1 页，共 42 页 - - - - - - - - - 6.15 分别写出算法，实现在中序线索二叉树T 中查找给定结点*p 在中序序列中的前驱与后继。在先序线索二叉树T 中，查找给定结点*p 在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p 在后序序列中的前驱。（1）找结点的中序前驱结点BiTNode *InPre (BiTNode *p) /*在中序线索二叉树中查找p 的中序前驱结点，并用pre 指针返回结果*/ if (p-Ltag= =1) pre = p-LChild; /*直接利用线索*/ else /* 在 p 的左子树中查找“最右下端”结点*/ for ( q=p-L

35、Child; q-Rtag= =0; q=q-RChild); pre = q; return (pre); （2）找结点的中序后继结点BiTNode *InSucc (BiTNode *p) /*在中序线索二叉树中查找p 的中序后继结点，并用succ指针返回结果*/ if (p-Rtag= =1) succ = p-RChild; /*直接利用线索*/ else /* 在 p 的右子树中查找“最左下端”结点*/ for ( q=p-RChild; q-Ltag= =0; q=q-LChild); succ= q; return (succ); (3) 找结点的先序后继结点BiTNode *P

36、reSucc (BiTNode *p) /*在先序线索二叉树中查找p 的先序后继结点，并用succ指针返回结果*/ if (p-Ltag= =0) succ = p-LChild; else succ= p-RChild; return (succ); (4) 找结点的后序前驱结点BiTNode *SuccPre (BiTNode *p) /*在后序线索二叉树中查找p 的后序前驱结点，并用pre 指针返回结果*/ if (p-Ltag= =1) pre = p-LChild; else pre= p-RChild; return (pre); 6.21 已知二叉树按照二叉链表方式存储，利用栈的

37、基本操作写出先序遍历非递归形式的算法。【解答】Void PreOrder(BiTree root) /*先序遍历二叉树的非递归算法*/ InitStack(&S); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 42 页 - - - - - - - - - p=root; while(p!=NULL | !IsEmpty(S) ) if(p!=NULL) Visit(p-data); push(&S,p); p=p-Lchild; else Pop(&S,&p); p

38、=p-RChild; 6.24 已知二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。【解答】算法 (一) Void exchange ( BiTree root ) p=root; if ( p-LChild != NULL | p-RChild != NULL ) temp = p-LChild; p-LChild = p-RChild; p-RChild = temp; exchange ( p-LChild ); exchange ( p-RChild ); 算法 (二) Void exchange ( BiTree root ) p=root; if ( p-LChil

39、d != NULL | p-RChild != NULL ) exchange ( p-LChild ); exchange ( p-RChild ); temp = p-LChild; p-LChild = p-RChild; p-RChild = temp; 第七章答案名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 42 页 - - - - - - - - - 7.1 已知如图所示的有向图，请给出该图的：（1）每个顶点的入度、出度；（2）邻接矩阵；（3）邻接表；（4

40、）逆邻接表；（5）十字链表；（6）强连通分量。【解答】（1）顶点入度出度1 3 0 2 2 2 3 1 2 4 1 3 5 2 1 6 2 3 （3）邻接矩阵（3）邻接表1 5 6 2 4 3 题 1 图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 42 页 - - - - - - - - - （4）逆邻接表（5）十字链表（6）强连通分量7.2 已知如图所示的无向图，请给出该图的：（2）深度优先遍历该图所得顶点序列和边的序列；（3）广度优先遍历该图所得顶点序列和边的序

41、列。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 42 页 - - - - - - - - - 【解答】（2）深度优先搜索顶点序列： 1-2-3-4-5-6 边的序列：（1，2） （2，3） （3，4） （4，5） （ 5，6）深度优先搜索树：（2）广度优先搜索顶点序列： 1-2-3-6-5-4 边的序列： （1， 2） （1，3） （1，6） （1，5） （5，4）深度优先搜索树：注：本题中所求深度优先序列和广度优先序列有多种，以上为其中一种。73 【解答】源点终点

42、最短路径路径长度1 2 1，3，2 19 3 1，3 15 4 1，3， 2，4 29 5 1，3，5 29 6 1，3， 2，4，6 44 712 【解答】（A）深度遍历： 1， 2，3，8，4，5，7，6 或 1，2，3，8，5， 7，4，（B）广度遍历： 1， 2，4，6，3，5，7，8 （C）拓扑序列： 1， 2，4，6，5，3，7，8 （D）最短路径： 1， 2，5，7，8 （E）关键路径： 1， 6，5，3，8 713 【解答】按层遍历二叉树LayerOrder(BiTree root) LinkQueue Q; InitQueue(&Q); if(root=NULL) retur

43、n; EnterQueue(&Q,root); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 42 页 - - - - - - - - - while(!Empty(&Q) DelQueue(&Q,&p); visite(p-data); if(p-LChild!=NULL) EnterQueue(&Q,p-LChild); if(p-RChild!=NULL) EnterQueue(&Q,p-RChild); 第八章答案82 【解答】5 ASLsucc=（1+2X2

44、+3X4+4X3）/10=2.9 8.5 【解答】ASLSUCC=(1 X4+2 X3+6 )/8=2 ASLUNSUCC=(2+1+8+7+6+5+4+3+2+1+1)/11=40/11 8.12 【解答】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 42 页 - - - - - - - - - (1)ASLSUCC=(1+2 X2+3 X3+4X3+5X2+6)/12=3.5 (2)排序为： Apr,Aug,Dec,Feb,Jan,July,June,Mar,Ma

45、y,Nov,Oct,Sep 折半查找 ASLSUCC=(1+2 X2+3 X4+4X5)/12=37/12 9.1 (1) 无序表：顺序查找不成功时， 查找长度为n+1； 成功时，平均查找长度为1/(n+1)*(1+2+,+(n+1)=(n+2)/2；两者不相同。（2）表中只有一个关键字等于给定值k 的记录，无序表、有序表：顺序查找成功时，平均查找长度均为1/(n)*(1+2+,+n)=(n+1)/2；两者相同。（3）表中只有m个关键字等于给定值k 的记录，无序表：ASL=n+1；有序表： ASL= （n+1）/2+m；两者不相同。9.3 ASL=1/10（1+2*2+4*3+3*4 ）=2.

46、9 9.11 6 5 2 8 3 1 97 4 10 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 42 页 - - - - - - - - - 9.14 删除 50 后删除 68 后20 20 30 50 20 30 50 52 20 30 50 20 30 52 60 50 20 30 52 60 68 68 30 52 20 70 60 50 60 20 30 52 68 70 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

47、 - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 42 页 - - - - - - - - - 9.19 22 67 41 30 53 46 13 01 0 1 2 3 4 5 6 7 8 9 10 ASL= （4*1+2*2+3+6 ）/8=17/8 9.25 int Search-Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于key 的数据元素，ST按关键字自大至小有序，/ 若找到，则函数值为该元素在表中的位置，否则为0 ST.elemST.length+1.key=key; for (i=1; ST

48、.elemi.keykey; +i); if (ST.elemi.key=key)&(irchild; p=p-rchild); return p-data; /Maxv TelemType Minv(Bitree T) / 返回二叉排序树T 中所有结点的最小值for (p=T; p-lchild; p=p-lchild); return p-data; /Minv Status IsBST(Bitree T) /判别 T 是否为二叉排序树 if (!T) return OK; else if (!T-lchild)|(T-lchild)&(IsBST(T-lchild)&(Maxv(T-lc

49、hild)data) &(!T-rchild)|(T-rchild)&(IsBST(T-rchild)&(Minv(T-rchild)T-data) return OK else return ERROR; /IsBST 9.33 Status OutputGEx(Bitree T, TelemType x) /从大到小输出给定二叉排序树T 中所有值不小于x 的数据元素 if (T) if (OutputGEx(T-rchild, x) 60 70 20 30 52 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

50、- - - - - - - 第 20 页，共 42 页 - - - - - - - - - if (T-data=x) print(T-data); if (OutputGEx(T-lchild, x) return OK; else return OK; else return OK; /OutputGEx 第九章查找9.25 int Search_Sq(SSTable ST,int key)/在有序表上顺序查找的算法,监视哨设在高下标端 ST.elemST.length+1.key=key; for(i=1;ST.elemi.keykey;i+); if(iST.length|ST.ele