【正文】 課后答案網(wǎng)第 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)，樹(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è)輸出，有窮性，確定性，可行性⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四種，其中，（ ）被稱為算法語(yǔ)言。【解答】自然語(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 線性結(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 樹(shù) B 圖 C 線性表 D 集合【解答】B【分析】將丈夫、妻子和子女分別作為數(shù)據(jù)元素，根據(jù)題意畫出邏輯結(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，E3. 判斷題⑴ 算法的時(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è)基本操作：插入、刪除和查找?！窘獯稹垮e(cuò)。如數(shù)組就沒(méi)有插入和刪除操作。此題注意是每種數(shù)據(jù)結(jié)構(gòu)。⑶ 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系?！窘獯稹垮e(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)是唯一的。【解答】錯(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)?！窘獯稹科溥壿嫿Y(jié)構(gòu)圖如圖 13 所示，它是一種圖結(jié)構(gòu)。6. 為整數(shù)定義一個(gè)抽象數(shù)據(jù)類型，包含整數(shù)的常見(jiàn)運(yùn)算，每個(gè)運(yùn)算對(duì)應(yīng)一個(gè)基本操作，每個(gè)基本操作的接 口需定義前置條件、輸入、功能、輸出和后置條件?！窘獯稹空麛?shù)的抽象數(shù)據(jù)類型定義如下：ADT integerData整數(shù) a：可以是正整數(shù)(1, 2, 3, … )、負(fù)整數(shù)(1, 2, 3, …)和零OperationConstructor 前置條件：整數(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ā)生改變endADT7. 求多項(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)劣?！窘獯稹康诙N算法的時(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í)可以作出處理的特性稱為（ ）?！窘獯稹拷研?. 常見(jiàn)的算法時(shí)間復(fù)雜度用大Ｏ記號(hào)表示為：常數(shù)階( )、對(duì)數(shù)階( )、線性階 ( )、平方階( )和指數(shù)階( )。【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)4．將下列函數(shù)按它們?cè)?n 時(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ù)類型的概念與程序設(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)所示；⑶ 屬于樹(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 章 線性表課后習(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)），則需修改指針的操 作為（ ）?！窘獯稹縫next=(pnext)next⑷ 單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（ ）?！窘獯稹繛榱诉\(yùn)算方便【分析】例如在插入和刪除操作時(shí)不必對(duì)表頭的情況進(jìn)行特殊處理。⑸ 非空的單循環(huán)鏈表由頭指針 head 指示，則其尾結(jié)點(diǎn)（由指針 p 所指）滿足（ ）?！窘獯稹縫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?！痉治觥坎僮魇疽鈭D如圖 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è)尾指針唯一確定的鏈表有（ ）、（ ）、（ ）?！窘獯稹垦h(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【分析】參見(jiàn) 。⑵ 線性表采用鏈接存儲(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í)，能更好地保證鏈表不斷開(kāi)?！窘獯稹緽⑷ 鏈表不具有的特點(diǎn)是（ ）。A 可隨機(jī)訪問(wèn)任一元素 B 插入、刪除不