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

该【南邮数据结构作业答案讲解 】是由【1485173816】上传分享，文档一共【47】页，该文档可以免费在线阅读，需要了解更多关于【南邮数据结构作业答案讲解 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。(3)for(inti=1;i<=n;i++) for(intj=1;j<=i;j++) for(intk=1;k<=j;k++) x++;划线语句的执行次数为n(n+1)(n+2)/6,渐近时间复杂度为O(n3)(4)x=n;y=0; while(x>=(y+1)*(y+1))y++;划线语句的执行次数为?n1/2?,渐近时间复杂度为O(n1/2)2024/4/1612-(A[i][j][k])=134+(i*n*p+j*p+k)*2第二章****题讲解2024/4/1622-,设计一个算法,将原数组中的元素以逆序排列voidInvert(Telements[],intlength) //length数组长度 //elements[]为需要逆序的数组{Te;for(inti=1;i<length/2;i++){e=elements[i-1];elements[i-1]=elements[length-i];elements[length-i]=e;}}2024/4/1632-,将单链表中结点以逆序排列。逆序的单链表中的结点均为原表中的结点。 Node*pInvert(Node*first) { Node*p=first,*q; first=NULL; while(p) { q=p->Link;p->Link=first; first=p;p=q; } returnfirst; }2024/4/1643-,B,C,D,E五个元素依次进栈(进栈后可立即出栈),问能否得到下列序列。若能得到,则给出相应的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();第三章****题讲解2024/4/1653-,B,C,D,E五个元素依次进栈(进栈后可立即出栈),问能否得到下列序列。若能得到,则给出相应的push和pop序列;若不能,则说明理由。(2)A,C,E,B,D(2)不能得到该序列,在E出栈时,B和D在栈中,B比D先进栈,所以D应比B先出栈。第三章****题讲解2024/4/166(3)不能得到该序列,在C出栈时,A和B在栈中,A比B先进栈,所以B应比A先出栈。3-,B,C,D,E五个元素依次进栈(进栈后可立即出栈),问能否得到下列序列。若能得到,则给出相应的push和pop序列;若不能,则说明理由。(3)C,A,B,D,E2024/4/167(4)能得到该序列。相应的push和pop序列为:push(A);push(B);push(C);push(D);push(E);pop();pop();pop();pop();pop();3-,B,C,D,E五个元素依次进栈(进栈后可立即出栈),问能否得到下列序列。若能得到,则给出相应的push和pop序列;若不能,则说明理由。(4)E,D,C,B,A2024/4/168第四章****题讲解4-,并假定顺序表是有序的(设表中元素已按非递减次序排列)。编写函数,实现线性表的如下运算:(1)intSearch_Insert(List*lst,Tx) 后置条件:在有序的顺序表中搜索元素x。若x在表中,则返回x在表中的位置。否则,若表未满,则在表中插入新元素x,并且插入后,线性表仍然是有序的,返回新元素x的位置;若表已满,无法插入新元素,则返回-1。2024/4/169intSearch_Insert(List*lst,Tx){inti,j;for(i=0;(x>lst->Elements[i])&&(i<lst->Size);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[i]=x; //++;returni; //插入新元素并返回该元素的位置}①②③2024/4/1610