《数据结构第三章到第九章练习题答案.docx》由会员分享，可在线阅读，更多相关《数据结构第三章到第九章练习题答案.docx（30页珍藏版）》请在课桌文档上搜索。
1、第三章栈和队列借助栈实现单链表上的逆置运算。/Stdafx.h#include#includettincludezztime.husingnamespacestd;结点类structLinkNodeintdata;1.inkNode*link;1.inkNode(constint&item,LinkNode*ptr=NULL)data=item;link=ptr;1.inkNode(LinkNode*ptr=NULL)link=ptr;；#Pragmaonce带附加头结点的单链表classList(public:1.ist(void);构造函数1.ist(constint&x);构造函数Lis
2、t(void);析构函数voidinput(intn);输入voidOUtPUt(VOid);输出voidmakcEmpty(void);清空voidinverse(void);逆转函数protected:1.inkNode*first;链表头指针；#Pragmaonceinclude.list.hclassstack(public:stack(void);“stack(VOid);protected:1.inkNode*top;friendclassList;public:voidPush(constint&x);boolPop();boolIsEmpty(void)return(top=N
3、ULL)?true:false;)；ItincludeStdAfx.hinclude”.list.hfusing1.ist:List(constint&x)(first=newLinkNode(x);)1.ist:List(void)(first=newLinkNode;)1.ist:List(void)(makeEmpty();)voidList:input(intn)(1.inkNode*newNode;first=newLinkNode;for(inti=0;i1ink=first-link;first-link=newNode;)voidList:output(void)(1.inkN
4、ode*current=first-link;while(current!=NULL)(coutdatalink;)coutlink!=NULL)p=first-link;first-link=p-link;deletep;)逆转函数voidList:inverse(void)(stacks;1.inkNode*p=first-link,*q;while(p!=NULL)(s.Push(p-data);p=p-link;)p=first-link;while(!s.IsEmptyO)(q=s.top;p-data=q-data;p=p-link;s.PopO;)includeStdAfx.hi
5、nclude”.stack.hfusingstack:stack(void):top(NULL)()stack:飞tack(void)()入栈voidstack:Push(constint&x)(top=newLinkNode(x,top);)出栈boolstack:Pop()(if(IsEmptyO-true)returnfalse;1.inkNode*p=top;top=top-link;deletep;returntrue;)includestdafx.hinclude.list.h#usingllusingnamespaceSystem;int_tmain()(srand(time(N
6、ULL);1.ist1;调用输入函数1.input(10);调用输出函数1.output();COUt调用逆转函数endl;1.inverse();调用输出函数1.output();return0;QB数据结构作业3新建文件夹逆转Debug实套exeHglX7662241调用逆转函数217205Pressanykey367907221?9364122676tocontinue编写一个算法，将一个非负的十进制整数N转换为另一个基为B的B进制数。/stdafx.h#include#includeusingnamespacestd;structLinkNodeintdata;1.inkNode*li
7、nk;1.inkNode(constint&item,LinkNode*ptr=NULL)(data=item;link=ptr;1.inkNode(LinkNode*ptr=NULL)link=ptr;)；#Pragmaonceclassstackpublic:stack(void);stack(void);voidPush(constint&x);boolPop(int&x);boolIsEmpty(void)return(top=NULL)?true:false;protected:1.inkNode*top;);WincludeStdAfx.hincludestack.hfusings
8、tack:stack(void):top(NULL)()stack:StaCk(VOid)()voidstack:Push(constint&x)(top=newLinkNode(x,top);)boolstack:Pop(int&x)(if(IsEmpty()=true)returnfalse;1.inkNode*p=top;top=top-link;x=p-data;deletep;returntrue;)#includestdafx.hinclude”.stack.hfusingusingnamespaceSystem;int_tmain()(intn,m,temp,yu;COUtn;C
9、OUtm;stack1;while(n!=O&m!=0)temp=n%m;n=nm;1.Push(temp);)while(!1.IsEmptyO)1.Pop(yu);coutyu;coutendl;return0;)试编写一个算法，求解最大公因数问题：在求两个正整数m和n的最大公因数常常使用辗转相除法，反复计算直到余数为零为止。其递归定义为：/stdafx.h#includeinclude#includeusingnamespacestd;intf(intnl,intn2);includezzstdafx.hfusingusingnamespaceSystem;int_tmain()intn
10、l,n2;COUtEnterthefirstpositivenumber:znl;coutzzEnterthesecondpositivenumber:zn2;if(nlO&n20)(coutnl和n2的最大公约数是：f(nl,n2)endl;)elseCoUt非法数据endl;returnO;)intf(intnl,intn2)(intt;while(n2!=0)(t=nl%112inl=n2;n2=t;)returnnl;)3.23假设以数组Qm存放循环队列中的元素，同时设置一个标志tag,以tag=O和tag=l来区别在对头指针(fr。IIt)和对尾指针(rear)相等时，队列状态为“空
11、”还是“满、试编写与此结构相应的插入(EnQueue)和删除(DeQlIelIe)算法。#includeItincludettincludeusingnamespacestd;#pragmaonceclassSeqQueuepublic:SeqQueue(intsize=10);SeqQucue(void);protected:intrear,front,tag;int*element;intmaxSize;public:boolEnQueue(constint&x);boolDeQueue(void);boolIsEmpty(void)return(front=rear&tag=0)?tru
12、e:false;boolIsFulKvoid)return(front=rear&tag=l)?true:false;friendOStreaoperator(ostream&os,SeqQueueftQ);；includeStdAfx.h#include”.SeqQeue.httusingSeqQueue:SeqQueue(intsize):rear(O),front(O),tag(O),maxSize(size)(element=newintmaxSize;SeqQucue:SeqQucue(void)deleteelement;)boolSeqQueue:EnQueue(constint
13、&x)if(IsFullO=true)returnfalse;elementrear=x;rear=(rear+l)%maxSize;tag=l;returntrue;)boolSeqQueue:DeQueue(void)if(IsEmpty()=true)returnfalse;front=(front+1)%maxSize;tag=0;returntrue;)Ostreamftoperator(ostream&os,SeqQueuefeQ)(intnum;if(Q.front=Q.rear&Q.tag=l)num=Q.maxSize;elsenum=(Q.rear-Q.front+Q.ma
14、xSize)%Q.maxSize;for(inti=0;inum;i+)os(i+Q.front)%Q.maxSize*:*Q.element(i+Q.front)%Q.maxSize,t,;returnos;)includestdafx.hinclude”.SeqQueue.hfusingusingnamespaceSystem;int_tmain()srand(time(NULL);SeqQueueq;coutz,CalltheEnQueuefunctio11z,endl;for(inti=0;i9;i+)(q.EnQueue(rand()%100);coutqendl;coutz,Cal
15、ltheDeQueuefunction”endl;q.DeQueue();q.DeQueue();coutqendl;returnO;e:数据结构作业3新建文件夹队列Debug作业le*eCalltheEnQueuefunction0:71:532:533：274:555：946:457:428:33CalltheDeQueuefunction2:533:274:555:946:457:428:33Pressanykeytocontinue二口 X第四章数组、串与广义表Am*n中的某一元素Aij是第i行中的最小值，同时又是第j列中的最大值，那么称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵
16、，试编写一个函数，确定鞍点在数组中的位置（假设鞍点存放在时），并分析该函数的时间复杂度。#include#includeusingnamespacestd;includestdafx.httincludefusingusingnamespaceSystem;int_tmain()intA1010,rsize,row,column,maxC,minD,max,min;srand(time(NULL);for(row=0;row10;row+)for(column=0;column10;column+)Arowcolumn=rand()%(100/(10-row)+100/(10-column);
17、coutArowcolumn,t,;for(rsize=0;rsize10;rsize+)minD=0;min=Arsize0;for(column=l;columnArsizecolumn)(IninD=Column;min=ArsizeminD;maxC=0;max=A0minD;for(row=1;row10;row+)if(maxArowminD)maxC=row;max=ArowminD;)if(max=min)CoUtArrayrsize+lminD+l是鞍点endl;)return0;时间复杂度分析：第二个for的嵌套循环是寻找鞍点的主要程序，假设数组Amn,那么第一、二个内嵌循
18、环时间代价分别为tl(n)=O(f(n)和t2(m)=O(g(m),外循环的时间复杂度为t(m)=O(F(m)那么整个程序段的时间复杂度为T=t(m)(tl(n)+t2(m)因为for语句里if后面语句被执行的平均次数为(nl)+(n-2)+l+0=n2;所以f(n)=n2*2+n*3+2=n*4+2；那么tl(n)=O(f(n)=O(n),同理得t2(m)=O(g(m)=O(m),而最后的if后面语句被执行的平均次数为(m+l)/2那么T=O(2+2+tl+2+t2+l)m+2+(m+l)2)=O(maxmn,mm)4.13所谓回文，是指从前向后顺读和从后向前读都一样的不含空白字符的串。例如
19、did,madamimadam,pop即是回文。试编写一个算法，以判断一个串是否是回文。#include#includettincludeusingnamespacestd;结点类#ifndefstdafx_h#definestdafx_htemplatestructLinkNodeTdata;1.inkNode*link;1.inkNode(constT&item,LinkNode*ptr=NULL)(data=item;link=ptr;1.inkNode(LinkNode*ptr=NULL)link=ptr;)；ttendif#PragmaoncetemplateclassCCStack
20、(public:CCStack(void);CCStack(void);protected:1.inkNode*top;public:voidPush(constT&x);boolPop();boolIsEmpty(void)return(top=NULL)?true:false;TgetTop();)；includeStdAfx.hinclude”.cstack.hfusingtemplateCCStack:CCStack(void):top(NULL)()templateCCStack:CCStack(void)()templatevoidCCStack:Push(constT&x)(to
21、p=newLinkNode(x,top);)templateboolCCStack:Pop()if(IsEmpty()=true)returnfalse;LinkNode*p=top;top=top-link;deletep;returntrue;)templateTCCStack:getTop()(Tx;if(IsEmpty()=true)returnNULL;x=top-data;returnx;)#includestdafx.h#include.cstack.cpp”fusingusingnamespaceSystem;int_tmain()(stringa;booltemp=true;
22、inti=0;CCStackst;cina;while(ai!=,0,)(st.Push(ai);i+；)i=0;while(ai!=,0,)(if(ai=st.getTop()(st.Pop();i+；)elsetemp=false;break;if(temp)COUt“此字符是回文endl;elseCOUt此字符不是回文endl;return0;Ee:数据结构作业4回文Debug回文.exe*poopllpoopR匕字符是回文Pressanykeytocontinue415编写一个算法frequency,统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。/std
23、afx.h#include#includeftincludeusingnamespacestd;include*stdafx.hfusingusingnamespaceSystem;int_tmain()(stringa;intk,*num;char*A;cina;k=a.length()；A=newchark;num=newintk;frequency(a,A,num,k=0);for(inti=0;ik;i+)(COUtXAi:numi个endl;)deleteA;deletenum;returnO;)voidfrequency(strings,charA,intC,int&k)(inti
24、,j,Ien=s.length();A0=s0;C0=1;种类数k=1;for(i=1;ilen;i+)Ci=O;for(i=1;ilen;i+)(J=0；while(jk&Aj!=si)j+;if(j=k)(Ak=si;Ck+;k+;)elseCj+;二口 X%:数据结构作业4字符统计Debug字符统计.execontnuey45a45个个个个Ss.J2122eh:rJJh4SP第五章树表示法，分别画出图示二叉树的存储表示。答:12345678910U121314151617181254561l8l95.15写出向堆中参加数据4,2,5,8,3,6,10,14时，每参加一个数据后堆的变化。判
25、断以下序列是否是最小堆？如果不是，将它调整为:100,86,48,73,35,39,42,57,66,21)答：不是i=05.18一棵二叉树的前序遍历的结果是Abecdfghij,中序遍历是Ebcdafhigj,试画出这颗二叉树。答：519给定权值集合15,03,14,02,06,09,16,17),构造相应的HlIffmaIl树，并计算它的带权外部路径长度。答：它的带权外部路径长度WPL=229第六章集合与字典6.1SA=1,2,3,B=3,4,5),求以下结果：(1)A+B；(2)A*B;(3)A-B5(4)A.Contains(l);(5)AAddMember(I);(6)A.DelMe
26、mber(1)；(7)A.Min()。答：(1) A+B=1,2,3,4,5)(2) A*B=3A-B=l,2(4) A.Contains(1)=true(5)A.AddMember(l)=false9集合A不变(6)A.DelMember(1)=true,集合A=2,3(7) A.Min()=169设散列表为HT13,散列函数为H(key)=key%13,用闭散列法解决冲突，对以下关键码序列12,23,45,57,20,03,78,31,15,36造表。采用线性探查法寻找下一个空位，画出相应的散列表。答：Hash(12)=12Hash(20)=7Hash(15)=2012Hash(23)=1
27、0Hash(3)=3Hash(36)=1034Hash(45)=6Hash(78)=0567Hash(57)=5Hash(31)=5890111278153574520312336I126.10设有150个记录要存储到散列表中，并利用线性探查法解决冲突，要求找到所需记录的平均比拟次数不超过2次。试问散列表需要设计多大？(设a是散列表的装载因子，那么有ASLsu3(553612(612,6771 /.斯(677,765/08(765,8971v,1/.(908：8(I897908)117.3设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,
28、677,765,897,908。试画出对其进行折半搜索时的判定树。答：8.1请给出该图的邻接矩阵，邻接表和逆邻接表。邻接矩阵:Edge=OOOOOO1O1OO01010OOOOO10010OOOOO00010邻接表:ABCDEAF逆邻接表:8.2对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判断以下有关问题；(1)图中有多少条边？(2)任意两个顶点i和j是否有边相连？任意一个顶点的度是多少？解：(1)用邻接矩阵表示无向图时，由于其为对称矩阵，所以统计矩阵的上三角或者下三角非零元素个数即为图的边数，用邻接表表示时，邻接表中的边链表的边结点个数。除以2便是其边数。用邻接矩阵表示有向图
29、时，矩阵的上非零个数即为其边数，用邻接表表示时，邻接表中的边链表的边结点个数便是其边数。(2)用邻接矩阵表示无向图时，如果邻接矩阵中i行、j列不为非零元素那么表示其有边相连。用邻接表表示时，如果顶点i的边结点的desk域有j,那么可判断i和j相连。用邻接矩阵表示有向图时，如果邻接矩阵中i行、j列或j行、i列不为非零元素表示此i和j有边连。用邻接表表示时，如果顶点i的边结点的desk域有j或顶点j的边结点的desk域有i,那么可判断i和j相连。(3)用邻接矩阵表示无向图时，统计处第i行或第i列的非零元素个数，就可得到顶点i的度。用邻接表表示时，统计顶点i的边链表中边结点个数即为其度。用邻接矩阵表
30、示有向图时，第i行和i列的非零元素个数总数即为其度。用邻接表表示时，统计顶点i的边链表中边结点个数和其他所有顶点对应的边链表中边结点的desk域为i的个数之和即为其度。8.4 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？解：用邻接矩阵表示图时，矩阵元素的个数是顶点个数的平方，所以相关，但与边的条数无关。矩阵的非零个数与边的条数有关。对于有向图，有边的条数个非零元素，对于无向图，有2倍边的条数个非零元素。8.5 用邻接矩阵表示图时，假设图中有100O个顶点，100O条边，那么形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？解：图中有IoOO个顶点，那么矩
31、阵的元素应该有IoOo*10Oo=100oooO个。对于有向图，有100O个非零元素，对于无向图，有2000个非零元素。S=10001000000=0.0010.05有向图)，=2000/1000000=0.0020.05无向图)，所以是稀疏矩阵。8.6 画出1个顶点，2个顶点，3个顶点，4个顶点，和5个顶点的无向完全图。试证明在n个顶点的无向完全图中，边的条数为n(n-l)2o解：证明：在有n个顶点的无向完全图中，每一个顶点都有一条边与其他某一个顶点相连，所以每个顶点有ml条边与其他n-1各顶点相连，总计n个顶点有你n(n-l)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所
32、以总共有n(n-l)/2,所以得证。8.12图8.33是一个连通图，请画出:(1)以顶点为根的DFS树。设待排序码序王列为12,2,16,30,28,10,16*,20,6,18),试分别写出使用以下方法每趟排序后的结果。并说明做了多少次排序码比拟。希乐排序(4)快速排序基数排序解:使用希尔排序法第一趟：10,2,16,6,18,12,16*,20,30,28第二趟：10,2,16,6,16*,12,18,20,30,28,第三趟:2,6,10,12,16,16*,18,20,28,30排序码比拟次数为：28次(4)使用快速排序法第一趟:6,2,10,12,28,30,16*,20,16,18第二趟:2,6,10,12,18,16,16*,20,28,30第三趟:2,6,10,12,16*,16,18,20,28,30第四趟:2,6,10,12,16*,16,18,20,28,30排序码比拟次数为:20次(9)使用基数排序:第一趟:30,10,20,12,2,16,16*,6,28,18第二趟：2,6,10,12,16,16*,18,20,28,30
