数据结构的第4-7习题的答案

, , , , , ,*, , , , , , ,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,单击幻灯片,*,线性结构,操作受限的线性表：栈、队列,线性结构线性表,数据元素受限的线性表：串,线性表回顾,第四章线性表知识要点：,1,、线性表类型的定义：（,a1,a2,an,）,2,、线性表的存储形式：顺序存储和链式存储方式，以及,各自的优缺点,顺序存储：,连续存储单元存储，分静态和动态,2,种,链式存储：,单链表、静态链表、双链表、循环链表,3,、线性表的应用：一元多项式相加,第四章 习题,4.2,请给出下述要求的判断条件：,（,1,）以,head,为头指针、不带头结点的单链表为空的条件是什么？不为空的条件是什么？,为空：,head=NULL;,不为空：,head!=NULL;,(2),以,head,为头指针、带头结点的单链表为空的条件是什么？不为空的条件是什么？,为空：,head-next=NULL;,不为空：,head-next!=NULL;,(3),以,head,为头指针、不带头结点的单链环为空的条件是什么？不为空的条件是什么？,为空：,head=NULL;,不为空：,head!=NULL;,(4),以,head,为头指针、带头结点的单链环为空的条件是什么？不为空的条件是什么？,为空：,head-next=head;,不为空：,head-next!=head;,4.2,请给出下述要求的判断条件：,（,5,）以,head,为头指针、不带头结点的单链表仅含有两个结点的条件是什么？,head-next-next=NULL,；,(6),以,head,为头指针、带头结点的单链表仅含有两个结点的条件是什么？,head-next-next-next=NULL,；,(7),以,head,为头指针、不带头结点的单链环仅含有两个结点的条件是什么？,head-next-next=head,；,(8),以,head,为头指针、带头结点的单链环仅含有两个结点的条件是什么？,head-next-next-next=head,；,4.3,在长度为,n,的顺序表上进行插入运算，有几个可插入的位置？在第,i,（假设合法）个位置上插入一个数据元素，需要向什么方向平移多少个数据元素？在长度为,n,的顺序表上进行删除运算，有几个可删除的数据元素？删除第,i,（假设合法）个位置上的数据元素，需要向什么方向平移多少个数据元素？,长度为,n,有,n+1,个插入位置,第,i,个位置上插入，需向右移动,n-i+1,个数据元素,长度为,n,，有,n,个删除位置,第,i,个位置上删除，需向左移动,n-i,个数据元素,4.4,根据图示回答下面的问题：,（,1,）如何访问,p,结点的数据域？,P-data,（,2,）如何访问,p,结点的直接前驱结点的数据域？,P-prior-data,（,3,）如何访问,p,结点的直接后继结点的数据域？,P-next-data,4.5,对于以,head,为头指针的不带头结点的双链环而言，如何判断,p,指针所指结点是否为尾元结点？如何判断,p,指针所指结点是否为首元结点？对于以,head,为头指针的带头结点的双链环而言情况又如何？,不带头结点 判断尾元,p-next ?= head,判断首元,p ?= head,带头结点 判断尾元,p-next ?= head,判断首元,p ?= head-next,4.6,若线性表中的数据元素以值递增有序排列（数据元素的类型为整数类型），且用带头结点的单链表存储。试写出一个高效算法删除表中所有值大于,min,且小于,max,的数据元素（表中有这样的数据元素时），并说明该算法的时间复杂度。（说明：,min,和,max,是给定的两个参变量，可以设定为任意的整数值。）,Void Delete(LinkList head), LinkList p,q;,p=head;,while(p-next!=NULL),if(p-next-datanext-datamin),q=p-next; p-next=q-next;free(q);,else,p=p-next;,4.8,若有一个以,head,为头指针的带头结点的单链表，结点数据域值属于整数类型。现将其数据域值除以,3,，得余数,0,1,2,。试按这,3,种不同的情况，把原有的链表分解成,3,个不同的单链表，且只增设两个头结点空间，不允许另辟空间。写出一个算法实现上述要求，并且要求头结点的数据域记录该链表中的数据结点数目。,void decomposition(LinkList ah,LinkList &bh,LinkList &ch),int k,num0=0,num1=0,num2=0;,LinkList pa,pb,pc,q;,pa=ah;,bh=(LNode *)malloc(sizeof(LNode);,ch=(LNode *)malloc(sizeof(LNode);,bh-next=NULL;ch-next=NULL;pb=bh;pc=ch;,while(pa-next!=NULL),if(pa-next-data%3=0) k=0;,else if(pa-next-data%3=1) k=1;,elsek=2;,switch(k),case 0:pa=pa-next;num0+;break;,case 1:q=pa-next;pa-next=q-next;q-next=pb-next;,pb-next=q;pb=q;num1+;break;,case 2:q=pa-next;pa-next=q-next; q-next=pc-next;,pc-next=q; pc=q;num2+ break;,ah-data=num0;bh-data=num1;ch-data=num2;,4.9,设有一个不带头结点的单链表，其结点的值均为整数，并按绝对值从小到大链接。试将该单链表改造为结点按绝对值从大到小进行链接。不允许另辟空间，写出一个算法实现上述要求。,*,A,&,C,3,E,head,1,$,D,p,q,r,q,p=NULL,r,r=NULL,q,p,Void invert(LinkList &head), linklist p,q,r;,p=r=NULL;,q=head;,while(q!=NULL),r=q-next;,q-next=p;,p=q;,q=r;,head=p;,4.10,线性表有两种存储结构，即顺序表和单链表。试问：,（,1,）若有,N,个线性表同时并存，且在处理过程中各表长度会动态发生变化，线性表的总数也会自动地改变，在此情况下应选用哪种存储结构？为什么？,应采用链式存储结构，因为采用链式存储时插入删除操作不需要移动数据元素,（,2,）若线性表的总数基本稳定，且很少进行插入和删除操作，但要以最快的速度存取表中元素，那么应采用哪种存储结构？为什么？,应采用顺序存储结构，因为采用顺序存储时可以随机存取，提高存取表中元素的速度。,栈回顾,第五章栈知识要点：,1,、栈类型的定义：（,a1,a2,an,），只在栈顶进行插删操作，先进后出。,2,、栈的存储形式：,顺序存储：,链式存储：,3,、栈的应用：表达式求值,5.2,设计一个算法，判断某输入字符串是否具有中心对称关系，例如,ababbaba,，,baxzxab,皆具有中心对称性（具有中心对称性的字符串称为回文）。,思路：采用顺序栈解决。,void judge( ),SqStack S;,InitStack(,char e1;int i=0;,cout“,请输入字符串：,”;,c=getchar( );,while(c!=#) Push(S,c);c=getchar( );,n=S.top+1;,while(in/2), Pop(S,e1);,if(e1!=S.datai) cout“,不是回文！,”,;return;,i+;,cout0,时,式中，,n,为正整数。写出它的递归算法。,Int f(int n),if(n=0) return 1;,return n*f(int(n/2);,5.8,写出下列程序的输出结果。（说明：该程序中用到的栈,S,是数据元素为,char,类型的栈。）,Void main(), stack S;,char x,y;,InitStack(S);,x=c;,y=y;,push(S,x);,push(S,n);,push(S,y);,pop(S,x);,push(S,a);,push(S,x);,pop(S,x);,push(S,n);,While(!StackEmpty(S),pop(S,y);,printf(“%c”,y);,printf(“%c”,x);,结果：,nancy,5.9,已知一个栈,S,的输入序列为,abcd,，下面两个序列是否能通过栈的,push,和,pop,操作输出？如果能，请写出操作序列；如果不能，请说明原因。（,x,表示入栈，,s,表示出栈）,（,1,）,dbca,； （,2,）,cbda,。,（,1,）不能,（,2,）,xxxssxss,5.10,写一个算法将给定十进制数转换为二进制数。,void conversion(),initstack(s);/,初始化一个空栈,cinn;/,输入要转换的十进制整数,n,while(n)/,当,n,不为,0,时执行,push(s,n%2); n=n/2; /,余数进栈,while(!stackempty(s)/,当栈不为空时进行,pop(s,e); coute;,while(e!= and e!=#) push(s,e); cine;,if (e=#) return 0;,cine;,while(e!=#) if(StackEmpty(s) return 0; pop(s,c); if(e!=c) return 0;,cine;,if(!StackEmpty(s) return 0; return 1;,/IsReverse,队列回顾,第六章队列知识要点：,1,、队列类型的定义：（,a1,a2,an,），只在队首进行删除操作，在队尾进行插入操作，先进先出。,2,、队列的存储形式：,链式存储：,顺序存储：循环队列,6.1,循环队列的优点是什么？如何判别它的空和满？,由于队列的顺序存储结构中从队尾入队、从队首出队，可能会造成存储空间实际未满，但又数据元素无法入队的情况，即虚溢出现象，而循环队列将整个队列看成一个环，则可以解决虚溢出问题。,对于循环队列,Q,，其存储空间大小为,MAXQSIZE,，则：,队空条件：,Q.front=Q.rear,队满条件：,(Q.rear+1)%MAXQSIZE=Q.front,6.2,设长度为,n,的链队列用循环单链表表示，若只设头指针，则入列操作、出列操作实现的时间开销是多少？若只设尾指针呢？,若只设头指针：入列、出列操作实现时间开销分别为,O(n),和,O(1),若只设尾指针：入列、出列操作实现时间开销分别为,O(1),和,O(1),6.4,用两个栈实现一个队列，并分析你的算法的时间复杂度。,思路：利用栈,S1,和,S2,模拟一个队列，其中,S1,栈用于插入元素，,S2,栈用于删除元素时辅助空间，每次删除元素时将,S1,栈的所有元素出栈并进栈到,S2,栈中。算法实现为：,Status EnQueue(stack &s1,ElemType x), if(S1.top=n-1) return 0;,else Push(s1,x); return 1;,时间复杂度,T(n)=O(1),Status DeQueue(stack &s1,Stack &s2,ElemType &x), ElemType y;,While(!StackEmpty(S1),Pop(S1,y); Push(S2,y);,Pop(S2,x);,While(!StackEmpty(S2),Pop(S2,y); Push(S1,y);,时间复杂度,T(n)=O(n),6.6,简述下列算法的功能（假设栈和队列的元素类型均为,int,类型）。,Void alg(Queue Q),stack S; int e; InitStack(S);,while(!QueueEmpty(Q) DeQueue(Q,e); push(S,e);,while(!StackEmpty(S) Pop(Q,e); EnQueue(S,e);,实现功能：将队列,Q,逆置。,串回顾,第七章串知识要点：,1,、串类型的定义：“,a1,a2,an”,2,、串的存储形式：,顺序存储：,堆存储：,链式存储：块链结构,7.2,已知：,S,1,= ”Im a girl.”,，,S,2,= ”girl”,，,S,3,= ” is very nice.”,，试求下列各运算的结果：,StrIndex(S,1, S,2,);,StrLength (S,1,);,Concat (S, S,2, S,3,),；,答：,StrIndex(S,1, S,2,)=7,StrLength (S,1,)=11,Concat (S, S,2, S,3,)=” girl is very nice.”,7.7,将串的各字符均相同且长度大于,1,的子串称为该串的一个等值子串。试写算法实现：输入字符串,S,，以,#,为结束符；如果串,S,中不存在等值子串，则输出“无等值子串”，否则输出串,S,的一个长度最大的等值子串。如，若,S,= “,abc345b6a7c,”,，则输出“无等值子串”；若,S =,“,abcaaabbac,”,，则输出,“,aaa,”,。,void EqSubString(char s),int i,j,k,head,max,count;,printf(“,请输入字符串：,”,);,for(k=0;k+) /,输入串,scanf(“%c”,for(i=0,j=1,head=0,max=1;si!=#i=j,j+),/,找等值子串,count=1;,while(si=sj) j+;count+;,if(countmax) head=i; max=count; ,if(max1),printf(“,最大等值子串：,”,);,for(k=head;k,S,2,则输出一个正数；若,S,1,=,S,2,，则输出,0,；若,S,1,top!=0,B,、,ST-top=0,C,、,sT-top!=m0,D,、,ST-top=m0-1,2,、判定栈,ST(,最多元素为,m0),为空的条件是,（）,A,、,Q-rear-Q-front=m0,B,、,Q-rear-Q-front-1=m0,C,、,Q-front=Q-rear,D,、,Q-front=Q-rear+1,3,、判定链队列,Q(,最多元素为,m0),为空的条件是,（）,A,、,Q-front=Q-rear,B,、,Q-front!=Q-rear,C,、,Q-front=(Q-rear+1)%m0,D,、,Q-front!=(Q-rear+1)%m0,4,、判定循环队列,Q(,最多元素为,m0),为空的条件是,（）,A,、,Q.rear=Q.front-next,B,、,Q.rear-next=Q.rear-next-next,C,、,Q.front-next=Q.front-next-next,D,、,Q.front=Q.rear-next,5,、在链队列,Q,中删除一结点需要执行的命令是,（）,B,C,C,A,C,一、选择题（下列各小题均有一个答案是正确的接上）,A,、,Q.front-next=s;f=s;,B,、,Q.rear-next=s;Q.rear=s;,6,、链队列,Q,中，若插入结点,s,需顺序执行的指令是,C,、,S-next=Q.rear;Q.rear=s;,D,、,S-next=Q.front;Q.front=s;,（）,A,、链头,B,、链中,C,、链尾,D,、不确定,7,、用单链表表示的链式队列 的队头在链表中,( ),位置,（）,A,、,AB-C+D/E*,B,、,ABC+D/E*-,C,、,ABCD/E*+-,D,、,ABCD/+E*-,8,、中缀表达式,A-(B+C/D)*E,的后缀表达式是,（）,A,、,Q-front=Q-rear,B,、,Q-front!=Q-rear,C,、,Q-front=(Q-rear+1)%m0,D,、,Q-front!=(Q-rear+1)%m0,9,、判定循环队列,Q(,最多元素为,m0),为满的条件是,（）,A,、,+*3-527,B,、,*,3-52+7,C,、*,+-3527,D,、*,3-+527,10,、,3*(5-2)+7,的前缀表达式是,（）,A,B,D,C,A,二、填空题（请用正确答案填充下列空白）,1,、向栈中压入元素的操作是先,_,后,_;,存入元素 移动栈顶指针,2,、循环队列中删除一个元素时则应该先,_,后,_,；,移动头指针 取元素,3,、在具有,N,个存储单元的循环队列中，队满时共有,_,个元素；,N-1,4,、在链队列,Q,中判定只有一个结点的条件是,_,；,Q.front-next=Q.rear,5,、栈,S,和队列,Q,的初始状态为空，元素,a,b,c,d,e,f,依次通过栈,S,，一个元,素出栈后即进入队列,Q,，若这,6,个元素出队列的顺序是,b,d,c,f,e,a,则栈,S,的容量至少应该是,_,；,3,6,、非空队列中，头指针始终指向,_,，而尾指针,则始终指向队列,_,元素的,_,一个位置；,队列头元素,尾 下,7,、栈和队列的共同特点 是,_,；,只允许在端点处进行插入和删除元素,8,、对不带头结点的链式队列，其队头指针指向队头结点，对尾指针指向队,尾结点，则进行出队操作时队头指针,_,修改，对尾指针,_,修,改，填写,(,要或不要或可能要,),；,可能要 可能要,三、阅读下列程序段，请说明这些程序段所描述的算法的功能。,(1) Status algol(stack s) (2) status algol2(stack s,int e), int i,n=0,a255; stack t; int d;,while(!stackempty(s) initstack(t);, n+; while(!stackempty(s),pop(s,an); pop(s,d);,for(i=1;i2,从栈,T,中出来后变为,3y-,*ay2/-,的操作步骤。,XSXXXSSSXXSXXSXXSSSS,(1) Int count (linklist HS), linklist p; p=HS;,while(p), n+; p=p-next;,return(n); ,1,、在栈顶指针为,HS,的链栈中，写出计算该链栈中结点个数的算法；,五、根据题意要求回答问题。,2,、为什么具有,N,个存储空间的循环队列满时整个队列只有,N-1,个元素？,(2),一般环状队列的头和尾其中之一要进行特殊处理，否则队空或满时只凭,Q.rear=Q.front,是无法判断的，一般处理方法是将,Q.rear,指向下一个要插入的位置，这样虽然牺牲了一个单元的存储空间，但很容易区分队列的空与满。,串补充习题,一、选择题（下列各小题均有一个答案是正确的）,1,、串是一种特殊的线性表，其特殊性表现在,( ),A,、可以顺序存储,B,、数据元素是一个字符,C,、可以链接存储,D,、数据元素可要是多个字符,2,、空串与空格串之间的关系是,( ),A,、相等的,B,、不相等的,C,、等值的,D,、无法确定的,3,、设,S=efghij,则,SubString(str,s,3,2),的值是,( ),A,、,ef B,、,ij,C,、,hi D,、,gh,4,、,S1=ABCDEFGS2=PQRST,则,subs(S1,2,len(S2),A,、,BCDEF B,、,BCDEFG,C,、,BCDE D,、,CDEFG,5,、同上,con(subs(S1,2,len(S2),subs(s1,len(S2),2),A,、,BCDEFEF B,、,BCDEF,C,、,BCDEFG D,、,BCDPQRST,（）,B,D,D,A,A,（）,（）,（）,（）,二、填空题（请用正确答案填充下列空白）,1、设S1=GOOD,S2= ,S3=BYE!则,con(con(S1,S2),S3,)=_,2、两个串相等的充分必要条件是：,_,3、S1=ABCDEFG,S2=9898,S3=#,S4=012345,则,Substr(M,S1,4,len(S3),=_,Replace(S1,M,S3)=,_,PP=index(s2,8)=,_,Substr(H,S4,pp,len(S2) =,_,Con(S1,H)=,_,GOOD BYE!,两串长度相等并且对应位置上字符相同,DEF,ABC#G,2,1234,ABC#G1234,三、根据题意要求问题,1、书籍下列字符串，(采用定长顺序存储结构),a=this,b= ,c=good,d=ne,f=a sample,g=is,则顺序执行以下各种操作：,s=Concat(a,Concat(Substr(f,2,7),Concat(b,Substr(a,3,2),;,t=Replace(f,Substr(f,3,6),c),;,u=Concat(Substr(c,3,1),d),;,v=Concat(s,Concat(b,Concat(t,Concat(b,u),;,问：s、t、u、v、len(s)、index(v,g)、index(u,g)分别是多少？,2、已知s=(xyz)+*,t=(x+z)*y,试利用连接(Con)、求子串(Subs)、,置换(Replace)等基本操作，将s转化为t。,s=this sample if,t= a good one,;,u=one,v=this sample is a good one;,len(s)=14,index(v,g)=3,index(u,g)=0,Subs(s1,s,1,5):(xyz);,Subs(s2,s,3,1):y;,Subs(s3,s,6,1):+;,Subs(s4,s,7,1):*;,Replace(s1,3,1,s3):(x+z);,Con(Con(s1,s4),s2):(x+z)*y,