《数据结构与实训（第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
