數(shù)據(jù)結(jié)構(gòu)C++版王紅梅版課后答案khdaw

1、第1章緒論課后習題講解填空（ ）是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理?！窘獯稹繑?shù)據(jù)元素（ ）是數(shù)據(jù)的最小單位，（）是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位。【解答】數(shù)據(jù)項，數(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)系算法具有五個特性，分別是（）、（ ）、（ ）、（ ）、（ ）?！窘獯稹坑辛銈€

2、或多個輸入，有一個或多個輸出，有窮性，確定性，可行性 算法的描述方法通常有（）、（ ）、（ ）和（ ）四種，其中，（）被稱為算法語言?！窘獯稹孔匀徽Z言，程序設(shè)計語言，流程圖，偽代碼，偽代碼 在一般情況下，一個算法的時間復雜度是（）的函數(shù)。【解答】問題規(guī)模設(shè)待處理問題的規(guī)模為 n，若一個算法的時間復雜度為一個常數(shù)，則表示成數(shù)量級的形式為（ ），若 為 n*log25n，則表示成數(shù)量級的形式為（）?！窘獯稹?(1，(nlog2n)【分析】用大O 記號表示算法的時間復雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。選擇題順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（）表示的，鏈接存儲結(jié)構(gòu)中的數(shù)據(jù)元素之間的

3、邏輯關(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ù)組中的下標）表示；鏈接存儲結(jié)構(gòu)中一個數(shù)據(jù)元素對應鏈表中的一個結(jié)點，元素之間的邏輯關(guān)系由結(jié)點中的指針表示。假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應該是（ ）。A樹B圖C線性表D集合【解答】B【分析】將丈夫、妻子和子女分別作為數(shù)據(jù)元素，根據(jù)題意畫出邏輯結(jié)構(gòu)圖。算法指的是（ ）。對特定問題求解步驟的一種描述，是指令的

4、有限序列。計算機程序 C 解決問題的計算方法數(shù)據(jù)處理【解答】A【分析】計算機程序是對算法的具體實現(xiàn)；簡單地說，算法是解決問題的方法；數(shù)據(jù)處理是通過算法完成的。所以，只有 A 是算法的準確定義。下面（）不是算法所必須具備的特性。A有窮性B確切性C高效性D可行性【解答】C【分析】高效性是好算法應具備的特性。算法分析的目的是（ ），算法分析的兩個主要方面是（ ）。A 找出數(shù)據(jù)結(jié)構(gòu)的合理性B 研究算法中輸入和輸出的關(guān)系C 分析算法的效率以求改進D分析算法的易讀性和文檔性E 空間性能和時間性能 F 正確性和簡明性G 可讀性和文檔性H 數(shù)據(jù)復雜性和程序復雜性【解答】 C，E判斷題 算法的時間復雜度都要通過

5、算法中的基本語句的執(zhí)行次數(shù)來確定?！窘獯稹垮e。時間復雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級來確定。 每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本操作：插入、刪除和查找。【解答】錯。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結(jié)構(gòu)。 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系?！窘獯稹垮e。是數(shù)據(jù)之間的邏輯關(guān)系的整體。 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)?！窘獯稹繉?。因此邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。 基于某種邏輯結(jié)構(gòu)之上的基本操作，其實現(xiàn)是唯一的?！窘獯稹垮e。基本操作的實現(xiàn)是基于某種存儲結(jié)構(gòu)設(shè)計的，因而不是唯一的。分析以下各程序段，并用大 O 記號表示其執(zhí)行時間?！窘獯稹炕菊Z句是k=k+10*i ，共執(zhí)

6、行了 n-2 次，所以 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)2n，所以 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)?！窘獯稹科溥壿?/p>

7、結(jié)構(gòu)圖如圖1-3 所示，它是一種圖結(jié)構(gòu)。為整數(shù)定義一個抽象數(shù)據(jù)類型，包含整數(shù)的常見運算，每個運算對應一個基本操作，每個基本操作的接 口需定義前置條件、輸入、功能、輸出和后置條件?！窘獯稹空麛?shù)的抽象數(shù)據(jù)類型定義如下：ADT integerData整數(shù) a：可以是正整數(shù) (1, 2, 3,) 、負整數(shù) (-1, -2, -3,)和零OperationConstructor 前置條件：整數(shù)a不存在 輸入：一個整數(shù) b功能：構(gòu)造一個與輸入值相同的整數(shù)輸出：無后置條件：整數(shù) a具有輸入的值Set前置條件：存在一個整數(shù) a輸入：一個整數(shù) b功能：修改整數(shù) a的值，使之與輸入的整數(shù)值相同 輸出：無后置條件：

8、整數(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é)果后

9、置條件：整數(shù) a 的值發(fā)生改變Mod 前置條件：存在一個整數(shù) a輸入：一個整數(shù) b功能：求當前整數(shù)與輸入整數(shù)的模，即正的余數(shù)輸出：若整數(shù) b 為零，則拋出除零異常，否則輸出取模的結(jié)果后置條件：整數(shù) a 的值發(fā)生改變Equal 前置條件：存在一個整數(shù) a 輸入：一個整數(shù) b功能：判斷整數(shù) a與輸入的整數(shù) b是否相等 輸出：若相等返回 1，否則返回 0后置條件：整數(shù) a的值不發(fā)生改變endADT求多項式 A(x)的算法可根據(jù)下列兩個公式之一來設(shè)計： A(x)=anxn+an-1xn-1+ +a1x+a0A(x)= ( (anx+an-1)x+ +a1)x)+a0根據(jù)算法的時間復雜度分析比較這兩種算

10、法的優(yōu)劣。【解答】第二種算法的時間性能要好些。第一種算法需執(zhí)行大量的乘法運算，而第二種算法進行了優(yōu)化，減少了不必要的乘法運算。算法設(shè)計（要求：算法用偽代碼和 C+ 描述，并分析最壞情況下的時間復雜度） 對一個整型數(shù)組An設(shè)計一個排序算法?！窘獯稹肯旅媸呛唵芜x擇排序算法的偽代碼描述。下面是簡單選擇排序算法的 C+ 描述。分析算法，有兩層嵌套的for 循環(huán)，所以，找出整型數(shù)組An中元素的最大值和次最大值。【解答】算法的偽代碼描述如下：。算法的C+ 描述如下：分析算法，只有一層循環(huán)，共執(zhí)行n-2 次，所以，T(n)=O(n) 。學習自測及答案1順序存儲結(jié)構(gòu)的特點是（），鏈接存儲結(jié)構(gòu)的特點是（ ）?！?/p>

11、解答】用元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，用指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。算法在發(fā)生非法操作時可以作出處理的特性稱為（ ）?！窘獯稹拷研猿Ｒ姷乃惴〞r間復雜度用大記號表示為：常數(shù)階 ( )、對數(shù)階 ( )、線性階 ( )、平方階 ( )和指數(shù)階 ( )?！窘獯稹?1)， (log2n)， (n)，(n2)， (2n)4將下列函數(shù)按它們在n 時的無窮大階數(shù)，從小到大排列。n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!,n2+log2n【解答】 log2n, n1/2+log2n, n,

12、 nlog2n, n2+log2n, n3, n-n3+7n5,2n/2, (3/2)n, n!5試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計語言中數(shù)據(jù)類型概念的區(qū)別?！窘獯稹繑?shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。而抽象數(shù)據(jù)類型是指一個數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作。程序設(shè)計語言中的數(shù)據(jù)類型是一個值的集合和定義在這個值集上一組操作的總稱。抽象數(shù)據(jù)類型可以看成是對數(shù)據(jù)類型的一種抽象。對下列用二元組表示的數(shù)據(jù)結(jié)構(gòu) ,試分別畫出對應的邏輯結(jié)構(gòu)圖，并指出屬于何種結(jié)構(gòu)。A=(D，R)， 其中 D=a1, a2, a3, a4，R= B=(D ，R)， 其中 D=a, b, c, d,

13、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)圖如圖1-4(a)所示； 屬于線性結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖 1-4(b)所示；屬于樹結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖 1-4(c)所示；屬于圖結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖 1-4(d)所示。求下列算法的時間復雜度。count=0;x=1; while (x x*=2; count+;return count;【解答】

14、 (log2n)第2 章線性表課后習題講解填空在順序表中，等概率情況下，插入和刪除一個元素平均需移動（）個元素，具體移動元素的個數(shù)與（） 和（ ）有關(guān)。【解答】表長的一半，表長，該元素在表中的位置順序表中第一個元素的存儲地址是 100，每個元素的長度為2，則第 5 個元素的存儲地址是（ ）?！窘獯稹?108【分析】第 5 個元素的存儲地址 = 第 1 個元素的存儲地址 (5 1) 2=108設(shè)單鏈表中指針p 指向結(jié)點 A，若要刪除 A 的后繼結(jié)點（假設(shè) A 存在后繼結(jié)點），則需修改指針的操作為（ ）?！窘獯稹?p-next=(p-next)-next單鏈表中設(shè)置頭結(jié)點的作用是（）?！窘獯稹繛榱?/p>

15、運算方便【分析】例如在插入和刪除操作時不必對表頭的情況進行特殊處理。非空的單循環(huán)鏈表由頭指針 head指示，則其尾結(jié)點（由指針p 所指）滿足（ ）。【解答】 p-next=head【分析】如圖 2-8 所示。在由尾指針rear 指示的單循環(huán)鏈表中，在表尾插入一個結(jié)點s 的操作序列是（ ）；刪除開始結(jié)點的操作序列為（ ）?！窘獯稹?s-next =rear-next; rear-next =s; rear =s;q=rear-next-next; rear-next-next=q-next; delete q;【分析】操作示意圖如圖2-9 所示： 一個具有n 個結(jié)點的單鏈表，在指針 p 所指結(jié)點

16、后插入一個新結(jié)點的時間復雜度為（ ）；在給定值為的結(jié)點后插入一個新結(jié)點的時間復雜度為（ ）?！窘獯稹?(1)，(n)【分析】在 p 所指結(jié)點后插入一個新結(jié)點只需修改指針，所以時間復雜度為(1)；而在給定值為 x 的結(jié)點 后插入一個新結(jié)點需要先查找值為x 的結(jié)點，所以時間復雜度為 (n)。 可由一個尾指針唯一確定的鏈表有（）、（ ）、（ ）?！窘獯稹垦h(huán)鏈表，循環(huán)雙鏈表，雙鏈表選擇題線性表的順序存儲結(jié)構(gòu)是一種（）的存儲結(jié)構(gòu)，線性表的鏈接存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)。A 隨機存取 B 順序存取 C 索引存取 D散列存取【解答】 A ，B【分析】參見2.2.1。 線性表采用鏈接存儲時，其地址（ ）

17、。A 必須是連續(xù)的B 部分地址必須是連續(xù)的C 一定是不連續(xù)的D連續(xù)與否均可以【解答】D【分析】線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。單循環(huán)鏈表的主要優(yōu)點是（ ）。不再需要頭指針了從表中任一結(jié)點出發(fā)都能掃描到整個鏈表；已知某個結(jié)點的位置后，能夠容易找到它的直接前趨；在進行插入、刪除操作時，能更好地保證鏈表不斷開?！窘獯稹緽 鏈表不具有的特點是（ ）。A 可隨機訪問任一元素B 插入、刪除不需要移動元素C 不必事先估計存儲空間D 所需空間與線性表長度成正比【解答】A若某線性表中最常用的操作是取第i 個元素和找

18、第 i 個元素的前趨，則采用（）存儲方法最節(jié)省時間。A順序表B單鏈表C雙鏈表D單循環(huán)鏈表【解答】A【分析】線性表中最常用的操作是取第i 個元素，所以，應選擇隨機存取結(jié)構(gòu)即順序表，同時在順序表中查找第 i 個元素的前趨也很方便。 單鏈表和單循環(huán)鏈表既不能實現(xiàn)隨機存取， 查找第 i 個元素的前趨也不方便，雙鏈表雖然能快速查找第 i 個元素的前趨，但不能實現(xiàn)隨機存取。若鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除第一個結(jié)點，則采用（ ）存儲方法 最節(jié)省時間。A 單鏈表B 帶頭指針的單循環(huán)鏈表C 雙鏈表D帶尾指針的單循環(huán)鏈表【解答】D【分析】在鏈表中的最后一個結(jié)點之后插入一個結(jié)點需要知道終

19、端結(jié)點的地址，所以，單鏈表、帶頭指針的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第一個結(jié)點，其時間性能是O(1)， 所以，答案是 D 。若鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采用（）存儲方 法最節(jié)省運算時間。A 單鏈表 B 循環(huán)雙鏈表 C 單循環(huán)鏈表D帶尾指針的單循環(huán)鏈表【解答】B【分析】在鏈表中的最后一個結(jié)點之后插入一個結(jié)點需要知道終端結(jié)點的地址，所以，單鏈表、單循環(huán)鏈表都不合適，刪除最后一個結(jié)點需要知道終端結(jié)點的前驅(qū)結(jié)點的地址，所以，帶尾指針的單循環(huán)鏈表不合適，而循環(huán)雙鏈表滿足條件。 在具有 n 個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然

20、有序的時間復雜度是（）。A O(1) B O(n) C O(n2) DO(nlog2n)【解答】B【分析】首先應順序查找新結(jié)點在單鏈表中的位置。 對于 n 個元素組成的線性表，建立一個有序單鏈表的時間復雜度是（ ）。A O(1) B O(n) C O(n2) DO(nlog2n)【解答】C【分析】該算法需要將n 個元素依次插入到有序單鏈表中，而插入每個元素需 O(n)。 使用雙鏈表存儲線性表，其優(yōu)點是可以（ ）。A 提高查找速度B 更方便數(shù)據(jù)的插入和刪除C 節(jié)約存儲空間D 很快回收存儲空間【解答】B【分析】在鏈表中一般只能進行順序查找，所以，雙鏈表并不能提高查找速度，因為雙鏈表中有兩個指針域，

21、顯然不能節(jié)約存儲空間，對于動態(tài)存儲分配，回收存儲空間的速度是一樣的。由于雙鏈表具有對稱性，所以，其插入和刪除操作更加方便。在一個單鏈表中，已知 q 所指結(jié)點是 p 所指結(jié)點的直接前驅(qū)，若在q 和 p 之間插入 s 所指結(jié)點，則執(zhí) 行（ ）操作。A s-next=p-next; p-next=s; B q-next=s; s-next=p; C p-next=s-next; s-next=p; D p-next=s; s-next=q;【解答】B【分析】注意此題是在q 和 p 之間插入新結(jié)點，所以，不用考慮修改指針的順序。在循環(huán)雙鏈表的 p 所指結(jié)點后插入s 所指結(jié)點的操作是（ ）。Ap-nex

22、t=s;s-prior=p;p-next-prior=s;s-next=p-next; B p-next=s; p-next-prior=s; s-prior=p;s-next=p-next;Cs-prior=p;s-next=p-next; p-next=s; p-next-prior=s; D s-prior=p;s-next=p-next;p-next-prior=s;p-next=s【解答】D【分析】在鏈表中，對指針的修改必須保持線性表的邏輯關(guān)系，否則，將違背線性表的邏輯特征，圖 2-10給出備選答案 C 和 D 的圖解。判斷題 線性表的邏輯順序和存儲順序總是一致的。【解答】錯。順序表

23、的邏輯順序和存儲順序一致，鏈表的邏輯順序和存儲順序不一定一致。 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈接存儲結(jié)構(gòu)。【解答】錯。兩種存儲結(jié)構(gòu)各有優(yōu)缺點。設(shè)p， q 是指針，若 p=q ，則*p=*q 。【解答】錯。 p=q 只能表示 p 和 q 指向同一起始地址，而所指類型則不一定相同。 線性結(jié)構(gòu)的基本特征是：每個元素有且僅有一個直接前驅(qū)和一個直接后繼。【解答】錯。每個元素最多只有一個直接前驅(qū)和一個直接后繼，第一個元素沒有前驅(qū)，最后一個元素沒有后繼。 在單鏈表中，要取得某個元素，只要知道該元素所在結(jié)點的地址即可，因此單鏈表是隨機存取結(jié)構(gòu)?！窘獯稹垮e。要找到該結(jié)點的地址，必須從頭指針開始查找，所以單鏈表是順序

24、存取結(jié)構(gòu)。4請說明順序表和單鏈表各有何優(yōu)缺點，并分析下列情況下，采用何種存儲結(jié)構(gòu)更好些。 若線性表的總長度基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素。如果n 個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化。 描述一個城市的設(shè)計和規(guī)劃?！窘獯稹宽樞虮淼膬?yōu)點：無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間；可以快速地存取表中任一位置的元素（即隨機存取）。順序表的缺點：插入和刪除操作需移動大量元素；表的 容量難以確定；造成存儲空間的“碎片”。單鏈表的優(yōu)點： 不必事先知道線性表的長度； 插入和刪除元素時只需修改指針，不用移動元素。單鏈表的缺點：指針的結(jié)構(gòu)

25、性開銷；存取表中任意元素不方便，只能進行順序存取。 應選用順序存儲結(jié)構(gòu)。因為順序表是隨機存取結(jié)構(gòu)，單鏈表是順序存取結(jié)構(gòu)。本題很少進行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應選用順序存儲結(jié)構(gòu)。 應選用鏈接存儲結(jié)構(gòu)。鏈表容易實現(xiàn)表容量的擴充，適合表的長度動態(tài)發(fā)生變化。 應選用鏈接存儲結(jié)構(gòu)。因為一個城市的設(shè)計和規(guī)劃涉及活動很多， 需要經(jīng)常修改、擴充和刪除各種信息，才能適應不斷發(fā)展的需要。而順序表的插入、刪除的效率低，故不合適。5算法設(shè)計 設(shè)計一個時間復雜度為 (n)的算法，實現(xiàn)將數(shù)組An中所有元素循環(huán)右移 k 個位置?！窘獯稹克惴ㄋ枷胝垍⒁娭鹘滩牡谝徽滤枷牖鸹?。下面給出具體算法。分析

26、算法，第一次調(diào)用 Reverse函數(shù)的時間復雜度為 O(k)，第二次調(diào)用 Reverse函數(shù)的時間復雜度為 O(n-k)， 第三次調(diào)用 Reverse函數(shù)的時間復雜度為O(n)，所以，總的時間復雜度為 O(n)。已知數(shù)組An中的元素為整型，設(shè)計算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時間復雜度為(n)?！窘獯稹繌臄?shù)組的兩端向中間比較，設(shè)置兩個變量i 和 j，初始時 i=0， j=n-1，若Ai為偶數(shù)并且 Aj為奇 數(shù)，則將 Ai與 Aj交換。具體算法如下：分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時間復雜度為(n)。試編寫在無頭結(jié)點的單鏈表上實現(xiàn)線性表的插入

27、操作的算法，并和帶頭結(jié)點的單鏈表上的插入操作的實現(xiàn)進行比較?！窘獯稹繀⒁?2.2.3。試分別以順序表和單鏈表作存儲結(jié)構(gòu)，各寫一實現(xiàn)線性表就地逆置的算法?！窘獯稹宽樞虮淼哪嬷茫词菍ΨQ元素交換， 設(shè)順序表的長度為 length，則將表中第 i 個元素與第 length-i-1個元素相交換。具體算法如下：單鏈表的逆置請參見 2.2.4算法 2-4 和算法 2-6。假設(shè)在長度大于1 的循環(huán)鏈表中，即無頭結(jié)點也無頭指針，s 為指向鏈表中某個結(jié)點的指針，試編寫算法刪除結(jié)點 s的前趨結(jié)點。【解答】利用單循環(huán)鏈表的特點， 通過指針 s 可找到其前驅(qū)結(jié)點 r 以及 r 的前驅(qū)結(jié)點 p，然后將結(jié)點 r 刪除，

28、 如圖 2-11 所示，具體算法如下：已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個循環(huán)鏈表，使每個循環(huán)鏈表中只含同一類字符?！窘獯稹吭趩捂湵?A 中依次取元素，若取出的元素是字母，把它插入到字母鏈表B 中，若取出的元素是數(shù)字，則把它插入到數(shù)字鏈表D 中，直到鏈表的尾部，這樣表 B，D ， A 中分別存放字母、數(shù)字和其他字符。具體算法如下： 設(shè)單鏈表以非遞減有序排列，設(shè)計算法實現(xiàn)在單鏈表中刪去值相同的多余結(jié)點?！窘獯稹繌念^到尾掃描單鏈表，若當前結(jié)點的元素值與后繼結(jié)點的元素值不相等，則指針后移；否則刪除該后繼結(jié)點。具體算法如下： 判斷帶頭結(jié)點的雙循環(huán)鏈表是否對稱

29、?！窘獯稹吭O(shè)工作指針 p 和 q 分別指向循環(huán)雙鏈表的開始結(jié)點和終端結(jié)點，若結(jié)點 p和結(jié)點 q 的數(shù)據(jù)域相等，則工作指針 p 后移，工作指針 q 前移，直到指針 p 和指針 q指向同一結(jié)點（循環(huán)雙鏈表中結(jié)點個數(shù)為奇數(shù)）， 或結(jié)點 q 成為結(jié)點 p 的前驅(qū)（循環(huán)雙鏈表中結(jié)點個數(shù)為偶數(shù)）。如圖2-12所示。學習自測及答案已知一維數(shù)組 A 采用順序存儲結(jié)構(gòu)，每個元素占用 4 個存儲單元，第 9 個元素的地址為 144，則第一個 元素的地址是（ ）。A 108 B 180 C 176 D 112【解答】 D2在長度為 n 的線性表中查找值為 x 的數(shù)據(jù)元素的時間復雜度為：（ ）。A O(0) B O(

30、1) C O(n) D O(n2)【解答】 C3在一個長度為 n 的順序表的第 i（ 1 i n+1）個元素之前插入一個元素，需向后移動（ ）個元素，刪除 第 i（ 1 i n）個元素時，需向前移動（）個元素。【解答】 n-i+1， n-i4在單鏈表中，除了頭結(jié)點以外，任一結(jié)點的存儲位置由（）指示?！窘獯稹科淝摆吔Y(jié)點的指針域5當線性表采用順序存儲結(jié)構(gòu)時，其主要特點是（）?！窘獯稹窟壿嫿Y(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰6在雙鏈表中，每個結(jié)點設(shè)置了兩個指針域，其中一個指向（ ）結(jié)點，另一個指向（ ）結(jié)點?！窘獯稹壳膀?qū)，后繼7設(shè) A 是一個線性表（ a1, a2, ,an），采用順序存儲結(jié)構(gòu)，則在等

31、概率的前提下，平均每插入一個元素需要移動的元素個數(shù)為多少？若元素插在ai 與 ai+1 之間（ 1 i n的）概率為，則平均每插 入一個元素所要移動的元素個數(shù)又是多少？【解答】，。8線性表存放在整型數(shù)組Aarrsize的前 elenum 個單元中，且遞增有序。編寫算法，將元素x 插入到線性表的適當位置上，以保持線性表的有序性，并且分析算法的時間復雜度?！窘獯稹勘绢}是在一個遞增有序表中插入元素x，基本思路是從有序表的尾部開始依次取元素與x 比較， 若大于 x，此元素后移一位，再取它前面一個元素重復上 述 步 驟 ； 否 則 ， 找 到 插 入 位 置 ， 將x插 入 。 具 體算 法 如 下 ：

32、已知單鏈表中各結(jié)點的元素值為整型且遞增有序，設(shè)計算法刪除鏈表中所有大于 mink 且小于 maxk 的所有元素，并釋放被刪結(jié)點的存儲空間?！窘獯稹恳驗槭窃谟行騿捂湵砩系牟僮?，所以，要充分利用其有序性。在單鏈表中查找第一個大于 mink的結(jié)點和第一個小于maxk 的結(jié)點，再將二者間的所有結(jié)點刪除。10設(shè)單循環(huán)鏈表 L1，對其遍歷的結(jié)果是： x1, x2, x3, ,xn-1, xn。請將該循環(huán)鏈表拆成兩個單循環(huán)鏈表L1 和 L2，使得 L1 中含有原 L1 表中序號為奇數(shù)的結(jié)點且遍歷結(jié)果為： x1, x3, ；L2 中含有原L1 表中序號為偶數(shù)的結(jié)點且遍歷結(jié)果為： x4, x2?！窘獯稹克惴ㄈ缦?/p>

33、：第 3 章 特殊線性表 棧、隊列和串課后習題講解填空設(shè)有一個空棧，棧頂指針為 1000H，現(xiàn)有輸入序列為 1、2、3、4、5， 經(jīng)過 push，push，pop，push，pop， push，push 后，輸出序列是（），棧頂指針為（）?！窘獯稹?23，1003H棧通常采用的兩種存儲結(jié)構(gòu)是（）；其判定?？盏臈l件分別是（），判定棧滿的條件分別是（）?！窘獯稹宽樞虼鎯Y(jié)構(gòu)和鏈接存儲結(jié)構(gòu)（或順序棧和鏈棧），棧頂指針top=NULL ，棧頂指針top= -1 和top 等于數(shù)組的長度和內(nèi)存無可用空間（ ）可作為實現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)?！窘獯稹織！痉治觥窟f歸函數(shù)的調(diào)用和返回正好符合后進先出性。

34、表達式a*(b+c)-d 的后綴表達式是（）。【解答】 abc+*d-【分析】將中綴表達式變?yōu)楹缶Y表達式有一個技巧：將操作數(shù)依次寫下來，再將算符插在它的兩個操作數(shù)的后面。棧和隊列是兩種特殊的線性表，棧的操作特性是（），隊列的操作特性是（ ），棧和隊列的主要區(qū)別在于（ ）?！窘獯稹亢筮M先出，先進先出，對插入和刪除操作限定的位置不同循環(huán)隊列的引入是為了克服（ ）?！窘獯稹考僖绯鰯?shù)組Qn用來表示一個循環(huán)隊列，front 為隊頭元素的前一個位置，rear為隊尾元素的位置，計算隊列中元素個數(shù)的公式為（）。【解答】（ rear-front+n） % n【分析】也可以是（ rear-front）% n，但

35、rear-front 的結(jié)果可能是負整數(shù)，而對一個負整數(shù)求模，其結(jié)果在不同的編譯器環(huán)境下可能會有所不同。用循環(huán)鏈表表示的隊列長度為 n，若只設(shè)頭指針，則出隊和入隊的時間復雜度分別是（ ）和（ ）?！窘獯稹?(1)， (n)【分析】在帶頭指針的循環(huán)鏈表中，出隊即是刪除開始結(jié)點，這只需修改相應指針；入隊即是在終端結(jié)點的后面插入一個結(jié)點，這需要從頭指針開始查找終端結(jié)點的地址。串是一種特殊的線性表，其特殊性體現(xiàn)在（）?！窘獯稹繑?shù)據(jù)元素的類型是一個字符兩個串相等的充分必要條件是（）。【解答】長度相同且對應位置的字符相等【分析】例如abc abc，abc bca。選擇題若一個棧的輸入序列是 1，2，3，

36、， n，輸出序列的第一個元素是n，則第 i 個輸出元素是（ ）。A 不確定 B n-i C n-i-1 D n-i+1【解答】 D【分析】此時，輸出序列一定是輸入序列的逆序。設(shè)棧S和隊列 Q 的初始狀態(tài)為空，元素 e1、e2、e3、e4、e5、e6依次通過棧 S，一個元素出棧后即進入隊列 Q，若 6 個元素出隊的順序是 e2、e4、e3、e6、 e5、e1，則棧 S的容量至少應該是（）。A6B4C3D2【解答】 C【分析】由于隊列具有先進先出性，所以，此題中隊列形同虛設(shè)，即出棧的順序也是 e2、e4、e3、e6、e5、e1。一個棧的入棧序列是 1， 2， 3， 4， 5，則棧的不可能的輸出序列

37、是（）。A 54321 B 45321 C 43512 D 12345【解答】 C【分析】此題有一個技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序號）的兩個元素。設(shè)計一個判別表達式中左右括號是否配對的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳A 順序表 B棧C隊列D 鏈表【解答】 B【分析】每個右括號與它前面的最后一個沒有匹配的左括號配對，因此具有后進先出性。在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印緩沖區(qū)，該緩沖區(qū)應該是一個 （ ） 結(jié)構(gòu)。棧B隊列C數(shù)組D線性表【解答】 B【分析】先進入打印緩沖區(qū)的文件先被打印，因此具有先進先出性。一個隊列的入隊順序是 1，2，

38、3，4，則隊列的輸出順序是（）。A 4321 B 1234 C 1432 D 3241【解答】 B【分析】隊列的入隊順序和出隊順序總是一致的。棧和隊列的主要區(qū)別在于（ ）。A 它們的邏輯結(jié)構(gòu)不一樣B 它們的存儲結(jié)構(gòu)不一樣C 所包含的運算不一樣D 插入、刪除運算的限定不一樣【解答】 D【分析】棧和隊列的邏輯結(jié)構(gòu)都是線性的，都有順序存儲和鏈接存儲，有可能包含的運算不一樣，但不是主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對具體問題時包含的運算都可能不同。設(shè)數(shù)組Sn作為兩個棧 S1 和 S2 的存儲空間，對任何一個棧只有當Sn全滿時才不能進行進棧操作。為這兩個棧分配空間的最佳方案是（）。A S1 的棧底位置為 0，S

39、2的棧底位置為 n-1B S1的棧底位置為 0， S2的棧底位置為 n/2C S1的棧底位置為 0，S2的棧底位置為 nD S1 的棧底位置為 0，S2 的棧底位置為 1【解答】 A【分析】兩棧共享空間首先兩個棧是相向增長的，棧底應該分別指向兩個棧中的第一個元素的位置，并注意 C+ 中的數(shù)組下標是從 0 開始的。設(shè)有兩個串p 和 q，求 q 在 p 中首次出現(xiàn)的位置的運算稱作（）。A 連接 B 模式匹配 C 求子串 D 求串長【解答】 B判斷題有n 個元素依次進棧，則出棧序列有(n-1)/2 種?！窘獯稹垮e。應該有種。棧可以作為實現(xiàn)過程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。【解答】對。只要操作滿足后進先出性，都

40、可以采用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。在棧滿的情況下不能做進棧操作，否則將產(chǎn)生“上溢”。【解答】對。在循環(huán)隊列中，front 指向隊頭元素的前一個位置，rear 指向隊尾元素的位置，則隊滿的條件是front=rear?！窘獯稹垮e。這是隊空的判定條件，在循環(huán)隊列中要將隊空和隊滿的判定條件區(qū)別開?？沾c空格串是相同的?！窘獯稹垮e。空串的長度為零，而空格串的長度不為0，其長度是串中空格的個數(shù)。設(shè)有一個棧，元素進棧的次序為 A，B，C，D ，E，能否得到如下出棧序列，若能，請寫出操作序列，若 不能，請說明原因。C ，E，A，B，DC ，B，A，D，E【解答】不能，因為在C、E 出棧的情況下， A 一定在棧中，而

41、且在B 的下面，不可能先于 B 出棧?？梢?，設(shè)為進棧操作，為入棧操作，則其操作序列為 IIIOOOIOIO 。舉例說明順序隊列的“假溢出”現(xiàn)象?！窘獯稹考僭O(shè)有一個順序隊列，如圖3-6 所示，隊尾指針 rear=4，隊頭指針 front=1 ，如果再有元素入隊，就會產(chǎn)生“上溢”，此時的“上溢”又稱為“假溢出”，因為隊列并不是真的溢出了，存儲隊列的數(shù)組中還有2 個存儲單元空閑，其下標分別為0 和 1。在操作序列 push(1)、 push(2)、 pop、push(5)、push(7)、pop、 push(6)之后，棧頂元素和棧底元素分別是什么？（ push(k)表示整數(shù) k 入棧， pop 表示

42、棧頂元素出棧。）【解答】棧頂元素為 6，棧底元素為 1。其執(zhí)行過程如圖 3-7 所示。7 在操作序列 EnQueue(1)、 EnQueue(3)、 DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，隊頭元素和隊尾元素分別是什么？（EnQueue(k)表示整數(shù) k 入隊， DeQueue表示隊頭元素出隊）?！窘獯稹筷狀^元素為5，隊尾元素為 9。其執(zhí)行過程如圖 3-8 所示。8空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的 個數(shù)。串

43、中的空格符可用來分隔一般的字符，便于人們識別和閱讀，但計算串長時應包括這些空格符?？?串在串處理中可作為任意串的子串。算法設(shè)計假設(shè)以不帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點，但不設(shè)頭指針。試設(shè)計相應的入隊和出隊的算法。【解答】出隊操作是在循環(huán)鏈表的頭部進行，相當于刪除開始結(jié)點，而入隊操作是在循環(huán)鏈表的尾部進行，相當于在終端結(jié)點之后插入一個結(jié)點。由于循環(huán)鏈表不帶頭結(jié)點，需要處理空表的特殊情況。入隊算法如下：出隊算法如下：設(shè)順序棧 S 中有 2n 個元素，從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-1， ， a1，要求通過一個循環(huán)隊列重新排列棧中元素，使得從棧頂?shù)綏５椎脑匾来螢閍2

44、n，a2n-2， ， a2， a2n-1， a2n-3， ， a1，請設(shè) 計算法實現(xiàn)該操作，要求空間復雜度和時間復雜度均為 O(n)?！窘獯稹坎僮鞑襟E為： 將所有元素出棧并入隊； 依次將隊列元素出隊，如果是偶數(shù)結(jié)點，則再入隊，如果是奇數(shù)結(jié)點，則入棧； 將奇數(shù)結(jié)點出棧并入隊；將偶數(shù)結(jié)點出隊并入棧；將所有元素出棧并入隊；將所有元素出隊并入棧即為所求。用順序存儲結(jié)構(gòu)存儲串 S，編寫算法刪除 S中第 i 個字符開始的連續(xù) j 個字符?！窘獯稹肯扰袛啻?S中要刪除的內(nèi)容是否存在， 若存在，則將第 i+j-1 之后的字符前移 j 個位置。算法如下：對于采用順序存儲結(jié)構(gòu)的串 S，編寫一個函數(shù)刪除其值等于ch

45、 的所有字符?！窘獯稹繌暮笙蚯皠h除值為 ch 的所有元素，這樣所有移動的元素中沒有值為 ch 的元素，能減少移動元素 的次數(shù)，提高算法的效率。算法如下：對串的模式匹配KMP 算法設(shè)計求模式滑動位置的next 函數(shù)?！窘獯稹繀⒁?3.2.5學習自測及答案1在一個具有 n 個單元的順序棧中，假定以地址低端（即下標為0 的單元）作為棧底，以 top 作為棧頂指 針，當出棧時， top 的變化為（ ）。A 不變 B top=0; C top=top-1; D top=top+1;【解答】 C2一個棧的入棧序列是 a, b, c, d, e，則棧的不可能的出棧序列是（）。A edcba B cdeba

46、C debca D abcde【解答】 C3從棧頂指針為 top 的鏈棧中刪除一個結(jié)點，用x 保存被刪除結(jié)點的值，則執(zhí)行（ ）。A x=top; top=top-next; B x=top-data;C top=top-next; x=top-data; D x=top-data; top=top-next;【解答】 D4設(shè)元素 1, 2, 3, P, A依次經(jīng)過一個棧，進棧次序為123PA，在棧的輸出序列中，有哪些序列可作為 C+程序設(shè)計語言的變量名?！窘獯稹?PA321, P3A21, P32A1, P321A, AP3215.設(shè) S=I_ am_ a_ teacther，其長度為（ ）。

47、【解答】 156對于棧和隊列，無論它們采用順序存儲結(jié)構(gòu)還是鏈接存儲結(jié)構(gòu)，進行插入和刪除操作的時間復雜度都是（ ）?！窘獯稹?(1)7如果進棧序列為 A 、 B、 C、D ，則可能的出棧序列是什么？答：共 14 種，分別是： ABCD ，ABDC ，ACBD ，ACDB ，ADCB ，BACD，BADC ，BCAD ，BCDA ，BDCA ，CBAD ，CBDA ，CDBA ，DCBA8簡述隊列和棧這兩種數(shù)據(jù)結(jié)構(gòu)的相同點和不同點?！窘獯稹肯嗤c：它們都是插入和刪除操作的位置受限制的線性表。不同點：棧是限定僅在表尾進行插入和刪除的線性表，是后進先出的線性表，而隊列是限定在表的一端進行插入，在另一端

48、進行刪除的線性表，是先進先出的線性表。利用兩個棧 S1 和 S2 模擬一個隊列，如何利用棧的運算實現(xiàn)隊列的插入和刪除操作，請簡述算法思想。【解答】利用兩個棧 S1 和 S2 模擬一個隊列，當需要向隊列中插入一個元素時，用 S1 來存放已輸入的元 素，即通過向棧 S1 執(zhí)行入棧操作來實現(xiàn)；當需要從隊列中刪除元素時，則將 S1 中元素全部送入到 S2 中， 再從 S2 中刪除棧頂元素，最后再將 S2 中元素全部送入到 S1 中；判斷隊空的條件是：棧 S1 和 S2 同時為 空。設(shè)計算法把一個十進制整數(shù)轉(zhuǎn)換為二至九進制之間的任一進制數(shù)輸出?！窘獯稹克惴ɑ谠恚篘=(N div d) d+ N mo

49、d d （div 為整除運算， mod 為求余運算）。11假設(shè)一個算術(shù)表達式中可以包含三種括號：圓括號“（”和“）”，方括號“ ”和“”以及花括號“ ”和“ ”，且這三種括號可按任意的次序嵌套使用。編寫算法判斷給定表達式中所含括號是否配對出現(xiàn)?！窘獯稹考僭O(shè)表達式已存入字符數(shù)組An中，具體算法如下：第 4 章 廣義線性表 多維數(shù)組和廣義表課后習題講解填空數(shù)組通常只有兩種運算：（ ）和（ ），這決定了數(shù)組通常采用（）結(jié)構(gòu)來實現(xiàn)存儲?！窘獯稹看嫒。薷?，順序存儲【分析】數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種

50、操作。二維數(shù)組A 中行下標從 10 到 20，列下標從 5 到 10，按行優(yōu)先存儲，每個元素占 4個存儲單元， A105的存儲地址是 1000，則元素 A1510的存儲地址是（ ）?！窘獯稹?1140【分析】數(shù)組 A 中每行共有 6 個元素，元素 A1510的前面共存儲了 (15-10) 6+5個元素，每個元素占 4個存儲單元，所以，其存儲地址是1000+140=1140。設(shè)有一個10 階的對稱矩陣 A 采用壓縮存儲， A00為第一個元素，其存儲地址為 d，每個元素占 1 個 存儲單元，則元素 A85的存儲地址為（）。【解答】 d+41【分析】元素 A85的前面共存儲了(1+2+8)+5=41

51、個元素。稀疏矩陣一般壓縮存儲方法有兩種，分別是（）和（ ）?！窘獯稹咳M順序表，十字鏈表廣義表(a), (b),c),(d)的長度是（），深度是（），表頭是（），表尾是（）。【解答】 3，4，(a)，(b),c),(d)已知廣義表LS=(a，(b，c，d)，e)，用 Head 和 Tail 函數(shù)取出 LS 中原子 b 的運算是（ ）?！窘獯稹?Head(Head(Tail(LS)選擇題二維數(shù)組 A 的每個元素是由6 個字符組成的串，行下標的范圍從08，列下標的范圍是從 09，則存 放 A 至少需要（）個字節(jié)， A 的第 8 列和第 5 行共占（）個字節(jié)，若 A 按行優(yōu)先方式存儲，元素 A85

52、的起始地址與當 A 按列優(yōu)先方式存儲時的（）元素的起始地址一致。A90B180C240D540E108F114G54H A85 I A310 J A58 K A49【解答】 D，E，K【分析】數(shù)組 A 為 9 行 10 列，共有 90 個元素，所以，存放A 至少需要 90 6=540個存儲單元，第8 列 和第 5 行共有 18 個元素（注意行列有一個交叉元素），所以，共占 108 個字節(jié)，元素 A85按行優(yōu)先存 儲的起始地址為 d+8 10+5=d+85，設(shè)元素 Aij 按列優(yōu)先存儲的起始地址與之相同， 則 d+j 9+i=d+85，解此方程，得 i=4，j=9。將數(shù)組稱為隨機存取結(jié)構(gòu)是因為（

53、）A 數(shù)組元素是隨機的B 對數(shù)組任一元素的存取時間是相等的C 隨時可以對數(shù)組進行訪問D 數(shù)組的存儲結(jié)構(gòu)是不定【解答】 B下面的說法中，不正確的是（ ）A 數(shù)組是一種線性結(jié)構(gòu)B 數(shù)組是一種定長的線性結(jié)構(gòu)除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等數(shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操【解答】 C【分析】數(shù)組屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)和每維中的元素個數(shù)是確定的，所以，數(shù)組通常沒有插入和刪除操作。對特殊矩陣采用壓縮存儲的目的主要是為了（）A 表達變得簡單 B 對矩陣元素的存取變得簡單C 去掉矩陣中的多余元素D 減少不必要的存儲空間【解答】 D【分析

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

55、陣只須存放非零元素即可。稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲。稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲【解答】 D【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲。如果零元素的分布有規(guī)律，就沒有必要存儲非零元素的行號和列號，而需要按其壓縮規(guī)律找出相應的映象函數(shù)。判斷題 數(shù)組是一種復雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的?！窘獯稹垮e。例如二維數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。使用三元組表存儲稀疏矩陣的元素，有時并不能節(jié)省存儲空間?！窘獯稹繉?。因為三元組表除了存儲非零元素值外，還需要存儲其行號和列號。稀疏矩

56、陣壓縮存儲后，必會失去隨機存取功能。【解答】對。因為壓縮存儲后，非零元素的存儲位置和行號、列號之間失去了確定的關(guān)系。線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是單元素，則廣義表便成為線性表?！窘獯稹繉?。若一個廣義表的表頭為空表，則此廣義表亦為空表?！窘獯稹垮e。如廣義表L=( )，(a，b)的表頭為空表，但 L 不是空表。4一個稀疏矩陣如圖 4-4 所示，寫出對應的三元組順序表和十字鏈表存儲表示?！窘獯稹繉娜M順序表如圖4-5 所示，十字鏈表如圖 4-6 所示。5已知 A 為稀疏矩陣，試從空間和時間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲結(jié)構(gòu)完成求 運算的優(yōu)缺點?！窘獯?/p>

57、】設(shè)稀疏矩陣為 m 行 n 列，如果采用二維數(shù)組存儲，其空間復雜度為(mn)；因為要將所有的矩陣元素累加起來，所以，需要用一個兩層的嵌套循環(huán)，其時間復雜度亦為(mn)。如果采用三元組順序表進行壓縮存儲，假設(shè)矩陣中有t 個非零元素，其空間復雜度為(t)，將所有的矩陣元素累加起來只需將三元組順序表掃描一遍，其時間復雜度亦為(t)。當 t0）個結(jié)點的滿二叉樹共有（ ）個葉子 結(jié)點和（ ）個非終端結(jié)點?！窘獯稹?2i-1， (n+1)/2 ，(n-1)/2【分析】設(shè)滿二叉樹中葉子結(jié)點的個數(shù)為n0，度為 2 的結(jié)點個數(shù)為 n2，由于滿二叉樹中不存在度為 1 的 結(jié)點，所以 n=n0+n2 ；由二叉樹的性

58、質(zhì) n0=n2+1，得n0=(n+1)/2 ，n2=(n-1)/2 。設(shè)高度為h 的二叉樹上只有度為 0 和度為 2 的結(jié)點，該二叉樹的結(jié)點數(shù)可能達到的最大值是（），最 小值是（ ）。【解答】 2h -1， 2h-1【分析】最小結(jié)點個數(shù)的情況是第1 層有 1 個結(jié)點，其他層上都只有2 個結(jié)點。深度為k 的二叉樹中，所含葉子的個數(shù)最多為（）?！窘獯稹?2k-1【分析】在滿二叉樹中葉子結(jié)點的個數(shù)達到最多。具有100 個結(jié)點的完全二叉樹的葉子結(jié)點數(shù)為（）?！窘獯稹?50【分析】100 個結(jié)點的完全二叉樹中最后一個結(jié)點的編號為100，其雙親即最后一個分支結(jié)點的編號為 50， 也就是說，從編號 51 開

59、始均為葉子。已知一棵度為3 的樹有 2 個度為 1 的結(jié)點， 3 個度為 2 的結(jié)點， 4 個度為 3 的結(jié)點。則該樹中有（） 個葉子結(jié)點?！窘獯稹?12【分析】根據(jù)二叉樹性質(zhì)3 的證明過程，有 n0=n2+2n3+1（ n0、n2、n3 分別為葉子結(jié)點、度為 2 的結(jié)點 和度為 3 的結(jié)點的個數(shù)）。某二叉樹的前序遍歷序列是 ABCDEFG ，中序遍歷序列是 CBDAFGE ，則其后序遍歷序列是（）?！窘獯稹?CDBGFEA【分析】根據(jù)前序遍歷序列和后序遍歷序列將該二叉樹構(gòu)造出來。 在具有n 個結(jié)點的二叉鏈表中，共有（ ）個指針域，其中（ ）個指針域用于指向其左右孩子，剩下的（ ）個指針域則是

60、空的。【解答】 2n，n-1，n+110） 在有 n 個葉子的哈夫曼樹中，葉子結(jié)點總數(shù)為（ ），分支結(jié)點總數(shù)為）?！窘獯稹?n， n-1【分析】 n-1 個分支結(jié)點是經(jīng)過 n-1 次合并后得到的。選擇題如果結(jié)點A 有 3 個兄弟， B 是 A 的雙親，則結(jié)點 B 的度是（）。A1B2C3D4【解答】 D設(shè)二叉樹有n 個結(jié)點，則其深度為（）。An-1BnC+1D 不能確定【解答】 D【分析】此題并沒有指明是完全二叉樹，則其深度最多是n，最少是+1 。二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A 空或只有一個結(jié)點B 高度等于其結(jié)點數(shù)C 任一結(jié)點無左孩子D 任一結(jié)點無右孩子【