(完整word版)數(shù)據(jù)結構習題與答案

1、第1 章緒論課后習題講解1. 填空(1)()是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理?！窘獯稹繑?shù)據(jù)元素3()是數(shù)據(jù)的最小單位，()是討論數(shù)據(jù)結構時涉及的最小數(shù)據(jù)單位?！窘獯稹繑?shù)據(jù)項，數(shù)據(jù)元素【分析】數(shù)據(jù)結構指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關系。 從邏輯關系上講，數(shù)據(jù)結構主要分為( )、( )、( )和( )?！窘獯稹考?，線性結構，樹結構，圖結構 數(shù)據(jù)的存儲結構主要有( )和( )兩種基本方法，不論哪種存儲結構，都要存儲兩方面的內(nèi)容：()和( )。【解答】順序存儲結構，鏈接存儲結構，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關系 算法具有五個特性，分別是( )、( )、()、( )、( )

2、?！窘獯稹坑辛銈€或多個輸入，有一個或多個輸出，有窮性，確定性，可行性 算法的描述方法通常有( )、( )、( )和( )四種，其中，( )被稱為算法語言?！窘獯稹孔匀徽Z言，程序設計語言，流程圖，偽代碼，偽代碼 在一般情況下，一個算法的時間復雜度是( )的函數(shù)?！窘獯稹繂栴}規(guī)模設待處理問題的規(guī)模為 n，若一個算法的時間復雜度為一個常數(shù)，則表示成數(shù)量級的形式為()，若為 n*log25n ，則表示成數(shù)量級的形式為( )?！窘獯稹?(1), O(nlog2n)【分析】用大 O 記號表示算法的時間復雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。2. 選擇題 順序存儲結構中數(shù)據(jù)元素之間的邏輯關系是由(

3、)表示的，鏈接存儲結構中的數(shù)據(jù)元素之間的邏輯關 系是由( )表示的。A 線性結構 B 非線性結構 C 存儲位置 D 指針【解答】 C， D【分析】順序存儲結構就是用一維數(shù)組存儲數(shù)據(jù)結構中的數(shù)據(jù)元素，其邏輯關系由存儲位置(即元素在數(shù) 組中的下標)表示；鏈接存儲結構中一個數(shù)據(jù)元素對應鏈表中的一個結點，元素之間的邏輯關系由結點中 的指針表示。子女間不 假設有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn); 能相互繼承。則表示該遺產(chǎn)繼承關系的最合適的數(shù)據(jù)結構應該是（）。A樹B圖C線性表D集合【解答】B【分析】將丈夫、妻子和子女分別作為數(shù)據(jù)元素，根據(jù)題意畫岀邏輯結構圖。團17

4、逅產(chǎn)綻承邏輯結構團算法指的是（）。A對特定問題求解步驟的一種描述，是指令的有限序列。B計算機程序 C解決問題的計算方法 D數(shù)據(jù)處理【解答】A【分析】計算機程序是對算法的具體實現(xiàn)；簡單地說，算法是解決問題的方法；數(shù)據(jù)處理是通過算法完成 的。所以，只有A是算法的準確定義。下面（）不是算法所必須具備的特性。A有窮性 B確切性C高效性 D可行性【解答】C【分析】高效性是好算法應具備的特性。算法分析的目的是（），算法分析的兩個主要方面是（ ）。A找岀數(shù)據(jù)結構的合理性 B研究算法中輸入和輸岀的關系C分析算法的效率以求改進 D分析算法的易讀性和文檔性E空間性能和時間性能 F正確性和簡明性G可讀性和文檔性 H

5、數(shù)據(jù)復雜性和程序復雜性【解答】C，E3. 判斷題 算法的時間復雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定。【解答】錯。時間復雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級來確定。每種數(shù)據(jù)結構都具備三個基本操作：插入、刪除和查找?！窘獯稹垮e。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結構。所謂數(shù)據(jù)的邏輯結構指的是數(shù)據(jù)之間的邏輯關系?！窘獯稹垮e。是數(shù)據(jù)之間的邏輯關系的整體。 邏輯結構與數(shù)據(jù)元素本身的內(nèi)容和形式無關。【解答】對。因此邏輯結構是數(shù)據(jù)組織的主要方面?；谀撤N邏輯結構之上的基本操作，其實現(xiàn)是唯一的?！窘獯稹垮e?；静僮鞯膶崿F(xiàn)是基于某種存儲結構設計的，因而不是唯一的4. 分析以下各程序段，并

6、用大 0記號表示其執(zhí)行時間do(1)出whilek=k-+iO*i；i+i while (Hf) y-Q ;while (y+l) + (y+l)=n) i-Uj-D;while (i+j=n) 勒)j卄; dsei+,fir瓷司，廿十)for (T,衣勺;K+)【解答】 基本語句是k=k+1O*i，共執(zhí)行了 n-2次，所以T(n)=O(n)?；菊Z句是k=k+1O*i，共執(zhí)行了 n次，所以T(n)=O(n)。分析條件語句，每循環(huán)一次，i+j整體加1，共循環(huán)n次，所以T(n)=O(n)設循環(huán)體共執(zhí)行T(n)次，每循環(huán)一次，循環(huán)變量y加1，最終T(n)=y，即:仃(n)+1)2 所以 T(n)=

7、O(n1/2)。x+是基本語句，所以5 設有數(shù)據(jù)結構(D，R)，其中 D=1,2, 3, 4, 5, 6，R=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)試畫岀其邏輯結構圖并指岀屬于何種結構?！窘獯稹科溥壿嫿Y構圖如圖1-3所示，它是一種圖結構。H1-3邏梔結構囲6. 為整數(shù)定義一個抽象數(shù)據(jù)類型，包含整數(shù)的常見運算，每個運算對應一個基本操作，每個基本操作的接 口需定義前置條件、輸入、功能、輸岀和后置條件?！窘獯稹空麛?shù)的抽象數(shù)據(jù)類型定義如下：ADT integerData整數(shù)a：可以是正整數(shù)（1,2, 3,、負整數(shù)（-1,-2,- 3,和零Oper

8、ationConstructor前置條件：整數(shù)a不存在輸入：一個整數(shù) b 功能：構造一個與輸入值相同的整數(shù) 輸出：無后置條件：整數(shù) a 具有輸入的值Set前置條件：存在一個整數(shù) a 輸入：一個整數(shù) b功能：修改整數(shù) a 的值，使之與輸入的整數(shù)值相同 輸出：無后置條件：整數(shù) a 的值發(fā)生改變Add前置條件：存在一個整數(shù) a 輸入：一個整數(shù) b 功能：將整數(shù) a 與輸入的整數(shù) b 相加 輸出：相加后的結果后置條件：整數(shù) a 的值發(fā)生改變Sub 前置條件：存在一個整數(shù) a 輸入：一個整數(shù) b 功能：將整數(shù) a 與輸入的整數(shù) b 相減 輸出：相減的結果后置條件：整數(shù) a 的值發(fā)生改變Multi 前置條

9、件：存在一個整數(shù) a 輸入：一個整數(shù) b 功能：將整數(shù) a 與輸入的整數(shù) b 相乘 輸出：相乘的結果后置條件：整數(shù) a 的值發(fā)生改變Div 前置條件：存在一個整數(shù) a 輸入：一個整數(shù) b 功能：將整數(shù) a 與輸入的整數(shù) b 相除 輸出：若整數(shù) b 為零，則拋出除零異常，否則輸出相除的結果 后置條件：整數(shù) a 的值發(fā)生改變Mod前置條件：存在一個整數(shù) a 輸入：一個整數(shù) b 功能：求當前整數(shù)與輸入整數(shù)的模，即正的余數(shù) 輸出：若整數(shù) b 為零，則拋出除零異常，否則輸出取模的結果 后置條件：整數(shù) a 的值發(fā)生改變Equal前置條件：存在一個整數(shù)a輸入：一個整數(shù)b功能：判斷整數(shù)a與輸入的整數(shù)b是否相等

10、輸岀：若相等返回1，否則返回0后置條件：整數(shù)a的值不發(fā)生改變endADT7. 求多項式A(x)的算法可根據(jù)下列兩個公式之一來設計： A(x)=anxn+an-1xn- 1+a1x+a0 A(x)=(anx+an -1)x+ +a1)x)+a0根據(jù)算法的時間復雜度分析比較這兩種算法的優(yōu)劣?！窘獯稹康诙N算法的時間性能要好些。第一種算法需執(zhí)行大量的乘法運算，而第二種算法進行了優(yōu)化, 減少了不必要的乘法運算。8. 算法設計(要求：算法用偽代碼和C+描述，并分析最壞情況下的時間復雜度)對一個整型數(shù)組An設計一個排序算法?！窘獯稹肯旅媸呛唵芜x擇排序算法的偽代碼描述。AT對n個記錄進行n-l趙簡單選捋捷序

11、Iy 1.1在無序區(qū)i, tri中選取最小記錄，設其下標次indeK： V 1.2播最中記錄弓第1個記靈交換1下面是簡單選擇排序算法的 C+描述。簡笙選擇掃卡序算廷Se!比詣ort 5roid Sd ectSort.(ml r , int n)(for (i=0;kh-1u)錄進行卷簡單遶擇排序(indcsE”for (j=i+l;jvi,戶再閃無序區(qū)中選職盤小記錄if 曲next=（p-next）-next單鏈表中設置頭結點的作用是（）。【解答】為了運算方便【分析】例如在插入和刪除操作時不必對表頭的情況進行特殊處理。非空的單循環(huán)鏈表由頭指針head指示，則其尾結點（由指針 p所指）滿足（）。

12、【解答】p-next=head【分析】如圖2-8所示。j-L-k-1-在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個結點s的操作序列是（）；刪除開始結點的操作序列為（）。【解答】 s-next =rear-next; rear-next =s; rear =s;q=rear-next-next; rear-next-next=q-next; delete q;【分析】操作示意圖如圖2-9所示：q総的 一% 務J亠 )rearj3real8 ;3-!5國帶尾指打的腿環(huán)鏈表中菇入和刪除操件示意冏一個具有n個結點的單鏈表，在指針 p所指結點后插入一個新結點的時間復雜度為（）；在給定值為x的結點

13、后插入一個新結點的時間復雜度為（）?！窘獯稹?（1）, 0（n）【分析】在p所指結點后插入一個新結點只需修改指針，所以時間復雜度為0（1）;而在給定值為x的結點后插入一個新結點需要先查找值為x的結點，所以時間復雜度為0（n）。 可由一個尾指針唯一確定的鏈表有（ ）、（ ）、（ ）?！窘獯稹垦h(huán)鏈表，循環(huán)雙鏈表，雙鏈表2. 選擇題 線性表的順序存儲結構是一種（ ）的存儲結構，線性表的鏈接存儲結構是一種（ ）的存儲結構。A 隨機存取 B 順序存取 C 索引存取 D 散列存取【解答】 A， B 【分析】參見 2.2.1 。 線性表采用鏈接存儲時，其地址（ ）。A 必須是連續(xù)的 B 部分地址必須是連續(xù)

14、的C 一定是不連續(xù)的 D 連續(xù)與否均可以【解答】 D 【分析】線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以連續(xù)，也 可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。 單循環(huán)鏈表的主要優(yōu)點是（ ）。A 不再需要頭指針了B 從表中任一結點出發(fā)都能掃描到整個鏈表；C 已知某個結點的位置后，能夠容易找到它的直接前趨；D 在進行插入、刪除操作時，能更好地保證鏈表不斷開?！窘獯稹?B 鏈表不具有的特點是（ ）。A 可隨機訪問任一元素 B 插入、刪除不需要移動元素C 不必事先估計存儲空間 D 所需空間與線性表長度成正比【解答】 A 若某線性表中最常用的操作是取第 i 個元素和找

15、第 i 個元素的前趨，則采用（ ）存儲方法最節(jié)省時間。A 順序表 B 單鏈表 C 雙鏈表 D 單循環(huán)鏈表【解答】 A【分析】線性表中最常用的操作是取第 i 個元素，所以，應選擇隨機存取結構即順序表，同時在順序表中 查找第 i 個元素的前趨也很方便。 單鏈表和單循環(huán)鏈表既不能實現(xiàn)隨機存取， 查找第 i 個元素的前趨也不方 便，雙鏈表雖然能快速查找第 i 個元素的前趨，但不能實現(xiàn)隨機存取。 若鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除第一個結點，則采用（ ）存儲方法 最節(jié)省時間。A 單鏈表 B 帶頭指針的單循環(huán)鏈表 C 雙鏈表 D 帶尾指針的單循環(huán)鏈表【解答】 D 【分析】在鏈表中的

16、最后一個結點之后插入一個結點需要知道終端結點的地址，所以，單鏈表、帶頭指針 的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第一個結點，其時間性能是 O（1） ， 所以，答案是 D 。 若鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，則采用( )存儲方 法最節(jié)省運算時間。A 單鏈表 B 循環(huán)雙鏈表 C 單循環(huán)鏈表 D 帶尾指針的單循環(huán)鏈表【解答】 B 【分析】在鏈表中的最后一個結點之后插入一個結點需要知道終端結點的地址，所以，單鏈表、單循環(huán)鏈 表都不合適，刪除最后一個結點需要知道終端結點的前驅(qū)結點的地址，所以，帶尾指針的單循環(huán)鏈表不合 適，而循環(huán)雙鏈表滿足

17、條件。 在具有 n 個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是( )。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】 B【分析】首先應順序查找新結點在單鏈表中的位置。 對于 n 個元素組成的線性表，建立一個有序單鏈表的時間復雜度是( )。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】 C【分析】該算法需要將 n 個元素依次插入到有序單鏈表中，而插入每個元素需 O(n) 。 使用雙鏈表存儲線性表，其優(yōu)點是可以( )。A 提高查找速度 B 更方便數(shù)據(jù)的插入和刪除C 節(jié)約存儲空間 D 很快回收存儲空間【解答】 B【分析】在鏈表中

18、一般只能進行順序查找，所以，雙鏈表并不能提高查找速度，因為雙鏈表中有兩個指針 域，顯然不能節(jié)約存儲空間，對于動態(tài)存儲分配，回收存儲空間的速度是一樣的。由于雙鏈表具有對稱性， 所以，其插入和刪除操作更加方便。(11) 在一個單鏈表中，已知q所指結點是p所指結點的直接前驅(qū)，若在q和p之間插入s所指結點，則執(zhí)行( )操作。A s-next=p-next; p-next=s; B q-next=s; s-next=p;C p-next=s-next; s-next=p; D p-next=s; s-next=q;【解答】 B【分析】注意此題是在 q 和 p 之間插入新結點，所以，不用考慮修改指針的順序

19、。(12) 在循環(huán)雙鏈表的p所指結點后插入s所指結點的操作是()。A p-next=s; s-prior=p; p-next-prior=s; s-next=p-next;B p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;C s-prior=p; s-next=p-next; p-next=s; p-next-prior=s;D s-prior=p; s-next=p-next; p-next-prior=s; p-next=s【解答】 D【分析】在鏈表中，對指針的修改必須保持線性表的邏輯關系，否則，將違背線性表的邏輯特征，圖2-10給出

20、備選答案C和D的圖解。闔備選答案C操作示意圖（第4步指針修改無法進行）0備選答案D操作示意剛圄Q10滾槌表橢入揉非修改扌詐i撫作示意圄3. 判斷題線性表的邏輯順序和存儲順序總是一致的?！窘獯稹垮e。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序和存儲順序不一定一致。線性表的順序存儲結構優(yōu)于鏈接存儲結構。【解答】錯。兩種存儲結構各有優(yōu)缺點。設p，q是指針，若p=q，則*p=*q。【解答】錯。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相同。 線性結構的基本特征是：每個元素有且僅有一個直接前驅(qū)和一個直接后繼?！窘獯稹垮e。每個元素最多只有一個直接前驅(qū)和一個直接后繼，第一個元素沒有前驅(qū)，最后

21、一個元素沒有 后繼。 在單鏈表中，要取得某個元素，只要知道該元素所在結點的地址即可，因此單鏈表是隨機存取結構?！窘獯稹垮e。要找到該結點的地址，必須從頭指針開始查找，所以單鏈表是順序存取結構。4 請說明順序表和單鏈表各有何優(yōu)缺點，并分析下列情況下，采用何種存儲結構更好些。若線性表的總長度基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素。如果n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化。描述一個城市的設計和規(guī)劃。【解答】順序表的優(yōu)點： 無需為表示表中元素之間的邏輯關系而增加額外的存儲空間；可以快速地存取表中任一位置的元素（即隨機存?。?。順序表的缺點：插入和刪

22、除操作需移動大量元素； 表的容量難以確定； 造成存儲空間的 碎片”單鏈表的優(yōu)點： 不必事先知道線性表的長度；插入和刪除元素時只需修改指針，不用移動元素。單鏈表的缺點： 指針的結構性開銷； 存取表中任意元素不方便，只能進行順序存取。應選用順序存儲結構。因為順序表是隨機存取結構，單鏈表是順序存取結構。本題很少進行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應選用順序存儲結構。應選用鏈接存儲結構。鏈表容易實現(xiàn)表容量的擴充，適合表的長度動態(tài)發(fā)生變化。 應選用鏈接存儲結構。因為一個城市的設計和規(guī)劃涉及活動很多，需要經(jīng)常修改、擴充和刪除各種信息，才能適應不斷發(fā)展的需要。而順序表的插入、刪除的效率

23、低，故不合適。5 算法設計 設計一個時間復雜度為O (n)的算法，實現(xiàn)將數(shù)組 An中所有元素循環(huán)右移 k個位置 【解答】算法思想請參見主教材第一章思想火花。下面給岀具體算法。錨環(huán)石移茸法Conversevoid Converse(int A n int n, int k)Reverse CA, XReverse fA,匕 n- DReverse氏void Reverse (int A T iiit fr(jin= uit tn)胛S魏組 A 中元索或 訊到怙進置far (iHJ, iw十 1)/2; i”)Afrom+i A to-i:阪換元素分析算法，第一次調(diào)用Reverse函數(shù)的時間復雜度

24、為 O(k)，第二次調(diào)用Reverse函數(shù)的時間復雜度為O(n-k),第三次調(diào)用Reverse函數(shù)的時間復雜度為 O(n)，所以，總的時間復雜度為0(n)。 已知數(shù)組An中的元素為整型，設計算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元 素為偶數(shù)，并要求算法的時間復雜度為O(n)?！窘獯稹繌臄?shù)組的兩端向中間比較，設置兩個變量i和j,初始時i=0 , j=n-1 ,若Ai為偶數(shù)并且Aj為奇數(shù)，則將Ai與Aj交換。具體算法如下：分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時間復雜度為O(n)。試編寫在無頭結點的單鏈表上實現(xiàn)線性表的插入操作的算法，并和帶頭結點的單鏈表上的插入操作的實現(xiàn)進行比較

25、?！窘獯稹繀⒁?.2.3。試分別以順序表和單鏈表作存儲結構，各寫一實現(xiàn)線性表就地逆置的算法?！窘獯稹宽樞虮淼哪嬷茫词菍ΨQ元素交換，設順序表的長度為length，則將表中第i個元素與第length-i-1 個元素相交換。具體算法如下：順序表逆置算法 Kever鴕template void Reversed data r tut len.gUi) for (i=t); i=length/2 F(teiwp=d3tai;datai =dataltngth_i_ 1 , datalength-i-1 temp;單鏈表的逆置請參見 224算法2-4和算法2-6。假設在長度大于1的循環(huán)鏈表中，即無頭結

26、點也無頭指針，s為指向鏈表中某個結點的指針，試編寫算法刪除結點s的前趨結點?！窘獯稹坷脝窝h(huán)鏈表的特點， 通過指針s可找到其前驅(qū)結點r以及r的前驅(qū)結點p，然后將結點r刪除, 如圖2-11所示，具體算法如下：E2-11釧除結點令的前駛結點按作示意圖已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構造三個循環(huán)鏈表， 使每個循環(huán)鏈表中只含同一類字符?！窘獯稹吭趩捂湵?A中依次取元素，若取岀的元素是字母，把它插入到字母鏈表B中，若取岀的元素是數(shù)字，則把它插入到數(shù)字鏈表 D中，直到鏈表的尾部，這樣表 B，D，A中分別存放字母、數(shù)字和其他字符。 具體算法如下：teniplate

27、void Adjust (No deblode *D ModeD-neviz Node-ne5Ct-D; 他逹空諂環(huán)鏈表D存敢蛾手 Miew Node, B-nEKt=B, 卩刨逢空循環(huán)鏈裘B存戲字咼 P=AP“工作指鈦勺初敕；while gif (CAdaU)&(q*2911 (pa data) & (q-datazO)( p-ne5!t=q- ned； q-iieKt=B-nKt;B-Mext刑采用頭插法插在循環(huán)鏈表B的頭箔點的后面dse if (lO=9)(p-neKt=q-nsd.pq-ncKt=D-1161,D-nexi-q;采用頭插法插在循環(huán)鋰表D的頭結點的后面else p=qF

28、q=;p-TiesL;p-nffirt=A; R=A卜將犍憲A構造為褲環(huán)謹表為隊芋母和數(shù)字輕耳幗孚符 設單鏈表以非遞減有序排列，設計算法實現(xiàn)在單鏈表中刪去值相同的多余結點?！窘獯稹繌念^到尾掃描單鏈表，若當前結點的元素值與后繼結點的元素值不相等，則指針后移；否則刪除 該后繼結點。具體算法如下：單讎袁州除和同值算決Purgevoid Purge (Node * first)(p-first-)neKt;while (pnsKt)if (p- data- =p- n ext- tiata) q=next;delete qp判斷帶頭結點的雙循環(huán)鏈表是否對稱。【解答】設工作指針p和q分別指向循環(huán)雙鏈表的

29、開始結點和終端結點，若結點p和結點q的數(shù)據(jù)域相等,則工作指針p后移，工作指針q前移，直到指針p和指針q指向同一結點（循環(huán)雙鏈表中結點個數(shù)為奇數(shù)） 或結點q成為結點p的前驅(qū)（循環(huán)雙鏈表中結點個數(shù)為偶數(shù)）。如圖 2-12所示。圖茁口判斷循環(huán)雙雜表對稱的操作示意圖判斷雙讎表對徹算蟲Equaltemphte struct DiilNcdcCT data：Dulblocle rpirior? *neift;,template boal Eqral (DulNode * first)(p=first-nExt: q=iirEt-pricrrjwhile (p!=q p-prior!=q)if (p-dat

30、a= =q-data)(p=p-nesrtT工作獵針p后穆pnar;工作捋針q前移) else return 0?rettrti I;學習自測及答案1. 已知一維數(shù)組A采用順序存儲結構，每個元素占用 4個存儲單元，第9個元素的地址為144，則第一個 元素的地址是（）。A 108 B 180 C 176 D 112【解答】D2 在長度為n的線性表中查找值為x的數(shù)據(jù)元素的時間復雜度為：（）。A 0（0） B 0（1） C 0（n） D 0（n2）【解答】C3 .在一個長度為n的順序表的第i （1 i n+1個元素之前插入一個元素，需向后移動（）個元素，刪除第i （1i n個元素時，需向前移動（）個

31、元素。【解答】n-i+1 ，n-i4 在單鏈表中，除了頭結點以外，任一結點的存儲位置由（）指示。【解答】其前趨結點的指針域5 當線性表采用順序存儲結構時，其主要特點是（【解答】邏輯結構中相鄰的結點在存儲結構中仍相鄰）結點，另一個指向（）結點6 在雙鏈表中，每個結點設置了兩個指針域，其中一個指向（ 【解答】前驅(qū)，后繼7 設A是一個線性表（a1, a2,）,an采用順序存儲結構，則在等概率的前提下，平均每插入一個元素需要移動的元素個數(shù)為多少？若元素插在ai與ai+1之間（1i n的概率為冷（耳十D，則平均每插入一個元素所要移動的元素個數(shù)又是多少？【解答】- a + 1) = i.i28 .線性表存

32、放在整型數(shù)組 Aarrsize的前elenum個單元中，且遞增有序。編寫算法，將元素 x插入到線 性表的適當位置上，以保持線性表的有序性，并且分析算法的時間復雜度?！窘獯稹勘绢}是在一個遞增有序表中插入元素 x，基本思路是從有序表的尾部開始依次取元素與x比較，若大于x，此元素后移一位，再取它前面一個元素重復上述步驟；否則，找到插入位置，將x插入。具體算法如下：9.已知單鏈表中各結點的元素值為整型且遞增有序，設計算法刪除鏈表中所有大于mink且小于maxk的所有元素，并釋放被刪結點的存儲空間?！窘獯稹恳驗槭窃谟行騿捂湵砩系牟僮?，所以，要充分利用其有序性。在單鏈表中查找第一個大于mink的結點和第一

33、個小于 maxk的結點，再將二者間的所有結點刪除。有序犍除算DdeteB etweeo tetnplate void D 日 EttBctwccfi* firsts int mink, int mank)Cp=firsl;while& neirtdatacmnk)if (p-nest) q=|L neKt;while u=q-neKts p-nesi=q-.tie3rtJ delete q,10 設單循環(huán)鏈表L1，對其遍歷的結果是：x1, x2, x3,1,畑。請將該循環(huán)鏈表拆成兩個單循環(huán)鏈表L1和L2，使得L1中含有原L1表中序號為奇數(shù)的結點且遍歷結果為：x1, x3,; L2中含有原L1表

34、中序號為偶數(shù)的結點且遍歷結果為：,x4, x2。【解答】算法如下：彳盾環(huán)潘衣柄分算法DePatch template class TNod? *D ePatch (Hq de *L1) (L-2=new NodeT?*, L2 116x12; q=Li-neKU Ll-nEXt=Ll;P=L11；whole (q!=Ll)(1)川至用尾插法 pnert.q; p=q” p=iiE2b=Ll L q=q-nextu；) else L2-tieKt=q1L iq-neKtp cj- nezb=L 2 - ne5jtT i+h第 3 章 特殊線性表 棧、隊列和串課后習題講解1. 填空 設有一個空棧，

35、棧頂指針為 1000H ，現(xiàn)有輸入序列為 1、2、3、4、5， 經(jīng)過 push ，push ，pop ，push ， pop ，push ，push 后，輸出序列是( )，棧頂指針為( )?！窘獯稹?23， 1003H 棧通常采用的兩種存儲結構是( )；其判定?？盏臈l件分別是( )，判定棧滿的條件分別是( )。 【解答】順序存儲結構和鏈接存儲結構(或順序棧和鏈棧)，棧頂指針 top= -1 和 top=NULL ，棧頂指針 top 等于數(shù)組的長度和內(nèi)存無可用空間3()可作為實現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結構?！窘獯稹織！痉治觥窟f歸函數(shù)的調(diào)用和返回正好符合后進先出性。 表達式 a*(b+c)-d 的

36、后綴表達式是( )。【解答】 abc+*d- 【分析】將中綴表達式變?yōu)楹缶Y表達式有一個技巧：將操作數(shù)依次寫下來，再將算符插在它的兩個操作數(shù)的后面。 棧和隊列是兩種特殊的線性表，棧的操作特性是( )，隊列的操作特性是( )，棧和隊列的主要區(qū)別 在于( )。【解答】后進先出，先進先出，對插入和刪除操作限定的位置不同 循環(huán)隊列的引入是為了克服( )。【解答】假溢出 數(shù)組 Qn 用來表示一個循環(huán)隊列， front 為隊頭元素的前一個位置， rear 為隊尾元素的位置，計算隊列 中元素個數(shù)的公式為( )。【解答】( rear-front+n ) % n【分析】也可以是( rear-front ) % n

37、 ，但 rear-front 的結果可能是負整數(shù)，而對一個負整數(shù)求模，其結果 在不同的編譯器環(huán)境下可能會有所不同。用循環(huán)鏈表表示的隊列長度為n,若只設頭指針，則出隊和入隊的時間復雜度分別是()和()。【解答】0，0(n) 【分析】在帶頭指針的循環(huán)鏈表中，出隊即是刪除開始結點，這只需修改相應指針；入隊即是在終端結點的后面插入一個結點，這需要從頭指針開始查找終端結點的地址。 串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。【解答】數(shù)據(jù)元素的類型是一個字符 兩個串相等的充分必要條件是（ ）?！窘獯稹块L度相同且對應位置的字符相等【分析】例如abc工abc , abc工bca。2. 選擇題若一個棧的輸入序列

38、是1 , 2, 3,，n，輸出序列的第一個元素是n，則第i個輸出元素是（）。A 不確定 B n-i C n-i-1 D n-i+1【解答】 D【分析】此時，輸出序列一定是輸入序列的逆序。 設棧S和隊列Q的初始狀態(tài)為空，元素 el、e2、e3、e4、e5、e6依次通過棧S, 個元素出棧后即進 入隊列Q,若6個元素出隊的順序是 e2、e4、e3、e6、e5、el，則棧S的容量至少應該是（）。A 6B 4C 3D 2【解答】 C【分析】 由于隊列具有先進先出性， 所以，此題中隊列形同虛設， 即出棧的順序也是 e2、 e4、 e3、 e6、 e5、e1 。 一個棧的入棧序列是 1， 2， 3， 4，

39、5，則棧的不可能的輸出序列是（ ）。A 54321 B 45321 C 43512 D 12345【解答】 C【分析】此題有一個技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序 號）的兩個元素。 設計一個判別表達式中左右括號是否配對的算法，采用（）數(shù)據(jù)結構最佳A 順序表 B 棧 C 隊列 D 鏈表【解答】 B【分析】每個右括號與它前面的最后一個沒有匹配的左括號配對，因此具有后進先出性。 在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印緩沖區(qū)，該緩沖區(qū)應該是一個 （ ）結構。A 棧 B 隊列 C 數(shù)組 D 線性表【解答】 B【分析】先進入打印緩沖區(qū)的文件先被

40、打印，因此具有先進先出性。 一個隊列的入隊順序是 1， 2， 3， 4，則隊列的輸出順序是（ ）。A 4321 B 1234 C 1432 D 3241【解答】 B【分析】隊列的入隊順序和出隊順序總是一致的。 棧和隊列的主要區(qū)別在于（ ）。A 它們的邏輯結構不一樣 B 它們的存儲結構不一樣C所包含的運算不一樣D插入、刪除運算的限定不一樣【解答】D【分析】棧和隊列的邏輯結構都是線性的，都有順序存儲和鏈接存儲，有可能包含的運算不一樣，但不是主要區(qū)別，任何數(shù)據(jù)結構在針對具體問題時包含的運算都可能不同。 設數(shù)組Sn作為兩個棧S1和S2的存儲空間，對任何一個棧只有當Sn全滿時才不能進行進棧操作。為這兩個

41、棧分配空間的最佳方案是（）。A S1的棧底位置為0，S2的棧底位置為n-1B S1的棧底位置為0， S2的棧底位置為n/2C S1的棧底位置為0，S2的棧底位置為nD S1的棧底位置為0，S2的棧底位置為1【解答】A【分析】兩棧共享空間首先兩個棧是相向增長的，棧底應該分別指向兩個棧中的第一個元素的位置，并注意C+中的數(shù)組下標是從 0開始的。 設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作（）。A連接B模式匹配 C求子串D求串長【解答】B3. 判斷題 有n個元素依次進棧，則出棧序列有 （n-1）/2種。（加）！【解答】錯。應該有川十1）刑種。 ?？梢宰鳛閷崿F(xiàn)過程調(diào)用的一種數(shù)據(jù)結構?！窘獯稹?/p>

42、對。只要操作滿足后進先岀性，都可以采用棧作為輔助數(shù)據(jù)結構。在棧滿的情況下不能做進棧操作，否則將產(chǎn)生上溢”【解答】對。 在循環(huán)隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，則隊滿的條件是front=rear 。【解答】錯。這是隊空的判定條件，在循環(huán)隊列中要將隊空和隊滿的判定條件區(qū)別開?？沾c空格串是相同的?！窘獯稹垮e?？沾拈L度為零，而空格串的長度不為0，其長度是串中空格的個數(shù)。4. 設有一個棧，元素進棧的次序為A，B，C，D，E,能否得到如下岀棧序列，若能，請寫岀操作序列，若不能，請說明原因。 C，E，A，B，D C，B，A，D，E【解答】不能，因為在 C、E出棧的情

43、況下，A一定在棧中，而且在 B的下面，不可能先于 B出棧。 可以，設I為進棧操作，0為入棧操作，則其操作序列為HI000I0I0。5. 舉例說明順序隊列的假溢出”現(xiàn)象。【解答】假設有一個順序隊列，如圖3-6所示，隊尾指針rear=4，隊頭指針front=1，如果再有元素入隊，就會產(chǎn)生 上溢”此時的 上溢”又稱為 假溢出”因為隊列并不是真的溢出了，存儲隊列的數(shù)組中還有2個存儲單元空閑，其下標分別為0和1。6. 在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂元素和棧底元素分 別是什么？ ( push(k)表示整數(shù)k入棧，pop表示

44、棧頂元素出棧。)【解答】棧頂元素為6，棧底元素為1。其執(zhí)行過程如圖3-7所示。 push(l) j push 出甌何 pop j push C5) t F宙h C7)9) pop f (6)圖牛了棧的執(zhí)行過程示意圖7. 在操作序列 EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue7)、DeQueue、EnQueue(9) 之后，隊頭元素和隊尾元素分別是什么？(EnQueue(k)表示整數(shù)k入隊，DeQueue表示隊頭元素出隊)?！窘獯稹筷狀^元素為5，隊尾元素為9。其執(zhí)行過程如圖3-8所示。同 EiiQiiaue G) jEnQueue G) (b

45、) DeQueue jEnQwtue C5) jEnQueue U) (c) De Queue jEnQueue CS) 圖滬8臥列的執(zhí)行過程示意團8 .空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的 個數(shù)。串中的空格符可用來分隔一般的字符，便于人們識別和閱讀，但計算串長時應包括這些空格符?？?串在串處理中可作為任意串的子串。9.算法設計假設以不帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾結點，但不設頭指針。試設計相應的入隊和出隊的算法?！窘獯稹砍鲫牪僮魇窃谘h(huán)鏈表的頭部進

46、行，相當于刪除開始結點，而入隊操作是在循環(huán)鏈表的尾部進行，相當于在終端結點之后插入一個結點。由于循環(huán)鏈表不帶頭結點，需要處理空表的特殊情況。入隊算法如下：循環(huán)隊列入既毎法Enqueue ,template void Enqueue CNodc T x)if (reai-IULU 對處理空寰的特殊轄況rearnext=s;)else“處理際空表以外的一股倚況s-n.eKt-reaj next,rear- next=s;rear=s;出隊算法如下:彳盾環(huán)陸列出嘰算法Dequeue template T Dequeue(Node Year)(if (rear= =4IULL) throw under

47、flow, /判斷恚空 dse s=reainext,if (s=才出r) rear=-MULL;颶恚中只有一平結點else rear-neKt= nest;delete s;設順序棧S中有2n個元素，從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-1，al，要求通過一個循環(huán)隊列重新排列棧中元素，使得從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-2，a2，a2n-1，a2n-3，al，請設計算法實現(xiàn)該操作，要求空間復雜度和時間復雜度均為O(n)?！窘獯稹坎僮鞑襟E為： 將所有元素出棧并入隊； 依次將隊列元素出隊，如果是偶數(shù)結點，則再入隊，如果是奇數(shù)結點，則入棧； 將奇數(shù)結點出棧并入隊； 將偶數(shù)結點出隊并入棧；

48、 將所有元素出棧并入隊； 將所有元素出隊并入棧即為所求。用順序存儲結構存儲串 S,編寫算法刪除S中第i個字符開始的連續(xù)j個字符?！窘獯稹肯扰袛啻甋中要刪除的內(nèi)容是否存在， 若存在，則將第i+j-1之后的字符前移j個位置。算法如下:串珊慄算法Dd |void Del (charS,inlt mtj)熾怕C號單売存散審的卷廈(if &+fSOJ) for (k=i k0;i)if (Si-=ch)(for0=i+l営riFUh機一；)對串的模式匹配KMP算法設計求模式滑動位置的next函數(shù)?！窘獯稹繀⒁?25學習自測及答案1 在一個具有n個單元的順序棧中，假定以地址低端（即下標為0的單元）作為棧底，以top作為棧頂指針，當出棧時，top的變化為（）。A 不變 B top=0; C top=top-1; D top=top+1;【解答】C2一個棧的入棧序列是 a,