《耿国华数据结构课后习题答案》由会员分享，可在线阅读，更多相关《耿国华数据结构课后习题答案（45页珍藏版）》请在金锄头文库上搜索。
1、第第 1 1 章章绪绪 论论2.(1)(2)(3)3.（1）A（2）C（3）C5.计算下列程序中 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)/66.编写算法， 求 一元多项式 pn(x)=a0+a1x+a2x2+.+anxn的值 pn(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度， 要求时间复杂度尽可能小， 规定算法中不能使用求幂函数。注意：本题中的输入为ai(i=0,1,n)、x 和
2、 n,输出为 Pn(x0)。 算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。【解答】（1）通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。（2）通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue() int i,n;float x,a,p;printf(“nn=
3、”);scanf(“%f”,&n);printf(“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)通过参数表中的参数显式传递floatPolyValue(floata ,floatx,intn)float p,s;int i;p=x;s=a0;for(i=1;inext=S;B P-next= P-next-next;C P-next= S-next;D
4、 S-next= P-next;E S-next= L;F S-next= NULL;G Q= P;H while (P-next!=Q) P=P-next;I while (P-next!=NULL) P=P-next;J P= Q;K P= L;L L= S;M L= P;(3) D(4) D(5) D(6) A7 试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表（a1,a2,an）逆置为(an,an-1,a1)。【解答】（1）用一维数组作为存储结构void invert(SeqList *L, int *num)int j;ElemType tmp;for(j=
5、0;jnext =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;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;pb=
7、qb;if(pa!=NULL)p-next=pa;/*A 的长度大于 B 的长度*/if(pb!=NULL)p-next=pb;/*B 的长度大于 A 的长度*/C=A;Return(C);实习题实习题约瑟夫环问题约瑟夫问题的一种描述为：编号 1,2,n的 n 个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个报数上限值m,从第一个人开始顺时针自 1 开始顺序报数，报到m 时停止报数。报 m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。 利用单向循环链表作为存储结构模拟
8、此过程， 按照出列顺序打印出各人的编号。例如m的初值为20； n=7， 7个人的密码依次是： 3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,3,5。【解答】算法如下：typedef struct Nodeint password;int num;struct Node *next; Node,*Linklist;void Josephus()Linklist L;Node *p,*r,*q;int m,n,C,j;L=(Node*)malloc(sizeof(Node); /*初始化单向循环链表*/if(L=NULL) printf(n 链表申请不到空间!);return;L-ne
9、xt=NULL;r=L;printf(请输入数据 n 的值(n0):);scanf(%d,&n);for(j=1;jpassword=C;p-num=j;r-next=p;r=p;r-next=L-next;printf(请输入第一个报数上限值m(m0):);scanf(%d,&m);printf(*n);printf(出列的顺序为:n);q=L;p=L-next;while(n!=1)/*计算出列的顺序*/j=1;while(jnext;j+;printf(%d-,p-num);m=p-password;/*获得新密码*/n-;q-next=p-next;/*p 出列*/r=p;p=p-ne
10、xt;free(r);printf(%dn,p-num);第 3 章 限定性线性表 栈和队列第三章答案1 按 3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：（1）如进站的车厢序列为 123，则可能得到的出站车厢序列是什么？（2）如进站的车厢序列为 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
11、(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 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？【解答】 （1）顺序栈（top 用来存放栈顶元素的下标）判断栈 S 空：如果 S-top=-1 表示栈空。判断栈 S 满：如果 S-top=Stack_Size-1表示栈满。(2) 链栈（top 为栈顶指针，指向当前栈顶元素前面的头结点）判断栈空：如果 top-next=NULL 表示栈空。判断栈满：当系统没有
12、可用空间时，申请不到空间存放要进栈的元素，此时栈满。4 照四则运算加、减、乘、除和幂运算的优先惯例，画出对下列表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D+EF【解答】5 写一个算法，判断依次读入的一个以为结束符的字母序列，是否形如序列1&序列 2的字符序列。 序列 1 和序列 2 中都不含 & ， 且序列 2 是序列 1 的逆序列。 例如， a+b&b+a是属于该模式的字符序列，而1+3&3-1则不是。【解答】算法如下：intIsHuiWen()Stack*S;Charch,temp;InitStack(&S);Printf(“n 请输入字符序列：”);Ch=getchar();
13、While( ch!=&)/*序列 1 入栈*/Push(&S,ch);ch=getchar();do/*判断序列 2 是否是序列 1 的逆序列*/ ch=getchar();Pop(&S,&temp);if(ch!= temp)/*序列 2 不是序列 1 的逆序列*/ return(FALSE);printf(“nNO”); while(ch!=&!IsEmpty(&S)if(ch = = &IsEmpty(&S) return(TRUE);printf(“nYES”);/*序列 2 是序列 1 的逆序列*/elsereturn(FALSE);printf(“nNO”);/*IsHuiWen
14、()*/8要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以 tag 为 0 或 1 来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。【解答】入队算法：intEnterQueue(SeqQueue*Q,QueueElementTypex)/*将元素 x 入队*/if(Q-front=Q-front&tag=1)/*队满*/return(FALSE);if(Q-front=Q-front&tag=0)/*x 入队前队空，x 入队后重新设置标志*/tag=1;Q-elememtQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE;/*设置队尾
15、指针*/Return(TRUE);出队算法：intDeleteQueue( 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;/*队头元素出队后队列为空，重新设置标志域*/Return(TUUE);第第4 4章章 串串第四章答案1 设 s=I AM A STUDENT ，t=GOOD， q=
16、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 。2 编写算法，实现串的基本操作StrReplace(S,T,V) 。【解答】算法如下：intstrReplace(SString S,SString T, SStr
17、ing V)/*用串 V 替换 S 中的所有子串 T */intpos,i;pos=strIndex(S,1,T);/*求 S 中子串 T 第一次出现的位置*/if(pos = = 0)return(0);while(pos!=0)/*用串 V 替换 S 中的所有子串 T */switch(T.len-V.len)case0:/*串 T 的长度等于串 V 的长度*/for(i=0;ichpos+i=V.chi;case0:/*串 T 的长度大于串 V 的长度*/for(i=pos+t.ien;ilen;i-)/*将 S 中子串 T 后的所有字符S-chi-t.len+v.len=S-chi;前
18、移 T.len-V.len个位置*/for(i=0;ichpos+i=V.chi;S-len=S-len-T.len+V.len;caselen-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=pos+T.len; i-)S-chi=s-chi-T.len+V.lenfor(i=0;ichpos+i=V.chi;S-len=MA
19、XLEN;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()*/第五章第五章数组和广义表数组和广义表第五章答案1.假设有 6 行 8 列的二维数组 A，每个元素占用 6 个字节，存储器按字节编址。已知 A 的基地址为 1000，计算：（1）数组 A 共占用多少字节； （288）（2）数组 A 的最后一个元素的地址； （1282）（3）按行存储时，元
20、素 A36 的地址； （1126）（4）按列存储时，元素 A36 的地址； （1192）4.设有三对角矩阵 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.在稀疏矩阵的快速转置算法5.2 中，将计算 positioncol的方法稍加改动，使算法只占用一个辅助向量空间。【解答】算法（一）FastTransposeTSMatrix(TSMartrixA,TSMatrix*
21、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 的位置，存放在 positioncol中*/for(col=2;col=A.n;col+)posit
22、ioncol=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(TSMartrixA,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(col=1;col=A.n;col+)positioncol=0;for(t=1;t0;col-)t=t-p
23、ositioncol;positioncol=t+1;for(p=1;pdataq.row=A.datap.col;B-dataq.col=A.datap.row;B-dataq.e=A.datap.e;Positioncol+;8.画出下面广义表的两种存储结构图示：(a), b), ( ), d), (e, f)【解答】第一种存储结构第二种存储结构第二种存储结构9.求下列广义表运算的结果：（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（
24、5）TAILHEADTAIL(a,b),(c,d);(d)第六章第六章答案6 1分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态。【解答】具有 3 个结点的树具有 3 个结点的二叉树6.3 已知一棵度为 k 的树中有 n1个度为 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+ + kn
25、k + 1由上式可得叶子结点数为：n0= n2 + 2n3+ + (k-1)nk + 16.5 已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少应有多少个？【解答】n0表示叶子结点数，n2表示度为 2 的结点数，则 n0= n2+1所以 n2=n01=49，当二叉树中没有度为1 的结点时，总结点数 n=n0+n2=996.6 试分别找出满足以下条件的所有二叉树:(1) 前序序列与中序序列相同;(2) 中序序列与后序序列相同;(3) 前序序列与后序序列相同。【解答】(1) 前序与中序相同：空树或缺左子树的单支树；(2) 中序与后序相同：空树或缺右子树的单支树；(3) 前序与后序相同：空树
26、或只有根结点的二叉树。6.9假设通讯的电文仅由 8 个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这 8 个字母设计哈夫曼编码。【解答】构造哈夫曼树如下：哈夫曼编码为：I1：11111I5：1100I2：11110I6： 10I3：1110 I7： 01I4：1101 I8： 006.11 画出如下图所示树对应的二叉树。【解答】6.16 分别写出算法，实现在中序线索二叉树T 中查找给定结点*p 在中序序列中的前驱与后继。在先序线索二叉树 T 中，查找给定结点*p 在先序序列中的后继。在后序线索二叉树 T中，查找给定结
27、点*p 在后序序列中的前驱。（1）找结点的中序前驱结点BiTNode*InPre (BiTNode*p)/*在中序线索二叉树中查找p 的中序前驱结点，并用pre 指针返回结果*/ if (p-Ltag= =1)pre = p-LChild;/*直接利用线索*/else/*在 p 的左子树中查找“最右下端”结点*/for ( q=p-LChild; q-Rtag= =0; q=q-RChild);pre = q;return (pre);（2）找结点的中序后继结点BiTNode*InSucc (BiTNode*p)/*在中序线索二叉树中查找p 的中序后继结点，并用succ 指针返回结果*/ if
28、 (p-Rtag= =1)succ = p-RChild;/*直接利用线索*/else/*在 p 的右子树中查找“最左下端”结点*/for ( q=p-RChild; q-Ltag= =0; q=q-LChild);succ= q;return (succ);(3) 找结点的先序后继结点BiTNode*PreSucc (BiTNode*p)/*在先序线索二叉树中查找p 的先序后继结点，并用succ 指针返回结果*/ if (p-Ltag= =0)succ = p-LChild;elsesucc= p-RChild;return (succ);(4) 找结点的后序前驱结点BiTNode*Succ
29、Pre (BiTNode*p)/*在后序线索二叉树中查找p 的后序前驱结点，并用pre 指针返回结果*/ if (p-Ltag= =1)pre = p-LChild;elsepre= p-RChild;return (pre);6.20 已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。【解答】VoidPreOrder(BiTreeroot)/*先序遍历二叉树的非递归算法*/InitStack(&S);p=root;while(p!=NULL | !IsEmpty(S) ) if(p!=NULL)Visit(p-data);push(&S,p);p=p-Lchild
30、;elsePop(&S,&p);p=p-RChild;6.26 二叉树按照二叉链表方式存储，编写算法将二叉树左右子树进行交换。【解答】算法(一)Voidexchange ( BiTreeroot )p=root;if ( p-LChild != NULL | p-RChild != NULL )算法(二)Voidexchange ( BiTreeroot )p=root;if ( p-LChild != NULL | p-RChild != NULL )exchange ( p-LChild );exchange ( p-RChild );temp = p-LChild;p-LChild =
31、p-RChild;p-RChild = temp;第八章temp = p-LChild;p-LChild = p-RChild;p-RChild = temp;exchange ( p-LChild );exchange ( p-RChild );第八章答案81 【解答】5ASLsucc=（1+2X2+3X4+4X3）/10=2.98.5【解答】(1)ASLSUCC=(1+2 X2+3 X3+4X3+5X2+6)/12=3.5(2)排序为：Apr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,Sep折半查找 ASLSUCC=(1+2 X2+3 X4+4X5
32、)/12=37/128.12 【解答】ASLSUCC=(1 X4+2 X3+6)/8=2ASLUNSUCC=(2+1+8+7+6+5+4+3+2+1+1)/11=40/11f87第一章绪论一、问答题1.什么是数据结构？2.叙述四类基本数据结构的名称与含义。3.叙述算法的定义与特性。4.叙述算法的时间复杂度。5.叙述数据类型的概念。6.叙述线性结构与非线性结构的差别。7.叙述面向对象程序设计语言的特点。8.在面向对象程序设计中，类的作用是什么？9.叙述参数传递的主要方式及特点。10.叙述抽象数据类型的概念。二、判断题（在各题后填写“”或“”）1.线性结构只能用顺序结构来存放，非线性结构只能用非顺
33、序结构来存放。（）2.算法就是程序。 （）3.在高级语言（如 C 或 PASCAL）中，指针类型是原子类型。 （）三、计算下列程序段中X=X+1 的语句频度for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x=x+1;【解答】i=1 时： 1 = (1+1)1/2 = (1+12)/2i=2 时： 1+2 = (1+2)2/2 = (2+22)/2i=3 时： 1+2+3 = (1+3)3/2 = (3+32)/2i=n 时： 1+2+3+n = (1+n)n/2 = (n+n2)/2x=x+1 的语句频度为：f(n) = (1+2+3+n) + (12
34、 + 22 + 32 + + n2 ) / 2= (1+n)n/2 + n(n+1)(2n+1)/6 / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n) = O(n3)四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+anxn的值 Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度， 要求时间复杂度尽可能小， 规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,n),x 和 n，输出为 Pn(x0)。通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递。（2）通过全局
35、变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出【解答】（1）通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。（2）通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue() int i,n;float x,a,p;printf(“nn=”);scanf(“%f”,&n);printf(“nx=”);scanf(“%f”,&x)
36、;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)通过参数表中的参数显式传递floatPolyValue(floata ,floatx,intn)float p,s;int i;p=x;s=a0;for(i=1;inext=S;（2）P-next= P-next-next;（3）P-next= S-next;（4）S-next= P-next;（5）S-next= L;（6）S-next= NUL
37、L;（7）Q= P;（8）while(P-next!=Q) P=P-next;（9）while(P-next!=NULL) P=P-next;（10）P= Q;（11）P= L;（12）L= S;（13）L= P;2.4 已知线性表 L 递增有序。试写一算法，将 X 插入到 L 的适当位置上，以保持线性表 L的有序性。Status Insert_SqList(SqList &va,int x)/把 x 插入递增有序表 va 中if(va.length+1va.listsize) return ERROR;va.length+;for(i=va.length-1;va.elemix&i=0;i-
38、)va.elemi+1=va.elemi;va.elemi+1=x;return103fOK;/Insert_SqList2.5 写一算法，从顺序表中删除自第i 个元素开始的 k 个元素。提示：注意检查 i 和 k 的合法性。（集体搬迁，“新房”、“旧房”） 以待移动元素下标 m（“旧房号”）为中心，计算应移入位置（“新房号”） ：for ( m= i1+k;mlast;m+)Lelem mk = Lelem m ; 同时以待移动元素下标 m 和应移入位置 j 为中心： 以应移入位置 j 为中心，计算待移动元素下标：2.6 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写
39、一高效算法，删除表中所有大于mink 且小于 maxk 的元素（若表中存在这样的元素） ，分析你的算法的时间复杂度（注意：mink 和 maxk 是给定的两个参变量，它们的值为任意的整数） 。Status Delete_Between(Linklist &L,int mink,int maxk)/删除元素递增排列的链表 L 中值大于mink 且小于 maxk 的所有元素p=L;while(p-next-datanext; /p是最后一个不大于 mink 的元素if(p-next)/如果还有比 mink 更大的元素q=p-next;while(q-datanext; /q是第一个不小于 maxk
40、 的元素p-next=q;/Delete_Between2.7 试分别以不同的存储结构实现线性表的就地逆置算法， 即在原表的存储空间将线性表 （a1,a2., an）逆置为（an, an-1,., a1） 。（1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前 elenum 个分量中。（2）以单链表作存储结构。方法 1:在原头结点后重新头插一遍方法 2:可设三个同步移动的指针p, q, r，将 q 的后继 r 改为 p2.8 假设两个按元素值递增有序排列的线性表 A 和 B，均以单链表作为存储结构，请编写算法， 将 A 表和 B 表归并成一个按元素值递减有序的排列的线性表C，
41、并要求利用原表 （即A 表和 B 表的）结点空间存放表C.提示：参 P.28例 2-1voidmerge(LinkListA;LinkListB;LinkList*C)pa=Anext;pb=Bnext;*C=A;(*C)next=NULL;while ( pa!=NULL & pb!=NULL ) if ( padata data ) smaller=pa;pa=panext;smallernext = (*C)next;/* 头插法 */(*C)next = smaller;else smaller=pb;pb=pbnext;smallernext = (*C)next;(*C)next
42、= smaller;while ( pa!=NULL)smaller=pa;pa=panext;smallernext = (*C)next;(*C)next = smaller;while ( pb!=NULL)smaller=pb;pb=pbnext;smallernext = (*C)next;(*C)next = smaller;LinkListmerge(LinkListA;LinkListB)LinkListC；pa=Anext;pb=Bnext;C=A;Cnext=NULL;returnC;while(pa|pb)if(pa-datadata|!pb)pc=pa;q=pa-nex
43、t;pa-next=pre;pa=q; /将 A 的元素插入新表elsepc=pb;q=pb-next;pb-next=pre;pb=q; /将 B 的元素插入新表pre=pc;C=A;A-next=pc; /构造新表头/reverse_merge分析:本算法的思想是,按从小到大的顺序依次把A 和 B 的元素插入新表的头部pc 处,最后处理 A 或 B 的剩余元素.2.9 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s 为指向链表某个结点的指针，试编写算法在链表中删除指针s 所指结点的前趋结点。提示：设指针 p 指向 s 结点的前趋的前趋，则p 与 s 有何关系？Statu
44、s Delete_Pre(CiLNode *s)/删除单循环链表中结点 s 的直接前驱p=s;while(p-next-next!=s) p=p-next; /找到 s 的前驱的前驱 pp-next=s;return OK;/Delete_Pre2.10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符） ， 试编写算法来构造三个以循环链表表示的线性表， 使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiLi
45、st &C)/ 把单链表 L 的元素按类型分为三个循环链表.CiList 为带头结点的单循环链表类型.s=L-next;A=(CiList*)malloc(sizeof(CiLNode);p=A;B=(CiList*)malloc(sizeof(CiLNode);q=B;C=(CiList*)malloc(sizeof(CiLNode);r=C; /建立头结点while(s)if(isalphabet(s-data)p-next=s;p=s;else if(isdigit(s-data)q-next=s;q=s;elser-next=s;r=s;/whilep-next=A;q-next=B;
46、r-next=C; /完成循环链表/LinkList_Divide2.11 设线性表 A=(a1, a2,am)，B=(b1, b2,bn)，试写一个按下列规则合并A、B 为线性表 C 的算法，使得：C= (a1, b1,am, bm, bm+1, ,bn)当 mn 时；或者C= (a1, b1,an, bn, an+1, ,am)当 mn 时。线性表 A、B、C 均以单链表作为存储?103f峁梗褻表利用 A 表和 B 表中的结点空间构成。注意：单链表的长度值m 和 n 均未显式存储。提示：voidmerge(LinkListA;LinkListB;LinkList*C)或：LinkListm
47、erge(LinkListA;LinkListB)void merge1(LinkList &A,LinkList &B,LinkList &C)/把链表 A 和B 合并为C,A 和B 的元素间隔排列,且使用原存储空间p=A-next;q=B-next;C=A;while(p&q)s=p-next;p-next=q; /将 B 的元素插入if(s)t=q-next;q-next=s; /如 A 非空,将 A 的元素插入p=s;q=t;/while/merge12.12 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这
48、两个链表。提示：注明用头指针还是尾指针。void Divide_LinkedPoly(LinkedPoly &L,&A,&B)/把循环链表存储的稀疏多项式 L 拆成只含奇次项的 A 和只含偶次项的 Bp=L-next;A=(PolyNode*)malloc(sizeof(PolyNode);B=(PolyNode*)malloc(sizeof(PolyNode);pa=A;pb=B;while(p!=L)if(p-data.exp!=2*(p-data.exp/2)pa-next=p;pa=p;elsepb-next=p;pb=p;p=p-next;/whilepa-next=A;pb-nex
49、t=B;/Divide_LinkedPoly2.13 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data 域存放一个二进制位。并在此链表上实现对二进制数加1 的运算 。提示：可将低位放在前面。2.14 设多项式 P(x)采用课本中所述链接方法存储。写一算法，对给定的x 值，求P(x)的值。提示：floatPolyValue(Polylistp;floatx) 第三章栈和队列1.按图 3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： 如进站的车厢序列为123，则可能得到的出站车厢序列是什么？如进站的车厢序列为 123456，能否得到435612 和 1
50、35426 的出站序列，并说明原因。 （即写出以“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)。2.设队列中有 A、B、C、D、E 这 5 个元素，其中队首元素为A。如果对这个队列重复执行下
51、列 4 步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。直到队列成为空队列为止，则是否可能得到输出序列：（1）A、C、E、C、C（2） A、C、E（3）A、C、E、C、C、C（4） A、C、E、C提示：A、B、C、D、E（输出队首元素 A）A、B、C、D、E、A（把队首元素 A 插入到队尾）B、C、D、E、A（删除队首元素 A）C、D、E、A（再次删除队首元素B）C、D、E、A （输出队首元素 C）C、D、E、A、C（把队首元素 C 插入到队尾）D、E、A、C（删除队首元素 C）E、A、C（再次删除队首元素D）3.给出栈的两种存储结构形式名
52、称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：AB【解答】5.试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列 1&序列 2模式的字符序列。 其中序列 1 和序列 2中都不含字符&， 且序列 2是序列 1 的逆序列。例如，a+b&b+a是属该模式的字符序列，而+&则不是。提示：（1）边读边入栈，直到&（2）边读边出栈边比较，直到int IsReverse()/判断输入的字符串中&前和&后部分是否为逆串,是则返回 1,否则返回 0InitStack(s);whil
53、e(e=getchar()!=&)push(s,e);while(e=getchar()!=)if(StackEmpty(s) return 0;pop(s,c);if(e!=c) return 0;if(!StackEmpty(s) return 0;return 1;/IsReverse6.假设表达式由单字母变量和双目四则运算算符构成。 试写一个算法， 将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀） 。void NiBoLan(char *str,char *new)/把中缀表达式 str 转换成逆波兰式 newp=str;q=new; /为方便起见,设 str 的两端
54、都加上了优先级最低的特殊符号InitStack(s); /s为运算符栈while(*p)if(*p 是字母) *q+=*p; /直接输出elsec=gettop(s);if(*p 优先级比 c 高) push(s,*p);elsewhile(gettop(s)优先级不比*p 低)pop(s,c);*(q+)=c;/whilepush(s,*p); /运算符在栈内遵循?103f酵欢畔燃对礁叩脑?/else/elsep+;/while/NiBoLan /参见编译原理教材7.假设以带头结点的循环链表表示队列， 并且只设一个指针指向队尾元素结点 （注意不设头指针） ，试编写相应的队列初始化、入队列和出
55、队列的算法。void InitCiQueue(CiQueue &Q)/初始化循环链表表示的队列QQ=(CiLNode*)malloc(sizeof(CiLNode);Q-next=Q;/InitCiQueuevoid EnCiQueue(CiQueue &Q,int x)/把元素 x 插入循环链表表示的队列 Q,Q 指向队尾元素,Q-next 指向头结点,Q-next-next 指向队头元素p=(CiLNode*)malloc(sizeof(CiLNode);p-data=x;p-next=Q-next; /直接把 p 加在 Q 的后面Q-next=p;Q=p;/修改尾指针Status DeC
56、iQueue(CiQueue &Q,int x)/从循环链表表示的队列Q 头部删除元素 xif(Q=Q-next) return INFEASIBLE; /队列已空p=Q-next-next;x=p-data;Q-next-next=p-next;free(p);return OK;/DeCiQueue8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以 tag 为 0 或 1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。提示：初始状态：front=0,rear=0,tag=0队空条件：front=rear,tag=0队满条件：front
57、=rear,tag=1其它状态：front !=rear,tag=0（或 1、2）入队操作：（入队）if (front=rear)tag=1； （或直接 tag=1）出队操作：（出队）tag=0；问题：如何明确区分队空、队满、非空非满三种情况？9.简述以下算法的功能（其中栈和队列的元素类型均为int） ：（1）void proc_1(Stack S) int i, n, A255;n=0;while(!EmptyStack(S)n+;Pop(&S,&An);for(i=1;i=n;i+)Push(&S,Ai);将栈 S 逆序。（2）void proc_2(Stack S,int e) Stac
58、k T;int d;InitStack(&T);while(!EmptyStack(S) Pop(&S,&d);if (d!=e) Push( &T,d);while(!EmptyStack(T) Pop(&T,&d);Push( &S,d);删除栈 S 中所有等于 e 的元素。（3）void proc_3(Queue*Q) Stack S;int d;InitStack(&S);while(!EmptyQueue(*Q)DeleteQueue(Q,&d);Push( &S,d);while(!EmptyStack(S) Pop(&S,&d);EnterQueue(Q，d)将队列 Q 逆序。第
59、四章串1. 设 s=I AM A STUDENT, 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;SubString(sub1,s,1,7)sub1=I AM A ;SubString(sub2,s,7,1)sub2= ;StrIndex(s,4,A)=6;StrReplace(s,
60、STUDENT,q);s=I AM A WORKER;StrCat(StrCat(sub1,t),StrCat(sub2,q)sub1=I AM A GOOD WORKER 。2. 编写算法，实现串的基本操作StrReplace(S,T,V)。StrCat(S,T)； SubString(Sub,S,pos,len)。int String_Replace(Stringtype &S,Stringtype T,Stringtype V);/ 将串 S 中所有子串 T 替换为 V,并返回置换次数for(n=0,i=1;iT0) /找到了与 T 匹配的子串:分三种情况处理if(T0=V0)for(l
61、=1;l=T0;l+) /新子串长度与原子串相同时:直接替换Si+l-1=Vl;else if(T0=i+T0;l-)Sl+V0-T0=Sl;for(l=1;l=V0;l+)Si+l-1=Vl;else /新子串长度小于原子串时:先将后部左移for(l=i+V0;l=S0+V0-T0;l+)Sl=Sl-V0+T0;for(l=1;lnext;p;p=p-next)r=(LStrNode*)mallo103fc(sizeof(LStrNode);r-ch=p-ch;StrCat(S,T) ；q-next=r;q=r;q-next=NULL;/StringAssignvoid StringCopy
62、(LString &s,LString t)/把串t复制为串s.与前一个程序的区别在于,串s业已存在.for(p=s-next,q=t-next;p&q;p=p-next,q=q-next)p-ch=q-ch;pre=p;while(q)p=(LStrNode*)malloc(sizeof(LStrNode);p-ch=q-ch;pre-next=p;pre=p;p-next=NULL;/StringCopychar StringCompare(LString s,LString t)/串的比较,st时返回正数,s=t 时返回0,snext,q=t-next;p&q&p-ch=q-ch;p=p
63、-next,q=q-next);if(!p&!q) return 0;else if(!p) return -(q-ch);else if(!q) return p-ch;else return p-ch-q-ch;/StringCompareint StringLen(LString s)/求串 s 的长度(元素个数)for(i=0,p=s-next;p;p=p-next,i+);return i;/StringLenLString * Concat(LString s,LString t)/连接串 s 和串 t 形成新串,并返回指针p=malloc(sizeof(LStrNode);for
64、(q=p,r=s-next;r;r=r-next)q-next=(LStrNode*)malloc(sizeof(LStrNode);q=q-next;q-ch=r-ch;/for /复制串 sfor(r=t-next;r;r=r-next)q-next=(LStrNode*)malloc(sizeof(LStrNode);q=q-next;q-ch=r-ch;/for /复制串 tq-next=NULL;return p;/ConcatLString * Sub_String(LString s,int start,int len)/返回一个串,其值等于串 s 从 start 位置起长为le
65、n 的子串p=malloc(sizeof(LStrNode);q=p;for(r=s;start;start-,r=r-next); /找到 start 所对应的结点指针 rfor(i=1;inext)q-next=(LStrNode*)malloc(sizeof(LStrNode);q=q-next;q-ch=r-ch; /复制串 tq-next=NULL;return p;/Sub_String4 叙述以下每对术语的区别：空串和空格串；串变量和串常量； 主串和子串；串变量的名字和串变量的值。char StrCompare(Stringtype s,Stringtype t)/串的比较,st
66、时返回正数,s=t 时返回 0,st 时返回负数for(i=1;i=s0&is0&it0) return 0;else if(is0) return -ti;else if(it0) return si;else return si-ti;/StrCompare5 已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将S 转换为 T.int HString_Replace(HString &S,HString T,HString V)/ 堆结构串上的置换操作,返回置换次数for(n=0,i=0;i=S.length-T.length;i+)for(j=i,k=0
67、;kT.length&S.chj=T.chk;j+,k+);if(k=T.length) /找到了与 T 匹配的子串:分三种情况处理if(T.length=V .length)for(l=1;l=T.length;l+) /新子串长度与原子串相同时:直接替换S.chi+l-1=V.chl-1;else if(T.length=i+T.length;l-)S.chl+V.length-T.length=S.chl;for(l=0;lV.length;l+)Si+l=Vl;else /新子串长度小于原子串时:先将后部左移for(l=i+V.length;lS.length+V.length-T.l
68、ength;l+)S.chl=S.chl-V.length+T.length;for(l=0;lV.length;l+)Si+l=Vl;S.length+=V.length-T.length;i+=V.length;n+;/if/forreturn n;/HString_Replace6 S 和 T 是用结点大小为 1 的单链表存储的两个串，设计一个算法将串 S 中首次与 T 匹配的子串逆置。7 S 是用结点大小为 4 的单链表存储的串,分别编写算法在第 k 个字符后插入串T， 及从第k 个字符删除 len 个字符。以下算法用定长顺序串：8 写下列算法：（1）将顺序串 r 中所有值为 ch1
69、的字符换成 ch2 的字符。（2）将顺序串 r 中所有字符按照相反的次序仍存放在r 中。（3）从顺序串 r 中删除其值等于 ch 的所有字符。（4）从顺序串 r1 中第 index 个字符起求出首次与串r2 相同的子串的起始位置。（5）从顺序串 r 中删除所有与串 r1 相同的子串。9 写一个函数将顺序串 s1 中的第 i 个字符到第 j 个字符之间的字符用 s2 串替换。提示： （1）用静态顺序串（2）先移位，后复制10写算法，实现顺序串的基本操作StrCompare(s,t)。11写算法，实现顺序串的基本操作StrReplace(&s,t,v)。提示：（1）被替换子串定位（相当于第9 题中
70、 i）（2）被替换子串后面的字符左移或右移（为替换子串准备房间）（3）替换子串入住（复制）（4）重复上述，直到实习题1 一、已知串 S 和 T，试以以下两种方式编写算法，求得所有包含在 S 中而不包含在 T中的字符构成的新串 R，以及新串 R 中每个字符在串 S 中第一次出现的位置。（1）利用 CONCAT、LE103fN、SUB 和 EQUAL 四种基本运算来实现。（2）以顺序串作为存储结构来实现。void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)/ 求所有包含在串 s 中而 t 中没有的字符构成的新串 rStrAssi
71、gn(r,);for(i=1;i=Strlen(s);i+)StrAssign(c,SubString(s,i,1);for(j=1;ji&StrCompare(c,SubString(s,j,1);j+); /判断 s 的当前字符 c 是否第一次出现if(i=j)for(k=1;kStrlen(t) StrAssign(r,Concat(r,c);/for/String_Subtract第五章数组和广义表1 假设有 6 行 8 列的二维数组 A，每个元素占用 6 个字节，存储器按字节编址。已知 A的基地址为 1000，计算：（1）数组 A 共占用多少字节； （288）（2）数组 A 的最后一
72、个元素的地址； （1282）（3）按行存储时，元素 A36 的地址； （1126）（4）按列存储时，元素 A36 的地址； （1192）注意：本章自定义数组的下标从1 开始。2 设有三对角矩阵（aij）nn ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得 Bk= aij ，求：（1）用 i,j 表示 k 的下标变换公式；（2）用 k 表示 i,j 的下标变换公式。i = k/3 + 1,j = k%3 + i - 1 = k%3 + k/3或：i = k/3 + 1,j = k - 2( k/3 )3. 假设稀疏矩阵 A 和 B 均以三元组表作为存储结构。试写出矩阵相加的算法
73、，另设三元组表 C 存放结果矩阵。void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)/ 三元组表示的稀疏矩阵加法C.mu=A.mu;C.nu=A.nu;C.tu=0;pa=1;pb=1;pc=1;for(x=1;x=A.mu;x+) /对矩阵的每一行进行加法while(A.datapa.ix) pa+;while(B.datapb.iB.datapb.j)C.datapc.i=x;C.datapc.j=B.datapb.j;C.datapc.e=B.datapb.e;pb+;pc+;elseC.datapc.i=x;C.datapc.j=A
74、.datapa.j;C.datapc.e=A.datapa.epa+;pc+;/whilewhile(A.datapa=x) /插入 A 中剩余的元素(第 x 行)C.datapc.i=x;C.datapc.j=A.datapa.j;C.datapc.e=A.datapa.epa+;pc+;while(B.datapb=x) /插入 B 中剩余的元素(第 x 行)C.datapc.i=x;C.datapc.j=B.datapb.j;C.datapc.e=B.datapb.e;pb+;pc+;/forC.tu=pc;/TSMatrix_Add4在稀疏矩阵的快速转置算法5.2 中，将计算 posi
75、tioncol的方法稍加改动，使算法只占用一个辅助向量空间。5写一个在十字链表中删除非零元素aij 的算法。提示：“删除”两次，释放一次。6画出下面广义表的两种存储结构图示：(a), b), ( ), d), (e, f)7求下列广义表运算的结果：（1）HEAD(a,b),(c,d);（2）TAIL(a,b),(c,d);（3）TAILHEAD(a,b),(c,d);（4）HEADTAILHEAD(a,b),(c,d);b（5）TAILHEADTAIL(a,b),(c,d);(d)实习题若矩阵 Amn 中的某个元素 aij 是第 i 行中的最小值，同时又是第 j 列中的最大值，则称此元素为该矩
76、阵中的一个马鞍点。 假设以二维数组存储矩阵， 试编写算法求出矩阵中的所有马鞍点。void Get_Saddle(int Amn)/求矩阵 A 中的马鞍点for(i=0;im;i+)for(min=Ai0,j=0;jn;j+)if(Aijmin) min=Aij; /求一行中的最小值for(j=0;jn;j+)if(Aij=min) /判断这个(些)最小值是否鞍点for(flag=1,k=0;km;k+)if(mindata=x )FreeTree(*bt);*bt =NULL;elseDelTree( *bt,x)void DelTree(BiTree bt,DataType x) if (
77、bt ) if (bt-LChild & bt-LChild-data=x) FreeTree(bt-LChild);bt-LChild=NULL;if (bt-RChild & bt-RChild-data=x) FreeTree(bt-RChild);bt-RChild=NULL;DelTree(bt-LChild,x);DelTree(bt-RChild,x);方法 2： （1）先序查找； （2）直接查看当前根结点（3）用指针参数；方法 3： （1）先序查找； （2）直接查看当前根结点（3）通过函数值，返回删除后结果；（参示例程序）14分别写函数完成：在先序线索二叉树 T 中，查找给定结
78、点*p 在先序序列中的后继。在后序线索二叉树 T 中，查找给定结点*p 在后序序列中的前驱。提示：（1）先查看线索，无线索时用下面规律：（2）结点*p 在先序序列中的后继为其左子或右子；（3）结点*p 在后序序列中的前驱也是其左子或右子。15分别写出算法，实现在中序线索二叉树中查找给定结点 *p 在中序序列中的前驱与后继。（参例题）16编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。提示：（1）可将孩子-兄弟链表划分为根、首子树、兄弟树，递归处理。（2）可利用返回值，或全局变量。17对以孩子-兄弟链表表示的树编写计算树的深度的算法。18 已知二叉树按照二叉链表方式存储， 利用栈的基本
79、操作写出后序遍历非递归的算法。 （参课本）19设二叉树按二叉链表存放， 写算法判别一棵二叉树是否是一棵正则二叉树。 正则二叉树是指：在二叉树中不存在子树个数为1 的结点。提示：可利用任何递归、非递归遍历算法。20计算二叉树最大宽度的算法。 二叉树的最大宽度是指： 二叉树所有层中结点个数的最大值。提示：方法一：（1）利用队列，初值为根（2）出队访问，并将左、右子入队，直到队空（3）记录每一层中最后一个结点在队中的位置（4）第 i 层最后一个结点的右子，必是第i+1 层的最后一个结点（5）第 1 层最后一个结点在队中的位置为0方法二：利用层号和全局数组，任意遍历、统计21 已知二叉树按照二叉链表方
80、式存储， 利用栈的基本操作写出先序遍历非递归形式的算法。22. 证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树；给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树；23. 二叉树按照二叉链表方式存储，编写算法将二叉树左右子树进行交换。第七章图7.1 已知如图所示的有向图，请给出该图的：（1）每个顶点的入度、出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表；（5）十字链表；（6）强连通分量。7.2 已知如图所示的无向图，请给出该图的：（1）邻接多重表； （要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。
81、）（2）从顶点 1 开始，深度优先遍历该图所得顶点序列和边的序列； （给出深度优先搜索树）（3）从顶点 1 开始，广度优先遍历该图所得顶点序列和边的序列。 （给出广度优先搜索树）7.3 已知如图 7.31 所示的 AOE-网，试求：（1）每个事件的最早发生时间和最晚发生时间；（2）每个活动103f的最早开始时间和最晚开始时间；（3）给出关键路径。7.4 已知如图 7.30 所示的有向网， 试利用 Dijkstra 算法求顶点 1 到其余顶点的最短路径， 并给出算法执行过程中各步的状态。7.5 编写算法，由依次输入的顶点数目、 弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。Status
82、 Build_AdjList(ALGraph &G)/输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表InitALGraph(G);scanf(%d,&v);if(v0) return ERROR; /顶点数不能为负G.vexnum=v;scanf(%d,&a);if(a0) return ERROR; /边数不能为负G.arcnum=a;for(m=0;mv;m+)G.verticesm.data=getchar(); /输入各顶点的符号for(m=1;m=a;m+)t=getchar();h=getchar(); /t为弧尾,h 为弧头if(i=LocateVex(G ,t)0) r
83、eturn ERROR;if(j=LocateVex(G ,h)nextarc;q=q-nextarc);q-nextarc=p;p-adjvex=j;p-nextarc=NULL;/whilereturn OK;/Build_AdjList7.6 试在邻接矩阵存储结构上实现图的基本操作：InsertVertex(G ,v);InsertArc(G, v, w);DeleteVertex(G ,v)和 DeleteArc(G, v, w)。/本题中的图 G 均为有向无权图,其余情况容易由此写出Status Insert_Vex(MGraph &G , char v)/在邻接矩阵表示的图 G 上
84、插入顶点 vif(G.vexnum+1)MAX_VERTEX_NUM return INFEASIBLE;G.vexs+G.vexnum=v;return OK;/Insert_VexStatus Insert_Arc(MGraph &G ,char v,char w)/在邻接矩阵表示的图 G 上插入边(v,w)if(i=LocateVex(G ,v)0) return ERROR;if(j=LocateVex(G ,w)0) return ERROR;if(i=j) return ERROR;if(!G.arcsij.adj)G.arcsij.adj=1;G.arcnum+;return O
85、K;/Insert_ArcStatus Delete_Vex(MGraph &G,char v)/ 在邻接矩阵表示的图 G 上删除顶点 vn=G.vexnum;if(m=LocateVex(G ,v)0) return ERROR;G.vexsmG.vexsn; /将待删除顶点交换到最后一个顶点for(i=0;in;i+)G.arcsim=G.arcsin;G.arcsmi=G.arcsni; /将边的关系随之交换G.arcsmm.adj=0;G.vexnum-;return OK;/Delete_Vex分析:如果不把待删除顶点交换到最后一个顶点的话 ,算法将会比较复杂,而伴随着大量元素的移动
86、,时间复杂度也会大大增加.Status Delete_Arc(MGraph &G ,char v,char w)/在邻接矩阵表示的图 G 上删除边(v,w)if(i=LocateVex(G ,v)0) return ERROR;if(j=LocateVex(G ,w)0) return ERROR;if(G.arcsij.adj)G.arcsij.adj=0;G.arcnum-;return OK;/Delete_Arc7.7 试对邻接表存储结构重做题6。/为节省篇幅,本题只给出 Insert_Arc 算法.其余算法请自行写出.Status Insert_Arc(ALGraph &G ,cha
87、r v,char w)/在邻接表表示的图 G 上插入边(v,w)if(i=LocateVex(G ,v)0) return ERROR;if(j=LocateVex(G ,w)adjvex=j;p-nextarc=NULL;if(!G.verticesi.firstarc) G.verticesi.firstarc=p;elsefor(q=G.verticesi.firstarc;q-q-nextarc;q=q-nextarc)if(q-adjvex=j) return ERROR; /边已经存在q-nextarc=p;G.arcnum+;return OK;/Insert_Arc7.8 试基
88、于图的深度优先搜索策略写一算法， 判别以邻接表方式存储的有向图中， 是否存在由顶点 vi 到顶点 vj 的路径（ij） 。注意：算法中涉及的图的基本操作必须在此存储结构上实现。int visitedMAXSIZE; /指示顶点是否在当前路径上int exist_path_DFS(ALGraph G,int i,int j)/深度优先判断有向图 G 中顶点 i 到顶点 j 是否有路径,是则返回 1,否则返回 0if(i=j) return 1; /i就是 jelsevisitedi=1;for(p=G.verticesi.firstarc;p;p=p-nextarc)k=p-adjvex;if(
89、!visitedk&exist_path(k,j) return 1;/i下游的顶点到 j 有路径/for/else/exist_path_DFS7.9 同上题要求。试基于图的广度优先搜索策略写一算法。int exist_path_BFS(ALGraph G,int i,int j)/广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回 1,否则返回 0int visitedMAXSIZE;InitQueue(Q);EnQueue(Q,i);while(!QueueEmpty(Q)DeQueue(Q,u);visitedu=1;for(p=G.verticesi.firstarc;p;p=
90、p-nextarc)k=p-adjvex;if(k=j) return 1;if(!visitedk) EnQueue(Q,k);/for/whilereturn 0;/exist_path_BFS7.10 试利用栈的?103f静僮鳎嘈窗瓷疃扔畔炔呗员槔桓銮苛嫉摹堑莨樾问降乃惴惴胁还娑 咛宓拇娲峁梗糋 raph 看成是一种抽象数据类型。void STraverse_Nonrecursive(Graph G)/非递归遍历强连通图 Gint visitedMAXSIZE;InitStack(S);Push(S,GetVex(S,1); /将第一个顶点入栈visit(1);visited=1;whi
91、le(!StackEmpty(S)while(Gettop(S,i)&i)j=FirstAdjVex(G ,i);if(j&!visitedj)visit(j);visitedj=1;Push(S,j); /向左走到尽头/whileif(!StackEmpty(S)Pop(S,j);Gettop(S,i);k=NextAdjVex(G ,i,j); /向右走一步if(k&!visitedk)visit(k);visitedk=1;Push(S,k);/if/while/Straverse_Nonrecursive分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考 6.37.由于是强
92、连通图,所以从第一个结点出发一定能够访问到所有结点.7.11 采用邻接表存储结构， 编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为 k 的简单路径（指顶点序列中不含有重现的顶点）的算法。提示：利用深度搜索，增设一个深度参数，深度超过k 则停止对该结点的搜索。int visitedMAXSIZE;int exist_path_len(ALGraph G,int i,int j,int k)/判断邻接表方式存储的有向图G 的顶点 i 到 j 是否存在长度为 k 的简单路径if(i=j&k=0) return 1; /找到了一条路径,且长度符合要求else if(k0)visitedi
93、=1;for(p=G.verticesi.firstarc;p;p=p-nextarc)l=p-adjvex;if(!visitedl)if(exist_path_len(G,l,j,k-1) return 1; /剩余路径长度减一/forvisitedi=0; /本题允许曾经被访问过的结点出现在另一条路径中/elsereturn 0; /没找到/exist_path_len7.12 下图是带权的有向图 G 的邻接表表示法。从结点 V1 出发，深度遍历图 G 所得结点序列为（ A ） ，广度遍历图G 所得结点序列为（ B ） ；G 的一个拓扑序列是（ C ） ；从结点V1 到结点 V8 的最短
94、路径为（ D ） ；从结点 V1 到结点 V8 的关键路径为（ E ） 。其中 A、B、C 的选择有：V1,V2,V3,V4,V5,V6,V7,V8V1,V2,V4,V6,V5,V3,V7,V8V1,V2,V4,V6,V3,V5,V7,V8V1,V2,V4,V6,V7,V3,V5,V8V1,V2,V3,V8,V4,V5,V6,V7V1,V2,V3,V8,V4,V5,V7,V6V1,V2,V3,V8,V5,V7,V4,V6D、E 的选择有：V1,V2,V4,V5,V3,V8V1,V6,V5,V3,V8V1,V6,V7,V8V1,V2,V5,V7,V87.13 已知一棵以二叉链表作存储结构的二叉树
95、， 试编写按层次顺序（同一层自左至右）遍历二叉树的算法。void LayerOrder(Bitree T)/层序遍历二叉树InitQueue(Q); /建立工作队列EnQueue(Q,T);while(!QueueEmpty(Q)DeQueue(Q,p);visit(p);if(p-lchild) EnQueue(Q,p-lchild);if(p-rchild) EnQueue(Q,p-rchild);/LayerOrder第八章查找8.1 若对大小均为 n 的有序的顺序表和无序的顺序表分别进行查找， 试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？（1）查找不成功，即表中没有
96、关键字等于给定值K 的记录。（2）查找成功，且表中只有一个关键字等于给定值K 的记录。（3）查找成功，且表中有若干个关键字等于给定值 K 的记录，一次查找要求找出所有记录。提示：均用顺序查找法。8.2画出对长度为 10 的有序表进行折半查找的判定树， 并求其等概率时查找成功的平均查找长度。提示：根据 P.191ASL 定义计算平均查找长度。8.3试推导含 12 个结点的平衡二叉树的最大深度并画出一棵这样的树。提示：沿最左分支生长，前提是：其任一祖先的右分支与左分支等深，如不等深，则先生长右分支，而生长右分支的前提是：其任一祖先的左分支与右分支等深，如不等深，则先生长左分支，如此交互考虑，逐步生
97、长，直到12 个结点。8.4试从空树开始， 画出按以下次序向 2-3 树，即 3 阶 B-树中插入关键码的建树过程： 20，30，50，52，60，68，70。如果此后删除 50 和 68，画出每一步执行后 2-3 树的状态。8.5选取哈希函数 H(k)=(3k)%11，用线性探测再散列法处理冲突。试在010 的散列地址空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。提示：平均查找长度参考P.225。012345678910224130015346136711221126ASLsucc = (14 + 23 +
98、 6) / 8 = 2ASLunsucc = ( 2 + 1 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 1 ) / 11 = 40 / 118.6试为下列关键字建立一个装载因子不小于0.75 的哈希表， 并计算你所构造的哈希表的平均查找长度。（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG，JIN）提示： （1）由装填因子求出表长， （2）可利用?103f帜感蚝派杓乒：?（3）确定解决冲突的方法。8.7试编写利用折半查找确定记录所在块的分块查找算法。8.8试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以
99、二叉链表作存储结构，且树中结点的关键字均不同。提示：检验中序遍历序列是否递增有序？方法 1：用非递归中序遍历算法，设双指针pre,p一旦 pre-data p-data 则返回假方法 2：用递归中序遍历算法，设全局指针pre， （参中序线索化算法）一旦 pre-data p-data 则返回假方法 3：用递归（中序或后序）算法（1）空树是（2）单根树是（3）左递归真（4）右递归真（5）左子树的右端小于根（6）右子树的左端大于根int last=0,flag=1;int Is_BSTree(Bitree T)/判断二叉树 T 是否二叉排序树,是则返回 1,否则返回 0if(T-lchild&fl
100、ag) Is_BSTree(T-lchild);if(T-datadata;if(T-rchild&flag) Is_BSTree(T-rchild);return flag;/Is_BSTree8.9编写算法，求出指定结点在给定的二叉排序树中所在的层数。8.10 编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结点 A、B 中，A 是 B 的祖先，则认为A 是 A、B 的最近公共祖先） 。提示：（1）假设 Akey 大于、等于 x，则删除 p-rchild 和 p，（3）左走一步，转（2）（4）如果 p-key 小于 x，则反复右走，（5）转（2）（6）直到 p=NU
101、LLvoid Delete_NLT(BiTree &T,int x)/ 删除二叉排序树 T 中所有不小于 x 元素结点,并释放空间if(T-rchild) Delete_NLT(T-rchild,x);if(T-datalchild;free(q); /如果树根不小于 x,则删除树根,并以左子树的根作为新的树根if(T) Delete_NLT(T,x); / 继续在左子树中执行算法/Delete_NLT8.15 在平衡二叉排序树的每个结点中增加一个lsize 域， 其值为它的左子树中的结点数加1。编写一时间复杂度为 O(log n)的算法，确定树中第 k 个结点的位置。提示：先画图手工求。（1
102、）sum=0,（2）从当前根开始沿左链找sum + lsize=k重复（2） 、 （3） ，直到 sum=ktypedef struct int data;int bf;int lsize; /lsize域表示该结点的左子树的结点总数加1BlcNode *lchild,*rchild; BlcNode,*BlcTree; /含 lsize 域的平衡二叉排序树类型BTNode *Locate_BlcTree(BlcTree T,int k)/在含 lsize 域的平衡二叉排序树 T 中确定第 k 小的结点指针if(!T) return NULL; /k小于 1 或大于树结点总数if(T-lsiz
103、e=k) return T; / 就是这个结点else if(T-lsizek)return Locate_BlcTree(T-lchild,k); / 在左子树中寻找else return Locate_BlcTree(T-rchild,k-T-lsize); / 在右子树中寻找,注意要修改 k 的值/Locate_BlcTree第九章内部排序9.1 以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出（前三趟）每一趟排序结束时的关键码状态：（1）直接插入排序；（2）希尔排序（增量 d1=5） ；（3）快速排序；（4）
104、堆排序；（5）归并排序；（6）基数排序。9.2一组关键字码，40，27，28，12，15，50，7，采用快速排序或堆排序，写出每趟排序结果。9.3不难看出，对长度为 n 的记录序列进行快速排序时，所需进行的比较次数依赖于这 n个元素的初始排列。n=7 时在最好情况下需进行多少次比较？请说明理由。对 n=7 给出一个最好情况的初始排列实例103f。（保证每个基准记录都是中间记录）9.4 假设序列由 n 个关键字不同的记录构成， 要求不经排序而从中选出关键字从大到小顺序的前 k(kn)个记录。试问如何进行才能使所作的关键字间比较次数达到最小？（简单选择、冒泡排序、堆排序均有可能）9.5插入排序中找
105、插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。9.6编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。提示： （1）参快速排序（2）“水底”、“水面”相遇时结束。void Bubble_Sort2(int a ,int n)/相邻两趟是反方向起泡的冒泡排序算法low=0;high=n-1; /冒泡的上下界change=1;while(lowhigh&change)change=0;for(i=low;iai+1)aiai+1;change=1;high-; /修改上界for(i=high;ilow;i-) /从下向上起泡if(aiai-1)aiai-1;ch
106、ange=1;low+; /修改下界/while/Bubble_Sort29.7 编写算法，对n 个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：采取顺序存储结构，至多使用一个记录的辅助存储空间；算法的时间复杂度 O(n)；讨论算法中记录的最大移动次数。提示：r0=r1，以 0 为分界值，参快速排序划分过程，但不要求对元素排序。void Divide(int a ,int n)/把数组 a 中所有值为负的记录调到非负的记录之前low=0;high=n-1;while(lowhigh)while(low=0) high-; /以 0 作为虚拟的枢
107、轴记录alowahigh;while(lowhigh&alow0) low+;alowahigh;/Divide9.8 试以单链表为存储结构实现简单选择排序的算法void LinkedList_Select_Sort(LinkedList &L)/单链表上的简单选择排序算法for(p=L;p-next-next;p=p-next)q=p-next;x=q-data;for(r=q,s=q;r-next;r=r-next) /在 q 后面寻找元素值最小的结点if(r-next-datanext-data;s=r;if(s!=q) /找到了值比 q-data 更小的最小结点 s-nextp-nex
108、t=s-next;s-next=q;t=q-next;q-next=p-next-next;p-next-next=t; /交换 q 和 s-next 两个结点/for/LinkedList_Select_Sort9.9 假设含 n 个记录的序列中， 其所有关键字为值介于v 和 w 之间的整数， 且其中很多关键字的值是相同的。则可按如下方法排序：另设数组 numberv.w且令 numberi为统计关键字取整数 I 的记录数，之后按 number 重排序列以达到有序，编写算法实现上述排序方法，并讨论此方法的优缺点。void Enum_Sort(int a ,int n)/对关键字只能取 v 到
109、 w 之间任意整数的序列进行排序int numberw+1,posw+1;for(i=0;in;i+) numberai+; /计数for(pos0=0,i=1;in;i+)posi=posi-1+numi; /pos数组可以把关键字的值映射为元素在排好的序列中的位置for(i=0;in;i+) /构造有序数组 ccposai+=ai;for(i=0;in;i+)ai=ci;/Enum_Sort分析:本算法参考了第五章三元组稀疏矩阵转置的算法思想,其中的 pos 数组和那里的cpot 数组起的是相类似的作用.9.10 已知两个有序序列(a1, a2 ,., am)和(am+1 , am+2 ,
110、., an),并且其中一个序列的记录个数少于s,且s= floor ( sqrt (n) ).试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。void SL_Merge(int a ,int l1,int l2)/把长度分别为 l1,l2 且 l12(l1+l2)的两个有序子序列归并为有序序列start1=0;start2=l1; /分别表示序列 1 和序列 2 的剩余未归并部分的起始位置for(i=0;il1;i+) /插入第 i 个元素for(j=start2;jl1+l2&ajastart1+i;j+); /寻找插入位置k=j-start2; /k 为要向右循环移
111、动的位数RSh(a,start1,j-1,k);/将 astart1到 aj-1之间的子序列循环右移 k 位start1+=k+1;start2=j; /修改两序列尚未归并部分的起始位置/SL_Mergevoid RSh(int a ,int start,int end,int k)/ 将 astart到 aend之间的子序列循环右移k 位,算法原理参见 5.18len=end-start+1;for(i=1;i=k;i+)if(len%i=0&k%i=0) p=i; /求 len 和 k 的最大公约数 pfor(i=0;iai+1,则将两者交换；第一趟对所?b73衅媸齣, 第二趟对所有偶数
112、i，,依次类推直至整个序列有序为止。（1）这种排序方法的结束条件是什么？（2）分析当初始序列为正序或逆序两种情况下， 奇偶交换排序过程中所需进行的关键字比较的次数。（3）写出奇偶交换排序的算法。void LinkedList_Select_Sort(LinkedList &L)/单链表上的简单选择排序算法for(p=L;p-next-next;p=p-next)q=p-next;x=q-data;for(r=q,s=q;r-next;r=r-next) /在 q 后面寻找元素值最小的结点if(r-next-datanext-data;s=r;if(s!=q) /找到了值比 q-data 更小的
113、最小结点 s-nextp-next=s-next;s-next=q;t=q-next;q-next=p-next-next;p-next-next=t; /交换 q 和 s-next 两个结点/for/LinkedList_Select_Sort9.12 设计一个用链表表示的直接选择排序算法。 （与 9.8 重）9.13 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。（与 9.5 重复）9.14 一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对元素排序，但要尽量减少交换次数。（
114、与 9.7 类似）9.15 为什么通常使用一维数组作为堆的存放形式？9.16 已知（k1,k2,，kn）是堆，写一个算法将（k1,k2,，kn，kn+1）调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。void Build_Heap(Heap &H,int n)/从低下标到高下标逐个插入建堆的算法for(i=2;iH.rk.key)H.rjH.rk;j=k;/for/Build_Heap9.17 试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基数排序的时空性能、稳定性和适用情况。9.18在供选择的答案中填入正确答案：1） 、排序（分类）的方法有许多种：
115、_A_法从未排序序列中依次取出元素，与排序序列（初始为空）中的元素作比较，将其放入已排序列的正确位置上； _B_法从未排序序列中挑选元素，并将其依次放入已排序序（初始时为空）的一端；交换排序法是对序列中元素进行一系列的比较， 当被比较的两元素逆序时进行交换。 _C_和_D_是基于这类方法的两种排序方法，而_D_是比_C_效率更高的方法，利用某种算法，根据元素的关键值计算出排序位置的方法是_E_。供选择答案选择排序快速排序插入排序冒泡排序归并排序二分排序哈希排序基数排序2） 、一组记录的关键字为（46，79，56，38，40，84） ，利用快速排序的方法，以第一个记录为基准得到的一次划分结果为C。A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，793） 、下列排序算法中，C算法可能会出现下面情况：初始数据有序时，花费时间反而最多。A、堆排序B、冒泡排序C、快速排序D、SHELL 排序9.19判断正误：（）在一个大堆中，最小元素不一定在最后。（ X ）对 n 个记录采用快速排序方法进行排序，最坏情况下所需时间是o（nlog2n） 。（ X ） 在执行某排序算法过程中， 出现了排序码朝着与最终排序序列相反方向移动的现象，则称该算法是不稳定的。20
