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

《数据结构的第4-7习题的答案.ppt》由会员分享，可在线阅读，更多相关《数据结构的第4-7习题的答案.ppt（37页珍藏版）》请在三一办公上搜索。

1、线性结构,操作受限的线性表：栈、队列 线性结构线性表 数据元素受限的线性表：串,线性表回顾,第四章线性表知识要点：1、线性表类型的定义：（a1,a2,an）2、线性表的存储形式：顺序存储和链式存储方式，以及各自的优缺点 顺序存储：连续存储单元存储，分静态和动态2种 链式存储：单链表、静态链表、双链表、循环链表3、线性表的应用：一元多项式相加,第四章 习题,4.2请给出下述要求的判断条件：（1）以head为头指针、不带头结点的单链表为空的条件是什么？不为空的条件是什么？为空：head=NULL;不为空：head!=NULL;(2)以head为头指针、带头结点的单链表为空的条件是什么？不为空的条件

2、是什么？为空：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为头指针、带头结点的单链表仅含有两个结点的条件是什么？hea

3、d-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个位置上插入，需向右

4、移动n-i+1个数据元素长度为n，有n个删除位置第i个位置上删除，需向左移动n-i个数据元素,4.4根据图示回答下面的问题：（1）如何访问p结点的数据域？P-data（2）如何访问p结点的直接前驱结点的数据域？P-prior-data（3）如何访问p结点的直接后继结点的数据域？P-next-data4.5对于以head为头指针的不带头结点的双链环而言，如何判断p指针所指结点是否为尾元结点？如何判断p指针所指结点是否为首元结点？对于以head为头指针的带头结点的双链环而言情况又如何？不带头结点 判断尾元 p-next?=head 判断首元 p?=head带头结点 判断尾元 p-next?=hea

5、d 判断首元 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;,

6、4.8 若有一个以head为头指针的带头结点的单链表，结点数据域值属于整数类型。现将其数据域值除以3，得余数0,1,2。试按这3种不同的情况，把原有的链表分解成3个不同的单链表，且只增设两个头结点空间，不允许另辟空间。写出一个算法实现上述要求，并且要求头结点的数据域记录该链表中的数据结点数目。,void decomposition(LinkList ah,LinkList,4.9 设有一个不带头结点的单链表，其结点的值均为整数，并按绝对值从小到大链接。试将该单链表改造为结点按绝对值从大到小进行链接。不允许另辟空间，写出一个算法实现上述要求。,head,p,q,r,q,p=NULL,r,r=NU

7、LL,q,p,Void invert(LinkList,4.10 线性表有两种存储结构，即顺序表和单链表。试问：（1）若有N个线性表同时并存，且在处理过程中各表长度会动态发生变化，线性表的总数也会自动地改变，在此情况下应选用哪种存储结构？为什么？应采用链式存储结构，因为采用链式存储时插入删除操作不需要移动数据元素（2）若线性表的总数基本稳定，且很少进行插入和删除操作，但要以最快的速度存取表中元素，那么应采用哪种存储结构？为什么？应采用顺序存储结构，因为采用顺序存储时可以随机存取，提高存取表中元素的速度。,栈回顾,第五章栈知识要点：1、栈类型的定义：（a1,a2,an），只在栈顶进行插删操作，先

8、进后出。2、栈的存储形式：顺序存储：链式存储：3、栈的应用：表达式求值,5.2 设计一个算法，判断某输入字符串是否具有中心对称关系，例如ababbaba，baxzxab皆具有中心对称性（具有中心对称性的字符串称为回文）。思路：采用顺序栈解决。void judge()SqStack S;InitStack(,5.5 已知函数F(n)=n+1 当n=0时 n*F(n/2)当n0时 式中，n为正整数。写出它的递归算法。Int f(int n)if(n=0)return 1;return n*f(int(n/2);,5.8 写出下列程序的输出结果。（说明：该程序中用到的栈S是数据元素为char类型的栈

9、。）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

10、）不能（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;,5.11写一算法识别依次读入的一个以#为结束符的字符序列是否是形如“序列1序列2”的字符序列。其中，序列1和序列2中都不含有字符，且序列2是序列1的逆序列。例如“aab*cdaadc*baa”是满足条件的字符序列。,int Is

11、Reverse()/判断输入的字符串中前和后部分是否为逆串,是则返回1,否则返回0InitStack(s);char e;cine;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、队列的

12、存储形式：链式存储：顺序存储：循环队列,6.1 循环队列的优点是什么？如何判别它的空和满？由于队列的顺序存储结构中从队尾入队、从队首出队，可能会造成存储空间实际未满，但又数据元素无法入队的情况，即虚溢出现象，而循环队列将整个队列看成一个环，则可以解决虚溢出问题。对于循环队列Q，其存储空间大小为MAXQSIZE，则：队空条件：Q.front=Q.rear队满条件：(Q.rear+1)%MAXQSIZE=Q.front6.2 设长度为n的链队列用循环单链表表示，若只设头指针，则入列操作、出列操作实现的时间开销是多少？若只设尾指针呢？若只设头指针：入列、出列操作实现时间开销分别为O(n)和O(1)若

13、只设尾指针：入列、出列操作实现时间开销分别为O(1)和O(1),6.4 用两个栈实现一个队列，并分析你的算法的时间复杂度。思路：利用栈S1和S2模拟一个队列，其中S1栈用于插入元素，S2栈用于删除元素时辅助空间，每次删除元素时将S1栈的所有元素出栈并进栈到S2栈中。算法实现为：Status EnQueue(stack 时间复杂度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);whil

14、e(!StackEmpty(S)Pop(Q,e);EnQueue(S,e);实现功能：将队列Q逆置。,串回顾,第七章串知识要点：1、串类型的定义：“a1,a2,an”2、串的存储形式：顺序存储：堆存储：链式存储：块链结构,7.2已知：S1=”Im a girl.”，S2=”girl”，S3=”is very nice.”，试求下列各运算的结果：StrIndex(S1,S2);StrLength(S1);Concat(S,S2,S3)；答：StrIndex(S1,S2)=7StrLength(S1)=11Concat(S,S2,S3)=”girl is very nice.”,7.7 将串的各字

15、符均相同且长度大于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”,7.8 试编写一个算法，将两个字符串S1和S2进行比较，若S1 S2则输出一个正数；若S1=S2，则输出0；若S1 S2则

16、输出一个负数（要求：不允许利用C的库函数strcpy）。int CmpString(char s1,char s2)int i=0;while(s1i=s2i),栈和队列补充习题,一、选择题（下列各小题均有一个答案是正确的）,B,C,C,A,C,一、选择题（下列各小题均有一个答案是正确的接上）,A,B,D,C,A,二、填空题（请用正确答案填充下列空白）,1、向栈中压入元素的操作是先_后_;,存入元素 移动栈顶指针,2、循环队列中删除一个元素时则应该先_后_；,移动头指针 取元素,3、在具有N个存储单元的循环队列中，队满时共有_个元素；,N-1,4、在链队列Q中判定只有一个结点的条件是_；,Q.

17、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、对不带头结点的链式队列，其队头指针指向队头结点，对尾指针指向队 尾结点，则进行出队操作时队头指针_修改，对尾指针 _修 改，填写(要或不要或可能要)；,可能要 可能要,三、阅读下列程序段，请说明这些程序段所描述的

18、算法的功能。,(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;i=n;i+)if(d!=e)push(s,ai);push(t,d);while(!stackempty(t)pop(t,d);push(s,d);,(1)的功能：利用栈t将数组a中的元素逆置,(2)的功能：利用栈t将栈s中的数据e删除,四、假设用X

19、代表扫描该字符串函数，并顺序取一字符进栈的操作，用S代表从栈中取出一个字符加到新字符串尾的出栈的操作，试用X和S的组合写出字符串3*-y-a/y2从栈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)一般环状队列的头和尾其中之一要进行特殊处理，否则队空

20、或满时只凭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、gh4、S1=ABCDEFGS2=PQRST,则sub

21、s(S1,2,len(S2)A、BCDEF B、BCDEFG C、BCDE D、CDEFG5、同上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)=_,Repla

22、ce(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(S

23、ubstr(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,