數(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 = a1，a2，a 3，a4 ， 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>

2、;，<3，4>，<3，5>，<3，6>，<4，5>，<4，6>(1) 集合(2) 線性表 (3) 樹(shù) (4) 圖 1.2 設(shè)n為正整數(shù)，求下列各程序段中的下劃線語(yǔ)句的執(zhí)行次數(shù)。(1) i=1; k=0while(i<=n-1)k+=10*i ;i+;(2) for (int i=1; i<=n; i+)for (int j=1; j<=n; j+) cij=0; for (int k=1; k<=n; k+) cij=cij+aik*bkj解：(1) n-1 (2) (3) x=0; y=0;for (int

3、i=1; i<=n; i+)for (int j=1; j<=i; j+)for (int k=1; k<=j; k+) x=x+y;(3) 1.3 指出下列個(gè)算法的功能，并求其時(shí)間復(fù)雜度。(1) int sum1(int n)int p=1,s=0;for (int i=1;i<=n; i+) p*= i; s+=p;return s;(2) int sum2 (int n) int s=0;for ( int i=1; i<=n; i+) int p=1;for (int j=1; j<=i; j+) p*=j;s+=p;return s;解：(1) ,

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

5、行刪除操作 for ( j=i; j<length; j+) / ai至an依次前移 Elemj-1 = elemj; length - - ; / 表長(zhǎng)減一 return 1 ; /刪除成功，返回 1 return 0 ; / 未找到，刪除不成功，返回 02. 分析順序表中元素定位算法 int SqList<T>:Locate ( T e ) 的時(shí)間復(fù)雜度。解：設(shè)表長(zhǎng)為n，等概率下，每個(gè)元素被定位的概率為：p=1/n定位成功第i個(gè)元素，需比較i次3.對(duì)于有頭結(jié)點(diǎn)的單鏈表，分別寫出定位成功時(shí)，實(shí)現(xiàn)下列定位語(yǔ)句序列。 (1) 定位到第i個(gè)結(jié)點(diǎn)ai；p=head; j=0;whi

6、le ( p && j<i ) p=p->next; j+;(2) 定位到第i個(gè)結(jié)點(diǎn)的前驅(qū)ai-1；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ǔ)的是鏈表中首

7、結(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)。5. 對(duì)于無(wú)頭結(jié)點(diǎn)單鏈表，給出刪除第i個(gè)結(jié)點(diǎn)的算法描述。 template <calss T> T LinkList<T>:Delete(int i)template <calss T> T LinkList<T>:Delete(int i) / 在單鏈表上刪除第i個(gè)數(shù)據(jù)元素 if ( head=NULL) throw “表空!”; / 空表，不能刪 else if ( i=1) / 刪除第1個(gè)元素 p=Head;

8、x=p->data; / 保存被刪元素值Head= p->next ; delete p ; else / 元素定位到第ai-1 p=Head; j=1 ; / 定位查找起始位置 while p->next && j<i-1 p=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; delete q; retrun x; / 返回

9、被刪除元素值 /#6. 用教材定義的順序表的基本操作實(shí)現(xiàn)下列操作： template <calss T> int DeleteElem(SqList L, T e)#include “SqList.h“template <calss T> int DeleteElem(SqList L, T e) / i = 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ǔ)句序列。

10、(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;(3) q=L;while( q->next!=NULL) q=q->next;s->next= q->next ; q->

11、;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)站的六輛列車順序如上所述, 那么是否能夠得到325641和154623的出站序列, 如果不能, 說(shuō)明為什么不能; 如果能, 說(shuō)明如何得到(即寫出"進(jìn)棧"或"出棧"的序列)。解：325641 可以 154623不可以。2. 簡(jiǎn)述以下算法的功能（棧的元素類型為 int ）。(1) status algo_1( SqStack S ) int i,

12、 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); while (!T.StackEmpty() d=T.Pop();T.Push(d); 解：(1) 借助一個(gè)數(shù)組，將棧中的元素逆置。(2) 借助棧T，將棧S中所有值為e的數(shù)據(jù)元素刪除之。3.編寫

13、一個(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.h”int NumTrans( int N, int B) /十進(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.pop(); If (i>9) i=A+10-i; cout<< S.pop()

14、; / 依次出棧，得到從高到低的輸出結(jié)果/#4 借且棧，設(shè)計(jì)算法：假設(shè)一個(gè)算術(shù)表達(dá)式中包含“(”、“)”括號(hào)，對(duì)一個(gè)合法的數(shù)學(xué)表達(dá)式來(lái)說(shuō)，括號(hào)“(”和“)”應(yīng)是相互匹配的。若匹配，返回1；否則，返回0。解：以字符串存儲(chǔ)表達(dá)式，也可以邊輸入邊判斷。 順序掃描表達(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<char> s; / 創(chuàng)建一個(gè)棧 char *p=exp; / 工作指針p指向表達(dá)式首

15、while ( *p!=) / 不是表達(dá)式結(jié)束符 switch(p) case (: /左括號(hào)，入棧 s.push(ch); break; case ) / 右括號(hào) if (s.StackEmpty() return 0; / ?？眨黄ヅ?，多右括號(hào) else s.Pop(); break; / 左括號(hào)出棧 /switch p+; / 取表達(dá)式下一個(gè)字符 / while if (!s.StackEmpty() / 表達(dá)式結(jié)束，棧不空 return 0 ; /不匹配，多左括號(hào) else return 1 ; / 匹配 /#5. 簡(jiǎn)述棧和隊(duì)列的邏輯特點(diǎn)，各舉一個(gè)應(yīng)用實(shí)例。6. 寫出下列中綴表達(dá)式的

16、后綴表達(dá)式。(1)-A+B-C+D(2)(A+B)*D+E/(F+A*D)+C(3) A&&B|!(E>F)(1) A-B+C-D+(2) AB+D*EFAD*+/+C+(3) AB&&EF ! |7.計(jì)算后綴表達(dá)式：4 5 * 3 2 + - 的值。解：158.將下列遞推過(guò)程改寫為遞歸過(guò)程。void recursion( int n ) int i=n; while( i>1) cout<<i; i-; 解：void recurision(int j) if (j>1) cour<<j; recurision(j-1)

17、; 9. 將下列遞歸過(guò)程改寫為非遞歸過(guò)程。void test( int &sum) int x;cin>>x;if (x=0) sum=0;else test(sum); sum+=x; cout<<sum;解：void test (int &sum) stack S; /借助一個(gè)棧 int x; cin>>x;while (x) S.push(x); cin>>x; sum=0; cout<<sum;while ( x=S.pop() ) sum+=x; cout<<sum; /10. 簡(jiǎn)述以下算法的功能

18、（棧和隊(duì)列的元素類型均為 int）。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); 解：利用棧，將隊(duì)列中的元素逆置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ì)滿判

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

20、if ( rear= =fornt ) /隊(duì)空，不能出隊(duì)!throw “隊(duì)空，不能出隊(duì)!” 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é)果?void demonstrate( ) StrAssign( s, 'THIS IS A BOOK');StrRep ( s, StrSub(s, 3, 7), 

21、9;ESE ARE');StrAssign( t, StrConcat ( s, 'S' ) ) ;StrAssign(u, 'XYXYXYXYXYXY' );StrAssign(v, StrSub ( u, 6, 3 ) );StrAssign(w, 'W');cout<<“'t=”<< t<<endl;cout<<“v=”<< v;cout<<“u=”<< StrRep(u, v, w); / demonstrate解：t= THESE ARE

22、 BOOKSv= YXYw= XWXWXW2.設(shè)字符串S=aabaabaabaac'，P=aabaac'1）給出S和P的next值和nextval值；2）若S作主串，P作模式串，試給出KMP算法的匹配過(guò)程。p的next與nextval值分別為012123和0020032）利用KMP算法的匹配過(guò)程： 第一趟匹配：aabaabaabaac aabaac(i=6,j=6) 第二趟匹配：aabaabaabaac (aa)baac 第三趟匹配：aabaabaabaac (成功) (aa)baac3. 算法設(shè)計(jì)串結(jié)構(gòu)定義如下：struct SString char *data； / 串首址

23、 int len; / 串長(zhǎng) int StrSize； / 存放數(shù)組的最大長(zhǎng)度. ;(1) 編寫一個(gè)函數(shù)，計(jì)算一個(gè)子串在一個(gè)字符串中出現(xiàn)的次數(shù)，如果不出現(xiàn)，則為0。int str_count (SString S, SString T )解：int str_count (SString S, SString T) int i, 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 + +; return count;(2) 編寫算法，從串s中刪

24、除所有和串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 && si+j=ti; j+);    if (j > t.len) /找到了與t匹配的子串    

25、0;     for ( k = i; k<s.len-t.len; k+ ) sk=sk+t.len; /左移刪除      s.len-=t.len ;n+; / 被刪除次數(shù)增1      /for  return n;/Delete_SubString(2) 編寫一個(gè)函數(shù)，求串s和串t 的一個(gè)最長(zhǎng)公共子串。void maxcomstr( SString *s, SString *t)解：void

26、 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 < t.len ) if (s.datai = = t.dataj ) / 序號(hào)為i，長(zhǎng)度為len2的子串 len2 =1; / 開(kāi)始計(jì)數(shù) for ( k=1; s.datai+k=t.dataj+k && s.datai+k!=NULL; k+ ) len2+; if ( len2>len1) / 將較

27、大長(zhǎng)度者給index和len1 index=i; len1=len2; j + = len2; /if else j+; /while cout<<”最長(zhǎng)公共子串：” for ( i=0; i<len1; i+; ) cout<<s.dataindex+1; / #1. 已知下列字符串a(chǎn) = 'THIS', f = 'A SAMPLE', c = 'GOOD', d ='NE', b = ' ', s = StrConcat(a,StrConcat(StrSub(f,2,7),StrC

28、oncat(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),試問(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 ( &

29、amp;S,T )求子串：(char *) StrSub( S, i, len ) 置換：StrRep ( &S, T, R )上機(jī)練習(xí)題要求：給出問(wèn)題分析、算法描述、源程序及運(yùn)行截圖，在線提交。串結(jié)構(gòu)定義如下：struct SString char *data； / 串首址 int len; / 串長(zhǎng) int StrSize； / 存放數(shù)組的最大長(zhǎng)度. ;求：串S所含不同字符的總數(shù)和每種字符的個(gè)數(shù)，不區(qū)分英文字母的大小寫。第5章 數(shù)組與壓縮矩陣1. 假設(shè)有二維數(shù)組 A6×8，每個(gè)元素用相鄰的 6 個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知 A 的起始存儲(chǔ)位置(基地址)為 1000，

30、計(jì)算：(1) 數(shù)組 A 的體積（即存儲(chǔ)量）;(2) 數(shù)組 A 的最后一個(gè)元素 a57 的第一個(gè)字節(jié)的地址;(3) 按行存儲(chǔ)時(shí)，元素 a14 的第一個(gè)字節(jié)的地址;(4) 按列存儲(chǔ)時(shí)，元素 a47 的第一個(gè)字節(jié)的地址。 解：(1）6×8×6 = 288Byte(2）1000+288-6=1282；(3）1000+(1×8+4)×6=1072(4）1000+(7×6+4)×6=12762. 假設(shè)按低下標(biāo)優(yōu)先存儲(chǔ)整數(shù)數(shù)組A9×3×5×8時(shí)，第一個(gè)元素的字節(jié)地址是 100，每個(gè)整數(shù)占四個(gè)字節(jié)。問(wèn)下列元素的存儲(chǔ)地址是什么？(1) a0000 (2) a8247解：(1) 100 (2) 100+8×3×5×8+2×5×8+4×8+7=45003一個(gè)稀疏矩陣如圖所示(1) 給出三元組存儲(chǔ)示意圖；(2) 給出帶行指針向量的鏈?zhǔn)酱鎯?chǔ)示意圖；(3) 十字鏈表存儲(chǔ)示意圖。(1) (2)(3) 4. 算法設(shè)計(jì)：一個(gè)按行優(yōu)先存儲(chǔ)的n*n矩陣，就地轉(zhuǎn)置。解