數(shù)據(jù)結(jié)構(gòu)各章習(xí)題

1、數(shù)據(jù)結(jié)構(gòu)各章習(xí)題第1章 緒論一、名詞解釋 數(shù)據(jù)   數(shù)據(jù)項(xiàng)   數(shù)據(jù)元素   數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)邏輯結(jié)構(gòu)   數(shù)據(jù)物理結(jié)構(gòu)   算法 算法的時(shí)間復(fù)雜性二、單項(xiàng)選擇題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中,數(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

2、上的 有限集合。 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. 算法分析的目的是 ，算法分析的兩個(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.算法指的是 。A. 計(jì)算方法 B. 排序方法C. 解決問(wèn)題的有限運(yùn)算序列 D. 調(diào)度方法6. 數(shù)據(jù)在計(jì)

3、算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱之為（ ）。A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu) C.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.順序存儲(chǔ)結(jié)構(gòu)三、 填空題（將正確的答案填在相應(yīng)的空中）1. 數(shù)據(jù)邏輯結(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. 在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 個(gè)直接前驅(qū)結(jié)點(diǎn)，葉子結(jié)點(diǎn)沒(méi)有 結(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)系，樹(shù)形結(jié)構(gòu)中元素之間存在 關(guān)系，

4、圖形結(jié)構(gòu)中元素之間存在 關(guān)系。6. 算法的五個(gè)重要特性是_ _ , _ _ , _ _ , _ _ , _ _。四、分析下列算法的時(shí)間復(fù)雜度: 1sum=0; for (i=1;i<=n;i+) sum=sum+i; 2i=1; while(i<=n) i=i*10;3sum=0; for(i=0;i<n;i+) for(j=0;j<n;j+) sum=sum+Arrayij;4 s =0;for( I =0; i<n; i+) for(j=0;j<n;j+)s +=Bij;sum = s ;5 for( i =0; i<n; i+) for(j=0;

5、j<m;j+)Aij 0;6 i 0；while（i<=n）i = i * 3；第2章 線性表 一、 單項(xiàng)選擇題1. 一個(gè)向量（即一批地址連續(xù)的存儲(chǔ)單元）第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是_ _。 A. 110 B. 108 C. 100 D. 1202. 線性表的邏輯順序與存儲(chǔ)順序總是一致的，這種說(shuō)法_ _。A. 正確 B. 不正確3. 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址_ _。A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的C. 一定是不連續(xù)的 D. 連續(xù)或不連續(xù)都可以4. 在以下的敘述中，正確的是_ _。A.線性表的順序

6、存儲(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)5.在等概率情況下，順序表的插入操作要移動(dòng)_結(jié)點(diǎn)。  A全部 B一半  C三分之一   D四分之一 6. 不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是_。A. head= =NULL B. head->next= =NULLC. head->next= =head D. head!=NULL7. 帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是_。A. head= =NULL B. h

7、ead->next= =NULLC. head->next= =head D. head!=NULL8. 非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足_。A. p->next= =NULL B. p= =NULLC. p->next= =head D. p= =head 9. 在一個(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;B. q->next=s; s->

8、;next=p; C. p->next=s; s->next=q;10. 在一個(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; p->next=s;C. s->next=p->next; p=s; C. p->next=s; s->next=p;11. 在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行_。A. p->next= p->next->next； B. p= p->next; p-&

9、gt;next= p->next->next；C. p->next= p->next; D. p= p->next->next；12. 從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較_個(gè)結(jié)點(diǎn)。A. n B. n/2 C. (n-1)/2 D. (n+1)/213. 在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是_ _。A. O(1) B. O(n) C. O (n2) D. O (nlog2n)14. 給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是_ _。A. O(1)） B. O(n) C.

10、 O (n2) D. O (n*log2n)15.在n個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是O（1）的操作是 。A訪問(wèn)第i（1<=i<=n）個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（1<i<=n）B在第i（1<=i<=n）個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C刪除第i（1<=i<=n）個(gè)結(jié)點(diǎn)D以上都不對(duì)二、 填空題 1. 單鏈表可以做_ _的鏈接存儲(chǔ)表示。2. 在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向_ _，另一個(gè)指向_ _。3. 在一個(gè)單鏈表中p所指結(jié)點(diǎn)之前插入一個(gè)s (值為e)所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作：q=head;while (q->next!=

11、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)，應(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)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是_ _。三、簡(jiǎn)答 1. 算法分

12、析的目的是什么？2. 什么是算法的最壞和平均時(shí)間復(fù)雜性？3. 什么是線性表？線性表的主要運(yùn)算有哪些？4. 試比較順序表與鏈表的優(yōu)缺點(diǎn)。5. 寫(xiě)出在單鏈表L中的p所指結(jié)點(diǎn)之前插入一個(gè)s所指結(jié)點(diǎn)的操作。 四、算法題 1. 設(shè)順序表La中的數(shù)據(jù)元數(shù)遞增有序。試寫(xiě)一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。2、寫(xiě)算法：在順序表L中找到最小的元素，并將其與原來(lái)第一個(gè)元素?fù)Q位置，顯示改變后的順序表。3、寫(xiě)算法：在單鏈表L中找到最小的元素，并將其與原來(lái)第一個(gè)元素?fù)Q位置，顯示改變后的單鏈表。4. 設(shè)計(jì)一個(gè)函數(shù)，查找單鏈表中數(shù)值為x的結(jié)點(diǎn)。 5. 已知一個(gè)單鏈表，編寫(xiě)一個(gè)刪除其值為x的結(jié)點(diǎn)的算法。

13、 6. 已知一個(gè)遞增有序的單鏈表，編寫(xiě)一個(gè)函數(shù)向該單鏈表中插入一個(gè)元素為x的結(jié)點(diǎn)，使插入后該鏈表仍然遞增有序。7. 試寫(xiě)一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲(chǔ)空間將線性表（a1, a2,. an）逆置為(an, an-1,., a1)。8. 試寫(xiě)一算法，實(shí)現(xiàn)單鏈表的就地逆置(要求在原鏈表上進(jìn)行)。*9. 已知一個(gè)單鏈表，編寫(xiě)一個(gè)函數(shù)從此單鏈表中刪除自第i個(gè)元素起的中k個(gè)元素*10. 有一個(gè)共10個(gè)結(jié)點(diǎn)的單鏈表，試設(shè)計(jì)一個(gè)函數(shù)將此單鏈表分為兩個(gè)結(jié)點(diǎn)數(shù)相等的單鏈表。 *11. 已知一個(gè)指針p指向單循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，編寫(xiě)一個(gè)對(duì)此單循環(huán)鏈表進(jìn)行遍歷的算法。 *12. 一個(gè)順序表中的元素為全

14、部為正或者負(fù)整數(shù)，試設(shè)計(jì)一算法，在盡可能少的時(shí)間內(nèi)重排該表，將正、負(fù)整數(shù)分開(kāi)，使順序表中所有負(fù)整數(shù)在正整數(shù)前面。 *13. 已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫(xiě)一算法，刪除表中所有大于x且小于y的元素（若表中存在這樣的元素）同時(shí)釋放被刪除結(jié)點(diǎn)空間。第3章 棧和隊(duì)列一 單項(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為_(kāi) _。 A. i B. n=i C. n-i+

15、1 D. 不確定3. 棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是_ _。4. 判定一個(gè)順序棧ST（最多元素為m）為空的條件是_ _。5. 判定一個(gè)順序棧ST（最多元素為m）為棧滿的條件是_ _。6. 棧的特點(diǎn)是_，隊(duì)列的特點(diǎn)是_。 A. 先進(jìn)先出 B. 先進(jìn)后出 7. 一個(gè)隊(duì)列的數(shù)據(jù)入列序列是1，2，3，4，則隊(duì)列的出隊(duì)時(shí)輸出序列是_ _ 。 8. 判定一個(gè)循環(huán)隊(duì)列Q（最多元素為m）為空的條件是 _ _,為滿的條件是_ _。9. 循環(huán)隊(duì)列用數(shù)組A0，m-1存放其元素值，已知其頭尾指針?lè)謩e是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是_。A. (rear-front+m)%m B. rear-front+

16、1C. rear-front-1 D. rear-front10. 棧和隊(duì)列的共同點(diǎn)是_ _。A. 都是先進(jìn)后出 B. 都是先進(jìn)先出C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒(méi)有共同點(diǎn)二 填空題（將正確的答案填在相應(yīng)的空中）1. 向量（數(shù)組）、棧和隊(duì)列都是_ _結(jié)構(gòu)，可以在向量的_ _位置插入和刪除元素；對(duì)于棧只能在_ _插入和刪除元素；對(duì)于隊(duì)列只能在_ _插入元素和_ _刪除元素。2. 向棧中壓入元素的操作是_ _。對(duì)棧進(jìn)行退棧時(shí)的操作是_ _。（寫(xiě)涵數(shù)調(diào)用語(yǔ)句）3. 在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的_ _。4. 從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是_ _。（寫(xiě)涵數(shù)調(diào)用語(yǔ)句）三、簡(jiǎn)答

17、題 1. 什么是棧？什么是隊(duì)列？它們各自的特點(diǎn)是什么？ 2. 線性表、棧、隊(duì)列有什么異同？ 3. 簡(jiǎn)述棧的入棧、出棧操作的過(guò)程。（用文字描述） 4. 在循環(huán)隊(duì)列中簡(jiǎn)述入隊(duì)、出隊(duì)操作的過(guò)程。（用文字描述） 5. 在什么情況下，會(huì)選擇使用?；蜿?duì)列數(shù)據(jù)結(jié)構(gòu)？ 6. 順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？四、讀棧隊(duì)相關(guān)的程序，寫(xiě)出程序的運(yùn)行結(jié)果五、算法設(shè)計(jì)題 1. 輸入一個(gè)任意的非負(fù)十進(jìn)制整數(shù),輸出與其等值的八進(jìn)值數(shù)。2. 試寫(xiě)一個(gè)算法判別讀入的一個(gè)以為結(jié)束符的字符序列是否是“回文”。 3. 設(shè)計(jì)一算法能判斷一個(gè)算術(shù)表達(dá)式中的圓括號(hào)配對(duì)是否正確。（提示：對(duì)表達(dá)式進(jìn)行掃描，凡遇到“

18、（”就進(jìn)棧，遇到“）”就退出棧頂?shù)摹埃ā保磉_(dá)式掃描完畢時(shí)棧若為空則圓括號(hào)配對(duì)正確。 第5章 樹(shù)與二叉樹(shù)一、 單項(xiàng)選擇題1.樹(shù)最適合用來(lái)表示_ _。A. 有序數(shù)據(jù)元素 B. 無(wú)序數(shù)據(jù)元素 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無(wú)聯(lián)系的數(shù)據(jù)2.假定在一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為 個(gè)。 A15 B16 C17 D473. 按照二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的不同形狀的二叉樹(shù)有_ _種。A. 3 B. 4 C. 5 D. 65. 深度為5的二叉樹(shù)至多有_ _個(gè)結(jié)點(diǎn)。A. 16 B. 32 C. 31 D. 106. 如果某二叉樹(shù)的前根次序遍歷結(jié)果為

19、stuwv，中序遍歷為uwtvs，那么該二叉樹(shù)的后序?yàn)開(kāi) _。 A. uwvts B. vwuts C. wuvts D. wutsv7. 二叉樹(shù)的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說(shuō)法_ _。 A. 正確 B. 錯(cuò)誤8. 某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是_ _。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca9. 在一非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊_。A. 只有右子樹(shù)上的所有結(jié)點(diǎn) B. 只有右子樹(shù)上的部分結(jié)點(diǎn)C. 只有左子樹(shù)上的

20、部分結(jié)點(diǎn) D. 只有左子樹(shù)上的所有結(jié)點(diǎn) 10. 一棵二叉樹(shù)如圖6.1所示，其中序遍歷的序列為 _。agedbchf圖6.1A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh11設(shè)a,b為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是 。Aa在b的右方Ba在b的左方 Ca是b的祖先 Da是b的子孫12. 已知某二叉樹(shù)的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是_ _。 A. acbed B. decab C. deabc D. cedba13.已知一棵完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)為9個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為 。A. 1 B.

21、 2C. 3D. 414. 如圖6.2所示的4棵二叉樹(shù)，_不是完全二叉樹(shù)。(A) (B) (C) (D)圖6.2二、 填空題（將正確的答案填在相應(yīng)的空中） 1. 將樹(shù)轉(zhuǎn)化為二叉樹(shù)的基本目的是_ _。 2. 深度為k的完全二叉樹(shù)至少有_ _個(gè)結(jié)點(diǎn)。至多有_ _個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號(hào)（從1開(kāi)始），則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是 _。3. 在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為 n2，則有n0=_ _。4. 一棵二叉樹(shù)的第i（i1）層最多有_ _個(gè)結(jié)點(diǎn)；一棵有n（n>0）個(gè)結(jié)點(diǎn)的滿二叉樹(shù)共有_ _個(gè)葉子和_ _個(gè)非終端結(jié)點(diǎn)。iaedbchHf圖6.3

22、 一棵二叉樹(shù)gi5. 哈夫曼樹(shù)是指_的二叉樹(shù)6. 有如圖6.3所示的二叉樹(shù)，回答以下問(wèn)題： 其中序遍歷序列為_(kāi)； 其前序遍歷序列為_(kāi)； 其后序遍歷序列為_(kāi)；三、應(yīng)用題1.分別寫(xiě)出下圖所示二叉樹(shù)的前序、中序和后序遍歷序列。 2. 若二叉樹(shù)中各結(jié)點(diǎn)值均不相同。 1)已知一個(gè)二叉樹(shù)的中序和后序遍歷序列分別為GDHBAECIF和GHDBEIFCA，請(qǐng)畫(huà)出此二叉樹(shù)。 2)已知一個(gè)二叉樹(shù)的前序和中序分別為ABCDEFGH和BDCEAFHG，請(qǐng)畫(huà)出此二叉樹(shù)。 3. 一個(gè)二叉樹(shù)如圖所示,將其轉(zhuǎn)換為樹(shù)。iaedbchHf圖6.4 一棵二叉樹(shù)gi 4畫(huà)出該森林對(duì)應(yīng)的二叉樹(shù)。ABDEFCGHJIKNOML圖6.5

23、森林5有一份電文中共使用5個(gè)字符：a、b、c、d、e，它們的出現(xiàn)頻率依次為5、2、1、6、4；試畫(huà)出對(duì)應(yīng)的哈夫曼樹(shù)，并求出每個(gè)字符的哈夫曼編碼。 四、算法設(shè)計(jì)題 1. 一個(gè)二叉樹(shù)以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)，分別給出求二叉樹(shù)結(jié)點(diǎn)總數(shù)和葉子結(jié)點(diǎn)總數(shù)和高度的算法。 2. 一個(gè)二叉樹(shù)以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)，寫(xiě)出在二叉樹(shù)中查找值為x的結(jié)點(diǎn)的算法。 3. 設(shè)計(jì)算法將一個(gè)以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的二叉樹(shù)進(jìn)行各種遍歷第6章 圖 一、單項(xiàng)選擇題1在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_倍。A. 1/2 B. 1 C. 2 D. 4 2任何一個(gè)無(wú)向連通圖的最小生成樹(shù) 。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3在一個(gè)有向

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

25、 n-1 D. n*n9對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的大小為_(kāi)；所有鄰接表中的接點(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)序列為_(kāi)；按寬度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_(kāi)。 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

26、,c,f,d,e,bbaecdf圖 6.1 一個(gè)無(wú)向圖11已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖6.2所示。12345324524圖6.2 一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu) 根據(jù)有向圖的深度優(yōu)先遍歷算法，從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)先遍歷算法，從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)

27、先遍歷算法類似于二叉樹(shù)的_。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷13采用鄰接表存儲(chǔ)的圖的寬度優(yōu)先遍歷算法類似于二叉樹(shù)的_。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷15在圖6.3所示的拓樸排列的結(jié)果序列為 。A.125634B.516234C.123456D.521634圖6.3有向圖16一個(gè)有n個(gè)頂點(diǎn)的無(wú)向連通圖，它所包含的連通分量個(gè)數(shù)為 。A.0B.1C.nD.n+117對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1,、出度為k2，則對(duì)應(yīng)鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為 。A.k1B.k2C.k1-k2D.k1+k218對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度

28、為k1,、出度為k2，則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為 。A.k1B.k2C.k1-k2D.k1+k2二、基本知識(shí)題 1. 圖的邏輯結(jié)構(gòu)特點(diǎn)是什么？什么是無(wú)向圖和有向圖？什么是子圖？什么是網(wǎng)絡(luò)？ 什么是完全圖，生成樹(shù)？2. 什么是頂點(diǎn)的度？什么是路徑？什么是連通圖和非連通圖？什么是非連通圖的連通分量？ 3. 給出圖所示的無(wú)向圖G的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)。 4. 假設(shè)圖的頂點(diǎn)是A、B請(qǐng)根據(jù)下面的鄰接矩陣畫(huà)出相應(yīng)的無(wú)向圖或有向圖。5. 分別給出圖所示G圖的深度優(yōu)先搜索和廣度優(yōu)先搜索得到的頂點(diǎn)訪問(wèn)序列。 6. 應(yīng)用prim算法求圖所示帶權(quán)連通圖的最小生成樹(shù)。 7. 寫(xiě)出圖所示有向圖的拓

29、樸排序序列。 8在無(wú)權(quán)圖G的鄰接矩陣A中，若(vi,vj)或vi,vj屬于圖G的邊集合，則對(duì)應(yīng)元素Aij等于_，否則等于_。9在無(wú)向圖G的鄰接矩陣A中，若Aij等于1，則Aji 等于_。 10已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是_ _。11已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是_ _。12如果含n個(gè)頂點(diǎn)的圖形成一個(gè)環(huán)，則它有 棵生成樹(shù)。三、算法設(shè)計(jì)題 1. 如圖1所示圖G，建立其對(duì)應(yīng)的鄰接表存儲(chǔ)，并寫(xiě)出深度優(yōu)先算法。 2. 如圖1所示圖G，建立其對(duì)應(yīng)的的鄰接矩陣存儲(chǔ)，并寫(xiě)出廣度優(yōu)先算法。 圖13. 編寫(xiě)一個(gè)函數(shù) 建立一個(gè)有向圖的鄰接表。 4. 編寫(xiě)

30、一個(gè)無(wú)向圖的鄰接矩陣轉(zhuǎn)換成鄰接表的算法。第7章 查找一、基礎(chǔ)知識(shí)題 1. 解釋下列名詞 (1) 查找     (2) 樹(shù)型查找    (3) 平衡因子 (4) 散列函數(shù)    (5) 沖突 2. 設(shè)有序表為a,b,c,d,e,f,g，請(qǐng)分別畫(huà)出對(duì)給定值f,g和h進(jìn)行拆半查找的過(guò)程。 3. 試述順序查找法、二分查找法和分塊查找法對(duì)被查找表中元素的要求，每種查找法對(duì)長(zhǎng)度為n的表的等概率查找長(zhǎng)度是多少？4.順序查找法的平均查找長(zhǎng)度為_(kāi) _；折半查找法的平均查找長(zhǎng)度為_(kāi) _；哈希表查

31、找法采用鏈接法處理沖突時(shí)的平均查找長(zhǎng)度為_(kāi) _。5.在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是_。6.折半查找的存儲(chǔ)結(jié)構(gòu)僅限于_ _，且是_ _。7.假設(shè)在有序線性表A1.20上進(jìn)行折半查找 ，則比較一次查找成功的結(jié)點(diǎn)數(shù)為_(kāi)，則比較二次查找成功的結(jié)點(diǎn)數(shù)為_(kāi)，則比較三次查找成功的結(jié)點(diǎn)數(shù)為_(kāi)，則比較四次查找成功的結(jié)點(diǎn)數(shù)為_(kāi)，則比較五次查找成功的結(jié)點(diǎn)數(shù)為_(kāi)，平均查找長(zhǎng)度為_(kāi)。8. 對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為_(kāi)；若采用折半法查找，則時(shí)間復(fù)雜度為_(kāi)；9已知有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)用折半查找90時(shí)，需進(jìn)行

32、_ _次查找可確定成功；查找47時(shí)，需進(jìn)行_ _次查找成功；查找100時(shí)，需進(jìn)行_ _次查找才能確定不成功。10二叉排序樹(shù)的查找長(zhǎng)度不僅與_ _有關(guān)，也與二叉排序樹(shù)的_ _有關(guān)。11一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵_ _樹(shù)而變成一個(gè)有序樹(shù)，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。12平衡二叉排序樹(shù)上任一結(jié)點(diǎn)的平衡因子只可能是 、 或 。二、算法設(shè)計(jì)題 1. 一個(gè)鏈表的元素是從小到大排列的，試寫(xiě)出對(duì)此鏈表的查找算法，并說(shuō)明是否可以采用折半查找2. 假設(shè)二叉排序樹(shù)t的各元素值均不相同，設(shè)計(jì)一個(gè)算法按遞增次序打印各元素值。第8章 排序一、 解釋下列概念 (1) 排序 (2) 內(nèi)部排序 (3) 堆 (4

33、) 穩(wěn)定排序 二、選擇題1. 在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是_。A. 希爾排序 B. 起泡排序 C. 插入排序 D. 選擇排序2. 設(shè)有1000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用_排序法。A. 起泡排序 B. 快速排序 C. 堆排序 D. 基數(shù)排序3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是_。A. 直接插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序4. 一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始大頂堆為_(kāi)。A. 79，46，56，38，40，80 B. 3

34、8，46, 56，79， 40，84，C. 84，79，56，38，40，46 D. 84，56，79，40，46，385. 一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為_(kāi)。A. 38，40，46，56，79，84 B. 40，38，46，79，56，84C. 40，38，46，56，79，84 D. 40，38，46，84，56，796. 一組記錄的排序碼為（25，48，16，35，79，82，23，40，36，72），其中含有5個(gè)長(zhǎng)度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為_(kāi) _。A. 16，25，35，48，23，40，79，82，36，72 B. 16，25，35，48，79，82，23，36，40，72C. 16，25，48，35，79，82，23，36，40，72D. 16，25，35，48，79，23，36，40，7