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

1、.專業(yè).專注.word可編輯第1章緒1.1后卜列兒種二兀組表上的數(shù)據(jù)結(jié)構(gòu)，試畫出它們分別對(duì)應(yīng)的圖形表示，并指出它們分別屬于何種結(jié)構(gòu)。(1) A= ( D , R ),其中，D = a i, a2, a 3, a，, 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

2、 = 1 , 2,3, 4, 5, 6,R= , , , , , , , 1.2設(shè)n為正整數(shù)，求卜列各程序段中的下劃線語(yǔ)句的執(zhí)行次數(shù)。(1) i=1; k=0(2) for (int i=1; i=n; i+)while(i=n-1)for (int j=1; j=n; j+)(1)集合(；：$一展(金(3(2)線性表 j j u 7 72/占)p5(3)樹f (4)圖%?解：(1) n-1k+=10*i ;i+； ci j=0；for (int k=1; k=n; k+)ci j=cij+aik*bkjn n n(2) Z Z Z 1 = n3ijV k x=0;y=0;for (int i

3、=1; i=n; i+)for (int j=1; j=i; j+)for (int k=1; k=j; k+) x=x+y;上31Hz j=i2i J .n(n+1)(2n+-(3) j止k壬jm im 22 T2 廿 2622_n(n+1)(n+2)61.3指出下列個(gè)算法的功能，并求其時(shí)間復(fù)雜度。 int sum1(int n)(2) int sum2 (int n) int s=0;解：int p=1,s=0;for (int i=1;i=n; i+) p*= i; s+=p;return s;for ( int i=1; i=n; i+) int p=1;for (int j=1; j

4、=i; j+) p*=j;s+=p;return s; Z i! , T(n)=O(n)i(2)工 i! , T(n)=O(n 2)i1.4算法設(shè)計(jì)有3枚硬幣，其中后1枚是假的，偽幣與真幣重量略有小何。如何借用一架 天平，找出偽幣？以流程圖表示算法。開始:1日是 A=B ?:一C是偽幣工是:A=C ?Bze偽幣否A是偽幣L尸結(jié)束上機(jī)練習(xí)題要求：給出問(wèn)題分析、算法描述、源程序及運(yùn)行截圖，在線提交。1.設(shè)a, b, c為3個(gè)整數(shù)，求其中位于中間值的整數(shù)。第2章線性表1.設(shè)計(jì)算法：在順序表中刪除值為e的元素，刪除成功，返回1;否則，返回0。int Sqlist:DeleteElem( T e ) f

5、or (i=1; i=length; i+) 按值順序查找* i可從0開始if (elemi-1= =e)/ 找到，進(jìn)行刪除操作 for ( j=i; jlength; j+)/ ai 至 an 依次前移Elemj-1 = elem j;length - - ;/ 表長(zhǎng)減一return 1 ;/刪除成功，返回1return 0 ;/未找到，刪除不成功，返回02.分析順序表中兀素te位算法int SqList:Locate ( Te )的時(shí)間復(fù)雜度。解：設(shè)表長(zhǎng)為n,等概舉下，每個(gè)元素被定位的概率為：p=1/n定位成功第i個(gè)元素,需比較i次，1 .1J .1 n(n + 1) n + 1f (n)

6、- *i =一工 i = =y nn y n223.對(duì)于有頭結(jié)點(diǎn)的單鏈表，分別寫出定位成功時(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ū)am ;p=head; j=0;while ( p & jnext; 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è)指針變量，里面存

7、儲(chǔ)的是鏈表中首結(jié)點(diǎn)的地址，并以此來(lái)標(biāo)識(shí)一個(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).a5.對(duì)于無(wú)頭結(jié)點(diǎn)單鏈表，給出刪除第i個(gè)結(jié)點(diǎn)的算法描述。template T LinkList:Delete(int i)template T LinkList:Delete(int i)if ( head=NULL) throwelse if ( i=1) /在單鏈表上刪除第i個(gè)數(shù)據(jù)元素表空！”; 空表，不能刪刪除第1個(gè)元素p=Head; x=p-data;/保存被刪元素值Head= p-next ;delete p ;else

8、 / 元素定位到第ai-ip=Head; j=1 ; /定位查找起始位置while p-next & jnext; j+ ; if ( !p-next | ji-1 ); /throw刪除位置不合理”；else /定位成功，進(jìn)行結(jié)點(diǎn)刪除q=p-next;x=pdata;p-next=q-next;delete q;retrun x; /返回被刪除元素值/#6.用教材定義的順序表的基本操作實(shí)現(xiàn)下列操作#include SqList.h template template int DeleteElem(SqList L, T e)int DeleteElem(SqList L, T e) /i =

9、 L.LocateElem(e) ; /按值查找if (!i)/未找到return 0;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).解】(1) s-next=p-next; p-next=s;(2) q=L;while( q-next!=p)q=q-next;s-next=p 或 q-next ;q -next=s;(3) s-next=L-next; L-next=s; q=

10、L；while( q-next!=NULL)q=q-next;s-next= q-next ; q-next=s;上機(jī)練習(xí)題要求：給出問(wèn)題分析、算法描述、源程序及運(yùn)行截圖，在線提交。編程實(shí)現(xiàn)：刪除單鏈表中值為 e的元素。第3章棧與隊(duì)列1.鐵路進(jìn)行列車調(diào)度時(shí)，常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)的站臺(tái)，如右圖所示。試問(wèn)：若進(jìn)站的六輛列車順序如上所述123456解：325641可以154623不可以。那么是否能夠得到 325641和154623的出站序列,如果不能,說(shuō)明為什么不能；如果能，說(shuō)明如彳5得到（即寫出進(jìn)?；虺鰲５?序列）。2.簡(jiǎn)述以下算法的功能(棧的元素類型為int )。 status algo_1(

11、 SqStack S ) int i, n, A 255;n=0;while (!S.StackEmpty() ) n+; An= S.Pop(); for ( i=1; i= n ; i+) S.Push(Ai);(2) status algo_2(SqStack S, int e) SqStack T;int d;while (!S.tackEmpty() d = S.Pop();if (d!=e ) T.Push(d); 解：(1)借助一個(gè)數(shù)組，將棧中的元素逆置。(2)借助棧T,將棧S中所有值為e的數(shù)據(jù)元素刪除之。while (!T.StackEmpty() d=T.Pop();T.Pu

12、sh(d); 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é)果為多少？#include Stack.hint NumTrans( int N, int B)/十進(jìn)制整數(shù) N轉(zhuǎn)換為B進(jìn)制數(shù)stack S; / 建立一個(gè)棧while( N!=0) / N 非零i=N%B ;/從低到高，依次求得各位N=N/B;S.push(i); / 各位入棧while ( !S.StackEmpty() 棧不空 i= S.pop()；If (i9) i= A+10-i;cout S.pop(); /依次出棧，得到從高到低的輸出結(jié)果

13、/#4借且棧，設(shè)計(jì)算法：假設(shè)一個(gè)算術(shù)表達(dá)式中包含解：以字符串存儲(chǔ)表達(dá)式，也可以邊輸入邊判斷號(hào)，對(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)。int blank_match(char *exp)用子符串存表達(dá)式SqStack s;/ 創(chuàng)建一個(gè)棧char *p=exp; /工作指針p指向表達(dá)式首while ( *p!= =) /不是表達(dá)式結(jié)束符switch(p) case (: /左括號(hào),入棧s.p

14、ush(ch); break;case ) / 右括 pif (s.StackEmpty() return 0;/ 棧空,不匹配,多右括號(hào)else s.Pop(); break; 左括號(hào)出棧switchp+; 取表達(dá)式下一個(gè)字符/ whileif (!s.StackEmpty()/表達(dá)式結(jié)束,棧不空return 0 ; /小匹配，多左括號(hào)elsereturn 1 ; / 匹配/#5.簡(jiǎn)述棧和隊(duì)列的邏輯特點(diǎn)，各舉一個(gè)應(yīng)用實(shí)例。6.寫出下列中綴表達(dá)式的后綴表達(dá)式。-A+B-C+D(2)(A+B)*D+E/(F+A*D)+C(3) A&B|!(EF)(1) A-B+C-D+(2) AB+D*EFAD

15、*+/+C+(3) AB&EF ! |7.計(jì)算后綴表送式：4 5 * 3 2 + - 的值。解：158.將下列遞推過(guò)程改寫為遞歸過(guò)程。void recursion( int n )int i=n;while( i1) cout1) courx;if (x=0) sum=0;else test(sum); sum+=x; 解:void test (int &sum) stack S; 借助一個(gè)棧int x;cinx;while (x) S.push(x);cinx; coutsum;sum=0;coutsum;while ( x=S.pop() ) sum+=x; coutsum; /10.簡(jiǎn)述

16、以下算法的功能（棧和隊(duì)列的元素類型均為int)。解：利用棧,將隊(duì)列中的元素逆置void algo (Queue & Q)Stack S; 創(chuàng)建一個(gè)棧 int d;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ì)

17、空與隊(duì)滿判別方法。為了區(qū)分隊(duì)空與隊(duì)滿條件，犧牲一個(gè)元素空間。即：rear=front , 為隊(duì)空；rear=(front+1)%m ,為隊(duì)滿。template void EnQueue( T Se, T e, int m ) 入隊(duì)if ( rear+1)%m =fornt )隊(duì)滿，不能插入throw 隊(duì)滿，不能才1入！”else rear = (rear+1) % m ; /隊(duì)尾指針后移serear=e; /九素入隊(duì)return ;/#template T DnQueue( T Se口，int m )/ 出隊(duì)if ( rear= =fornt )/ 隊(duì)空，不能出隊(duì)！throw 隊(duì)空，不能出隊(duì)！

18、”else front = (front+1)%m ;/指針后移，指向隊(duì)首元素e =sefront; 取隊(duì)return e ;/#上機(jī)練習(xí)題要求：給出問(wèn)題分析、算法描述、源程序及運(yùn)行截圖，在線提交。1.借助棧，實(shí)現(xiàn)單鏈表上的逆置運(yùn)算 。第4章串1.試問(wèn)執(zhí)行以下函數(shù)會(huì)產(chǎn)生怎樣的輸出結(jié)果解：t= THESE ARE BOOKSvoid demonstrate()v= YXYw= XWXWXWStrAssign( s, THIS IS A BOOK);StrRep ( s, StrSub(s, 3, 7), ESE ARE);StrAssign( t, StrConcat ( s, S);StrAs

19、sign(u, XYXYXYXYXYXY);StrAssign(v, StrSub ( u, 6, 3 );StrAssign(w, W);cout t= tendl;cout v= v;cout u= StrRep(u, v, w); / demonstrate2.設(shè)字符串 S= aabaabaabaac , P= aabaac1）給出S和P的next值和nextval值；2）若S作主串，P作模式串，試給出KMP算法的匹配過(guò)程。1) S 的 next 與 nextval 值分另為 012123456789 和 002002002009 ,p的next與nextval值分另為 012123和0

20、020032)利用KMP算法的匹配過(guò)程：趟匹配：aabaabaabaacaabaac(i=6,j=6)第二趟匹配：aabaabaabaac(aa)baac第三趟匹配 ：aabaabaabaac(成功)(aa)baac3.算法設(shè)計(jì)串結(jié)構(gòu)定義如下：struct SStringchar *data ；/ 串首址int len; / 串長(zhǎng)int StrSize ; /存放數(shù)組的最大長(zhǎng)度；如果不出現(xiàn)，則為0。(1)編寫一個(gè)函數(shù)，計(jì)算一個(gè)子串在一個(gè)字符串中出現(xiàn)的次數(shù)， 解：int str_count (SString S, SString T) for ( i=0; S.datai; i+)int i,

21、j,k, count=0;int str_count (SString S, SString T )for ( j=i, k=0; (S.dataj=T.datak; j+,k+) if ( k= =T.len-1)count + +;return count;(2)編寫算法，從串s中刪除所有和串t相同的子串。解：int SubString_Delete(SString &s, SString t )從串s中刪除所有與t相同的子串，并返回刪除次數(shù)for ( n=0, i=0; i=s.len-t.len; i+ )for ( j=0; j t.len) 找到了與t匹配的子串for ( k =

22、i; ks.len-t.len; k+ )sk=sk+t.len; /左移刪除5.1 en-=t.len ;n+; 被刪除次數(shù)增1 /forreturn n;Delete_SubString(2)編寫一個(gè)函數(shù)，求串s和串t的一個(gè)最長(zhǎng)公共子串解：void maxcomstr( SString *s, SString *t) void maxcomstr( SString *s, SString *t)int index=0,len1=0, i,j,k,len2;i=0;/作為掃描s的指針while ( i s.len) j = 0;/作為掃描t的指針while ( j len1) 將較大長(zhǎng)度者給

23、 index和lenlindex=i;len1=len2;j + = len2;/if else j+;/whilecout ”最長(zhǎng)公共子串for ( i=0; ilen1; i+;)couts.dataindex+1;/ #1.已知下列字符串a(chǎn) = THIS, f = A SAMPLE, 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(StrSub(c,3,1),d), g

24、= 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)化 為t。聯(lián)接：StrConcat ( &S,T )求: (char *) StrSub( S, i, len )置換：StrRep ( &S, T, R )上機(jī)練習(xí)題要求：給出問(wèn)題分析、算法描述、源程序及運(yùn)行截圖，在線提交。串結(jié)構(gòu)定義如下：struct SStringchar *da

25、ta ;串首址int len;/ 串長(zhǎng)int StrSize ; /存放數(shù)組的最大長(zhǎng)度.;求：串S所含不同字符的總數(shù)和每種字符的個(gè)數(shù)，/、區(qū)分英文字母的大小寫。第5章數(shù)組與壓縮矩陣1.假設(shè)有二維數(shù)組A6X8,每個(gè)元素用相鄰的 6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按解：（1） 6X8X6 = 288Byte字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000,計(jì)算：數(shù)組A的體積（即存儲(chǔ)量）（2）數(shù)組A的最后一個(gè)元素a57的第一個(gè)字節(jié)的地址（3）按行存儲(chǔ)時(shí)，元素a14的第一個(gè)字節(jié)的地址（4）按列存儲(chǔ)時(shí)，元素a47的第一個(gè)字節(jié)的地址(2) 1000+288-6=1282(3) 1000+(1 X8+4) X6=1072(4) 1000+(7 X6+4) X6=12762.假設(shè)按低下標(biāo)優(yōu)先存儲(chǔ)整數(shù)數(shù)組A9 X 3X5 X時(shí)，第一個(gè)元素的字節(jié)地址解：（1）100是100,每個(gè)整數(shù)占四個(gè)字節(jié)。問(wèn)下列元素的存儲(chǔ)地址是什么 a 0000(2) a 8247(