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

1、第1章緒1.1 后卜列兒種二兀組表示的數(shù)據(jù)結(jié)構(gòu)，試畫出它們分別對應(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ù)，求下列各程序段中的下劃線語句的執(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指出下列個算法的功能，并求其時間復(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è)計1枚是假的，偽幣與真幣重量略有不同。如何借用一架有3枚硬幣，其中有天平，找出偽幣？以流程圖表示算法。上機練習(xí)題要求：給出問題分析、算法描述、源程序及運行截圖，在線提交。1.設(shè)a,b,c為3個整數(shù)，求其中位于中間值的整數(shù)。1.設(shè)計算法：在順序表中刪除值為e的兀素,否則，返回0。刪除成功，返回1;intSqlist<T>:DeleteElem(Te)for(i=1;i<=length;i+)/按值順序查找*i可從0開始if(elemi-1=e)/找到，進行刪除操作for(j=i;j<

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

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

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

8、if(i=1)/刪除第1個元素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/定位成功，進行結(jié)點刪除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é)點的單鏈表，且P結(jié)點既不是首兀結(jié)點，也不是尾結(jié)點，試寫出實現(xiàn)卜列功能的語句序列。(1)在P結(jié)點后插入S結(jié)點；(2)在P結(jié)點前插入S結(jié)點；(3)在表首插入S結(jié)點；(4)在表尾插入S結(jié)點.【解】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;上機練習(xí)題要求：給出問題分析、算法描述、源程序及運行截圖，在線提交。編程實現(xiàn)：刪除單鏈表中值為e的兀素。解：325641可以154623不可以。第3章棧與隊列1.鐵路進行列車調(diào)度時，常把站臺設(shè)計成棧式結(jié)構(gòu)的站臺，如右圖所示。試問：若進站的六輛列車順序如上所述，那么是否能夠得到325641和154623的出站序列

11、，如果不能，說明為什么不能；如果能,說明如彳5得到（即寫出"進棧"或"出棧"的序列）。2.簡述以下算法的功能(棧的兀素類型為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)借助一個數(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é)果為多少？#includeStack.h"intNumTrans(intN,intB)/十進制整數(shù)N轉(zhuǎn)換為B進制數(shù)stack<int>S;/建立一個棧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è)計算法：假設(shè)一個算術(shù)表達式中包含（、”“后號,解：以字符串存儲表達式，也可以邊輸入邊判斷。對一個合法的數(shù)學(xué)表達式來說，括號"（和“）應(yīng)是相互匹配的。若匹配，返回1;否則，返回0。順序掃描表達式，左括號，入棧；右括號，如果此時?？眨硎径嘤依ㄌ?，不匹配；如果棧不空，出棧一個左括號。掃描結(jié)束，如果?？?，表示括號匹配；否則，括號不匹配，多左括號。intblank_match(char*exp)用字符串存表達式SqStack<cha

14、r>s;/創(chuàng)建一個棧char*p=exp;工作指針p指向表達式首while(*p!='=')/不是表達式結(jié)束符switch(p)case'(':左括號，入棧s.push(ch);break;case')'/右括號if(s.StackEmpty()return0;/棧空，不匹配，多右括號elses.Pop();break;/左括號出棧/switchp+;/取表達式下一個字符/whileif(!s.StackEmpty()/表達式結(jié)束，棧不空return0;/小匹配，多左括號elsereturn1;/匹配/#5.簡述棧和隊列的邏輯特點，各舉一個

15、應(yīng)用實例。6.寫出下列中綴表達式的后綴表達式。(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.計算后綴表達式：45*32+-的值。解：158.將下列遞推過程改寫為遞歸過程。voidrecursion(intn)inti=n;while(i>1)cout<<i;i-;解：voidrecurision(intj)if(j>1)cour<<j;recurision(j-1);9.將下列遞歸過程改寫為非遞歸過程。voi

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

17、Q)(StackS;/創(chuàng)建一個棧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)隊列的兀素，同時設(shè)變量rear和front分別作為隊首、隊尾指針，且隊首指針指向隊首前一個位置，隊尾指針指向隊尾兒素處，初始時，rear=fornt=-1。與出這樣設(shè)計的循環(huán)隊列入隊、出隊的算法。解：米用教材隊空與隊滿判別方法。為了區(qū)分隊空與隊滿條件，犧牲一個兀素空間。即：rear=front,為隊空；rear=(front+1)%m,為隊滿。tem

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

19、運行截圖，在線提交。1.借助棧，實現(xiàn)單鏈表上的逆置運算。第4章串.試問執(zhí)行以下函數(shù)會產(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法的匹配過程。解：t=THESEAREBOOKSv=YXYw=XWXWXW1)S的next與nextval值分另為012123456789和002002002009,p的next與nextval值分另U為01

21、2123和0020032)利用KMPIT法的匹配過程：第趟匹配：aabaabaabaacaabaac(i=6,j=6)第二趟匹配：aabaabaabaac(aa)baac第三趟匹配：aabaabaabaac(成功)(aa)baac3.算法設(shè)計串結(jié)構(gòu)定義如下:structSString(char*data;/串首址intlen;/串長intStrSize;/存放數(shù)組的最大長度.)；(1)編寫一個函數(shù)，計算一個子串在一個字符串中出現(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)編寫一個函數(shù)，求串s和串t的一個最長公共子串。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)/序號為i,長

24、度為len2的子串len2=1;/開始計數(shù)for(k=1;s.datai+k=t.dataj+k&&s.datai+k!=NULL;k+)len2+;if(len2>len1)/將較大長度者給index和len1index=i;len1=len2;j+=len2;/ifelsej+;/whilecout<<”最長公共子串：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、'。試利用下列運算，將s轉(zhuǎn)化為t。聯(lián)接：StrConcat(&S,T)求子串：(char*)StrSub(S,i,len)置換：StrRep(&S,T,R)上機練習(xí)題要求：給出問題分析、算法描述、源程序及運行截圖，在線提交。串結(jié)構(gòu)定義如下：structSStringchar*data;/串首址intlen;/串長intStrSize;/存放數(shù)組的最大長度.;求：串S所含不同字符的總數(shù)和每種字符的個數(shù)，不區(qū)分英文字母的大小寫。1.假設(shè)有二維數(shù)組A6如每個兀素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置(基地址)為1000,計算：數(shù)組A的體積(即存儲量);(

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