【正文】 課后答案網(wǎng)第 1 章 緒 論課后習(xí)題講解1. 填空⑴（ ）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理?！窘獯稹繑?shù)據(jù)元素⑵（ ）是數(shù)據(jù)的最小單位，（ ）是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(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ù)的存儲結(jié)構(gòu)主要有（ ）和（ ）兩種基本方法，不論哪種存儲結(jié)構(gòu)，都要存儲兩方面的內(nèi)容：（ ） 和（ ）?！窘獯稹宽樞虼鎯Y(jié)構(gòu)，鏈接存儲結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關(guān)系⑸ 算法具有五個特性，分別是（ ）、（ ）、（ ）、（ ）、（ ）?！窘獯稹坑辛銈€或多個輸入，有一個或多個輸出，有窮性，確定性，可行性⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四種，其中，（ ）被稱為算法語言?！窘獯稹孔匀徽Z言，程序設(shè)計(jì)語言，流程圖，偽代碼，偽代碼⑺ 在一般情況下，一個算法的時間復(fù)雜度是（ ）的函數(shù)?！窘獯稹繂栴}規(guī)模⑻ 設(shè)待處理問題的規(guī)模為 n，若一個算法的時間復(fù)雜度為一個常數(shù)，則表示成數(shù)量級的形式為（ ），若 為 n*log25n，則表示成數(shù)量級的形式為（ ）。【解答】Ο(1)，Ο(nlog2n)【分析】用大 O 記號表示算法的時間復(fù)雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。2. 選擇題⑴ 順序存儲結(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é)點(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 對特定問題求解步驟的一種描述，是指令的有限序列。B 計(jì)算機(jī)程序 C 解決問題的計(jì)算方法 D 數(shù)據(jù)處理【解答】A【分析】計(jì)算機(jī)程序是對算法的具體實(shí)現(xiàn)；簡單地說，算法是解決問題的方法；數(shù)據(jù)處理是通過算法完成 的。所以，只有 A 是算法的準(zhǔn)確定義。⑷ 下面（ ）不是算法所必須具備的特性。A 有窮性 B 確切性 C 高效性 D 可行性【解答】C【分析】高效性是好算法應(yīng)具備的特性。⑸ 算法分析的目的是（ ），算法分析的兩個主要方面是（ ）。A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B 研究算法中輸入和輸出的關(guān)系 C 分析算法的效率以求改進(jìn) D 分析算法的易讀性和文檔性 E 空間性能和時間性能 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)之上的基本操作，其實(shí)現(xiàn)是唯一的?！窘獯稹垮e?；静僮鞯膶?shí)現(xiàn)是基于某種存儲結(jié)構(gòu)設(shè)計(jì)的，因而不是唯一的。4. 分析以下各程序段，并用大 O 記號表示其執(zhí)行時間?！窘獯稹竣?基本語句是 k=k+10*i，共執(zhí)行了 n2 次，所以 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)2≤n，所以 T(n)=O(n 1/2)。⑸ x++是基本語句，所以 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ù)定義一個抽象數(shù)據(jù)類型，包含整數(shù)的常見運(yùn)算，每個運(yùn)算對應(yīng)一個基本操作，每個基本操作的接 口需定義前置條件、輸入、功能、輸出和后置條件?！窘獯稹空麛?shù)的抽象數(shù)據(jù)類型定義如下：ADT integerData整數(shù) a：可以是正整數(shù)(1, 2, 3, … )、負(fù)整數(shù)(1, 2, 3, …)和零OperationConstructor 前置條件：整數(shù) a 不存在 輸入：一個整數(shù) b 功能：構(gòu)造一個與輸入值相同的整數(shù)輸出：無后置條件：整數(shù) a 具有輸入的值Set 前置條件：存在一個整數(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 與輸入的整數(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ā)生改變endADT7. 求多項(xiàng)式 A(x)的算法可根據(jù)下列兩個公式之一來設(shè)計(jì)：⑴ A(x)=anxn+an1xn1+…+a1x+a0⑵ A(x)=(…(anx+an1)x+…+a1)x)+a0根據(jù)算法的時間復(fù)雜度分析比較這兩種算法的優(yōu)劣?！窘獯稹康诙N算法的時間性能要好些。第一種算法需執(zhí)行大量的乘法運(yùn)算，而第二種算法進(jìn)行了優(yōu)化， 減少了不必要的乘法運(yùn)算。8. 算法設(shè)計(jì)（要求：算法用偽代碼和 C++描述，并分析最壞情況下的時間復(fù)雜度）⑴ 對一個整型數(shù)組 A[n]設(shè)計(jì)一個排序算法?！窘獯稹肯旅媸呛唵芜x擇排序算法的偽代碼描述。下面是簡單選擇排序算法的 C++描述。分析算法，有兩層嵌套的 for 循環(huán)，所以， 。⑵ 找出整型數(shù)組 A[n]中元素的最大值和次最大值。【解答】算法的偽代碼描述如下：算法的 C++描述如下：分析算法，只有一層循環(huán)，共執(zhí)行 n2 次，所以，T(n)=O(n)。學(xué)習(xí)自測及答案1．順序存儲結(jié)構(gòu)的特點(diǎn)是（ ），鏈接存儲結(jié)構(gòu)的特點(diǎn)是（ ）。【解答】用元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，用指示元素存儲地址的指針表示 數(shù)據(jù)元素之間的邏輯關(guān)系。2. 算法在發(fā)生非法操作時可以作出處理的特性稱為（ ）?！窘獯稹拷研?. 常見的算法時間復(fù)雜度用大Ｏ記號表示為：常數(shù)階( )、對數(shù)階( )、線性階 ( )、平方階( )和指數(shù)階( )?！窘獯稹浚?1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)4．將下列函數(shù)按它們在 n 時的無窮大階數(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ì)語言中數(shù)據(jù)類型概念的區(qū)別?！窘獯稹繑?shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。而抽象數(shù)據(jù)類型是指一個數(shù)據(jù)結(jié)構(gòu)以及 定義在該結(jié)構(gòu)上的一組操作。程序設(shè)計(jì)語言中的數(shù)據(jù)類型是一個值的集合和定義在這個值集上一組操作的 總稱。抽象數(shù)據(jù)類型可以看成是對數(shù)據(jù)類型的一種抽象。6. 對下列用二元組表示的數(shù)據(jù)結(jié)構(gòu),試分別畫出對應(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. 求下列算法的時間復(fù)雜度。count=0。 x=1。 while (x { x*=2。 count++。}return count?！窘獯稹浚?log2n)第 2 章 線性表課后習(xí)題講解1. 填空⑴ 在順序表中，等概率情況下，插入和刪除一個元素平均需移動（ ）個元素，具體移動元素的個數(shù)與（ ） 和（ ）有關(guān)。【解答】表長的一半，表長，該元素在表中的位置⑵ 順序表中第一個元素的存儲地址是 100，每個元素的長度為 2，則第 5 個元素的存儲地址是（ ）。【解答】108【分析】第 5 個元素的存儲地址=第 1 個元素的存儲地址＋(5－1)2=108⑶ 設(shè)單鏈表中指針 p 指向結(jié)點(diǎn) A，若要刪除 A 的后繼結(jié)點(diǎn)（假設(shè) A 存在后繼結(jié)點(diǎn)），則需修改指針的操 作為（ ）。【解答】pnext=(pnext)next⑷ 單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（ ）。【解答】為了運(yùn)算方便【分析】例如在插入和刪除操作時不必對表頭的情況進(jìn)行特殊處理。⑸ 非空的單循環(huán)鏈表由頭指針 head 指示，則其尾結(jié)點(diǎn)（由指針 p 所指）滿足（ ）?！窘獯稹縫next=head【分析】如圖 28 所示。⑹ 在由尾指針 rear 指示的單循環(huán)鏈表中，在表尾插入一個結(jié)點(diǎn) s 的操作序列是（ ）；刪除開始結(jié)點(diǎn)的操作序列為（ ）?！窘獯稹縮next =rearnext。 rearnext =s。 rear =s。q=rearnextnext。 rearnextnext=qnext。 delete q。【分析】操作示意圖如圖 29 所示：⑺ 一個具有 n 個結(jié)點(diǎn)的單鏈表，在指針 p 所指結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為（ ）；在給定值為x 的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為（ ）?！窘獯稹喀?1)，Ο(n)【分析】在 p 所指結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)只需修改指針，所以時間復(fù)雜度為 Ο(1)；而在給定值為 x 的結(jié)點(diǎn) 后插入一個新結(jié)點(diǎn)需要先查找值為 x 的結(jié)點(diǎn)，所以時間復(fù)雜度為 Ο(n)。⑻ 可由一個尾指針唯一確定的鏈表有（ ）、（ ）、（ ）。【解答】循環(huán)鏈表，循環(huán)雙鏈表，雙鏈表2. 選擇題⑴ 線性表的順序存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)，線性表的鏈接存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)。A 隨機(jī)存取 B 順序存取 C 索引存取 D 散列存取【解答】A，B【分析】參見 。⑵ 線性表采用鏈接存儲時，其地址（ ）。A 必須是連續(xù)的 B 部分地址必須是連續(xù)的C 一定是不連續(xù)的 D 連續(xù)與否均可以【解答】D【分析】線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以連續(xù)，也 可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。⑶ 單循環(huán)鏈表的主要優(yōu)點(diǎn)是（ ）。A 不再需要頭指針了B 從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個鏈表；C 已知某個結(jié)點(diǎn)的位置后，能夠容易找到它的直接前趨；D 在進(jìn)行插入、刪除操作時，能更好地保證鏈表不斷開?！窘獯稹緽⑷ 鏈表不具有的特點(diǎn)是（ ）。A 可隨機(jī)訪問任一元素 B 插入、刪除不