數(shù)據(jù)結(jié)構(gòu)考試習(xí)試題庫完整

1、緒論一、填空題1. 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合、 ( 線性結(jié)構(gòu) ) 、 ( 樹形結(jié)構(gòu) ) 和 ( 圖狀結(jié)構(gòu) ) 四種。2. 物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，又稱為( 存儲結(jié)構(gòu) ) 。3. 數(shù)據(jù)元素的邏輯結(jié)構(gòu)包括 ( 線性 ) 、 ( 樹) 和圖狀結(jié)構(gòu) 3 種類 型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱為 ( 非線性結(jié)構(gòu) ) 。4.( 數(shù)據(jù)元素 ) 是數(shù)據(jù)的基本單位， ( 數(shù)據(jù)項(xiàng) ) 是數(shù)據(jù)不可分割的最小單位。5. 線性結(jié)構(gòu)中元素之間存在 ( 一個(gè)對一個(gè) ) 關(guān)系，樹形結(jié)構(gòu)中元素之間 存在 ( 一個(gè)對多個(gè) ) 關(guān)系，圖狀結(jié)構(gòu)中元素之間存在 ( 多個(gè)對多個(gè) ) 關(guān)系。？ 6. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程

2、序設(shè)計(jì)問題中：計(jì)算機(jī)的( 數(shù)據(jù)元素 ) 以及它們之間的( 關(guān)系 ) 和( 運(yùn)籌 ) 等的學(xué)科。7. 算法的五個(gè)重要特性為有窮性、 確定性、 ( 輸入 ) 、( 輸出 ) 和 ( 可行性) 。二、選擇題1. 數(shù)據(jù)的不可分割的基本單位是 ( D) 。 A. 元素 B. 結(jié)點(diǎn) C. 數(shù)據(jù)類型 D. 數(shù)據(jù)項(xiàng)*2. 線性表的邏輯順序與存儲順序總是一致的，這種說法( B) 。A. 正確B. 不正確C. 不確定D. 無法選擇3. 線性結(jié)構(gòu)是指數(shù)據(jù)元素之間存在一種( D) 。A. 一對多關(guān)系B. 多對多關(guān)系C. 多對一關(guān)系D. 一對一關(guān)系4. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成( A) 。A. 動態(tài)結(jié)構(gòu)

3、和靜態(tài)結(jié)構(gòu) B. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu) D. 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)5. 線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地址( D)。A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的 C. 一定是不連續(xù)的 D. 連續(xù)不連續(xù)都可以三、簡答題1. 算法的特性是什么。.答：有窮性 確定性 可行性 有 0 或多個(gè)輸入 有 1 或多個(gè)輸出線性結(jié)構(gòu)一、填空題1. 在一個(gè)長度為n 的線性表中刪除第i 個(gè)元素（ 1i n）時(shí)，需向前移動 ( n-i ) 個(gè)元素。2. 從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是( 先移動隊(duì)首指針，后取出元素 ) 。3.在線性表的單鏈接存儲中，若一個(gè)元素所在結(jié)點(diǎn)

4、的地址為p，則其后繼結(jié)點(diǎn)的地址為 ( p->next ) 。4.在一個(gè)單鏈表中指針 p 所指向結(jié)點(diǎn)的后面插入一個(gè)指針q 所指向的結(jié)點(diǎn)時(shí)，首先把 ( p->next ) 的值賦給 q->next ，然后 ( q->date ) 的值賦給 p->next 。5. 從一個(gè)棧刪除元素時(shí)，首先取出 ( 棧頂元素 ) ，然后再使 ( 棧頂指針)減 1。6. 子串的定位操作通常稱做串的 ( 模式匹配 ) 。7. 設(shè)目標(biāo) T=abccdcdccbaa，模式 P=cdcc則第 ( 六) 次匹配成功。8. 順序棧 S 中 ， 出 棧操作時(shí) 要執(zhí)行的 語句序列 中有S->top(

5、 - ) ；進(jìn)棧操作時(shí)要執(zhí)行的語句序列中有S->top( +) 。9. 順序表中邏輯上相鄰元素的物理位置 ( 一定 ) 緊鄰；單鏈表中 邏輯上相鄰元素的物理位置 ( 不一定 ) 緊鄰。10. 在 ( 循環(huán) ) 鏈表中，從任何一結(jié)點(diǎn)出發(fā)都能訪問到表中的所有結(jié)點(diǎn)。11. 棧和隊(duì)列均是 ( 運(yùn)算受限 ) 的線性表，棧的特點(diǎn)是 ( 先進(jìn)后出 后進(jìn)先出) ；隊(duì)列的特點(diǎn)是 ( 先進(jìn)先出 后進(jìn)后出 ) 。12. 通常，在程序中使用的串可分為串常量和串變量；而串按存儲方式又可分為 ( 定長順序存儲 ) 和 ( 堆分配存儲 ) 。13. 循環(huán)隊(duì)列頭指針 front 指向隊(duì)頭元素，隊(duì)尾指針 rear 指向隊(duì)

6、 尾元素后的一個(gè)空閑元素， 隊(duì)列的最大空間為 Queuelen 。在循環(huán)隊(duì)列中 ，隊(duì)空標(biāo)志為 (front=rear) ， 隊(duì)滿標(biāo)志為（rear+1 ）%max=front) 。 當(dāng)(rear>=front時(shí)，隊(duì)列長度為 ( rear-front) ，當(dāng) rear<front時(shí)，隊(duì)列 長度為 ( rear-front+max ) 。14. 在一個(gè)長度為n 的線性表中的第i 個(gè)元素（ 1i n）之前插入一.個(gè)元素時(shí)，需向后移動( n-i+1 ) 個(gè)元素。15. 在具有 n 個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有( n-1 ) 個(gè)元素。16.帶 有 一 個(gè) 頭 結(jié) 點(diǎn) 的 單 鏈 表Head為

7、 空 的 條 件 是( Head->next=null) 。17. 在一個(gè)單鏈表中刪除指針p 所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，需要把( p->next->next ) 值賦給 p->next 指針域。18. 一個(gè)順序循環(huán)隊(duì)列存于aM 中，假定隊(duì)首和隊(duì)尾指針分別為front 和 rear ，則判斷隊(duì)空的條件為 ( a.front=a.rear) ，判斷隊(duì)滿的條件為 ( （a.rear+1 ）%M=a.front ) 。19. 在雙向鏈表中， 每個(gè)結(jié)點(diǎn)有兩個(gè)指針域， 一個(gè)指向其 ( 前驅(qū) ) 結(jié)點(diǎn)，另一個(gè)指向其 ( 后繼 ) 結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的( 后繼結(jié)點(diǎn) ) 指針域?yàn)榭铡?20

8、.若 D=(a， (b， c)， e， a)，則 Head( D )=()，Tail( D )=() ，Head(Tail( D )=() 。（本人不會）21. 在循環(huán)鏈表中， 每個(gè)結(jié)點(diǎn)有 ( 一個(gè) ) 個(gè)指針域， 指向其 ( 后繼 ) 結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的指針域 ( 為空 ) 。*22.若S=(a，(b，c)，e ，d)，則Head( S )=()， Tail( S)=()， Head(Tail( S)=()。（本人不會）二、選擇題1. 在一個(gè)單鏈表中，若q 所指結(jié)點(diǎn)是p 所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與 p 之間插入一個(gè) s 所指的結(jié)點(diǎn)，則執(zhí)行 ( A) 。 A.s->link=p-&g

9、t;link; p->link=s; B.p->link=s; s->link=q;C.p->link=s->link; s->link=p; D.q->link=s; s->link=p;2. 對于順序存儲的隊(duì)列，存儲空間大小為n，頭指針為 F，尾指針為 R。若在邏輯上看一個(gè)環(huán)，則隊(duì)列中元素的個(gè)數(shù)( A) 。A.R-FB.n+R-F C.(R-F+1)mod nD.(n+R-F)mod n3. 如下陳述中正確的是 ( A) 。A. 串是一種特殊的線性表B. 串的長度必須大于零C.串中元素只能是字母D. 空串就是空白串4. 若讓元素1，2， 3

10、依次進(jìn)棧，則出棧次序不可能出現(xiàn)C( )的情況。A.3 ，2，1B.2 ，1，3C.3，1，2D.1 ，3，25. 判定一個(gè)隊(duì)列 QU（最多元素為 m0）為空的條件是 ( C) 。A.QU->rear-QU->front=m0 B.QU->rear-QU->front-1=m0C.QU->front=QU->rearD.QU->front=QU->rear+1.6. 設(shè)目標(biāo)串 S=abcdef ，模式串 p=de，則第 ( C) 次匹配成功。A.1B.2C.4D.57. 設(shè)字符串s1=ABCDEFG， S2=PQRST，T， sub1， sub2

11、為空串。則 運(yùn) 算s=Concat(T，SubString(sub1，s1，2，SubLength(s2)， SubString(sub2，s1 ， SubLength(s2) ， 2)后的串T值為( D)。A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF8. 一個(gè)順序線性表第一個(gè)元素的存儲地址是100，每個(gè)元素的 長度為2，則第 5 個(gè)元素的地址是(B) 。A.100B.108C.110D.1209. 非空的循環(huán)單鏈表 head 的尾結(jié)點(diǎn)（由 p 所指向）滿足 ( C) 。A.p->next=NULLB.p=NULLC.p->next=headD.p=head1

12、0. 在一個(gè)鏈隊(duì)中，假設(shè) f 和 r 分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算時(shí) ( C) 。A.r=f->next;B.r=r->next;C.f=f->next;D.f=r->next;11. 在一個(gè)長度為n 的線性表中，刪除值為x 的元素時(shí)，需要比較元素和移動元素的總次數(shù)為C() 。A.(n+1)/2B.n/2C.nD.n+112. 在一個(gè)單鏈表中，若要在 p 所指向的結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)，則需要相繼修改( B) 個(gè)指針域的值。A.1B.2C.3D.413. 線性結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn) ( C) 。A. 無直接前驅(qū) B. 只有一個(gè)直接前驅(qū)和個(gè)數(shù)不受限制的直接后繼C.

13、只有一個(gè)直接前驅(qū)和后繼 D. 有個(gè)數(shù)不受限制的直接前驅(qū)和后繼14. 隊(duì)列是限定在 ( D) 進(jìn)行操作的線性表。A. 中間B.隊(duì)頭C. 隊(duì)尾D. 端點(diǎn)15. 設(shè)串 S1=“ABCDEFG”， S2=“PQRST”，函數(shù) StrCat(x,y) 返回 x和 y 串的連接串，函數(shù) StrSub(S ， i ，j) 返回串 S 的從序號 i 的字符開始的 j 個(gè) 字 符 組 成 的 子 串 ， StrLen(S) 返 回 串 S 的 長 度 ， 則StrCat(StrSub(S1， 2， StrLen(S2)， StrSub(S1 ， StrLen (S2)，2) 的.結(jié)果串是 ( D) 。A.BCD

14、EFB.BCDEFGC.BCPQRST D.BCDEFEF16. 學(xué)生成績表是一種 ( C) 結(jié)構(gòu)。A. 圖形B. 樹形C. 線性D.集合17. 在一個(gè)鏈隊(duì)中，假設(shè)f 和 r 分別為隊(duì)首和隊(duì)尾指針，則插入s 所指結(jié)點(diǎn)的運(yùn)算時(shí)( C) 。A.f->next=s;f=s;B.r->next=s; r=s; C.s->next=r;r=s;D.s->next=f; f=s;18. 向順序表中的 i 位置處插入元素，下面哪項(xiàng)能夠準(zhǔn)確的表明i 的位置是合法的。( D)A.i<=1|i>l->length+1B.i>=1C.i>=l->lengt

15、h+1D.1<=i<=l->length+119. 設(shè)線性鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（ data ，next ），已知指針 q 所 指結(jié)點(diǎn)是指針 p 所指結(jié)點(diǎn)的直接后繼，若在 *q 和 *p 之間插入結(jié)點(diǎn) *s ，則應(yīng)執(zhí)行( A) 操作。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;20. 一個(gè)棧的入棧序列為 a，b，c，d，e，則出棧序列不可能的是 ( C) 。A.edc

16、baB.dcbae C.dceab D.abcde21. 如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時(shí)( B) 。A. 必須判別棧是否滿B. 必須判別棧是否為空C.必須判別棧元素類型D. 可不做任何判斷22. 設(shè)有兩個(gè)串 p 和 q，求 q 在 p 中首次出現(xiàn)的位置的運(yùn)算稱為B( ) 。A. 連接 B. 模式匹配 C. 求子串D. 求串長23.p 指向線性鏈表中的某一結(jié)點(diǎn)，則在線性鏈表的表尾插入結(jié)點(diǎn) S 的語句序列是 ( A) 。A.while(p->next!=NULL) p=p->next; p->next=s; s->next=N ULL; B.while(p!=NU

17、LL) p=p->next; p->next=s; s->next=NULL; C.while(p->next!=NULL) p=p->next; s->next=p;p->next=NULL; D.while(p!=NULL) p=p->next->next;->next;p->next=s;s->next=p24. 向順序棧中壓入新元素時(shí)，應(yīng)當(dāng) ( A) 。A. 先移動棧頂指針，再存入元素B.先存入元素，再移動棧頂指針C.先后次序無關(guān)緊要D.同時(shí)進(jìn)行25. 假定一個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別為f 和 r ，則判斷隊(duì)空

18、的條件為 (D)。.f+1=rB.r+1=fC.f=0D.f=r26. 棧的插入和刪除操作在 ( A) 進(jìn)行。A. 棧頂 B. 棧底C. 任意位置 D. 指定位置27. 棧和隊(duì)列的共同點(diǎn)是 ( C) 。A. 都是先進(jìn)后出B. 都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D. 沒有共同點(diǎn)28. 若 6 行 8 列的數(shù)組以列序?yàn)橹餍蝽樞虼鎯Γ刂窞?000， 每個(gè)元素占 2 個(gè)存儲單元，則第5 行第 3 列的元素 ( 假定無第 0 行第 0 列) 的地B址是( )。A.1086B.1032C.1068D. 答案 A，B， C 都不對29. 設(shè)有 50 行的二維數(shù)組A5060 ，其元素長度為 2字

19、節(jié)，按 行優(yōu)先順序存儲，基地址為100，則元素 A1825 的存儲地址D為( )。A.1850B.2188C.1950D.2310三、論述題1. 寫出線性表的插入算法、刪除算法。解：太麻煩略略略*2. 畫出主串為 ababcabcacbab，子串為 abc的模式匹配過程。解：四、算法設(shè)計(jì)題1. 在帶頭結(jié)點(diǎn)的單鏈線性表L 中第 i 個(gè)位置之前插入新的元素e。略2. 在帶頭結(jié)點(diǎn)的單鏈線性表L 中，刪除第i 個(gè)元素，并由e 返回其值。略樹形結(jié)構(gòu)一、填空題1. 赫夫曼樹，又稱最優(yōu)樹，是一類 ( 帶權(quán)路徑 ) 長度最短的樹。2. 在一棵二叉樹中，第 5 層上的結(jié)點(diǎn)數(shù)最多為 ( 16) 個(gè)。3. 一棵高度

20、為 5 的二叉樹中最少含有 ( 5) 個(gè)結(jié)點(diǎn)，最多含 有( 31) 個(gè)結(jié)點(diǎn)。4. 若一棵二叉樹中有 8 個(gè)度為 2 的結(jié)點(diǎn)，則它有 ( 9) 個(gè)葉子。5. 一棵深度為 6 的滿二叉樹有 ( 31) 個(gè)非終端結(jié)點(diǎn)。.6. 樹中結(jié)點(diǎn) A 的 ( 子樹數(shù) ) 稱為結(jié)點(diǎn) A 的度。7. 對一棵二叉排序樹進(jìn)行中序遍歷時(shí)， 得到的結(jié)點(diǎn)序列是一個(gè) ( 升序序列)。8. 在樹型結(jié)構(gòu)中，根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且僅有 ( 一)個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn) ( 沒有 ) 后繼結(jié)點(diǎn)， 其余每個(gè)結(jié)點(diǎn)都可以有 ( 一或多個(gè)) 個(gè)后繼結(jié)點(diǎn)。9. 在最優(yōu)二叉樹中沒有度為 1 的結(jié)點(diǎn)，則一棵有 n 個(gè)葉子結(jié)點(diǎn)的最優(yōu)二叉樹中

21、共有 ( 2n-1 ) 個(gè)結(jié)點(diǎn)。10. 深度為 4（設(shè)根的層數(shù)為 1）的二叉樹至少有 ( 4) 個(gè)結(jié)點(diǎn)，至多有( 15) 個(gè)結(jié)點(diǎn)，第i 層上至多有 ( 2n-1 ) 個(gè)結(jié)點(diǎn)。11. 深度為 6（設(shè)根的層數(shù)為 1）的二叉樹至少有 ( 6) 個(gè)結(jié)點(diǎn)，至多有 ( 63) 個(gè)結(jié)點(diǎn)，第 4 層上至多有 (8) 個(gè)結(jié)點(diǎn)。.A.nB. N+1 C.n-1 D.不確定注： 1:B 2:D 3:A4:B5. 下面 ( A) 是對的。A. 哈夫曼樹中結(jié)點(diǎn)的度只可能是0 和 2。 B. 二叉樹的順序存儲中，是以先序遍歷存儲結(jié)點(diǎn)的。C. 完全二叉樹實(shí)際上就是滿二叉樹。D.一棵二叉樹第i 層的最大結(jié)點(diǎn)數(shù)為2i-1 。6

22、. 將含 100 個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每層上從左到右依次對結(jié)點(diǎn)編號，根結(jié)點(diǎn)的編號為 1。編號為 49 的結(jié)點(diǎn) X 的右孩子編號為 ( B) 。A.98B.99C.24D. 無法確定7. 先序?yàn)?A， B， C 且后序?yàn)?C， B， A 的二叉樹共有 ( B) 種。A.3 B.4C.5D.68. 在一棵度為 3 的樹中，度為 3 的結(jié)點(diǎn)個(gè)數(shù)為 2，度為 2 的結(jié)點(diǎn)個(gè)數(shù)為 1，則度為 0 的結(jié)點(diǎn)個(gè)數(shù)為 ( C)。A.4 B.5C.6D.79. 由權(quán)值分別為 11， 8， 6，2， 5 的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為B( ) 。A.24B.71C.48D.5310. 一

23、個(gè)具有 767 個(gè)結(jié)點(diǎn)的完全二叉樹， 其葉子結(jié)點(diǎn)個(gè)數(shù)為 ( B) 。A.382B.384C.385D.38611. 在一棵具有 35 個(gè)結(jié)點(diǎn)的完全二叉樹中，該樹的深度為 ( A) 。A.6 B.7C.5D.812. 由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有B( ) 種不同的結(jié)構(gòu)。.A.3B.4C.5D.613. 深度為 k 的二叉樹至多有 ( 2K-1 ) 個(gè)結(jié)點(diǎn) (k 1) 。A.2kB.2k-1C.2k-1D.2k三、簡答題1. 已知一棵二叉樹的先序遍歷和中序遍歷，則該二叉樹的后序遍歷是什么？先序遍歷： A，B， C， D， E， F，G， H， I ，J中序遍歷： C，B， A， E， F， D，I

24、 ， H， J，G解：后序遍歷： C,B,F,E,I,J,H,G,D,A2. 如下圖的森林轉(zhuǎn)化為二叉樹。.解：此題沒法寫略略略3. 已 知 某 二 叉 樹 的 前 序 序 列 為 EBADCFHGI ， 中 序 序 列 為 ABCDEFGHI，請給出二叉樹且寫出二叉樹的后序序列。解：二叉樹略后序序列 :A,C,D,B,G,I,H,F,E4. 試用權(quán)集合 6 ， 4， 8， 3， 7，5， 10， 8， 2， 1，11 ，構(gòu)造 哈夫曼 (Huffman) 樹。(1) 畫出這棵哈夫曼樹； (2) 分別計(jì)算該哈夫曼樹的路徑長度和帶權(quán)路徑長度。解： (1) 略(2) 路徑長度為： 1x2+2x4+3x

25、8+4x3+5x2=60;帶權(quán)路徑長度為： 3x(6+7+8+8+10+11)+4x(3+4+5)+5x(1+2)=2135. 試按表 (10 ，18，9，2，20，5，6，15，19，25) 中元素的排 列次序，將所有元素插入一棵初始為空的二叉排序樹中，使之 仍是一棵二叉排序樹。(1) 試畫出插入完成之后的二叉排序樹； (2) 若查找元素 2，它將依次與二叉排序樹中哪些元素比較大小 ? (3) 對該樹進(jìn)行中序遍歷，試寫出中序遍歷序列。解： (1) 略(2)10,9,2(3)2,5,6,9,10,15,18,19,20,256. 已知一棵二叉樹的順序存儲表示如下，其中0 表示空，請分別寫出二叉

26、的先序、中序、后序遍歷序列。12345678910111213.20846515300001018035解：先序序列： 20,8,5,15,10,18,46,30,35中序序列： 5,8,10,15,18,20,30,35,46后序序列： 5,10,18,15,8,35,30,46,207. 將如下圖的一般樹轉(zhuǎn)化為二叉樹。.8. 將下圖中的二叉樹轉(zhuǎn)換成森林。BAEGKCFHILJ.四、論述題1. 由分別帶權(quán)為 3，12， 9，2， 5， 7 的葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，并計(jì)算該樹的帶權(quán)路徑長度。解: 帶權(quán)路徑長度為 :91圖狀結(jié)構(gòu)一、填空題1. 若一個(gè)圖的頂點(diǎn)集為a ， b， c， d， e，

27、f ，邊集為 (a ， b) ， (a ，c) ， (b ，c) ， (d ，e),則該圖含有 (3) 個(gè)連通分量。452. 具有 10 個(gè)頂點(diǎn)的無向圖，邊的總數(shù)最多為( ) 。3. 圖的廣度優(yōu)先搜索遍歷類似于樹的( 按層次 ) 遍歷的過程。4. 在無向圖 G的鄰接矩陣 A 中，若 Aij等于 1，則 Aji1等于( )。5. 圖的 ( 深度 ) 優(yōu)先搜索遍歷算法是一種遞歸算法，圖的 ( 廣度 ) 優(yōu)先搜索遍歷算法需要使用隊(duì)列二、選擇題1. 一個(gè)有 n 個(gè)頂點(diǎn)的無向圖最多有 ( C) 條邊。A.nB.n(n-1)C.n(n-1)/2D.2n2. 在一個(gè)無向圖中， 所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)

28、的( B) 倍。A.3B.2C.1D.1/23. 在一個(gè)具有 n 個(gè)頂點(diǎn)的無向圖中，若具有e 條邊，則所有頂點(diǎn)的度數(shù)之為D( ) 。A.n B.eC.n+eD.2e三、簡答題.1. 給出如下圖所示的無向圖 G的鄰接矩陣存儲結(jié)構(gòu)。 （答案略）2. 畫出下圖的鄰接表存儲結(jié)構(gòu)。（答案略）.3. 給出下圖從 A 點(diǎn)出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列。解：深度優(yōu)先遍歷： AECDB廣度優(yōu)先遍歷： AEBDC.5. 給出從 V1 點(diǎn)出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列。解：深度優(yōu)先遍歷 ;v1 v2 v3 v4 v5 v6 v7 v8 v9 廣度優(yōu)先遍歷 ;v1 v2 v3 v4 v7 v5

29、 v6 v8 v9.四、論述題1. 寫出下面帶權(quán)有向圖的的關(guān)鍵路徑。解： (1)1->2->5->8->92. 設(shè)將整數(shù) 1、 2、3、 4 依次進(jìn)棧，請回答下述問題：1）若入、出棧順序?yàn)?Push(1) ，Pop() ， Push(2) ，Push(3) ， Pop() ，Pop() ，Push(4) ，Pop() ，則出棧的數(shù)字序列是什么？ 2 ）能否得到出棧序列 1432 和 1423？并說明為什么不能得到或者如何得到？解： (1):1324(2): 可以得到 1432不能得到 1423得到1432的過程為：Push(1),pop(),push(2),push(3),push(4),pop(),pop(),pop(),不能得到 1423 無法執(zhí)行此操作.3. 求出下圖的最小生成樹。4. 求出下圖的最小生成樹。（答案略）（答案略）.查找一、簡答題1. 關(guān)鍵字集合 19 ， 01，23， 14，55， 68，11， 82，36 ，哈希函數(shù)為：