《数据结构-C语言描述》习题及答案

第1章绪论ー、问答题什么是数据结构?四类基本数据结构的名称与含义。算法的定义与特性。4,算法的时间复杂度。数据类型的概念。线性结构与非线性结构的差别。面向对象程序设计语言的特点。在面向对象程序设计中，类的作用是什么?参数传递的主要方式及特点。抽象数据类型的概念。二、判断题.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。.算法就是程序。.在高级语言(如C、或PASCAL)中，指针类型是原子类型。三、计算下列程序段中X=X+1的语句频度for(i=l;i<=n;i++)for(j=l;j<=i;j++)for(k=l;k<=j;k++)x=x+l;［提示］:i=l时:1=(l+l)xl/2=(l+r)/2i=2时:1+2=(112)x2/2=(2+2?)/2i=3时：1+2+3=(1+3)x3/2=(3+32)/2i=n时:1+2+3+ +n=(l+n)xn/2=(n+n2)/2f(n)=[(1+2+3+……+n)+(12+22+32+……+n2)]/2=[(l+n)n/2+n(n+l)(2n+l)/6]/2=n(n+l)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度:O(f(n))=0(n3)四、试编写算法求一元多项式Pn(x)=ao+aix+azx'+asxa…anx"的值Pn(xo)，并确定算法中的每ー语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求森函数。注意:本题中的输入ai(i=0,1,%n),x和n，输出为Pn(xo),通常算法的输入和输出可采用下列两种方式之一:(1)通过参数表中的参数显式传递;(2)通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的ー种方式实现输入和输出〇[提示]:floatPolyValue(floata[],floatx,intn){ }核心语句:p=l;(x的零次幕)s=0;i从0到n循环s=s+a[i]*p;p=p*x;或:p=x;(X的一次嘉)s=a[0];i从1到n循环s=s+a[i]*p;P=P*x;实习题设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法，除法，以及求有理数的分子、分母。第一章答案1.3计算下列程序中x=x+l的语句频度for(i=l;i<=n;i++)for(j=l;j<=i;j++)for(k=l;k<=j;k++)x=x+l;【解答】x=x+l的语句频度为:T(n)=l+(l+2)+(1+2+3)+……+(1+2+……+n)=n(n+l)(n+2)/6.4试编写算法，求pr.(x)=ao+aix+azx2++a»x"的值pn(xo),并确定算法中每ー语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求寡函数。注意:本题中的输入为ai(i=0,1,…n)、x和n,揄出为PKxo)。算法的输入和输出采用下列方法(1)通过参数表中的参数显式传递(2)通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的ー种实现输入输出。【解答】(1)通过参数表中的参数显式传递优点:当没有调用函数时，不占用存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点:形参须与实参对应，且返回值数量有限。(2)通过全局变量隐式传递优点:减少实参与形参的个数，从而减少存空间以及传递数据时的时间消耗缺点:函数通用性降低，移植性差算法如下:通过全局变量隐式传递参数PolyValueO{inti,n;floatx,a[],p;printf("\nn=");scanf("%f",&n);printf("\nx=");scanf("%f",&x);for(i=0;i<n;i++)scanf("%f",&a[i]); /*执行次数:n次・/P=a[0];for(i=l;i<=n;i++){p=p+a[i]*x; /*执行次数:n次・/x=x*x;}printf(,p);算法的时间复杂度:T(n)=O(n)通过参数表中的参数显式传递floatPolyValue(floata[],floatx,intn)(floatp,s;inti;P=x;s二a[0];for(i=l;i<=n;i++){s=s+a[i]*p; /*执行次数:n次・/P=P*x;}return(p);)算法的时间复杂度:T(n)=0(n)第2章线性表习题.! 描述以下三个概念的区别:头指针，头结点，首元素结点。填空:在顺序表中插入或删除ー个元素，需要平均移动 一半元素，具体移动的元素个数与 插入或删除的位置 有关»在顺序表中，逻辑上相邻的元素，其物理位置 相邻。在单链表中，逻辑上相邻的元素，其物理位置 相邻。在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋的next域指示。已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。a.在P结点后插入S结点的语句序列是:⑷、⑴ 。b.在P结点前插入S结点的语句序列是:(7)、(在)、(8)、(4)、(1)。c,在表首插入S结点的语句序列是:(5)、(12)。d,在表尾插入S结点的语句序列是:(11)、(9)、⑴、(6)。供选择的语句有:P->next=S;P->next=P->next->next;P->next=S->next;S->next=P->next;S->next=L;S->next=NULL;Q=P;while(P->next!=Q)P=P->next;whi1e(P->next!=NULL)P=P->next;P=Q；P=L;L=S;L=P;已知线性表L递增有序。试写ー算法，将X插入到L的适当位置上，以保持线性表L的有序性。[提示]:voidinsert(SeqList*L;ElemTypex)く方法1〉(1)找出应插入位置i，(2)移位'(3)……く方法2>参P.229写ー算法，从顺序表中删除自第i个元素开始的k个元素。[提示]:注意检查i和k的合法性。(集体搬迁，"新房"'"旧房")方法1>以待移动元素下标m(“旧房号”)为中心，计算应移入位置(“新房号”)：for(m=i—1+k;m<=L—>last;m++)L—>elem[m—k]=L—>elem[m];方法2>同时以待移动元素下标m和应移入位置j为中心:方法3>以应移入位置j为中心，计算待移动元素下标:2.6已知线性表中的元素(整数)以值递增有序排列，并以单链表作存储结构。试写一高效算法»删除表中所有大于mink且小于maxk的元素(若表中存在这样的元素)，分析你的算法的时间复杂度(注意:mink和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;试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表(ai,a2...,an)逆置为(an,an-i,...,ai)°(1)以ー维数组作存储结构，设线性表存于a(l:arrsize)的前elenum个分量中。(2)以单链表作存储结构。［方法I］:在原头结点后重新头插一遍［方法2］:可设三个同步移动的指针p,q,r，将q的后继r改为p假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C.［提示］:参P.28例2-1く方法1>voidmerge(LinkListA;LinkListB;LinkList*C)pa=A—>next;pb=B—>next;*C=A;(*C)ー)next二NULL;while(pa!=NULL&&pb!=NULL)if(pa—>data<=pb—>data)sma11er=pa;pa=pa—>next;/・头插法・/smaller—/・头插法・/(*C)—>next=smaller;}else(sma11er=pb;pb=pb—>next;smaller—>next=(*C)—>next;(*C)—>next=smaller;})while(pa!=NULL){sma11er=pa;pa=pa—>next;smaller—>next=(*C)—>next;(*C)—>next=smaller;Iwhile(pb!=NULL){sma11er=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，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。［提示］:设指针P指向S结点的前趋的前趋，则P与S有何关系?已知有单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其它字符)，试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间'头结点可另辟空间。设线性表A=(ai,az,…,a.)，B=(b,レ,…，bn)，试写ー个按下列规则合并A、B为线性表C的算法，使得:C=(ai,bi,•,,,a»,b»,tw…，bn)当mWn时;或者 C=(ai,bi,…，a”，bn,a»i,…,疝)当m>n时。线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意:单链表的长度值m和n均未显式存储。［提示］:voidmerge(LinkListA;LinkListB;LinkList*C)或:LinkListmerge(LinkListA;LinkListB)将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。［提示］:注明用头指针还是尾指针。建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。［提示］:可将低位放在前面。设多项式P(x)采用课本中所述方法存储。写ー算法，对给定的x值，求P(x)的值。［提示］:floatPolyValue(Polylistp;floatx)［ }实习题•将若干城市的信息存入ー个带头结点的单链表，结点中的城市信息包括城市名、城市的位置坐标。要求：给定一个城市名，返回其位置坐标;给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。2・约瑟夫环问题。约瑟夫问题的ー种描述是:编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。ー开始任选ー个整数作为报数上限值m,从第一个人开始顺时针自!开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计ー个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如m的初值为20；n=7，7个人的密码依次是:3T出列的顺序为6，1，4,7,2,3,5。第二章答案实习题ニ:约瑟夫环冋题约瑟夫问题的ー种描述为:编号1,2,…，n的n个人按顺时针方向围坐ー圈»每个人持有一个密码(正整数)。ー开始任选ー个报数上限值01,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的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;voidJosephusO{LinklistL;Node*p,*r,*q;intm,n,C,j;L=(Node*)ma11oc(sizeof(Node));/*初始化单向循环链表・/if(L==NULL){printf("\n链表申请不到空间!")；return;}L->next=NULL;

r=L;printf("请输入数据n的值(n>0):");scanf(H%d",&n);for(j=l;j<=n;j++) /・建立链表・/(p=(Node*)malloc(sizeof(Node));if(p!=NULL){printf(w请输入第％d个人的密码:"，j);scanf(u%d\&C);p->password=C;p->num=j;r->next=p;r=p;)}r->next=L->next;printfC请输入第一个报数上限值m(m>O):H);scanf(n%d\&m);printf(M****************糕***********************、ゼ)；printf("出列的顺序为:\nH);q=L;p=L->next;while(n!=l) /*计算出列的顺序・/{j=l；while(j<m) /・计算当前出列的人选p*/q=p; /*q为当前结点p的前驱结点・/p=p->next;j++；"获得新密码*/printf("获得新密码*/n-q->next=p->next; /*p出列*/r=p;p=p->next;free(r);)printf(M%d\n\p->num);}2.7试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表(ai,a2,,,,,a»)逆置为(a[】,an-i,ai)°【解答】(1)用ー维数组作为存储结构voidinvert(SeqList礼,int*num)intj;ElemTypetmp;for(j=0;j<=(*num-l)/2;j++)(tmp=L[j];L[j]=L[*num-j-l];L[*num-j-l]=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=(al,a2,……am),B=(bl,b2,……bn)合并成线性表C,C=(al,bl, am,bm,bm+1, bn)当mく=n时»或C=(al,bl, 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(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章限定性线性表ー栈和队列习题按图3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度，回答:(1)如进站的车厢序列为123，则可能得到的出站车厢序列是什么?123、213、132、231'321(312)(2)如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。(即写出以飞”表示进栈、以“X”表示出栈的栈操作序列)。SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X6设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步操作:输出队首元素;把队首元素值插入到队尾;删除队首元素;再次删除队首元素。直到队列成为空队列为止，则是否可能得到输出序列:A'C'E'C'C (2)A'C'EA'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)给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满?按照四则运算加、减、乘、除和寡运算(f)优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程:A-B*C/D+EtF试写ー个算法，判断依次读入的ー个以为结束符的字母序列遥否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。例如，'a+b&b+a’是属该模式的字符序列，而‘1+3&3—1t则不是。［提示］:边读边入栈，直到&边读边出栈边比较，直到…….假设表达式由单字母变量和双目四则运算算符构成。试写ー个算法，将一个通常书写形式(中缀)且书写正确的表达式转换为逆波拦式(后缀)。［提示］:例:中缀表达式:a+b 后缀表达式:ab+中缀表达式:a+bxc 后缀表达式:abcx+中爆表达式:a+bxc-d 后缀表达式:abcx+d-中缀表达式:a+bxc-d/e 后缀表达式：abcx+de/-中缀表达式:a+bx(c-d)-e/f 后缀表达式:abcd-x+ef/-« 后缀表达式的计算过程:(简便)顺序扫描表达式，(1)如果是操作数，直接入栈;(2)如果是操作符op，则连续退栈两次，得操作数X,Y，计算XopY，并将结果入栈。» 如何将中缀表达式转换为后缀表达式?顺序扫描中缀表达式，(1)如果是操作数，直接输出;(2)如果是操作符op，则与栈顶操作符opi比较:如果op2>opl»则op2入栈;如果op?=opi,则脱括号;如果0P2くopi»则输出opi；.假设以带头结点的循环链表表示队列，并且只设ー个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。［提示］:参P.56P.70先画图.typedefLinkListCLQueue;intInitQueue(CLQueue*Q)intEnterQueue(CLQueueQ,QueueElementTypex)intDe1eteQueue(CLQueueQ,QueueE1ementType*x).要求循环队列不损失ー个空间全部都能得到利用,设置ー个标志域tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。[提示]:初始状态:frontニニ〇,rearニニ〇,tagニニ〇队空条件:front==rear,tagニニ〇队满条件:front==rear,tag==l其它状态:front!=rear,tag==O(或1、2)入队操作:…(入队)if(front==rear)tag二1；(或直接tag二1)出队操作:…(出队)tag二。;[问题]:如何明确区分队空、队满、非空非满三种情况?.简述以下算法的功能(其中栈和队列的元素类型均为int)：voidproc_l(StackS)(iinti,n,A[255];n=0;while(!EmptyStack(S))(n++;Pop(&S,&A[n]);)for(i=l;i<=n;i++)Push(&S,A[i]);将栈S逆序。voidproc_2(StackS,inte)StackT;intd;lnitStack(&T);while(!EmptyStack(S))(Pop(&S,&d);if(d!=e)Push(&T,d);}while(JEmptyStack(T))(Pop(&T,&d);Push(&S,d);})删除栈S中所有等于e的元素。voidproc_3(Queue*Q)(StackS;intd;lnitStack(&S);while(!EmptyQueue(*Q))(DeleteQueueCQ,&d);Push(&S,d);)while(!EmptyStack(S))(Pop(&S,&d);EnterQueue(Q，d)将队列Q逆序。实习题1•回文判断。称正读与反读都相同的字符序列为“回文”序列。试写ー个算法，判断依次读入的ー个以为结束符的字母序列，是否为形如‘序列1&序列2'模式的字符序列。其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。例如，'a+b&b+a'是属该模式的字符序列，而‘1+3&3-1’则不是。2・停车场管理。设停车场是ー个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若车场已停満n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。当停车场某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。试编写程序，模拟上述管理过程。要求以顺序栈模拟停车场，以链队列模拟便道。从终端读入汽车到达或离去的数据，每组数据包括三项:①是“到达"还是"离去"；②汽车牌照:③“到达”或“离去”的时刻。与每组输入信息相应的输出信息为:如果是到达的车辆，则输出其在停车场中或便道上的位置;如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。（提示:需另设ー个栈，临时停放为让路而从车场退出的车»）车库暂时退车道 疝便道3•商品货架管理。商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。用队列和栈作为周转，实现上述管理过程。第三章答案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(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)顺序栈 (top用来存放栈顶元素的下标)判断栈S空:如果S->top==-l表示栈空。判断桟S満:如果S->top==Stack_Size-1表示栈満。(2)链栈(top为栈顶指针，指向当前栈顶元素前面的头结点)判断栈空:如果top->next==NULL表示栈空。判断栈满:当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。照四则运算加、减、乘、除和赛运算的优先惯例，画出对下列表达式求值时操作数栈和运算符栈的变化过程:A-B*C/D+EtF【解答】写ー个算法，判断依次读入的ー个以为结束符的字母序列，是否形如‘序列1&序列2'的字符序列。序列1和序列2中都不含‘&'，且序列2是序列1的逆序列。例如，’a+b&b+a'是属于该模式的字符序列，而‘1+3&3-1,则不是。【解答】算法如下:intIsHuiWenOStack*S;Charch,temp;InitStack(&S);Printf("\n请输入字符序列:");Ch=getchar();/・/・序列1入栈*/Push(&S,ch);ch=getchar();}do /・判断序列2是否是序列1的逆序列・/(ch=getchar();Pop(&S,&temp);if(ch!=temp) /・序列2不是序列1的逆序列・/(return(FALSE);printf("\nN0”);)}while(ch!=&&!IsEmpty(&S))if(ch== &&IsEmpty(&S)){return(TRUE);printf("\nYES");} /・序列2是序列1的逆序列・/else{return(FALSE);printf("\nN0");}}/*IsHuiWen()*/3.8要求循环队列不损失ー个空间全部都能得到利用，设置ー个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。【解答】入队算法:intEnterQueue(SeqQueue*Q,QueueE1ementTypex){/・将元素x入队米/if(Q->front==Q->front&&tagニニ1) /・队满・/return(FALSE);if(Q->front==Q->front&&tag==0) /*x入队前队空，x入队后重新设置标志tag=l;Q->e1ememt[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE; /*设置队尾指针*/Return(TRUE);}出队算法:intDeleteQueue(SeqQueue*Q,QueueE1ementType*x){/米删除队头元素，用x返回其值*/if(Q->front==Q->rear&&tag==O)/米队空米/return(FALSE);*x=Qー)element[Q->front];Q->front=(Q->front+l)%MAXSIZE; /*重新设置队头指针*/if(Q->front==Q->rear)tag=0; /*队头元素出队后队列为空，重新设置标志域:/Return(TUUE);}编写求解Hanoi问题的算法，并给出三个盘子搬动时的递归调用过程。【解答】算法:voidhanoi(intn,charx,chary,charz){/・将塔座X上按直径由小到大且至上而下编号为1至リn的n个圆盘按规则搬到塔座Z上，Y可用做辅助塔座"/if(n==1)move(x,1,z);else{Hanoi(n-l,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)Move(A->B)Hanoid,C,A,B)move(C->B)1号搬到B3号搬至リ3号搬至リCHanoi(2,B,A,C)Hanoi(1,B,C,A) move(B->A)1号搬到AMove(B->C)Hanoi(1,A,B,C)move(A->C)习题.设s='IAMASTUDENT',t='GOOD',q='WORKER,。给出下列操作的结果:StrLength(s);SubStringCsubl,s,1,7);SubString(sub2,s,7,1)；Strlndex(s,'A',4);StrReplace(s,'STUDENT',q);StrCat(StrCat(subl,t),StrCat(sub2,q));［参考答案］StrLength(s)=14;subl="IAMA_*;sub2='_*;Strlndex(s,'A',4)=6;StrReplace(s,'STUDENT',q)='IAMAWORKER';StrCat(StrCat(subl,t),StrCat(sub2,q))='IAMAGOODWORKER';.编写算法，实现串的基本操作StrReplace(S,T,V)。.假设以块链结构表示串，块的大小为1，且附设头结点。试编写算法，实现串的下列基本操作:StrAsignCS,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；StrCat(S,T)；SubString(Sub,S,pos,len)°［说明］:用单链表实现。.叙述以下每对术语的区别:空串和空格串;串变量和串常量;主串和子串;串变量的名字和串变量的值。.已知：S="(xyz)*",T="(x+z)*y"。试利用联接、求子串和置换等操作，将S转换为T..S和T是用结点大小为1的单链表存储的两个串，设计ー个算法将串S中首次与T匹配的子串逆置。.S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除!en个字符。以下算法用定长顺序串:.写下列算法:(1)将顺序串r中所有值为chi的字符换成ch2的字符。(2)将顺序串r中所有字符按照相反的次序仍存放在r中。(3)从顺序串r中删除其值等于ch的所有字符。(4)从顺序串rl中第index个字符起求出首次与串r2相同的子串的起始位置。(5)从顺序串r中删除所有与串rl相同的子串。.写ー个函数将顺序串si中的第i个字符到第j个字符之间的字符用s2串替换。［提示］:(1)用静态顺序串(2)先移位，后复制.写算法，实现顺序串的基本操作StrCompare(s,t)°.写算法，实现顺序串的基本操作StrReplace(&s,t,v)。［提示］:(1)被替换子串定位(相当于第9题中i)(2)被替换子串后面的字符左移或右移(为替换子串准备房间)(3)替换子串入住(复制)(4)重复上述，直到……第四章答案4.I设s='1AMASTUDENT'，t='GOOD"，q='WORKER,。给出下列操作的结果:【解答】StrLength(s)=14;SubString(subl,s,1,7) subl='IAMA';SubString(sub2,s,7,1) sub2='';Strlndex(s,4,'A')=6;StrReplace(s,'STUDENT',q); s='IAMAWORKER,;StrCat(StrCat(subl,t),StrCat(sub2,q))subl='IAMAGOODWORKER,。4.2编写算法，实现串的基本操作StrReplace(S,T,V)。【解答】算法如下:intstrRep1ace(SStringS,SStringT,SStringV){/・用串V替换S中的所有子串T*/intpos,i;pos=strIndex(S,1,T);/*求S中子intpos,i;pos=strIndex(S,1,T);/*求S中子串T第一次出现的位置*/if(pos==0)return(O);while(pos!=0)/