【正文】 1數(shù)據(jù)結(jié)構(gòu)（C 語言版）（第2 版）習(xí)題解析揭安全 李云清 楊慶紅江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院聯(lián)系方式：janquan@（習(xí)題答案僅供參考）2第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)算集合。 數(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)算集合。 兩個(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)。 線性結(jié)構(gòu)的特點(diǎn)是什么？非線性結(jié)構(gòu)的特點(diǎn)是什么？【答】：線性結(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ì)多的。 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式有哪幾種？【答】：數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、散列存儲(chǔ)和索引存儲(chǔ)等四種方式。 算法有哪些特點(diǎn)？它和程序的主要區(qū)別是什么？【答】：算法具有（1）有窮性（2）確定性（3）0 個(gè)或多個(gè)輸入（4）1 個(gè)或多個(gè)輸出（5）可行性等特征。程序是算法的一種描述方式，通過程序可以在計(jì)算機(jī)上實(shí)現(xiàn)算法。 抽象數(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ù)類型。 算法的時(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í)行效率，通常采用大寫O 符號(hào)表示算法的時(shí)間復(fù)雜度，大寫O 符號(hào)給出了函數(shù)f 的一個(gè)上限。其它義如下：3定義：f (n)=O (g (n)) 當(dāng)且僅當(dāng)存在正的常數(shù)c 和n0，使得對(duì)于所有的n≥n0，有f (n) ≤c g(n)。上述定義表明，函數(shù)f 頂多是函數(shù)g 的c 倍，除非n 小于n0。因此對(duì)于足夠大的n (如n≥n0)，g 是f 的一個(gè)上限（不考慮常數(shù)因子c）。在為函數(shù)f 提供一個(gè)上限函數(shù)g 時(shí)，通常使用比較簡單的函數(shù)形式。比較典型的形式是含有n 的單個(gè)項(xiàng)（帶一個(gè)常數(shù)系數(shù)）。表11 列出了一些常用的g 函數(shù)及其名稱。對(duì)于表11 中的對(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è)常量。表11 常用的漸進(jìn)函數(shù) 算法的空間復(fù)雜度指的是什么？如何表示？【答】：算法的空間復(fù)雜度是指算法在執(zhí)行過程中占用的額外的輔助空間的個(gè)數(shù)?？梢詫⑺硎緸閱栴}規(guī)模的函數(shù)，并通過大寫O符號(hào)表示空間復(fù)雜度。 對(duì)于下面的程序段，分析帶下劃線的語句的執(zhí)行次數(shù)，并給出它們的時(shí)間復(fù)雜度T(n)。（1） i++。（2） for(i=0。in。i++)if (a[i]x) x=a[i]。（3）for(i=0。in。i++)for(j=0。jn。j++)printf(“%d”,i+j)。（4）for (i=1。i=n1。i++){ k=i。for(j=i+1。j=n。j++)if(a[j]a[j+1]) k=j。t=a[k]。 a[k]=a[i]。 a[i]=t。}（5）for(i=0。in。i++)for(j=0。jn。j++){++x。s=s+x。}【答】：（1）O（1）；（2）O（n）；（3）O（n2）；（4）O（n）；（5）O（n2）4第2 章 線性表及其順序存儲(chǔ) 選擇題（1）表長為n 的順序存儲(chǔ)的線性表，當(dāng)在任何位置上插入或刪除一個(gè)元素的概率相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為（ E ），刪除一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為（ A ）。A．（n ? 1）/2 B．n C．n + 1 D．n ? 1E．n/2 F．(n + 1)/2 G．(n ? 2)/2（2）設(shè)棧S 和隊(duì)列Q 的初始狀態(tài)為空，元素eeee__________e5 和e6 依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6 個(gè)元素出隊(duì)的序列為eeeee5 和e1，則棧S的容量至少應(yīng)該為（ C ）。A．6 B．4 C．3 D．2（3）設(shè)棧的輸入序列為3 … n，若輸出序列的第一個(gè)元素為n，則第i 個(gè)輸出的元素為（ B ）。A．不確定 B．n ? i + 1 C．i D．n ? i（4）在一個(gè)長度為n 的順序表中刪除第i 個(gè)元素（1 = i = n）時(shí)，需向前移動(dòng)（ A ）個(gè)元素。A．n?i B．n ? i +1 C．n ? i ? 1 D．i（5）若長度為n 的線性表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，在第i 個(gè)位置上插入一個(gè)新元素的時(shí)間復(fù)雜度為（ A ）。A．O(n) B．O(1) C．O(n2) D．O(n3)（6）表達(dá)式a*(b+c)?d 的后綴表達(dá)式是（ B ）。A．a(chǎn)bcd*+? B．a(chǎn)bc+*d? C．a(chǎn)bc*+d? D．?+*abcd（7）隊(duì)列是一種特殊的線性表，其特殊性在于（ C ）。A．插入和刪除在表的不同位置執(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 + 1)%n = front ? 1 B．(rear + 1)%n = frontC．(rear)%n = front D．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 和1 B．2 和4 C．1 和5 D．4 和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)。 設(shè)計(jì)一個(gè)算法，求順序表中值為x 的結(jié)點(diǎn)的個(gè)數(shù)?！敬稹浚喉樞虮淼拇鎯?chǔ)結(jié)構(gòu)定義如下（）：include define N 100 /*預(yù)定義最大的數(shù)據(jù)域空間*/typedef int datatype。 /*假設(shè)數(shù)據(jù)類型為整型*/typedef struct {datatype data[N]。 /*此處假設(shè)數(shù)據(jù)元素只包含一個(gè)整型的關(guān)鍵字域*/int length。 /*線性表長度*/} seqlist。 /*預(yù)定義的順序表類型*/算法countx（L,x）用于求順序表L 中值為x 的結(jié)點(diǎn)的個(gè)數(shù)。int countx(seqlist *L,datatype x){ int c=0。int i。for (i=0。iLlength。i++)if (Ldata[i]==x) c++。return c。} 設(shè)計(jì)一個(gè)算法，將一個(gè)順序表倒置。即，如果順序表各個(gè)結(jié)點(diǎn)值存儲(chǔ)在一維數(shù)組a 中，倒置的結(jié)果是使得數(shù)組a 中的a[0]等于原來的最后一個(gè)元素，a[1] 等于原來的倒數(shù)第2 個(gè)元素，…，a 的最后一個(gè)元素等于原來的第一個(gè)元素?！敬稹浚海瑢?shí)現(xiàn)順序表倒置的算法程序如下：void verge(seqlist *L){int t,i,j。i=0。j=Llength1。while (ij){ t=Ldata[i]。Ldata[i++]=Ldata[j]。Ldata[j]=t。}} 已知一個(gè)順序表中的各結(jié)點(diǎn)值是從小到大有序的，設(shè)計(jì)一個(gè)算法，插入一個(gè)值為x 的結(jié)點(diǎn)，使順序表中的結(jié)點(diǎn)仍然是從小到大有序?！敬稹浚?，實(shí)現(xiàn)本題要求的算法程序如下：6void insertx(seqlist *L,datatype x){int j。if (LlengthN){ j=Llength1。while (j=0 amp。amp。 Ldata[j]x){ Ldata[j+1]=Ldata[j]。j。}Ldata[j+1]=x。Llength++。}} 將下列中綴表達(dá)式轉(zhuǎn)換為等價(jià)的后綴表達(dá)式。(1) 5+6*7(2) (56)/7(3) 56*7*8(4) 5*78(5) 5*(76)+8/9(6) 7*(56*8)9【答】：(7) 5+6*7 后綴表達(dá)式：5 6 7*+(8) (56)/7 后綴表達(dá)式：5 67/(9) 56*7*8 后綴表達(dá)式：5 6 7*8*(10) 5*78 后綴表達(dá)式：5 7* 8(11) 5*(76)+8/9 后綴表達(dá)式：5 7 6*8 9/+(12) 7*(56*8)9 后綴表達(dá)式：7 5 6 8**9 循環(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á)式。【答】：循環(huán)隊(duì)列中當(dāng)前結(jié)點(diǎn)個(gè)數(shù)的計(jì)算公式是：(n+rearfront)%n 編號(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={r1,r2,…,rn}是要進(jìn)行排列的n 個(gè)元素，Ri=R{ri}。集合X 中元素的全排列記為perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個(gè)排列前加上前綴ri 得到的排列。R 的全排列可歸納定義如下：當(dāng)n=1 時(shí)，perm(R)=(r)，其中r 是集合R 中惟一的元素；當(dāng)n1 時(shí)，perm(R)由(r1)perm(R1),(r2)perm(R2),…,(rn)perm(Rn)構(gòu)成。依此遞歸定義，可設(shè)計(jì)產(chǎn)生perm(R)的遞歸算法如下：遞歸解法：()includeint cont=1。 /*全局變量，用于記錄所有可能的出棧序列個(gè)數(shù)*/void print(int str[],int n)。/*求整數(shù)序列str[]從k 到n 的全排列*/void perm(int str[],int k,int n){int i,temp。if (k==n1) print(str,n)。else{ for (i=k。in。i++){temp=str[k]。 str[k]=str[i]。 str[i]=temp。perm(str,k+1,n)。 /*遞歸調(diào)用*/temp=str[i]。 str[i]=str[k]。 str[k]=temp。}}}/*本函數(shù)判斷整數(shù)序列str[]是否滿足進(jìn)出棧規(guī)則,若滿足則輸出*/void print(int str[],int n){int i,j,k,l,m,flag=1,b[2]。for(i=0。in。i++) /*對(duì)每個(gè)str[i]判斷其后比它小的數(shù)是否為降序序列*/{ m=0。for(j=i+1。jnamp。amp。flag。j++)if (str[i]str[j]) {if (m==0) b