《数据结构与实训（第4版）》习题参考答案.docx

第一东I.填空题(I)在计算机中的存储映像(是逻辑结构在计徵机中的实现或存储衣示数据元素的去示元素之间关系的表示数据元素.(2)一对一一对多多对多(3)时、空效率指人对匏法问读埋解的难易程度对于非法的输入数据,算法能给出相应的响应，而不是产生不可预料的后果。(4)软硬件环境问时规模的(5)最坏(6)O(n*)O(n2)(7)时间复杂度(8)n2O<n-)(9)指针2.判断越(1) ×<2)×<3>(4)(6)(7)×(8)×(9)×<10)X(II)X3,简答题(I)略(见教材第3页的1.2数据结构的基本概念)(2) （八）n-l.O(n)(b)n-1.O(n)(c)ll*n+I,O(n)(n为初始值Kxn第二串线性表I、填空SS(I)addrcss+m*i(2)断序顺序瞅序琏式存储链代存谛(3)亦相邻不一定(4) 0n(5) OWiWla的长度-IWjWIb的长度-IOWkWIC的长度-1(6) 2插入的位置,元素个数n(顺序表长度n)(7) p的前驰O(n>(8)p的前骗O(n)(9)PfneXt=pnext-next(IO)head-Iiext=NuIIhead=Nllhead-next=headhead=Nll(IDhead-ncxl=head-next-nexthead=head-next2 .判断题(1) ×(2)<3>×(4)×(5)×<6)×(7>(8)×(9)×<10)×3 .选择SS(1) A(2)A<3)A(4)D4 .简答胆(I)单向循环链表双向循环链表存储密度脑低代找后继的时间以杂度O(I)O(I)否找前胆的时间狂杂度0(n)O(I)(2)在带头结点的单於表匕查找指针P所指结点的前驱.(3)交换指针P与指竹q所指结点的值.5 .算法设计JS(1)voidrcvcrsc(Scq1.istI)for(i=0;i<=<l.lis(leng(h-1)/2;i+)l.elemi<->l.eleml.listleng(h-l-i:(2)voiddelete<Seq1.istI.in<i.intk)，从顺序表中捌除自第i个元素开始的k个元素力if(i<0Hi>l.listlength-lk<0>IIWintf("Error”)；return：)if(i+k<=l.listlcngth)小衣中从i个元素起到最后一个元素有k个元素/(for(j=i÷kJO.Iisdength;j+)l.elemj-k=l.elemj;1.IistIengt=I.Iisllength-k:)else*表中从i个元素起Il到最后一个元素不足k个元素*/IJiSUenglh=i:(3)voidinsert(1.ink1.iSih.EIememTyPex)产将x插入到递增链表h中，插入后的链表有序性不变if(h-ncxt=Null)C空表时/q=(linklis)InaUoC(Sizeoft1.istNode):q-IWXt=NuIkq-data=x:h-*ncxt=q;)pl=h-next:p2=h:while(plnext!=Null&&pldata<x)(p2=p;pI=pI-*next;if(p-*ncxt=Null&&p-*(hta<x)q=(linklis()nalloc(Sizeof(1.istNode);q-next=Null;q-data=x:pl-ncxt=q;Ielse尸(pl-nexl=Null&&pl-data>=x>(pl-nexl!=Null&&pl-*dala>=x)4/(q=(1.ink1.ist)malloc(sizcof(1.istNodckq-*data=x;p2-*nex(=q;q-nexl=pl;I(4)voiddelete(1.ink1.islp)片在不带头结点且长度大于1的单向循环链表中,P指向某结点删除P的前郭结点，PPP=PinCKI；while(p)p-*nex<_*>ex(!=)ppp=PPPrrwxl:尸刷除P的前弱结点”/PP=PPPinCXt;PPPfneXl=PPfnext;fr<x<pp>:I(5)voiddelete(1.ink1.islh)/*h为带头结点的,非降序排列的单鞋表的头指针.删除表中值相同的结点.使之只保留一个p=h-*nex<if(!p)return:x=p-*data:while(PineKt)if(x!=PfneX1.daUox=PrnCX1.ddla:p=p-nextelseIq=p-next:PTneXt=Pinext-next:Ircc(q)；1.ink1.islintersectk>n(1.ink1.islla.1.ink1.istlb>/la.lb.lc分别为表示集合A,BC的带头结点的递增有序的单健表的头指针C=AGBillIct表返回州(Ic=(1.ink1.isl)malloc(Sizeof(1.inkNode);Ic-ncxt=null:tail=lc;4tail指向IC健的尾结点if(!(la-*ncxc)Itlum(Ic);elsepa=la-next:if(!(lb-*next)rc(um(lc);while(pa)Ipb=lb-next;while(pb&&pa-data!=pb-data>pb=pb-ncxt;if<pb>inseft(lc,(ail.pa-*data);Pa=ParnCxl:rcturn(lc);Ivoidinsert<1.ink1.islI.1.ink1.isttail.EkinenTypex>M值X插入到单链表1的尾部*/P=(1.ink1.ist)malloc(Sizcof(1.inkNodc)-*daa=x;PfrWXl=null:tail-*ncxt=p:tail=p;IScq1.istintcrs<xtio11(Scq1.istla.Scq1.istlb)"集合A,B,C对应的顺序递增表为EItMc,C=AB由Ic表示，/IcJistlength=O;if(IaJistIcngth=OIbJislknglh=O)rclum(lc)for(a=0:a<la.iistlength;a+÷)for(b=0;txlb.listleng(h&&lb.elcmb!=la.clcma;b÷÷)if(IxIbJistlength)(lc.elemlc.lisilength)sla.elema:Ic-Iistlcngth+;I)relucn(lc):(11)intDel1.st(Seq1.st,1.intx.inty)i11ti=O,k=O:while(i<1.>listlngth)if(1.->elemi>=x&&1.->emi<=y)k÷+j÷+j)else1.->elemik=1.->lmi;i+；)1.-XistIength=1.,IiStIength-k;return(OK);(12)intDelUsUSeqUst,1.)(intI=O1j=1;while(j<Hstength-1)if(1.->elemi=1.->elemj)j+；elsei+;1.->elemi=1.->elemj;j+；)1.->listength-i*1;return(OK);第三章堆栈和队列I.填空题(1) 1.3.51(2) push,pop,push.push.pop.push.pop.pop(3)栈空(4)Of!)栈满O(I)(5)=s.top-1=s.top+1（6）S(7)空（8）栈底栈顶（9）队尾队首（头）（10）是否为空是否为满(II)21(!2>fix)nt-nexl=rcar(I3>front=rcar2.判断SS(rcar+l)%MAX=frontrear+MAX-frort(I)(2)×<3>(4>(5)X<6)(7>(8>×(9)<IO)3 .选择鹿(DC(2)C(3)C(4)D(5)C(6)B4 .简答即(I)当进行入队掾作时，队尾指针的侑已经到达数殂空间的最大下标(MaXSize-1),而队首指针的值却大于0.这时就产生了假溢出现象,(2)使栈S中的元素顺序置逆.(3)借助于另一脏栈t,使得链栈S去掉指定的元素。5 .算法设计鹿对于输入序列123,4,对应的24种排列是：1.2.3.412431.3.2.41.3.4.21,4231.4.3.22.1.3.42.1.4.32.3.1.42.3.4.12.4.1.32.4.3.1Jelseif(!Empty(s2)Pop(s2>:elseIWhiH!Empty(sl)Push(s2.Pop(sl);PoPG2);)I(7)WdciincMAXSIZE50typcdcfstructQucucEIcnKntTypcclcmMAXSIZE;i11(fronauag;a将标志u设蔚为队列的一个成员，便于数据的传递Uig=O衣示队列为空，Iag=I表示队列不空*/ICirQucuc:voidlnitQucuc(CirQucuc*q)q->fro11(=q->rea-0;q->tag=O:IintA(klQucuc(CirQucuc*q,EIcmcmTypcc)产入队SVif(q->tag=l&&q->rcar=q->fn>nl>(printf(*noverflow)returnERROR;Jif(q>Ug=0&&q->rear=q->frnl>q->tag=l:f有元素入队则队列一定不空将Ulg置1/q->clcmq->rcar=c;q>rear=(q->tea,÷I)%MAXSIZE:relurn0K:IintDelctcQueuc(CirQucuc*q,QucucEIcmcntTypc*c)产出队衾/if(q->(ag=0&&q->rear=q>!ronl)returnERROR:4c=q->clcmq->frontl;q->fron(q->fmm+1)%MaxSizc;if(q>rear=q>>fn>11)q-><ag=O;产有元索出队后，队头和队尾相等，队列为空，则将I胆置0*/returnOK:第四章a1,0.().0a1.0.0.1a1.0.0.2a1.0.1.0a1.0.1.1a1.0.1.2aIJAOaI,I.0,a1,1.0.2a1.1.1.0a1.1,1.1a1.1,1,2a1.2.0,0列优先：a12.0.1a1.2,0.2aI.2.I,0al,2,l.la1.2,1.2a0,0.0.0a1.0.0.0a0.1.0.0a1.1.0.0a0.2.0.0a1.2.0.0aOA1.Oa1.0.1.0a0.1,1,0a1,1,1,0a0.2,1.0a1.2,1,0a0.0.0Ja1.0.0.1a0.1.0.a1.1.0.1a0.2,0.1a1.2.0.1a0.0.1.1u1.0.1.1a0.1,1.1a1.1.1.1a0.2.1.1a1.2.1.1a0.0.0.2a1.0.0.2a0.1.0.2a1.1.0.2a0.2.0.2a1.2.0.2a0,0J,2a1.0,1.2a0.1.1.2a1.1.1.2a0.2.I.2a1.2,1,2(7)稀疏矩阵压缩存储后会失去随机存取的功能，因为稀疏矩阵不能根据元素在矩阵中的位理求得在其在三元组顺序表中的位置，而特殊矩阵则可以，11*mt<(8)当3tvmn即3时，三元组的表示才有意义.(9) i=j或i+j=n+l4J2(i-1)(当/=；) 2(r-l)+l(当i+j="+I)4,算法设计题(I)void/KssigiUBIock1.ink气char()产将存放在字符数组t中常砒赋给川ss=s:Mi=0it0!=0i÷÷)Iif(i%NodeNumO)(j=o：P=(Block1.inN)malloc(Sizcof(BIock1.ink):p-*ncxt=Null;ss-*nex(=p;SS=:)p-*(tatalj=ti;j+:>while(j!=NtxlcNum-I)(p-dataj='#'j+：I(2)voidfrcq>ency(intnum)intlistlength;Scq1.ist;voidGelSaddle(intA(.iniin.intn.ScqI1.isls()，求矩阵Ai,中的载点.鞍点的位置存放在顺序表S中，/SJistIength=O;for(i=0:i<m;i+)Ifor(min=Ai)0,j=0;j<n;j+)if(Ai)j<min)求一行中的母小值Al'or(j=OJ<nj+)if(Aijl=min"判阍这个(些)最小值是否鞍点”/(fb(ag=l,k=O;k<m;k+)if(min<A(k(j)flag=0;尸不是一点*/i,(tlag)"是鞍点/s.clcm|listlcngth|.row=i;s.elemlislengh.colmn=j;s.listlength+:I(5)【题目分析:矩阵中元索按行和按列都己排序，要求比较次数不断过mn,因此不能采用行规的二层循环的杳找.Ur以先从右上角(i=0,j=u)元素与X比较,只有三种情况:一是Alxj>x,这情况下向j小的方向维埃查找:二是Ai,j<x,下步应向i大的方向查找:三是Ai,j-x.查找成功.否则,若下班已超出范围，则查我失败.voidsearch(ElementTypeA,intm,intn,ElementTypex,int*row,int*column)/m*n的矩阵b,本算法查找X在矩阵b中的位置(*row,*column)/ii-0;j-n;flag-0;*flag是成功查到X的标志”uhile(i<=m&&j>=0&&!flag)if(bij=)flag=l;elseif(bj>x)j：elsei+：if(11ag)*ro=i;*column=j;A.datapc.r=x;.datapc.c=.datapa).c;A.datapc.d=A.datapa.dpa”;PC+;1)while(A.datapa=x)*插入A中剜余的元素第X行)”.datapc.r=x;A.<Jata(pc).c=A.data(pa).c;,datac.d=A.datapa.dpa14;PCwhiIe(B.datapb=x)/*插入B中剩余的元素(第X行)*/.datapc.r-x;.datapcj.c=B.dataipb.c;A.data(pcj.d=B.data(pb).d;pb+÷:pc+;A.nms=pc;for(i=,hubs;i<MaxSize;i+÷)/*消除原来A中的元素*/(.datai.r=-l;A.datai.C=-I;A.datai.d=nil:第五章习题答案1.填空题(I)am.n.d.j.k.l.fca.cj.ki.m.ndg.h25533O（2）能唯一确定这榇二叉树.二叉树为:若给定先序序列和后序序列无法睢一确定一棵二叉树，因为根据先序序列虽可以确定根.但不可以根据后序序列确定左子树和右子树.如下面两榇二叉树,它们的先序序列和后序序列相同，但却确定了两探不同的二叉树.II注；函数BSTSearch1.BSTDeIete参阅教材§7.3.3.§7.3.4,第8章习题答案1,填空题(1) i(2) n-l(3) n/2(4) O(n2)(5) O(n)(6)冒泡排序(7)希尔排序(8)直接插入排序(9)插入排序、选择排序(10) 79,46,71,35,41.25,56(11) 25.41.35.46.56.79.71(12) n/2n-lO(nlogn)(13)正反反(14)宜接选择排序、希尔排序、堆排序、快速排序(15)堆排序、快速排序、归并排序、归并排序、快速推序、堆排序2、判断题(1) (2)<3)×(4)X(5)×(6) ×(7)×<8)×(9)×(10)3、简答题略(参考教材写).(2)易于链表实现的是插入持序、归并排序和基数排序(3)初始状态为逆序时.直接插入、直接选择和冒泡排序的比较次数分别为(n+2)(n-l)2.n(n-l)2,n(n-l)2.移动次数分别为(n+4)(n-l)2,3(n-l),3n(n-l)2,因此文件逆序时采用直接选择排序较好。(4)在初始状态为逆序情况下，采用冒泡排序是稔定排序。（5）高度为h的堆，最多有2lM个元素，最少有2h4个元素。在高度为h的大顶堆中，关键字最小的元素存放在堆的第h层上的最后个元素的位置W上，其中2"Ww2h-l,（6）燃好选用堆排序，对比其他效率较高的排序算法，大都是在排序结束后才能确定数据元素的全部顺序，而无法知道排序过程中部分元素的有序性，而堆排序则每次输出一个极值元素，且比较次数不超过|_"10七“，耍好丁如冒泡排序、选择排序等简单排序算法，由题意，只选择前10个大元素，所以可以利用大顶堆进行排序。（7）d是8,分配和收集8趟，rd是26,队列个数26。（8）是大顶堆不是堆，可以调整为下面的小顶堆1234567891012243065335648988670是大顶堆不是堆，可以把它调整为下面的小顶堆23456789IOIl120523203528382961567640I(X)4、算法设计题（1）分析与解答给head单涟表设置个附加表头结点，在排序过程中,单链表分成两个子表，即排序子表和未排序子表，首先将单链表的头结点和第一个结点看成是已经排序的子表，设置rear指针指向已排序子表的最后一个结点，初始时也就是维链表的第个结点。设置h指针指向未排序子表的第个结点，初始时也就是单依表的第二个结点，每次取出未排序子表的第一个结点，将其插入到前面已排序子表的合适位置上。设置q指针从已排序子表的第个结点出发，顺序查找合适位S：并设置指针P用来跟踪q的直接前驱，以便插入操作。typcdefstructnodeintdata;SInIClnode*ncxt;1.istNode;typedef1.istNode*1.ink1.ist;Instersort(1.ink1.isthead)(1.istNodc*p.*q.*h.*rcar:rear=head-next;产rear指向已排序子表的最后一个结点，初始时为单链表的第一个结点*/h=rear-next：*h指向未排序了表的第个结点*/while(H=NU1.1.)if(hdata<rear-data)p=head:q=p-nexl;*<从已排序子表的第一个结点出发，找插入位置*/WhiIe(q-data<h-data)(P=q；q=q-next;realnexl=h-*next:*从未排序子表中分高出h结点*/h-next=q;/*将h结点插入到已排序子表的P和q之间*/PfneXt=h：h-rear-next;*h指向卜.一个待插入的结点*/elserear=h;h=h-next;(2) i从左向右扫描数组，找到正数后，j从右向左扫描数组，找到负数后，交换i、j位置上的数据，然后i继续向右扫描，反笑执行上述操作，直到i和相遇。defineMaxSizc100/*待排序记录可能达到的最大长度*/Iypedefstruct/*记录类型*/KeyTypekey；/*关键字项*/InfoTypeOtherData:/*其他数据项，InfoTypQ根据实际情况定义*/JRecordType:typcdefRccordTypeRccDataMaxSizc；*RccData为眼序表类型*/voidResort(RecDalar)inti=O,j=n-l;RecordTypex;dowhile(i<j&&ri.kcy<O)i+;WhiIC(j>i&&rj.koy>0)j;if(i<j)x=ri:ri=rj:rj=x：i+;j-;while(i<j);)(3)voidBubblcSort(RccDatar,intn)*自下往上扫描的冒泡持序算法*/(intlastexchange,j,i0,x：while(i<n-l)UaSleXChUnge=nT;for(j=n-l:j>i:j)*自下,往上扫描r0.i*/if(rj-l.key>rj.key)*rjT和rj交换/x=rj:rj=rj-l;rj-l)=x:Iastexchange=J:i=lastexchange：)(4)排序结束条件为没有交换元素为止或进行r几趟排序.函数描述如卜.：voidQrsort(RccDatar)/*排序元素r0-rn-l*/i11ti,flag:RecordTypet：doflag=O;for(i-0;i<n;i+)*奇数扫描*/if(ri.key>ri+l.key)flag=l:t=ri+l;ri+l=ri;ri=tzi+；)for(i=l：i<n;i+)*偶数扫描*/if(ri.key>ri+l.key)flag=l:t=ri+l;ri+l=ri;ri=t：i+：)Jwhilc(glag!=O)：(5)略(参考教材1>(6)设向量C有IO个元素，其值在09之间，如下图所示:O12345678?119O5-138762根据题意排序结果如下图所示："l'01234567890123456789兑法描述如下：Sort(intc,intb,intn)(inti;for(i=0;i<n;i+)bci=ci;)(7)堆的类型定义：SdefineN50typedestructelement;KeyTypckey：RecType:typedefstructlist;KcyTypeRN;intn:)Seq1.ist;voidHeaPDel.ele(Seq1.isl*heap,inti)(intj;heap-Ri=heap-*Kn;*Ki堆底元素交换位置*/heap-*11-=l：Heapify(heap,i,haep-n);/*调用调整堆算法*/)Heapify(Seq1.ist+heap,inti;intbase)/*将Ri.base调整为堆*/(inij;RecTypetcmp=heap-Ri：for(j=2*i:j<=base:j*=2)if(j<base&&heap-Rj.key<heap-RCj+l.key)j+：/*若i有右孩子，口右孩子大于左孩子，则让j指向右孩子*/if(heap-R(j.key<=temp.key)break：heap-Ri-heap-*RIjJ;i=j；)