《数据结构》各章课后作业答案.doc

《《数据结构》各章课后作业答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》各章课后作业答案第一章绪论课后作业答案1.简述线性结构与非线性结构的不同点。答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。2．分析下面各程序段的时间复杂度（每小题5分，共20分）（2）s=0;for（i=0;i

2、j<=n-i;j++)x++;(4)i=1;while(i<=n)i=i*3;解：1.第一个for循环执行n+1次，第二个for循环执行n(m+1)次，A[i][j]=0;语句执行n*m次，此程序段总的执行次数为n+1+n*(m+1)+n*m=2nm+2n+1次。故时间复杂度为O(n*m)。2.算法的时间复杂度是由嵌套最深层语句的执行次数决定的，本程序段嵌套最深层语句为：s+=B[i][j];它的执行次数为n2，所以本程序段的时间复杂度是O(n2)。3.该算法的基本操作是语句x++,其语句频度为：==所

3、以本程序段的时间复杂度是O(n2)。4.设语句执行m次，则有3m≤nÞm≤log3n所以本程序段的时间复杂度为O(log3n)。第二章线性表课后作业答案1.填空题。（1）在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。（2）线性表中结点的集合是有限的，结点间的关系是一对一的。（3）向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1个元素。（4）顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的

4、元素的物理位置不一定相邻。2.试写一算法，对单链表实现就地逆置。分析：将单链表就地逆置，即不另外开辟结点空间，而将链表元素翻转顺序。解：从链上依次取下结点，按照逆序建表的方法重新建表。voidReverse(LinkList&L){p=L->next;//原链表L->next=NULL;//新表(空表)while(p){//从原链表中取下结点ss=p;p=p->next;//插入L新表表头s->next=L->next;L->next=s;}}第三章栈和队列课后作业答案1、填空题。（1）栈是一种特殊的线

5、性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。（2）队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。（3）在具有n个单元的循环队列中，队满时共有n-1个元素。2．计算题。设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？解：用队列长度计算公式：(N＋r－f)%N①L=(40＋19－11)%40=8②L=(4

6、0＋11－19)%40=323.写出下列程序段的输出结果（栈的元素类型SElemType为char）。voidmain(){StackS;charx,y;InitStack(S);x=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);Push(S,’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);}printf(x);}答：输出结果为“stack”。

7、第四章串课后作业答案1．算法填空题。本算法是在S中找子串t。若找到。则返回子串t第一次出现在主串s中的位置，否则返回-1。intindex(chars[],chart[]){inti=0,j=0;while(①){if(s[i+j]==t[j])j++;else{②;③;}}if(④)retruni;elsereturn–1;}解：可以参照课本上模式匹配算法中的BF算法思想。答案为：①i=strlen(t)2．写出子串t=”ABCABC

8、ACAB”的next值和nextval值。解：j12345678910模式串ABCABCACABnext[j]0111234512nextval[j]0110110501第五章数组和广义表课后作业答案1、选择题。（1）设数组a[1..60,1..70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950。解：不考虑0行0列，利用列优先公式：LOC(aij)=LOC(ac1，c2)+[