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

1、第1章緒1.1 后卜列兒種二兀組表示的數(shù)據(jù)結(jié)構(gòu)，試畫出它們分別對(duì)應(yīng)的圖形表示，并指出它們分別屬于何種結(jié)構(gòu)。(1) A=(D,R),其中，D=ai,a2,a3,包,R=(2) B=(D,R),其中，D=a,b,c,d,e,R=(a,b),(b,c),(c,d),(d,e)(3) C=(D,R)，其中，D=a,b,c,d,e,f,g,R=(d,b),(d,g),(b,a),(b,c),(g,e),(e,f)(4) K=(D,R),其中，D=1,2,3,4,5,6,R=<1,2>,<2,3>,<2,4>,<3,4>,<3,5>,<3,

2、6>,<4,5>,<4,6>1.2設(shè)n為正整數(shù)，求下列各程序段中的下劃線語(yǔ)句的執(zhí)行次數(shù)。(1)i=1;k=0while(i<=n-1)k+=10*i;i+;(2)for(inti=1;i<=n;i+)for(intj=1;j<=n;j+)cij=0;for(intk=1;k<=n;k+)cij=cij+aik*bkjx=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)集合(2)線性表77777)(2(3)樹,''

3、(4)圖4)解：1 n-1nnn2 ZZZ1=n3i=1j=1k=1ZZZ1=f£j更生i2+1fi，血±典。+nn±D(2) i±j±k壬i=tj=ti=t22t22622_n(n+1)(n+2)一61.3指出下列個(gè)算法的功能，并求其時(shí)間復(fù)雜度。解：Zi!,T(n)=O(n)y(2)vi!,T(n)=O(n2)iWintsum1(intn)(intp=1,s=0;for(inti=1;i<=n;i+)p*=i；s+=p;returns;intsum2(intn)ints=0;for(inti=1;i<=n;i+)intp=1;fo

4、r(intj=1;j<=i;j+)p*=j;s+=p;結(jié)束returns;1.4算法設(shè)計(jì)1枚是假的，偽幣與真幣重量略有不同。如何借用一架有3枚硬幣，其中有天平，找出偽幣？以流程圖表示算法。上機(jī)練習(xí)題要求：給出問題分析、算法描述、源程序及運(yùn)行截圖，在線提交。1.設(shè)a,b,c為3個(gè)整數(shù)，求其中位于中間值的整數(shù)。1.設(shè)計(jì)算法：在順序表中刪除值為e的兀素,否則，返回0。刪除成功，返回1;intSqlist<T>:DeleteElem(Te)for(i=1;i<=length;i+)/按值順序查找*i可從0開始if(elemi-1=e)/找到，進(jìn)行刪除操作for(j=i;j<

5、;length;j+)/ai至an依次前移Elemj-1=elemj;length-;/表長(zhǎng)減一return1;刪除成功，返回1)return0;/未找到，刪除不成功，返回0)>:Locate(Te)解：設(shè)表長(zhǎng)為n,等概率F,每個(gè)兀素被定位的概率為：p=1/n2.分析順序表中兀素te位算法intSqList<!的時(shí)間復(fù)雜度。定位成功第i個(gè)兀素，需比較i次'1.1",1n(n+1)n+1f(n)*iZi-ynn曰n223.對(duì)于有頭結(jié)點(diǎn)的單鏈表，分別寫出定位成功時(shí)，實(shí)現(xiàn)卜列定位語(yǔ)句序列。(1)定位到第i個(gè)結(jié)點(diǎn)ai；p=head;j=0;while(p&&

6、;j<i)p=p->next;j+;(2)定位到第i個(gè)結(jié)點(diǎn)的前驅(qū)a-i；p=head;j=0;while(p&&j<i-1)p=p->next;j+;(3)定位到尾結(jié)點(diǎn)；p=head;while(p->next)p=p->next;(4)定位到尾結(jié)點(diǎn)的前驅(qū)。p=head;while(p->next->next)p=p->next;4.描述一下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首兀結(jié)點(diǎn)。并給頭指針：是一個(gè)指針變量，里面存儲(chǔ)的是鏈表中首結(jié)點(diǎn)的地址，并以此來(lái)標(biāo)識(shí)一個(gè)鏈表。予圖示。頭結(jié)點(diǎn)：附加在第一個(gè)兀素結(jié)點(diǎn)之前的一個(gè)結(jié)點(diǎn)，頭指針指向

7、頭結(jié)點(diǎn)。首兀結(jié)點(diǎn)：指鏈表中的個(gè)兀素結(jié)點(diǎn)。頭指針頭結(jié)點(diǎn)首(元)結(jié)點(diǎn)尾(兀)結(jié)點(diǎn)ai|_+1a2.n1a|.對(duì)于無(wú)頭結(jié)點(diǎn)單鏈表，給出刪除第i個(gè)結(jié)點(diǎn)的算法描述。template<calssT>TLinkList<T>:Delete(inti).用教材定義的順序表的基本操作實(shí)現(xiàn)下列操作:template<calssT>intDeleteElem(SqListL,Te)template<calssT>TLinkList<T>:Delete(inti)在單鏈表上刪除第i個(gè)數(shù)據(jù)元素if(head=NULL)throw表空！”;/空表，不能刪else

8、if(i=1)/刪除第1個(gè)元素p=Head;x=p->data;/保存被刪元素值Head=p->next;deletep;)else/元素定位到第ai-ip=Head;j=1;/定位查找起始位置whilep->next&&j<i-1p=p->next;j+;if(!p->next|j>i-1);定位失敗throw刪除位置不合理”；else/定位成功，進(jìn)行結(jié)點(diǎn)刪除q=p->next;x=p>data;p->next=q->next;deleteq;retrunx;/返回被刪除元素值/#includeSqList.h

9、"template<calssT>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)，試寫出實(shí)現(xiàn)卜列功能的語(yǔ)句序列。(1)在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)；(2)在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)；(3)在表首插入S結(jié)點(diǎn)；(4)在表尾插入S結(jié)點(diǎn).【解】s->next=p->next;p->next=s;q=L;while(q->next!=p)q=q->next;s-&

10、gt;next=p或q->next;q->next=s;s->next=L->next;L->next=s;q=L;while(q->next!=NULL)q=q->next;s->next=q->next;q->next=s;上機(jī)練習(xí)題要求：給出問題分析、算法描述、源程序及運(yùn)行截圖，在線提交。編程實(shí)現(xiàn)：刪除單鏈表中值為e的兀素。解：325641可以154623不可以。第3章棧與隊(duì)列1.鐵路進(jìn)行列車調(diào)度時(shí)，常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)的站臺(tái)，如右圖所示。試問：若進(jìn)站的六輛列車順序如上所述，那么是否能夠得到325641和154623的出站序列

11、，如果不能，說(shuō)明為什么不能；如果能,說(shuō)明如彳5得到（即寫出"進(jìn)棧"或"出棧"的序列）。2.簡(jiǎn)述以下算法的功能(棧的兀素類型為int)。statusalgo_1(SqStackS)inti,n,A255;n=0;while(!S.StackEmpty()n+;An=S.Pop();for(i=1;i<=n;i+)S.Push(Ai);statusalgo_2(SqStackS,inte)SqStackT;intd;while(!S.tackEmpty()d=S.Pop();if(d!=e)T.Push(d);while(!T.StackEmpty()

12、d=T.Pop();T.Push(d);解：(1)借助一個(gè)數(shù)組，將棧中的兀素逆置。(2)借助棧T,將棧S中所有值為e的數(shù)據(jù)元素刪除之。3.編寫一個(gè)算法，將一個(gè)非負(fù)的十進(jìn)制整數(shù)N轉(zhuǎn)換為B進(jìn)制數(shù)，并輸出轉(zhuǎn)換后的結(jié)果。當(dāng)N=248D,B分別為8和16時(shí)，轉(zhuǎn)換后的結(jié)果為多少？#includeStack.h"intNumTrans(intN,intB)/十進(jìn)制整數(shù)N轉(zhuǎn)換為B進(jìn)制數(shù)stack<int>S;/建立一個(gè)棧while(N!=0)/N非零i=N%B;/從低到高，依次求得各位N=N/B;S.push(i);/各位入棧while(!S.StackEmpty()/棧不空i=S.po

13、p();If(i>9)i='A'+10-i;cout<<S.pop();/依次出棧，得到從高到低的輸出結(jié)果/#4借且棧，設(shè)計(jì)算法：假設(shè)一個(gè)算術(shù)表達(dá)式中包含（、”“后號(hào),解：以字符串存儲(chǔ)表達(dá)式，也可以邊輸入邊判斷。對(duì)一個(gè)合法的數(shù)學(xué)表達(dá)式來(lái)說(shuō)，括號(hào)"（和“）應(yīng)是相互匹配的。若匹配，返回1;否則，返回0。順序掃描表達(dá)式，左括號(hào)，入棧；右括號(hào)，如果此時(shí)?？眨硎径嘤依ㄌ?hào)，不匹配；如果棧不空，出棧一個(gè)左括號(hào)。掃描結(jié)束，如果?？?，表示括號(hào)匹配；否則，括號(hào)不匹配，多左括號(hào)。intblank_match(char*exp)用字符串存表達(dá)式SqStack<cha

14、r>s;/創(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è)字符/whileif(!s.StackEmpty()/表達(dá)式結(jié)束，棧不空return0;/小匹配，多左括號(hào)elsereturn1;/匹配/#5.簡(jiǎn)述棧和隊(duì)列的邏輯特點(diǎn)，各舉一個(gè)

15、應(yīng)用實(shí)例。6.寫出下列中綴表達(dá)式的后綴表達(dá)式。(1)-A+B-C+D(2)(A+B)*D+E/(F+A*D)+C(3)A&&B|!(E>F)A-B+C-D+AB+D*EFAD*+/+C+AB&&EF!|7.計(jì)算后綴表達(dá)式：45*32+-的值。解：158.將下列遞推過(guò)程改寫為遞歸過(guò)程。voidrecursion(intn)inti=n;while(i>1)cout<<i;i-;解：voidrecurision(intj)if(j>1)cour<<j;recurision(j-1);9.將下列遞歸過(guò)程改寫為非遞歸過(guò)程。voi

16、dtest(int&sum)intx;cin>>x;if(x=0)sum=0;elsetest(sum);sum+=x;cout<<sum;解：voidtest(int&sum)stackS;借助一個(gè)棧intx;cin>>x;while(x)S.push(x);cin>>x;sum=0;cout<<sum;while(x=S.pop()sum+=x;cout<<sum;"/10.簡(jiǎn)述以下算法的功能（棧和隊(duì)列的兀素類型均為int）。解：利用棧，將隊(duì)列中的兀素逆置voidalgo(Queue&

17、Q)(StackS;/創(chuàng)建一個(gè)棧intd;while(!Q.QueueEmpty()d=DeQueue(Q);S.Push(d);while(!S.StackEmpty()d=S.Pop();Q.EnQueue(d);12.假設(shè)以數(shù)組sem存放循環(huán)隊(duì)列的兀素，同時(shí)設(shè)變量rear和front分別作為隊(duì)首、隊(duì)尾指針，且隊(duì)首指針指向隊(duì)首前一個(gè)位置，隊(duì)尾指針指向隊(duì)尾兒素處，初始時(shí)，rear=fornt=-1。與出這樣設(shè)計(jì)的循環(huán)隊(duì)列入隊(duì)、出隊(duì)的算法。解：米用教材隊(duì)空與隊(duì)滿判別方法。為了區(qū)分隊(duì)空與隊(duì)滿條件，犧牲一個(gè)兀素空間。即：rear=front,為隊(duì)空；rear=(front+1)%m,為隊(duì)滿。tem

18、plate<calssT>voidEnQueue(TSe,Te,intm)/入隊(duì)if(rear+1)%m=fornt)/隊(duì)滿，不能插入throw隊(duì)滿，不能插入！”elserear=(rear+1)%m;/隊(duì)尾指針后移serear=e;/九素入隊(duì)return;/#template<calssT>TDnQueue(TSe,intm)/出隊(duì)if(rear=fornt)隊(duì)空，不能出隊(duì)！throw隊(duì)空，不能出隊(duì)！”elsefront=(front+1)%m;/指針后移，指向隊(duì)首元素e=sefront;/取隊(duì)首元素returne;/#上機(jī)練習(xí)題要求：給出問題分析、算法描述、源程序及

19、運(yùn)行截圖，在線提交。1.借助棧，實(shí)現(xiàn)單鏈表上的逆置運(yùn)算。第4章串.試問執(zhí)行以下函數(shù)會(huì)產(chǎn)生怎樣的輸出結(jié)果?voiddemonstrate()(StrAssign(s,'THISISABOOK');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="<

20、<t<<endl;cout<<“v="<<v;cout<<“u="<<StrRep(u,v,w);/demonstrate.設(shè)字符串S='aabaabaabaac',P='aabaac'1)給出S和P的next值和nextval值；2)若S作主串，P作模式串，試給出KMPB法的匹配過(guò)程。解：t=THESEAREBOOKSv=YXYw=XWXWXW1)S的next與nextval值分另為012123456789和002002002009,p的next與nextval值分另U為01

21、2123和0020032)利用KMPIT法的匹配過(guò)程：第趟匹配：aabaabaabaacaabaac(i=6,j=6)第二趟匹配：aabaabaabaac(aa)baac第三趟匹配：aabaabaabaac(成功)(aa)baac3.算法設(shè)計(jì)串結(jié)構(gòu)定義如下:structSString(char*data;/串首址intlen;/串長(zhǎng)intStrSize;/存放數(shù)組的最大長(zhǎng)度.)；(1)編寫一個(gè)函數(shù)，計(jì)算一個(gè)子串在一個(gè)字符串中出現(xiàn)的次數(shù)，如果/、出現(xiàn)，則為0。intstr_count(SStringS,SStringT)解：intstr_count(SStringS,SStringT)inti,

22、j,k,count=0;for(i=0;S.datai;i+)for(j=i,k=0;(S.dataj=T.datak;j+,k+)if(k=T.len-1)count+;)returncount;)(2)編寫算法，從串s中刪除所有和串t相同的子串。解：intSubString_Delete(SString&s,SStringt)從串s中刪除所有與t相同的子串，并返回刪除次數(shù)for(n=0,i=0;i<=s.len-t.len;i+)for(j=0;j<t.len&&si+j=ti;j+);if(j>t.len)找至ij了與t匹配的子串for(k=i;

23、k<s.len-t.len;k+)sk=sk+t.len;/左移刪除s.len-=t.len;n+;被刪除次數(shù)增1/forreturnn;/Delete_SubString(2)編寫一個(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(i<s.len)j=0;/作為掃描t的指針while(j<t.len)if(s.datai=t.dataj)/序號(hào)為i,長(zhǎng)

24、度為len2的子串len2=1;/開始計(jì)數(shù)for(k=1;s.datai+k=t.dataj+k&&s.datai+k!=NULL;k+)len2+;if(len2>len1)/將較大長(zhǎng)度者給index和len1index=i;len1=len2;j+=len2;/ifelsej+;/whilecout<<”最長(zhǎng)公共子串：for(i=0;i<len1;i+;)cout<<s.dataindex+1;/#1.已知下列字符串a(chǎn)='THIS',f='ASAMPLE',c='GOOD',d='N

25、E',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(StrSub(c,3,1),d),g='IS',v=StrConcat(s,StrConcat(b,StrConcat(t,StrConcat(b,u),試問：s,t,v,StrLength(s),StrIndex(v,g),StrIndex(u,g)各是什么？已知：s='(XYZ)+*',t='(X+Z)*Y

26、'。試?yán)孟铝羞\(yùn)算，將s轉(zhuǎn)化為t。聯(lián)接：StrConcat(&S,T)求子串：(char*)StrSub(S,i,len)置換：StrRep(&S,T,R)上機(jī)練習(xí)題要求：給出問題分析、算法描述、源程序及運(yùn)行截圖，在線提交。串結(jié)構(gòu)定義如下：structSStringchar*data;/串首址intlen;/串長(zhǎng)intStrSize;/存放數(shù)組的最大長(zhǎng)度.;求：串S所含不同字符的總數(shù)和每種字符的個(gè)數(shù)，不區(qū)分英文字母的大小寫。1.假設(shè)有二維數(shù)組A6如每個(gè)兀素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置(基地址)為1000,計(jì)算：數(shù)組A的體積(即存儲(chǔ)量);(

27、2)數(shù)組A的最舟-個(gè)元素357的第一個(gè)字節(jié)的地址；(3)按行存儲(chǔ)時(shí)，元素ai4的第一個(gè)字節(jié)的地址；(4)按列存儲(chǔ)時(shí)，元素347的第一個(gè)字節(jié)的地址。解：(1)6X8X6=288Byte1000+288-6=1282;1000+(1X8+4)X6=10721000+(7X6+4)X6=12762.假設(shè)按低下標(biāo)優(yōu)先存儲(chǔ)整數(shù)數(shù)組A9X3馮4時(shí)，A個(gè)兀素的字節(jié)地址是100,每個(gè)整數(shù)占四個(gè)字節(jié)。1可下列元素的存儲(chǔ)地址是什么？(1)30000(2)38247解：(1)100(2)100+8X3X5X8+2>5X8+4X8+7=45003.一個(gè)稀疏矩陣如圖所示_030000020500(1)給出三元組存儲(chǔ)示意圖；A=000000(2)給出帶行指針向量的鏈?zhǔn)酱鎯?chǔ)示意圖；90000144(3)十字鏈表存儲(chǔ)示意圖。M.dataijeA01234013112-h013A135112235A309A351309451AM.muM.nuM.tu465(2)A.cheadA.rheadI卜Amu4r131A.nu61112I1135A.tu5AAA八(3)3I|9_31A卜-第5章數(shù)組與壓縮矩陣013112135309351013A112309