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

《《数据结构与实训（第4版）》习题参考答案.docx》由会员分享，可在线阅读，更多相关《《数据结构与实训（第4版）》习题参考答案.docx（17页珍藏版）》请在优知文库上搜索。

1、第一东I.填空题(I)在计算机中的存储映像(是逻辑结构在计徵机中的实现或存储衣示数据元素的去示元素之间关系的表示数据元素.(2)一对一一对多多对多(3)时、空效率指人对匏法问读埋解的难易程度对于非法的输入数据,算法能给出相应的响应，而不是产生不可预料的后果。(4)软硬件环境问时规模的(5)最坏(6)O(n*)O(n2)(7)时间复杂度(8)n2On-)(9)指针2.判断越(1) 2)(4)(6)(7)(8)(9)(8)p的前骗O(n)(9)PfneXt=pnext-next(IO)head-Iiext=NuIIhead=Nllhead-next=headhead=Nll(IDhead-ncxl

2、=head-next-nexthead=head-next2 .判断题(1) (2)(4)(5)(8)(9)10)3 .选择SS(1) A(2)A3)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.elemil.eleml.listleng(h-l-i:(2)voiddeleteSeq1

3、.istI.ini.intk)，从顺序表中捌除自第i个元素开始的k个元素力if(il.listlength-lkIIWintf(Error”)；return：)if(i+k=l.listlcngth)小衣中从i个元素起到最后一个元素有k个元素/(for(j=ikJO.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

4、(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&pldatax)(p2=p;pI=pI-*next;if(p-*ncxt=Null&p-*(hta=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)片在不带头

5、结点且长度大于1的单向循环链表中,P指向某结点删除P的前郭结点，PPP=PinCKI；while(p)p-*nexex(!=)ppp=PPPrrwxl:尸刷除P的前弱结点”/PP=PPPinCXt;PPPfneXl=PPfnext;frx:I(5)voiddelete(1.ink1.islh)/*h为带头结点的,非降序排列的单鞋表的头指针.删除表中值相同的结点.使之只保留一个p=h-*nexn(1.ink1.islla.1.ink1.istlb/la.lb.lc分别为表示集合A,BC的带头结点的递增有序的单健表的头指针C=AGBillIct表返回州(Ic=(1.ink1.isl)malloc(

6、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-datapb=pb-ncxt;ifinseft(lc,(ail.pa-*data);Pa=ParnCxl:rcturn(lc);IvoidinsertM值X插入到单链表1的尾部*/P=(1.ink1.ist)malloc(Sizcof(1.inkNodc)-*daa=x;PfrWXl

7、=null:tail-*ncxt=p:tail=p;IScq1.istintcrsxtio11(Scq1.istla.Scq1.istlb)集合A,B,C对应的顺序递增表为EItMc,C=AB由Ic表示，/IcJistlength=O;if(IaJistIcngth=OIbJislknglh=O)rclum(lc)for(a=0:ala.iistlength;a+)for(b=0;txlb.listleng(h&lb.elcmb!=la.clcma;b)if(IxIbJistlength)(lc.elemlc.lisilength)sla.elema:Ic-Iistlcngth+;I)relu

8、cn(lc):(11)intDel1.st(Seq1.st,1.intx.inty)i11ti=O,k=O:while(ilistlngth)if(1.-elemi=x&1.-emielemik=1.-lmi;i+；)1.-XistIength=1.,IiStIength-k;return(OK);(12)intDelUsUSeqUst,1.)(intI=O1j=1;while(jelemi=1.-elemj)j+；elsei+;1.-elemi=1.-elemj;j+；)1.-listength-i*1;return(OK);第三章堆栈和队列I.填空题(1) 1.3.51(2) push,p

9、op,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(!2fix)nt-nexl=rcar(I3front=rcar2.判断SS(rcar+l)%MAX=frontrear+MAX-frort(I)(2)(4(5)X(8(9):elseIWhiH!Empty(sl)Push(s2.Pop(sl);PoPG2);)I(7)WdciincMAXSIZE50typcdcfstructQucucEIcnKntTypcclcmMAXSIZE

10、;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-fnnl(printf(*noverflow)returnERROR;Jif(qUg=0&q-rear=q-frnlq-tag=l:f有元素入队则队列一定不空将Ulg置1/q-clcmq-rcar=c;qrear=(q-tea,I)

11、%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(qrear=qfn11)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