數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)_題目

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題（打星號(hào)內(nèi)容可以不考慮）習(xí)題1 緒論1.1 單項(xiàng)選擇題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的課程，它研究程序設(shè)計(jì)問題中數(shù)據(jù)元素的 、數(shù)據(jù)信息在計(jì)算機(jī)中的 以及一組相關(guān)的運(yùn)算等的課程。 A操作對(duì)象計(jì)算方法邏輯結(jié)構(gòu)數(shù)據(jù)映象 A存儲(chǔ)結(jié)構(gòu) 關(guān)系 運(yùn)算 算法2. 數(shù)據(jù)結(jié)構(gòu)DS(Data Struct)可以被形式地定義為DS=（D，R），其中D是 的有限集合，R是D上的 有限集合。 A算法 數(shù)據(jù)元素 數(shù)據(jù)操作 數(shù)據(jù)對(duì)象 A操作 映象 存儲(chǔ) 關(guān)系3. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 。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. 算法分析的目

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

3、種類型，樹形結(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)沒有 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 個(gè)直接前驅(qū)結(jié)點(diǎn)，葉子結(jié)點(diǎn)沒有 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的直接后續(xù)結(jié)點(diǎn)可以 。4. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 。5. 線性結(jié)構(gòu)中元素之間存在 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 關(guān)系。6. 算法的五個(gè)重要特性是_ _ , _ _ , _ _ , _ _ , _ _。7. 分析下面算法（程序段），給出最大語句頻度 ，該算法的時(shí)

4、間復(fù)雜度是_ _。for (i=0;i<n;i+) for (j=0;j<n; j+) Aij=0;8. 分析下面算法（程序段），給出最大語句頻度 ，該算法的時(shí)間復(fù)雜度是_ _。for (i=0;i<n;i+) for (j=0; j<i; j+)Aij=0;9. 分析下面算法（程序段），給出最大語句頻度 ，該算法的時(shí)間復(fù)雜度是_ _。s=0;for (i=0;i<n;i+) for (j=0;j<n;j+) for (k=0;k<n;k+) s=s+Bijk;sum=s;10. 分析下面算法（程序段）給出最大語句頻度 ，該算法的時(shí)間復(fù)雜度是_ _。i

5、=s=0;while (s<n) i+; s+=i; /s=s+i 11. 分析下面算法（程序段）給出最大語句頻度 ，該算法的時(shí)間復(fù)雜度是_ _。i=1;while (i<=n) i=i*2;習(xí)題2 線性表2.1 單項(xiàng)選擇題1. 一個(gè)向量（即一批地址連續(xù)的存儲(chǔ)單元）第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是_ _。 A. 110 B. 108 C. 100 D. 1202. 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種_ _的存儲(chǔ)結(jié)構(gòu)，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種_ _的存儲(chǔ)結(jié)構(gòu)。A隨機(jī)存取 B索引存取 C順序存取 D散列存取3. 線性表的邏輯順序與存儲(chǔ)順序總是一致的，這種說法_

6、 _。A. 正確 B. 不正確4. 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址_ _。A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的C. 一定是不連續(xù)的 D. 連續(xù)或不連續(xù)都可以5. 在以下的敘述中，正確的是_ _。A. 線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B. 線性表的順序存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況C. 線性表的鏈表存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況D. 線性表的鏈表存儲(chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)6. 每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本運(yùn)算：插入、刪除和查找，這種說法_ _。A. 正確 B. 不正確7. 不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是_。A. head=

7、=NULL B. head->next= =NULLC. head->next= =head D. head!=NULL8. 帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是_。A. head= =NULL B. head->next= =NULLC. head->next= =head D. head!=NULL9. 非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足_。A. p->next= =NULL B. p= =NULLC. p->next= =head D. p= =head 10. 在雙向循環(huán)鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是_。A. p-&g

8、t;right=s; s->left=p; p->right->left=s; s->right=p->right;B. p->right=s; p->right->left=s; s->left=p; s->right=p->right;C. s->left=p; s->right=p->right; p->right=s; p->right->left=s;D. s->left=p; s->right=p->right; p->right->left=s; p

9、->right=s; 11. 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行_。A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p;C. q->next=s; s->next=p; D. p->next=s; s->next=q;12. 在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行_。A. s->next=p; p->next=s; B. s->next=p->next

10、; p->next=s;C. s->next=p->next; p=s; C. p->next=s; s->next=p;13. 在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行_。A. p->next= p->next->next； B. p= p->next; p->next= p->next->next；C. p = p->next; D. p= p->next->next；14. 從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較_個(gè)結(jié)點(diǎn)。A. n B. n/2 C

11、. (n-1)/2 D. (n+1)/2 15. 在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是_ _。A. O(1) B. O(n) C. O (n2) D. O (nlog2n) 16. 給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是_ _。A. O(1)） B. O(n) C. O (n2) D. O (n*log2n)2.2 填空題（將正確的答案填在相應(yīng)的空中）1. 單鏈表可以做_ _的鏈接存儲(chǔ)表示。2. 在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向_ _，另一個(gè)指向_ _。3. 在一個(gè)單鏈表中p所指結(jié)點(diǎn)之前插入一個(gè)s (值為e)所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作

12、：q=head;while (q->next!=p) q=q->next;s= new Node; s->data=e;q->next= ; /填空s->next= ; /填空4. 在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：q= p->next;p->next= _ _; /填空delete ; /填空5. 在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行s->next=_ _和p->next=_的操作。 6. 對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是_ _；在給定值為x的結(jié)點(diǎn)后插

13、入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是_ _。習(xí)題3 棧和隊(duì)列3.1 單項(xiàng)選擇題1. 一個(gè)棧的入棧序列a，b，c，d，e，則棧的不可能的輸出序列是_。 A. edcba B. decba C. dceab D. abcde 2. 若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為_。 A. i B. n-i C. n-i+1 D. 不確定3. 棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是_。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)4. 判定一個(gè)順序棧ST（最多元素為m0）為空的條件是_。A. top

14、!=0 B. top= =0 C. top !=m0 D. top= =m0-15. 判定一個(gè)順序棧ST（最多元素為m0）為棧滿的條件是_。A. top！=0 B. top= =0 C. top！=m0 D. top= =m0-16. 棧的特點(diǎn)是_，隊(duì)列的特點(diǎn)是_。 A. 先進(jìn)先出 B. 先進(jìn)后出7. 向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，則執(zhí)行_ _。(不帶空的頭結(jié)點(diǎn))A. HSnext=s;B. snext= HSnext; HSnext=s;C. snext= HS; HS=s;D. snext= HS; HS= HSnext;8. 從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)

15、，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行_ _。(不帶空的頭結(jié)點(diǎn)) A. x=HS; HS= HSnext; B. x=HSdata;C. HS= HSnext; x=HSdata; D. x=HSdata; HS= HSnext;9. 一個(gè)隊(duì)列的數(shù)據(jù)入列序列是1，2，3，4，則隊(duì)列的出隊(duì)時(shí)輸出序列是_ 。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，110. 判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m0）為空的條件是_。A. rear - front= =m0 B. rear-front-1= =m0C. front= = rear D. front= = rear+1

16、11. 判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m0, m0= =Maxsize-1）為滿隊(duì)列的條件是_。A. (rear- front)+ Maxsize)% Maxsize = =m0B. rear-front-1= =m0 C. front= =rear D. front= = rear+112. 循環(huán)隊(duì)列用數(shù)組Am存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是_。A. (rear-front+m)%m B. rear-front+1C. rear-front-1 D. rear-front13. 棧和隊(duì)列的共同點(diǎn)是_。A. 都是先進(jìn)后出 B. 都是先進(jìn)先出C.

17、 只允許在端點(diǎn)處插入和刪除元素 D. 沒有共同點(diǎn)3.2 填空題（將正確的答案填在相應(yīng)的空中）1. 向量、棧和隊(duì)列都是_結(jié)構(gòu)，可以在向量的_位置插入和刪除元素；對(duì)于棧只能在_插入和刪除元素；對(duì)于隊(duì)列只能在_插入元素和_刪除元素。2. 向一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素（1in+1）之前插入一個(gè)元素時(shí)，需向后移動(dòng)_個(gè)元素。3. 向一個(gè)長(zhǎng)度為n的向量中刪除第i個(gè)元素（1in）時(shí)，需向前移動(dòng)_個(gè)元素。4. 棧頂指針指向棧頂元素，向棧中壓入元素的操作是先_，后 。5. 棧頂指針指向棧頂元素，對(duì)棧進(jìn)行退棧時(shí)的操作是先_，后 _。6. 在一個(gè)循環(huán)隊(duì)列中，隊(duì)尾指針指向隊(duì)尾元素，隊(duì)首指針指向_ 位置。7. 從循環(huán)

18、隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先_，后 _。8. 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有_個(gè)元素。9. 一個(gè)棧的輸入序列是12345，則棧的輸出序列43512是_。10. 一個(gè)棧的輸入序列是12345，則棧的輸出序列12345是_。習(xí)題5 數(shù)組和*廣義表5.1 單項(xiàng)選擇題1. 常對(duì)數(shù)組進(jìn)行的兩種基本操作是_。A. 建立與刪除 B. 索引和修改 C. 對(duì)數(shù)據(jù)元素的存取和修改 D. 查找與索引2. 二維數(shù)組M的元素是6個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元，即一個(gè)字節(jié)）組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從0到9，則存放M 至少需要_ _個(gè)字節(jié)；M數(shù)組的第8列和第5行共占_個(gè)字節(jié)。 A. 90

19、 B. 180 C. 240 D. 540 A. 108 B. 114 C. 54 D. 603. 二維數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的字節(jié)數(shù)是_。A. 80 B. 100 C.240 D. 270 4. 二維數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，數(shù)組元素A74的起始地址為_。A. SA+141 B. SA+144 C. SA+222 D. SA+225 5. 二維數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i

20、從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A47的起始地址為_。A. SA+141 B. SA+180 C. SA+222 D. SA+2255.2 填空題（將正確的答案填在相應(yīng)的空中）1. 已知二維數(shù)組Amn采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A00)，則Aij的地址是_。2. 二維數(shù)組A1020采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元并且A00的存儲(chǔ)地址是200，則A612的地址是_。3. 二維數(shù)組A10.205.10采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A105的存儲(chǔ)地址是1000，則

21、A189的地址是_。*4求下列廣義表操作的結(jié)果：(1) GetTailGetHead(a,b),c,d);(2) GetTailGetTail(a,b),c,d)*5.利用廣義表的GetHead和GetTail操作寫出如上題的函數(shù)表達(dá)式,把原子banana分別從下列廣義表中分離出來. (1) L1=(apple),(pear),(banana),orange); (2) L2=(apple,( (banana, )pear,orange);*6.畫出下面廣義表的兩種存儲(chǔ)結(jié)構(gòu)圖示(a,b),(d,( ),(e,(f)*7.寫出下圖存儲(chǔ)結(jié)構(gòu)所示的廣義表（表達(dá)式），習(xí)題6 樹和二叉樹6.1 單項(xiàng)選擇

22、題1. 有關(guān)二叉樹下列說法正確的是 A二叉樹的度為2 B一棵二叉樹的度可以小于2 C二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 D二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為22. 假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為 個(gè)。 A15 B16 C17 D473. 按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的不同形狀的二叉樹有_種。A. 3 B. 4 C. 5 D. 64. 按照二叉樹的定義，具有3個(gè)不同數(shù)據(jù)結(jié)點(diǎn)的不同的二叉樹有_種。A. 5 B. 6 C. 30 D. 325. 深度為5的二叉樹至多有_個(gè)結(jié)點(diǎn)。A. 16 B. 32 C. 31 D. 106. 設(shè)高度為h的二叉樹上只有度為0和度

23、為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為_ _。A. 2h B. 2h-1 C. 2h+1 D. h+17. 對(duì)一個(gè)滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h，則_ 。A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-18. 任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序_。A.不發(fā)生改變 B.發(fā)生改變 C.不能確定 D.以上都不對(duì)9. 如果某二叉樹的前根次序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序?yàn)開。 A. uwvts B. vwuts C. wuvts D. wutsv10. 二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)

24、點(diǎn)的前面，這種說法_。 A. 正確 B. 錯(cuò)誤11. 某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是_。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca12. 在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊_。A. 只有右子樹上的所有結(jié)點(diǎn) B. 只有右子樹上的部分結(jié)點(diǎn)C. 只有左子樹上的部分結(jié)點(diǎn) D. 只有左子樹上的所有結(jié)點(diǎn)13. 如圖6.1所示二叉樹的中序遍歷序列是_。A. abcdgef B. dfebagc C. dbaefcg D. defbagcgcefdbaaged

25、bchf圖6.2 圖6.1 14. 一棵二叉樹如圖6.2所示，其中序遍歷的序列為_ _。A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh15設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是 。Aa在b的右方Ba在b的左方Ca是b的祖先Da是b的子孫16. 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是_。 A. acbed B. decab C. deabc D. cedba17. 若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是_A9 B11 C15 D不確定 18.

26、 如圖6.3所示的4棵二叉樹，_不是完全二叉樹。(A) (B) (C) (D)圖6.319. 一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是 A 250 B 500 C254 D505 E以上答案都不對(duì) 20. 在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是_。A. tleft=NULL B. tltag=1C. tltag=1且tleft=NULL D. 以上都不對(duì)21. 二叉樹按某種順序線索化后，任一結(jié)點(diǎn)均有指向其前驅(qū)和后續(xù)的線索，這種說法_。 A. 正確 B. 錯(cuò)誤22. 二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法_。 A.

27、 正確 B. 錯(cuò)誤23. 一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為_。A11 B10 C11至1025之間 D10至1024之間24. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵數(shù)對(duì)應(yīng)的二叉樹。結(jié)論_是正確的。A.樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同B.樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同C.樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同D.以上都不對(duì)25. 樹最適合用來表示_。A. 有序數(shù)據(jù)元素 B. 無序數(shù)據(jù)元素 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間

28、無聯(lián)系的數(shù)據(jù)k1 11kkkkkk21 4356 76.2 填空題（將正確的答案填在相應(yīng)的空中）1. 有一棵樹如圖6.5所示，回答下面的問題： 這棵樹的根結(jié)點(diǎn)是_； 這棵樹的葉子結(jié)點(diǎn)是_； 結(jié)點(diǎn)k3的度是_； 這棵樹的度是_； 這棵樹的深度是_； 結(jié)點(diǎn)k3的子女是_；圖6.5 一棵樹 結(jié)點(diǎn)k3的父結(jié)點(diǎn)是_； 2. 指出樹和二叉樹的兩個(gè)主要差別_、_。3. 樹可采用 做存儲(chǔ)結(jié)構(gòu)，并利用 解決樹的有關(guān)問題。4. 一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)于數(shù)組t中，如圖6.6所示，則該二叉樹的鏈接表示形式為_ _。123456789101112131415161718192021eafdgcjlh

29、b圖6.6 一棵二叉樹的順序存儲(chǔ)數(shù)組t5. 深度為k的完全二叉樹至少有_個(gè)結(jié)點(diǎn)。至多有_個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號(hào)（從1開始），則編號(hào)最小的葉子結(jié)點(diǎn)的編號(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.一棵樹T中，包括一個(gè)度為1的結(jié)點(diǎn)，兩個(gè)度為2的結(jié)點(diǎn)，三個(gè)度為3的結(jié)點(diǎn)，四個(gè)度為4的結(jié)點(diǎn)和若干葉子結(jié)點(diǎn)，則T的葉結(jié)點(diǎn)數(shù)為_。iaedbchHf圖6.7 一棵二叉樹gi9. 現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，

30、問有_種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是_（作圖）。10. 由如圖6.7所示的二叉樹，回答以下問題： 其中序遍歷序列為_； 其前序遍歷序列為_； 其后序遍歷序列為_；11. 給定一組數(shù)據(jù)6，2，7，10，3，12以它構(gòu)造一棵哈夫曼樹，則樹高為_，帶權(quán)路徑長(zhǎng)度WPL的值為_。6.3 簡(jiǎn)答題1. 根據(jù)二叉樹的定義，具有三個(gè)結(jié)點(diǎn)的二叉樹有5種不同的形態(tài)，請(qǐng)將它們分別畫出。2. 假設(shè)一棵 二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。請(qǐng)畫出該樹。3. 由如圖6.7所示的二叉樹，回答以下問題：（1）畫出該二叉樹的中序線索二叉樹；（2）畫出該二叉樹對(duì)應(yīng)的

31、森林。gcefdba圖6.8 一棵樹4. 已知一棵樹如圖6.8所示，轉(zhuǎn)化為一棵二叉樹，表示為_5. 以數(shù)據(jù)集4，5，6，7，10，12，18為結(jié)點(diǎn)權(quán)值，畫出構(gòu)造Huffman樹的每一步圖示，計(jì)算其帶權(quán)路徑長(zhǎng)度為。6. 用一維數(shù)組存放的一棵完全二叉樹如下圖所示：ABCDEFGHIJKL寫出后序遍歷該二叉樹時(shí)訪問結(jié)點(diǎn)的順序。習(xí)題7 圖7.1 單項(xiàng)選擇題1在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_倍。A. 1/2 B. 1 C. 2 D. 4 2任何一個(gè)無向連通圖的最小生成樹 。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和

32、的_倍。A. 1/2 B. 1 C. 2 D. 44一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有_條邊。A. n B. n(n-1) C. n(n-1)/2 D. 2n5具有4個(gè)頂點(diǎn)的無向完全圖有_條邊。A. 6 B. 12 C. 16 D. 206具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有_條邊才能確保是一個(gè)連通圖。A. 5 B. 6 C. 7 D. 87在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要_條邊。A. n B. n+1 C. n-1 D. n/28對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是_。A. n B. (n-1)2 C. n-1 D. n29對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無

33、向圖，若采用鄰接表表示，則表頭向量的大小為_；所有鄰接表中的接點(diǎn)總數(shù)是_。 A. n B. n+1 C. n-1 D. n+e A. e/2 B. e C.2e D. n+e 10已知一個(gè)圖如圖7.1所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_；按寬度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_。 A. a,b,e,c,d,f B. e,c,f,e,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,bbaecdf圖 7.1 一個(gè)無向圖1

34、1已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖7.2所示。12345324524圖7.2 一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu) 根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是_。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)序列是_。A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v212采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的_。A. 先序遍歷 B

35、. 中序遍歷 C. 后序遍歷 D. 按層遍歷13采用鄰接表存儲(chǔ)的圖的寬度優(yōu)先遍歷算法類似于二叉樹的_。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷14判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用_。A. 求關(guān)鍵路徑的方法 B. 求最短路徑的Dijkstra方法C. 寬度優(yōu)先遍歷算法 D. 深度優(yōu)先遍歷算法15關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中 。A.從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B.從源點(diǎn)到匯點(diǎn)的最短路徑C.最長(zhǎng)的回路 D.最短的回路16下面不正確的說法是 。 （1）在AOE網(wǎng)中，減小一個(gè)關(guān)鍵活動(dòng)上的權(quán)值后，整個(gè)工期也就相應(yīng)減小； （2）AOE網(wǎng)工程工期為關(guān)鍵路徑上各關(guān)鍵

36、活動(dòng)的權(quán)之和； （3）在關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng)，而關(guān)鍵活動(dòng)也必在關(guān)鍵路徑上。A.（1）B.（2）C.（3）D.（1）、（2）17用DFS遍歷一個(gè)無環(huán)有向圖，并在DFS算法退棧返回時(shí)打印出相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是 。A.逆拓樸有序的B.拓樸有序的C.無序的18在圖7.3所示的拓樸排列的結(jié)果序列為 。A.125634B.516234C.123456D.521634圖7.3有向圖19一個(gè)有n個(gè)頂點(diǎn)的無向連通圖，它所包含的連通分量個(gè)數(shù)為 。A.0B.1C.nD.n+120對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1,、出度為k2，則對(duì)應(yīng)鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為 。A.k1B.k2C.k1

37、-k2D.k1+k221對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1,、出度為k2，則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為 。A.k1B.k2C.k1-k2D.k1+k27.2 填空題（將正確的答案填在相應(yīng)的空中）1n個(gè)頂點(diǎn)的連通圖至少_條邊。2在無權(quán)圖G的鄰接矩陣A中，若(vi,vj)或vi,vj屬于圖G的邊集合，則對(duì)應(yīng)元素Aij等于_，否則等于_。3在無向圖G的鄰接矩陣A中，若Aij等于1，則Aji 等于_。4已知圖G的鄰接表如圖7.4所示，其從頂點(diǎn)v1出發(fā)的深度優(yōu)先搜索序列為_，其從頂點(diǎn)v1出發(fā)的寬度優(yōu)先搜索序列為_。v1v3v2v4v5v6v2v5v4v3v5v6v4v6v3 圖7.4 圖

38、G的鄰接表5已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是_。6已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是_。7如果含n個(gè)頂點(diǎn)的圖形成一個(gè)環(huán)，則它有 棵生成樹。8一個(gè)非連通無向圖，共有28條邊，則該圖至少有 個(gè)頂點(diǎn)。9遍歷圖的過程實(shí)質(zhì)上是 。BFS遍歷圖的時(shí)間復(fù)雜度為 ，DFS遍歷圖的時(shí)間復(fù)雜度為 ，兩者不同之處在于 ，反映在數(shù)據(jù)結(jié)構(gòu)上的差別是 。10一個(gè)圖的鄰接矩陣表示法 唯一的，而鄰接表表示法 唯一的。11有向圖中的結(jié)點(diǎn)前驅(qū)后繼關(guān)系的特征是 。12若無向圖G的頂點(diǎn)度數(shù)最小值大于等于 時(shí)，G至少有一條回路。13根據(jù)圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行某種次序的遍歷，得到的頂點(diǎn)序列

39、是 的。7.3 綜合題1562431已知如圖7.5所示的有向圖，請(qǐng)給出該圖的:（1）每個(gè)頂點(diǎn)的入/出度；（2）鄰接距陣；（3）鄰接表；（4）逆鄰接表；（5）強(qiáng)連通分量。圖7。5一個(gè)有向圖2請(qǐng)用克魯斯卡爾和普里姆兩種算法分別為圖7.6、圖7.7構(gòu)造最小生成樹： badcef16111515151613141221（1） 圖7.661213212495201516106154372（2） 圖7.73試列出圖7.8中全部的拓?fù)渑判蛐蛄小?23456圖7.84請(qǐng)用圖示說明圖7.9從頂點(diǎn)a到其余各頂點(diǎn)之間的最短路徑。543223356abdfce圖7.95已知AOE網(wǎng)有9個(gè)結(jié)點(diǎn)：V1，V2，V3，V4，

40、V5，V6，V7，V8，V9，其鄰接矩陣如下：V1V2V3V4V5V6V7V8V9V1645V21V31V42V597V64V72V84V9(1)請(qǐng)畫出該AOE圖。(2)計(jì)算完成整個(gè)計(jì)劃需要的時(shí)間。(3)求出該AOE網(wǎng)的關(guān)鍵路徑。習(xí)題8 查找8.1 單項(xiàng)選擇題1.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為_的線性表。A. 散列存儲(chǔ) B. 順序存儲(chǔ)或鏈接存儲(chǔ)C. 壓縮存儲(chǔ) D. 索引存儲(chǔ)2.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須_。A. 以順序方式存儲(chǔ) B. 以鏈接方式存儲(chǔ)C. 以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序D. 以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序3.采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素

41、的平均查找長(zhǎng)度為_.A. n B. n/2 C. (n+1)/2 D. (n-1)/24.采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為_。AO（n2） B. O(nlog2n) C. O(n) D. O(log2n)5.二分查找和二叉排序樹最壞情況下的時(shí)間性能_。A. 相同 B. 不相同6.有一個(gè)有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當(dāng)二分查找值82為的結(jié)點(diǎn)時(shí)，_次比較后查找成功。A. 1 B. 2 C. 4 D. 87.設(shè)哈希表長(zhǎng)m=14，哈希函數(shù)H(key)=key%11。表中已有4個(gè)結(jié)點(diǎn)：addr (15)=4; addr

42、(38)=5; addr (61)=6; addr (84)=7如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是_。A. 8 B. 3 C. 5 D. 98.有一個(gè)長(zhǎng)度為12的有序表，按二分查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為_。A. 35/12 B. 37/12 C. 39/12 D. 43/129對(duì)于靜態(tài)表的順序查找法，若在表頭設(shè)置崗哨，則正確的查找方式為 。A.從第0個(gè)元素往后查找該數(shù)據(jù)元素B.從第1個(gè)元素往后查找該數(shù)據(jù)元素C.從第n個(gè)元素往開始前查找該數(shù)據(jù)元素D.與查找順序無關(guān)10解決散列法中出現(xiàn)的沖突問題常采用的方法是 。A.數(shù)字分析法、除

43、余法、平方取中法B.數(shù)字分析法、除余法、線性探測(cè)法C.數(shù)字分析法、線性探測(cè)法、多重散列法D.線性探測(cè)法、多重散列法、鏈地址法11采用線性探測(cè)法解決沖突問題，所產(chǎn)生的一系列后繼散列地址 。A.必須大于等于原散列地址B.必須小于等于原散列地址C.可以大于或小于但不能等于原散列地址D.地址大小沒有具體限制12對(duì)于查找表的查找過程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插入到集合中。這種方式主要適合于 。A.靜態(tài)查找表B.動(dòng)態(tài)查找表C.靜態(tài)查找表與動(dòng)態(tài)查找表D兩種表都不適合13.散列表的平均查找長(zhǎng)度 。A.與處理沖突方法有關(guān)而與表的長(zhǎng)度無關(guān)B.與處理沖突方法無關(guān)而與表的長(zhǎng)度有關(guān)C.與處理沖突方法有

44、關(guān)且與表的長(zhǎng)度有關(guān)D.與處理沖突方法無關(guān)且與表的長(zhǎng)度無關(guān)14. 分別以下列序列構(gòu)造二叉排序樹，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是( ) A（100，80，90，60，120，110，130） B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130） D. (100，80，60，90，120，130，110)15. 設(shè)有一組記錄的關(guān)鍵字為19，14，23，1，68，20，84，27，55，11，10，79，用鏈地址法構(gòu)造散列表，散列函數(shù)為H（key）=key MOD 13,散列地址為1的鏈中有（ ）個(gè)記錄。A1 B. 2 C. 3 D. 48.2 填空題（將正確的答案填在相應(yīng)的空中）1. 順序查找n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為_ _次；當(dāng)使用監(jiān)視哨時(shí)，若查找失敗，則比較關(guān)鍵字的次數(shù)為_。2.在各種查找方法中，平均查找長(zhǎng)度與表結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是_。3.折半查找的存儲(chǔ)結(jié)構(gòu)僅限于_，且是_。4. 假設(shè)在有序線性表A1.20上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為_，則比較二次查找成功的結(jié)點(diǎn)數(shù)為_，則比較三次查找成功的結(jié)點(diǎn)數(shù)為_，則比較四次查找成功的結(jié)點(diǎn)數(shù)為_，則比較五次查找成功的結(jié)點(diǎn)數(shù)為_，平均查找長(zhǎng)度為_。5. 對(duì)