李云清揭安全數(shù)據(jù)結(jié)構(gòu)答案

《李云清揭安全數(shù)據(jù)結(jié)構(gòu)答案》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

李云清揭安全數(shù)據(jù)結(jié)構(gòu)答案數(shù)據(jù)結(jié)構(gòu)（C語言版）（第2版）習(xí)題解析揭安全李云清楊慶紅江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院聯(lián)系方式：janquan@163（習(xí)題答案僅供參考）2第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)？【答】：數(shù)據(jù)結(jié)構(gòu)是指按一定的邏輯結(jié)構(gòu)組成的一批數(shù)據(jù)，使用某種存儲(chǔ)結(jié)構(gòu)將這批數(shù)據(jù)存儲(chǔ)于計(jì)算機(jī)中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算集合。1.2數(shù)據(jù)結(jié)構(gòu)涉及哪幾個(gè)方面？【答】：數(shù)據(jù)結(jié)構(gòu)涉及三個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算集八口O1.3兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)都相同，但是它們的運(yùn)算集合中有一個(gè)運(yùn)算的定義不一樣，它們是否可以認(rèn)作是同一個(gè)數(shù)據(jù)結(jié)構(gòu)？為什么？【答】：不能，運(yùn)算集合是數(shù)據(jù)結(jié)構(gòu)的重要組成部分，不同的運(yùn)算集合所確定的數(shù)據(jù)結(jié)構(gòu)是不一樣的，例如，棧與隊(duì)列它們的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)可以相同，但由于它們的運(yùn)算集合不一樣，所以它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。1.4線性結(jié)構(gòu)的特點(diǎn)是什么？非線性結(jié)構(gòu)的特點(diǎn)是什么？

1【答】：線性結(jié)構(gòu)元素之間的關(guān)系是一對(duì)一的，在線性結(jié)構(gòu)中只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，一其他的每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)和一個(gè)后繼結(jié)點(diǎn)。而非線性結(jié)構(gòu)則沒有這個(gè)特點(diǎn)，元素之間的關(guān)系可以是一對(duì)多的或多對(duì)多的。1.2數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式有哪幾種？【答】：數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、散列存儲(chǔ)和索引存儲(chǔ)等四種方式。1.3算法有哪些特點(diǎn)？它和程序的主要區(qū)別是什么？【答】：算法具有（D有窮性（2）確定性（3）0個(gè)或多個(gè)輸入（4）1個(gè)或多個(gè)輸出（5）可行性等特征。程序是算法的一種描述方式，通過程序可以在計(jì)算機(jī)上實(shí)現(xiàn)算法。1.4抽象數(shù)據(jù)類型的是什么？它有什么特點(diǎn)？【答】：抽象數(shù)據(jù)類型是數(shù)據(jù)類型的進(jìn)一步抽象，是大家熟知的基本數(shù)據(jù)類型的延伸和發(fā)展。抽象數(shù)據(jù)類型是與表示無關(guān)的數(shù)據(jù)類型，是一個(gè)數(shù)據(jù)模型及定義在該模型上的一組運(yùn)算。對(duì)一個(gè)抽象數(shù)據(jù)類型進(jìn)行定義時(shí)，必須給出它的名字及各運(yùn)算的運(yùn)算符名，即函數(shù)名，并且規(guī)定這些函數(shù)的參數(shù)性質(zhì)。一旦定義了一個(gè)抽象數(shù)據(jù)類型及具體實(shí)現(xiàn)，程序設(shè)計(jì)中就可以像使用基本數(shù)據(jù)類型那樣，十分方便地使用抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型的設(shè)計(jì)者根據(jù)這些描述給出操作的具體實(shí)現(xiàn)，抽象數(shù)據(jù)類型的使用者依據(jù)這些描述使用抽象數(shù)據(jù)類型。1.5算法的時(shí)間復(fù)雜度指的是什么？如何表示?【答】：算法執(zhí)行時(shí)間的度量不是采用算法執(zhí)行的絕對(duì)時(shí)間來計(jì)算的，因?yàn)橐粋€(gè)算法在不同的機(jī)器上執(zhí)行所花的時(shí)間不一樣，在不同時(shí)刻也會(huì)由于計(jì)算機(jī)資源占用情況的不同，使得算法在同一臺(tái)計(jì)算機(jī)上執(zhí)行的時(shí)間也不一樣，另外，算法執(zhí)行的時(shí)間還與輸入數(shù)據(jù)的狀態(tài)有關(guān)，所以對(duì)于算法的時(shí)間復(fù)雜性，采用算法執(zhí)行過程中其基本操作的執(zhí)行次數(shù)，稱為計(jì)算量來度量。算法中基本操作的執(zhí)行次數(shù)一般是與問題規(guī)模有關(guān)的，對(duì)于結(jié)點(diǎn)個(gè)數(shù)為n的數(shù)據(jù)處理問題，用T(n)表示算法基本操作的執(zhí)行次數(shù)。為了評(píng)價(jià)算法的執(zhí)行效率，通常采用大寫0符號(hào)表示算法的時(shí)間復(fù)雜度，大寫0符號(hào)給出了函數(shù)f的一個(gè)上限。其它義如下：3

2定義：f(n)=0(g(n))當(dāng)且僅當(dāng)存在正的常數(shù)c和nO,使得對(duì)于所有的ndnO,有f(n)Wcg(n)?上述定義表明，函數(shù)f頂多是函數(shù)g的c倍，除非n小于nO。因此對(duì)于足夠大的n(如n》nO),g是f的一個(gè)上限(不考慮常數(shù)因子c)。在為函數(shù)f提供一個(gè)上限函數(shù)g時(shí)，通常使用比較簡單的函數(shù)形式。比較典型的形式是含有n的單個(gè)項(xiàng)(帶一個(gè)常數(shù)系數(shù))。表1T列出了一些常用的g函數(shù)及其名稱。對(duì)于表1T中的對(duì)數(shù)函數(shù)logn,沒有給出對(duì)數(shù)基，原因是對(duì)于任何大于1的常數(shù)a和b都有l(wèi)ogan=logbn/logba,所以logan和logbn都有一個(gè)相對(duì)的乘法系數(shù)1/logba,其中a是一個(gè)常量。表1-1常用的漸進(jìn)函數(shù)1.2算法的空間復(fù)雜度指的是什么？如何表示？【答】：算法的空間復(fù)雜度是指算法在執(zhí)行過程中占用的額外的輔助空間的個(gè)數(shù)?？梢詫⑺硎緸閱栴}規(guī)模的函數(shù)，并通過大寫。符號(hào)表示空間復(fù)雜度。1.3對(duì)于下面的程序段，分析帶下劃線的語句的執(zhí)行次數(shù)，并給出它們的時(shí)間復(fù)雜度T(n)0(1)i++;(2)for(i-0;ia[j+l])k=j;t=a[k];a[k]=a[i];a[i]=t;}(5)for(i=0;i

3for(j=0;j

4A.插入和刪除在表的不同位置執(zhí)行B.插入和刪除在表的兩端位置執(zhí)行C.插入和刪除分別在表的兩端執(zhí)行D.插入和刪除都在表的某一端執(zhí)行(8)棧是一種特殊的線性表，具有(B)性質(zhì)。A.先進(jìn)先出B.先進(jìn)后出C.后進(jìn)后出D.順序進(jìn)出(9)順序循環(huán)隊(duì)列中(數(shù)組的大小為n),隊(duì)頭指示front指向隊(duì)列的第1個(gè)元素，隊(duì)尾指示rear指向隊(duì)列最后元素的后1個(gè)位置，則循環(huán)隊(duì)列中存放了n-1個(gè)元素，即循環(huán)隊(duì)列滿的條件為（B）。A.（rear+l）%n=front-IB.（rear+l）%n=frontC.（rear）%n=frontD.rear+1=front（10）順序循環(huán)隊(duì)列中（數(shù)組的大小為6）,隊(duì)頭指示front和隊(duì)尾指示rear的值分別為3和0,當(dāng)從隊(duì)列中刪除1個(gè)元素，再插入2個(gè)元素后，front和rear的值分別為（D）.A.5和1B.2和4c.1和5D.4和22.2什么是順序表？什么是棧？什么是隊(duì)列？5【答】：當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，即為順序表。棧是一種特殊的線性表，它的特殊性表現(xiàn)在約定了在這種線性表中數(shù)據(jù)的插入與刪除操作只能在這種線性表的同一端進(jìn)行（即棧頂），因此，棧具有先進(jìn)后出、后進(jìn)先出的特點(diǎn)。隊(duì)列也是一種特殊的線性表，它的特殊性表現(xiàn)在約定了在這種線性表中數(shù)據(jù)的插入在表的一端進(jìn)行，數(shù)據(jù)的刪除在表的另一端進(jìn)行，因此隊(duì)列具有先進(jìn)先出，后進(jìn)后出的特點(diǎn)。2.3設(shè)計(jì)一個(gè)算法，求順序表中值為x的結(jié)點(diǎn)的個(gè)數(shù)?！敬稹浚喉樞虮淼拇鎯?chǔ)結(jié)構(gòu)定義如下（文件名seqlist.h）：Sinclude?tdefineN100/*預(yù)定義最大的數(shù)據(jù)域空間*/typedefintdatatype;/*假設(shè)數(shù)據(jù)類型為整型*/

5typedefstruct{datatypedata[N];/*此處假設(shè)數(shù)據(jù)元素只包含一個(gè)整型的關(guān)鍵字域*/intlength;/*線性表長度*/}seqlist;/*預(yù)定義的順序表類型*/算法countx(L,x)用于求順序表L中值為x的結(jié)點(diǎn)的個(gè)數(shù)。intcountx(seqlist*L,datatypex){intc=0;inti;for(i=0;ilength;i++)if(L->data[i]==x)c++;returnc;}2.4設(shè)計(jì)一個(gè)算法，將一個(gè)順序表倒置。即，如果順序表各個(gè)結(jié)點(diǎn)值存儲(chǔ)在一維數(shù)組a中，倒置的結(jié)果是使得數(shù)組a中的a[0]等于原來的最后一個(gè)元素，a[l]等于原來的倒數(shù)第2個(gè)元素，…，a的最后一個(gè)元素等于原來的第一個(gè)元素。【答】：順序表的存儲(chǔ)結(jié)構(gòu)定義同題2.3,實(shí)現(xiàn)順序表倒置的算法程序如下：voidverge(seqlist*L){intt,i,j;i=0;j=L->length~l;while(idata[i];L->data[i++]=L->data[j];L->data[j-]=t;

62.4已知一個(gè)順序表中的各結(jié)點(diǎn)值是從小到大有序的，設(shè)計(jì)一個(gè)算法，插入一個(gè)值為x的結(jié)點(diǎn)，使順序表中的結(jié)點(diǎn)仍然是從小到大有序。【答】：順序表的定義同題2.3,實(shí)現(xiàn)本題要求的算法程序如下：6voidinsertx(seqlist*L,datatypex){intj;if(L->lengthlength-l;while(j>=0&&L->data[j]>x){L->data[j+l]=L->data[j];j—；)L->data[j+l]=x;L->length++;))2.5將下列中綴表達(dá)式轉(zhuǎn)換為等價(jià)的后綴表達(dá)式。(1)5+6*7(2)(5-6)/7(3)5-6*7*8(4)5*7-8(5)5*(7-6)+8/9(6)7*(5-6*8)-9

7【答】：(1)5+6*7后綴表達(dá)式：567*+(2)(5-6)/7后綴表達(dá)式：56-7/(3)5-6*7*8后綴表達(dá)式：567*8*-(4)5*7-8后綴表達(dá)式：57*8(5)5*(7-6)+8/9后綴表達(dá)式：576-*89/+(12)7*(5-6*8)-9后綴表達(dá)式：7568*-*9-2.7循環(huán)隊(duì)列存儲(chǔ)在一個(gè)數(shù)組中，數(shù)組大小為n,隊(duì)首指針和隊(duì)尾指針分別為front和rear,請(qǐng)寫出求循環(huán)隊(duì)列中當(dāng)前結(jié)點(diǎn)個(gè)數(shù)的表達(dá)式?！敬稹浚貉h(huán)隊(duì)列中當(dāng)前結(jié)點(diǎn)個(gè)數(shù)的計(jì)算公式是：(n+rear-front)%n2.8編號(hào)為1,2,3,4的四列火車通過一個(gè)棧式的列車調(diào)度站，可能得到的調(diào)度結(jié)果有哪些？如果有n列火車通過調(diào)度站，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，輸出所有可能的調(diào)度結(jié)果?！敬稹浚航忸}思路：棧具有先進(jìn)后出、后進(jìn)先出的特點(diǎn)，因此，任何一個(gè)調(diào)度結(jié)果應(yīng)該是1,2,3,4全排列中的一個(gè)元素。由于進(jìn)棧的順序是由小到大的，所以出棧序列應(yīng)該滿足以下條件：對(duì)于序列中的任何一個(gè)數(shù)其后面所有比它小的數(shù)應(yīng)該是倒序的，例如4321是一個(gè)有效的出棧序列，1423不是一個(gè)有效的出棧結(jié)果(4后面比它小的兩個(gè)數(shù)2,3不是倒序)。據(jù)此，本題可以通過算法產(chǎn)生n個(gè)數(shù)的全排列，然后將滿足出棧規(guī)則的序列輸出。產(chǎn)生n個(gè)數(shù)的全排列有遞歸與非遞歸兩種實(shí)現(xiàn)算法。產(chǎn)生全排列的遞歸算法:7設(shè)R={rl,r2,…,rn}是要進(jìn)行排列的n個(gè)元素，Ri=R-{ri}o集合X中元素的全排列記為perm(X)o(ri)perm(X)表示在全排列perm(X)的每一個(gè)排列前加上前綴列得到的排列。R的全排

8列可歸納定義如下：當(dāng)n=l時(shí)，perm(R)=(r),其中r是集合R中惟一的元素；當(dāng)n>l時(shí)，perm(R)由(rl)perm(Rl),(r2)perm(R2),…，(rn)perm(Rn)構(gòu)成。依此遞歸定義，可設(shè)計(jì)產(chǎn)生perin(R)的遞歸算法如下：遞歸解法：(2_8」.c)#includeintcont=l;/*全局變量，用于記錄所有可能的出棧序列個(gè)數(shù)*/voidprint(intstr[],intn);/*求整數(shù)序列str口從k到n的全排列*/voidperm(intstr[],intk,intn){inti,temp;if(k==n-l)print(str,n);else{for(i=k;i

9/*本函數(shù)判斷整數(shù)序列str口是否滿足進(jìn)出棧規(guī)則，若滿足則輸出*/voidprint(intstr[],intn)(inti,j,k,1,m,flag=l,b[2];for(i=0;istr[j]){if(m==0)b[m++]=str[j];else{if(str[j]>b[0]){flag=0;}elseb[0]=str[j];if(flag)/*滿足出棧規(guī)則則輸出str□中的序列*/{printf(，z%2d:",cont++);for(i=0;i

10");8)}intmainO{intstr[100],n,i;printf(*inputaint:*);/*輸出排列的元素個(gè)數(shù)*/scanf&n);

11for(i=0;i

12，z);perm(str,0,n);printf("

13");return0;當(dāng)參與進(jìn)出棧的元素個(gè)數(shù)為4時(shí)，輸出的結(jié)果如下圖所示。該算法執(zhí)行的時(shí)間復(fù)雜度為0(n!)o隨著n的增大，算法的執(zhí)行效率非常的低。非遞歸解法：(2_7_8.c)對(duì)一組數(shù)窮盡所有排列，還可一種更直接的方法，將一個(gè)排列看作一個(gè)長整數(shù)，則所有排列對(duì)應(yīng)著一組整數(shù)，將這組整數(shù)按從小到大的順序排成一個(gè)數(shù)列，從對(duì)應(yīng)最小的整數(shù)開始，按數(shù)列的遞增順序逐一列舉每個(gè)排列對(duì)應(yīng)的每一個(gè)整數(shù)，這能更有效地完成排列的窮舉。從一個(gè)排列找出對(duì)應(yīng)數(shù)列的下一個(gè)排列可在當(dāng)前排列的基礎(chǔ)上作部分調(diào)整來實(shí)現(xiàn)。倘若當(dāng)前排列為1,2,4,6,5,3,并令其對(duì)應(yīng)的長整數(shù)為124653。要尋找比長整數(shù)124653更大的排列，可從該排列的最后一個(gè)數(shù)字順序向前逐位考察，當(dāng)發(fā)現(xiàn)排列中的某個(gè)數(shù)字比它前一個(gè)數(shù)字大時(shí)，如本例中的6比它的前一位數(shù)字4大，則說明還有可能對(duì)應(yīng)更大整數(shù)的排列。但為順序從小到大列舉出所有的排列，不能立即調(diào)整得太大，如本例中將數(shù)字6與數(shù)字4交換得到的排列為126453就不是排列124653的下一個(gè)排列。為得到排列124653的下一個(gè)排列，應(yīng)從已考察過的那部分?jǐn)?shù)字中選出比數(shù)字4大，但又是它們中最小的那一個(gè)數(shù)字，比如數(shù)字5,與數(shù)字4交換。該數(shù)字也是從后向前考察過程中第一個(gè)比4大的數(shù)字，5與4交換后，得到排列125643。在前面數(shù)字1,2,5固定的情況下，還應(yīng)選擇對(duì)應(yīng)最小整數(shù)的那個(gè)排列，為此還需將后面那部分?jǐn)?shù)字的排列顛倒，如將數(shù)字6,4,3的排列順序顛倒，得到排列1,2,5,3,4,6,這才是排列1,2,4,6,95,3的下?個(gè)排列。按照以上想法可以編寫非遞歸程序?qū)崿F(xiàn)n個(gè)數(shù)的全排列，對(duì)滿足進(jìn)出棧規(guī)則的排列則計(jì)數(shù)并輸出。

14/*本程序輸出12.??n個(gè)序列進(jìn)棧出棧的序列*/ttincludeintpl(intn){inta[100];/*最大處理范圍為99個(gè)數(shù)*/intflag=l,flagl=O;FILE*rf;inti,j,k,x,count=0;rf=fopen("stack.txt","w");/*pl.txt用于存放進(jìn)出棧序列結(jié)果*/for(i=l;i<=n;i++)/*初始序列*/while(flag)/*還剩余未輸出的排列*/{flagl=l;/*判斷本次排列是否符合進(jìn)棧出棧序列*/for(i=l;i<=n;i++){j=i+l;while(j<=n&&a[j]>a[i])j++;/*找a[i]后第一個(gè)比a[i]小的元素a[j]*/k=j+l;while(k<=n)/*如果后還有比a[i]小且比a[j]大的元素，則此排列無效*/{if(a[k]a[j])flagl=0;k++;if(flagl){for(i=l;i<=n;i++)/*輸出當(dāng)前排列*/{printf(z/%4d，z,a[i]);fprintf(rf,"%4d”,a[i]);}printf('

15");fprintf(rf,"

16");count++;/*計(jì)數(shù)器加1*/

17}i=n;/*從后向前找相鄰位置后大前小的元素值*/while(i>l&&a[i]j&&a[i]=k&&x

18{intn,m=0;printf("pleaseinputn:*);/*輸入排列規(guī)模*/scanf(*%(!*,&n);m-pl(n);printf("

19m=%d”,m)；/*輸出滿足進(jìn)出棧的排列總個(gè)數(shù)*/}程序運(yùn)行時(shí)如果輸入4,則輸出的結(jié)果如下圖所示。該算法的時(shí)間復(fù)雜度也是0(n!)?結(jié)論：如果n個(gè)數(shù)按編號(hào)由小到大的順序進(jìn)棧，進(jìn)棧的過程中可以出棧，則所有可能的出棧序列的總數(shù)為：I1)!!(2)!nnnII第3章線性表的鏈?zhǔn)酱鎯?chǔ)3.1選擇題(1)兩個(gè)有序線性表分別具有n個(gè)元素與m個(gè)元素且nWm,現(xiàn)將其歸并成一個(gè)有序表，其最少的比較次數(shù)是(A)。A.nB.mC.n—1D.m+n(2)非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)滿足(C)。A.p->next==NULLB.p==NULLC.p->next==headD.p==head(3)在帶頭結(jié)點(diǎn)的單鏈表中查找x應(yīng)選擇的程序體是(C)。A.node*p=head->next;while(p&&p->info!=x)p=p->next;if(p->info-x)returnpelsereturnNULL;B.node*p=head;while(p&&p->info!=x)p=p->next;returnp;

20A.node*p=head->next;while(p&&p->info!=x)p=p->next;returnp;B.node*p=head;while(p->info!=x)p=p->next;returnp;(4)線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址(D)。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)不連續(xù)都可以(5)在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持單鏈表仍然有序的時(shí)間復(fù)雜度是(B)。A.0(1)B.0(n)C.0(n2)D.0(nlog2n)(6)用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)(D)。A.僅修改隊(duì)頭指針B,僅修改隊(duì)尾指針C.隊(duì)頭、隊(duì)尾指針都要修改D.隊(duì)頭,隊(duì)尾指針都可能要修改（7）若從鍵盤輸入n個(gè)元素，則建立一個(gè)有序單向鏈表的時(shí)間復(fù)雜度為（B）。A.0（n）B.0（n2）C.0（n3）D.0（n?Iog2n）（8）下面哪個(gè)術(shù)語與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)（D）。A.順序表B.鏈表C.散列表D.隊(duì)列（9）在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（A）。A.p->next=p->next->next;B.p=p->next;p->next=p->next->next;C.p->next=p->next;D.p=p->next->next;（10）在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行（B）。A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;C.s->next=p->next;p=s;D.p->next=s;s->next=p;3.2設(shè)計(jì)一個(gè)算法，求一個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)?！敬稹浚簡捂湵泶鎯?chǔ)結(jié)構(gòu)定義如下（相關(guān)文件：linklist.h）

21ttinclude12ffincludetypedefstructnode{intdata;structnode*next;}linknode;typedeflinknode*linklist;/*尾插法創(chuàng)建帶頭結(jié)點(diǎn)的單鏈表*/linklistcreatlinklist(){linklisthead,r,x,s;head=r=(1inklist)malloc(sizeof(linknode));printfC

22請(qǐng)輸入一組以0結(jié)束的整數(shù)序列：

23〃);scanf&x);while(x){s=(linklist)malloc(sizeof(linknode));s->data=x;r->next=s;r=s;scanf("%d",&x);}r->next=NULL;returnhead;

24}/*輸出帶頭結(jié)點(diǎn)的單鏈表*/voidprint(linklisthead){linklistp;p=head->next;printf(*Listis:

25");while(p){printfp->data);p=p->next;printf("

26");}基于上述結(jié)構(gòu)定義，求單鏈表中的結(jié)點(diǎn)個(gè)數(shù)的算法程序如下：intcount(linklisthead){intc=0;linklistp=head;while(p){c++;13p=p->next;)returnc;)3.2設(shè)計(jì)一個(gè)算法，求一個(gè)帶頭結(jié)點(diǎn)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)。【答】：帶頭結(jié)點(diǎn)的單鏈表的存儲(chǔ)結(jié)構(gòu)定義同題3.2,實(shí)現(xiàn)本題功能的算法程序如下

27(3_3.c)ttinclude"linklist,h”intcount(linklisthead){intc=0;linklistp=head->next;while(p){c++;p=p->next;returnc;main()/*測(cè)試函數(shù)*/{linklisthead;head=creatlinklist0;print(head);printf(zz

28Lengthofheadis:%dzz,count(head));getchO;}當(dāng)輸入5個(gè)數(shù)據(jù)時(shí)，產(chǎn)生的輸出結(jié)果如下圖所示：3.2設(shè)計(jì)一個(gè)算法，在一個(gè)單鏈表中值為y的結(jié)點(diǎn)前面插入一個(gè)值為x的結(jié)點(diǎn)。即使值為x的新結(jié)點(diǎn)成為值為y的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)?！敬稹浚簍tinclude"linklist,h”voidinsert(linklisthead,inty,intx){/*在值為y的結(jié)點(diǎn)前插入?個(gè)值為x的結(jié)點(diǎn)*/linklistpre,p,s;

29pre=head;p=head->next;14while(p&&p->data!=y){pre=p;p=p->next;if(p)/*找到了值為y的結(jié)點(diǎn)*/{s=(linklist)malloc(sizeof(linknode));s->data=x;s->next=p;pre->next=s;}}voidmain()/*測(cè)試程序*/{linklisthead;inty,x;head=creatlinklist0;/*創(chuàng)建單鏈表*/print(head);/*輸出單鏈表*/printf(*

30請(qǐng)輸入y與x的值:

31");scanf("%d%d”,&y,&x);insert(head,y,x);print(head);)程序的一種運(yùn)行結(jié)果如下圖所示：

323.2設(shè)計(jì)一個(gè)算法，判斷一個(gè)單鏈表中各個(gè)結(jié)點(diǎn)值是否有序?！敬稹浚篰include"linklist.h"intissorted(linklisthead,charc)/*當(dāng)參數(shù)c='a'時(shí)判斷鏈表是否為升序，當(dāng)參數(shù)c='d'是判斷鏈表是否為降序*/{intflag=l;linklistp=head->next;switch(c){caseJa:/*判斷帶頭結(jié)點(diǎn)的單鏈表head是否為升序*/15while(p&&p->next&&flag){if(p->data<=p->next->data)p=p->next;elseflag=O;}break;case'd':/*判斷帶頭結(jié)點(diǎn)的單鏈表head是否為降序*/while(p&&p->next&&flag){if(p->data>=p->next->data)pzzp->next;elseflag=O;}break;)returnflag;}

33intmain()/*測(cè)試程序*/{linklisthead;head=creatlinklist();print(head);if(issorted(head,*a*))printf("單鏈表head是升序排列的!

34");elseif(issorted(head,'d'))printf("單鏈表head是降序排列的！

35");elseprintf("單鏈表head是無序的！

36");}程序運(yùn)行時(shí)的三種輸出結(jié)果如下圖所示：3.6設(shè)計(jì)一個(gè)算法，利用單鏈表原來的結(jié)點(diǎn)空間將一個(gè)單鏈表就地轉(zhuǎn)置?！敬稹浚篰include"linklist.h"voidverge(1inklisthead){/*本函數(shù)的功能是就地倒置帶頭結(jié)點(diǎn)的單鏈表*/16linklistp,q;p=head->next;head->next=NULL;while(p)/*每次從原表取一個(gè)結(jié)點(diǎn)插入到新表的最前面*/{q=p;p=p->next;

37q->next=head->next;head->next=q;intmain()/*測(cè)試函數(shù)*/(linklisthead;head=creatlinklist();/*創(chuàng)建單鏈表*/print(head);/*輸出原單鏈表*/verge(head);/*就地倒置單鏈表*/print(head);/*輸出倒置后的單鏈表*/)3.7設(shè)計(jì)一個(gè)算法，將一個(gè)結(jié)點(diǎn)值自然數(shù)的單鏈表拆分為兩個(gè)單鏈表，原表中保留值為偶數(shù)的結(jié)點(diǎn)，而值為奇數(shù)的結(jié)點(diǎn)按它們?cè)谠碇械南鄬?duì)次序組成一個(gè)新的單鏈表?！敬稹浚簍tinclude"linklist.h"linklistsprit(1inklisthead){/*將帶頭結(jié)點(diǎn)的單鏈表head中的奇數(shù)值結(jié)點(diǎn)刪除生成新的單鏈表并返回*/linklistL,pre,p,r;L=r=(1inklist)malloc(sizeof(linknode));r->next=NULL;pre二head;p=head->next;while(p){if(p->data%2==l)/*刪除奇數(shù)值結(jié)點(diǎn)*/{pre->next=p->next;

38r->next=p;r=p;p=pre->next;else/*保留偶數(shù)值結(jié)點(diǎn)*/{pre=p;p=p->next;}17}r->next=NULL;/*置鏈表結(jié)束標(biāo)記*/returnL;}intmain()/*測(cè)試函數(shù)*/{linklisthead,L;head=creatlinklist();/*創(chuàng)建單鏈表*/print(head);/*輸出原單鏈表*/L=sprit(head);/*分裂單鏈表head*/printf(*

39原單鏈表為：

40");print(head);/*輸出倒置后的單鏈表*/printfC

41分裂所得奇數(shù)單鏈表為：

42〃)；print(L);)

43本程序的一組測(cè)試情況如下圖所示。3.7設(shè)計(jì)一個(gè)算法，對(duì)一個(gè)有序的單鏈表，刪除所有值大于x而不大于y的結(jié)點(diǎn)?！敬稹浚簍tinclude"linklist,h”voiddeletedata(linklisthead,datatypex,datatypey){/*刪除帶頭結(jié)點(diǎn)單鏈表中所有結(jié)點(diǎn)值大于x而不大于y的結(jié)點(diǎn)*/linklistpre=head,p,q;p=head->next;/*初始化*/while(p&&p->data<=x)/*找第1處大于x的結(jié)點(diǎn)位置*/{pre=p;p=p->next;}while(p&&p->data<=y)/*找第1處小于y的位置*/p=p->next;q=pre->next;/*刪除大于x而小于y的結(jié)點(diǎn)*/pre->next=p;pre=q->next;18while(pre!=p)/*糅放被刪除結(jié)點(diǎn)所占用的空間*/{free(q);q=pre;pre=pre->next;}

44)voidmain()/*測(cè)試函數(shù)*/{linklisthead,L;datatypex,y;head=creatlinklist();/*創(chuàng)建單鏈表*/print(head);/*輸出原單鏈表*/printfC

45請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù)區(qū)間：

46")；scanf("%d%d”,&x,&y);deletedata(head,x,y);print(head);/*輸出刪除后的單鏈表*/}3.7設(shè)計(jì)一個(gè)算法，在雙鏈表中值為y的結(jié)點(diǎn)前面插入一個(gè)值為x的新結(jié)點(diǎn)。即使值為x的新結(jié)點(diǎn)成為值為y的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)?！敬稹浚菏紫榷x雙鏈表的數(shù)據(jù)結(jié)構(gòu)，相關(guān)文件dlink.h,內(nèi)容如下：typedefintdatatype;/*預(yù)定義的數(shù)據(jù)類型*/typedefstructdlink_node{/*雙鏈表結(jié)點(diǎn)定義*/datatypedata;structdlink_node*llink,*rlink;}dnode;typedefdnode*dlinklist;/*雙鏈表結(jié)點(diǎn)指針類型定義*//*尾插法創(chuàng)建帶頭結(jié)點(diǎn)的雙鏈表*/dlinklistcreatdlinklist(void)

47{dlinklisthead,r,s;datatypex;head=r=(dlinklist)malloc(sizeof(dnode));/*建立雙鏈表的頭結(jié)點(diǎn)*/head->llink=head->rlink=NULL;printfC

48請(qǐng)輸入雙鏈表的內(nèi)容：(整數(shù)序列，以0結(jié)束)

49〃)；scanf&x);while(x)/*輸入結(jié)點(diǎn)值信息,以0結(jié)束*/{s=(dlinklist)malloc(sizeof(dnode));s->data=x;s->rlink=r->rlink;/*將新結(jié)點(diǎn)s插入到雙鏈表鏈尾*/19s->llink=r;r->rlink=s;r=s;scanf("%d",&x);}returnhead;}/*輸出雙鏈表的內(nèi)容*/voidprint(dlinklisthead){dlinklistp;p=head->rlink;printfC

50雙鏈表的內(nèi)容是：

51");while(p)

52{printf(*%5d*,p->data);p=p->rlink;本題的求解程序如下:ftincludettinclude"dlink.h"voidinsertxaty(dlinklisthead,datatypey,datatypex){dlinklists,p;/*首先在雙鏈表中找y所在的結(jié)點(diǎn)，然后在y前面插入新結(jié)點(diǎn)*/p=head->rlink;while(p&&p->data!=y)p=p->rlink;if(!p)printf(*

53雙鏈表中不存在值為y的結(jié)點(diǎn)，無法插入新結(jié)點(diǎn)!

54");else/*插入值為x的新結(jié)點(diǎn)*/{s=(dlinklist)malloc(sizeof(dnode));s->data=x;s->rlink=p;s->llink=p->llink;p->llink->rlink=s;p->llink=s;}}voidmain()/*測(cè)試函數(shù)*/{dlinklisthead;datatypex,y;20

55head=creatdlinklist();print(head);printfC

56請(qǐng)輸入要輸入的位置結(jié)點(diǎn)值y:

57");scanf&y);printf(*

58請(qǐng)輸入要輸入的結(jié)點(diǎn)值x:

59");scanf&x);insertxaty(head,y,x);/*在值為y的結(jié)點(diǎn)前插入值為x的新結(jié)點(diǎn)*/print(head);/*輸出新的雙鏈表*/getchO;)本程序的一組測(cè)試情況如下圖所示。3.10設(shè)計(jì)一個(gè)算法，從右向左打印一個(gè)雙鏈表中各個(gè)結(jié)點(diǎn)的值。【答】：本題的雙鏈表定義同題3.9,實(shí)現(xiàn)從右向左打印雙鏈表的各個(gè)結(jié)點(diǎn)的值可以用遞歸程序?qū)崿F(xiàn)如下：ttincludeftinclude"dlink.h"voidvprint(dlinklisthead){/*遞歸方法從右向左打印雙鏈表的值*/if(head->rlink){vprint(head->rlink);printf("%5d”,head->r1ink->data);voidmain()/*測(cè)試函數(shù)*/{dlinklisthead;head=creatdlinklist();

60print(head);printfCXn從右向左打印的雙鏈表的內(nèi)容是:

61〃)；21vprint(head);getchO;}本程序的一組測(cè)試情況如下圖所示。3.11設(shè)計(jì)一個(gè)算法，將一個(gè)雙鏈表改建成一個(gè)循環(huán)雙鏈表?！敬稹浚簍tincludettinclude"dlink.h"/*將一個(gè)雙鏈表改成循環(huán)雙鏈表*/voiddlinktocdlink(dlinklisthead){dlinklistr;r=head;while(r->rlink)/*尋找尾結(jié)點(diǎn)*/r=r->rlink;head->11ink=r;r->rlink=head;voidprintcd1ink(dlinklisthead){/*打印雙鏈表*/dlinklistp;p=head->r1ink;whi1e(p!=head)

62{printf(*%5d*,p->data);p=p->rlink;}}intmain()/*測(cè)試函數(shù)*/{dlinklisthead;head=creatdlinklist();dlinktocdlink(head);printf("

63循環(huán)雙鏈表的內(nèi)容是：

64");printcdlink(head);}22第4章字符串、數(shù)組和特殊矩陣1.1稀疏矩陣常用的壓縮存儲(chǔ)方法有(三元組順序存儲(chǔ))和(十字鏈表)兩種。1.2設(shè)有一個(gè)10X10的對(duì)稱矩陣A采用壓縮方式進(jìn)行存儲(chǔ)，存儲(chǔ)時(shí)以按行優(yōu)先的順序存儲(chǔ)其下三角陣，假設(shè)其起始元素a00的地址為1,每個(gè)數(shù)據(jù)元素占2個(gè)字節(jié)，則a65的地址為(53)。1.3若串S二usoftware",其子串的數(shù)目為(36)。1.4常對(duì)數(shù)組進(jìn)行的兩種基本操作為(訪問數(shù)據(jù)元素)和(修改數(shù)組元素)。1.5要計(jì)算一個(gè)數(shù)組所占空間的大小，必須已知(數(shù)組各維數(shù))和(每個(gè)元素占用的空間)。1.6對(duì)于半帶寬為b的帶狀矩陣，它的特點(diǎn)是：對(duì)于矩陣元素aij,若它滿足(|i-jI>b),則aij=Oo1.7字符串是一種特殊的線性表，其特殊性體現(xiàn)在(該線性表的元素類型為字符)。1.8試編寫一個(gè)函數(shù)，實(shí)現(xiàn)在順序存儲(chǔ)方式下字符串的strcompare(SI,S2)運(yùn)算?！敬稹浚?include

65ttincludettdefineMAXSIZE100typedefstruct{charstr[MAXSIZE];intlength;}seqstring;/*函數(shù)strcompare()的功能是：當(dāng)sl>s2時(shí)返回1,當(dāng)si二二s2時(shí)返回0,當(dāng)sls2.str[i]){m=l;break;}elseif(si.str[i]

66");23gets(si.str);51.length=strlen(si.str);printf(''inputchartos2:

67");gets(s2.str);

6851.length=strlen(s2.str);m=strcompare(si,s2);if(m=l)printf("sl>s2

69");elseif(m==-l)printf("s2>sl

70");elseif(m==0)printf(*sl=s2

71zz);}4.9試編寫一個(gè)函數(shù)，實(shí)現(xiàn)在順序存儲(chǔ)方式下字符串的replace(S,Tl,T2)運(yùn)算?！緟⒖汲绦?】：/*本程序用來在順序存儲(chǔ)下用快速匹配模式實(shí)現(xiàn)在字符串S中用T2替換所有T1出現(xiàn)的可能*/#include#include#include#definemaxsize100typedefstruct{charstr[maxsize];intlength;}seqstring;〃求next口函數(shù)voidgetnext(seqstring*p,intnext[]){inti,j;next[0]=-l;i=0;j=-l;while(ilength)

72(if(j==-l||p->str[i]==p->str[j]){++i;++j;next[i]=j;}elsej=next[j];}}〃快速模式匹配算法intkmp(seqstring*t,seqstring*p,intnext[],inttemppos){inti,j;24i=temppos,j=0;while(ilength&&jlength)if(j==-lIt->str[i]==p->str[j]){i++；j++；}elsej=next[j];}if(j==p->length)return(i-p->length);elsereturn(-1);}〃替換函數(shù)voidtakeplace(seqstring*S,seqstring*Tl,seqstring*T2){intnext[maxsize],temppos=0,pos,i;intlent1,lent2;

73lentl=strlen(Tl->str);//求T1串長度lent2=strlen(T2->str);〃求T2串長度getnext(Tl,next);〃求T1串的next[]向量do{pos=kmp(S,Tl,next,temppos);〃快速模式匹配temppos=pos+T1->1ength;if(pos!=-l)〃匹配成功(if(lentl>lent2)//Tl串長度大于T2串長度for(i=temppos;ilength;i++)〃前移S->str[i-lentl+lent2]=S->str[i];for(i=0;ilength;i++)〃替換S->str[pos+i]=T2->str[i];S->length-=lentl-lent2;//修改長度)elseif(lent2>lentl)//T2串長度大于T1串長度ifor(i=S->length-l;i>=temppos;i-)〃后移留空S->str[i+lent2-lentl]=S->str[i];for(i=0;ilength;i++)〃替換25

74S->str[pos+i]=T2->str[i];S->length+=lent2-lentl;〃修改長度}else//Tl長度與T2長度相等{for(i=0;ilength;i++)S->str[pos+i]=T2->str[i];}temppos=pos+T2->length;〃修改下一次模式匹配的起點(diǎn)位置}}while(pos!=-1);S->str[S->length]=，\0f;intmain(){seqstring*S,*T1,*T2;printf("

75

76本程序用來實(shí)現(xiàn)字符串替換，將S中用T2替換T1所有出現(xiàn)

77Thisprogramisusedforcharactersbatchtakeingplace,TheT1charactersbatchwilltakeplaceal1theT2'sappearancesincharactersbatchS:

78

79");printf(“請(qǐng)輸入S中的字符(pleseinputcharactersbatchS:)

80");S=(seqstring*)malloc(sizeof(seqstring));Tl=(seqstring*)malloc(sizeof(seqstring));T2=(seqstring*)malloc(sizeof(seqstring));scanfS->str);S->length=strlen(S->str);printf("輸入要被替換的串(inputTl):

81*);scanf('%s”,Tl->str);

82Tl->length=strlen(Tl->str);printf("輸入替換串(inputT2):

83");scanfT2->str);T2->length=strlen(T2->str);takeplace(S,Tl,T2);printf(〃替換后的字符串為：

84〃)；printf("%s

85”,S->str);free(S);free(Tl);free(T2);[參考程序2]：#include26ftdefineMAXSIZE100typedefstruct{charstr[MAXSIZE];intlength;}seqstring;voidgetnext(seqstringp,intnext[])〃求模式的next函數(shù){inti,j;next[0]=-l;i=0;j=-l；while(i

86{++i;++j;next[i]=j;}elsej=next[j];}}voidreplace(seqstring*s,seqstringtl,seqstringt2,intnext[]){inti,j,k,c,m;i=0;j=O;k=O;while(ilength)｛產(chǎn)0；while(ilength&&jstr[i]==tl.str[j]){i++；j++;}elsej=next[j];}if(j=tl.length)//匹配成功{c=i-tl.length;if(tl.Iength==t2.length)〃兩串長度相等直接替換for(k=0;kstr[c+k]=t2.str[k];elseif(tl.Iengthlength-l;m-)s->str[t2.length-tl.length+m]=s->str[ni];//后移留空for(k=0;kstr[c+k]=t2.str[k];

87s->length=s->length-tl.Iength+t2.length;s->str[s->length]=，\0J;)27else{for(m=i-l;mlength;m++)〃前移s->str[m-tl.Iength+t2.length]=s->str[m];for(k=0;kstr[c+k]=t2.str[k];s->length=s->length-tl.Iength+t2.length;s->str[s->length]=，\0*;)i=i+t2.length-tl.length;}i++；}}intmainO{intnext[MAXSIZE];seqstrings,tl,t2;printf("Inputstrings:");〃輸入主串gets(s.str);

88printf(*

89lnputstringtl:*)；//輸入模式串gets(tl.str);printfCAnlnputstringt2:〃)；//輸入擬替換的串gets(t2.str);s.length=strlen(s.str);tl.length=strlen(tl.str);t2.Iength=strlen(t2.str);getnext(tl,next);replace(&s,tl,t2,next);puts(s.str);4.10試編寫一個(gè)函數(shù)，實(shí)現(xiàn)在鏈?zhǔn)酱鎯?chǔ)方式下字符串的strcompare(SI,S2)運(yùn)算。【參考程序】：/*建立字符串鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)文件linkstring,h*/ttincludettincludetypedefstructnode[chardata;structnode*next;}linkstrnode;28typedeflinkstrnode*1inkstring;/**//*尾插法建立單鏈表*//**/

90voidstrcreate(1inkstring*S){charch;linkstrnode*p,*r;*S=NULL;r=NULL;while((ch=getchar())!=>

91){p=(linkstrnode*)malloc(sizeof(linkstrnode));p->data=ch;/*產(chǎn)生新結(jié)點(diǎn)*/if(*S==NULL)/*新結(jié)點(diǎn)插入空表*/{*S=p;r=p;}else{r->next=p;r=p;}}if(r!=NULL)r->next=NULL;/*處理表尾結(jié)點(diǎn)指針域*/}/**//*輸出單鏈表的內(nèi)容*//**/voidprint(linkstringhead)(linkstrnode*p;p=head;while(p){printf(，z%c->”,p->data);p=p->next;}printf("

92");

93}ttinclude"linkstring,h”intstrcompare(1inkstrnode*Sl,1inkstrnode*S2){while(S1&&S2){if(Sl->data>S2->data)return1;elseif(Sl->datadata)29return-1;Sl=Sl->next;S2=S2->next;}if(SI)return1;elseif(S2)return-1;return0;}intmainO{linkstringsi,s2;intk;printfCAnPleaseinputstrcreate(&sl);/*建立字符串si*/print(si);printf("

94Pleaseinputs2:");

95strcreate(&s2);/*建立字符串s2*/print(s2);k=strcompare(sl,s2);if(k==l)printf("sl>s2");elseif(k=="l)printfCsldata=p->data;if(L==NULL)L=r=s;else{r->next=s;30r=s;}

96p=p->next;}if(r!=NULL)r->next=NULL;returnL;/*-—*//*在字符串S中用T2替換T1*/—*/linkstringreplace(linkstringS,linkstringTl,linkstringT2){linkstringp,q,r,s,pre,temp,pos;intflag=l;if(S==NULL||T1==NULL)returnS;/*若S為空或T1為空，則原串不變*/pre=NULL;pos=S;/*pos表示可能的T1串在S中的起始位置*/while(pos&&flag)/*flag表示S中存在Tl*/{P二pos;q=Tl;while(p&&q)/*從pos開始找子串Tl*/{if(p->data==q->data){p=p->next;q=q->next;}else{pre=pos;pos=pos->next;p=pos;q二Tl;}

97}if(q!=NULL)flag=0;/*未找到子串Tl*/else{flag=1;/*找到了子串門，用T2代替Tl*/r=pos;while(r!=p)/*首先刪除子串Tl,最后p指向刪除串T1的下一個(gè)結(jié)點(diǎn)*/{s=r;r=r->next;free(s);}if(T2!=NULL)/*T2不為空*/31{temp=r=copy(T2);/*復(fù)制一個(gè)T2串*/while(r->next!=NULL)/*找temp串的尾結(jié)點(diǎn)*/r=r->next;r->next=p;if(pre==NULL)/*如果T1出現(xiàn)在S的鏈頭*/S二temp;/*新串成為鏈?zhǔn)?/else/*T1不是鏈?zhǔn)状?/pre->next=temp;pre=r;pos=p；/*從p開始繼續(xù)找子串n*/)else/*原T2子串為空*/

98{if(pre=NULL)/*T1為鏈?zhǔn)状?/S=p;elsepre->next=p;pos=p;returnS;intmain(){linkstringS,Tl,T2;printfCAnPleaseinputS:");strcreate(&S);/*建立字符串S*/print(S);printf(*

99PleaseinputT1:*);strcreate(&T1);/*建立字符串Tl*/print(Tl);printf(*

100PleaseinputT2:');strcreate(&T2);/*建立字符串T2*/print(T2);S=replace(S,Tl,T2);printf(*

101Theresultis:

102");print(S);}4.12已知如下字符串，求它們的next數(shù)組值：(1)“bbdcfbbdac”

10332【答】：-1010001230(1)waaaaaaa【答】：-1012345(2)ababbabab”【答】：-100112324.13已知正文t="ababbaabaa"，模式p:“aab”,試使用KMP快速模式匹配算法尋找P在t中首次出現(xiàn)的起始位置，給出具體的匹配過程分析?！敬稹浚耗Ｊ絇的next向量如下表所示：012aab-101第一趟匹配：0123456789ababbaabaaaai=l,j=l,匹配失敗，此時(shí)j取next[l]=0,即下一趟匹配從i=l,j=0開始；第二趟匹配：0123456789ababbaabaaai=Lj=0,匹配失敗,此時(shí)j=next[0]=T,下一趟匹配從i=2,j=0開始;第三趟匹配：0123456789ababbaabaai=3,j=l,匹配失敗，此時(shí)j=next[l]=O,下一趟匹配從i=3,j=0開始；

104第四趟匹配：0123456789ababbaabaaai=3,j=0,匹配失敗，此時(shí)j=next[0]=配,下一趟匹配從i=4,j=0開始；第五趟匹配：0123456789ababbaabaaai=4,j=0,匹配失敗,此時(shí)j=next[0]=T,下一趟匹配從i=5,j=0開始；第五趟匹配：012345678933ababbaabaaaabi=8,j=3,匹配完成，表明匹配成功的位置是：i-j=5。4.14已知三維數(shù)組A[3][2][4],數(shù)組首地址為100,每個(gè)元素占用1個(gè)存儲(chǔ)單元，分別計(jì)算數(shù)組元素A[0][1][2]在按行優(yōu)先和按列優(yōu)先存儲(chǔ)方式下的地址。【答】：A[0][1][2]按行優(yōu)先方式在內(nèi)存的存儲(chǔ)地址為：100+0*8+1*4+2=106[2]按列優(yōu)先方式在內(nèi)存的儲(chǔ)儲(chǔ)地址為：100+2*6+1*3+0*8=1154.15已知兩個(gè)稀疏矩陣A和B,其行數(shù)和列數(shù)均對(duì)應(yīng)相等，編寫一個(gè)函數(shù)，計(jì)算A和B之和，假設(shè)稀疏矩陣采用三元組表示?！緟⒖汲绦?】：#include

105typedefstruct{intdata[100][100];intm,n;/*分別存放稀疏矩陣的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)*/}matrix;typedefintspmatrix[100][3];〃三元組存儲(chǔ)結(jié)構(gòu)spmatrixc;voidadd(spmatrixa,spmatrixb,spmatrixc)〃基于三元組結(jié)構(gòu)的矩陣相加算法{inti,j,k,t,r;i=j=k=l;while(i<=a[0][2]&&j<=b[0][2]){if(a[i][0]b[j][0]||(a[i][0]==b[j][0]&&a[i][l]>b[j][1])){c[k][O]=b[j][0];c[k][l]=b[j][1];c[kH2]=b[j]⑵;j++；k++;else

106if(a[i][O]=b[j][0]&&(a[i][l]=b[j][1])){c[k][O]=a[i][0];34c[k][l]=a⑴[1];c[k][2]=a[i][2]+b[j][2];i++;j++;if(c[k][2]!=0)k++;/*如果相加的和不為0,則生成一個(gè)有效項(xiàng)*/))while(j<=b[0][2])(c[k][0]=b[j][0];c[k][l]=b[j][l]：c[k][2]=b[j][2];j++；k++;)while(i<=a[0][2])!c[k][0]=a[i][0];c[k][l]=a[i][l];c[k][2]=a[i]⑵；i++;k++;c[0][0]=a[0][0]:c[0][l]=a[O][1];c[0][2]=k-l;

107)//函數(shù)compressmatrix將普通矩陣存儲(chǔ)轉(zhuǎn)換為二元組存儲(chǔ)結(jié)構(gòu)voidcompressmatrix(matrix*A,spmatrixB){inti,j,k：k=l;for(i=0;im;i++)for(j=0;jn;j++)if(A->data[i][j]!=0){B[k][0]=i;B[k][l]=j;B[k][2]=A->data[i][j]：k++;)B[0][0]=A->m;B[0][l]=A->n;B[0][2]=k-l：35i=0;printf("thespmatrixis:

108");while(i<=B[0][2]){printf("%d%5d%5d

109",B[i][0],B[i][1],B[i][2]):i++；voidcreat(intr,intw,matrix*s)

110{inti,j,data;printf('inputnumbers:

111/z);for(i=0;idata[i][j]=data;}printf(/zthearrayis:

112");for(i=0;idata[i][j]);printf;)s->m=r;s->n=w;}intmain(){matrixp,q;spmatrixa,b,c;intr,w,i;i=0;printf(*inputr,w<);/*輸入行和列*/

113scanf("%d%d”,&r,&w);creat(r,w,&p);creat(r,w,&q);compressmatrix(&p,a);compressmatrix(&q,b);i=0;add(a,b,c);printf(，zthespmatrixcis:

114〃)；36while(i<=c[0][2]){printf(*%d%5d%5d

115*,c[i][0],c[i][1],c[i][2]);i++；}}程序運(yùn)行時(shí)先輸入矩陣的行和列，然后按普通矩陣格式輸入矩陣值，一組程序測(cè)試用例運(yùn)行結(jié)果如下圖：【參考程序2】：37#include#includettdefineMAX100typedefstruct{intdata[MAX][3];intm,n,value;

116}matrix;matrix*Input(matrix*A){inti,j;A=(matrix*)malloc(sizeof(matrix));scanf("%d%d%d”,&A->m,&A->n,&A->value);A->data[0][0]=A->m;A->data[0][1]=A->n;A->data[0][2]=A->value;for(i=1;i<=A->value;i++){for(j=0;j<3;j++)scanf("%d”,&A->data[i][j]);)returnA;)voidOutput(matrix*A){inti,j;printf("************************************

117");for(i=0;i<=A->value;i++){for(j=0;j<3;j++)printf(*%d*,A_>data[i][j]);printf('

118");

119}printf("************************************

120");}matrix*addmatrix(matrix*A,matrix*B,matrix*C){inti=1,j=1,k=1;C=(matrix*)malloc(sizeof(matrix));while(i<=A->value&&j<=B->value)(if(A->data[i][0]==B->data[j][0])(38if(A->data[i][1]==B->data[j][1]){C->data[k][0]=A->data[i][0];C->data[k][1]=A->data[i][1];C->data[k][2]=A->data[i][2]+B->data[j][2];if(C->data[k][2]!=0)k++;i++；j++；elseif(A->data[i][1]data[j][1]){C->data[k][0]=A->data[i][0];C->data[k][1]=A->data[i][1];C->data[k][2]=A->data[i][2];k++;i++；}

121else(C->data[k][0]=B->data[j][0];C->data[k][1]=B->data[j][1];C->data[k][2]=B->data[j][2];k++;j++；}}elseif(A->data[i][0]data[j][0]){C->data[k][0]=A->data[i][0];C->data[k][1]=A->data[i][1];C->data[k][2]=A->data[i][2];k++;i++；elseC->data[k][0]=B->data[j][0];C->data[k][1]=B->data[j][1];C->data[k][2]=B->data[j][2];39k++;j++；

122}}while(i<=A->value){C->data[k][0]=A->data[i][0];C->data[k][1]=A->data[i][1];C->data[k][2]=A->data[i][2];k++;i++;}while(j<=B->value){C->data[k][0]=B->data[j][0];C->data[k][1]=B->data[j][1];C->data[k][2]=B->data[j][2];k++;j++；C->data[O][0]=(A->data[0][0]>=B->data[0][0])?A->data[0][0]:B->data[0][0];C->data[0][1]=(A->data[0][l]>=B->data[0][l])?A->data[0][1]:B->data[0][1];C->data[0][2]=k-1;C->value=k-l;returnC;}intmainO{matrix*A=NULL,*B=NULL,*C=NULL;printf("提示：請(qǐng)按三元組格式輸入矩陣內(nèi)容。

123");printf(，zInputAmatrix:

124z，);A=Input(A);

125printf("InputBmatrixAn"");B=Input(B);C=addmatrix(A,B,C);Output(C);free(A);free(B);40free(C);return0;程序運(yùn)行時(shí)按照三元組的格式輸入矩陣信息，程序運(yùn)行結(jié)果如下圖所示:4.16寫出兩個(gè)稀疏矩陣相乘的算法，計(jì)算：Cpn=Apm*Bmn其中，A、B和C都采用三元組表示法存儲(chǔ)。【答】：4.1cludettinclude#defineMAX100typedefstruct{intdata[MAX][3];intm,n,value;}matrix;matrix*Input(matrix*A){inti,j;

126A=(matrix*)malloc(sizeof(matrix));scanf("%d%d%d”,&A->m,&A->n,&A->value);A->data[0][0]=A->m;41A->data[0][1]=A->n;A->data[0][2]=A->value;for(i=1;i<=A->value;i++)ifor(j=0;j<3;j++)scanf("%d”,&A->data[i][j]);returnA;voidOutput(matrix*A)(inti,j;printf("*******************************

127");for(i=0;i<=A->value;i++)ifor(j=0;j<3;j-H-)printf(*%dA->data[i][j]);printf('

128");}printf("*******************************

129");}

130/*基于三元組存儲(chǔ)結(jié)構(gòu)的矩陣相乘算法*/matrix*MulMatrix(matrix*A,matrix*B,matrix*C){inti,j,k,r=l,p,q,s;C=(matrix*)malloc(sizeof(matrix));C->iD=A->m;C->n=B->n;C->data[0][0]=C->m;C->data[0][l]=C->n;for(i=0;im;i++)for(j=0;jn;j++){s=0;for(k=0;kn;k++)〃找A[i][k];p=l;while(p<=A->value)if(A->data[p][O]==i&&A->data[p][l]==k)break;42elsep++;〃找q=l；while(q<=B->value)if(B->data[q][O]==k&&B->data[q][l]=j)break;elseq++;if(p<=A->value&&q<=B->value)

131s=s+A->data[p][2]*B->data[q][2];}if(s!=0){C->data[r][0]=i;C->data[r][l]=j;C->data[r][2]=s;r++,))C->data[O][2]=r-l;C->value=r-l;returnC;intmain(){matrix*A=NULL,*B=NULL,*C=NULL;printf("提示：請(qǐng)按三元組格式輸入矩陣內(nèi)容。

132");printf(*InputAmatrix:

133z，);A=Input(A);printf(z，InputBmatrix:

134z，);B=Input(B);C=MulMatrix(A,B,C);Output(C);free(A);free(B);free(C);

135return0;}程序運(yùn)行時(shí)，要求按照三元組的格式輸入矩陣信息。4344第5章遞歸4.1試述遞歸程序設(shè)計(jì)的特點(diǎn)。【答】：(1)具備遞歸出口。遞歸出口定義了遞歸的終止條件，當(dāng)程序的執(zhí)行使它得到滿足時(shí)，遞歸執(zhí)行過程便終止。有些問題的遞歸程序可能存在幾個(gè)遞歸出口。(2)在不滿足遞歸出口的情況下，根據(jù)所求解問題的性質(zhì)，將原問題分解成若干子問題，子問題的求解通過以一定的方式修改參數(shù)進(jìn)行函數(shù)自身調(diào)用加以實(shí)現(xiàn)，然后將子問題的解組合成原問題的解。遞歸調(diào)用時(shí)，參數(shù)的修改最終必須保證遞歸出口得以滿足。4.2試簡述簡單遞歸程序向非遞歸程序轉(zhuǎn)換的方法。【答】：簡單遞歸程序轉(zhuǎn)換為非遞歸程序可以采用算法設(shè)計(jì)中的遞推技術(shù)。遞歸方法與遞推方法共同采用的分劃技術(shù)，為使用遞推技術(shù)解決遞歸問題奠定了基礎(chǔ)。由于簡單遞歸問題求解過程中無需回溯，因而要轉(zhuǎn)換成非遞歸方式實(shí)現(xiàn)完全可以使用遞推技術(shù)。為了使用自底向上的遞推方式來解決遞歸問題，利用子問題已有的解構(gòu)造規(guī)模較大子問題的解，進(jìn)而構(gòu)造原問題的解，必須建立原問題與子問題解之間的遞推關(guān)系，然后定義若干變量用于記錄求解過程中遞推關(guān)系的每個(gè)子問題的解；程序的執(zhí)行便是根據(jù)遞推關(guān)系，不斷修改這些變量的值，使之成為更大子問題的解的過程；當(dāng)?shù)玫皆瓎栴}解時(shí)，遞推過程便可結(jié)束了。4.3試簡述復(fù)雜遞歸程序向非遞歸程序轉(zhuǎn)換的方法，并說明棧在復(fù)雜遞歸程序轉(zhuǎn)換成非遞歸程序的過程中所起的作用?！敬稹浚簭?fù)雜遞歸問題在求解的過程中無法保證求解動(dòng)作一直向前，需要設(shè)置一些回溯點(diǎn)，當(dāng)求解無法進(jìn)行下去或當(dāng)前處理的工作已經(jīng)完成時(shí)，必須退回到所設(shè)置的回溯點(diǎn)，繼續(xù)問題的求解。因此，在使用非遞歸方式實(shí)現(xiàn)一個(gè)復(fù)雜遞歸問題的算法時(shí)，經(jīng)常使用棧來記錄和管理所設(shè)置的回溯點(diǎn)。5.4試給出例題5.1中Fact(5)的執(zhí)行過程分析。

136【答】：Fact(5)的執(zhí)行過程如下圖所示：4.5已知多項(xiàng)式pn(x)=aO+alx+a2x2+,,+anxn的系數(shù)按順序存儲(chǔ)在數(shù)組a中，試：(1)編寫一個(gè)遞歸函數(shù)，求n階多項(xiàng)式的值；45(2)編寫一個(gè)非遞歸函數(shù)，求n階多項(xiàng)式的值?！敬稹浚篺tinclude#includettincludedoublepnxl(doublea[],intn,doublex)//(1)遞歸函數(shù){if(n==0)returna[0];elsereturnpnxl(a,n-l,x)+a[n]*pow(x,n);}doublepnx2(doublea[],intn,doublex)//(2)非遞歸迭代函數(shù)(doublet;inti;t=a[n];for(i=n-l;i>=0;i)t=a[i]+t*x;returnt;)intmain()

137{double*a,x,p;intn,i;printf("請(qǐng)輸入n,x:

138");scanf("%d%lf”,&n,&x);a=(double*)malloc((n+l)*sizeof(double));printf("請(qǐng)輸入%d項(xiàng)系數(shù)：

139〃,n+1);for(i=0;i<=n;i++)scanf&a[i]);p=pnxl(a,n,x);printfp);p=pnx2(a,n,x);printf(,p);free(a);)5.6已知兩個(gè)一維整型數(shù)組a和b,分別采用遞歸和非遞歸方式編寫函數(shù)，求兩個(gè)數(shù)組的內(nèi)積(數(shù)組的內(nèi)積等于兩個(gè)數(shù)組對(duì)應(yīng)元素相乘后再相加所得到的結(jié)果)?！敬稹浚篺tincludeusingnamespacestd;46longsuml(inta[],intb[],intn)〃非遞歸函數(shù){longs=0;inti;for(i=0;i

140s+=a[i]*b[i];returns;longsum2(inta[],intb[],intn)〃遞歸函數(shù)if(n==l)returna[0]*b[0];elsereturnsum2(a,b,n-l)+a[n-l]*b[n-l];)intmain()(inti,n,*a,*b;longs;coutC〈”輸入數(shù)組的長度："<>n;a=newint[n];b=newint[n];cout<<”請(qǐng)輸入數(shù)組a的值"<>a[i];cout<<”請(qǐng)輸入數(shù)組b的值〃<

141s=suml(a,b,5);cout<<"非遞歸計(jì)算的和="<0且m>0【答】：//輸入m,和n的值，計(jì)算Ack(m,n)ttincludeintAck(intm,intn){if(m==0){returnn+1;)elseif(n==0)

142{returnAck(m-1,1);}else{returnAck(m-1,Ack(m,n-1));intmain(){intm,n;printf("Pleaseinputmn

143");scanf("%d%d”,&m,&n);printf("Ack(m,n)=%d

144”,Ack(m,n));return0;}5.8已知多項(xiàng)式Fn(x)的定義如下：1220()213()2(1)()1nnnnFxxnxFxnFxn=□□==□□

145試寫出計(jì)算Fn(x)值的遞歸函數(shù)?！敬稹浚?/輸入n,x計(jì)算F(x)ttinclude//為了符合遞歸函數(shù)的表達(dá)這里將x作為參數(shù)傳遞，在實(shí)際運(yùn)用中建議使用全局變量。//C++中也可以傳遞引用intFunction(intn,constint&x)intFunction(intn,intx){if(n==0){return1;}elseif(n==1)48——{return2*x;}else{return2*x*Function(n-1,x)-2*(n-1)*Function(n-2,x);}}intmain(){intn,x;printf("inputn,x:

146");scanf("%d%d”,&n,&x);printf(“F(x)=%d

147”,Function(n,x));return0;

1485.9n階Hanoi塔問題：設(shè)有3個(gè)分別命名為X,丫和Z的塔座，在塔座X上從上到下放有n個(gè)直徑各不相同、編號(hào)依次為1,2,3,n的圓盤(直徑大的圓盤在下，直徑小的圓盤在上)，現(xiàn)要求將X塔座上的n個(gè)圓盤移至塔座Z上，并仍然按同樣的順序疊放，且圓盤移動(dòng)時(shí)必須遵循以下規(guī)則：(1)每次只能移動(dòng)一個(gè)圓盤；(2)圓盤可以插在塔座X,丫和Z中任何一個(gè)塔座上；(3)任何時(shí)候都不能將一個(gè)大的圓盤壓在一個(gè)小的圓盤之上。試編寫一個(gè)遞歸程序?qū)崿F(xiàn)該問題。【答】：#includevoidHanoi(intn,charx,chary,charz)(if(n==l)printf(*%c—>%c

149”,x,z);elseIHanoi(n-1,x,z,y);printf(*%c—>%c

150”,x,z);Hanoi(n-1,y,x,z);

151intn;printf("請(qǐng)輸入盤子個(gè)數(shù)：”)；49scanf&n);Hanoi(n,'X','Y','Z');return0;)5.10八皇后問題：在一個(gè)8X8格的國際象棋棋盤上放上8個(gè)皇后，使其不能相互攻擊，即任何兩個(gè)皇后不能處于棋盤的同一行、同一列和同一斜線上。試編寫一個(gè)函數(shù)實(shí)現(xiàn)八皇后問題?！敬稹浚航夥ㄒ唬?程序place.cpp)解向量：(xl,x2,,,,xn)顯約束：xi=l,2,n隱約束：1)不同列：xiWxj2)不處于同一正、反對(duì)角線：i-j|#=|xi-xj|ttincludettinclude#definen8intx[n+l]={0};〃x[i]的含義表示第i行放置在x[i]列intsum=0;//sum用于記錄n后問題的所有解

152voidprint。；〃輸出n后問題的解intPlace(intk)//檢測(cè)第k行的皇后放置是否符后規(guī)則{for(intj=l;jn){sum++;print();〃輸出一種解方案getchar();50}elsefor(inti=l;i<=n;i++){x[t]=i;〃試探在第t行放在第i列if(Place(t))Backtrack(t+1);}}voidprint()〃輸出n后問題的解{inti;printfC%d皇后問題的第%d種解為：

153”,n,sum);for(i=l;i<=n;i++)printf("%d:%d

154”,i,x[i]);

155intmain()Backtrack（1）;}解法二：程序思想：用3個(gè)數(shù)組分別存放8歹IJ,15個(gè)左對(duì)角線和15個(gè)右對(duì)角線的值，同時(shí)用一個(gè)8元素大小的數(shù)組記錄下放置的皇后的位置。初始時(shí)將三個(gè)數(shù)組全部標(biāo)記為Oo一，從第一行開始，從左向右開始查找。當(dāng)找到第一個(gè)能夠放下棋子的點(diǎn)x,y（其對(duì)應(yīng)的歹U,左對(duì)角，右對(duì)角全部為0）后，將此棋子所對(duì)應(yīng)的列，左對(duì)角，右對(duì)角全部設(shè)置為1,然后繼續(xù)放置下一行——x+1行（調(diào)用自身的子函數(shù)）。二，當(dāng)其子函數(shù)執(zhí)行完畢后，將放在x,y上的點(diǎn)拿起，然后將這點(diǎn)對(duì)應(yīng)的列，左對(duì)角，右對(duì)角元素全部置0,然后繼續(xù)在此行的y后查找能放置的點(diǎn)。三，如果當(dāng)前要放置的棋子為第9個(gè)棋子的時(shí)候，打印結(jié)果。程序見5」0.c（遞歸法）5_10_byStack.c（用?；厮莘ǎ?*八皇后問題遞歸解法*/#includeintleft[16],right[16],row[9],queen[9],count=0;/*分別用來存放左對(duì)角線和右對(duì)角線的使用情況,row數(shù)組記錄行數(shù)的棋子擺放情況，未使用的話就賦予0,使用的話就賦予1*//*row的數(shù)組用來存放列的使用情況，當(dāng)?shù)趎行，第m列被使用的時(shí)候在row[n]=m*//*其中queen數(shù)組用來專門存放當(dāng)前皇后的擺放情況*/51intprin（）/*打印出皇后的放置情況*/{intm;count++;

156printf(*The%dth”,count);for(m=l;m<=8;m++)printf(*%d”,queen[m]);printf(〃

157");return0;)intkaiserin(intline)/*line表示當(dāng)前放棋子的列數(shù)，第一次放的時(shí)候?yàn)?列*/{inti;/*本變量用來記錄當(dāng)前行放子的列數(shù)*/for(i=l;i<=8;i++)if((row[i]|left[i+lineT]|lright[8-i+line])=0)/*看當(dāng)前的列是否可以放*/{row[i]=l;left[i+line-l]=l;right[8-i+line]=l;queen[line]=i;if(line=8)/*如果當(dāng)前找到第8行了，說明找成功了，打印*/prin();elsekaiserin(line+l);/*找到了，但是還沒找完，將這點(diǎn)放上，然后嘗試下一列*/left[i+line-l]=0;row[i]=0;right[8-i+line]=0;queen[line]=0;/*不管找到?jīng)]找到，重新初始化當(dāng)前放子的點(diǎn)，開始右移放子*/}return0;

158)voidinit()/*將三個(gè)數(shù)組進(jìn)行初始化*/for(i=l;i<16;i++)left[i]=right[i]=O;for(i=l;i<9;i++)queen[i]=row[i]=0;}intmain(){init();kaiserin(l);return0;)52/*八皇后問題回溯法*/#includeftdefinemax10typedefstruct{/*用來存放回溯點(diǎn)的信息，row用來存放回溯點(diǎn)所放的行數(shù)，line用來存放所放的列數(shù)*/introw;intline;

159}node;intleft[16],right[16],row[9],queen[9],count=0;/*分別用來存放左對(duì)角線和右對(duì)角線的使用情況,row數(shù)組記錄行數(shù)的棋子擺放情況，未使用的話就賦予0,使用的話就賦予1*//*row的數(shù)組用來存放列的使用情況，當(dāng)?shù)趎行，第m列被使用的時(shí)候在row[n]=m*//*其中queen數(shù)組用來專門存放當(dāng)前皇后的擺放情況*/voidprint()/*打印出皇后的放置情況*/{intm;count++;printf(*The%dth*,count);for(m=1;m<=8;m++)printf(*%d”,queen[m]);printf('

160");}voidinit()/*將三個(gè)數(shù)組進(jìn)行初始化*/{inti;for(i=l;i<16;i++)queen[i]=left[i]=right[i]=O;for(i=l;i<9;i++)row[i]=0;)intkaiserin(){nodeback[max];intopline=l,oprow=l,i,find,top=0;while(l)/*循環(huán)條件用真，用return來結(jié)束循環(huán)和整個(gè)函數(shù)*/{find=0;

161for(i=oprow;i<=8;i++)if((row[i]|left[i+opline-l]||right[8-i+opline])==0)/*判斷當(dāng)前的點(diǎn)是否可放*/{find=l;/*找到的話結(jié)束循環(huán)*/break;53}if(find)/*找到了這點(diǎn)*/(oprow=i;row[oprow]=1;left[oprow+opline-l]=l;right[8-oprow+op1ine]=1;queen[opline]=oprow;/*把這個(gè)點(diǎn)放上*/top++;back[top].row=oprow;back[top].line=opline;/*記錄回溯點(diǎn)*/opline++;oprow=l;/*開始找下一行*/}else/*需要進(jìn)行回溯*/{if(opline==9)print();do{if(top==0)return0;/*如果棧取空了，說明查找結(jié)束*/oprow=back[top].row;/*如果棧中還有元素可取*/opline=back[top].line;/*取出棧頂元素*/

162top——;row[oprow]=0;left[oprow+opline-l]=0;/*同時(shí)將這個(gè)棋子拿起*/right[8-oprow+opline]=0;queen[opline]=0;}while(oprow==8);/*當(dāng)取到的oprow的右邊可以放子時(shí)，開始下一步操作*/oprow++;main（）{init（）;kaiserin（）;）54第6章樹6.1樹最適合用來表示具有（有序）性和（層次）性的數(shù)據(jù)。6.2在選擇存儲(chǔ)結(jié)構(gòu)時(shí)，既要考慮數(shù)據(jù)值本身的存儲(chǔ)，還需要考慮（數(shù)據(jù)間關(guān)系）的存儲(chǔ)。6.3對(duì)于一?棵具有n個(gè)結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為（n-1）。6.4已知一棵樹如圖6.11所示，試回答以下問題：圖6.II一棵樹（1）樹中哪個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)？哪些結(jié)點(diǎn)為葉子結(jié)點(diǎn)？【答】：A是根結(jié)點(diǎn)；E,G,H,I,C,J,K,L為葉結(jié)點(diǎn)。（2）結(jié)點(diǎn)B的雙親為哪個(gè)結(jié)點(diǎn)？其子女為哪些結(jié)點(diǎn)？【答】：B的雙親結(jié)點(diǎn)是A,其子女結(jié)點(diǎn)為E和F。

163(3)哪些結(jié)點(diǎn)為結(jié)點(diǎn)I的祖先？哪些結(jié)點(diǎn)為結(jié)點(diǎn)B的子孫？【答】：F,B,A是結(jié)點(diǎn)I的祖先結(jié)點(diǎn)：E,F,G,H,I是B的子孫結(jié)點(diǎn)。(4)哪些結(jié)點(diǎn)為結(jié)點(diǎn)D的兄弟？哪些結(jié)點(diǎn)為結(jié)點(diǎn)K的兄弟？【答】：B,C,L是結(jié)點(diǎn)D的兄弟結(jié)點(diǎn)，J是結(jié)點(diǎn)K的兄弟結(jié)點(diǎn)。(5)結(jié)點(diǎn)J的層次為多少？樹的高度為多少？【答】：結(jié)點(diǎn)J的層次為3,樹的高度為4。(6)結(jié)點(diǎn)A、C的度分別為多少？樹的度為多少？【答】：結(jié)點(diǎn)A的度為4,結(jié)點(diǎn)C的度是0,樹的度是4。(7)以結(jié)點(diǎn)B為根的子樹的高度為多少？【答】：以結(jié)點(diǎn)B為根的子樹的高度是3。(8)試給出該樹的括號(hào)表示及層號(hào)表示形式?！敬稹浚涸摌涞睦ㄌ?hào)表示為：A(B(E,F(G,H,I)),C,D(J,K),L),該樹的層號(hào)表示為：10A,20B,30E,30F,40G,40H,401,20C,20D,25J,25K,20L6.2試寫出圖6.11所示樹的前序遍歷、后序遍歷和層次遍歷的結(jié)果?！敬稹浚呵靶虮闅v：ABEFGHICDJKL后序遍歷：EGHIFBCJKDLA層次遍歷：ABCDLEFJKGHI6.3試給出圖6.11所示樹的雙親表示法和數(shù)組方式孩子表示法的表示。55【答】：雙親表示法：dataparent1B02C0

1643D04E15F16G57II58I59J310K311L0數(shù)組方式的孩子表示法：dataChild[0]Child[l]Child[2]Child[3]0A123111B45-1-12C-1-1-1-13D910-1-14E-1-1-1-15F678-16G-1-1-1-17H-1-1-1-181-1-1-1-19J_1_1-1_111L-1-1-1-11.7已知一棵度為m的樹中有nl個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，，,,,，nm個(gè)度為m的結(jié)點(diǎn)，問該樹中有多少個(gè)葉子結(jié)點(diǎn)？

165【答】：樹中結(jié)點(diǎn)總數(shù)n=nO+nl+n2+?+nm樹中結(jié)點(diǎn)的度數(shù)之和為n-1,且有：n-l=nl+2n2+3n3+,,+mnm所以葉子結(jié)點(diǎn)個(gè)數(shù)為：n0=n2+2n3+?+(m-l)nm1.7假設(shè)樹采用指針方式的孩子表示法表示，試編寫一個(gè)非遞歸函數(shù)，實(shí)現(xiàn)樹的前序遍歷算法。56【答】：本程序在運(yùn)行時(shí)請(qǐng)按樹的括號(hào)表示法輸入擬遍歷的樹，例如，對(duì)習(xí)題6.4圖6.11所示的樹為例，應(yīng)輸入A(B(E,F(G,H,I)),C,D(J,K),L)定義樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及建'7：樹的存儲(chǔ)結(jié)構(gòu)CreateTree函數(shù)(tree,h)內(nèi)容如下：ttincludettincludettinclude//樹的最大度定義為5ttdefineMAXN5ttdefineMAXLEN100typedefchardataType;typedefstructnode{dataTypekey;structnode*child[MAXN];}TreeNode;樹的括號(hào)法轉(zhuǎn)化到樹指針方式的孩子表示法**/TreeNode*CreateTree(TreeNode*root,charstring[MAXLEN]){intlength;inti,j,top;TreeNode*stack[MAXLEN],*temp=NULL,*n;

166intchildSeq[MAXLEN];//其第幾個(gè)孩子top=-1;length=strlen(string);for(i=0;i

16757elseif(top!=-1){n=(TreeNode*)malloc(sizeof(TreeNode));n->key=string[i];for(j=0;jchild[j]=NULL;}temp=n;stack[top]->child[chiIdSeq[top]++]=temp;}else(root=(TreeNode*)malloc(sizeof(TreeNode));root->key=string[i];for(j=0;jchild[j]=NULL;)temp=root;}returnroot;

168voidPreOrder(TreeNode*root){inti;if(root!=NULL)(printf("%5c”,root->key);for(i=0;ichild[i]);樹的前序非遞歸遍歷算法及其測(cè)試程序(6_8.c)如下所示：^include"tree,h"/*前序遍歷(非遞歸)*/58voidPreOrder1(TreeNode*root){TreeNode*stack[MAXLEN];inttop=-l,i;while(root||top!=~l)(if(root){printf("c”,root->key);for(i=MAXN-l;i>O;i-)if(root->child[i])stack[++top]=root->chiId[i];

169root=root->child[0];}elseif(top>-l){root=stack[top-];intmain(){charstring[MAXLEN];TreeNode*root=NULL;printf("請(qǐng)用樹的括號(hào)表示法輸入一棵樹:

170〃)；scanfstring);root=CreateTree(root,string);PreOrder1(root);return0;}6.1假設(shè)樹采用指針方式的孩子表示法表示，試編寫一個(gè)非遞歸函數(shù)，實(shí)現(xiàn)樹的后序遍歷算法?！敬稹浚?include"tree,h”intPostOrderByStack(TreeNode*root)TreeNode*temp;TreeNode*stack[MAXLEN];

171//childSeq表示當(dāng)前打印到了此樹第幾個(gè)孩子,inttop,childSeq[MAXLEN];inti;top=T;〃初始化空棧59temp=root;while(1)iwhile(temp!=NULL)(for(i=0;ichild[i]!=NULL){childSeq[++top]=i+1;stack[top]=temp;temp=temp->child[i];break;})//如果此節(jié)點(diǎn)是葉子節(jié)點(diǎn)，則輸出該結(jié)點(diǎn)if(i==MAXN){printftemp->key);temp=NULL;

172break;}}while(top!=-1)(for(i=childSeq[top];ichiId[i]!=NULL)itemp=stack[top]->child[i];childSeq[top]=i+1;break;})if(i==MAXN)(printf("%5c”,stack[top]->key);top一；}if(temp!=NULL)!break;60

173if(top==-1)return1;intmain(){charstring[MAXLEN];TreeNode*root=NULL;printf(“請(qǐng)用樹的括號(hào)表示法輸入-?棵樹:

174");scanfstring);root=CreateTree(root,string);PostOrderByStack(root);return0;}6.1假設(shè)樹采用指針方式的孩子表示法表示，試編寫一個(gè)函數(shù)，判斷兩棵給定的樹是否等價(jià)(兩棵樹等價(jià)當(dāng)且僅當(dāng)其根結(jié)點(diǎn)的值相等且其對(duì)應(yīng)的子樹均相互等價(jià))。ttinclude"tree,h”#defineTRUE1ttdefineFALSE0遞歸比較兩棵樹是否相等*/intPreCmp(TreeNode*treel,TreeNode*tree2)

175{inti;if(treel==NULL&&tree2=NULL)(returnTRUE;}elseif(treel==NULL&&tree2!=NULL||treel!=NULL&&tree2==NULL){returnFALSE;}else(if(treel->key!=tree2->key)(61returnFALSE;}for(i=0;ichiId[i],tree2->chiId[i])=FALSE)returnFALSE;

176returnTRUE;intmain()(charstring[MAXLEN];TreeNode*treel=NULL,*tree2=NULL;printf("請(qǐng)用樹的括號(hào)表示法輸入第一棵樹:

177〃);scanf(〃％s”,string);treel=CreateTree(treel,string);printf(〃請(qǐng)用樹的括號(hào)表示法輸入第二棵樹:

178〃);scanfstring);tree2=CreateTree(tree2,string);if(PreCmp(treel,tree2)==TRUE){printf("兩樹相等

179");}else(printf("兩樹不相等\rT);

18062第7章二叉樹6.1選擇題。（1）前序遍歷和中序遍歷結(jié)果相同的二叉樹為（F）；前序遍歷和后序遍歷結(jié)果相同的二叉樹為（B）。A.一般二叉樹B.只有根結(jié)點(diǎn)的二叉樹C.根結(jié)點(diǎn)無左孩子的二叉樹D.根結(jié)點(diǎn)無右孩子的二叉樹E.所有結(jié)點(diǎn)只有左子樹的二叉樹F.所有結(jié)點(diǎn)只有右子樹的二叉樹。（2）以下有關(guān)二叉樹的說法正確的是（B）。A.二叉樹的度為2B.一棵二叉樹的度可以小于2C.二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹中任一個(gè)結(jié)點(diǎn)的度均為2（3）一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)為（D）。A.250B.500C.254D.501（4）一棵完全二叉樹有999個(gè)結(jié)點(diǎn)，它的深度為（B）。A.9B.10C.11D.12（5）一棵具有5層的滿二叉樹所包含的結(jié)點(diǎn)個(gè)數(shù)為（B）。A.15B.31C.63D.327.2用一維數(shù)組存放完全二叉樹：ABCDEFGHI,則后序遍歷該二叉樹的結(jié)點(diǎn)序列為（HIDEBFGCA）.7.3有n個(gè)結(jié)點(diǎn)的二叉樹，已知葉結(jié)點(diǎn)個(gè)數(shù)為n0,則該樹中度為1的結(jié)點(diǎn)的個(gè)數(shù)為（n-2n0+l）；若此樹是深度為k的完全二叉樹，則n的最小值為（2k-l）（.7.4設(shè)F是由Tl、T2和T3三棵樹組成的森林，與F對(duì)應(yīng)的二叉樹為B。已知Tl、T2和T3的結(jié)點(diǎn)數(shù)分別是nl、n2和n3,則二叉樹B的左子樹中有（nl-1）個(gè)結(jié)點(diǎn)，二叉樹B的右子樹中有（n2+n3）結(jié)點(diǎn)。7.5高度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為（2k-l）,最小結(jié)點(diǎn)數(shù)為（k）。

1817.2對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，該二叉樹中所有結(jié)點(diǎn)的度數(shù)之和為（nT）。7.7已知一棵二叉樹如圖7.12所示，試求：（1）該二叉樹前序、中序和后序遍歷的結(jié)果；【答】：前序:abdgecfh；中序：dgbcafhc；后序：gdebhfca（2）該二叉樹是否是滿二叉樹？是否是完全二叉樹？【答】：該二叉樹不是滿二叉樹，也不是完全二叉樹。（3）將它轉(zhuǎn)換成對(duì)應(yīng)的樹或森林；【答】：圖7.12一棵二叉樹63（4）這棵二叉樹的深度為多少？【答】：該二叉樹的深度為4。（5）試對(duì)該二叉樹進(jìn)行前序線索化；【答】：abcdefgh（6）試對(duì)該二叉樹進(jìn)行中序線索化?！敬稹浚?.8試述樹和二叉樹的主要區(qū)別。

18264【答】：（1）樹的結(jié)點(diǎn)個(gè)數(shù)至少為1，而二叉樹的結(jié)點(diǎn)個(gè)數(shù)可以為0。（2）樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹結(jié)點(diǎn)的最大度數(shù)為2o（3）樹分為有序樹與無序樹，而二叉樹一定是有序樹，它的結(jié)點(diǎn)有左，右之分。7.8試分別畫出具有3個(gè)結(jié)點(diǎn)的樹和具有3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。【答】：三個(gè)結(jié)點(diǎn)的樹有兩種形態(tài)：三個(gè)結(jié)點(diǎn)的二叉樹具有五種形態(tài)：7.910已知一棵二叉樹的中序遍歷的結(jié)果為ABCEFGHD,后序遍歷的結(jié)果為ABFHGEDC,試畫出此二叉樹?！敬稹浚?.11已知一棵二叉樹的前序遍歷的結(jié)果為ABCDEF,中序遍歷的結(jié)果為CBAEDF,試畫出此二叉樹?！敬稹浚?57.12若一棵二叉樹的左、右子樹均有3個(gè)結(jié)點(diǎn)，其左子樹的前序序列與中序序列相同，右子樹的中序序列與后序序列相同，試畫出該二叉樹?！敬稹浚?.13分別采用遞歸和非遞歸方式編寫兩個(gè)函數(shù)，求一棵給定二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)?！敬稹浚簽榉奖銣y(cè)試二叉樹相關(guān)程序，定義二叉樹頭文件bintree,h如下：#include#defineN100externchar*a;/*存放擴(kuò)充二叉樹的前序序列*/typedefstructnode/*二叉樹結(jié)構(gòu)定義*/

183chardata;structnode*lchild,*rchild;}binnode;typedefbinnode*bintree;/*函數(shù)creat(根據(jù)擴(kuò)充二叉樹的前序序列(字符串a(chǎn))建立二叉樹t的存儲(chǔ)結(jié)構(gòu)*/voidcreat(bintree*t){charch=*a++;if(ch='')*t=NULL;else{*t=(bintree)malloc(sizeof(binnode));(*t)->data=ch;creat(&(*t)->lchild);creat(&(*t)->rchiId);}}voidpreorder(bintreet)/*前序遞歸遍歷二叉樹*/(66if(t){printf(*%c*,t->data);preorder(t->rchiId);

184/*順序棧定義*/typedefstruct{bintreedata[N];inttop;}seqstack;voidinit(seqstack*s)/*初始化空棧*/is->top=-l;}intempty(seqstack*s)/*判斷棧是否為空*/(if(s->top>-l)return0;elsereturn1;}intfull(seqstack*s)/*判斷棧是否為滿*/(if(s->top==N-l)return1;elsereturn0;voidpush(seqstack*s,bintreex)/*進(jìn)棧*/s->data[++s->top]=x;}

185bintreepop(seqstack*s)/*出棧*/(if(!empty(s))returns->data[s->top-];}基于上述結(jié)構(gòu)，遞歸方法與非遞歸方法求二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)的算法分別如leafl()67與leaf2()所示：ttinclude"bintree.h〃char*a="ABCDEFG/*擴(kuò)充二叉樹序樹t的前序序列*/intleafl(bintreet)/*遞歸方法求二叉樹葉子結(jié)點(diǎn)的個(gè)數(shù)*/(if(t二二NULL)return0;elseif(!t->lchild&&!t->rchild)return1;elsereturnleafl(t->lchild)+leaf1(t->rchild);intleaf2(bintreet)/*非遞歸方法求二叉樹葉子結(jié)點(diǎn)的個(gè)數(shù)*/{seqstacks;/*順序棧*/intcount=0;/*葉子結(jié)點(diǎn)計(jì)數(shù)變量*/init(&s);/*初始化空棧*/while(t!empty(&s))

186iif(t){if(!t->lchild&&!t->rchild)count++;push(&s,t);t=t->lchild;)else{t=pop(&s);t=t->rchild;))returncount;}intmain(){bintreet;creat(&t);/*建立二叉樹t的存儲(chǔ)結(jié)構(gòu)*/printfC

187該二叉樹一共有%d個(gè)葉子結(jié)點(diǎn)！

188",leafl(t));printfCz

189該二叉樹一共有%d個(gè)葉子結(jié)點(diǎn)！

190z/,leaf2(t));7.14試編寫一個(gè)函數(shù)，將一棵給定二叉樹中所有結(jié)點(diǎn)的左、右子女互換。68【答】：ftinclude"bintree,h”char*a=〃ABCDEFG/*擴(kuò)充二叉樹序樹t的前序序列*/

191voidchange(bintreet){bintreep;if(t)(p=t->lchild;t->1chi1d=t->rchild;t->rchild=p;change(t->lchiId);change(t->rchiId);}}intmain(){bintreet;creat(&t);/*建立二叉樹t的存儲(chǔ)結(jié)構(gòu)*/preorder(t);change(t);printf("

192");preorder(t);7.15試編寫一個(gè)函數(shù)，返回一棵給定二叉樹在中序遍歷下的最后一個(gè)結(jié)點(diǎn)?！敬稹浚?include"bintree,h”char*a="ABCDEFG/*擴(kuò)充二叉樹序樹t的前序序列*/bintreeinlast(bintreet)

193{bintreep=t;while(p&&p->rchild)p=p->rchiId;returnp;)intmain(){bintreet;creat(&t);/*建立二叉樹t的存儲(chǔ)結(jié)構(gòu)*/printf("二叉樹中序遍歷最后一個(gè)結(jié)點(diǎn)是%。11",inlast(t)->data);)7.16試編寫一個(gè)函數(shù)，返回一棵給定二叉樹在前序遍歷下的最后一個(gè)結(jié)點(diǎn)。69【答】：^include"bintree.h〃char*a="ABCDEFG〃；/*擴(kuò)充二叉樹序樹t的前序序列*//*求二叉樹前序遍歷的最后一個(gè)結(jié)點(diǎn)*/bintreeprelast(bintreet){bintreep;if(t)P=t;while(p&&p->lchild||p->rchild)if(p->rchild)p=p->rchild;else

194p=p->lchild;}returnp;}intmainO{bintreet;creat(&t);/*建立二叉樹t的存儲(chǔ)結(jié)構(gòu)*/printf("二叉樹前序遍歷的最后一個(gè)結(jié)點(diǎn)是%c

195”,prelast(t)->data);}7.17試編寫一個(gè)函數(shù)，返回一棵給定二叉樹在后序遍歷下的第一個(gè)結(jié)點(diǎn)?！敬稹浚篺tinclude"bintree,h”char*a="ABCDEFG/*擴(kuò)充二叉樹序樹t的前序序列*//*求二叉樹后序遍歷的第一個(gè)結(jié)點(diǎn)*/bintreesuccfirst(bintreet){bintreep;if(t){P=t;while(p&&p->lchild||p->rchild)if(p->lchild)p=p->lchild;elsep=p->rchiId;

196}returnp;)70intmain()(bintreet;creat(&t);/*建立二叉樹t的存儲(chǔ)結(jié)構(gòu)*/printf("二叉樹后序遍歷的第一個(gè)結(jié)點(diǎn)是枇\“"，succfirst(t)->data);}7.18假設(shè)二叉樹采用鏈?zhǔn)椒绞酱鎯?chǔ)，root為其根結(jié)點(diǎn)，p指向二叉樹中的任意一個(gè)結(jié)點(diǎn)，編寫一個(gè)求從根結(jié)點(diǎn)到p所指結(jié)點(diǎn)之間路徑長度的函數(shù)?！敬稹浚涸诤笮虮闅v非遞歸算法中，當(dāng)訪問的結(jié)點(diǎn)為p時(shí)，其祖先點(diǎn)正好全部在棧中，此時(shí)棧中結(jié)點(diǎn)的個(gè)數(shù)就是根結(jié)點(diǎn)到P所指結(jié)點(diǎn)之間路徑長度。#include#includetypedefchardatatype;typedefstructnode/*二叉樹結(jié)點(diǎn)定義*/{datatypedata;structnode*lchild,*rchild;}bintnode;typedefbintnode*bintree;typedefstructstackbintreedata[100];

197inttag[100];inttop;}seqstack;voidcreat(bintree*t);/*函數(shù)Depth,功能：求根結(jié)點(diǎn)到x的路徑長度*/intDepth(bintreet,datatypex)(seqstacks;inti=0,j;s.top=0;while(t|s.top!=0)(while(t){s.data[s.top]=t;s.tag[s.top]=0;71s.top++;while(s.top>0&&s.tag[s.top-1])s.top一；t=s.data[s.top];

198if(t->data==x)returns.top;//此時(shí)棧中的結(jié)點(diǎn)都是x的祖先結(jié)點(diǎn)}if(s.top>0)(t=s.data[s.top-1];s.tag[s.top-l]=l;t=t->rchild;}elset=NULL;))/*函數(shù)creat(根據(jù)擴(kuò)充二叉樹的前序序列建立二叉樹t的存儲(chǔ)結(jié)構(gòu)*/voidcreat(bintree*t)(charch;scanf(*%c*,&ch);if(ch=，')*t=NULL;else{*t=(bintnode*)malloc(sizeof(bintnode));(*t)->data=ch;creat(&(*t)->lchild);creat(&(*t)->rchild);}}

199intmain(){bintreeroot,p=NULL;datatypex;intk=0;printf(〃請(qǐng)輸入擴(kuò)充二叉樹的前序序列：\<);creat(&root);72printf("請(qǐng)輸入樹中的1個(gè)結(jié)點(diǎn)值:\rT);scanf&x);k=Depth(root,x);printf("根結(jié)點(diǎn)到%c的長度是%d

200”,x,k);}7.19假設(shè)二叉樹采用鏈?zhǔn)椒绞酱鎯?chǔ)，root為其根結(jié)點(diǎn)，p和q分別指向二叉樹中任意兩個(gè)結(jié)點(diǎn)，編寫一個(gè)函數(shù)，返回P和q最近的共同祖先。【答】：方法同上題，利用后序遍歷非遞歸算法分別求出p和q的公共祖先，然后再查找它們的最近公共祖先結(jié)點(diǎn)。#include#includetypedefchardatatype;typedefstructnode/*二叉樹結(jié)點(diǎn)定義*/{datatypedata;structnode*lchild,*rchild;}bintnode;typedefbintnode*bintree;

201typedefstructstack〃順序棧結(jié)構(gòu)定義{bintreedata[100];inttag[100];inttop;}seqstack;voidcreat(bintree*t);〃創(chuàng)建二叉樹結(jié)構(gòu)函數(shù)聲明/*函數(shù)SeekAncestor的功能是返回二叉樹t中結(jié)點(diǎn)x與結(jié)點(diǎn)y的最近公共祖先結(jié)點(diǎn)*/voidSeekAncestor(bintreet,datatypex,datatypey,bintree*antor){seqstacks;bintreedata[100]={0};inti=0,j;5.top="l;while(t||s.top>-l){while(t){6.data[++s.top]=t;7.tag[s.top]=0;t=t->lchild;73while(s.top>-l&&s.tag[s.top]){t=s.data[s.top];if(t->data==x)while(i<=s.top)〃記錄x結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)

202idata[i]=s.data[i];i++；}elseif(t->data==y)(while(s.top>-l)(j=i-l；while(j>=0&&t!二data[j])〃查找y與x的最近公共祖先結(jié)點(diǎn)j—；if(j>=0){*antor二data[j];〃返回公共祖先結(jié)點(diǎn)地址return;t=s.data[--s.top];-s.top;)if(s.top>-l)(t=s.data[s.top];s.tag[s.top]=l;

203t=t->rchild;)elset=NULL;)}/*函數(shù)creat(根據(jù)擴(kuò)充二叉樹的前序序列建立二叉樹t的存儲(chǔ)結(jié)構(gòu)*/voidcreat(bintree*t){charch;74scanf,&ch);if(ch='')*t=NULL;else{*t=(bintnode*)malloc(sizeof(bintnode));(*t)->data=ch;intmainOIbintreeroot,p=NULL;datatypex='B",y=，C,;printf（"請(qǐng)輸入擴(kuò)充二叉樹的前序序列：

204"）;creat（&root）;printf（"請(qǐng)輸入樹中的兩個(gè)結(jié)點(diǎn)值：

205"）;scanf（"機(jī)s%c”,&x,&y）;SeekAncestor（root,x,y,&p）;

206if（p）printf（*%c和%c的最近公共祖先是：％c

207”,x,y,p->data）;）75第8章圖8.1選擇題（1）如果某圖的鄰接矩陣是對(duì)角線元素均為零的匕三角矩陣，則此圖是（D）。A.有向完全圖B.連通圖C.強(qiáng)連通圖D.有向無環(huán)圖（2）若鄰接表中有奇數(shù)個(gè)表結(jié)點(diǎn)，則一定（D）。A.圖中有奇數(shù)個(gè)頂點(diǎn)B.圖中有偶數(shù)個(gè)頂點(diǎn)C.圖為無向圖D.圖為有向圖（3）下列關(guān)于無向連通圖特性的敘述中，正確的是（A）。I.所有頂點(diǎn)的度之和為偶數(shù)II.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1III.至少有一個(gè)頂點(diǎn)的度為1A.只有IB.只有nC.I和IID.I和HI(4)假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是(B)。A.0(n)B.0(e)C.0(n+e)D.0(n*e)(5)已知一個(gè)有向圖&30所示，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先偏歷，不可能得到的DFS序列為(A)。A.adbefcB.adcefbC.adcbfeD.adefcbbacefd圖8.30有向圖

208(6)無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是(D)。A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b(7)下列哪一個(gè)選項(xiàng)不是圖8.31所示有向圖的拓?fù)渑判蚪Y(jié)果(C)。A.AFBCDEB.FABCDEC.FACBDED.FADBCE圖8.31A0V網(wǎng)76(8)判斷一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用(D)oA.單源最短路Dijkstra算法B.所有頂點(diǎn)對(duì)最短路Floyd算法C.廣度優(yōu)先遍歷算法D.深度優(yōu)先遍歷算法(9)在一個(gè)帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在G的(A)。A.最小生成樹中B.深度優(yōu)先生成樹中C.廣度優(yōu)先生成樹中D.深度優(yōu)先生成森林中(10)下圖所示帶權(quán)無向圖的最小生成樹的權(quán)為(C)。A.14B.15C.17D.18圖8.32帶權(quán)無向圖8.2對(duì)于如圖&33所示的無向圖，試給出：(1)圖中每個(gè)頂點(diǎn)的度；(2)該圖的鄰接矩陣；(3)該圖的鄰接表與鄰接多重表；(4)該圖的連通分量。圖8.33無向圖圖8.34有向圖【答】：

209(1)D(V0)=2；D(VI)=2；D(V2)=3；D(V3)=3；D(V4)=2；D(V5)=2；D(V6)=1。(2)該圖的鄰接矩陣如圖8.33.1所示。77圖8.33.4兩個(gè)連通分量圖8.33.1鄰接矩陣圖8.33.2鄰接表(3)該圖的鄰接表如圖8.30.2所示：該圖的鄰接多重表如圖8.30.3所示。圖8.33.3鄰接多重表(4)該圖的兩個(gè)連通分量如圖8.33.4所示。8.2對(duì)于如圖&34所示的有向圖，試給出:(1)頂點(diǎn)D的入度與出度；(2)該圖的出邊表與入邊表；(3)該圖的強(qiáng)連通分量。【答】：(1)頂點(diǎn)D的入度是2；頂點(diǎn)D的出度為lo(2)該圖的出邊表如圖&34.1所示，該圖的入邊表如圖8.34.2所示。78圖8.34.1出邊表圖&34.2入邊表(3)該圖的兩個(gè)強(qiáng)連通分量如圖8.34.3所示。ABCDE圖8.34.3兩個(gè)強(qiáng)連通分量

2108.2試回答下列關(guān)于圖的一些問題。(1)有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有多少條邊？最少有多少條邊？(2)表示一個(gè)有500個(gè)頂點(diǎn)，500條邊的有向圖的鄰接矩陣有多少個(gè)非零元素？(3)G是一個(gè)非連通的無向圖，共有28條邊，則該圖至少有多少個(gè)頂點(diǎn)？【答】：(1)有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖昨多有n(n-l)條邊；最少有n-1條邊。(2)500個(gè)。(3)9個(gè)頂點(diǎn)。8.5圖8.35所示的是某個(gè)無向圖的鄰接表，試:(1)畫出此圖；(2)寫出從頂點(diǎn)A開始的DFS遍歷結(jié)果；(3)寫出從頂點(diǎn)A開始的BFS遍歷結(jié)果。【答】：(1)圖8.35鄰接表對(duì)應(yīng)的無向圖如圖8.35.1所示。圖8.35.1(2)從頂點(diǎn)A開始的DFS遍歷結(jié)果是：A,B,C,F,E,G,D(3)從頂點(diǎn)A開始的BFS遍歷結(jié)果是：A,B,C,D,F,E,G8.6證明，用Prim算法能正確地生成一棵最小生成樹?！咀C明】：圖8.35題8.5的鄰接表79Prim算法是按照逐邊加入的方法來構(gòu)造最小生成樹過程的。記構(gòu)造過程中生成的子圖為G',顯然G'始終是一棵樹。這是因?yàn)槌跏紩r(shí)V(G')={uO},E(G')=①，是一棵樹。隨后每一

211步都是向G，中添加一個(gè)頂點(diǎn)同時(shí)添加一條邊，始終保持G，中所有頂點(diǎn)連通。這樣，當(dāng)G，有n個(gè)頂點(diǎn)時(shí)是僅有nT條邊的連通圖，所以G，是一棵樹。Prim算法在執(zhí)行過程中，始終能保證G'=(V,E')是無向連通網(wǎng)絡(luò)6=(V,E)上某個(gè)最小代價(jià)生成樹的連通圖，如果該結(jié)論正確，則隨著V(G')頂點(diǎn)不斷增加，當(dāng)V(G')=V(G)時(shí)，G'=(V',E')就是G=(V,E)上的最小代價(jià)生成樹。下面證明Prim算法的每一步都能保證G'=(V',E')是無向連通網(wǎng)絡(luò)G=(V,E)上某個(gè)代價(jià)生成樹的子連通圖。初始時(shí)，G'僅有一個(gè)頂點(diǎn)V(G')={uO},E(G')=中，設(shè)該樹為T1,此時(shí)G'顯然是G的某個(gè)最小生成樹的子連通圖?，F(xiàn)假設(shè)第i步G，=(V，,E，)中含有i個(gè)頂點(diǎn)，不妨設(shè)該樹為Ti,在G(V,E)中存在一棵最小生成樹包含著Ti,在第i+1步，存在uGTi,v陣Ti,且(u,V)是最小兩棲邊，將頂點(diǎn){v},邊(u,V)添加到樹Ti中，所得樹Ti+1是包含V(Ti)+{v}頂點(diǎn)集的生成樹，且具有i+1個(gè)頂點(diǎn)。根據(jù)MST性質(zhì)，此時(shí)在G=(V,E)中必存在一棵最小生成樹包含著Ti+1。由此可知，當(dāng)i=n時(shí)，G'(Tn)即為無向圖G含有n個(gè)頂點(diǎn)的最小生成樹。當(dāng)然在進(jìn)行最小兩棲邊選擇時(shí)，如果同時(shí)存在幾個(gè)具有相同代價(jià)的最小兩棲邊，則可任選一條，因些Prim算法構(gòu)造的最小生成樹不是唯一的。但它們的最小(代價(jià))總和是相等的。8.5證明，用Kruskal算法能正確地生成一棵最小生成樹?！咀C明】：算法首先構(gòu)造具有n個(gè)不同頂點(diǎn)的n個(gè)連通分量，然后在E(G)中選擇邊(u,v),若u,v頂點(diǎn)屬于不同的兩個(gè)連通分量，則把該邊添加到樹T中，每添加一條邊就減少一個(gè)連通分量。當(dāng)添加了共n-1條邊時(shí)，就把n個(gè)連通分量變成一個(gè)連通分量，此時(shí)T就是具有n個(gè)頂點(diǎn)nT條邊的樹。由于n是有限數(shù)，E(G)中邊數(shù)也是有限的，所以算法具有有窮性。不妨設(shè)T的邊為(ul,vl),(u2,v2),”，(un-1,vn-1),按權(quán)值從小到大排列，若存在一棵樹丁的代價(jià)總和小于T的代價(jià)總和，則必在T'中存在一條邊(u，,v，)GTE',(u‘，v')?TE,且(u',v')的代價(jià)小于(unT,vn-1)的代價(jià)，這就說明(u',v')邊沒有選取的原因是因?yàn)閡',v'在同一個(gè)連通分量，添加(u',v')將產(chǎn)生回路，說明T’不可能是樹(添加一條邊沒有減少一個(gè)連通分量，這樣V的邊數(shù)將大于n-1)。這與T'是一棵樹的假設(shè)相矛盾。證畢。

2128.58對(duì)如圖8.36所示的連通圖，分別用Prim和Kruskal算法構(gòu)造其最小生成樹?！敬稹浚?/p>

213(1)采用Prim算法求解最小生成樹的過程如圖8.36.1所示。圖8.36無向連通網(wǎng)80(2)采用Kruskal算法求解最小生成樹時(shí)首先要對(duì)邊進(jìn)行由小到大進(jìn)行排序，本題對(duì)邊進(jìn)行排序的結(jié)果是：（D,F）1、（C,F）2、（D,B）4、（C,D）5、（E,G）5、（A,D）6>（D,G）6、的過程如圖8.33.2所示。442ABCDEFG341（a）選?。ˋ,F）（b）選?。―,F）4（A,F）3、（A,C）4、（F,G）4、（D,E）4、(A,B)7o根據(jù)Kruskal算法，構(gòu)造最小生成樹（c）選取（C,F）4

214FG341(d)選取(F,G)(e)選取(D,E)(f)選取(D,B)圖8.36.1Prim算法求解最小生成樹過程(a)選取(D,F)(b)選取(C,F)(c)選取(A,F)42ABCDEFG341442ABCDEFG3

2154(d)選取(F,G)(e)選取(D,E)(f)選取(D,B)圖8.36.2Kruskal算法求解最小生成樹過程81BAECDGF4828154033209131843233312AB

216GC

217EH1圖8.37有向網(wǎng)圖8.38題8.10的AOV網(wǎng)8.9對(duì)于如圖8.37所示的有向網(wǎng)，用Dijkstra方法求從頂點(diǎn)A到圖中其他頂點(diǎn)的最短路徑，并寫出執(zhí)行算法過程中距離向量d與路徑向量p的狀態(tài)變化情況?！敬稹浚簩?duì)于如圖8.37所示的有向網(wǎng)，Dijkstra方法求從頂點(diǎn)A到圖中其它頂點(diǎn)的最短徑時(shí)，距離向量與路徑向量的狀態(tài)變化如下表示：距離向量d路徑向量p循環(huán)集合Sv01234560123456初始化{A}-04881528840-10-100-101{AD}30480°15284838-10-100332{ADE}40486115284838-10400333{ADG}60486115284838-10400334{ADGB}10486015284838-10100335{ADGBF)50485715284838-10500336{ADGBFC)20485715284838-1050033從表中可以看出源點(diǎn)A到其它各頂點(diǎn)的最短距離及路徑為：A-*B：48路徑：A-BA-*C：57路徑：A-D-F-CA-D：15路徑：A-DA-E：28路徑：A-E

218A-*F：48路徑：A-DfFA-G：38路徑：A-DfG8.10試寫出如圖8.38所示的AOV網(wǎng)的4個(gè)不同的拓?fù)湫蛄??！敬稹浚簣D8.38所示的AOV網(wǎng)的4個(gè)不同的拓?fù)湫蛄袨椋?1)ABDCEFGIH(2)ABDECFGIH(3)DABCEFGIH(4)DAECBFGIH8.11計(jì)算如圖8.39所示的AOE網(wǎng)中各頂點(diǎn)所表示的事件的發(fā)生時(shí)間ve(j),vl(j),各邊所表示的活動(dòng)的開始時(shí)間e(i),l(i),并找出其關(guān)鍵路徑。82【答】：為描述方便，將AOE網(wǎng)中的所有邊事件記為a0-a7,如圖&39所示。按照關(guān)鍵路徑算法，求得各頂事件的最早與最晚開始時(shí)間如下表所示。頂點(diǎn)vevl活動(dòng)e11-e關(guān)鍵活動(dòng)v0vlv2v3v4v56

219222565132225aOala2a3a4a5a6a7644131322

220131522可見，該AOE網(wǎng)的關(guān)鍵路徑是a0,a2,a5,a7。（注：圖中箭頭指示求解的順序）8.12無向圖采用鄰接表作為存儲(chǔ)結(jié)構(gòu)，試寫出以下算法(1)求一個(gè)頂點(diǎn)的度;(2)往圖中插入一個(gè)頂點(diǎn);往圖中插入一條邊;(4)刪去圖中某頂點(diǎn);(5)刪去圖中某條邊?！敬稹浚罕绢}的參考解答基于以下的存儲(chǔ)結(jié)構(gòu):^definem20/*預(yù)定義圖的最大頂點(diǎn)數(shù)*/

221typedefchardatatype;/*頂點(diǎn)信息數(shù)據(jù)類型*/typedefstructnode{/*邊表結(jié)點(diǎn)*/intadjvex;/*鄰接點(diǎn)*/structnode*next;}edgenode;typedefstructvnode{/*頭結(jié)點(diǎn)類型*/datatypevertex;/*頂點(diǎn)信息*/edgenode*firstedge;/*鄰接鏈表頭指針*/}vertexnode;vOvlv2v3v56v4478209103aOal

222a3a4a5a6a7圖8.39題8.10的AOE網(wǎng)83typedefstruct{/*鄰接表類型*/vertexnodeadjlist[m];/*存放頭結(jié)點(diǎn)的順序表*/intn,e;/*圖的頂點(diǎn)數(shù)與邊數(shù)*/}adjgraph;(1)求一個(gè)頂點(diǎn)的度；/*求無向圖g的第i個(gè)頂點(diǎn)的度*/intd(adjgraphg,inti){intk=0;edgenode*p;p=g.adjlist[i].firstedge;while(p){k++;p=p->next;returnk;

223(2)往圖中插入一個(gè)頂點(diǎn)；voidinsertvex(adjgraph*g,datatypex){inti=0,flag=0;/*查找待插入的結(jié)點(diǎn)是否存在*/while(!flag&&in){if(g->adj1ist[i].vertex==x)flag=l;i++;}if(flag){printf("結(jié)點(diǎn)已存在!");getch();exit(0);}if(g->n>m){printf("鄰接表已滿！")；exit(0);}g->adjlist[g->n].vertex=x;g->adjlist[g->n].firstedge=NULL;g->n++;}(3)往圖中插入一條邊；/*在無向圖g中插入無向邊(i,j)*/voidinsertedge(adjgraph*g,inti,intj){edgenode*p,*s;84intflag=0;if(in&&jn){p=g->adjlist[i].firstedge;while(!flag&&p){if(p->adjvex==j)flag=l;

224p=p->next;}if(flag){printf("邊已存在!”)；getchO;exit(0);}/*插入無向邊(i,j)*/s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=j;/*鄰接點(diǎn)序號(hào)為j*/s->next=g->adjlist[i].firstedge;g->adjlist[i].firstedge=s;/*將新結(jié)點(diǎn)*s插入頂點(diǎn)vi的邊表頭部*/s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=i;/*鄰接點(diǎn)序號(hào)為i*/s->next=g->adjlist[j].firstedge;g->adjlist[j].firstedge=s;/*將新結(jié)點(diǎn)*$插入頂點(diǎn)vj的邊表頭部*/}elseprintf("插入邊不合法!”)；}(4)刪去圖中某頂點(diǎn)；/*下面的函數(shù)刪除無向圖中頂點(diǎn)編號(hào)為i的頂點(diǎn)。由于該頂點(diǎn)被刪除，與這個(gè)頂點(diǎn)相關(guān)聯(lián)的邊也應(yīng)該被刪除，具體做法是，通過鄰接表查找與頂點(diǎn)i鄰接的其它所有頂點(diǎn)，在這些頂點(diǎn)的鄰接邊鏈表中刪除編號(hào)為i的邊結(jié)點(diǎn)，再將鄰接表中最后一個(gè)頂點(diǎn)移動(dòng)到第i個(gè)頂點(diǎn)在鄰接表中的位置，相應(yīng)地修改最后一個(gè)頂點(diǎn)在鄰接表中的頂點(diǎn)編號(hào)為i*/

225voiddeletevex(adjgraph*g,inti){intk;edgenode*pre,*p,*s;if(i>=0&&in)/*頂點(diǎn)下標(biāo)合法*/{/*刪除與原頂點(diǎn)i有關(guān)的所有邊*/s=g->adjlist[i].firstedge;while(s){k=s->adjvex;pre=NULL;85p=g->adjlist[k].firstedge;while(p){if(p->adjvex==i)/*結(jié)點(diǎn)編號(hào)是i,應(yīng)該刪除*/if(!pre)/*邊鏈表的第一個(gè)邊結(jié)點(diǎn)*/{g->adjlist[k].firstedge=p->next;free(p);p=g->adjlist[k].firstedge;}else/*不是第一個(gè)邊結(jié)點(diǎn)*/{pre->next=p->next;free(p);p=pre->next;else/*結(jié)點(diǎn)編號(hào)不是i*/{pre=p;

226p=p->next;))g->adjlist[iLfirstedge=s->next;free(s);/*釋放頂點(diǎn)i邊鏈表上的結(jié)點(diǎn)*/s=g->adjlist[i].firstedge;}g->adj1ist[i]=g->adjlist[g->n-1];/*將最后一個(gè)結(jié)點(diǎn)換到第i個(gè)結(jié)點(diǎn)的位置*/p=g->adjlist[i].firstedge;/*由于第nT個(gè)結(jié)點(diǎn)的編號(hào)被改為i,所以調(diào)整所有與這個(gè)結(jié)點(diǎn)關(guān)聯(lián)的邊信息*/while(P){k=p->adjvex;s=g->adjlist[k].firstedge;while(s){if(s->adjvex==g->n-l)/*將最后一個(gè)結(jié)點(diǎn)的編號(hào)改為i*/s->adjvex=i;s=s->next;}p=p->next;g->n—;/*結(jié)點(diǎn)個(gè)數(shù)減1*/elseprintf(〃不存在指定的結(jié)點(diǎn)!

227〃)；86

228}(5)刪去圖中某條邊。voiddeleteedge(adjgraph*g,inti,intj){edgenode*pre,*p;intk;if(i>=0&&in&&j>=0&&jn)/*判斷邊是否有效*/{pre=NULL;/*找無向邊(i,j)并刪除*/p=g->adjlist[i].firstedge;while(p&&p->adjvex!=j){pre=p;p=p->next;}if(p)/*找到了被刪除邊結(jié)點(diǎn)*/{if(!pre)/*是第一個(gè)邊結(jié)elsepre->next=p->next;free(p);pre=NULL;/*找無向邊(j,i)并刪除*/p=g->adjlist[j].firstedge;while(p&&p->adjvex!=i){pre=p;p=p->next;

229}if(!pre)g->adjlist[j].firstedge=p->next;elsepre->next=p->next;free(p);g->e—;/*邊的個(gè)數(shù)減1*/)else{printf("找不到指定的邊！”)；getchO;exit(0);))else{printf("邊不合法!

230");exit(0);87)}8.13設(shè)有向圖采用鄰接表的存儲(chǔ)結(jié)構(gòu)(出邊表)，試寫出求圖中一個(gè)頂點(diǎn)的入度的算法?！敬稹浚?*求有向圖g中頂點(diǎn)i的入度，g的存儲(chǔ)結(jié)構(gòu)為出邊表，結(jié)構(gòu)定義同題8.11*/

231intid(adjgraph*g,inti){intj,count=0;edgenode*p;for(j=0;jn;j++){p=g->adjlist[j].firstedge;while(p){if(p->adjvex==i)count++;p=p->next;returncount;}8.14設(shè)計(jì)一個(gè)算法，不利用拓?fù)渑判蚺袛嘤邢驁D中是否存在環(huán)?！敬稹浚簩?duì)于有向圖進(jìn)行深度優(yōu)先遍歷，如果從有向圖上某個(gè)頂點(diǎn)v出發(fā)的遍歷，dfs(v)結(jié)束之前出現(xiàn)一條從頂點(diǎn)u到頂點(diǎn)v的回邊，由于u在生成樹上是v的子孫，則有向圖中必定存在包含頂點(diǎn)v到頂點(diǎn)u的環(huán)。因此判斷有一個(gè)有向圖中是否有環(huán)可以借助圖的深度優(yōu)先遍歷算法。intvisited[m];voiddfs(adjgraphg,inti){edgenode*p;visited[i]=l;p=g.adjlist[i].firstedge;while(p)

232(if(!visited[p->adjvex])dfs(g,p->adjvex);else/*深度優(yōu)先遍歷到已訪問的結(jié)點(diǎn)，出現(xiàn)環(huán)*/{printfCfoundacircle!*);getchO;exit(0);}p=p->next;}}voidfindcircle(adjgraphg){inti;88for(i=0;i

233過的結(jié)點(diǎn)，這些結(jié)點(diǎn)的鄰接點(diǎn)可能還沒有全部訪問完成，遍歷過程中可能需要回溯。參考程序如下：#defineMAXVEX100/*定義棧的最大容量*/intvisited[m];voiddfs(adjgraphg,inti){/*以vi為出發(fā)點(diǎn)對(duì)鄰接表表示的圖g進(jìn)行深度優(yōu)先遍歷*/edgenode*p;edgenode*stack[MAXVEX];/*棧用來保存回溯點(diǎn)*/inttop=-l;printf(*visitvertex:%cg.adjlist[i].vertex);/*訪|司頂點(diǎn)i*/visited[i]=l;p=g.adjlist[i].firstedge;while(top>-l||p)/*當(dāng)棧不空或p不空時(shí)*/{if(p)/*優(yōu)先處理p不空的情況*/if(visited[p->adjvex])p=p->next;else{printf('%c”,g.adjlist[p->adjvex].vertex);visited[p->adjvex]=1;stack[++top]=p;p=g.adjlist[p->adjvex].firstedge;else/*從棧中進(jìn)行回溯*/if(top>-l){p=stack[top-];

234p=p->next;voiddfstraverse(adjgraphg){inti;89for(i=0;i

235}edge;/*定義邊結(jié)構(gòu)類型，存放每個(gè)活動(dòng)的最早開始時(shí)間與最晚允許開始時(shí)間*/若活動(dòng)ak的尾事件是vi,頭事件是vj,則e(k)就是vi的最早發(fā)生時(shí)間，l(k)是vj所允許的最晚開始時(shí)間減去活動(dòng)ak的持續(xù)的時(shí)間。求解AOE網(wǎng)絡(luò)事件的最早發(fā)生時(shí)間與最晚允許發(fā)生時(shí)間的算法參見教材算法8.10o/*求AOE網(wǎng)中各活動(dòng)的最早開始時(shí)間*/voide(aoegraph*gout,intve[],edgeactive口){inti,k=0;edgenode*p;for(i=0;in;i++)/*對(duì)出邊表中的每?條邊進(jìn)行求解*/{p=gout->adjlist[i].firstedge;while(p){active[k].vi=i;/*邊的起點(diǎn)*/active[k].vj=p->adjvex;/*邊的終點(diǎn)*/active[k].e=ve[i];k++;p=p->next;/*求AOE網(wǎng)中各活動(dòng)的最晚允許開始時(shí)間*/void1(aoegraph*gout,intvl[],edgeactive[])(inti,k=0;edgenode*p;for(i=0;in;i++){p-gout->adjlist[i].firstedge;

23690while(p){active[kj.l=vl[p->adjvex]-p->len;p=p->next;k++;91第9章檢索8.1選擇題（1）在關(guān)鍵字序列（12,23,34,45,56,67,78,89,91）中二分查找關(guān)鍵字為45、89和12的結(jié)點(diǎn)時(shí)，所需進(jìn)行的比較次數(shù)分別為（B）。A.4,4,3B.4,3,3C.3,4,4D.3,3,4（2）適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（D）。A.鏈?zhǔn)椒绞酱鎯?chǔ)，元素?zé)o序B.鏈?zhǔn)椒绞酱鎯?chǔ)，元素有序C.順序方式存儲(chǔ)，元素?zé)o序D.順序方式存儲(chǔ)，元素有序（3）設(shè)順序存儲(chǔ)的線性表共有123個(gè)元素，按分塊查找的要求等分成3塊。若對(duì)索引表采用順序查找來確定塊，并在確定的塊中進(jìn)行順序查找，則在查找概率相等的情況下，分塊查找成功時(shí)的平均查找長度為（B）。A.21B.23C.41D.62（4）已知含10個(gè)結(jié)點(diǎn)的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成功的平均查找長度等于（B）。A.1.0B.2.9C.3.4D.5.5（5）在圖9.27所示的各棵二叉樹中，二叉排序樹是（C）.圖9.27題（5）圖

237（6）由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹（B）。A.其形態(tài)不一定相同，但平均查找長度相同B.其形態(tài)不一定相同，平均查找長度也不一定相同C.其形態(tài)均相同，但平均查找長度不一定相同D.其形態(tài)均相同，平均查找長度也都相同（7）有數(shù)據(jù){53,30,37,12,45,24,96},從空二叉樹開始逐步插入數(shù)據(jù)形成二叉排序樹，若希望高度最小，則應(yīng)該選擇下列（A）的序列輸入。A.37,24,12,30,53,45,96B.45,24,53,12,37,96,30C.12,24,30,37,45,53,96D.30,24,12,37,45,96,53（8）若在9階B-樹中插入關(guān)鍵字引起結(jié)點(diǎn)分裂，則該結(jié)點(diǎn)在插入前含有的關(guān)鍵字個(gè)數(shù)為（C）。92A.4B.5C.8D.9（9）對(duì)于哈希函數(shù)H（key）=key%13,被稱為同義詞的關(guān)鍵字是（D）。A.35和41B.23和39C.15和44D.25和51（10）下列敘述中，不符合m階B樹定義要求的是（D）。A.根結(jié)點(diǎn)最多有m棵子樹B.所有葉結(jié)點(diǎn)都在同一層上C.各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D.葉結(jié)點(diǎn)之間通過指針鏈接9.2在分塊檢索中，對(duì)256個(gè)元素的線性表分成多少塊最好？每塊的最佳長度是多少？若每塊的長度為8,其平均檢索的長度是多少？【答】：對(duì)256個(gè)元素的線性表分成16塊，每塊的最佳長度是17；若每塊的長度為8,當(dāng)采用順序檢索方法確定所在的塊時(shí)平均檢索長度是21,當(dāng)采用二分檢索方法確定所在的塊時(shí)平

238均檢索長度是9。9.2設(shè)有關(guān)鍵碼A、B、C和D,按照不同的輸入順序，共可能組成多少不同的二叉排序樹。請(qǐng)畫出其中高度較小的6種?！敬稹浚汗部赡芙M成14種不同形態(tài)的二叉排序樹。其中高度較小的6種如圖9.28(a)所示。其它8種分別是高度為4的二叉排序樹如圖9.28(b)所示。(a)4個(gè)結(jié)點(diǎn)組成的高度較小的6棵二叉排序樹(b)4個(gè)結(jié)點(diǎn)組成的高度為4的二叉排序樹圖9.284個(gè)結(jié)點(diǎn)輸入序列構(gòu)成的不同二叉排序樹9.3已知序列17,31,13,11,20,35,25,8,4,11,24,40,27?請(qǐng)畫出由該輸入序列構(gòu)成的二叉排序樹，并分別給出下列操作后的二叉排序樹。(1)插入數(shù)據(jù)9：(2)刪除結(jié)點(diǎn)17；(3)再刪除結(jié)點(diǎn)13【答】：該序列的二叉排序樹如圖9.29(a)所示，插入數(shù)據(jù)9后的二叉排序樹如圖9.29(b)所示，刪除結(jié)點(diǎn)17后的二叉排序樹如圖9.29(c)所示，再刪除結(jié)點(diǎn)13后的二叉排序樹如圖9.29(d)所示。93(a)二叉排序樹(b)插入9之后的二叉排序樹(c)刪除17之后的二叉排序樹(d)刪除13之后的二叉排序樹圖9.29二叉樹結(jié)點(diǎn)插入與刪除操作示例9.4試寫一算法判別給定的二叉樹是否為二叉排序樹，設(shè)此二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，且樹中結(jié)點(diǎn)的關(guān)鍵字均不相同?！敬稹浚号卸ǘ鏄涫欠駷槎媾判驑淇梢越⒃诙鏄渲行虮闅v的基礎(chǔ)匕在遍歷中附設(shè)一指針pre指向樹中當(dāng)前訪問結(jié)點(diǎn)的中序直接前驅(qū)，每訪問一個(gè)結(jié)點(diǎn)就比較前驅(qū)結(jié)點(diǎn)pre和此結(jié)點(diǎn)是否有序；若遍歷結(jié)束后各結(jié)點(diǎn)和其中序直接前驅(qū)均滿足有序，則此二叉樹即為二叉排序樹，否則不是二叉排序樹。二叉樹存儲(chǔ)結(jié)構(gòu)定義為：typedefintdatatype;

239typedefstructnode/*二叉樹結(jié)點(diǎn)定義*/{datatypedata;structnode*lchild,*rchild;}bintnode;typedefbintnode*bintree;函數(shù)bisorttree()用于判斷二叉樹t是否為二叉排序樹，初始時(shí)pre=NULL；flag二1；結(jié)束時(shí)若flag=l,則此二叉樹為二叉排序樹，否則此二叉樹不是二叉排序樹。voidbisorttree(bintreet,bintree*pre,int*flag){if(t&&*flag==l){bisorttree(t->lchild,pre,flag);/*判斷左子樹*/if(pre==NULL)/*訪問中序序列的第一個(gè)結(jié)點(diǎn)時(shí)不需要比較*/94(*flag=l;*pre=t;}else/*比較t與中序直接前驅(qū)pre的大小(假定無相同關(guān)鍵字)*/(if((*pre)->datadata){?flag=l;*pre=t;else/*pre與t無序*/*flag=O;)

240bisorttree(t->rchiId,pre,flag);/*判斷右子樹*/))9.2設(shè)T是一棵給定的查找樹，試編寫一個(gè)在樹T中刪除根結(jié)點(diǎn)值為a的子樹的程序。要求在刪除的過程中釋放該子樹中所有結(jié)點(diǎn)所占用的存儲(chǔ)空間。這里假設(shè)樹T中的結(jié)點(diǎn)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)?！敬稹浚簞h除二叉樹可以采用后序遍歷方法，先刪除左子樹，再刪除右子樹，最后刪除根結(jié)點(diǎn)。本題先在指定的樹中查找值為a的結(jié)點(diǎn)，找到后刪除該棵子樹。相關(guān)函數(shù)實(shí)現(xiàn)如下(二叉排序樹的結(jié)構(gòu)定義同題9.5)/*刪除以t為根的二叉樹*/voiddeletetree(bintree*t){if(*t){deletetree(&(*t)->lchild);/*遞歸刪除左子樹*/deletetree(&(*t)->rchild);/*遞歸刪除右子樹*/free(*t);/*刪除根結(jié)點(diǎn)*//*刪除二叉樹中以根結(jié)點(diǎn)值為a的子樹*/voiddeletea(bintree*t,datatypea){bintreepre=NULL,p=*t;while(p&&p->data!=a)/*查找值為a的結(jié)點(diǎn)*/{pre=p;p=(adata)?p->lchild:p->rchild;)

241if(!pre)*t=NULL;/*樹根*/else/*非樹根*/if(pre->lchild==p)pre->lchild=NULL;elsepre->rchi1d=NULL;95deletetree(&p);/*刪除以p為根的子樹*/)9.2含有12個(gè)節(jié)點(diǎn)的平衡二叉樹的最大深度是多少(設(shè)根結(jié)點(diǎn)深度為0),并畫出一棵這樣的樹?！敬稹浚汉?2個(gè)節(jié)點(diǎn)的平衡二叉樹的最大深度是4(設(shè)根結(jié)點(diǎn)深度為0),如果根結(jié)點(diǎn)的深度為1則本題的答案為5,該樹如圖9.30所示。圖9.30具有12個(gè)結(jié)點(diǎn)的深度為4的平衡二叉樹9.3試用Adelson插入方法依次把結(jié)點(diǎn)值為60,40,30,150,130,50,90,80,96,25的記錄插入到初始為空的平衡二叉排序樹中，使得在每次插入后保持該樹仍然是平衡查找樹。請(qǐng)依次畫出每次插入后所形成的平衡查找樹?！敬稹浚河山Y(jié)點(diǎn)序列構(gòu)成的平衡二叉排序樹如圖9.31所示。6060

242401604012304060304060-130-11500(a)空樹(b)60-130-21501130040130插入60(c)插入4040

243-1301506040130-230115060150d)插入30e)LL型調(diào)整f)插入150(((6013040一1150500030(g)插入130(h)RL型調(diào)整(i)插入50(j)RL型調(diào)整96

244(k)插入90(1)插入80(m)插入96(n)插入25圖9.31AVL樹的插入過程9.2結(jié)點(diǎn)關(guān)鍵字kl,k2,k3,k4,k5為一個(gè)有序序列，它們的相對(duì)使用頻率分別為pl=6,p2=8,p3=12,p4=2,p5=16,外部結(jié)點(diǎn)的相對(duì)使用頻率分別為q0=4,ql=9,q2=8,q3=12,q4=3,q5=2.試構(gòu)造出有序序列kl,k2,k3,k4,k5所組成的最優(yōu)查找Mo【答】：(略)9.10證明Huffman算法能正確地生成一棵具有最小帶權(quán)外部路枝長度的二叉樹?！敬稹浚汗蚵岢隽艘环N構(gòu)造最優(yōu)前綴編碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼算法。哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。算法以C個(gè)葉結(jié)點(diǎn)開始，執(zhí)行C-1次的''合并”運(yùn)算后產(chǎn)生最終所要求的樹T。要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問題具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。(1)貪心選擇性質(zhì)設(shè)C是編碼字符集，C中字符c的頻率為f(c)。又設(shè)x和y是C中具有最小頻率的兩個(gè)字符，則存在C的一個(gè)最優(yōu)前綴編碼使x和y具有相同碼長且僅最后一們編碼不同。證明：設(shè)二叉樹T表示C的任意一個(gè)最優(yōu)前綴碼。我們要證明可以對(duì)T作適當(dāng)修改后得到一棵新的二叉樹T'',使得在新樹中，x和y是最深中子且為兄弟。同時(shí)新樹T''表示的前綴碼也是CS的一個(gè)最優(yōu)前綴碼。如果我們能做到這一點(diǎn)，則x和y在T'表示的最優(yōu)前綴碼中就具有相同的碼長且僅最后一位編碼不同。設(shè)b和c是二叉樹T的最深葉子且為兄弟。不失一般性，可設(shè)f(b)

245cecs2Tcdcf)()(-Sf(c)d(c)'cGCST=()()()()()()()()''fxdxfbdbfxdxfbdbTTTT+——=f(x)d(x)f(b)d(b)f(x)d(b)f(b)d(x)TTTT+——=(f(b)-f(x))(d(b)-d(x))20TT最后一個(gè)不等式是因?yàn)閒(b)-f(x)和dT(b)-dT(x)均為非負(fù)。類似地，可以證明在T'中交換y與c的位置也不增加平均碼長，即B(T')-B(T'')也是非負(fù)的。由此可知B(T'')

246由貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)立即可推出：哈夫曼算法是正確的，Huffman算法能正確地生成一棵具有最小帶權(quán)外部路枝長度的二叉樹。HuffmanTree產(chǎn)生C的確一棵最優(yōu)前綴編碼樹。9.11假設(shè)通訊電文中只用到A,B,C,D,E,F六個(gè)字母，它們?cè)陔娢闹谐霈F(xiàn)的相對(duì)頻率分別為:8,3,16,10,5,20,試為它們?cè)O(shè)計(jì)Huffman編碼?！敬稹浚河葾,B,C,D,E,F建立的Huffman樹如下：各字符對(duì)應(yīng)的Huffman編碼為：A：001B：0000C：1098D：01E：0001F：11358101620BEADCF8629.12含有9個(gè)葉子結(jié)點(diǎn)的3階B-樹中至少有多少個(gè)非葉子結(jié)點(diǎn)？含有10個(gè)葉子結(jié)點(diǎn)的3階B-樹中至少有多少個(gè)非葉子結(jié)點(diǎn)？

247【答】：（略）9.13編寫在B-樹中插入結(jié)點(diǎn)與刪除結(jié)點(diǎn)的算法程序?！敬稹浚海裕?.14用依次輸入的關(guān)鍵字23、30、51、29、27、15、1k17和16建一棵3階B-樹，畫出建該樹的變化過程示意圖（每插入一個(gè)結(jié)點(diǎn)至少有一張圖）。【答】：（略）9.15設(shè)散列表長度為11,散列函數(shù)H（x）=x%11,給定的關(guān)鍵字序列為：1,13,12,34,38,33,27,22。試畫出分別用拉鏈法和線性探測(cè)法解決沖突時(shí)所構(gòu)造的散列表，并求出在等概率的情況下，這兩種方法查找成功和失敗時(shí)的平均查找長度?！敬稹浚海?）拉鏈法構(gòu)造的散列表如下：12345678

2481022333412113273899查找成功時(shí)的平均查找長度為：13/8查找失敗時(shí)的平均查找長度為：8/11(2)線性探測(cè)法構(gòu)造的散列表如下：查找成功時(shí)的平均查找長度為：(1+1+3+4+1+1+2+8)/8=21/8查找失敗時(shí)的平均查找長度為：(1+2+3+...+11)/11=6次9.16設(shè)散列表為H0..12],即表的大小m=13。現(xiàn)采用再哈希法(雙散列法)解決沖突。散列函數(shù)和再散列函數(shù)分別為：

249HO(k)=k%13、Hi=(Hi-l+REV(k+1)%11+1)%13；i=l,2,”，m-1其中，函數(shù)REV(x)表示顛倒10進(jìn)制數(shù)的各位，如REV(37)=73,REV(1)=1等。若插入的關(guān)鍵碼序列為｛2,8,31,20,19,18,53,27),(1)試畫出插入這8個(gè)關(guān)鍵碼后的散列表。(2)計(jì)算檢索成功的平均查找長度ASL?！敬稹浚孩?10(2)=2,2存入2號(hào)。H0(8)=8,8存入8號(hào)。H0(31)=5,31存入5號(hào)。H0(20)=7,20存入7號(hào)。H0(19)=6,19存入6號(hào)。H0(18)=5,出現(xiàn)碰撞，H1(18)=(5+91%11+1)M3=9,18存入9號(hào)。H0(53)=1,53存入1號(hào)。H0(27)=1,出現(xiàn)碰撞，H1(27)=(1+82%11+1)機(jī)3=7,發(fā)生碰撞，H2(27)=(7+82%11+1)%13=0,27存入0號(hào)。插入8個(gè)關(guān)鍵碼序列以后的散列表如下所示：(2)檢索成功的平均查找長度是1.375。位置0123456789101112關(guān)鍵碼2753231192085100第10章內(nèi)排序9.1選擇題。(1)下列序列中，(A)是執(zhí)行第一趟快速排序后得到的序列。A.[da,ax,eb,de,bb]ff[ha,gc]B.[cd,eb,ax,da]ff[ha,gc,bb]C.[gc,ax,eb,cd,bb]ff[da,ha]D.[ax,bb,cd,da]ffLeb,gc,ha]

250（2）下列說法錯(cuò)誤的是（D）A.冒泡排序在數(shù)據(jù)有序的情況下具有最少的比較次數(shù)。B.直接插入排序在數(shù)據(jù)有序的情況下具有最少的比較次數(shù)。C.二路歸并排序需要借助。（n）的存儲(chǔ)空間。D.基數(shù)排序適合于實(shí)型數(shù)據(jù)的排序。（3）下面的序列中初始序列構(gòu)成最小堆（小根堆）的是（D）.A.10、60、20、50、30、26、35、40B.70、40、36、30、20、16、28、10C.20、60、50、40、30、10、8,72D.10、30、20、50、40、26、35、60（4）在下列算法中，（C）算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。A.堆排序B.插入排序C.冒泡排序D.快速排序（5）若需在0（nlogn）的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序算法是穩(wěn)定的，則可選擇的排序方法是（A）。A.歸并排序B.堆排序C.快速排序D.直接插入排序（6）以下排序方法中，不穩(wěn)定的排序方法是（AC）。A.直接選擇排序B.二分法插入排序C.堆排序D.基數(shù)排序（7）一個(gè)序列中有10000個(gè)元素，若只想得到其中前10個(gè)最小元素，最好采用（B）方法。A.快速排序B.堆排序C.插入排序D.二路歸并排序(8)若要求盡可能快地對(duì)實(shí)數(shù)數(shù)組進(jìn)行穩(wěn)定的排序，則應(yīng)選(C)A.快速排序B.堆排序C.歸并排序D.基數(shù)排序(9)排序的趟數(shù)與待排序元素的原始狀態(tài)有關(guān)的排序方法是(A)。

251A.冒泡排序B.快速排序C.插入排序D.選擇排序(10)直接插入排序在最好情況下的時(shí)間復(fù)雜度為(A)。A.0(n)B.0(logn)C.0(nlogn)D.0(n2)10.2給出初始待排序碼｛27,46,5,18,16,51,32,26｝使用下面各種排序算法的狀態(tài)變化示意圖：(1)直接插入排序；【答】：101[27]4651816513226[2746]51816513226[52746]1816513226[5182746]16513226[516182746]513226[51618274651]3226[5161827324651]26[516182627324651](2)表插入排序；【答】：key274651816513226link012345678(a)初始存儲(chǔ)狀態(tài)(b)(c)

252(b)(c)(d)key274651816513226link10012345678key274651816513226link120012345678key274651816513226link3201012345678key274651816513226link32041012345678key274651816513226link320514012345678link3265140012345678102(e)

253(b)(c)(3)二分法插入排序；【答】：這里只給出最后?趟將26二分插入前面的有序序列的過程。26<27,將high二midT;26>16,將low=mid+l;26>16,將low=mid+l;此時(shí)，highGow,二分定位結(jié)束，將4.?7的所有元素后移一位，將26插入到low指定的位置。最終排序結(jié)果為：key274651816513226link37651402012345678key274651816513226link37658402101234567812345678516182732465126lowmidhigh12345678lowmidhigh12345678516182732465126low,high12345678516182732465126

254highlow12345678516182732465126highlow103(4)直接選擇排序；【答】：(5)冒泡排序；1234567851618262732465112345678274651816513226i=lk=312345678546271816513226i=2k=5516271846513226i=3k=412345678516182746513226i=4k=812345678516182646513227

255i=5k=812345678516182627513246i=6k=712345678516182627325146i=7k=812345678516182627324651i=8104【答】：2746518165132262751816463226[51]51816273226[4651]516182726[324651]

25651618[2627324651]（6）快速排序；【答】：274651816513226[2616518]27[513246][18165]2627[513246][516]182627[513246]5[16]182627[513246]516182627[4632]51516182627[32]4651516182627324651（7）二路歸并排序；【答】：[27][46][5][18][16][51][32][26][2746][518][1651][2632][5182746][16263251][516182627324651]（8）基數(shù)排序?！敬稹浚?0.3在冒泡排序過程中，有的排序碼在某一次起泡中可能朝著與最終排序相反的方向移動(dòng)，試舉例說明。在快速排序過程中是否也會(huì)出現(xiàn)這種現(xiàn)象？【答】：例如，80,70,40,50在第一趟冒泡后序列變?yōu)?0,40,50,80,70朝著與最終排序相反的方向移動(dòng)了。在快速排序中也會(huì)出現(xiàn)這種情況，例如，對(duì)序列[90,32,25,50,60]以90劃分時(shí)，序列變?yōu)?/p>

257[60,32,25,50],90,其中60也朝與最終排序相反的方向移動(dòng)了。10.4修改冒泡排序算法，使第一趟把排序序碼最大的記錄放到最末尾，第二趟把排序碼最小的記錄在最前面，如此反復(fù)進(jìn)行，達(dá)到排序的目的?！敬稹浚篺tinclude"table,h”/*冒泡排序*/105voidbubblesort(table*L)(inti,j,k,done;i=l;j=L->length;done=l;while(done)(done=0;for(k=i;k<=j;k++)if(L->r[k+1].keyr[k].key)iL->r[0]=L->r[k];L->r[k]=L->r[k+1];L->r[k+1]=L->r[0];done=l;}J—；done=0;

258for(k=j;k>=i;k-)if(L->r[k].keyr[k-1].key)[L->r[0]=L->r[k];L->r[k]=L->r[k-l];L->r[k-l]=L->r[0];done=l;)i++；))intmain(){tableL;/*定義表L*/input(&L,"in.txt");/*從文件in.txt中讀入排序數(shù)據(jù)*/print(L);/*輸出原表*/bubblesort(&L);print(L);/*輸出排序后的表*/)10.5對(duì)習(xí)題10.2中給出的初始數(shù)列，給出堆排序中建堆過程示意圖。10.6[計(jì)數(shù)排序]一個(gè)記錄在已排序的文件中的位置，可由此文件中比該記錄排序碼小的記錄的個(gè)數(shù)而定，由此得到一個(gè)簡單的排序方法，對(duì)于每一個(gè)記錄，增加一個(gè)count字段確106定在已排序的文件中位于該記錄之前的記錄的個(gè)數(shù)，寫一個(gè)算法，確定一個(gè)無序文件中的每個(gè)

259記錄的count的值，并證明若文件有n個(gè)記錄，則至多進(jìn)行n(n-1)/2次排序碼比較，即可確定所有記錄的count值。10.5設(shè)計(jì)一個(gè)算法，重新排列一組整數(shù)位置，使所有負(fù)值的整數(shù)位于正值的整數(shù)之前(不要對(duì)這一組整數(shù)進(jìn)行排序，要求盡量減少算法中的交換次數(shù))。10.6對(duì)本章中的各種排序算法，說明哪些是穩(wěn)定的？哪些是不穩(wěn)定的？對(duì)不穩(wěn)定的排序算法舉例說明。10.7總結(jié)本章中各種排序算法的特點(diǎn)，分析比較各算法的時(shí)間、空間復(fù)雜度及附加存儲(chǔ)空間情況。10.10一油田欲建設(shè)一條連接油田內(nèi)n口油井的主輸油管道，管道由東向西，從每一口油井都有一條支輸油管道和主輸油管道相連。如果知道每口油井的具體位置，應(yīng)該如何確定主輸油管道的建設(shè)位置，使得所有支輸油管道的長度之和最小。10.11某大學(xué)一、二、三年級(jí)的學(xué)生報(bào)名參加一知識(shí)競(jìng)賽，報(bào)名信息包括年級(jí)和姓名，已知這3個(gè)年級(jí)都有學(xué)生報(bào)名，報(bào)名信息中的年級(jí)用1、2、3表示，設(shè)計(jì)一個(gè)算法對(duì)所有報(bào)名參賽學(xué)生按年級(jí)排序，要求排序算法的時(shí)間復(fù)雜度是線性的。