南邮_数据结构作业答案讲解.ppt

《南邮_数据结构作业答案讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章习题讲解1-19.确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。(1)i=1;k=0;do{k=k+10*i;i++;}while(i<=n-1)划线语句的执行次数为n-1,渐近时间复杂度为O(n)(2）i=1;x=0;do{x++;i=2*i;}while（i

2、,渐近时间复杂度为O(n3)(4）x=n;y=0;while(x>=(y+1)*(y+1))y++;划线语句的执行次数为n1/2,渐近时间复杂度为O(n1/2)8/14/202122-4．Loc(A[i][j][k])=134+(i*n*p+j*p+k)*2第二章习题讲解8/14/202132-9.设有长度为n的一维整型数组A，设计一个算法，将原数组中的元素以逆序排列voidInvert(Telements[],intlength)//length数组长度//elements[]为需要逆序的数组{Te;for(inti=1;i

3、ements[i-1];elements[i-1]=elements[length-i];elements[length-i]=e;}}8/14/202142-12.设计一个算法，将单链表中结点以逆序排列。逆序的单链表中的结点均为原表中的结点。Node*pInvert(Node*first){Node*p=first,*q;first=NULL;while(p){q=p->Link;p->Link=first;first=p;p=q;}returnfirst;}8/14/202153-1.设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。

4、若能得到，则给出相应的push和pop序列；若不能，则说明理由。（1）A，B，C，D，E（1）能得到该序列。相应的push和pop序列为：push(A);pop();push(B);pop();push(C);pop();push(D);pop();push(E);pop();第三章习题讲解8/14/202163-1.设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。（2）A，C，E，B，D（2）不能得到该序列，在E出栈时，B和D在栈中，B比D先进栈，所以D应比B先出栈。第三章

5、习题讲解8/14/20217（3）不能得到该序列，在C出栈时，A和B在栈中，A比B先进栈，所以B应比A先出栈。3-1.设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。（3）C，A，B，D，E8/14/20218（4）能得到该序列。相应的push和pop序列为：push(A);push(B);push(C);push(D);push(E);pop();pop();pop();pop();pop();3-1.设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列

6、序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。（4）E，D，C，B，A8/14/20219第四章习题讲解4-1.设线性表采用顺序表示方式，并假定顺序表是有序的（设表中元素已按非递减次序排列）。编写函数，实现线性表的如下运算：（1）intSearch_Insert(List*lst,Tx)后置条件：在有序的顺序表中搜索元素x。若x在表中，则返回x在表中的位置。否则，若表未满，则在表中插入新元素x，并且插入后，线性表仍然是有序的，返回新元素x的位置；若表已满，无法插入新元素，则返回-1。8/14/202110intSearch_Insert(Lis

7、t*lst,Tx){inti,j;for(i=0;(x>lst->Elements[i])&&(iSize);i++);//查找首个大于等于x的元素位置，并记录在i中if(lst->Elements[i]==x)returni;//x在表中时，返回x的位置if(IsFull(lst))//或if(lst->Size==lst->maxList)return-1;//表已满时，无法插入，返回-1for(j=lst->Size-1;j>=i;j--)lst->Element[j+1]=lst->Element[j];lst->Element[