南邮数据结构课后习题答案讲解.ppt

南邮数据结构课后习题答案讲解.ppt

ID:55818610

大小:318.00 KB

页数:49页

时间:2020-06-08

南邮数据结构课后习题答案讲解.ppt_第1页
南邮数据结构课后习题答案讲解.ppt_第2页
南邮数据结构课后习题答案讲解.ppt_第3页
南邮数据结构课后习题答案讲解.ppt_第4页
南邮数据结构课后习题答案讲解.ppt_第5页
资源描述:

《南邮数据结构课后习题答案讲解.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)9/26/202122-4.Loc(A[i][j][k])=134+(i*n*p+j*p+k)*2第二章习题讲解9/26/202132-9.设有长度为n的一维整型数组A,设计一个算法,将原数组中的元素以逆序排列voidInvert(Telements[],intlength)//length数组长度//elements[]为需要逆序的数组{Te;for(inti=1;i

3、ents[i-1];elements[i-1]=elements[length-i];elements[length-i]=e;}}9/26/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;}9/26/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();第三章习题讲解9/26/202163-1.设A,B,C,D,E五个元素依次进栈(进栈后可立即出栈),问能否得到下列序列。若能得到,则给出相应的push和pop序列;若不能,则说明理由。(2)A,C,E,B,D(2)不能得到该序列,在E出栈时,B和D在栈中,B比D先进栈,所以D应比B先出栈。第三章习题讲解

5、9/26/20217(3)不能得到该序列,在C出栈时,A和B在栈中,A比B先进栈,所以B应比A先出栈。3-1.设A,B,C,D,E五个元素依次进栈(进栈后可立即出栈),问能否得到下列序列。若能得到,则给出相应的push和pop序列;若不能,则说明理由。(3)C,A,B,D,E9/26/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,A9/26/20219第四章习题讲解4-1.设线性表采用顺序表示方式,并假定顺序表是有序的(设表中元素已按非递减次序排列)。编写函数,实现线性表的如下运算:(1)intSearch_Insert(List*lst,Tx)后置条件:在有序的顺序表中搜索元素x。若x在表中,则返回x在表中的位置。否则,若表未满,则在表中插入新元素x,并且插入后,线性表仍然是有序的,返回新元素x的位置;若表已满,无法插入新元素,则返回-1。9/26/202110intSearch_Insert(List*lst,

7、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[

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。