公務(wù)員-計(jì)算機(jī)類 數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題

1、習(xí) 題 一 緒 論.1.1 單項(xiàng)選擇題 1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 A 以及它們之間的 B 和運(yùn)算等的學(xué)科。 A操作對(duì)象計(jì)算方法邏輯存儲(chǔ)數(shù)據(jù)映象 A結(jié)構(gòu) 關(guān)系 運(yùn)算 算法2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（K，R），其中K是 B 的有限集合，R是K上的D 有限集合。 A算法 數(shù)據(jù)元素 數(shù)據(jù)操作 邏輯結(jié)構(gòu) A操作 映象 存儲(chǔ) 關(guān)系 3. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 C 。A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4. 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種 A 的存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種 B 的存儲(chǔ)結(jié)構(gòu)。A隨機(jī)存取

2、 B順序存取 C索引存取 D散列存取5. 算法分析的目的是 C ，算法分析的兩個(gè)主要方面是 A 。 A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B. 研究算法中的輸入和輸出的關(guān)系C. 分析算法的效率以求改進(jìn) D. 分析算法的易懂性和文檔性 A. 空間復(fù)雜性和時(shí)間復(fù)雜性 B. 正確性和簡明性C. 可讀性和文檔性 D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 6. 計(jì)算機(jī)算法指的是 C ，它必具備輸入、輸出和 B 等五個(gè)特性。 A. 計(jì)算方法 B. 排序方法C. 解決問題的有限運(yùn)算序列 D. 調(diào)度方法 A. 可行性、可移植性和可擴(kuò)充性 B. 可行性、確定性和有窮性 C. 確定性、有窮性和穩(wěn)定性 D. 易讀性、穩(wěn)定性和安全性7.

3、線性表的邏輯順序與存儲(chǔ)順序總是一致的，這種說法 B 。A. 正確 B. 不正確8. 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址 D 。A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的C. 一定是不連續(xù)的 D. 連續(xù)或不連續(xù)都可以9. 在以下的敘述中，正確的是 B 。A. 線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B. 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C. 棧的操作方式是先進(jìn)先出D. 隊(duì)列的操作方式和先進(jìn)后出10. 每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本運(yùn)算：插入、刪除和查找，這種說法 B 。A. 正確 B. 不正確1.2 填空題（將正確的答案填在相應(yīng)的空中1. 數(shù)據(jù)邏輯結(jié)構(gòu)包括 線性結(jié)構(gòu) 、 樹

4、形結(jié)構(gòu) 和 圖形結(jié)構(gòu) 三種類型，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為 非線性結(jié)構(gòu) 。2. 在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 一 個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 沒有 后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 一 個(gè)后續(xù)結(jié)點(diǎn)。3. 在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 前驅(qū) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 一 個(gè)前驅(qū)結(jié)點(diǎn)，葉子結(jié)點(diǎn)沒有 后續(xù) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以 任意個(gè) 。4. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 任意個(gè) 。5. 線性結(jié)構(gòu)中元素之間存在 一對(duì)一 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在 多對(duì)多 關(guān)系。6. 算法的五個(gè)重要特性是 有窮性 、

5、確定性 、 可行性 、 輸入 、 輸出 。7. 下面程序段的時(shí)間復(fù)雜度是 O(m*n) 。for (i=0;i<n;i+) for (j=0;j<m;j+) Aij=0;8. 下面程序段的時(shí)間復(fù)雜度是 O (n) 。i=s=0;while (s<n) i+; /*i=i+1*/ s+=i; /*s=s+1*/9. 下面程序段的時(shí)間復(fù)雜度是 O(n2 ) 。s=0;for (i=0;i<n;i+) for (j=0;j<n;j+) s+=Bij;sum=s;10. 下面程序段的時(shí)間復(fù)雜度是 O(log3n) 。i=1;while (i<=n) i=i*3;1.

6、3 算法設(shè)計(jì)題: 1. 試寫一算法,自大到小依次輸出順序讀入的三個(gè)數(shù)X,Y和Z的值. 習(xí)題答案 1.1 1. AB 2. BD 3. C 4. AB 5. CA 6. CB 7. B 8. D 9. B 10. B1.2 1. 線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)、非線性結(jié)構(gòu) 2. 沒有、1、沒有、1 3. 前驅(qū)、1、后續(xù)、任意多個(gè) 4. 任意多個(gè) 5. 一對(duì)一、一對(duì)多、多對(duì)多 6. 有窮性、確定性、可行性、輸入、輸出 7. O（m*n） 8. O (n) 9. O (n2)10. log3n習(xí) 題 二 順序表示(線性表、棧和隊(duì)列)2.1 單項(xiàng)選擇題 1. 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元

7、素的長度為2，則第5個(gè)元素的地址是 B 。 A. 110 B. 108 C. 100 D. 120 2. 一個(gè)棧的入棧序列a，b，c，d，e，則棧的不可能的輸出序列是 C 。 A. edcba B. decba C. dceab D. abcde 3. 若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為 C 。 A. i B. n=i C. n-i+1 D. 不確定 4. 棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是 A 。A. 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B. 散列方式和索引方式C. 鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組D. 線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)5. 判定一個(gè)棧ST（最多

8、元素為m0）為空的條件是 B 。A. ST> top !=0 B. ST> top= =0C. ST> top !=m0 D. ST> top= =m06. 判定一個(gè)棧ST（最多元素為m0）為棧滿的條件是 D 。A. ST> top！=0 B. ST> top= =0C. ST> top！=m0 D. ST> top= =m0 7. 棧的特點(diǎn)是 B ，隊(duì)列的特點(diǎn)是 A 。 A. 先進(jìn)先出 B. 先進(jìn)后 8. 一個(gè)隊(duì)列的入列序列是1，2，3，4，則隊(duì)列的輸出序列是 B 。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，

9、2，4，1 9. 判定一個(gè)隊(duì)列QU（最多元素為m0）為空的條件是 C 。A. QU>rearQU>front= =m0B. QU>rearQU>front-1= =m0C. QU>front= =QU>rearD. QU>front= =QU>rear+110. 判定一個(gè)隊(duì)列QU（最多元素為m0, m0+1= =Maxsize）為滿隊(duì)列的條件是 A 。A. (QU>rear-QU>front)+ Maxsize)% Maxsize = =m0B. QU>rearQU>front-1= =m0C. QU>front=

10、=QU>rearD. QU>front= =QU>rear+111. 判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m0）為空的條件是 A 。A. QU>front= =QU>rearB. QU>front！=QU>rearC. QU>front= =（QU>rear+1）%m0D. QU>front！=（QU>rear+1）%m012. 判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是 C 。A. QU>front= =QU>rearB. QU>front！=QU>rearC. QU>front= =（Q

11、U>rear+1）%m0D. QU>front！=（QU>rear+1）%m013. 循環(huán)隊(duì)列用數(shù)組A0，m-1存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是 A 。A. (rear-front+m)%m B. rear-front+1C. rear-front-1 D. rear-front14. 棧和隊(duì)列的共同點(diǎn)是 C 。A. 都是先進(jìn)后出 B. 都是先進(jìn)先出C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒有共同點(diǎn)2.2 填空題（將正確的答案填在相應(yīng)的空中）1. 向量、棧和隊(duì)列都是 線性 結(jié)構(gòu)，可以在向量的 任何 位置插入和刪除元素；對(duì)于棧只

12、能在 棧頂 插入和刪除元素；對(duì)于隊(duì)列只能在 隊(duì)首 插入元素和 隊(duì)尾 刪除元素。2. 向一個(gè)長度為n的向量的第i個(gè)元素（1in+1）之前插入一個(gè)元素時(shí)，需向后移動(dòng) n-i+1 個(gè)元素。3. 向一個(gè)長度為n的向量中刪除第i個(gè)元素（1in）時(shí)，需向前移動(dòng) n-i 個(gè)元素。4. 向棧中壓入元素的操作是 先移動(dòng)棧頂指針，后存入元素 。5. 對(duì)棧進(jìn)行退棧時(shí)的操作是 先取出元素，后移動(dòng)棧頂指針 。6. 在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的 前一個(gè)位置 。7. 從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是 先移動(dòng)隊(duì)首元素，后取出元素 。8. 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 n-1 個(gè)元素。9. 一個(gè)棧的輸

13、入序列是12345，則棧的輸出序列43512是 不可能的 。10. 一個(gè)棧的輸入序列是12345，則棧的輸出序列12345是 可能的 。2.3 算法設(shè)計(jì)題:設(shè)順序表va中的數(shù)據(jù)元數(shù)遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。試寫一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲(chǔ)空間將線性表（a1, a2,. an）逆置為(an, an-1,., a1)。按照四則運(yùn)算加、減、乘、除和冪運(yùn)算（）優(yōu)先關(guān)系的慣例，并仿照教科書3.2節(jié)例31的格式，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程：A-B*C/D+EF 習(xí)題答案2.1 1. B 2. C 3. C 4. A

14、 5. B 6. D 7. BA 8. B 9. C 10. A 11. A 12. C 13. A 14. C 2.2 1. 線性、任何、棧頂、隊(duì)尾、隊(duì)首 2. n-i+1 3. n-i 4.先移動(dòng)棧頂指針，后存入元素 5. 先取出元素，后移動(dòng)棧頂指針 6.前一個(gè)位置 7. 先移動(dòng)隊(duì)首元素，后取出元素 8. n-1 9. 不可能的 10. 可能的習(xí) 題 三 鏈表（線性表、棧和隊(duì)列） 3.1 單項(xiàng)選擇題 1. 不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 A 。A. head= =NULL B. headnext= =NULLC. headnext= =head D. head!=NULL2.

15、帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 B 。A. head= =NULL B. headnext= =NULLC. headnext= =head D. head!=NULL3. 非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足 C 。A. pnext= =NULL B. p= =NULLC. pnext= =head D. p= =head4. 在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是 D 。A. pright=s; sleft=p; prightleft=s; sright=pright;B. pright=s; prightleft=s; sleft=p; sright=

16、pright;C. sleft=p; sright=pright; pright=s; prightleft=s;D. sleft=p; sright=pright; prightleft=s; pright=s;5. 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行 C 。A. snext=pnext; pnext=s;B. pnext=snext; snext=p;C. qnext=s; snext=p;D. pnext=s; snext=q;6. 在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行 B 。A. snext=p;

17、pnext=s;B. snext=pnext; pnext=s;C. snext=pnext; p=s;D. pnext=s; snext=p;7. 在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行 A 。A. pnext= pnextnext；B. p= pnext; pnext= pnextnext；C. pnext= pnext;D. p= pnextnext；9.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較 D 個(gè)結(jié)點(diǎn)。A. n B. n/2 C. (n-1)/2 D. (n+1)/210. 在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序

18、的時(shí)間復(fù)雜度是 B 。A. O（1） B.O（n） C. O (n2) D.O (nlog2n)11. 給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是 C 。A. O（1） B.O（n） C. O (n2) D.O (nlog2n)12. 向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，則執(zhí)行 C 。(不帶空的頭結(jié)點(diǎn))A. HSnext=s;B. snext= HSnext; HSnext=s;C. snext= HS; HS=s;D. snext= HS; HS= HSnext;13. 從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行 D。(不帶空的頭結(jié)點(diǎn))

19、A. x=HS; HS= HSnext; B. x=HSdata;C. HS= HSnext; x=HSdata; D. x=HSdata; HS= HSnext;3.2 填空題（將正確的答案填在相應(yīng)的空中） 1. 單鏈表是 線性表 的鏈接存儲(chǔ)表示。2. 可以使用 雙鏈表 表示樹形結(jié)構(gòu)。3. 在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向 前驅(qū)結(jié)點(diǎn) ，另一個(gè)指向 后續(xù)結(jié)點(diǎn) 。4. 在一個(gè)單鏈表中的p所指結(jié)點(diǎn)之前插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作： snext= pnext ; pnext=s; t=pdata; pdata= sdata ; sdata= t ;5. 在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)

20、時(shí)，應(yīng)執(zhí)行以下操作：q= pnext;pdata= pnextdata;pnext= pnextnext ;free(q);6. 帶有一個(gè)頭結(jié)點(diǎn)的單鏈表head為空的條件是 headnext= =NULL 。7. 在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行snext= pnext和pnext= s 的操作。8. 非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向），滿足條件 pnext= head 。9. 在棧頂指針為HS的鏈棧中，判定棧空的條件是 HS=NULL 。10. 對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是 O(1) ；在給定值為x的結(jié)點(diǎn)后插

21、入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是 O(n) 。3.3 算法設(shè)計(jì)題:1. 已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一算法，刪除表中所有大于x且小于y的元素（若表中存在這樣的元素）同時(shí)釋放被刪除結(jié)點(diǎn)空間。2. 試寫一算法，實(shí)現(xiàn)單鏈表的就地逆置。假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)（注意不設(shè)頭指針），試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。 習(xí)題答案 3.1 1. A 2. B 3. C 4. D 5. C 6. B 7. A 9. D 10. B 11.C 12. C 13.D 3.2 1. 線性表 2. 雙鏈表3. 前驅(qū)結(jié)點(diǎn)、后續(xù)結(jié)點(diǎn) 4. p

22、next、sdata、t 5. pnextnext 6. headnext= =NULL 7. pnext、s 8. pnext= head9. HS= =NULL11. O(1)、O（n）習(xí) 題 四 串4.1 單項(xiàng)選擇題1. 空串與空格串是相同的，這種說法 B 。A. 正確 B. 不正確2. 串是一中特殊的線性表，其特殊性體現(xiàn)在 B 。A. 可以順序存儲(chǔ) B. 數(shù)據(jù)元素是一個(gè)字符C. 可以鏈接存儲(chǔ) D. 數(shù)據(jù)元素可以是多個(gè)字符3. 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作 B 。A. 連接 B. 模式匹配C. 求子串 D. 求串長4. 設(shè)串s1=ABCDEFG，s2=PQRST，

23、函數(shù)con (x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號(hào)i的字符開始的j個(gè)字符組成的子串，len(s)返回串s的長度，則con (subs (s1,2,len (s2), subs (s1,len (s2),2)的結(jié)果串是 D 。A. BCDEF B. BCDEFGC. BCPQRST D. BCDEFEF4.2 填空題（將正確的答案填在相應(yīng)的空中）1. 串的兩種最基本的存儲(chǔ)方式是 順序存儲(chǔ)方式和鏈接存儲(chǔ)方式 。2. 兩個(gè)串相等的充分必要條件是 兩個(gè)串的長度相等且對(duì)應(yīng)位置的字符相同 。3. 空串是 零個(gè)字符的串 ，其長度等于 0 。4. 空格串是 由一個(gè)或多個(gè)空格字符

24、組成的串 ，其長度等于 其包含的空格個(gè)數(shù) 。5. 設(shè)s=IAMATEACHER,其長度是 14 。4.3 算法設(shè)計(jì)題:1編寫算法，從串s 中刪除所有和串 t相同的子串。2. 編寫算法，實(shí)現(xiàn)串的基本操作Replace(&S,T,V)。習(xí)題答案4.1 1. B 2. B 3. B 4. D 4.2 1. 順序存儲(chǔ)方式和鏈接存儲(chǔ)方式 2. 兩個(gè)串的長度相等且對(duì)應(yīng)位置的字符相同 3. 零個(gè)字符的串、零 4. 由一個(gè)或多個(gè)空格字符組成的串、其包含的空格個(gè)數(shù) 5. 14習(xí) 題 五 數(shù) 組5.1 單項(xiàng)選擇題（其中Ai.j表示下標(biāo)從i到j(luò)）1. 常對(duì)數(shù)組進(jìn)行的兩種基本操作是 C 。A. 建立與刪除 B

25、. 索引和修改C. 查找和修改 D. 查找與索引2. 二維數(shù)組M的成員是6個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元，即一個(gè)字節(jié)）組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則存放M 至少需要 D 個(gè)字節(jié)；M的第8列和第5行共占 B 個(gè)字節(jié)。 A. 90 B. 180 C. 240 D. 540 A. 108 B. 114 C. 54 D. 604. 數(shù)組A中，每個(gè)元素A的長度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是 C 。A. 80 B. 100 C.240 D. 2705. 數(shù)組A中，每個(gè)元素A的長度為3個(gè)字節(jié)，

26、行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A85的起始地址為 C 。A. SA+141 B. SA+144 C. SA+222 D. SA+2256. 數(shù)組A中，每個(gè)元素A的長度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A58的起始地址為 B 。A. SA+141 B. SA+180 C. SA+222 D. SA+2255.2 填空題（將正確的答案填在相應(yīng)的空中，其中Ai,j表示下標(biāo)從i到j(luò)）1. 已知二維數(shù)組Amn采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元

27、素的存儲(chǔ)地址是LOC(A00)，則Aij的地址是 LOC (A00)+(n*i+j)*k 。2. 二維數(shù)組A1020采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元并且A00的存儲(chǔ)地址是200，則A612的地址是 326 。3. 二維數(shù)組A10.205.10采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A105的存儲(chǔ)地址是1000，則A189的地址是 1208 。5.3 算法設(shè)計(jì)題:1. 假設(shè)稀疏矩陣A和B均以三元組順序表作為存儲(chǔ)結(jié)構(gòu)。試寫出矩陣相加的算法，另設(shè)三元組表C存放結(jié)果矩陣。2. 假設(shè)系數(shù)矩陣A和B均以三元組順序表作為存儲(chǔ)結(jié)構(gòu)。試寫出滿足以下條件的矩陣相加的算法：假設(shè)三元組順序表A的

28、空間足夠大，將矩陣B加到矩陣A上，不增加A，B之外的附加空間，你的算法能否達(dá)到O（m+n）的時(shí)間復(fù)雜度？其中m和n分別為A，B矩陣中非零元的數(shù)目。3試編寫一個(gè)以三元組形式輸出用十字鏈表表示的稀疏矩陣中非零元素及其下標(biāo)的算法。4求下列廣義表操作的結(jié)果：（1） GetTailGetHead(a,b),(c,d);（2） GetTailGetHeadGetTail(a,b),(c,d)5.利用廣義表的GetHead和GetTail操作寫出如上題的函數(shù)表達(dá)式,把原子banana分別從下列廣義表中分離出來. (1) L=(apple),(pear),(banana),orange); (2) L=(ap

29、ple,(pear,(banana),orange);習(xí)題答案 5.1 1. C 2. D,B 4. C 5. C 6. B 5.2 1. LOC (A00)+(n*i+j)*k 2. 326 3. 1208習(xí) 題 六 樹 和 二 叉 樹6.1 單項(xiàng)選擇題1. 如圖8.7所示的4棵二叉樹， C 不是完全二叉樹。2. 如圖8.8所示的4棵二叉樹， B 是平衡二叉樹。3. 在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是 B 。A. tleft=NULL B. tltag=1C. tltag=1且tleft=NULL D. 以上都不對(duì)4. 二叉樹按某種順序線索化后，任一結(jié)點(diǎn)均有指向其前驅(qū)和后續(xù)的

30、線索，這種說法 B 。A. 正確 B. 錯(cuò)誤5. 二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說法 A 。A. 正確 B. 錯(cuò)誤6. 由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2，所以二叉樹是一種特殊的樹，這種說法 B 。A. 正確 B. 錯(cuò)誤7. 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為 B 。A. 2h B. 2h-1 C. 2h+1 D. h+18. 如圖8.9所示二叉樹的中序遍歷序列是 B 。A. abcdgef B. dfebagc C. dbaefcg D. defbagc9. 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是d

31、ebac，它的前序遍歷序列是 D 。A. acbed B. decab C. deabc D. cedba10設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是 C 。Aa在b的右方Ba在b的左方Ca是b的祖先Da是b的子孫11. 假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為 B 個(gè)。A15B16C17D4712.某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是 D 。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca13. 二叉樹為

32、二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法 B 。A. 正確 B. 錯(cuò)誤14. 按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有 C 種。A. 3 B. 4 C. 5 D. 615. 一棵二叉樹如圖8.10所示，其中序遍歷的序列為 B 。A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh16. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵數(shù)對(duì)應(yīng)的二叉樹。結(jié)論 A 是正確的。A. 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序

33、列相同B. 樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同C. 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同D. 以上都不對(duì)17. 深度為5的二叉樹至多有 C 個(gè)結(jié)點(diǎn)。A. 16 B. 32 C. 31 D. 1018. 在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊 A 。A. 只有右子樹上的所有結(jié)點(diǎn) B. 只有右子樹上的部分結(jié)點(diǎn)C. 只有左子樹上的部分結(jié)點(diǎn) D. 只有左子樹上的所有結(jié)點(diǎn)19. 樹最適合用來表示 C 。A. 有序數(shù)據(jù)元素 B. 無序數(shù)據(jù)元素 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無聯(lián)系的數(shù)據(jù)20. 任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)

34、次序 A 。A. 不發(fā)生改變 B. 發(fā)生改變 C. 不能確定 D. 以上都不對(duì)21. 實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最佳方案是二叉樹采用 C 存儲(chǔ)結(jié)構(gòu)。A. 二叉鏈表 B. 廣義表存儲(chǔ)結(jié)構(gòu) C. 三叉鏈表 D. 順序存儲(chǔ)結(jié)構(gòu)22. 對(duì)一個(gè)滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h，則 D 。A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-123. 如果某二叉樹的前序?yàn)閟tuwv，中序?yàn)閡wtvs，那么該二叉樹的后序?yàn)?C 。A. uwvts B. vwuts C. wuvts D. wutsv24.具有五層結(jié)點(diǎn)的二叉平衡樹至少有 B 個(gè)結(jié)點(diǎn)。A. 1

35、0 B. 12 C. 15 D. 1725. 設(shè)n，m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是 C 。A. n在m右方 B. n是m祖先 C. n在m左方 D. n是m子孫6.2 填空題（將正確的答案填在相應(yīng)的空中）1. 有一棵樹如圖8.12所示，回答下面的問題： 這棵樹的根結(jié)點(diǎn)是 k1 ； 這棵樹的葉子結(jié)點(diǎn)是 k2、k5、k7、k4 ； 結(jié)點(diǎn)k3的度是 2 ； 這棵樹的度是 3 ； 這棵樹的深度是 4 ； 結(jié)點(diǎn)k3的子女是 k5、k6 ； 結(jié)點(diǎn)k3的父結(jié)點(diǎn)是 k1 ；2. 指出樹和二叉樹的三個(gè)主要差別 樹的結(jié)點(diǎn)個(gè)數(shù)至少為1，而二叉樹的結(jié)點(diǎn)個(gè)數(shù)可以為0 、 樹中結(jié)點(diǎn)的最大度數(shù)沒

36、有限制，而二叉樹結(jié)點(diǎn)的最大度數(shù)為2 、 樹的結(jié)點(diǎn)無左、右之分，而二叉樹的結(jié)點(diǎn)有左、右之分 。3. 從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是 樹可采用二叉樹的存儲(chǔ)結(jié)構(gòu)并利用二叉樹的已有算法解決樹的有關(guān)問題 。4. 一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)于數(shù)組t中，如圖8.13所示，則該二叉樹的鏈接表示形式為_。123456789101112131415161718192021eafdgcjlhb圖8.13 一棵二叉樹的順序存儲(chǔ)數(shù)組t5. 深度為k的完全二叉樹至少有_個(gè)結(jié)點(diǎn)。至多有_個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號(hào)（從1開始），則編號(hào)最小的葉子結(jié)點(diǎn)的

37、編號(hào)是_。6. 在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n 0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為 n 2，則有n0=_。7. 一棵二叉樹的第i（i1）層最多有_個(gè)結(jié)點(diǎn)；一棵有n（n>0）個(gè)結(jié)點(diǎn)的滿二叉樹共有_個(gè)葉子和_個(gè)非終端結(jié)點(diǎn)。8. 結(jié)點(diǎn)最少的樹為 只有一個(gè)結(jié)點(diǎn)的樹 ，結(jié)點(diǎn)最少的二叉樹為 空的二叉樹 。9. 現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有 5 種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是_。10. 根據(jù)二叉樹的定義，具有三個(gè)結(jié)點(diǎn)的二叉樹有 5 種不同的形態(tài)，它們分別是_。11. 由如圖8.17所示的二叉樹，回答以下問題： 其中序遍歷序列為 dgbaechif ； 其前序遍歷序列

38、為 abdgcefhi ； 其后序遍歷序列為 gdbeihfca ； 該二叉樹的中序線索二叉樹為_； 該二叉樹的后序線索二叉樹為_； 該二叉樹對(duì)應(yīng)的森林是_。12. 已知一棵樹如圖8.20所示，轉(zhuǎn)化為一棵二叉樹，表示為_。13. 以數(shù)據(jù)集4，5，6，7，10，12，18為結(jié)點(diǎn)權(quán)值所構(gòu)造的Huffman樹為_，其帶權(quán)路徑長度為 165 。6.3 算法設(shè)計(jì)題:1試編寫算法，對(duì)一棵以孩子-兄弟鏈表表示的樹統(tǒng)計(jì)葉子的個(gè)數(shù)。2. 一棵度為2的樹與一棵二叉樹有何區(qū)別?3. 一棵含有N個(gè)結(jié)點(diǎn)的k叉樹,可能達(dá)到的最大深度和最小深度各為多少?4. 證明:一棵滿k叉樹上的葉子結(jié)點(diǎn)數(shù)n和非葉子結(jié)點(diǎn)數(shù)n之間滿足以下關(guān)

39、系: n=(k-1)n+15. 請(qǐng)對(duì)下圖所示二叉樹進(jìn)行后序線索化，為每個(gè)空指針建立相應(yīng)的前驅(qū)或后繼線索。DHFECGGBA 6. 畫出和下列已知序列對(duì)應(yīng)的樹T： 樹的先根次序訪問序列為GFKDAIEBCHJ； 樹的后根次序訪問序列為DIAEKFCJHBFG。7. 假設(shè)用于通訊的電文僅有八個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。試為這八個(gè)字母設(shè)計(jì)哈夫曼編碼。使用0-7的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。8. 假設(shè)一棵 二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFG

40、HIJK。請(qǐng)畫出該樹。9. 編寫按層次順序（同一層自左至右）遍歷二叉樹的算法。 習(xí)題答案6.1 1. C 2. B 3. B 4. B 5. A 6. B 7. B 8. B 9. D 10. C11. B 12. D 13. B 14. C 15. B 16. A 17. C 18. A 19. C 20. A 21. C 22. D 23. C 24. B 25. C 6.2 1. k1 k2,k5,k7,k4 2 3 4 k5,k6 k1 2. 樹的結(jié)點(diǎn)個(gè)數(shù)至少為1，而二叉樹的結(jié)點(diǎn)個(gè)數(shù)可以為0；樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹結(jié)點(diǎn)的最大度數(shù)為2；樹的結(jié)點(diǎn)無左、右之分，而二叉樹的結(jié)點(diǎn)有

41、左、右之分； 3. 樹可采用二叉樹的存儲(chǔ)結(jié)構(gòu)并利用二叉樹的已有算法解決樹的有關(guān)問題 4. 如圖8.14所示 5. 2k-1 、 2k-1 、 2k-2+1 6. n2+1 7. 2i-1 2log2n+1-1 2log2n+1 1 8. 只有一個(gè)結(jié)點(diǎn)的樹；空的二叉樹9. 5；如圖8.15所示10. 5；如圖8.16所示11. djbaechif 、abdjcefhi 、jdbeihfca 、如圖8.18（左）所示 、如圖8.18（右）所示、如圖8.19所示圖 8.21 一棵樹的孩子兄弟表示12. 如圖8.21所示13. 如圖8.22所示 權(quán)值：165習(xí) 題 七 圖7.1 單項(xiàng)選擇題1. 在一個(gè)

42、圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 C 倍。A. 1/2 B. 1 C. 2 D. 4 2. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 B 倍。A. 1/2 B. 1 C. 2 D. 43. 一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有 C 條邊。A. n B. n(n-1) C. n(n-1)/2 D. 2n4. 具有4個(gè)頂點(diǎn)的無向完全圖有 A 條邊。A. 6 B. 12 C. 16 D. 205. 具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有 A 條邊才能確保是一個(gè)連通圖。A. 5 B. 6 C. 7 D. 86. 在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要 C 條邊。A. n B. n+

43、1 C. n-1 D. n/27. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是 D 。A. n B. (n-1)2 C. n-1 D. n28. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為_ A ；所有鄰接表中的接點(diǎn)總數(shù)是 C 。 A. n B. n+1 C. n-1 D. n+e A. e/2 B. e C.2e D. n+e 9. 已知一個(gè)圖如圖9.5所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為 D ；按寬度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為 B 。 A. a,b,e,c,d,f B. e,c,f,e,

44、b,d C. a,e,b,c,f,d D. a,e,d,f,c,b A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b10. 已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖9.6所示。12345324524圖9.6 一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu) 根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是 C 。A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2 根據(jù)有向圖的寬度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是 B 。A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v211. 采用鄰接表存儲(chǔ)