數(shù)據(jù)結(jié)構(gòu)習(xí)題有

1、.專(zhuān)業(yè).專(zhuān)注.第1章緒1.1有以下幾種二元組表示的數(shù)據(jù)結(jié)構(gòu)，試畫(huà)出它們分別對(duì)應(yīng)的圖形表示，(1)會(huì)集并指出它們分別屬于何種結(jié)構(gòu)。abcde(2)線(xiàn)性表(1)A=(D，R)，其中，D=a1，a2，a3，a4，R=(2)B=(D，R)，其中，D=a，b，c，d，e，R=(a，b)，(b，c)，(c，dd)，(d，e)bgace(3)C=(D，R)，其中，D=a，b，c，d，e，f，g，R=(d，b)，(d，(3)樹(shù)f圖(4)125346g)，(b，a)，(b，c)，(g，e)，(e，f)(4)K=(D，R)，其中，D=1，2，3，4，5，6，R=，1.2設(shè)n為正整數(shù)，求以下各程序段中的下劃線(xiàn)語(yǔ)句的

2、執(zhí)行次數(shù)。(1)i=1;k=0(2)for(inti=1;i=n;i+)解：while(i=n-1)for(intj=1;j=n;j+)(1)n-1.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.cij=0;k+=10*i;for(intk=1;k=n;k+)i+;cij=cij+aik*bkj(3)x=0;y=0;for(inti=1;i=n;i+)for(intj=1;j=i;j+)for(intk=1;k=j;k+)x=x+y;1.3指出以下個(gè)算法的功能，并求其時(shí)間復(fù)雜度。(1)intsum1(intn)(2)intsum2(intn)ints=0;nnn(2)1n3i1j1k1nijnini(i1)1n

3、21n1n(n1)(2n1)1n(n1)i(3)i11j22i2i1i622j1k1i1j1i112n(n1)(n2)6解：.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.intp=1,s=0;for(inti=1;i=n;i+)n(1)i!,T(n)=O(n)i1for(inti=1;i=n;i+)intp=1;nT(n)=O(n2)p*=i;s+=p;for(intj=1;j=i;j+)p*=j;(2)i!,i1returns;s+=p;returns;1.4算法設(shè)計(jì)有3枚硬幣，其中有1枚是假的，偽幣與真幣重量略有不相同。怎樣借用一架天平，找出偽幣？以流程圖表示算法。開(kāi)始是A=B？C是偽幣否是A=C？B是偽

4、幣否是偽幣結(jié)束.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.上機(jī)練習(xí)題要求：給出問(wèn)題解析、算法描述、源程序及運(yùn)行截圖，在線(xiàn)提交。1.設(shè)a,b,c為3個(gè)整數(shù)，求其中位于中間值的整數(shù)。.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.第2章線(xiàn)性表1.設(shè)計(jì)算法：在序次表中刪除值為e的元素，刪除成功，返回intSqlist:DeleteElem(Te)1；否則，返回0。for(i=1;i=length;i+)/按值序次查找*i可從0開(kāi)始if(elemi-1=e)/找到，進(jìn)行刪除操作for(j=i;jlength;j+)/ai至an依次前移Elemj-1=elemj;length-;/表長(zhǎng)減一return1;/刪除成功，返回1return

5、0;/未找到，刪除不能功，返回02.解析序次表中元素定位算法intSqList:Locate(Te)解：設(shè)表長(zhǎng)為n，等概率下，每個(gè)元素被定位的概率為：p=1/n的時(shí)間復(fù)雜度。定位成功第i個(gè)元素，需比較i次.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.nf(n)i11i1ni1n(n1)n1nni1n223.對(duì)于有頭結(jié)點(diǎn)的單鏈表，分別寫(xiě)出定位成功時(shí)，實(shí)現(xiàn)以下定位語(yǔ)句序列。(1)定位到第i個(gè)結(jié)點(diǎn)ai；p=head;j=0;while(p&jnext;j+;(2)定位到第i個(gè)結(jié)點(diǎn)的前驅(qū)ai-1；p=head;j=0;while(p&jnext;j+;(3)定位到尾結(jié)點(diǎn)；p=head;while(p-next)p=p

6、-next;(4)定位到尾結(jié)點(diǎn)的前驅(qū)。p=head;while(p-next-next)p=p-next;.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.4.描述一下三個(gè)看法的差異：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)。并給頭指針：是一個(gè)指針變量，里面儲(chǔ)藏的是鏈表中首結(jié)點(diǎn)的地址，并以此來(lái)表記一個(gè)鏈表。予圖示。頭結(jié)點(diǎn)：附加在第一個(gè)元素結(jié)點(diǎn)從前的一個(gè)結(jié)點(diǎn)，頭指針指向頭結(jié)點(diǎn)。首元結(jié)點(diǎn)：指鏈表中的第一個(gè)元素結(jié)點(diǎn)。頭指針頭結(jié)點(diǎn)首(元)結(jié)點(diǎn)尾(元)結(jié)點(diǎn).ana1a2.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.5.對(duì)于無(wú)頭結(jié)點(diǎn)單鏈表，給出刪除第i個(gè)結(jié)點(diǎn)的算法描述。templatetemplateTLinkList:Delete(inti)/在單鏈表上

7、刪除第i個(gè)數(shù)據(jù)元素TLinkList:Delete(inti)if(head=NULL)throw“表空!”;/空表，不能夠刪elseif(i=1)/刪除第1個(gè)元素p=Head;x=p-data;/保留被刪元素值Head=p-next;deletep;else/元素定位到第ai-1p=Head;j=1;/定位查找初步地址whilep-next&jnext;j+;if(!p-next|ji-1);/定位失敗.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.throw“刪除地址不合理”;else/定位成功，進(jìn)行結(jié)點(diǎn)刪除q=p-next;x=pdata;p-next=q-next;deleteq;retrunx;/返回

8、被刪除元素值/#6.用教材定義的序次表的基本操作實(shí)現(xiàn)以下操作：#include“SqList.h“templatetemplate.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.intDeleteElem(SqListL,Te)intDeleteElem(SqListL,Te)/i=L.LocateElem(e);/按值查找if(!i)/未找到return0;else/找到delete(i);/刪除被找到的元素7.已知L是有表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，【解】也不是尾結(jié)點(diǎn)，試寫(xiě)出實(shí)現(xiàn)以下功能的語(yǔ)句序列。(1)s-next=p-next;p-next=s;(1)在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)；(2)q=L;(2

9、)在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)；while(q-next!=p)q=q-next;(3)在表首插入S結(jié)點(diǎn)；s-next=p或q-next;(4)在表尾插入S結(jié)點(diǎn).q-next=s;.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.(3)s-next=L-next;L-next=s;(3)q=L;while(q-next!=NULL)q=q-next;s-next=q-next;q-next=s;上機(jī)練習(xí)題要求：給出問(wèn)題解析、算法描述、源程序及運(yùn)行截圖，在線(xiàn)提交。編程實(shí)現(xiàn)：刪除單鏈表中值為e的元素。.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.第3章棧與行列1.鐵路進(jìn)行列車(chē)調(diào)換時(shí),常把站臺(tái)設(shè)計(jì)解：325641能夠成棧式結(jié)構(gòu)的站臺(tái)，如右圖所

10、示。試3456154623不能夠夠。12問(wèn)：若進(jìn)站的六輛列車(chē)序次如上所述,那么可否能夠獲取325641和154623的出站序列,若是不能夠,說(shuō)明為什么不能夠;若是能,說(shuō)明怎樣獲取(即寫(xiě)出進(jìn)棧或出棧的序列)。.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.2.簡(jiǎn)述以下算法的功能（棧的元素種類(lèi)為int）。解：(1)借助一個(gè)數(shù)組，將棧中的元素逆置。(1)statusalgo_1(SqStackS)inti,n,A255;n=0;while(!S.StackEmpty()n+;An=S.Pop();(2)借助棧T，將棧S中全部值為e的數(shù)據(jù)元素刪除之。for(i=1;i=n;i+)S.Push(Ai);(2)status

11、algo_2(SqStackS,inte)SqStackT;intd;while(!S.tackEmpty()d=S.Pop();if(d!=e)T.Push(d);.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.while(!T.StackEmpty()d=T.Pop();T.Push(d);3.編寫(xiě)一個(gè)算法，將一個(gè)非負(fù)的十進(jìn)制整數(shù)N變換為B進(jìn)制數(shù)，#include“stack.h”并輸出變換后的結(jié)果。當(dāng)N=248D，B分別為8和16時(shí)，變換intNumTrans(intN,intB)/十進(jìn)制整數(shù)N變換為B進(jìn)制數(shù)后的結(jié)果為多少？stackS;/建立一個(gè)棧while(N!=0)/N非零.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)

12、注.i=N%B;/從低到高，依次求得各位N=N/B;S.push(i);/各位入棧while(!S.StackEmpty()/棧不空i=S.pop();If(i9)i=A+10-i;coutS.pop();/依次出棧，獲取從高到低的輸出結(jié)果/#4借且棧，設(shè)計(jì)算法：假設(shè)一個(gè)算術(shù)表達(dá)式中包含“(”、括“解：以字符串儲(chǔ)藏表達(dá)式，也能夠邊輸入邊判斷。)”號(hào)，對(duì)一個(gè)合法的數(shù)學(xué)表達(dá)式來(lái)說(shuō)，括號(hào)“(和”“)應(yīng)”是相互般配序次掃描表達(dá)式，左括號(hào)，入棧；右括號(hào)，若是此時(shí)棧空，表示多右括號(hào)，不的。若般配，返回1；否則，返回0。般配；若是棧不空，出棧一個(gè)左括號(hào)。掃描結(jié)束，若是?？?，表示括號(hào)般配；否則，括號(hào)不般配，多

13、左括號(hào)。.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.intblank_match(char*exp)用字符串存表達(dá)式SqStacks;/創(chuàng)辦一個(gè)棧char*p=exp;/工作指針p指向表達(dá)式首while(*p!=)/不是表達(dá)式結(jié)束符switch(p)case(:/左括號(hào)，入棧s.push(ch);break;case)/右括號(hào)if(s.StackEmpty()return0;/棧空，不般配，多右括號(hào)elses.Pop();break;/左括號(hào)出棧/switchp+;/取表達(dá)式下一個(gè)字符/while.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.if(!s.StackEmpty()/表達(dá)式結(jié)束，棧不空return0;/不般配，

14、多左括號(hào)elsereturn1;/般配/#簡(jiǎn)述棧和行列的邏輯特點(diǎn)，各舉一個(gè)應(yīng)用實(shí)例。6.寫(xiě)出以下中綴表達(dá)式的后綴表達(dá)式。(1)A-B+C-D+(1)-A+B-C+D(2)AB+D*EFAD*+/+C+(2)(A+B)*D+E/(F+A*D)+C(3)AB&EF!|(3)A&B|!(EF)7.計(jì)算后綴表達(dá)式：45*32+-的值。解：15.word可編寫(xiě).8.將以下遞推過(guò)程改寫(xiě)為遞歸過(guò)程。voidrecursion(intn)inti=n;while(i1)coutx;if(x=0)sum=0;elsetest(sum);sum+=x;.專(zhuān)業(yè).專(zhuān)注.解：voidrecurision(intj)if

15、(j1)courx;while(x)S.push(x);cinx;.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.coutsum;sum=0;coutsum;while(x=S.pop()sum+=x;coutsum;/.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.10.簡(jiǎn)述以下算法的功能（棧和行列的元素種類(lèi)均為int）。解：利用棧，將行列中的元素逆置voidalgo(Queue&Q)StackS;/創(chuàng)辦一個(gè)棧intd;while(!Q.QueueEmpty()d=DeQueue(Q);S.Push(d);while(!S.StackEmpty()d=S.Pop();Q.EnQueue(d);.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.12

16、.假設(shè)以數(shù)組sem存放循環(huán)行列的元素，同時(shí)設(shè)變量rear和解：采用教材隊(duì)空與隊(duì)滿(mǎn)鑒識(shí)方法。為了區(qū)分隊(duì)空與隊(duì)滿(mǎn)條件，犧牲一個(gè)元素空f(shuō)ront分別作為隊(duì)首、隊(duì)尾指針，且隊(duì)首指針指向隊(duì)首前一個(gè)位間。即：rear=front，為隊(duì)空；rear=(front+1)%m，為隊(duì)滿(mǎn)。置，隊(duì)尾指針指向隊(duì)尾元素處，初始時(shí)，rear=fornt=-1。寫(xiě)template出這樣設(shè)計(jì)的循環(huán)行列入隊(duì)、出隊(duì)的算法。voidEnQueue(TSe,Te,intm)/入隊(duì)if(rear+1)%m=fornt)/隊(duì)滿(mǎn)，不能夠插入throw“隊(duì)滿(mǎn)，不能夠插入!”elserear=(rear+1)%m;/隊(duì)尾指針后移serear=e

17、;/元素入隊(duì)return;/#.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.templateTDnQueue(TSe,intm)/出隊(duì)if(rear=fornt)/隊(duì)空，不能夠出隊(duì)!throw“隊(duì)空，不能夠出隊(duì)!”elsefront=(front+1)%m;/指針后移，指向隊(duì)首元素e=sefront;/取隊(duì)首元素returne;/#.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.上機(jī)練習(xí)題要求：給出問(wèn)題解析、算法描述、源程序及運(yùn)行截圖，在線(xiàn)提交。1.借助棧，實(shí)現(xiàn)單鏈表上的逆置運(yùn)算。.word可編寫(xiě).第4章串1.試問(wèn)執(zhí)行以下函數(shù)會(huì)產(chǎn)生怎樣的輸出結(jié)果?voiddemonstrate()StrAssign(s,THISISABOOK

18、);StrRep(s,StrSub(s,3,7),ESEARE);StrAssign(t,StrConcat(s,S);StrAssign(u,XYXYXYXYXYXY);StrAssign(v,StrSub(u,6,3);StrAssign(w,W);cout“t=”tendl;cout“v=”v;cout“u=”StrRep(u,v,w);.專(zhuān)業(yè).專(zhuān)注.解：t=THESEAREBOOKSv=YXYw=XWXWXW.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注./demonstrate2.設(shè)字符串S=aabaabaabaac，P=aabaac1）S的next與nextval值分別為和002002002009，

19、1）給出S和P的next值和nextval值；p的next與nextval值分別為012123和0020032）若S作主串，P作模式串，試給出KMP算法的般配過(guò)程。2）利用KMP算法的般配過(guò)程：第一趟般配：aabaabaabaacaabaac(i=6,j=6)第二趟般配：aabaabaabaac(aa)baac第三趟般配：aabaabaabaac(成功)(aa)baac3.算法設(shè)計(jì)串結(jié)構(gòu)定義以下：structSString.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.char*data；/串首址intlen;/串長(zhǎng)intStrSize；/存放數(shù)組的最大長(zhǎng)度.;(1)編寫(xiě)一個(gè)函數(shù)，計(jì)算一個(gè)子串在一個(gè)字符串中出現(xiàn)

20、的次數(shù)，解：intstr_count(SStringS,SStringT)若是不出現(xiàn)，則為0。inti,j,k,count=0;intstr_count(SStringS,SStringT)for(i=0;S.datai;i+)for(j=i,k=0;(S.dataj=T.datak;j+,k+)if(k=T.len-1)count+;.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.returncount;(2)編寫(xiě)算法，從串s中刪除全部和串t相同的子串。解：intSubString_Delete(SString&s,SStringt)/從串s中刪除全部與t相同的子串,并返回刪除次數(shù)for(n=0,i=0;i=

21、s.len-t.len;i+)for(j=0;jt.len)/找到了與t般配的子串for(k=i;ks.len-t.len;k+)sk=sk+t.len;/左移刪除.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.s.len-=t.len;n+;/被刪除次數(shù)增1/forreturnn;/Delete_SubString(2)編寫(xiě)一個(gè)函數(shù)，求串s和串t的一個(gè)最長(zhǎng)公共子串。解：voidmaxcomstr(SString*s,SString*t)voidmaxcomstr(SString*s,SString*t)intindex=0,len1=0,i,j,k,len2;i=0;/作為掃描s的指針while(is.len

22、)j=0;/作為掃描t的指針while(jlen1)/將較大長(zhǎng)度者給index和len1index=i;len1=len2;j+=len2;/ifelsej+;/whilecout”最長(zhǎng)公共子串：”for(i=0;ilen1;i+;).word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.couts.dataindex+1;/#已知以下字符串a(chǎn)=THIS,f=ASAMPLE,c=GOOD,d=NE,b=,s=StrConcat(a,StrConcat(StrSub(f,2,7),StrConcat(b,StrSub(a,3,2),t=StrRep(f,StrSub(f,3,6),c),u=StrConcat(StrSu

23、b(c,3,1),d),g=IS,v=StrConcat(s,StrConcat(b,StrConcat(t,StrConcat(b,u),試問(wèn):s,t,v,StrLength(s),StrIndex(v,g),StrIndex(u,g)各是什么?已知：s=(XYZ)+*，t=(X+Z)*Y。試?yán)靡韵逻\(yùn)算，將s轉(zhuǎn)變?yōu)閠。.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.聯(lián)接：StrConcat(&S,T)求子串：(char*)StrSub(S,i,len)置換：StrRep(&S,T,R)上機(jī)練習(xí)題要求：給出問(wèn)題解析、算法描述、源程序及運(yùn)行截圖，在線(xiàn)提交。串結(jié)構(gòu)定義以下：structSStringchar*da

24、ta；/串首址intlen;/串長(zhǎng)intStrSize；/存放數(shù)組的最大長(zhǎng)度.;.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.求：串S所含不相同字符的總數(shù)和每種字符的個(gè)數(shù)，不區(qū)分英文字母的大小寫(xiě)。.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.第5章數(shù)組與壓縮矩陣8個(gè)字節(jié)儲(chǔ)藏，儲(chǔ)藏器按解：(1）686=288Byte1.假設(shè)有二維數(shù)組A6，每個(gè)元素用相鄰的6字節(jié)編址。已知A的初步儲(chǔ)藏地址(基地址)為1000，計(jì)算：(2）1000+288-6=1282；(1)數(shù)組A的體積（即儲(chǔ)藏量）;(3）1000+(18+4)6=1072(2)數(shù)組A的最后一個(gè)元素a57的第一個(gè)字節(jié)的地址;(4）1000+(76+4)6=1276按行儲(chǔ)藏時(shí)，元素a14的第一個(gè)字節(jié)的地址;按列儲(chǔ)藏時(shí)，元素a47的第一個(gè)字節(jié)的地址。2.假設(shè)按低下標(biāo)優(yōu)先儲(chǔ)藏整數(shù)數(shù)組A935時(shí)，第一個(gè)元素的字節(jié)地址解：(1)1008是100，每個(gè)整數(shù)占四個(gè)字節(jié)。問(wèn)以下元素的儲(chǔ)藏地址是什么？(2)100+8358+258+48+7=4500(1)a0000(2)a8247.word可編寫(xiě).專(zhuān)業(yè).專(zhuān)注.3一個(gè)稀罕矩陣以下列圖030000M.dataije02050000131112A=0000002135900