數(shù)據(jù)結(jié)構(gòu)第二版課后習(xí)題答案王紅梅主編(已修改)

　

【正文】 第 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)主要分為（ ）、（ ）、（ ）和（ ）。 【解答】集合，線性結(jié)構(gòu)，樹結(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è)輸出，有窮性，確定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四種，其中，（ ）被稱為算法語(yǔ)言。 【解答】自然語(yǔ)言，程序設(shè)計(jì)語(yǔ)言，流程圖，偽代碼，偽代碼 ⑺ 在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是（ ）的函數(shù)。 【解答】問題規(guī)模 ⑻ 設(shè)待處理問題的規(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 線性結(jié)構(gòu) B 非線性結(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 樹 B 圖 C 線性表 D 集合 【解答】B 【分析】將丈夫、妻子和子女分別作為數(shù)據(jù)元素，根據(jù)題意畫出邏輯結(jié)構(gòu)圖。 ⑶ 算法指的是（ ）。 A 對(duì)特定問題求解步驟的一種描述，是指令的有限序列。 B 計(jì)算機(jī)程序 C 解決問題的計(jì)算方法 D 數(shù)據(jù)處理 【解答】A 【分析】計(jì)算機(jī)程序是對(duì)算法的具體實(shí)現(xiàn)；簡(jiǎn)單地說，算法是解決問題的方法；數(shù)據(jù)處理是通過算法完成的。所以，只有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ù)雜度都要通過算法中的基本語(yǔ)句的執(zhí)行次數(shù)來確定。 【解答】錯(cuò)。時(shí)間復(fù)雜度要通過算法中基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)來確定。 ⑵ 每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本操作：插入、刪除和查找。 【解答】錯(cuò)。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(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)容和形式無關(guān)。 【解答】對(duì)。因此邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。 ⑸ 基于某種邏輯結(jié)構(gòu)之上的基本操作，其實(shí)現(xiàn)是唯一的。 【解答】錯(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(n 1/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)}。試畫出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。 【解答】其邏輯結(jié)構(gòu)圖如圖13所示，它是一種圖結(jié)構(gòu)。 6. 為整數(shù)定義一個(gè)抽象數(shù)據(jù)類型，包含整數(shù)的常見運(yùn)算，每個(gè)運(yùn)算對(duì)應(yīng)一個(gè)基本操作，每個(gè)基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件。 【解答】整數(shù)的抽象數(shù)據(jù)類型定義如下： 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ù) 輸出：無 后置條件：整數(shù)a具有輸入的值 Set 前置條件：存在一個(gè)整數(shù)a 輸入：一個(gè)整數(shù)b 功能：修改整數(shù)a的值，使之與輸入的整數(shù)值相同 輸出：無 后置條件：整數(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è)公式之一來設(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]中元素的最大值和次最大值。 【解答】算法的偽代碼描述如下： 算法的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ì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，用指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。 2. 算法在發(fā)生非法操作時(shí)可以作出處理的特性稱為（ ）。 【解答】健壯性 3. 常見的算法時(shí)間復(fù)雜度用大Ｏ記號(hào)表示為：常數(shù)階( )、對(duì)數(shù)階( )、線性階 ( )、平方階( )和指數(shù)階( )。 【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n) 4．將下列函數(shù)按它們?cè)趎 時(shí)的無窮大階數(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ù)類型的概念與程序設(shè)計(jì)語(yǔ)言中數(shù)據(jù)類型概念的區(qū)別。 【解答】數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。而抽象數(shù)據(jù)類型是指一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作。程序設(shè)計(jì)語(yǔ)言中的數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上一組操作的總稱。抽象數(shù)據(jù)類型可以看成是對(duì)數(shù)據(jù)類型的一種抽象。 6. 對(duì)下列用二元組表示的數(shù)據(jù)結(jié)構(gòu),試分別畫出對(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)所示；⑵ 屬于線性結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖14(b)所示；⑶ 屬于樹結(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 章 線性表 課后習(xí)題講解 1. 填空 ⑴ 在順序表中，等概率情況下，插入和刪除一個(gè)元素平均需移動(dòng)（ ）個(gè)元素，具體移動(dòng)元素的個(gè)數(shù)與（ ）和（ ）有關(guān)。 【解答】表長(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所指）滿足（ ）。 【解答】pnext=head 【分析】如圖28所示。 ⑹ 在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個(gè)結(jié)點(diǎn)s的操作序列是（ ）；刪除開始結(jié)點(diǎn)的操作序列為（ ）。 【解答】snext =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. 選擇題 ⑴ 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（ ）的存儲(chǔ)結(jié)構(gòu)，線性表的鏈接存儲(chǔ)結(jié)構(gòu)是一種（ ）的存儲(chǔ)結(jié)構(gòu)。 A 隨機(jī)存取 B 順序存取 C 索引存取 D 散列存取 【解答】A，B 【分析】。 ⑵ 線性表采用鏈接存儲(chǔ)時(shí)，其地址（ ）。 A 必須是連續(xù)的 B 部分地址必須是連續(xù)的 C 一定是不連續(xù)的 D 連續(xù)與否均可以 【解答】D 【分析】線性表的鏈接存儲(chǔ)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(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í)，能更好地保證鏈表不斷開。 【解答】B ⑷ 鏈表不具有的特點(diǎn)是（ ）。 A 可隨機(jī)訪問任一元素 B 插入、刪除不需要移動(dòng)元素 C 不必事先估計(jì)存儲(chǔ)空間 D 所需空間與線性表長(zhǎng)度成正比 【解答】A