2022年数据结构习题答案 .pdf

《2022年数据结构习题答案 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构习题答案 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章绪论一选择题1B D 2C A 3C 4D 5A 6A 7D 8D 二填空题1数据的逻辑结构、数据的存储结构、基本操作2集合、线性结构、树结构、图结构3n、2)1(nn、（n2）三算法分析题1功能：求n!时间复杂度：（n）2功能：求n!时间复杂度：（n2）四解答略第二章线性表一选择题1A 2B 3A 4D 5A 6C 7A 8B 9A 二、填空1物理位置相邻指针2直接前驱直接后继名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -3顺序链式三、算法设计1int count(Linklist h,int x)int num=0;Linknode*p;p=h-next;w

2、hile(p&p-datanext;while(p)if(p-next&p-data=p-next-data)p=p-next;else num+;p=p-next;return num;void delevenl(Linklist h,int x)Linknode*p,*r;p=h-next;r=h;while(p&p-datadata%2=0)r-next=p-next;free(p);p=r-next;else r=p;p=p-next;2void Inverse（Linklist&h）名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 7 页 -Linklist p,q;p=

3、h;h=null;while(p)q=p;p=p-next;q-next=h;h=q;3void merge(Linklist La,Linklist&Lb,Linklist&Lc)Linknode*p;Lc=new Lnode;Lc-next=NULL;p=La-next;Lb=La;Lb-next=NULL;while(p)La=p-next;if(p-data0)p-next=Lc-next;Lc-next=p;else p-next=Lb-next;Lb-next=p;p=La;4int insect(Linklist La,Linklist Lb)Linknode*p,*q;p=La

4、-next;while(p)q=Lb-next;while(q)if(p-data=q-data)break;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 7 页 -else q=q-next;if(!q)return 0;p=p-next;return 1;5void change(Dublist&h)DubLnode*p;p=h;while(p-next!=h)p-next-prior=p;p=p-next;h-prior=p;第三章栈和队列一、选择题1C 2C 3D 4C 5A 6C 7D 二填空题1线性任意位置栈顶队尾 对头2bceda 33 三解答题1#define

5、M 20 struct DStack Selemtype dataM;int top1,top2;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -;void InitStack(DStack&s)s.top1=0;s.top2=M-1;int IsEmpty(DStack s,int i)switch(i)case 0:return s.top1=0;case 1:return s.top2=M-1;int IsFull(DStack s)return s.top1s.top2;void Push(DStack&s,int i,Selemtype x)if(IsFull

6、(s)coutfullendl;return;switch(i)case 0:s.datas.top1=x;s.top1+;break;case 1:s.datas.top2=x;s.top2-;break;return;Selemtype Pop(DStack&s,int i)Selemtype e;if(IsEmpty(s,i)coutEmptyendl;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 7 页 -exit(-1);switch(i)case 0:s.top1-;e=s.datas.top1;break;case 1:s.top2+;e=s.datas.top2

7、;return e;2#define M 3 struct Stack Qelemtype dataM;int top;struct Queue Stack s1;Stack s2;void InitQueue(Queue&Q)Q.s1.top=0;Q.s2.top=0;int IsEmpty(Queue&Q)if(Q.s1.top=0&Q.s2.top=0)return 1;if(Q.s2.top=0&Q.s1.top!=0)while(Q.s1.top!=0)Q.s2.dataQ.s2.top+=Q.s1.data-Q.s1.top;return 0;int IsFull(Queue&Q)

8、if(Q.s1.top=M&Q.s2.top!=0)名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 7 页 -return 1;if(Q.s1.top=M&Q.s2.top=0)while(Q.s1.top!=0)Q.s2.dataQ.s2.top+=Q.s1.data-Q.s1.top;return 0;if(Q.s1.top!=M)return 0;void InQueue(Queue&Q,Qelemtype e)if(IsFull(Q)coutOVERFLOWendl;exit(-1);Q.s1.dataQ.s1.top+=e;void DeQueue(Queue&Q,Qelemtype&e)if(IsEmpty(Q)coutUNDERFLOWendl;exit(-1);e=Q.s2.data-Q.s2.top;3功能：借助栈将队列Q 中的元素逆置队列 Q 的值：Q=8，4，25，34，12 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -