大數(shù)據(jù)的結(jié)構(gòu)習(xí)地的題目

1、第1章緒1.1有下列幾種二兀組表示的數(shù)據(jù)結(jié)構(gòu),試畫出它們分別對應(yīng)的圖形表示，(1)集合并指出它們分別屬于何種結(jié)構(gòu)。（1） A= （ D，R ），其中，D = a 1，a?.a 3，at ，R= 線性表(2) B= ( D，R )，其中，D = a，b，c，d，e，R= （a，b），（b，c），(c， d)，1 2(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） K= （ D ，R ），其中，D = 1，2, 3，4，5，6，R= ， ， ， ， ， ， 樹丄圖1.2設(shè)n為正整數(shù)，求下列

2、各程序段中的下劃線語句的執(zhí)行次數(shù)。(1) i=1; k=0(2) for (in t i=1; i=n; i+)解:while(i=n-1)for (int j=1; j=n; j+)(1) n-1 cij=0;n nn:仁n3k+=10*i ;for (i nt k=1; k=n; k+)i+;cij=cij+aik*bkji =1 j mkT(3) x=0;y=0;n i jEEEn in仁送送j乏i(i+1) 一 1卄+匸1 .n( n+1)(2 n+1)+ 1 . n(n+1)for (int i=1; i=n; i+)i=t j=t ki zi2 2-2 i亠2 6 2 2for (

3、int j=1; j=i; j+)n(n +1)( n*2)for (int k=1; k=j; k+)6x=x+v;1.3指出下列個算法的功能，并求其時間復(fù)雜度。(1) int sum1(i nt n)int p=1,s=0;for (int i=1;i=n; i+) p*= i； s+=p; return s; 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;解：n(1) i! , T(n)=0(n)n i!,T(n)=O(n2)iV結(jié)束return s;1

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

5、mj-1 = elemj;length - - ;/ 表長減一return 1 ;刪除成功，返回1return 0 ;/未找到，刪除不成功，返回02.分析順序表中兀素疋位算法int SqList:Locate ( T e )的時間復(fù)雜度。解：設(shè)表長為n,等概率下，每個兀素被定位的概率為：p-1/n疋位成功第i個兀素，需比較i次、二 1 .1.1 n(n + 1) n + 1f (n) _遲_ 遲 i -im nn i二n223對于有頭結(jié)點的單鏈表，分別寫出定位成功時，實現(xiàn)下列定位 語句序列。(1)定位到第i個結(jié)點ai ；p=head; j=0;while ( p & jn ext; j+;定位

6、到第i個結(jié)點的前驅(qū)a-1 ；p=head; j=0;while ( p & j next; j+;(3)定位到尾結(jié)點；p=head;while ( p -next )p=p-n ext;(4)定位到尾結(jié)點的前驅(qū)。p=head;while ( p-n ext- next )p=p-n ext;4描述一下二個概念的區(qū)別：頭指針，頭結(jié)點，首兀結(jié)點。并給頭指針：是一個指針變量，里面存儲的是鏈表中首結(jié)點的地址，并以此來標(biāo)識一個鏈表。予圖示。頭結(jié)點：附加在第一個兀素結(jié)點之前的一個結(jié)點，頭指針指向頭結(jié)點。首兀結(jié)點：指鏈表中的第一個兀素結(jié)點。頭指針頭結(jié)點首(元)結(jié)點尾(元)結(jié)點aia少丨Tn a5.對于無頭結(jié)

7、點單鏈表，給出刪除第i個結(jié)點的算法描述。template T LinkList:Delete(int i)template T LinkList:Delete(int i) /在單鏈表上刪除第i個數(shù)據(jù)元素if ( head=NULL) throw 表空！”;/ 空表，不能刪 else if ( i=1) /刪除第1個兀素p=Head; x=p-data;/保存被刪兀素值Head= p-n ext ;delete p ;else /兀素疋位到第 ai-1p=Head; j=1 ; /疋位查找起始位置while p- next & jn ext; j+ ; if ( !p- next | ji-1

8、 ); /定位失敗throw刪除位置不合理；else /定位成功，進行結(jié)點刪除q=p-n ext;x=pdata;p-n ext=q-n ext; delete q;retrun x; /返回被刪除兀素值/#6.用教材定義的順序表的基本操作實現(xiàn)下列操作： template int DeleteElem(SqList L, T e)#include SqList.h “ template int DeleteElem(SqList L, T e) /i = L.LocateElem(e) ; / 按值杳找if (!i)/未找到return 0;else/找到delete (i) ; /刪除被找到

9、的元素 7.已知L是有表頭結(jié)點的單鏈表，且P結(jié)點既不是首兀結(jié)點，也不是尾結(jié)點，試寫出實現(xiàn)下列功能的語句序列。(1) 在P結(jié)點后插入S結(jié)點；(2) 在P結(jié)點前插入S結(jié)點；(3) 在表首插入S結(jié)點；(4) 在表尾插入S結(jié)點.【解】(1) s-next=p-next; p-next=s; q=L;while( q-n ext!=p)q=q-n ext;s-next=p 或 q-next ;q _n ext=s;(3) s-n ext=L-n ext; L-n ext=s; q=L;while( q-n ext!=NULL)q=q-n ext;s-n ext= q-n ext ; q-n ext=s;

10、上機練習(xí)題要求：給出問題分析、算法描述、源程序及運行截圖，在線提交。編程實現(xiàn)：刪除單鏈表中值為e的兀素。第3章棧與隊列1.鐵路進行列車調(diào)度時，常把站臺設(shè)計 成棧式結(jié)構(gòu)的站臺，如右圖所示。試問： 若進站的六輛列車順序如上所述,那么是否能夠得到325641和154623的出站序 列，如果不能，說明為什么不能；如果能, 說明如何得到（即寫出”進?！被颉背鰲！钡?序列）。2.簡述以下算法的功能(棧的兀素類型為int )。 status algo_1( SqStack S ) int i, n, A 255;n=0;while (!S.StackEmpty() ) n+; An= S.Pop();for

11、 ( 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 .P op();T.Push(d);解：(1)借助一個數(shù)組，將棧中的兀素逆置。(2)借助棧T,將棧S中所有值為e的數(shù)據(jù)元素刪除之。3.編寫一個算法，將一個非負的十進制整數(shù) N轉(zhuǎn)換為B進制數(shù)， 并輸出轉(zhuǎn)換后的結(jié)果。 當(dāng)N=248D，B分別為8和16時，轉(zhuǎn)換后 的結(jié)果為多少？#

12、include stack.h”int NumTrans( int N, int B)/十進制整數(shù) N轉(zhuǎn)換為B進制數(shù)stack S; / 建立一個棧while( N!=0) / N 非零i=N%B ; /從低到高，依次求得各位N=N/B;S.push(i); / 各位入棧 while ( !S.StackEmpty() / 棧不空 i= S.pop();If (i9) i= 10-i;cout S.pop(); /依次出棧，得到從咼到低的輸出結(jié)果/#4借且棧，設(shè)計算法：假設(shè)一個算術(shù)表達式中包含“(、” “括號，對一個合法的數(shù)學(xué)表達式來說，括號“(和 “)應(yīng)是相互匹配的。若匹配，返回1 ;否則，

13、返回0。解：以字符串存儲表達式，也可以邊輸入邊判斷。順序掃描表達式，左括號，入棧；右括號，如果此時?？?，表示多右括號，不匹 配；如果棧不空，出棧一個左括號。掃描結(jié)束，如果?？眨硎纠ㄌ柶ヅ?；否則，括 號不匹配，多左括號。int blank_match(char *exp)用字符串存表達式SqStack s;/ 創(chuàng)建一個棧char *p=exp; 工作指針p指向表達式首 while ( *p!= = ) /不是表達式結(jié)束符switch(p) case (:左括號，入棧s.push(ch); break;case )/右括號if (s.StackEmpty() return 0;/ 棧空，不匹配，

14、多右括號else s.Pop(); break; / 左括號出棧/switchp+; /取表達式下一個字符 / whileif (!s.StackEmpty() / 表達式結(jié)束，棧不空return 0 ; /不匹配，多左括號 elsereturn 1 ; / 匹配 /#5.簡述棧和隊列的邏輯特點，各舉一個應(yīng)用實例。6.與出卜列中綴表達式的后綴表達式。(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 ! | A&B|!(EF)7計算后綴表達式：4 5 * 3 2 + -的值。解:158將下列遞推過程

15、改寫為遞歸過程。解:void recurisi on (i nt j)void recurs ion( int n ) if (j1)int i=n; cour1) recurisi on (j-1);cout x;cin x;if (x=0) sum=0;while (x) else S.push(x);test(sum); sum+=x; cin x; coutsum;sum=0;coutsum;while ( x=S.pop() ) sum+=x; coutsum; II10.簡述以下算法的功能（棧和隊列的兀素類型均為int ）。解：禾U用棧，將隊列中的兀素逆置void algo (Qu

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

17、ront+1)%m，為隊滿。template void EnQueue( T Se, T e, int m ) / 入隊if ( rear+1)%m =fornt ) / 隊滿，不能插入throw隊滿，不能插入！”else rear = (rear+1) % m ; /隊尾指針后移serear=e; / 兀素入隊return ;/#template T DnQueue( T Se, int m ) / 出隊if ( rear= =fornt )/隊空，不能出隊！throw隊空，不能出隊！”else front = (fron t+1)%m ; II指針后移，指向隊首兀素 e =sefront;

18、 II取隊首兀素return e ;/#上機練習(xí)題要求：給出問題分析、算法描述、源程序及運行截圖，在線提交。1借助棧，實現(xiàn)單鏈表上的逆置運算。1試問執(zhí)行以下函數(shù)會產(chǎn)生怎樣的輸出結(jié)果？void dem on strate()StrAssig n( s, THIS IS A BOOK);StrRep ( s, StrSub(s, 3, 7), ESE ARE);StrAssig n( t, StrCo neat ( s, S);StrAssig n(u, XYXYXYXYXYXY);StrAssig n(v, StrSub ( u, 6, 3 );StrAssig n(w, W);eout “ t

19、=” tendl;eout “v= ” v;eout “ u= ” StrRep(u, v, w); / dem on strate解: t= THESE ARE BOOKS v= YXYw= XWXWXW2.設(shè)字符串 S= aabaabaabaae ， P= aabaae1）給出S和P的next值和nextval值；2）若S作主串，P作模式串，試給出 KMP算法的匹配過程。1) S 的 next 與 nextval 值分別為 012123456789 和 002002002009， p 的 next 與 nextval 值分別為 012123 和 0020032) 利用KMP算法的匹配過程：

20、第一趟匹配：aabaabaabaaeaabaae(i=6,j=6)第二趟匹配： aabaabaabaae(aa)baae第三趟匹配：aabaabaabaae( 成功)(aa)baae3.算法設(shè)計 串結(jié)構(gòu)定義如下：struet SStri ngchar *data;/ 串首址int len;/ 串長int StrSize ;/存放數(shù)組的最大長度.；(1)編寫一個函數(shù)，計算一個子串在一個字符串中出現(xiàn)的次數(shù)， 如果不出現(xiàn)，則為 0。int str_co un t (SStri ng S, SStri ng T )解：int str_cou nt (SStri ng S, SStri ng T) in

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

22、n-t.le n; k+ )sk=sk+t.len; / 左移刪除s.len-=t.le n ;n+; II被刪除次數(shù)增1/for return n;/Delete_SubStri ng(2)編寫一個函數(shù)，求串s和串t的一個最長公共子串。void maxcomstr( SStri ng *s, SStri ng *t)解：void maxcomstr( SString *s, SString *t) in t i ndex=0,le n1=0, i,j,k,le n2;i=0;/作為掃描s的指針while ( i s.len) j = 0;/作為掃描t的指針while ( j len1) /

23、將較大長度者給 index 和 lenlin dex=i;len 1=le n2;j + = len2; /ifelse j+;/whilecout最長公共子串：for ( i=0; ile n1; i+;)cout8+7=45003 一個稀疏矩陣如圖所示-030000020500(1) 給出二元組存儲示意圖；A =000000(2) 給出帶行指針向量的鏈?zhǔn)酱鎯κ疽鈭D；9 0 0 0 0 4翅(3) 十字鏈表存儲示意圖。M dataijeA01234013112*013A135112*235 A309A351309b-451 AM.mu M.nu (1) M.tU465(2)A. cheadA. rheadA1A.mu 4 IA.nu 6o I 1 I 31 A1 1 21 1 35A.tu 5AA