清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)(C版)(第2版)課后習(xí)題答案最全整理

1、第1章緒論課后習(xí)題講解1.填空（1）（）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和 處理?！窘獯稹繑?shù)據(jù)元素3（）是數(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è)輸入，

2、有一個(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í)的形式為（）。【解答】0（1），0（nlog2n）【分析】用大0記號(hào)表示算法的時(shí)間復(fù)雜度，需要將低次幕去掉，將最高次幕 的系數(shù)去掉。2. 選擇題 順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)兀素之間的邏輯關(guān)系是由（）表示的，鏈接存儲(chǔ)結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是

3、由（）表示的。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ì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。B計(jì)算機(jī)程序C

4、解決問(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)

5、確定。【解答】錯(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)系。【解答】錯(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. 分析以下各程序段，并用大 0記號(hào)表示其執(zhí)行時(shí)間?！窘獯稹?基本語(yǔ)句是k=k+10*i ，共執(zhí)行了 n-2次，所以T(n)

6、=0(n)基本語(yǔ)句是k=k+10*i ，共執(zhí)行了 n次，所以T(n)=0(n)。分析條件語(yǔ)句，每循環(huán)一次，i+j整體加1,共循環(huán)n次，所以T(n)=0(n)設(shè)循環(huán)體共執(zhí)行T(n)次，每循環(huán)一次，循環(huán)變量y加1,最終T(n)=y，即:(T(n)+1)2 wn,所以 T(n)=0(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)。試畫出其邏輯結(jié)構(gòu)圖并指出屬 于何種結(jié)構(gòu)?！窘獯稹科溥壿嫿Y(jié)構(gòu)圖如圖1-3所示，它是一種圖結(jié)構(gòu)。6. 為整數(shù)定義一個(gè)抽象數(shù)

7、據(jù)類型，包含整數(shù)的常見運(yùn)算，每個(gè)運(yùn)算對(duì)應(yīng)一個(gè)基 本操作，每個(gè)基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件?！窘獯稹空麛?shù)的抽象數(shù)據(jù)類型定義如下：ADT i ntegerData整數(shù)a:可以是正整數(shù)(1,2, 3,)、負(fù)整數(shù)(-1, -2, -3,)和零Operati onCon structor前置條件：整數(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

8、與輸入的整數(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為零，則拋出除零異常，否則

9、輸出取模的結(jié)果后置條件：整數(shù)a的值發(fā)生改變Equal前置條件：存在一個(gè)整數(shù)a輸入：一個(gè)整數(shù)b功能：判斷整數(shù)a與輸入的整數(shù)b是否相等輸出：若相等返回1，否則返回0后置條件：整數(shù)a的值不發(fā)生改變en dADT7. 求多項(xiàng)式A(x)的算法可根據(jù)下列兩個(gè)公式之一來(lái)設(shè)計(jì)： A(x)=anxn+an-1xn-1+a1x+aO A(x)=(anx+an-1)x+a1)x)+aO根據(jù)算法的時(shí)間復(fù)雜度分析比較這兩種算法的優(yōu)劣?！窘獯稹康诙N算法的時(shí)間性能要好些。第一種算法需執(zhí)行大量的乘法運(yùn)算，而第二種算法進(jìn)行了優(yōu)化，減少了不必要的乘法運(yùn)算。8. 算法設(shè)計(jì)(要求：算法用偽代碼和 C+描述，并分析最壞情況下的時(shí)間復(fù)

10、雜度)對(duì)一個(gè)整型數(shù)組An設(shè)計(jì)一個(gè)排序算法?！窘獯稹肯旅媸呛?jiǎn)單選擇排序算法的偽代碼描述。下面是簡(jiǎn)單選擇排序算法的C+描述。分析算法，有兩層嵌套的for循環(huán)，所以，。 找出整型數(shù)組An中元素的最大值和次最大值?！窘獯稹克惴ǖ膫未a描述如下:算法的C+描述如下:分析算法，只有一層循環(huán)，共執(zhí)行 n-2次，所以，T(n)=0(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í)可以作出處理的特性稱為()。【解答】健壯性3. 常見的算法時(shí)間復(fù)

11、雜度用大O記號(hào)表示為：常數(shù)階 ()、對(duì)數(shù)階()、線性 階()、平方階()和指數(shù)階()。【解答】O ，O (Iog2n)，O (n)，O (n2)，O (2n)4. 將下列函數(shù)按它們?cè)趎時(shí)的無(wú)窮大階數(shù)，從小到大排列。n, n-n3+7n5, nlogn, 2n/2, n3, Iog2n, n1/2+log2n, (3/2)n, n!, n2+log2n【解答】Iog2n, n1/2+Iog2n, n, nIog2n, n2+Iog2n, n3, n-n3+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)是指相互之

12、間存在一定關(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)，

13、(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6)【解答】 屬于集合，其邏輯結(jié)構(gòu)圖如圖1-4(a)所示； 屬于線性結(jié)構(gòu)，其邏 輯結(jié)構(gòu)圖如圖1-4(b)所示；(3)屬于樹結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖1-4(c)所示； 屬于圖結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖1-4(d)所示。7. 求下列算法的時(shí)間復(fù)雜度。coun t=0; x=1;while (x x*=2;coun t+;retur n count;【解答】O （Iog2n）第2章線性表課后習(xí)題講解1. 填空在順序表中，等概率情況下，插入和刪除一個(gè)元素平均需移動(dòng)（）個(gè)元素，具體移動(dòng)元素的個(gè)數(shù)與（）和（）有關(guān)?！窘獯稹勘黹L(zhǎng)的一半，表長(zhǎng)，該元素在

14、表中的位置 順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5 個(gè)元素的存儲(chǔ)地址是（）。【解答】108【分析】第5個(gè)元素的存儲(chǔ)地址=第1個(gè)元素的存儲(chǔ)地址+ （5 1） X2=108 設(shè)單鏈表中指針p指向結(jié)點(diǎn)A，若要?jiǎng)h除A的后繼結(jié)點(diǎn)（假設(shè)A存在 后繼結(jié)點(diǎn)），則需修改指針的操作為（）。【解答】p-next=（p-next）-next 單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（）o【解答】為了運(yùn)算方便【分析】例如在插入和刪除操作時(shí)不必對(duì)表頭的情況進(jìn)行特殊處理。非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點(diǎn)（由指針p所指） 滿足（）。【解答】p-next=head【分析】如圖2-8所示。 在由尾指針

15、rear指示的單循環(huán)鏈表中，在表尾插入一個(gè)結(jié)點(diǎn)s的操作序 列是（）；刪除開始結(jié)點(diǎn)的操作序列為（）。【解答】 s-next =rear-next; rear-next =s; rear =s;q=rear- n ext- n ext; rear- n ext- n ext=q-n ext; delete q;【分析】操作示意圖如圖2-9所示：一個(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ù)雜度為 （）。【解答】0（1）, 0（n）【分析】在p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)只需修改指針，所以時(shí)間復(fù)雜度為0（1）； 而在給定值為x的

16、結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)需要先查找值為 x的結(jié)點(diǎn)，所以時(shí)間復(fù)雜度為0（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【分析】參見2.2.1 o線性表采用鏈接存儲(chǔ)時(shí)，其地址（）。A必須是連續(xù)的B部分地址必須是連續(xù)的C 一定是不連續(xù)的D連續(xù)與否均可以【解答】D【分析】線性表的鏈接存儲(chǔ)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素， 組存儲(chǔ)單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。單循環(huán)鏈表的主要

17、優(yōu)點(diǎn)是（）。A不再需要頭指針了B從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表；C已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前趨；D在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開?！窘獯稹緽鏈表不具有的特點(diǎn)是（）0A可隨機(jī)訪問(wèn)任一元素 B插入、刪除不需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間 D所需空間與線性表長(zhǎng)度成正比【解答】A若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨，則采用（）存儲(chǔ)方法最節(jié)省時(shí)間。A順序表B單鏈表C雙鏈表D單循環(huán)鏈表【解答】A【分析】線性表中最常用的操作是取第i個(gè)元素，所以，應(yīng)選擇隨機(jī)存取結(jié)構(gòu)即 順序表，同時(shí)在順序表中查找第i個(gè)元素的前趨也很方便。單鏈表和單循環(huán)鏈表 既不能

18、實(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【分析】在鏈表中的最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址， 所以，單鏈表、帶頭指針的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單 循環(huán)鏈表中刪除第一個(gè)結(jié)點(diǎn)，其時(shí)間性能是 0（1），所以，答案是D o若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè) 結(jié)點(diǎn)，則采用()存儲(chǔ)方法最節(jié)省運(yùn)算時(shí)間。A單

19、鏈表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)雙鏈表滿足條件。 在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜 度是()。A 0(1) B 0(n) C 0(n2) D 0( nl og2 n)【解答】B【分析】首先應(yīng)順序查找新結(jié)點(diǎn)在單鏈表中的位置。 對(duì)于n個(gè)元素組成的線性表，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是()A 0(1) B 0(n) C 0(n2) D 0( nl

20、 og2 n)【解答】C【分析】該算法需要將n個(gè)元素依次插入到有序單鏈表中，而插入每個(gè)元素需0(n)。使用雙鏈表存儲(chǔ)線性表，其優(yōu)點(diǎn)是可以()。A提高查找速度B更方便數(shù)據(jù)的插入和刪除C節(jié)約存儲(chǔ)空間D很快回收存儲(chǔ)空間【解答】B【分析】在鏈表中一般只能進(jìn)行順序查找，所以，雙鏈表并不能提高查找速度，因?yàn)殡p鏈表中有兩個(gè)指針域，顯然不能節(jié)約存儲(chǔ)空間，對(duì)于動(dòng)態(tài)存儲(chǔ)分配，回收 存儲(chǔ)空間的速度是一樣的。由于雙鏈表具有對(duì)稱性，所以，其插入和刪除操作更 加方便。(11) 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前驅(qū)，若在q和 p之間插入s所指結(jié)點(diǎn)，則執(zhí)行()操作。A s-n ext=p-n ext; p-n

21、 ext=s; B q-n ext=s; s-n ext=p;C p-n ext=s-n ext; s-n ext=p; D p-n ext=s; s-n ext=q;【解答】B【分析】注意此題是在q和p之間插入新結(jié)點(diǎn)，所以，不用考慮修改指針的順 序。(12) 在循環(huán)雙鏈表的p所指結(jié)點(diǎn)后插入s所指結(jié)點(diǎn)的操作是()。A p-n ext=s; s-prior=p; p-n ext-prior=s; s-n ext=p-n ext;B p-n ext=s; p-n ext-prior=s; s-prior=p; s-n ext=p-n ext;C s-prior=p; s-n ext=p-n ext

22、; p-n ext=s; p-n ext-prior=s;D s-prior=p; s-n ext=p-n ext; p-n ext-prior=s; p-n ext=s【解答】D【分析】在鏈表中，對(duì)指針的修改必須保持線性表的邏輯關(guān)系，否則，將違背線 性表的邏輯特征，圖2-10給出備選答案C和D的圖解3. 判斷題線性表的邏輯順序和存儲(chǔ)順序總是一致的。【解答】錯(cuò)。順序表的邏輯順序和存儲(chǔ)順序一致， 鏈表的邏輯順序和存儲(chǔ)順序不 一定一致。線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈接存儲(chǔ)結(jié)構(gòu)?！窘獯稹垮e(cuò)。兩種存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)。設(shè)p，q是指針，若p=q，則*p=*q。【解答】錯(cuò)。p=q只能表示p和q指向同一起始地址，

23、而所指類型則不一定相 同。 線性結(jié)構(gòu)的基本特征是：每個(gè)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。【解答】錯(cuò)。每個(gè)元素最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，第一個(gè)元素沒(méi)有前驅(qū)，最后一個(gè)元素沒(méi)有后繼。在單鏈表中，要取得某個(gè)元素，只要知道該元素所在結(jié)點(diǎn)的地址即可，因此 單鏈表是隨機(jī)存取結(jié)構(gòu)?！窘獯稹垮e(cuò)。要找到該結(jié)點(diǎn)的地址，必須從頭指針開始查找，所以單鏈表是順序 存取結(jié)構(gòu)。4 請(qǐng)說(shuō)明順序表和單鏈表各有何優(yōu)缺點(diǎn)，并分析下列情況下，采用何種存儲(chǔ)結(jié) 構(gòu)更好些。 若線性表的總長(zhǎng)度基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的 速度存取線性表中的元素。如果n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生

24、變化。描述一個(gè)城市的設(shè)計(jì)和規(guī)劃?！窘獯稹宽樞虮淼膬?yōu)點(diǎn)：無(wú)需為表示表中元素之間的邏輯關(guān)系而增加額外的 存儲(chǔ)空間； 可以快速地存取表中任一位置的元素（即隨機(jī)存?。ｍ樞虮淼?缺點(diǎn)：插入和刪除操作需移動(dòng)大量元素； 表的容量難以確定； 造成存 儲(chǔ)空間的“碎片”。單鏈表的優(yōu)點(diǎn)：不必事先知道線性表的長(zhǎng)度；插入和刪除元素時(shí)只需修改 指針，不用移動(dòng)元素。單鏈表的缺點(diǎn)： 指針的結(jié)構(gòu)性開銷； 存取表中任意 元素不方便，只能進(jìn)行順序存取。 應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。因?yàn)轫樞虮硎请S機(jī)存取結(jié)構(gòu)，單鏈表是順序存取結(jié)構(gòu)。 本題很少進(jìn)行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應(yīng)選 用順序存儲(chǔ)結(jié)構(gòu)。應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。

25、鏈表容易實(shí)現(xiàn)表容量的擴(kuò)充，適合表的長(zhǎng)度動(dòng)態(tài)發(fā)生 變化。應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。因?yàn)橐粋€(gè)城市的設(shè)計(jì)和規(guī)劃涉及活動(dòng)很多，需要經(jīng)常 修改、擴(kuò)充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。而順序表的插入、刪除 的效率低，故不合適。5 算法設(shè)計(jì) 設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O (n)的算法，實(shí)現(xiàn)將數(shù)組An中所有元素循環(huán)右 移k個(gè)位置?！窘獯稹克惴ㄋ枷胝?qǐng)參見主教材第一章思想火花。下面給出具體算法。分析算法，第一次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為O(k)，第二次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為 0(n-k)，第三次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度 為0(n)，所以，總的時(shí)間復(fù)雜度為 0(n)。 已知數(shù)組An中的元

26、素為整型，設(shè)計(jì)算法將其調(diào)整為左右兩部分，左邊 所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時(shí)間復(fù)雜度為O(n)。【解答】從數(shù)組的兩端向中間比較，設(shè)置兩個(gè)變量i和j，初始時(shí)i=0，j=n-1 ，若Ai為偶數(shù)并且Aj為奇數(shù)，則將Ai與Aj交換。具體算法如下：分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時(shí)間復(fù)雜度為O(n)。 試編寫在無(wú)頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)線性表的插入操作的算法，并和帶頭 結(jié)點(diǎn)的單鏈表上的插入操作的實(shí)現(xiàn)進(jìn)行比較。【解答】參見2.2.3。 試分別以順序表和單鏈表作存儲(chǔ)結(jié)構(gòu)，各寫一實(shí)現(xiàn)線性表就地逆置的算【解答】順序表的逆置，即是將對(duì)稱元素交換，設(shè)順序表的長(zhǎng)度為length，則將表中第i個(gè)

27、元素與第length-i-1個(gè)元素相交換。具體算法如下：?jiǎn)捂湵淼哪嬷谜?qǐng)參見224算法2-4和算法2-6。假設(shè)在長(zhǎng)度大于1的循環(huán)鏈表中，即無(wú)頭結(jié)點(diǎn)也無(wú)頭指針，s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)s的前趨結(jié)點(diǎn)?！窘獯稹坷脝窝h(huán)鏈表的特點(diǎn)，通過(guò)指針s可找到其前驅(qū)結(jié)點(diǎn)r以及r的前驅(qū)結(jié)點(diǎn)p，然后將結(jié)點(diǎn)r刪除，如圖2-11所示，具體算法如下： 已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個(gè)循環(huán)鏈表，使每個(gè)循環(huán)鏈表中只含同一類字符?！窘獯稹吭趩捂湵鞟中依次取元素，若取出的元素是字母，把它插入到字母鏈表B中，若取出的元素是數(shù)字，則把它插入到數(shù)字鏈表 D中，直到鏈

28、表的尾部, 這樣表B，D，A中分別存放字母、數(shù)字和其他字符。具體算法如下： 設(shè)單鏈表以非遞減有序排列，設(shè)計(jì)算法實(shí)現(xiàn)在單鏈表中刪去值相同的多 余結(jié)點(diǎn)?！窘獯稹繌念^到尾掃描單鏈表，若當(dāng)前結(jié)點(diǎn)的元素值與后繼結(jié)點(diǎn)的元素值不相等，則指針后移；否則刪除該后繼結(jié)點(diǎn)。具體算法如下： 判斷帶頭結(jié)點(diǎn)的雙循環(huán)鏈表是否對(duì)稱?！窘獯稹吭O(shè)工作指針p和q分別指向循環(huán)雙鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)，若結(jié)點(diǎn)p和結(jié)點(diǎn)q的數(shù)據(jù)域相等，則工作指針p后移，工作指針q前移，直到指針 p和指針q指向同一結(jié)點(diǎn)(循環(huán)雙鏈表中結(jié)點(diǎn)個(gè)數(shù)為奇數(shù))，或結(jié)點(diǎn) q成為結(jié) 點(diǎn)p的前驅(qū)(循環(huán)雙鏈表中結(jié)點(diǎn)個(gè)數(shù)為偶數(shù))。如圖 2-12所示。學(xué)習(xí)自測(cè)及答案1.已知一維

29、數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用 4個(gè)存儲(chǔ)單元，第9 個(gè)元素的地址為144，則第一個(gè)元素的地址是()。A 108 B 180 C 176 D 112【解答】D2 在長(zhǎng)度為n的線性表中查找值為x的數(shù)據(jù)元素的時(shí)間復(fù)雜度為：()。A 0(0) B 0(1) C 0( n) D 0( n2)【解答】C3.在一個(gè)長(zhǎng)度為n的順序表的第i （1 i n+1 ）個(gè)元素之前插入一個(gè)元素, 需向后移動(dòng)（）個(gè)元素，刪除第i （1 in ）個(gè)元素時(shí)，需向前移動(dòng)（）個(gè)元 素?！窘獯稹縩-i+1，n-i4 在單鏈表中，除了頭結(jié)點(diǎn)以外，任一結(jié)點(diǎn)的存儲(chǔ)位置由（）指示。【解答】其前趨結(jié)點(diǎn)的指針域5 當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)

30、時(shí)，其主要特點(diǎn)是（）。【解答】邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰6 在雙鏈表中，每個(gè)結(jié)點(diǎn)設(shè)置了兩個(gè)指針域，其中一個(gè)指向（）結(jié)點(diǎn)，另一個(gè)指向（）結(jié)點(diǎn)?！窘獯稹壳膀?qū)，后繼7 設(shè)A是一個(gè)線性表（a1, a2,an），采用順序存儲(chǔ)結(jié)構(gòu)，則在等概率的前提下，平均每插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為多少？若元素插在ai與ai+1之間（1 i n ext; B x=top-data;C top=top-n ext; x=top-data; D x=top-data; top=top-n ext;【解答】D4 .設(shè)元素1,2, 3, P, A依次經(jīng)過(guò)一個(gè)棧，進(jìn)棧次序?yàn)?23PA，在棧的輸出 序列中，有哪些序

31、列可作為 C+程序設(shè)計(jì)語(yǔ)言的變量名?！窘獯稹縋A321, P3A21, P32A1, P321A, AP3215. 設(shè) S=l_ am_ a_ teacther，其長(zhǎng)度為（）。【解答】156 對(duì)于棧和隊(duì)列，無(wú)論它們采用順序存儲(chǔ)結(jié)構(gòu)還是鏈接存儲(chǔ)結(jié)構(gòu)，進(jìn)行插入和 刪除操作的時(shí)間復(fù)雜度都是()。【解答】O (1)7 如果進(jìn)棧序列為A、B、C、D，則可能的出棧序列是什么？答：共 14 種，分別是：ABCD , ABDC , ACBD , ACDB , ADCB , BACD , BADC ,BCAD , BCDA , BDCA , CBAD, CBDA, CDBA, DCBA8 .簡(jiǎn)述隊(duì)列和棧這兩種數(shù)

32、據(jù)結(jié)構(gòu)的相同點(diǎn)和不同點(diǎn)?！窘獯稹肯嗤c(diǎn)：它們都是插入和刪除操作的位置受限制的線性表。不同點(diǎn)：棧是限定僅在表尾進(jìn)行插入和刪除的線性表， 是后進(jìn)先出的線性表，而 隊(duì)列是限定在表的一端進(jìn)行插入，在另一端進(jìn)行刪除的線性表，是先進(jìn)先出的線 性表。9.利用兩個(gè)棧S1和S2模擬一個(gè)隊(duì)列，如何利用棧的運(yùn)算實(shí)現(xiàn)隊(duì)列的插入和刪 除操作，請(qǐng)簡(jiǎn)述算法思想?！窘獯稹坷脙蓚€(gè)棧S1和S2模擬一個(gè)隊(duì)列，當(dāng)需要向隊(duì)列中插入一個(gè)元素時(shí)，用S1來(lái)存放已輸入的元素，即通過(guò)向棧 S1執(zhí)行入棧操作來(lái)實(shí)現(xiàn)；當(dāng)需要從隊(duì)列中刪除元素時(shí),則將S1中元素全部送入到S2中,再?gòu)腟2中刪除棧頂元素, 最后再將S2中元素全部送入到S1中；判斷隊(duì)空的條

33、件是：棧S1和S2同時(shí)為 空。10. 設(shè)計(jì)算法把一個(gè)十進(jìn)制整數(shù)轉(zhuǎn)換為二至九進(jìn)制之間的任一進(jìn)制數(shù)輸出。【解答】算法基于原理：N=（N div d） xd + N mod d （div為整除運(yùn)算，mod 為求余運(yùn)算）。11 假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三種括號(hào)：圓括號(hào)“（”和“）”，方括號(hào)“”和“”以及花括號(hào)“ ”和“”，且這三種括號(hào)可按任意的次序嵌 套使用。編寫算法判斷給定表達(dá)式中所含括號(hào)是否配對(duì)出現(xiàn)?！窘獯稹考僭O(shè)表達(dá)式已存入字符數(shù)組 An中，具體算法如下：第4章廣義線性表一一多維數(shù)組和廣義表課后習(xí)題講解1. 填空數(shù)組通常只有兩種運(yùn)算：（）和（），這決定了數(shù)組通常采用（）結(jié) 構(gòu)來(lái)實(shí)現(xiàn)存儲(chǔ)?！窘獯?/p>

34、】存取，修改，順序存儲(chǔ)【分析】數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、 刪除元素的操作。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操 作。二維數(shù)組A中行下標(biāo)從10到20 ,列下標(biāo)從5到10 ,按行優(yōu)先存儲(chǔ), 每個(gè)元素占4個(gè)存儲(chǔ)單元，A105的存儲(chǔ)地址是1000，則元素A1510的 存儲(chǔ)地址是()?！窘獯稹?140【分析】數(shù)組A中每行共有6個(gè)元素，元素A1510的前面共存儲(chǔ)了(15-10)X6+5個(gè)元素，每個(gè)元素占4個(gè)存儲(chǔ)單元，所以，其存儲(chǔ)地址是1000+140=1140 設(shè)有一個(gè)10階的對(duì)稱矩陣A采用壓縮存儲(chǔ)，A00為第一個(gè)元素，其 存儲(chǔ)地址為d，每個(gè)元素占1

35、個(gè)存儲(chǔ)單元，則元素A85的存儲(chǔ)地址為()。【解答】d+41【分析】元素A85的前面共存儲(chǔ)了 (1+2+ -+8)+5=41個(gè)元素。稀疏矩陣一般壓縮存儲(chǔ)方法有兩種，分別是()和()。【解答】三元組順序表，十字鏈表 廣義表(a), (b),c),(d)的長(zhǎng)度是()，深度是()，表頭是()，表尾是()。【解答】3, 4，(a)，(b),c),(d)已知廣義表LS=(a，(b，c，d)，e)，用Head和Tail函數(shù)取出LS中原子b 的運(yùn)算是()?！窘獯稹縃ead(Head(Tail(LS)2. 選擇題二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，行下標(biāo)的范圍從08 ,列下標(biāo)的范圍是從09，貝U存放A至少

36、需要（）個(gè)字節(jié)，A的第8列和第5行共占（）個(gè)字節(jié)，若A按行優(yōu)先方式存儲(chǔ)，元素 A85的起始地址與當(dāng)A按列優(yōu)先方式存儲(chǔ)時(shí)的（）元素的起始地址一致。A 90 B 180 C 240 D 540 E 108 F 114 G 54H A8 5 I A310 J A 58 K A49【解答】D，E，K【分析】數(shù)組A為9行10 列,共有90個(gè)元素，所以，存放A至少需要90 X6=540 個(gè)存儲(chǔ)單元，第8列和第5行共有18個(gè)元素（注意行列有一個(gè)交叉元素），所 以，共占108個(gè)字節(jié)，元素A85按行優(yōu)先存儲(chǔ)的起始地址為d+8 X 10+5=d+85 ，設(shè)元素Aij按列優(yōu)先存儲(chǔ)的起始地址與之相同，則d+j X9+

37、i=d+85 ，解此方程，得 i=4 , j=9。 將數(shù)組稱為隨機(jī)存取結(jié)構(gòu)是因?yàn)椋ǎ〢數(shù)組元素是隨機(jī)的B對(duì)數(shù)組任一元素的存取時(shí)間是相等的C隨時(shí)可以對(duì)數(shù)組進(jìn)行訪問(wèn) D數(shù)組的存儲(chǔ)結(jié)構(gòu)是不定【解答】B 廣義表（a）, （b）,c）,（d）的長(zhǎng)度是（），深度是（），表頭是（），表尾是（）。【解答】3, 4，(a)，(b),c),(d)已知廣義表LS=（a , （b, c, d）, e），用Head和Tail函數(shù)取出LS中原子b的運(yùn)算是（）?！窘獯稹縃ead（Head（Tail（LS）2. 選擇題二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，行下標(biāo)的范圍從08，列下 標(biāo)的范圍是從09，貝U存放A至少需要（）

38、個(gè)字節(jié)，A的第8列和第5行共占（）個(gè)字節(jié)，若A按行優(yōu)先方式存儲(chǔ)，元素 A85的起始地址與當(dāng)A按列優(yōu)先方式存儲(chǔ)時(shí)的（）元素的起始地址一致。A 90 B 180 C 240 D 540 E 108 F 114 G 54H A8 5 I A310 J A 58 K A49【解答】D，E，K【分析】數(shù)組A為9行10 列,共有90個(gè)元素，所以，存放A至少需要90 X6=540 個(gè)存儲(chǔ)單元，第8列和第5行共有18個(gè)元素（注意行列有一個(gè)交叉元素），所 以，共占108個(gè)字節(jié)，元素A85按行優(yōu)先存儲(chǔ)的起始地址為d+8 X 10+5=d+85 ，設(shè)元素Aij按列優(yōu)先存儲(chǔ)的起始地址與之相同，則d+j X9+i=d+

39、85 ，解此方程，得 i=4 , j=9。 將數(shù)組稱為隨機(jī)存取結(jié)構(gòu)是因?yàn)椋ǎ〢數(shù)組元素是隨機(jī)的B對(duì)數(shù)組任一元素的存取時(shí)間是相等的C隨時(shí)可以對(duì)數(shù)組進(jìn)行訪問(wèn)D數(shù)組的存儲(chǔ)結(jié)構(gòu)是不定【解答】B 下面的說(shuō)法中，不正確的是()A數(shù)組是一種線性結(jié)構(gòu) B數(shù)組是一種定長(zhǎng)的線性結(jié)構(gòu)C除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等D數(shù)組的基本操作有存取、修改、檢索和排序等，沒(méi)有插入與刪除操【解答】C【分析】數(shù)組屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)和每維中的元素個(gè)數(shù)是 確定的，所以，數(shù)組通常沒(méi)有插入和刪除操作。 對(duì)特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了()A表達(dá)變得簡(jiǎn)單B對(duì)矩陣元素的存取變得簡(jiǎn)單C去

40、掉矩陣中的多余元素 D減少不必要的存儲(chǔ)空間【解答】D【分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒(méi)有必要為值相同的元素重復(fù)存儲(chǔ)。下面()不屬于特殊矩陣。A對(duì)角矩陣B三角矩陣C稀疏矩陣D對(duì)稱矩陣【解答】C 若廣義表A滿足Head(A)=Tail(A)，則A為()A ( ) B ()C (),() D(),(),()【解答】B 下面的說(shuō)法中，不正確的是（)A廣義表是一種多層次的結(jié)構(gòu) B廣義表是一種非線性結(jié)構(gòu)C廣義表是一種共享結(jié)構(gòu) D廣義表是一種遞歸【解答】B【分析】從各層元素各自具有的線性關(guān)系講，廣義表屬于線性結(jié)構(gòu)。 下面的說(shuō)法中，不正確的是（）A對(duì)稱矩陣只須存放包括主對(duì)角線元素

41、在內(nèi)的下（或上）三角的元素即可。B對(duì)角矩陣只須存放非零元素即可。C稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲(chǔ)。D稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲(chǔ)【解答】D【分析】稀疏矩陣中大量值為零的元素分布沒(méi)有規(guī)律，因此采用三元組表存儲(chǔ)。 如果零元素的分布有規(guī)律，就沒(méi)有必要存儲(chǔ)非零元素的行號(hào)和列號(hào)，而需要按其 壓縮規(guī)律找出相應(yīng)的映象函數(shù)。3. 判斷題數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹 形的。【解答】錯(cuò)。例如二維數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。使用三元組表存儲(chǔ)稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)空間?！窘獯稹繉?duì)。因?yàn)槿M表除了存儲(chǔ)非零元素值外，還需要存儲(chǔ)其行號(hào)和列號(hào)。稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。【解