數(shù)據(jù)結(jié)構(gòu)c++版課后習(xí)題解析

1、第 1 章 緒 論11.1 本章導(dǎo)學(xué)11.2 習(xí)題解析2第 2 章 線性表92.1 本章導(dǎo)學(xué)92.2 習(xí)題解析10第 3 章 棧和隊列193.1 本章導(dǎo)學(xué)193.2 習(xí)題解析20第 4 章 字符串和多維數(shù)組264.1 本章導(dǎo)學(xué)264.2 習(xí)題解析27第 5 章 樹和二叉樹325.1 本章導(dǎo)學(xué)325.2 習(xí)題解析33第 6 章 圖436.1 本章導(dǎo)學(xué)436.2 習(xí)題解析44第 7 章 查找技術(shù)567.1 本章導(dǎo)學(xué)567.2 習(xí)題解析57第 8 章 排序技術(shù)678.1 本章導(dǎo)學(xué)678.2 習(xí)題解析68第 9 章 索引技術(shù)789.1 本章導(dǎo)學(xué)789.2 習(xí)題解析78第 1 章 緒 論1.1 本章導(dǎo)學(xué)

2、1. 知識結(jié)構(gòu)圖 本章的知識結(jié)構(gòu)如圖1-1所示，其中第二層的橢圓代表本章的學(xué)習(xí)主線。數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的分類存儲結(jié)構(gòu)常用存儲方法算法算法特性評價算法描述算法問題規(guī)?；菊Z句時間復(fù)雜度大O記號圖1-1 知識結(jié)構(gòu)圖緒 論數(shù)據(jù)結(jié)構(gòu)算 法基本概念邏輯結(jié)構(gòu)存儲結(jié)構(gòu)基本概念算法分析關(guān) 系2. 學(xué)習(xí)要點對本章的學(xué)習(xí)要從兩條主線出發(fā)，一條主線是數(shù)據(jù)結(jié)構(gòu)，包括數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念及含義，另一條主線是算法，包括算法的相關(guān)概念、描述方法以及時間復(fù)雜度的分析方法。在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時要抓住兩個方面：邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，并注意把握二者之間的關(guān)系。在學(xué)習(xí)算法時，要以算法的概念和特性為基本點，并在以

3、后的學(xué)習(xí)中注意提高算法設(shè)計的能力。對于算法時間性能的分析，要將注意力集中在增長率上，即基本語句執(zhí)行次數(shù)的數(shù)量級，在設(shè)計算法時，養(yǎng)成分析算法時間性能的習(xí)慣，進(jìn)而有效地改進(jìn)算法的效率。1.2 習(xí)題解析1. 填空（1）（ ）是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進(jìn)行考慮和處理。【解答】數(shù)據(jù)元素（2）（ ）是數(shù)據(jù)的最小單位，（ ）是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位。【解答】數(shù)據(jù)項，數(shù)據(jù)元素【分析】數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系。（3）從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為（ ）、（ ）、（ ）和（ ）?！窘獯稹考希€性結(jié)構(gòu)，樹結(jié)構(gòu)、圖結(jié)構(gòu)（4）數(shù)據(jù)的存儲結(jié)構(gòu)主要有（ ）和（ ）兩種

4、基本方法，不論哪種存儲結(jié)構(gòu)，都要存儲兩方面的內(nèi)容：（ ）和（ ）。【解答】順序存儲結(jié)構(gòu)，鏈接存儲結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關(guān)系（5）算法具有五個特性，分別是（ ）、（ ）、（ ）、（ ）、（ ）。【解答】有零個或多個輸入，有一個或多個輸出，有窮性，確定性，可行性（6）算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四種，其中，（ ）被稱為算法語言?！窘獯稹孔匀徽Z言，程序設(shè)計語言，流程圖，偽代碼，偽代碼（7）在一般情況下，一個算法的時間復(fù)雜度是（ ）的函數(shù)。【解答】問題規(guī)模（8）設(shè)待處理問題的規(guī)模為n，若一個算法的時間復(fù)雜度為一個常數(shù)，則表示成數(shù)量級的形式為（ ），若為2n*log25n

5、+ 8n，則表示成數(shù)量級的形式為（ ）。【解答】(1)，(nlog2n)【分析】用大O記號表示算法的時間復(fù)雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。2. 選擇題（1）順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的，鏈接存儲結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的。A 線性結(jié)構(gòu) B 非線性結(jié)構(gòu) C 存儲位置 D 指針【解答】C，D【分析】順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，其邏輯關(guān)系由存儲位置（即元素在數(shù)組中的下標(biāo)）表示；鏈接存儲結(jié)構(gòu)中一個數(shù)據(jù)元素對應(yīng)鏈表中的一個結(jié)點，元素之間的邏輯關(guān)系由結(jié)點中的指針表示。（2）假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；

6、子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承遺產(chǎn)。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（ ）。A 樹 B 圖 C 線性表 D 集合【解答】B【分析】將丈夫、妻子和子女分別作為數(shù)據(jù)元素，根據(jù)繼承關(guān)系畫出邏輯結(jié)構(gòu)圖如圖1-2丈夫妻子子女n子女1圖1-2 遺產(chǎn)繼承邏輯結(jié)構(gòu)圖所示。（3）計算機所處理的數(shù)據(jù)一般具有某種內(nèi)在聯(lián)系，這是指（ ）。A 數(shù)據(jù)和數(shù)據(jù)之間存在某種關(guān)系 B 元素和元素之間存在某種關(guān)系C 元素內(nèi)部具有某種結(jié)構(gòu) D 數(shù)據(jù)項和數(shù)據(jù)項之間存在某種關(guān)系【解答】B【分析】數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合，數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位，元素內(nèi)部各數(shù)據(jù)項一般

7、不予考慮。（4）對于數(shù)據(jù)結(jié)構(gòu)的描述，下列說法中不正確的是（ ）。A 相同的邏輯結(jié)構(gòu)對應(yīng)的存儲結(jié)構(gòu)也必相同B 數(shù)據(jù)結(jié)構(gòu)由邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和基本操作三方面組成C 對數(shù)據(jù)結(jié)構(gòu)基本操作的實現(xiàn)與存儲結(jié)構(gòu)有關(guān)D 數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的機內(nèi)實現(xiàn)【解答】A【分析】相同的邏輯結(jié)構(gòu)可以用不同的存儲結(jié)構(gòu)實現(xiàn)，一般來說，在不同的存儲結(jié)構(gòu)下基本操作的實現(xiàn)是不同的，例如線性表可以順序存儲也可以鏈接存儲，在順序存儲和鏈接存儲結(jié)構(gòu)下插入操作的實現(xiàn)截然不同。（5）可以用（ ）定義一個完整的數(shù)據(jù)結(jié)構(gòu)。A 數(shù)據(jù)元素 B 數(shù)據(jù)對象 C 數(shù)據(jù)關(guān)系 D 抽象數(shù)據(jù)類型【解答】D【分析】抽象數(shù)據(jù)類型是一個數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)

8、上的一組操作的總稱。（6）算法指的是（ ）。A 對特定問題求解步驟的一種描述，是指令的有限序列。B 計算機程序 C 解決問題的計算方法 D 數(shù)據(jù)處理【解答】A【分析】計算機程序是對算法的具體實現(xiàn)；簡單地說，算法是解決問題的方法；數(shù)據(jù)處理是通過算法完成的。所以，只有A是算法的準(zhǔn)確定義。（7）下面（ ）不是算法所必須具備的特性。A 有窮性 B 確切性 C 高效性 D 可行性【解答】C【分析】高效性是好算法應(yīng)具備的特性。（8）算法分析的目的是（ ），算法分析的兩個主要方面是（ ）。A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B 研究算法中輸入和輸出的關(guān)系C 分析算法的效率以求改進(jìn) D 分析算法的易讀性和文檔性E 空間

9、性能和時間性能 F 正確性和簡明性G 可讀性和文檔性 H 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性【解答】C，E3. 判斷題 算法的時間復(fù)雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定?！窘獯稹垮e。時間復(fù)雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級來確定。 每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本操作：插入、刪除和查找?！窘獯稹垮e。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結(jié)構(gòu)。 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系。【解答】錯。是數(shù)據(jù)之間的邏輯關(guān)系的整體。 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。【解答】對。因此邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。 基于某種邏輯結(jié)構(gòu)之上的基本操作，其實現(xiàn)是唯一的。【解答】錯。基本操作的實現(xiàn)是

10、基于某種存儲結(jié)構(gòu)設(shè)計的，因而不是唯一的。4. 分析以下各程序段，并用大O記號表示其執(zhí)行時間。 i = 1; k = 0; while (i = n) k = k + 10 * i;i+; i = 1; k = 0; do k = k + 10 * i;i+; while (i = n); y = 0; while (y + 1) *(y + 1) = n) y = y + 1; i = 1; j = 0;while (i + j j) j+; else i+; for (i = 1; i = n; i+) for (j = 1; j = i; j+) for (k = 1; k = j; k+

11、) x+;【解答】 基本語句是k=k+10*i，共執(zhí)行了n-2次，所以T(n)=O(n)。 基本語句是k=k+10*i，共執(zhí)行了n次，所以T(n)=O(n)。 分析條件語句，每循環(huán)一次，i+j 整體加1，共循環(huán)n次，所以T(n)=O(n)。 設(shè)循環(huán)體共執(zhí)行T(n)次，每循環(huán)一次，循環(huán)變量y加1，最終T(n)=y，即： (T(n)+1)2n，所以T(n)=O(n1/2)。 x+是基本語句，所以 5解答下列問題（1）設(shè)有數(shù)據(jù)結(jié)構(gòu)（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,

12、6)。試畫出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。142563圖1-3 邏輯結(jié)構(gòu)圖【解答】其邏輯結(jié)構(gòu)圖如圖1-3所示，它是一種圖結(jié)構(gòu)。（2）為整數(shù)定義一個抽象數(shù)據(jù)類型，包含整數(shù)的常見運算，每個運算對應(yīng)一個基本操作，每個基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件?！窘獯稹空麛?shù)的抽象數(shù)據(jù)類型定義如下： ADT integer Data 整數(shù)：可以是正整數(shù)(1, 2, 3, )、負(fù)整數(shù)(-1, -2, -3, )和零 Operation Constructor 前置條件：整數(shù)a不存在 輸入：一個整數(shù)b 功能：構(gòu)造一個與輸入值相同的整數(shù) 輸出：無 后置條件：整數(shù)a具有輸入的值 Set 前置條件

13、：存在一個整數(shù)a 輸入：一個整數(shù)b 功能：修改整數(shù)a的值，使之與輸入的整數(shù)值相同 輸出：無 后置條件：整數(shù)a的值發(fā)生改變 Add 前置條件：存在一個整數(shù)a 輸入：一個整數(shù)b 功能：將整數(shù)a與輸入的整數(shù)b相加 輸出：相加后的結(jié)果 后置條件：整數(shù)a的值發(fā)生改變 Sub 前置條件：存在一個整數(shù)a 輸入：一個整數(shù)b 功能：將整數(shù)a與輸入的整數(shù)b相減 輸出：相減的結(jié)果 后置條件：整數(shù)a的值發(fā)生改變 Multi 前置條件：存在一個整數(shù)a 輸入：一個整數(shù)b 功能：將整數(shù)a與輸入的整數(shù)b相乘 輸出：相乘的結(jié)果 后置條件：整數(shù)a的值發(fā)生改變 Div 前置條件：存在一個整數(shù)a 輸入：一個整數(shù)b 功能：將整數(shù)a與輸

14、入的整數(shù)b相除 輸出：若整數(shù)b為零，則拋出除零異常，否則輸出相除的結(jié)果 后置條件：整數(shù)a的值發(fā)生改變 Mod 前置條件：存在一個整數(shù)a 輸入：一個整數(shù)b 功能：求當(dāng)前整數(shù)與輸入整數(shù)的模，即正的余數(shù) 輸出：若整數(shù)b為零，則拋出除零異常，否則輸出取模的結(jié)果 后置條件：整數(shù)a的值發(fā)生改變 Equal 前置條件：存在一個整數(shù)a 輸入：一個整數(shù)b 功能：判斷整數(shù)a與輸入的整數(shù)b是否相等 輸出：若相等返回1，否則返回0 后置條件：整數(shù)a的值不發(fā)生改變endADT（3）求多項式A(x)的算法可根據(jù)下列兩個公式之一來設(shè)計： A(x)=anxn+an-1xn-1+a1x+a0 A(x)=(anx+an-1)x+

15、a1)x)+a0根據(jù)算法的時間復(fù)雜度分析比較這兩種算法的優(yōu)劣。【解答】第二種算法的時間性能要好些。第一種算法需執(zhí)行大量的乘法運算，而第二種算法進(jìn)行了優(yōu)化，減少了不必要的乘法運算。（4）選擇和評價數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)與方法是什么？【解答】首先，對給定的實際問題可以建立不同的數(shù)據(jù)結(jié)構(gòu)；其次，對于給定的數(shù)據(jù)結(jié)構(gòu)，可以選擇不同的存儲實現(xiàn)，即采用不同的存儲結(jié)構(gòu)；再次，在給定數(shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)的條件下，對同一基本操作可以設(shè)計出不同算法。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和操作（特別是基本操作）的實現(xiàn)這三者是密切相關(guān)的。一般地，在建立數(shù)據(jù)結(jié)構(gòu)時應(yīng)該考慮以下三個方面： 確定表示問題所需的數(shù)據(jù)及其特性； 確定必須支持的基

16、本操作，并度量每種操作所受的時、空資源限制，某些重要的操作，例如查找、插入和刪除的資源限制通常決定了數(shù)據(jù)結(jié)構(gòu)的選擇； 選擇（或設(shè)計）最接近這些開銷的數(shù)據(jù)結(jié)構(gòu)。6. 算法設(shè)計（要求：用偽代碼和C+描述兩種方法描述算法，并分析時間復(fù)雜度） 對一個整型數(shù)組An設(shè)計一個排序算法?！窘獯稹肯旅媸呛唵芜x擇排序算法的偽代碼描述。 1. 對n個記錄進(jìn)行n-1趟簡單選擇排序： 1.1 在無序區(qū)i，n-1中選取最小記錄，設(shè)其下標(biāo)為index； 1.2 將最小記錄與第i個記錄交換； 下面是簡單選擇排序算法的C+描述。void SelectSort(int r , int n) for (i = 0; i n - 1

17、; i+) /對n個記錄進(jìn)行n-1趟簡單選擇排序 index = i; for (j = i + 1; j n; j+) /在無序區(qū)中選取最小記錄 if (rj max，則Ai為最大值，原來的最大值為次最大值；2.2 否則，如果Ainmax，則最大值不變，Ai為次最大值；3. 輸出最大值max，次最大值nmax； 算法的C+描述如下：void Max_NextMax(int A , int n, int & max, int & nmax)if (A0 = A1) max = A0; nmax = A1;else max = A1; nmax = A0; for (i = 2; i = max

18、) nmax = max; max = Ai; else if (Ai nmax) nmax = Ai; cout最大值為：maxn次最大值為：nmaxnext=(p-next)-next 單鏈表中設(shè)置頭結(jié)點的作用是（ ）?！窘獯稹繛榱诉\算方便【分析】例如在插入和刪除操作時不必對表頭的情況進(jìn)行特殊處理。 非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點（由指針p所指）滿足（ ）?！窘獯稹縫-next=head【分析】如圖2-8所示。heada1a2an p圖2-8 尾結(jié)點p與頭指針head的關(guān)系示意圖 在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個結(jié)點s的操作序列是（ ）；刪除開始結(jié)點的

19、操作序列為（ ）?！窘獯稹縮-next =rear-next; rear-next =s; rear =s; q=rear-next-next; rear-next-next=q-next; delete q;【分析】操作示意圖如圖2-9所示：a1a2an rear sq圖2-9 帶尾指針的循環(huán)鏈表中插入和刪除操作示意圖rear 一個具有n個結(jié)點的單鏈表，在指針p所指結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為（ ）；在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為（ ）。【解答】(1)，(n)【分析】在p所指結(jié)點后插入一個新結(jié)點只需修改指針，所以時間復(fù)雜度為(1)；而在給定值為x的結(jié)點后插入一個新結(jié)點

20、需要先查找值為x的結(jié)點，所以時間復(fù)雜度為(n)。 可由一個尾指針唯一確定的鏈表有（ ）、（ ）、（ ）?！窘獯稹垦h(huán)鏈表，循環(huán)雙鏈表，雙鏈表2. 選擇題 線性表的順序存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)，線性表的鏈接存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)。A 隨機存取 B 順序存取 C 索引存取 D 散列存取【解答】A，B【分析】參見2.2.1。 線性表采用鏈接存儲時，其地址（ ）。A 必須是連續(xù)的 B 部分地址必須是連續(xù)的C 一定是不連續(xù)的 D 連續(xù)與否均可以【解答】D【分析】線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。

21、 單循環(huán)鏈表的主要優(yōu)點是（ ）。A 不再需要頭指針了 B 從表中任一結(jié)點出發(fā)都能掃描到整個鏈表；C 已知某個結(jié)點的位置后，能夠容易找到它的直接前趨；D 在進(jìn)行插入、刪除操作時，能更好地保證鏈表不斷開?！窘獯稹緽 鏈表不具有的特點是（ ）。A 可隨機訪問任一元素 B 插入、刪除不需要移動元素C 不必事先估計存儲空間 D 所需空間與線性表長度成正比【解答】A 若某線性表中最常用的操作是取第i 個元素和找第i個元素的前趨，則采用（ ）存儲方法最節(jié)省時間。A 順序表 B 單鏈表 C 雙鏈表 D 單循環(huán)鏈表【解答】A【分析】線性表中最常用的操作是取第i 個元素，所以，應(yīng)選擇隨機存取結(jié)構(gòu)即順序表，同時在順

22、序表中查找第i個元素的前趨也很方便。單鏈表和單循環(huán)鏈表既不能實現(xiàn)隨機存取，查找第i個元素的前趨也不方便，雙鏈表雖然能快速查找第i個元素的前趨，但不能實現(xiàn)隨機存取。 若鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除第一個結(jié)點，則采用（ ）存儲方法最節(jié)省時間。A 單鏈表 B 帶頭指針的單循環(huán)鏈表 C 雙鏈表 D 帶尾指針的單循環(huán)鏈表【解答】D【分析】在鏈表中的最后一個結(jié)點之后插入一個結(jié)點需要知道終端結(jié)點的地址，所以，單鏈表、帶頭指針的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第一個結(jié)點，其時間性能是O(1)，所以，答案是D 。 若鏈表中最常用的操作是在最后一個結(jié)點之后插

23、入一個結(jié)點和刪除最后一個結(jié)點，則采用（ ）存儲方法最節(jié)省運算時間。A 單鏈表 B 循環(huán)雙鏈表 C單循環(huán)鏈表 D 帶尾指針的單循環(huán)鏈表【解答】B【分析】在鏈表中的最后一個結(jié)點之后插入一個結(jié)點需要知道終端結(jié)點的地址，所以，單鏈表、單循環(huán)鏈表都不合適，刪除最后一個結(jié)點需要知道終端結(jié)點的前驅(qū)結(jié)點的地址，所以，帶尾指針的單循環(huán)鏈表不合適，而循環(huán)雙鏈表滿足條件。 在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是（ ）。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】B【分析】首先應(yīng)順序查找新結(jié)點在單鏈表中的位置。 對于n個元素組成的線性表，建立一個有序單鏈表的時

24、間復(fù)雜度是（ ）。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【分析】在鏈表中一般只能進(jìn)行順序查找，所以，雙鏈表并不能提高查找速度，因為雙鏈表中有兩個指針域，顯然不能節(jié)約存儲空間，對于動態(tài)存儲分配，回收存儲空間的速度是一樣的。由于雙鏈表具有對稱性，所以，其插入和刪除操作更加方便。 在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的直接前驅(qū)，若在q和p之間插入

25、s所指結(jié)點，則執(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之間插入新結(jié)點，所以，不用考慮修改指針的順序。 在循環(huán)雙鏈表的p所指結(jié)點后插入s所指結(jié)點的操作是（ ）。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

26、; 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【分析】在鏈表中，對指針的修改必須保持線性表的邏輯關(guān)系，否則，將違背線性表的邏輯特征，圖2-10給出備選答案C和D的圖解。(a) 備選答案C操作示意圖(第4步指針修改無法進(jìn)行) (b) 備選答案D操作示意圖 圖2-10 雙鏈表插入操作修改指針操作示意圖sai-1aixpsai-1aixp（13）用數(shù)組r存儲靜態(tài)鏈表，結(jié)點的next域指向后繼，工作指針j指向鏈中某結(jié)點，則j后移的操作語句為（ ）。A

27、j = rj.next B j = j + 1 C j = j-next D j = rj- next【解答】A【分析】注意next是數(shù)組下標(biāo)，因此排除C和D，對于備選答案B，假設(shè)工作指針j指向某結(jié)點p，則j+1不一定指向結(jié)點p的后繼結(jié)點。（14）設(shè)線性表有n個元素，以下操作中，（ ）在順序表上實現(xiàn)比在鏈表上實現(xiàn)的效率更高。A 輸出第i（1in）個元素值 B 交換第1個和第2個元素的值C 順序輸出所有n個元素 D 查找與給定值x相等的元素在線性表中的序號【解答】A【分析】在順序表上輸出第i（1in）個元素值需要O(1)時間，在鏈表上輸出第i（1in）個元素值需要O(n)時間；在順序表上和鏈表上

28、交換第1個和第2個元素的值都需要O(1)時間；在順序表上和鏈表上順序輸出所有n個元素都需要O(n)時間；在順序表上和鏈表上查找與給定值x相等的元素都需要進(jìn)行順序查找，需要O(n)時間。3. 判斷題 線性表的邏輯順序和存儲順序總是一致的?！窘獯稹垮e。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序和存儲順序不一定一致。 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈接存儲結(jié)構(gòu)?！窘獯稹垮e。兩種存儲結(jié)構(gòu)各有優(yōu)缺點。 設(shè)p，q是指針，若p=q，則*p=*q?！窘獯稹垮e。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相同。 線性結(jié)構(gòu)的基本特征是：每個元素有且僅有一個直接前驅(qū)和一個直接后繼?！窘獯稹垮e。每個元素最多

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

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

31、擴充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。而順序表的插入、刪除的效率低，故不合適。5算法設(shè)計 設(shè)計一個時間復(fù)雜度為(n)的算法，實現(xiàn)將數(shù)組An中所有元素循環(huán)左移k個位置?！窘獯稹克惴ㄋ枷胝垍⒁娭鹘滩牡谝徽滤枷牖鸹?。下面給出具體算法。void Converse(int A , int n, int k) Reverse(A, 0, k-1); Reverse(A, k, n-1); Reverse(A, 0, n-1);void Reverse(int A , int from, int to) /將數(shù)組A中元素從from到to逆置 for (i = 0; i (to from + 1)/2;

32、 i+)Afrom + iAto - i; /交換元素 循環(huán)左移算法Converse 分析算法，第一次調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(k)，第二次調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(n-k)，第三次調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(n)，所以，總的時間復(fù)雜度為O(n)。 已知數(shù)組An中的元素為整型，設(shè)計算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時間復(fù)雜度為(n)。【解答】從數(shù)組的兩端向中間比較，設(shè)置兩個變量i和j，初始時i=0，j=n-1，若Ai為偶數(shù)并且Aj為奇數(shù)，則將Ai與Aj交換。具體算法如下： void Adjust(int A ,

33、 n) i = 0; j = n - 1; while (i j) while (Ai % 2 != 0) i+; while (Aj % 2 = 0) j- if (i j) AiAj; 數(shù)組奇偶調(diào)整算法Adjust 分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時間復(fù)雜度為(n)。 試編寫在無頭結(jié)點的單鏈表上實現(xiàn)線性表的插入操作的算法，并和帶頭結(jié)點的單鏈表上的插入操作的實現(xiàn)進(jìn)行比較?！窘獯稹繀⒁?.2.3。 試分別以順序表和單鏈表作存儲結(jié)構(gòu)，各寫一實現(xiàn)線性表就地逆置的算法?！窘獯稹宽樞虮淼哪嬷茫词菍ΨQ元素交換，設(shè)順序表的長度為length，則將表中第i個元素與第length-i-1個元素相交

34、換。具體算法如下： template void Reverse(T data , int length) for (i = 0; i = length/2; i+) temp = datai; datai = datalength i - 1; datalength i - 1 = temp;順序表逆置算法Reverse單鏈表的逆置請參見2.2.4算法2-4和算法2-6。 假設(shè)在長度大于1的循環(huán)鏈表中，即無頭結(jié)點也無頭指針，s為指向鏈表中某個結(jié)點的指針，試編寫算法刪除結(jié)點s的前趨結(jié)點?！窘獯稹坷脝窝h(huán)鏈表的特點，通過指針s可找到其前驅(qū)結(jié)點r以及r的前驅(qū)結(jié)點p，然后將結(jié)點r刪除，如圖2-11所

35、示，具體算法如下：template void Del(Node *s) p = s; /工作指針p初始化，查找s的前驅(qū)結(jié)點的前驅(qū)結(jié)點，用p指示 while (p-next-next != s) p = p-next; r = p-next; /r為p的前驅(qū)結(jié)點，q為r的前驅(qū)結(jié)點 p-next = s; /刪除r所指結(jié)點 delete r; 循環(huán)鏈表刪除算法Dela1a2an 圖2-11 刪除結(jié)點s的前驅(qū)結(jié)點操作示意圖a3a4spr 已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個循環(huán)鏈表，使每個循環(huán)鏈表中只含同一類字符。【解答】在單鏈表A中依次取元素，若取出的元

36、素是字母，把它插入到字母鏈表B 中，若取出的元素是數(shù)字，則把它插入到數(shù)字鏈表D中，直到鏈表的尾部，這樣表B，D，A中分別存放字母、數(shù)字和其他字符。具體算法如下：template void Adjust(Node *A, Node *D, Node *B) D = new Node; D-next = D; /創(chuàng)建空循環(huán)鏈表D，存放數(shù)字 B = new Node; B-next = B; /創(chuàng)建空循環(huán)鏈表B，存放字符 p = A; q = p-next; /工作指針q初始化 while (q != NULL) if (Adata)&(q-data=Z)|(a data)&(q-data=z) p

37、-next = q-next; q-next = B-next; B-next = q; /采用頭插法插在循環(huán)鏈表B的頭結(jié)點的后面 else if (0data)&(q-data=9) p-next = q-next; q-next = D-next; D-next = q; /采用頭插法插在循環(huán)鏈表D的頭結(jié)點的后面 else p = q; q = p-next;p-next = A; R = A; /將鏈表A構(gòu)造為循環(huán)鏈表，為除字母和數(shù)字的其他字符單鏈表拆分算法Adjust 設(shè)單鏈表以非遞減有序排列，設(shè)計算法實現(xiàn)在單鏈表中刪去值相同的多余結(jié)點?！窘獯稹繌念^到尾掃描單鏈表，若當(dāng)前結(jié)點的元素值與

38、后繼結(jié)點的元素值不相等，則指針后移；否則刪除該后繼結(jié)點。具體算法如下：void Purge(Node *first) p = first-next; while (p-next != NULL) if (p-data = p-next-data) q = p-next; p-next = q-next; delete q; else p = p-next; 單鏈表刪除相同值算法Purge 判斷帶頭結(jié)點的雙循環(huán)鏈表是否對稱?！窘獯稹吭O(shè)工作指針p和q分別指向循環(huán)雙鏈表的開始結(jié)點和終端結(jié)點，若結(jié)點p和結(jié)點q的數(shù)據(jù)域相等，則工作指針p后移，工作指針q前移，直到指針p和指針q指向同一結(jié)點（循環(huán)雙鏈表中結(jié)

39、點個數(shù)為奇數(shù)），或結(jié)點q成為結(jié)點p的前驅(qū)（循環(huán)雙鏈表中結(jié)點個數(shù)為偶數(shù)）。如圖2-12所示。a1an-1anfirstpq圖2-12 判斷循環(huán)雙鏈表對稱的操作示意圖template struct DulNode T data; DulNode *prior, *next;template bool Equal (DulNode *first) p = first-next; q = first-prior; while (p != q & p-prior != q) if (p-data = q-data) p = p-next; /工作指針p后移 q = q-prior; /工作指針q前移 e

40、lse return 0; return 1; 判斷雙鏈表對稱算法Equal 第 3 章 棧和隊列3.1 本章導(dǎo)學(xué)1. 知識結(jié)構(gòu)圖 本章的知識結(jié)構(gòu)如圖3-1所示，其中第二層的橢圓表示本章的學(xué)習(xí)主線。特殊線性表 棧隊 列棧的定義操作特性ADT定義隊列定義操作特性ADT定義順序棧鏈棧循環(huán)隊列鏈隊列邏輯結(jié)構(gòu)存儲結(jié)構(gòu)邏輯結(jié)構(gòu)存儲結(jié)構(gòu)比 較圖3-1 知識結(jié)構(gòu)圖比較比較基本操作的實現(xiàn)時間性能基本操作的實現(xiàn)時間性能2. 學(xué)習(xí)要點對于本章的學(xué)習(xí)要從兩條主線出發(fā)，一條主線是棧，另一條主線是隊列，要以棧和隊列的操作特性為切入點，并注意將棧和隊列進(jìn)行對比。這部分有較多的經(jīng)典應(yīng)用，如漢諾塔問題、迷宮問題、八皇后問題、

41、車廂重排問題、開關(guān)盒布線、舞伴問題等等。要有意識地接觸這些經(jīng)典問題，深刻理解棧和隊列在程序設(shè)計中的重要作用，在實踐中培養(yǎng)數(shù)據(jù)結(jié)構(gòu)應(yīng)用能力和算法設(shè)計能力。 3.2 習(xí)題解析1. 填空 設(shè)有一個空棧，棧頂指針為1000H，每個元素需要1個單位的存儲空間，則執(zhí)行push、push、pop、push、pop、push、push后，棧頂指針為（ ）?！窘獯稹?003H 棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是（ ）；其判定?？盏臈l件分別是（ ），判定棧滿的條件分別是（ ）。【解答】順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)（或順序棧和鏈棧），棧頂指針top= -1和top=NULL，棧頂指針top等于數(shù)組的長度和內(nèi)存無可用空間（

42、 ）可作為實現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。【解答】?！痉治觥窟f歸函數(shù)的調(diào)用和返回正好符合后進(jìn)先出性。 表達(dá)式a*(b+c)-d的后綴表達(dá)式是（ ）?！窘獯稹縜bc+*d-【分析】將中綴表達(dá)式變?yōu)楹缶Y表達(dá)式有一個技巧：將操作數(shù)依次寫下來，再將算符插在它的兩個操作數(shù)的后面。 棧和隊列是兩種特殊的線性表，棧的操作特性是（ ），隊列的操作特性是（ ），棧和隊列的主要區(qū)別在于（ ）?！窘獯稹亢筮M(jìn)先出，先進(jìn)先出，對插入和刪除操作限定的位置不同 循環(huán)隊列的引入是為了克服（ ）。【解答】假溢出 數(shù)組Qn用來表示一個循環(huán)隊列，front為隊頭元素的前一個位置，rear為隊尾元素的位置，計算隊列中元素個數(shù)的公式為

43、（ ）?！窘獯稹浚╮ear-front+n）% n【分析】也可以是（rear-front）% n，但rear-front的結(jié)果可能是負(fù)整數(shù)，而對一個負(fù)整數(shù)求模，其結(jié)果在不同的編譯器環(huán)境下可能會有所不同。 用循環(huán)鏈表表示的隊列長度為n，若只設(shè)頭指針，則出隊和入隊的時間復(fù)雜度分別是（ ）和（ ）。【解答】(1)，(n)【分析】在帶頭指針的循環(huán)鏈表中，出隊即是刪除開始結(jié)點，這只需修改相應(yīng)指針；入隊即是在終端結(jié)點的后面插入一個結(jié)點，這需要從頭指針開始查找終端結(jié)點的地址。2. 選擇題（1）一個棧的入棧序列是1、2、3、4、5，則棧的不可能的輸出序列是（ ）。A 54321 B 45321 C 43512 D 12345 【解答】C【分析】此題有一個技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序號）的兩個元素。（2）若一個棧的輸入序列是1，2，3，n，輸出序列的第一個元素是n，則第i個輸出元素是（ ）。A 不確定 B n-i C n-i-1 D n-i+1【解答】D【分析】此時，輸出序列一定是輸入序列的逆序。（3）若一個棧的輸入序列是1，2，3，n，其輸出序列是p1, p2, , pn，若p1=3，則p2的值（ ）。A 一定是2 B 一定是1 C 不可能是1 D 以上都不對【解答】C【分析】由于p1=