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

1、數(shù)據(jù)結(jié)構(gòu)各章習(xí)題第1章緒論一、名詞解釋數(shù)據(jù)邏輯結(jié)構(gòu)數(shù)據(jù),數(shù)據(jù)元素的、數(shù)據(jù)信數(shù)據(jù) 數(shù)據(jù)項(xiàng)數(shù)據(jù)元素?cái)?shù)據(jù)結(jié)構(gòu)物理結(jié)構(gòu)算法算法的時(shí)間復(fù)雜性二、單項(xiàng)選擇題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中息在計(jì)算機(jī)中的 以及一組相關(guān)的運(yùn)算等的課程。D.數(shù)據(jù)映象D算法 A 操作對象E.計(jì)算方法C.邏輯結(jié)構(gòu) A 存儲結(jié)構(gòu)E.關(guān)系C.運(yùn)算2. 數(shù)據(jù)結(jié)構(gòu)DS(Data Struct)可以被形式地定義為 DS=(D, R),其中D是 的有限集合，R是D上的有限集合。A 算法E.數(shù)據(jù)元素C.數(shù)據(jù)操作D.數(shù)據(jù)對象15A 操作E.映象C存儲D關(guān)系3. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成。A. 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)E

2、.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4. 算法分析的目的是 ，算法分析的兩個(gè)主要方面是研究算法中的輸入和輸出的關(guān)系 分析算法的易懂性和文檔性 正確性和簡明性數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.C.分析算法的效率以求改進(jìn)D. A.空間復(fù)雜性和時(shí)間復(fù)雜性B.C.可讀性和文檔性D.5. 算法指的是A. 計(jì)算方法B.排序方法C.解決冋題的有限運(yùn)算序列D.調(diào)度方法6. 數(shù)據(jù)在計(jì)算機(jī)存儲器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱之為()A. 存儲結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.鏈?zhǔn)酱鎯Y(jié)構(gòu)D.順序存儲結(jié)構(gòu)三、填空題(將正確的答案填在相應(yīng)的空中)1. 數(shù)據(jù)邏輯結(jié)構(gòu)包括 、

3、和 四種類型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è)重要特性是 , , o四、分析下列算法的時(shí)間復(fù)雜度：1 sum=O;for (i=1;i<=n ;i+) sum=sum+i;2. i=1; while(i&l

4、t;=n) i=i*10;3. sum=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;j<m;j+)Aij二 0;6. i = 0 ;while (i<=n)i = i * 3第2章線性表一、單項(xiàng)選擇題100，每1. 一個(gè)向量（即一批地址連續(xù)的存儲單元）第一個(gè)元素的存儲地址是個(gè)元素的長度為2,則第5個(gè)元素的地址

5、是 。A. 110 B. 108 C. 100 D. 1202. 線性表的邏輯順序與存儲順序總是一致的，這種說法 。A.正確B.不正確3. 線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地址A.必須是連續(xù)的B.部分地址必須是連續(xù)的C. 一定是不連續(xù)的 D.連續(xù)或不連續(xù)都可以4. 在以下的敘述中，正確的是 。A. 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B. 線性表的順序存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況C. 線性表的鏈表存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況D. 線性表的鏈表存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)5. 在等概率情況下，順序表的插入操作要移動 吉點(diǎn)。A.全部B. 半C.三分之一D

6、.四分之一6. 不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是。A. head= =NULLB. head-> next= =NULLC. head-> next= =head D. head!=NULL7. 帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是。A. head= =NULLB. head-> next= =NULLC. head-> next= =head D. head!=NULL8. 非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)滿足。A. p-> next= =NULL B. p= =NULLC. p->n ext= =headD. p= =head

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

8、gt;n ext=s;C. s->n ext=p->n ext; p=s;C. p->n ext=s; s->n ext=p;11. 在一個(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->n ext= p->n ext;D. p= p->n ext- >n ext；12. 從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較結(jié)點(diǎn)。A.

9、n B. n/2 C. (n -1)/2D. (n+1)/213. 在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是。A. 0(1) B. 0( n) C. O (n2)D. O (nl og2 n)14. 給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是 。A. O(1) B. O(n)C. O (n2) D. O (n*log2n)15. 在n個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是O( 1)的操作A. 訪問第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)后插入

10、一個(gè)新結(jié)點(diǎn)C. 刪除第i (1<=i<=n)個(gè)結(jié)點(diǎn)D. 以上都不對二、填空題1. 單鏈表可以做 的鏈接存儲表示。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->n ext!=p) q=q->n ext;s= new Node; s->data=e;q->n ext=;/填空s->n ext= ;/4.在一個(gè)單鏈表中刪除填空p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作:q= p->n ext;填空填空p->n ext=

11、/delete ;/5. 在一個(gè)單鏈表p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)，應(yīng)執(zhí)行s->next=_ 和p->next=的操作。6. 對于一個(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ù)雜度是三、簡答1. 算法分析的目的是什么？2. 什么是算法的最壞和平均時(shí)間復(fù)雜性？3. 什么是線性表？線性表的主要運(yùn)算有哪些？4試比較順序表與鏈表的優(yōu)缺點(diǎn)。5. 寫出在單鏈表L中的p所指結(jié)點(diǎn)之前插入一個(gè)s所指結(jié)點(diǎn)的操作四、算法題1. 設(shè)順序表La中的數(shù)據(jù)元數(shù)遞增有序。試寫一算法，將x插入到順序表的適當(dāng) 位置上，以保持該表的有序

12、性。2. 寫算法：在順序表L中找到最小的元素，并將其與原來第一個(gè)元素?fù)Q位置， 顯示改變后的順序表。3. 寫算法：在單鏈表L中找到最小的元素，并將其與原來第一個(gè)元素?fù)Q位置， 顯示改變后的單鏈表。4. 設(shè)計(jì)一個(gè)函數(shù)，查找單鏈表中數(shù)值為 x的結(jié)點(diǎn)。5. 已知一個(gè)單鏈表，編寫一個(gè)刪除其值為 x的結(jié)點(diǎn)的算法。6. 已知一個(gè)遞增有序的單鏈表，編寫一個(gè)函數(shù)向該單鏈表中插入一個(gè)元素為x的結(jié)點(diǎn)，使插入后該鏈表仍然遞增有序。7. 試寫一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表(a1, a2,.an )逆置為(an, an- 1,.,a1)。8. 試寫一算法，實(shí)現(xiàn)單鏈表的就地逆置(要求在原鏈表上進(jìn)行

13、)。*9.已知一個(gè)單鏈表，編寫一個(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)，編寫一個(gè)對此單循環(huán)鏈表 進(jìn)行遍歷的算法。*12. 一個(gè)順序表中的元素為全部為正或者負(fù)整數(shù)，試設(shè)計(jì)一算法，在盡可能少 的時(shí)間內(nèi)重排該表，將正、負(fù)整數(shù)分開，使順序表中所有負(fù)整數(shù)在正整數(shù)前面。*13.已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一 算法，刪除表中所有大于x且小于y的元素(若表中存在這樣的元素)同時(shí)釋放 被刪除結(jié)點(diǎn)空間。第3章棧和隊(duì)列一單項(xiàng)選擇題1.

14、一個(gè)棧的入棧序列a, b, c, d, e,貝U棧的不可能的輸出序列是 。A. edcba B.decba C.dceab D.abcde2. 若已知一個(gè)棧的入棧序列是1,2, 3,，n,其輸出序列為p1, p2, p3,pn,若 p1= n,貝U pi 為。A. i B. n=i C. n-i+1 D.不確定3. 棧結(jié)構(gòu)通常采用的兩種存儲結(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í)輸出序列

15、是 。8. 判定一個(gè)循環(huán)隊(duì)列q （最多元素為m為空的條件是 _,為滿的條件是_。9. 循環(huán)隊(duì)列用數(shù)組A0 , m-1存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是 。A. （rear-fro nt+m）%mB. rear-fr on t+1C. rear-fr on t-1D. rear-fr ont10. 棧和隊(duì)列的共同點(diǎn)是。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D. 沒有共同點(diǎn)二 填空題（將正確的答案填在相應(yīng)的空中）1. 向量（數(shù)組）、棧和隊(duì)列都是結(jié)構(gòu)，可以在向量的位置插入和刪除元素；對于棧只能在 插入和刪除元素；對于隊(duì)列只能在

16、插入元素和刪除元素。2. 向棧中壓入元素的操作是 。對棧進(jìn)行退棧時(shí)的操作是 。（寫涵數(shù)調(diào)用語句）3. 在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的_ _ 。4. 從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是 。（寫涵數(shù)調(diào)用語句）三、簡答題1. 什么是棧？什么是隊(duì)列？它們各自的特點(diǎn)是什么？2. 線性表、棧、隊(duì)列有什么異同？3. 簡述棧的入棧、出棧操作的過程。（用文字描述）4. 在循環(huán)隊(duì)列中簡述入隊(duì)、出隊(duì)操作的過程。（用文字描述）5. 在什么情況下，會選擇使用棧或隊(duì)列數(shù)據(jù)結(jié)構(gòu)？6. 順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？四、讀棧隊(duì)相關(guān)的程序，寫出程序的運(yùn)行結(jié)果五、算法設(shè)計(jì)題1. 輸入一個(gè)

17、任意的非負(fù)十進(jìn)制整數(shù)，輸出與其等值的八進(jìn)值數(shù)。2試寫一個(gè)算法判別讀入的一個(gè)以 為結(jié)束符的字符序列是否是“回文” 00 3.設(shè)計(jì)一算法能判斷一個(gè)算術(shù)表達(dá)式中的圓括號配對是否正確。（提示：對表達(dá)式進(jìn)行掃描，凡遇到“（”就進(jìn)棧，遇到“）”就退出棧頂?shù)摹埃ā?，表達(dá)式掃 描完畢時(shí)棧若為空則圓括號配對正確。第5章樹與二叉樹一、單項(xiàng)選擇題1. 樹最適合用來表示0無序數(shù)據(jù)元素D.元素之間無聯(lián)系的數(shù)據(jù)15,單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)A.有序數(shù)據(jù)元素B.C.元素之間具有分支層次關(guān)系的數(shù)據(jù)2假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為 點(diǎn)數(shù)為個(gè)。A. 15B. 16 C . 17 D . 473.按照二叉樹的定義，具有3

18、個(gè)結(jié)點(diǎn)的不同形狀的二叉樹有 種A. 3 B. 4 C. 5 D. 65深度為5的二叉樹至多有個(gè)結(jié)點(diǎn)。A. 16 B. 32 C. 31 D. 106. 如果某二叉樹的前根次序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序?yàn)?A. uwvts B. vwuts C. wuvts D. wutsv7. 二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說法0 A. 正確 B. 錯(cuò)誤8. 某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是 abdgcefh，中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是。A. bdgcefha B. gdbecfha C. bdg

19、aechf D. gdbehfca9. 在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊 0A.只有右子樹上的所有結(jié)點(diǎn)B.只有右子樹上的部分結(jié)點(diǎn)C.只有左子樹上的部分結(jié)點(diǎn)D.只有左子樹上的所有結(jié)點(diǎn)10. 一棵二叉樹如圖6.1所示，其中序遍歷的序列為_0A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh11. 設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件A. a在b的右方 B. a在b的左方 C . a是b的祖先 D . a是b的子孫12. 已知某二叉樹的后序遍歷序列是 dabec，中序遍歷序列是debac，它的前序 遍歷序歹寸是_ _

20、0A. acbed B. decab C. deabc D. cedba13. 已知一棵完全二叉樹的結(jié)點(diǎn)總數(shù)為 9個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為 A. 1B. 2C. 3D. 414. 如圖6.2所示的4棵二叉樹，不是完全二叉樹。圖6.2的二叉樹abcdehi二、填空題(將正確的答案填在相應(yīng)的空中)1. 將樹轉(zhuǎn)化為二叉樹的基本目的是_2. 深度為k的完全二叉樹至少有個(gè)結(jié)點(diǎn)。至多有個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號(從1開始)，則編號最小的葉子結(jié)點(diǎn)的編P.日 號是 _。3. 在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，貝卩有n0=。4. 一棵二叉樹的第i (i >

21、; 1)層最多有個(gè)結(jié)點(diǎn)；一棵有n (n>0)個(gè)結(jié)點(diǎn)的滿二叉樹共有個(gè)葉子和個(gè)非終端結(jié)點(diǎn)。5. 哈夫曼樹是指6. 有如圖6.3所示的二叉樹，回答以下問題:其中序遍歷序列為;其前序遍歷序列為;其后序遍歷序列為;圖6.3 一棵二叉樹三、應(yīng)用題1. 分別寫出下圖所示二叉樹的前序、中序和后序遍歷序列。2. 若二叉樹中各結(jié)點(diǎn)值均不相同1) 已知一個(gè)二叉樹的中序和后序遍歷序列分別為 GDHBAECI和GHDBEIFC，請畫 出此二叉樹。2) 已知一個(gè)二叉樹的前序和中序分別為 ABCDEFG和 BDCEAFH請畫出此二叉樹。3.一個(gè)二叉樹如圖所示，將其轉(zhuǎn)換為樹4.畫出該森林對應(yīng)的二叉樹5. 有一份電文中共

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

23、頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍A. 1/2 B. 1 C. 2 D. 44. 一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有邊。A. n B. n(n-1) C. n(n-1)/2D. 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. 對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是A. n B. (n-1)2 C. n-1 D. n

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

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

26、3.米用鄰接表存儲的圖的寬度優(yōu)先遍歷算法類似于二叉樹的 oA.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷15. 在圖6.3所示的拓樸排列的結(jié)果序列為。A.125634B.516234C.123456D.52163421A、0 11110 11110 1B-請根據(jù)下面的鄰接矩陣畫出相應(yīng)的無向圖或有向16. 一個(gè)有n個(gè)頂點(diǎn)的無向連通圖，它所包含的連通分量個(gè)數(shù)為。A.OB.1C.nD.n+117. 對于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1,、出度為k2,則對應(yīng)鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為。A.k1B.k2C.k1-k2D.k1+k218. 對于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1,、出度為k2,則

27、對應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為。A.k1B.k2C.k1-k2D.k1+k2二、基本知識題1. 圖的邏輯結(jié)構(gòu)特點(diǎn)是什么？什么是無向圖和有向圖？什么是子圖？什么是網(wǎng) 絡(luò)？什么是完全圖，生成樹？2. 什么是頂點(diǎn)的度？什么是路徑？什么是連通圖和非連通圖？什么是非連通圖 的連通分量？3. 給出圖所示的無向圖G的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)0 110 00 0 0 101 0 0 0 1100C 00 10 105.分別給出圖所示G圖的深度優(yōu)先搜索和廣度優(yōu)先搜索得到的頂點(diǎn)訪問序列6. 應(yīng)用prim算法求圖所示帶權(quán)連通圖的最小生成樹。7. 寫出圖所示有向圖的拓樸排序序列8 在無權(quán)圖G的鄰接矩陣A中

28、，若(vi,vj)或v vi,vj 屬于圖G的邊集合，則 對應(yīng)元素Aij 等于，否則等于。9在無向圖G的鄰接矩陣A中，若Aij 等于1則Aji 等于。10已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是O11 已知一個(gè)圖的鄰接矩陣表示，刪除所有從第 i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是O12如果含n個(gè)頂點(diǎn)的圖形成一個(gè)環(huán)，則它有棵生成樹 二、算法設(shè)計(jì)題1. 如圖1所示圖G,建立其對應(yīng)的鄰接表存儲，并寫出深度優(yōu)先算法。2. 如圖1所示圖G,建立其對應(yīng)的的鄰接矩陣存儲，并寫出廣度優(yōu)先算法圖13. 編寫一個(gè)函數(shù) 建立一個(gè)有向圖的鄰接表。4. 編寫一個(gè)無向圖的鄰接矩陣轉(zhuǎn)換成鄰接表的算法 第7章查找一、基礎(chǔ)

29、知識題1. 解釋下列名詞查找(2)樹型查找(3)平衡因子散列函數(shù)(5)沖突2. 設(shè)有序表為a,b,c,d,e,f,g，請分別畫出對給定值f,g和h進(jìn)行拆半查找的過程。3. 試述順序查找法、二分查找法和分塊查找法對被查找表中元素的要求，每種 查找法對長度為n的表的等概率查找長度是多少？4順序查找法的平均查找長度為;折半查找法的平均查找長度為;哈希表查找法采用鏈接法處理沖突時(shí)的平均查找長度為 。5. 在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是 。6. 折半查找的存儲結(jié)構(gòu)僅限于，且是。7假設(shè)在有序線性表A1.2O上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù) 為 ，則比較二次查找成功的結(jié)

30、點(diǎn)數(shù)為 ，則比較三次查找成功的結(jié)點(diǎn)數(shù)為 ，則比較四次查找成功的結(jié)點(diǎn)數(shù)為 ，則比較五次查找成功的結(jié)點(diǎn)數(shù)為 ，平均查找長度為 。8. 對于長度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為_;若采用折半法查找，則時(shí)間復(fù)雜度為 ；9. 已知有序表為(12，18, 24，35, 47，50, 62，83, 90，115，134)，當(dāng)用折半查找90時(shí)，需進(jìn)行次查找可確定成功；查找47時(shí)，需進(jìn)行次查找成功；查找100時(shí)，需進(jìn)行次查找才能確定不成功。10. 二叉排序樹的查找長度不僅與 有關(guān)，也與二叉排序樹的 有關(guān)。11. 一個(gè)無序序列可以通過構(gòu)造一棵樹而變成一個(gè)有序樹，構(gòu)造樹的過 程即為對無序序列進(jìn)行排序的過

31、程。12. 平衡二叉排序樹上任一結(jié)點(diǎn)的平衡因子只可能是、 或 。二、算法設(shè)計(jì)題1. 一個(gè)鏈表的元素是從小到大排列的，試寫出對此鏈表的查找算法，并說明是 否可以采用折半查找2. 假設(shè)二叉排序樹t的各元素值均不相同，設(shè)計(jì)一個(gè)算法按遞增次序打印各元 素值。第8章排序一、解釋下列概念(1)排序(2)內(nèi)部排序堆(4)穩(wěn)定排序二、選擇題1. 在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是 CA.希爾排序B.起泡排序 C.插入排序 D.選擇排序2. 設(shè)有1000個(gè)無序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用卡序法。A.起泡排序B.快速排序 C. 堆排序 D.基數(shù)排序3.

32、 在待排序的兀素序列基本有序的前提下，效率最咼的排序方法是 。A.直接插入排序 B.選擇排序 C. 快速排序 D.歸并排序4. 一組記錄的排序碼為(46, 79, 56，38, 40，84)，則利用堆排序的方法建立 的初始大頂堆為。A. 79，46，56，38，40，80B. 38，46, 56 ，79，40，84，C. 84，79，56，38，40，46D. 84，56，79，40，46，385. 一組記錄的關(guān)鍵碼為(46, 79，56, 38, 40，84)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為 。A. 38 , 40, 46,56,79, 84B. 40, 38,

33、46,79,56, 84C. 40 , 38, 46,56,79, 84D. 40, 38,46,84,56, 796. 一組記錄的排序碼為(25, 48, 16, 35, 79, 82, 23, 40, 36, 72),其中含 有5個(gè)長度為2的有序表，按歸并排序的方法對該序列進(jìn)行一趟歸并后的結(jié)果為A.16 , 25,35,48,23,40,79,82,36,72B.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,72,827.排序方法中，從未排序'序列中依匚次取出元素與已排序序列(初始