【正文】 第 1 章 緒 論 課后習(xí)題講解 1. 填空⑴（ ）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。【解答】數(shù)據(jù)元素 ⑵（ ）是數(shù)據(jù)的最小單位，（ ）是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位。【解答】數(shù)據(jù)項(xiàng)，數(shù)據(jù)元素【分析】數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系。 ⑶ 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為（ ）、（ ）、（ ）和（ ）?！窘獯稹考希€(xiàn)性結(jié)構(gòu)，樹(shù)結(jié)構(gòu)，圖結(jié)構(gòu) ⑷ 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有（ ）和（ ）兩種基本方法，不論哪種存儲(chǔ)結(jié)構(gòu)，都要存儲(chǔ)兩方面的內(nèi)容：（ ）和（ ）?！窘獯稹宽樞虼鎯?chǔ)結(jié)構(gòu)，鏈接存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關(guān)系 ⑸ 算法具有五個(gè)特性，分別是（ ）、（ ）、（ ）、（ ）、（ ）?！窘獯稹坑辛銈€(gè)或多個(gè)輸入，有一個(gè)或多個(gè)輸出，有窮性，確定性，可行性⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四種，其中，（ ）被稱(chēng)為算法語(yǔ)言?！窘獯稹孔匀徽Z(yǔ)言，程序設(shè)計(jì)語(yǔ)言，流程圖，偽代碼，偽代碼 ⑺ 在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是（ ）的函數(shù)。【解答】問(wèn)題規(guī)模 ⑻ 設(shè)待處理問(wèn)題的規(guī)模為n，若一個(gè)算法的時(shí)間復(fù)雜度為一個(gè)常數(shù)，則表示成數(shù)量級(jí)的形式為（ ），若為n*log25n，則表示成數(shù)量級(jí)的形式為（ ）?！窘獯稹喀?1)，Ο(nlog2n) 【分析】用大O記號(hào)表示算法的時(shí)間復(fù)雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。2. 選擇題 ⑴ 順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的，鏈接存儲(chǔ)結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的。A 線(xiàn)性結(jié)構(gòu) B 非線(xiàn)性結(jié)構(gòu) C 存儲(chǔ)位置 D 指針【解答】C，D 【分析】順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，其邏輯關(guān)系由存儲(chǔ)位置（即元素在數(shù)組中的下標(biāo)）表示；鏈接存儲(chǔ)結(jié)構(gòu)中一個(gè)數(shù)據(jù)元素對(duì)應(yīng)鏈表中的一個(gè)結(jié)點(diǎn)，元素之間的邏輯關(guān)系由結(jié)點(diǎn)中的指針表示。⑵ 假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（ ）。A 樹(shù) B 圖 C 線(xiàn)性表 D 集合【解答】B【分析】將丈夫、妻子和子女分別作為數(shù)據(jù)元素，根據(jù)題意畫(huà)出邏輯結(jié)構(gòu)圖。⑶ 算法指的是（ ）。A 對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。B 計(jì)算機(jī)程序 C 解決問(wèn)題的計(jì)算方法 D 數(shù)據(jù)處理【解答】A【分析】計(jì)算機(jī)程序是對(duì)算法的具體實(shí)現(xiàn)；簡(jiǎn)單地說(shuō)，算法是解決問(wèn)題的方法；數(shù)據(jù)處理是通過(guò)算法完成的。所以，只有A是算法的準(zhǔn)確定義。⑷ 下面（ ）不是算法所必須具備的特性。A 有窮性 B 確切性 C 高效性 D 可行性【解答】C 【分析】高效性是好算法應(yīng)具備的特性。 ⑸ 算法分析的目的是（ ），算法分析的兩個(gè)主要方面是（ ）。A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B 研究算法中輸入和輸出的關(guān)系C 分析算法的效率以求改進(jìn) D 分析算法的易讀性和文檔性 E 空間性能和時(shí)間性能 F 正確性和簡(jiǎn)明性 G 可讀性和文檔性 H 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性【解答】C，E 3. 判斷題⑴ 算法的時(shí)間復(fù)雜度都要通過(guò)算法中的基本語(yǔ)句的執(zhí)行次數(shù)來(lái)確定?！窘獯稹垮e(cuò)。時(shí)間復(fù)雜度要通過(guò)算法中基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)來(lái)確定。⑵ 每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本操作：插入、刪除和查找。【解答】錯(cuò)。如數(shù)組就沒(méi)有插入和刪除操作。此題注意是每種數(shù)據(jù)結(jié)構(gòu)。 ⑶ 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系。【解答】錯(cuò)。是數(shù)據(jù)之間的邏輯關(guān)系的整體。 ⑷ 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。【解答】對(duì)。因此邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。⑸ 基于某種邏輯結(jié)構(gòu)之上的基本操作，其實(shí)現(xiàn)是唯一的?！窘獯稹垮e(cuò)?；静僮鞯膶?shí)現(xiàn)是基于某種存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)的，因而不是唯一的。4. 分析以下各程序段，并用大O記號(hào)表示其執(zhí)行時(shí)間。 　　　 【解答】⑴ 基本語(yǔ)句是k=k+10*i，共執(zhí)行了n2次，所以T(n)=O(n)。 ⑵ 基本語(yǔ)句是k=k+10*i，共執(zhí)行了n次，所以T(n)=O(n)。 ⑶ 分析條件語(yǔ)句，每循環(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)2≤n，所以T(n)=O(n1/2)。 ⑸ x++是基本語(yǔ)句，所以 5．設(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,6)}。試畫(huà)出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。【解答】其邏輯結(jié)構(gòu)圖如圖13所示，它是一種圖結(jié)構(gòu)。6. 為整數(shù)定義一個(gè)抽象數(shù)據(jù)類(lèi)型，包含整數(shù)的常見(jiàn)運(yùn)算，每個(gè)運(yùn)算對(duì)應(yīng)一個(gè)基本操作，每個(gè)基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件?！窘獯稹空麛?shù)的抽象數(shù)據(jù)類(lèi)型定義如下： ADT integer Data 整數(shù)a：可以是正整數(shù)(1, 2, 3, … )、負(fù)整數(shù)(1, 2, 3, …)和零Operation Constructor 前置條件：整數(shù)a不存在 輸入：一個(gè)整數(shù)b 功能：構(gòu)造一個(gè)與輸入值相同的整數(shù)輸出：無(wú) 后置條件：整數(shù)a具有輸入的值 Set前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b 功能：修改整數(shù)a的值，使之與輸入的整數(shù)值相同 輸出：無(wú) 后置條件：整數(shù)a的值發(fā)生改變 Add 前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b 功能：將整數(shù)a與輸入的整數(shù)b相加 輸出：相加后的結(jié)果 后置條件：整數(shù)a的值發(fā)生改變 Sub 前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b 功能：將整數(shù)a與輸入的整數(shù)b相減 輸出：相減的結(jié)果 后置條件：整數(shù)a的值發(fā)生改變 Multi 前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b 功能：將整數(shù)a與輸入的整數(shù)b相乘 輸出：相乘的結(jié)果 后置條件：整數(shù)a的值發(fā)生改變Div 前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b 功能：將整數(shù)a與輸入的整數(shù)b相除 輸出：若整數(shù)b為零，則拋出除零異常，否則輸出相除的結(jié)果 后置條件：整數(shù)a的值發(fā)生改變 Mod 前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b 功能：求當(dāng)前整數(shù)與輸入整數(shù)的模，即正的余數(shù)輸出：若整數(shù)b為零，則拋出除零異常，否則輸出取模的結(jié)果 后置條件：整數(shù)a的值發(fā)生改變 Equal 前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b 功能：判斷整數(shù)a與輸入的整數(shù)b是否相等 輸出：若相等返回1，否則返回0 后置條件：整數(shù)a的值不發(fā)生改變 endADT 7. 求多項(xiàng)式A(x)的算法可根據(jù)下列兩個(gè)公式之一來(lái)設(shè)計(jì)： ⑴ A(x)=anxn+an1xn1+…+a1x+a0 ⑵ A(x)=(…(anx+an1)x+…+a1)x)+a0 根據(jù)算法的時(shí)間復(fù)雜度分析比較這兩種算法的優(yōu)劣。【解答】第二種算法的時(shí)間性能要好些。第一種算法需執(zhí)行大量的乘法運(yùn)算，而第二種算法進(jìn)行了優(yōu)化，減少了不必要的乘法運(yùn)算。8. 算法設(shè)計(jì)（要求：算法用偽代碼和C++描述，并分析最壞情況下的時(shí)間復(fù)雜度）⑴ 對(duì)一個(gè)整型數(shù)組A[n]設(shè)計(jì)一個(gè)排序算法?！窘獯稹肯旅媸呛?jiǎn)單選擇排序算法的偽代碼描述。 下面是簡(jiǎn)單選擇排序算法的C++描述。 分析算法，有兩層嵌套的for循環(huán)，所以， 。⑵ 找出整型數(shù)組A[n]中元素的最大值和次最大值?！窘獯稹克惴ǖ膫未a描述如下：算法的C++描述如下：分析算法，只有一層循環(huán)，共執(zhí)行n2次，所以，T(n)=O(n)。學(xué)習(xí)自測(cè)及答案 1．順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是（ ），鏈接存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是（ ）?！窘獯稹坑迷卦诖鎯?chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，用指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。 2. 算法在發(fā)生非法操作時(shí)可以作出處理的特性稱(chēng)為（ ）。【解答】健壯性 3. 常見(jiàn)的算法時(shí)間復(fù)雜度用大Ｏ記號(hào)表示為：常數(shù)階( )、對(duì)數(shù)階( )、線(xiàn)性階 ( )、平方階( )和指數(shù)階( )?！窘獯稹浚?1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n) 4．將下列函數(shù)按它們?cè)趎 時(shí)的無(wú)窮大階數(shù)，從小到大排列。n, nn3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n 【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, nn3+7n5, 2n/2, (3/2)n, n! 5．試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類(lèi)型的概念與程序設(shè)計(jì)語(yǔ)言中數(shù)據(jù)類(lèi)型概念的區(qū)別。【解答】數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。而抽象數(shù)據(jù)類(lèi)型是指一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作。程序設(shè)計(jì)語(yǔ)言中的數(shù)據(jù)類(lèi)型是一個(gè)值的集合和定義在這個(gè)值集上一組操作的總稱(chēng)。抽象數(shù)據(jù)類(lèi)型可以看成是對(duì)數(shù)據(jù)類(lèi)型的一種抽象。6. 對(duì)下列用二元組表示的數(shù)據(jù)結(jié)構(gòu),試分別畫(huà)出對(duì)應(yīng)的邏輯結(jié)構(gòu)圖，并指出屬于何種結(jié)構(gòu)。 ⑴ A=(D，R)， 其中D={a1, a2, a3, a4}，R={ } ⑵ B=(D，R)， 其中D={a, b, c, d, e, f}，R={,} ⑶ C=( D，R)，其中D={a，b，c，d，e，f}，R={,,} ⑷ D=(D，R)， 其中D={1, 2, 3, 4, 5, 6}，R={(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6)} 【解答】⑴ 屬于集合，其邏輯結(jié)構(gòu)圖如圖14(a)所示；⑵ 屬于線(xiàn)性結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖14(b)所示；⑶ 屬于樹(shù)結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖14(c)所示；⑷ 屬于圖結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖14(d)所示。 7. 求下列算法的時(shí)間復(fù)雜度。count=0。 x=1。while (x {x*=2。count++。}return count?！窘獯稹浚?log2n)第 2 章 線(xiàn)性表 課后習(xí)題講解 1. 填空⑴ 在順序表中，等概率情況下，插入和刪除一個(gè)元素平均需移動(dòng)（ ）個(gè)元素，具體移動(dòng)元素的個(gè)數(shù)與（ ）和（ ）有關(guān)?！窘獯稹勘黹L(zhǎng)的一半，表長(zhǎng)，該元素在表中的位置⑵ 順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的存儲(chǔ)地址是（ ）。【解答】108【分析】第5個(gè)元素的存儲(chǔ)地址=第1個(gè)元素的存儲(chǔ)地址＋(5－1)2=108⑶ 設(shè)單鏈表中指針p 指向結(jié)點(diǎn)A，若要?jiǎng)h除A的后繼結(jié)點(diǎn)（假設(shè)A存在后繼結(jié)點(diǎn)），則需修改指針的操作為（ ）。【解答】pnext=(pnext)next⑷ 單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（ ）。【解答】為了運(yùn)算方便【分析】例如在插入和刪除操作時(shí)不必對(duì)表頭的情況進(jìn)行特殊處理。⑸ 非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點(diǎn)（由指針p所指）滿(mǎn)足（ ）?！窘獯稹縫next=head【分析】如圖28所示。⑹ 在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個(gè)結(jié)點(diǎn)s的操作序列是（ ）；刪除開(kāi)始結(jié)點(diǎn)的操作序列為（ ）?！窘獯稹縮next =rearnext。 rearnext =s。 rear =s。q=rearnextnext。 rearnextnext=qnext。 delete q。【分析】操作示意圖如圖29所示：⑺ 一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在指針p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）；在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）?！窘獯稹喀?1)，Ο(n)【分析】在p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)只需修改指針，所以時(shí)間復(fù)雜度為Ο(1)；而在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)需要先查找值為x的結(jié)點(diǎn)，所以時(shí)間復(fù)雜度為Ο(n)。 ⑻ 可由一個(gè)尾指針唯一確定的鏈表有（ ）、（ ）、（ ）。【解答】循環(huán)鏈表，循環(huán)雙鏈表，雙鏈表2. 選擇題⑴ 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種（ ）的存儲(chǔ)結(jié)構(gòu)，線(xiàn)性表的鏈接存儲(chǔ)結(jié)構(gòu)是一種（ ）的存儲(chǔ)結(jié)構(gòu)。 A 隨機(jī)存取 B 順序存取 C 索引存取 D 散列存取【解答】A，B【分析】。⑵ 線(xiàn)性表采用鏈接存儲(chǔ)時(shí)，其地址（ ）。A 必須是連續(xù)的　　　　　 B 部分地址必須是連續(xù)的C 一定是不連續(xù)的　　 　 D 連續(xù)與否均可以【解答】D【分析】線(xiàn)性表的鏈接存儲(chǔ)是用一組任意的存儲(chǔ)單元存儲(chǔ)線(xiàn)性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。⑶ 單循環(huán)鏈表的主要優(yōu)點(diǎn)是（ ）。A 不再需要頭指針了 B 從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表；C 已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前趨；D 在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開(kāi)。【解答】B⑷ 鏈表不具有的特點(diǎn)是（ ）。A 可隨機(jī)訪問(wèn)任一元素 B 插入、刪除不需要移動(dòng)元素C 不必事先估計(jì)存儲(chǔ)空間 D 所需空間與線(xiàn)性表長(zhǎng)度成正比【解答】A ⑸ 若某線(xiàn)性表中最常用的操作是取第i 個(gè)元素和找第i個(gè)元素的前趨，則采用（ ）存儲(chǔ)方法最節(jié)省時(shí)間。A 順序表 B 單鏈表 C 雙鏈表 D 單循環(huán)鏈表【解答】A【分析】線(xiàn)性表中最常用的操作是取第i 個(gè)元素，所以，應(yīng)選擇隨機(jī)存取結(jié)構(gòu)即順序表，同時(shí)在順序表中查找第i個(gè)元素的前趨也很方便。單鏈表和單循環(huán)鏈表既不能實(shí)現(xiàn)隨機(jī)存取，查找第i個(gè)元素的前趨也不方便，雙鏈表雖然能快速查找第i個(gè)元素的前趨，但不能實(shí)現(xiàn)隨機(jī)存取。⑹ 若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，則采用（ ）存儲(chǔ)方法最節(jié)省時(shí)間。A 單鏈表 B 帶頭指針的單循環(huán)鏈表 C 雙鏈表 D 帶尾指針的單循環(huán)鏈表【解答】D【分析】