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