数据结构——C语言描述习题及答案耿国华

1、第1章绪论一、问答题1 .什么是数据结构？2 .四类基本数据结构的名称与含义。3 .算法的定义与特性。4 .算法的时间复杂度。5 .数据类型的概念。6 .线性结构与非线性结构的差别。7 .面向对象程序设计语言的特点。8 .在面向对象程序设计中，类的作用是什么？9 .参数传递的主要方式及特点。10 .抽象数据类型的概念。二、判断题1 .线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。2 .算法就是程序。3 .在高级语言(如C、或PASCAL)中，指针类型是原子类型。三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i+)for(j=1;j<=i;j+)

2、for(k=1;k<=j;k+)x=x+1;提示:i=1时：1=(1+1)1/2=(1+12)/2i=2时：1+2=(1+2)22=(2+22)/2i=3时：1+2+3=(1+3)3/2=(3+32)/2i=n时：1+2+3+n=(1+n)的2=(n+n2)/2f(n)=(1+2+3+n)+21+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+aix+a2X2+a3X3+-anxn的值Pn(x0),并确定算法中的每

3、一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求备函数。注意：本题中的输入ai(i=0,1,n)x和n,输出为Pn(xo).通常算法的输入和输出可采用下列两种方式之一：(1)通过参数表中的参数显式传递；(2)通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。提示:floatPolyValue(floata,floatx,intn)核心语句：p=1;(x的零次募)s=0;i从0到n循环s=s+ai*p;p=p*x;p=x;(x的一次哥)s=a0;i从1到n循环s=s+ai*p;p=p*x;实习题设计实现抽象数

4、据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法,以及求有理数的分子、分母。第一章答案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)/61.4 试编写算法，求pn(x)=a0+ax+a2x2+.+anxn的值Pn(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求募函数。注意：本题中的输入为ai(

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

6、tf(nn=");scanf("%f",&n);printf(nx=");scanf("%f",&x);for(i=0;i<n;i+)scanf("%f,&ai);/*执行次数：n次*/p=a0;for(i=1;i<=n;i+)/*执行次数：n次*/p=p+ai*x;x=x*x;printf("%f",p);算法的时间复杂度：T(n)=O(n)通过参数表中的参数显式传递floatPolyValue(floata,floatx,intn)(floatp,s;inti;p=

7、x;s=a0;for(i=1;i<=n;i+)s=s+ai*p;/*执行次数:n次*/p=p*x;return(p);算法的时间复杂度：T(n)=O(n)第2章线性表习题< 描述以下三个概念的区别：头指针，头结点，首元素结点。< 填空： 在顺序表中插入或删除一个元素，需要平均移动一半元素,具体移动的元素个数与一插入或删除的位置_有关。 在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋的next域指示。

8、< 已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。a.在P结点后插入S结点的语句序列是：(4)、(1)。b.在P结点前插入S结点的语句序列是：(7)、(11)、(8)、(4)、(1)。c.在表首插入S结点的语句序列是：(5)、(12)。d.在表尾插入S结点的语句序列是：(11)、(9)、(1)、(6)。供选择的语句有：(1) P->next=S;(2) P->next=P->next->next;(3) P->next=S->next;(4) S->next=P->next;(

9、5) S->next=L;(6) S->next=NULL;(7) Q=P;(3) while(P->next!=Q)P=P->next;(4) while(P->next!=NULL)P=P->next;(5) P=Q;(6) )P=L;(7) L=S;(8) L=P;1.1 已知线性表L递增有序。试写一算法，将X插入到L的适当位置上，以保持线性表的有序性。提示:voidinsert(SeqList*L;ElemTypex)<方法1>(1)找出应插入位置i,(2)移位，(3)<方法2>参P.2291.2 写一算法，从顺序表中删除自第

10、i个元素开始的k个元素。提示:注意检查i和k的合法性。(集体搬迁，“新房”、“旧房”)4 方法1>以待移动元素下标m(“旧房号”)为中心，计算应移入位置(“新房号”)：for(m=i1+k;m<=L>last;m+)L>elemmk=L>elemm;5 方法2>同时以待移动元素下标m和应移入位置j为中心：6 方法3>以应移入位置j为中心，计算待移动元素下标：1.3 已知线性表中的元素(整数)以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素(若表中存在这样的元素)，分析你的算法的时间复杂度(注意：min

11、k和maxk是给定的两个参变量，它们的值为任意的整数)。提示:注意检查mink和maxk的合法性：mink<maxk不要一个一个的删除(多次修改next域)。(1)找到第一个应删结点的前驱prepre=L;p=L>next;while(p!=NULL&&p>data<=mink)pre=p;p=p>next;(2)找到最后一个应删结点的后继s,边找边释放应删结点s=p;while(s!=NULL&&s>data<maxk)t=s;s=s>next;free(t);(3)pre>next=s;1.4 试分别以不

12、同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表(a1，a2.,an)逆置为(a5an-1,.,a1)。(1)以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。(2)以单链表作存储结构。方法1：在原头结点后重新头插一遍方法2：可设三个同步移动的指针p,q,r,将q的后继r改为p1.5 假设两个按元素值递增有序排列的线性表A和B,均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表C,并要求利用原表(即A表和B表的)结点空间存放表C.提示:参P.28例2-1<方法1>voidmerge(LinkLi

13、stA;LinkListB;LinkList*C)pa=A>next;pb=B>next;*C=A;(*C)->next=NULL;while(pa!=NULL&&pb!=NULL)if(pa>data<=pb>data)smaller=pa;pa=pa>next;smaller>next=(*C)>next;/*头插法*/(*C)>next=smaller;)else(smaller=pb;pb=pb>next;smaller>next=(*C)>next;(*C)>next=smaller;

14、)while(pa!=NULL)(smaller=pa;pa=pa>next;smaller>next=(*C)>next;(*C)>next=smaller;)while(pb!=NULL)(smaller=pb;pb=pb>next;smaller>next=(*C)>next;(*C)>next=smaller;)<方法2>LinkListmerge(LinkListA;LinkListB)LinkListC;pa=A>next;pb=B>next;C=A;C>next=NULL;returnC;1 假设有一个

15、循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。提示:设指针p指向s结点的前趋的前趋，则p与s有何关系？1 已知有单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其它字符)，试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。1 设线性表A=(ai,a2,sm),B=(b1,b2,bn),试写一个按下列规则合并A、B为线性表C的算法，使得：C=(a1,b1,am,bm,bm+1,bn)当mn时；或者C=(a1,b

16、1,an,bn,an+1,am)当m>n时。线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。提示:voidmerge(LinkListA;LinkListB;LinkList*C)或：LinkListmerge(LinkListA;LinkListB)1 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。提示:注明用头指针还是尾指针。1 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。并

17、在此链表上实现对二进制数加1的运算。提示:可将低位放在前面。1 设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x值，求P(x)的值。提示:floatPolyValue(Polylistp;floatx)实习题1 .将若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市名、城市的位置坐标。要求：4 给定一个城市名，返回其位置坐标；5 给定一个位置坐标P和一个距离D,返回所有与P的距离小于等于D的城市。2,约瑟夫环问题。约瑟夫问题的一种描述是：编号为1,2,，n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个整数作为报数上限值m,从第一个人开始顺

18、时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如m的初值为20;n=7,7个人的密码依次是：3,1,7,2,4,8,4,出列的顺序为6,1,4,7,2,3,5。第二章答案实习题二：约瑟夫环问题约瑟夫问题的一种描述为：编号1,2,n的n个人按顺时针方向围坐一圈，每个人持有一个密码(正整数)。一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出

19、列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如，m的初值为20;n=7,7个人的密码依次是：3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,3,5。【解答】算法如下：typedefstructNode(intpassword;intnum;structNode*next;Node,*Linklist;voidJosephus()(LinklistL;Node*p,*r,*q;intm,n,C,j;L=(Node*)ma

20、lloc(sizeof(Node);/*初始化单向循环链表*/if(L=NULL)printf("n链表申请不到空间！");return;L->next=NULL;r=L;printf("请输入数据n的值(n>0):");scanf("%d",&n);for(j=1;j<=n;j+)/*建立链表*/(p=(Node*)malloc(sizeof(Node);if(p!=NULL)(printf("请输入第%d个人的密码：",j);scanf("%d",&C);p

21、->password=C;p->num=j;r->next=p;r=p;r->next=L->next;printf("请输入第一个报数上限值m(m>0):");scanf("%d",&m);printf("*n");printf("出列的顺序为：n");q=L;p=L->next;while(n!=1)/*计算出列的顺序*/(j=1;while(j<m)/*计算当前出列的人选p*/(q=p;/*q为当前结点p的前驱结点*/p=p->next;j+;pr

22、intf("%d->",p->num);/*获得新密码*/m=p->password;n-;q->next=p->next;/*p出歹U*/r=p；p=p->next;free(r);)printf("%dn",p->num);)2.7试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表(a1,a2,向)逆置为(an,an-1,向)。【解答】(1)用一维数组作为存储结构voidinvert(SeqList*L,int*num)intj;ElemTypetmp;for(j=0;j<=(*

23、num-1)/2;j+)tmp=Lj;Lj=L*num-j-1;L*num-j-1=tmp;)(2)用单链表作为存储结构voidinvert(LinkListL)Node*p,*q,*r;if(L->next=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=

24、(b1,b2,bn)合并成线性表C,C=(a1,b1,am,bm,bm+1,.bn)当m<=n时，或C=(a1,b1,an,bn,an+1,am)当m>n时，线性表A、B、C以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。【解答】算法如下：LinkListmerge(LinkListA,LinkListB,LinkListC)Node*pa,*qa,*pb,*qb,*p;pa=A->next;/*pa表示A的当前结点*/pb=B->next;p=A;/*利用p来指向新连接的表的表尾，初始值指向表A的头结点*/while

25、(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=qb;)if(pa!=NULL)p->next=pa;/*A的长度大于B的长度*/if(pb!=NULL)p->next=pb;/*B的长度大于A的长度*/C=A;return(C);第3章限定性线性表栈和队列习题1,按图3.1（b）所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：如进

26、站的车厢序列为123,则可能得到的出站车厢序列是什么？123、213、132、231、321（312）如进站的车厢序列为123456,能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X62.设队列中有A、B、C、D、E这5个元素，其中队首元素为Ao如果对这个队列重复执行下列4步操作：(1) 输出队首元素；(2) 把队首元素值插入到队尾；(3) 删除队首元素；(4) 再次删除队首元素。直到队列成为空队列为止，则是否可能得到输出序列：7 A、C、E、C、C（2）

27、A、C、E(5) 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,给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？15 .按照四则运算加、减、乘、除和哥运算（T）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程:AB*C/D+ETF16 .试写一个算法，

28、判断依次读入的一个以为结束符的字母序列，是否为形如序列1&序列2'模式的字符序列。其中序列1和序列2中都不含字符'&'且序列2是序列1的逆序列。例如，'a+b&b+a'是属该模式的字符序列，而1+3&31'则不是。提示:3 边读边入栈，直到&4 边读边出栈边比较，直到17 .假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式(中缀)且书写正确的表达式转换为逆波兰式(后缀)。提示:例：中缀表达式：a+b后缀表达式：ab+中缀表达式：a+bxc后缀表达式：abc/中缀表达式：a+bx

29、c-d后缀表达式：abc/d-中缀表达式：a+bxc-d/e后缀表达式：abcx+de/-中缀表达式：a+bx(c-d)-e/f后缀表达式：abcd->+ef/-6 后缀表达式的计算过程：(简便)顺序扫描表达式，(1)如果是操作数，直接入栈；(2)如果是操作符op,则连续退栈两次，得操作数X,Y,计算XopY,并将结果入栈。7 如何将中缀表达式转换为后缀表达式？顺序扫描中缀表达式，(1)如果是操作数，直接输出；(2)如果是操作符op2,则与栈顶操作符0Pl比较：如果op2>op1,贝Uop2入栈；如果op2=op1,则脱括号；如果op2<op1,贝U输出OPi;18 .假设以

30、带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。提示:参P.56P.70先画图.typedefLinkListCLQueue;intInitQueue(CLQueue*Q)intEnterQueue(CLQueueQ,QueueElementTypex)intDeleteQueue(CLQueueQ,QueueElementType*x)19 .要求循环队列不损失一个空间全部都能得到利用，设置一个标志域tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。提示:初始状态：

31、front=0,rear=0,tag=0tag=0tag=1tag=0(或1、2)队空条件：front=rear,队满条件：front=rear,其它状态：front!=rear,入队操作：(入队)if(front=rear)tag=1;(或直接tag=1)出队操作：(出队)tag=0;问题:如何明确区分队空、队满、非空非满三种情况？20 .简述以下算法的功能(其中栈和队列的元素类型均为int):3.3 voidproc_1(StackS)iinti,n,A255;n=0;while(!EmptyStack(S)n+;Pop(&S,&An);for(i=1;i<=n;i+

32、)Push(&S,Ai);将栈S逆序。voidproc_2(StackS,inte)(StackT;intd;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的元素。6 voidproc_3(Queue*Q)(StackS;intd;InitStack(&S);while(!EmptyQueue(*Q)(DeleteQueue(Q,&am

33、p;d);Push(&S,d);while(!EmptyStack(S)(Pop(&S,&d);EnterQueue(Q,d)将队列Q逆序。实习题5.6 .回文判断。称正读与反读都相同的字符序列为“回文”序列。试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列1&序列2'模式的字符序列。其中序列1和序列2中都不含字符'&',且序列2是序列1的逆序列。例如，'a+b&b+a'是属该模式的字符序列，而1+3&31'则不是。6.6 .停车场管理。设停车场是一个可停放n辆车的狭长通

34、道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。试编写程序，模拟上述管理过程。要求以顺序栈模拟停车场，以链队列模拟便道。从终端读入汽车到达或离去的数据，每组数据包括三项：是“到达”还是“离去”；汽车牌照号码；“到达”或“离去”的时刻。与每组输入信息相应的输出

35、信息为：如果是到达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。（提示：需另设一个栈，临时停放为让路而从车场退出的车。）车库便道暂时退车道7.6 .商品货架管理。商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。用队列和栈作为周转，实现上述管理过程。第三章答案7 按3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度，回答：(1)如进站的车厢序列为123,则可能得到的出站车厢序列是什么？(2)如进站的车厢序列为123456,能否得到435612和1354

36、26的出站序列，并说明原因(即写出以“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)。(1) 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？【解答】(1)顺序栈(top用来存放栈顶元素

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

38、39;,且序列2是序列1的逆序列。例如，'a+b&b+a'是属于该模式的字符序列，而1+3&31'则不是。【解答】算法如下：intIsHuiWen()Stack*S;Charch,temp;InitStack(&S);Printf(n请输入字符序列：");Ch=getchar();While(ch!=&)/*序列1入栈*/(Push(&S,ch);ch=getchar();do(ch=getchar();Pop(&S,&temp);if(ch!=temp)(return(FALSE);printf(nN&

39、#39;。);while(ch!=&&!IsEmpty(&S)if(ch=&&IsEmpty(&S)return(TRUE);printf(nYES');else/*判断序列2是否是序列1的逆序列*/*序列2不是序列1的逆序列*/*序列2是序列1的逆序列*/return(FALSE);printf(nNO);/*IsHuiWen()*/5 要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为。或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。【解答】入队算法：intEnterQueue(Se

40、qQueue*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;/*设置队尾指针*/Return(TRUE);出队算法：intDeleteQueue(SeqQueue*Q,QueueElementType*x

41、)/*删除队头元素，用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);编写求解Hanoi问题的算法，并给出三个盘子搬动时的递归调用过程。【解答】算法：voidhanoi(intn,charx,chary,charz)/*将塔

42、座X上按直径由小到大且至上而下编号为1到n的n个圆盘按规则搬到塔座Z上，Y可用做辅助塔座*/if(n=1)move(x,1,z);elseHanoi(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号搬到CMove(A->B)2号搬到BHanoi(1,C,A,B)move(C->B)1号搬到BMove(A->C)3号搬到CHanoi(2,B,A,C)Hanoi(1,B,C,A)move(B->A)1号搬到AMo

43、ve(B->C)2号搬到CHanoi(1,A,B,C)move(A->C)1号搬到C第4章串习题5.5 .设s='IAMASTUDENT',t='GOOD,q='WORKER。给出下列操作的结果：StrLength(s);SubString(sub1,s,1,7);SubString(sub2,s,7,1);StrIndex(s,'A',StrReplace(s,'STUDENT,q);StrCat(StrCat(sub1,t),StrCat(sub2,q);参考答案StrLength(s)=14;sub1='IAMA

44、二'sub2='工'StrIndex(s,'A'6;4)=StrReplace(s,'STUDENT,q)=IAMAWORKER;StrCat(StrCat(sub1,t),StrCat(sub2,q)='IAMAGOODWORKER;6.6 .编写算法，实现串的基本操作StrReplace(S,T,V)。7.7 .假设以块链结构表示串，块的大小为1,且附设头结点。试编写算法，实现串的下列基本操作：StrAsign(S,chars);StrCopy(S,T);StrCompare(S,T);StrLength(S);StrCat(S,T)

45、;SubString(Sub,S,pos,len)。说明:用单链表实现。8.8 .叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。9.9 .已知：S="(xyz)*“万="(x+z)*y利'用联接、求子串和置换等操作，将S转换为T.10.10 .S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。11.11 .S是用结点大小为4的单链表存储的串，分别编写算法在第k个字符后插入串T,及从第k个字符删除len个字符。以下算法用定长顺序串：8.写下列算法:8 将顺序串9 将顺序串10 从顺序串

46、11 从顺序串12 从顺序串r中所有值为chi的字符换成ch2的字符。r中所有字符按照相反的次序仍存放在r中。r中删除其值等于ch的所有字符。ri中第index个字符起求出首次与串r2相同的子串的起始位置。r中删除所有与串ri相同的子串。12.12 .写一个函数将顺序串si中的第提小:(1)用静态顺序串13.13 .写算法，实现顺序串的基本操作14.14 .写算法，实现顺序串的基本操作提示:(1)被替换子串定位(相当于第i个字符到第j个字符之间的字符用s2串替换。(2)先移位，后复制StrCompare(s,t)。StrReplace(&s,t,v)。9题中i)(2)被替换子串后面的字

47、符左移或右移(为替换子串准备房间)(3)替换子串入住(复制)(4)重复上述，直到答案q='WORKER。给出下列操作的结果：sub1='IAMA'；sub2='；s='IAMAWORKER；sub1='IAMAGOODWORKER。第四章1 设s='IAMASTUDENT',t='GOOD【解答】StrLength(s)=14;SubString(sub1,s,1,7)SubString(sub2,s,7,1)StrIndex(s,4,'A)=6;StrReplace(s,'STUDENT,q);StrCa

48、t(StrCat(sub1,t),StrCat(sub2,q)1 编写算法，实现串的基本操作StrReplace(S,T,V)。【解答】算法如下：intstrReplace(SStringS,SStringT,SStringV)/*用串V替换S中的所有子串T*/intpos,i;pos=strIndex(S,1,T);/*求S中子串T第一次出现的位置*/if(pos=0)return(0);/*用串V替换S中的所有子串T*/while(pos!=0)switch(T.len-V.len)case0:for(i=0;i<=V.len;i+)S->chpos+i=V.chi;case&

49、gt;0:for(i=pos+t.ien;i<S->len;i-)S->chi-t.len+v.len=S->chi;for(i=0;i<=V.len;i+)S->chpos+i=V.chi;S->len=S->len-T.len+V.len;case<0:if(S->len-T.len+V.len)<=MAXLEN/*将S中子串T后的所有字符后移/*串T的长度等于串V的长度*/*用V替换T*/*串T的长度大于串V的长度*/*将S中子串T后的所有字符前移T.len-V.len个位置*/*用V替换T*/*串T的长度小于串V的长度*

50、/*插入后串长小于MAXLEN*/V.len-T.len个位置*/for(i=S->len-T.len+V.len;i>=pos+T.len;i-)S->chi=S->chi-T.len+V.len;for(i=0;i<=V.len;i+)/*用V替换T*/S->chpos+i=V.chi;S->len=S->len-T.len+V.len;else/*替换后串长>MAXLEN,但串V可以全部替换*/if(pos+V.len<=MAXLEN)for(i=MAXLEN-1;i>=pos+T.len;i-)S->chi=s-&

51、gt;chi-T.len+V.lenfor(i=0;i<=V.len;i+)/*用V替换T*/S->chpos+i=V.chi;S->len=MAXLEN;else/*串V的部分字符要舍弃*/for(i=0;i<MAXLEN-pos;i+)S->chi+pos=V.chi;S->len=MAXLEN;pos=StrIndex(S,pos+V.len,T);/*求S中下一个子串T的位置*/*switch()*/*while()*/return(1);/*StrReplace()*/附加题：用链式结构实现定位函数。【解答】typedefstructNodecha

52、rdata;structNode*next;Node,*Lstring;intstrIndex(LstringS,intpos,LstringT)/*从串S的pos序号起，串T第一次出现的位置*/Node*p,*q,*Ppos;inti=0,j=0;if(T->next=NULL|S->next=NULL)return(0);p=S->next;q=T->next;while(p!=NULL&&j<pos)/*p指向串S中第pos个字符*/p=p->next;j+;if(j!=pos)return(0);while(p!=NULL&&

53、amp;q!=NULL)Ppos=p;/*Ppos指向当前匹配的起始字符*/if(p->data=q->data)p=p->next;q=q->next;else/*从Ppos指向字符的下一个字符起从新匹配*/p=Ppos->next;q=T->head->next;i+;/*匹配成功*/*失败*/if(q=NULL)return(pos+i);elsereturn(0);第五章数组和广义表习题.假设有6行8列的二维数组A,每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000,计算：000000000000 数组A共占用多少字节；(288)

54、111111111111 数组A的最后一个元素的地址；(1282)222222222222 按行存储时，元素A36的地址；(1126)333333333333 按列存储时，元素A36的地址；(1192)注意:本章自定义数组的下标从1开始。.设有三对角矩阵(a"nxn，将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得Bk=aij,求：用i,j表示k的下标变换公式；用k表示i,j的下标变换公式。i=k/3+1,j=k%3+i-1=k%3+k/3或：=k/3+1,j=k-2X(k/3).假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩

55、阵。提示:参考P.28例、P.47例。.在稀疏矩阵的快速转置算法5.2中，将计算positioncol的方法稍加改动，使算法只占用一个辅助向量空间。提示:positionk中为第k列非零元素个数，k=1,2,-nposition0=1;(第1列中第一个非零元素的正确位置)positionk=positionk-1+positionk,k=1,2,，npositionk=positionk-1,k=n,n-1,1.写一个在十字链表中删除非零元素aj的算法。提示:“删除”两次，释放一次。.画出下面广义表的两种存储结构图示:(a),b),(),d),(e,f)1IA0e第一种存储结构(自底向上看).

56、求下列广义表运算的结果：HEAD(a,b),(c,d);TAIL(a,b),(c,d);TAILHEAD(a,b),(c,d);HEADTAILHEAD(a,b),(c,d);bTAILHEADTAIL(a,b),(c,d);(d)参考题.试设计一个算法，将数组A(0:n-1)中的元素循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O(n)。.假设按低下标优先(以最左的下标为主序)存储整数数组A(1:8,1:2,1:4,1:7)时，第一个元素的字节地址是100,每个整数占4个字节，问元素A(4,2,3,5)的存储地址是什么？.高下标优先(以最右的下标为主序)存储整数数组A(1:8,1:2,1:4,1:7)时，顺序列出数组A的所有元素。.试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。实习题1,若矩阵A亦n中的某个元素a。是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍