清華數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案C語言版嚴(yán)蔚敏

1、清華數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案（C語言版嚴(yán)蔚敏）第1章緒論簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素.數(shù)據(jù)對(duì)象.數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu).數(shù)據(jù)類型和抽象數(shù)據(jù)類型。解：數(shù)據(jù)是對(duì)客觀爭物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符 號(hào)的總稱。數(shù)據(jù)元素定數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)對(duì)象定性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)是相互之問存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示。I敗據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組樂作的總稱。抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。長對(duì)一般數(shù)據(jù)類型的擴(kuò)展。

2、試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語言中數(shù)據(jù)類型概念的區(qū)別。解：抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的低念，但含義比一般數(shù)據(jù)類型更廣.更抽象。一般數(shù)據(jù)類型由 具體語言系統(tǒng)內(nèi)部定義，直接提供給編程者定義用戶數(shù)據(jù)，因此稱它們?yōu)轭A(yù)定義數(shù)據(jù)類型。抽象數(shù)據(jù)類型 通常由編程者定義，包括定義它所使用的數(shù)據(jù)利在這些數(shù)據(jù)上所進(jìn)行的探作。在定義抽象數(shù)據(jù)類型中的數(shù) 據(jù)部分和擾作部分時(shí)，要求只定義到數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說明，不考慮數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和操作的具體實(shí) 現(xiàn)，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。設(shè)有數(shù)據(jù)結(jié)構(gòu)（D.R）,其中D = 1,2,3,4, /? = /,廣=（1,2）,（2,3）,（3,

3、4）試按圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。試仿照三元組的抽象數(shù)據(jù)類型分別寫出抽象數(shù)據(jù)類型復(fù)數(shù)和有理數(shù)的定義（有理數(shù)是其分子.分母均為自 然數(shù)且分母不為零的分?jǐn)?shù)）.解：ADT Complex數(shù)據(jù)對(duì)象：Okii為實(shí)數(shù)）數(shù)據(jù)關(guān)系：R=rJ基本操作：InitComplex（&C.rc im）操作結(jié)果：構(gòu)造一個(gè)復(fù)數(shù)C,其實(shí)部和虛部分別為re和imDestroyCmoplex(&C)操作結(jié)果：銷毀復(fù)數(shù)CGet(C,k.&e)操作結(jié)果：用c返回復(fù)數(shù)C的第k元的值Put(&C,k.e)操作結(jié)果：改變復(fù)數(shù)C的第k元的值為eIsAscending(C)操作結(jié)果：如果復(fù)數(shù)C的兩個(gè)元素按升序排列，則返回1,否則返回

4、0IsDescending(C)操作結(jié)果：如果復(fù)數(shù)C的兩個(gè)元素按降序排列，則返回1,否則返回0Max(C.&e)操作結(jié)果：用e返回復(fù)數(shù)C的兩個(gè)元素中值較大的一個(gè)Min(C,&e)操作結(jié)果：用e返回復(fù)數(shù)C的兩個(gè)元素中值較小的一個(gè))ADT ComplexADT RationalNumber(數(shù)據(jù)對(duì)象：DMs.nis. m為自然數(shù)，且m不為0數(shù)據(jù)關(guān)系：R=m基本操作：InitRations1Number(&R s.m)操作結(jié)果：構(gòu)造一個(gè)有理數(shù)R,其分子和分母分別為s和mDestroyRationa1Number(&R)操作結(jié)果：銷毀有理數(shù)RGet(R.k.&c)操作結(jié)果：用c返回有理數(shù)R的第k元的值

5、Put(&R.ke)操作結(jié)果：改變有理數(shù)R的笫k元的值為eIsAscending(R)操作結(jié)果：若有理數(shù)R的兩個(gè)元素按升序排列，則返回1,否則返回0IsDescending(R)操作結(jié)果：若有理數(shù)R的兩個(gè)元素按降序排列，則返回1,否則返回0Max(R.&e)操作結(jié)果：用e返回有理數(shù)R的兩個(gè)元素中值校大的一個(gè)Min(R.&e)操作結(jié)果：用e返回有理數(shù)R的兩個(gè)元素中值較小的一個(gè))?DT Rat ionalNumber試畫出與下列程序段等價(jià)的框圖。(1) product=l； i=l；)wh訂 e(i=n) product = i；i+;(2) i=0；do while(i!=n) & (ai!=x

6、);(3) switch case xy： z=y-x； break；case x=y： z=abs (x*y)； break； default: z=(x-y)/abs(x)*abs(y)；在程序設(shè)計(jì)中.常用下列三種不同的出錯(cuò)處理方式：(1) 用exit語句終止執(zhí)行并報(bào)告錯(cuò)懼；(2) 以函數(shù)的返回值區(qū)別正確返回或錯(cuò)誤返回；)(3) 設(shè)置一個(gè)養(yǎng)型變量的函數(shù)參數(shù)以區(qū)別正確返回或某種錯(cuò)誤返回。試討論這三種方法各自的優(yōu)缺點(diǎn)。解：(l)exit #用于異常錯(cuò)誤處理，它可以強(qiáng)行中斷程序的執(zhí)行，返回操作系統(tǒng)。(2) 以函數(shù)的返回值判斷正確與否常用于子程序的測試，便于實(shí)現(xiàn)程序的局部控制。(3) 用整型函數(shù)進(jìn)

7、行錯(cuò)誤處理的優(yōu)點(diǎn)是可以給出錯(cuò)誤類型，便于迅速確定錯(cuò)誤。在程序設(shè)計(jì)中，可采用下列三種方法實(shí)現(xiàn)輸出和輸入：(1) 通過scanf和printf語句；(2) 通過函數(shù)的參數(shù)顯式傳遞；(3) 通過全局變量隱式傳遞。試討論這三種方法的優(yōu)缺點(diǎn)。解：(1)用scanf printf直接進(jìn)行輸入輸出的好處是形象、直觀，但缺點(diǎn)是需要對(duì)其進(jìn)行格式控制， 較為煩瑣，如果出現(xiàn)錯(cuò)誤，則會(huì)引起整個(gè)系統(tǒng)的崩潰。(2) 通過函數(shù)的參數(shù)傳遞進(jìn)行輸入輸出，便于實(shí)現(xiàn)信息的隱蔽，減少出錯(cuò)的可能。(3) 通過全局變量的隱式傳遞進(jìn)行輸入輸出最為方便，只需侈改變量的值即可，但過多的全局變量使程 序的維護(hù)較為困難。設(shè)n為正整數(shù)。試確定下列各

8、程序段中前置以記號(hào)的語句的頻度：(1) i=l; 口；while(i=n-l) k +二 10*i；i卄；(2) i=l; k=0；do 0 k += 10*i； i+; vrh訂e(i=n-l)； i=l; k=0;while (i=n-l) i+; k += 10*i；k=0；for(i=l； i=n； i+)( for(j=i； j=n； j+) k+；for(i=l； i=n； i+) for(j=l； j=i; j+) for(k=l； k=j: k+) x += delta； i=l; j=0;wh訂e(i+jj) j+;else i+；(7) x=n； y=0； 十巴凹21 +

9、(1+2) + (l+2+3)+. + (H2+3,.+n)-X j-i 21 n1 1 n1 n冷Q + 1)冷工雀+眾廠+*2 /-/ /-I乙 r-1 乙 r-1=n(n +1)(2“ +1) + n(n +1) = n(n +1)(2 + 3) 12 12向下取整(8) 1100假設(shè)n為2的乘碁，并且n2,試求下列算法的時(shí)間復(fù)雜度及變* count的值(以n的函數(shù)形式表示)。 int Time(int n) count = 0；x=2；while(x438 時(shí)，n2 50/2 log 2 n判斷下列各對(duì)函數(shù)/S)和g()，當(dāng)“TCC時(shí)，哪個(gè)函數(shù)增長更快(1) /()= 10/72 +

10、ln(!+10 ), g(n) = 2n4 +n + l(2) /(n) = (In(n!)+5)2, g(n)=13滬(3) f(n)=n2A + yin4 +1 , g() = (ln(n!)2 +n /S)=2()+(2)2, gS) =)+/(解:(l)g(n)快(2)g(n)快(3)f(n)快(4) f(n)快試用數(shù)學(xué)歸納法證明：(1)工廠=( + 1X2“ +1)/6 (n 0) 亡=(兀心 一 l)/(x-l)(X 1,/7 0)/- 1)J-l f -l) = n2(n 1)/l試寫一算法，自大至小依次輸出順序讀入的三個(gè)整數(shù)X, Y和Z的值解：int max3(int x.in

11、t z)(if(xy)if(xz) return x；else return z；elseif(yz) return y；else return z；巳知k階斐波那契序列的定:義為辦=0，/ = 0，fk-2 = 0 fk- = i ；fn = fn- + fn-2 + + fn-k +試編寫求k階斐波那契序列的笫m項(xiàng)值的函數(shù)算法，k和m均以值調(diào)用的形式在函數(shù)參數(shù)表中出現(xiàn)。解：k0為階數(shù)，n為數(shù)列的第n項(xiàng)int Fibonacci(int k,int n)if(kl) exit(OVERFLOW)；int *p.x；p=new intk+l；if(!p) exit(OVERFLOW

12、)；int i,j;for(i=0；ik+l；i+)if(ik-l) pi=O；else pi=l;for (i=k+l；in+l；i+)x=p0:for(j=0；jarrsize或?qū)δ硞€(gè)k(l k maxint時(shí)，應(yīng)按 出錯(cuò)處理。注意選擇你認(rèn)為較好的出錯(cuò)處理方法。解：ttincludcOttincludeOttdefine MAXINT 65535#define ArrSize 100int fun(int i)；int main()(int ik;int aArrSize；coutnEnter k：cink；if(kArrSize-l) exit(0)；for(i=0；iMAXINT) e

13、xit(0)；else ai=2*i*ai-l；for(i=0；iMAXINT) exit(0)；else coutaiN-l) exit(O)； cout輸入多項(xiàng)式的系數(shù)aLOan：for (iO； iOn； ii) cinai :coutwThe polynomai 1 value is M0) return ani+polynomai1(ai-lx.n)*x；else return an；本算法的時(shí)問復(fù)雜度為o(n)第2章踐性表描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)(第一個(gè)元素結(jié)點(diǎn))。解：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針。首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。頭結(jié) 點(diǎn)是

14、在首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)元素，其指針域指向首元結(jié)點(diǎn)，其作用主要是為 了方便對(duì)鏈表的操作。它可以對(duì)空表、非空表以及首元結(jié)點(diǎn)的操作進(jìn)行統(tǒng)一處理。填空題。解：(1)在順序表中插入或冊(cè)除一個(gè)元素，需要平均移益表中一半元素，具體移動(dòng)的元素個(gè)曝邑元素 在表中的位置勺關(guān)。(2) 順序表中邏輯上相鄰的元素的物理位置住緊鄰。單鏈表中邏輯上相鄰的元素的物理位矍不一定 緊鄰。 5 7 3 8 r “PQKS解:1SQSL10Tp14T16TsJ畫出執(zhí)行下列各行語句后各指針及鏈表的示意圖。L= QinkList)malloc(sizeof(LNode) ； P=L；for(i=l；inext=(

15、LinkList)malloc(sizeof(LNode)； P=P-next； P-data=i*2-l；P-next=NULL；for(i=4；i=l；i) Ins丄inkList(L,i+l,i*2)； for(i=l；inext=S；(2) P-next=P-next-next ；(3) P-next=S-next；(4) S-next=P-next；(5) S-next=L；(6) S-next=NULL；(7) Q=P;(8) while(P-next!=Q) P=P-next；(9) wh訂e(P-next!=NULL) P=P-next；(10) P=Q；(11) P=L；(1

16、2) L=S;(13) L=P；解：a. (4) (1)b. (7) (11) (8) (4) (1)c. (5) (12)d(9) (1) (6)巳知L是帝表頭結(jié)點(diǎn)的非空單後表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中 選擇合適的語句序列。a. 刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是.b. 刪除P結(jié)點(diǎn)的克接前驅(qū)結(jié)點(diǎn)的語句序列長oC刪除P結(jié)點(diǎn)的語句序列是d刪除首元結(jié)點(diǎn)的語句序列是Oe. 蒯除尾元結(jié)點(diǎn)的語句序列是.(1) P=P-next；(2) P-next=P；(3) P-next=P-next-next ；(4) P=P-next-next；(5) while(P!=NU

17、LL) P=P-next；(6) e(Q-next!=NULL) P=Q； Q=Q-next； (7) while(P-next!=Q) P-P-next；(8) wh訂e (P-next-next!=Q) P=P-next；(9) while(P-next-next!=NULL) P=P-next；(10) Q=P;(11) Q=P-next；(12) P=L;(13) L=L-next；(14) free (Q)；解：a. (11) (3) (14)b.(10)(12)(14)C(10)(12)(7)(3)(14)d.(12)(ID(14)C(9)(ID(14)巳知P結(jié)點(diǎn)是某雙向鏈表的中間

18、結(jié)點(diǎn).試從下列提供的答案中選擇合適的語句序列. a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是b在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是。c. 蒯除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是。d蒯除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是O(e刪除P結(jié)點(diǎn)的語句序列是o(1) P-next=P-next-next；(2) P-pr i ou=P-pr i ou-pr i ou；(3) P-next=S；(4) P-priou=S；(5) S-next=P；(6) S-priou=P；(7) S-next=P-next；?(8) S-pr i ou=P-pr i ou；(9) P-priou-next=P-next；(10) P-p

19、riou-next=P；(11) P-next-pr i ou=P；(12) P-next-priou=S；(13) P-pri ou-next=S；(14) P-next-priou=P-priou；(15) Q=P-next；(16) Q=P-priou；(17) free(P)；(18) free(Q)；解：a. (7) (3) (6) (12)b.(8)(13)C(15)(11)(18)d.(16)(10)(18)e.(14)(17)筒述以下算法的功能。(1)StatusA(LinkedListL) q = (q,”)B = (妬,J/T B AB A, = B, = A = BA,

20、BH A B ABA B S，,a”) (yj A = (%“2,，” J B =也)C = (%片，網(wǎng)婦,休+|,心)m n厶=(4,“2,“)L =.an)改造為(al.a3ana2)Status ListChange_DuL(DuLinkList &L)DuLinkList p.q.r； p=L-next； r=L-pre； i = l;while(p!=r) if(i%2=0)q 二P；p-p-next；Pn(x) =+ c2xe2 + + cmxm n = em e心 -el 0 q H 0(z = 12 )mlPnMx0 P(Q=Ei(x)-%(x) PB Pn Pj pk Pi

21、Pj pk Pi Pj Pk Pi Pi Pj PkPj Pi2n 1 olor；Push(s,g )；while(!StackEmpty(s)Pop(s.e)；CurPos=；g Color二Fi11Color； g . Visited；if0 &!g. Visited &gj . Color=01lColor)Push(s.g);if0 &!g. Visited &g . Color=01dColor)Push(s.g)；void CreateGDS（ElemType gMN）int i.j;for（i=0；iM；i+）for（j=0；jN；j+）gi jl. =i;gi jl.=j;gi

22、 j. Visited=0;gi jl. Color=0；for（i=2；i5；i+）for（j=2；j4；j+）gij Color二3；for（i=5；iM-l；i+）for（j=3；j6；jMgijl. Color=3；void ShowGraphArray（ElemType gMN）int i.j;for（i=0；iM；i+）（for（j=0；jN；j+）coutgi： j Color；0n + 1 n = 0F(%) h0P/4 1sqrtA込P + - 2l P)sqrt(A、p) =p1 - A ein = 0aknin,n)= maxaknm 一 ,aknin,n -1)a(a

23、+1)2i(i-1)-1il jlij f1(i) = (n+l)i-li2c = -(n + 1)|i-j| 10 k 3n -1ab = 0s(n) = s(n-l) + an =s(n-l) + a1 +(n-l)d add(a,b) = 0總共需進(jìn)行k次交換。注意最后一組可能出現(xiàn)不足k個(gè)元素的情況，此時(shí)最后一組為剩余元素加第一組 的前幾個(gè)元素共k個(gè)構(gòu)成最后一組。void RRMove(ElemType At int n)ElemType e；int i=Otj.p；while(in-k) p 二 i/kH；for(j=0；jk;j+)e=Aj；Aj=A(p*k+j)%n；A

24、(p*k+j)%n=e；i+;解：#include #define RS 4#define CS 4typedef int ElemType；typedef structElemType e；int i,j;int Flags；NodeType；void Initialize(NodeType aRSCS,ElemType ARSCS)； void SaddlePoint(NodeType aRSCS)；ElemType RowMin(NodeType aRSCS,int k):ElemType ColMax(NodeType aRSCS.int k)；void Show(NodeType a

25、RSCS)；int main()ElemType ARSCS=(),() ,() ,();NodeType aRSCS;Initialize(a.A)；SaddlePoint(a)；Show (a)；return 0；void Initialize(NodeType aRSCS.ElemType ARSCS) int i,j;for(i=0；iRS；i+)for(j=0；jCS；j+)aij.e=Aij:aijl. i=i;aijl. j=j;ai j Flags二0；) void SaddlePoint(NodeType aRSCS)

26、int i.j;ElemType x.y； for(i=0；iRS；i+)x-RowMin(a,i): for(j=0；jCS；j+)( y-ColMax(a.j)；if (ai j. ex&ai j. e=y) ai jl. Flagsl；ElemType RowMin(NodeType aRSCS.int k)ElemType x；x=ak0. e；int i；for(i=l；iaki. e)(x二akCi, e；return x；ElemType ColMax(NodeType aRSCSt int k)ElemType x；x=a0kJ. e；int i；for(i=l；iRS；i+)

27、if (xai kJ. e) *!x=aiEk e；return x；void Show(NodeType aRSCS)for(int i=0；iRS；i+)for(int j=0；jCS;j+4)if (ai j. Flags)coutiwis a sadd 1 e pointwendl；解：typedef int ElemType；class Triplepublic：int row；int col；ElemType e；TripleO virtual TripleO BOOL operator仃riple b)；BOOL operator (Triple b):;BOOL Triple：

28、operatorCTriple b)i f(row return TRIE；if(row-&col return TRUE； return FALSE；BOOL Triple：operator=(Triple b) i f (row= & col=return TRUE；elsereturn FALSE； class CSparseMatpublic：CSparseMat () virtual CSparseMat()(CSparseMat(ini r,int n)；CSparseMat operator+(CSparseMat B)；void ShowSparse(CDC* pD

29、C)；Tripleow=；m_pti col=；m_pti. e=；) void CSparseMat:ShowSparse(CDC pDC)char str10:int k=0；for(int i=0；im_nRow；i+)(for(int j-0；jText()ut (0+j*20.0+i*20t str, strlen(str)； ow-m_pti. row；k col=m_pti col ；k e二m_pt i e；i+;elseif (m_ptij) k row-m_pti row；k col=m_pti col；kJ. e=m_pt i, e+j. e；i+; j+;elsek r

30、ow=j. row；Lk.col二j col；kJ. e=j. e；jf)k+；while(im_nTrs) k. row=m_pti row；k col-m_pti col；k e=m_pt i e；i+;k+；while(jttincludeOftincludeOttdefine Max 128typedef int ElemType； typedef struct int col； ElemType e；Twin； class CSparseMatpublic：CSparseMat () (CSparseMat(int n)； virtual CSparseMat

31、()void ShowSparse(int j)；Twin* m_pt； olm_pti.e；for(i=0；im_nRow；i+)cout-請(qǐng)輸入每行第一個(gè)非零元在二元組中的序號(hào)(沒有輸入-1)：； cinrposi: olj)x-m_ptk. e；k+；coutxendl ；int mainOCSparseMat A(3.3,5)；(2.1)；return 0； 解：typedef int ElemType； typedef struct OLNode int row；int col；ElemType e；struct OLNode right.down；OLNode.*0Link；class CCrossListMatOLinkRHead,*CHead；kH -1k_l1 + 2n2 + 33 +. + knkn() = 1 + 2n2 + 3n3 +. + knk 一(q + n2 + z?3 +. + 人)=1 + 工(i 一 1)坷r-ln = l + nkk nQ=n-nk =n- ogk(n(k 一 1) +1)1 n0 nQ =(k 一l)nl +1 nQ = k1 k01kh-n =k_lk-1ku 1kH 1 1 k”R刖伙-嘰+1下h-S育3 一 1 2/? 3W -12n + l 3 3(2