數(shù)據(jù)結(jié)構(gòu)考試題庫(kù)

1、緒論一、填空題1.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合、(線性結(jié)構(gòu))、(樹(shù)形結(jié)構(gòu))和(圖狀結(jié)構(gòu))四種。2.物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，又稱為(存儲(chǔ)結(jié)構(gòu))。3.數(shù)據(jù)元素的邏輯結(jié)構(gòu)包括(線性)、(樹(shù))和圖狀結(jié)構(gòu)3種類 型，樹(shù)形結(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è)對(duì)一個(gè))關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間 存在(一個(gè)對(duì)多個(gè))關(guān)系，圖狀結(jié)構(gòu)中元素之間存在(多個(gè)對(duì)多個(gè))關(guān)系。 ？6.數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中：計(jì)算機(jī)的(數(shù)據(jù)元素)以及它們之間的(關(guān)系)和(運(yùn)籌)等的學(xué)科。7.算法的五個(gè)重要特性為有

2、窮性、確定性、(輸入)、(輸出)和(可行性)。二、選擇題1.數(shù)據(jù)的不可分割的基本單位是(D)。A.元素B.結(jié)點(diǎn)C.數(shù)據(jù)類型D.數(shù)據(jù)項(xiàng) *2.線性表的邏輯順序與存儲(chǔ)順序總是一致的，這種說(shuō)法(B)。A.正確B.不正確C.不確定D.無(wú)法選擇 3.線性結(jié)構(gòu)是指數(shù)據(jù)元素之間存在一種(D)。A.一對(duì)多關(guān)系B.多對(duì)多關(guān)系C.多對(duì)一關(guān)系D.一對(duì)一關(guān)系 4.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成(A)。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(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)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址( D)。A.必須是連續(xù)的B.部分地址必須是連續(xù)的 C.

3、一定是不連續(xù)的D.連續(xù)不連續(xù)都可以三、簡(jiǎn)答題1.算法的特性是什么。答：有窮性 確定性 可行性 有0或多個(gè)輸入 有1或多個(gè)輸出 線性結(jié)構(gòu)一、填空題1.在一個(gè)長(zhǎng)度為n的線性表中刪除第i個(gè)元素（1in）時(shí)， 需向前移動(dòng)(n-i)個(gè)元素。2.從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是(先移動(dòng)隊(duì)首指針，后取出元素)。3.在線性表的單鏈接存儲(chǔ)中，若一個(gè)元素所在結(jié)點(diǎn)的地址為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í)，首先取出(棧頂元素)

4、，然后再使(棧頂指針)減1。6.子串的定位操作通常稱做串的(模式匹配)。7.設(shè)目標(biāo)T=abccdcdccbaa，模式P=cdcc則第(六)次匹配成功。8. 順序棧 S 中 ， 出 棧操作時(shí) 要執(zhí)行的 語(yǔ)句序列 中有 S-top(-)；進(jìn)棧操作時(shí)要執(zhí)行的語(yǔ)句序列中有S-top(+)。 9.順序表中邏輯上相鄰元素的物理位置(一定)緊鄰；單鏈表中 邏輯上相鄰元素的物理位置(不一定)緊鄰。10.在(循環(huán))鏈表中，從任何一結(jié)點(diǎn)出發(fā)都能訪問(wèn)到表中的所有結(jié)點(diǎn)。11.棧和隊(duì)列均是(運(yùn)算受限)的線性表，棧的特點(diǎn)是(先進(jìn)后出 后進(jìn)先出)；隊(duì)列的特點(diǎn)是(先進(jìn)先出 后進(jìn)后出)。12.通常，在程序中使用的串可分為串常量

5、和串變量；而串按存儲(chǔ)方式又可分為(定長(zhǎng)順序存儲(chǔ))和(堆分配存儲(chǔ))。 13.循環(huán)隊(duì)列頭指針front指向隊(duì)頭元素，隊(duì)尾指針rear指向隊(duì) 尾元素后的一個(gè)空閑元素，隊(duì)列的最大空間為Queuelen。在循環(huán)隊(duì)列中 ， 隊(duì)空標(biāo)志為(front=rear)， 隊(duì)滿標(biāo)志為(（rear+1）%max=front)。 當(dāng)rear=front時(shí)，隊(duì)列長(zhǎng)度為(rear-front)，當(dāng)rearnext=null)。17.在一個(gè)單鏈表中刪除指針p所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，需要把(p-next-next)值賦給p-next指針域。 18.一個(gè)順序循環(huán)隊(duì)列存于aM中，假定隊(duì)首和隊(duì)尾指針?lè)謩e 為front和rear，則判斷

6、隊(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. 若 D=(a ， (b ， c) ， e ， a) ， 則 Head( D )=( ) ，Tail( D )=( )，Head(Tail( D )=()。（本人不會(huì)）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

7、 )=( ) ， Tail( S)=( )，Head(Tail( S)=( )。（本人不會(huì)）二、選擇題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-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ì)于順序存儲(chǔ)的隊(duì)列，存儲(chǔ)空間大小為n，頭指針為F，尾指針為R。若在邏輯上看一個(gè)環(huán)，則隊(duì)列中元素的個(gè)數(shù)(A)。A.R-FB.n+R-FC.(R-F+1)mod nD.(n+R-F)modn3.如

8、下陳述中正確的是(A)。A.串是一種特殊的線性表B.串的長(zhǎng)度必須大于零C.串中元素只能是字母 D.空串就是空白串4.若讓元素1，2，3依次進(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=m0B.QU-rear-QU-front-1=m0 C.QU-front=QU-rear D.QU-front=QU-rear+16.設(shè)目標(biāo)串S=abcdef，模式串p=de，則第(C)次匹配成功。A.1 B.2 C.4 D.57.設(shè)字符串s1=ABCDEFG，S2

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

10、ad D.p=head10.在一個(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è)長(zhǎng)度為n的線性表中，刪除值為x的元素時(shí)，需要比 較元素和移動(dòng)元素的總次數(shù)為(C)。A.(n+1)/2 B.n/2 C.n D.n+112.在一個(gè)單鏈表中，若要在p所指向的結(jié)點(diǎn)之后插入一個(gè)新結(jié) 點(diǎn)，則需要相繼修改(B)個(gè)指針域的值。A.1 B.2 C.3 D.413.線性結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)(C)。A.無(wú)直接前驅(qū) B.只有一個(gè)直接前驅(qū)和個(gè)數(shù)不受限制的直接后繼 C.只有一個(gè)直接前驅(qū)和后繼D.有個(gè)數(shù)不

11、受限制的直接前驅(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的從序號(hào)i 的字符開(kāi)始的j個(gè)字符組成的子串，StrLen(S)返回串S的長(zhǎng)度， 則StrCat(StrSub(S1，2，StrLen(S2)，StrSub(S1，StrLen (S2)，2)的結(jié)果串是(D)。A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF16.學(xué)生成績(jī)表是一種(C)結(jié)構(gòu)。A.圖形 B.樹(shù)形C.線性D.集合 17.

12、在一個(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.il-length+1B.i=1C.i=l-length+1 D.1=ilength+1 19.設(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

13、=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.edcbaB.dcbaeC.dceabD.abcde 21.如果以鏈表作為棧的存儲(chǔ)結(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.求串長(zhǎng)23.p指向線性鏈表中的某一結(jié)點(diǎn)，則在線性鏈表的表尾插入結(jié)點(diǎn)S的語(yǔ)句序列是(A)。A.while(

14、p-next!=NULL) p=p-next; p-next=s; s-next=N ULL;B.while(p!=NULL) 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.先移動(dòng)棧頂指針，再存入元素 B.先存入元素，再移動(dòng)棧頂指針C.先后次序無(wú)關(guān)緊要 D.同時(shí)進(jìn)行25.假定一個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針?lè)謩e為f和r，則判

15、斷隊(duì)空的條件為(D)。f+1=r B.r+1=f C.f=0 D.f=r26.棧的插入和刪除操作在(A)進(jìn)行。A.棧頂B.棧底C.任意位置D.指定位置27.棧和隊(duì)列的共同點(diǎn)是(C)。A.都是先進(jìn)后出 B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素 D.沒(méi)有共同點(diǎn) 28.若6行8列的數(shù)組以列序?yàn)橹餍蝽樞虼鎯?chǔ)，基地址為1000， 每個(gè)元素占2個(gè)存儲(chǔ)單元，則第5行第3列的元素(假定無(wú)第0行第0列)的地址是(B)。A.1086B.1032C.1068D.答案A，B，C都不對(duì)29.設(shè)有50行的二維數(shù)組A5060，其元素長(zhǎng)度為2字節(jié)，按 行優(yōu)先順序存儲(chǔ)，基地址為100，則元素A1825的存儲(chǔ)地址 為(D

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

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

18、至多有(63)個(gè)結(jié)點(diǎn)，第4層上至多有(8)個(gè)結(jié)點(diǎn)。A.n B. N+1 C.n-1 D.不確定注：1:B 2:D 3:A 4:B 5.下面(A)是對(duì)的。A.哈夫曼樹(shù)中結(jié)點(diǎn)的度只可能是0和2。 B.二叉樹(shù)的順序存儲(chǔ)中，是以先序遍歷存儲(chǔ)結(jié)點(diǎn)的。C.完全二叉樹(shù)實(shí)際上就是滿二叉樹(shù)。 D.一棵二叉樹(shù)第i層的最大結(jié)點(diǎn)數(shù)為2i-1。 6.將含100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每層上從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1。編號(hào)為49的結(jié)點(diǎn)X的右孩子編號(hào)為(B)。A.98 B.99C.24 D.無(wú)法確定7.先序?yàn)锳，B，C且后序?yàn)镃，B，A的二叉樹(shù)共有(B)種。A.3 B.4 C.5 D.68.在一棵度

19、為3的樹(shù)中，度為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.6 D.7 9.由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)， 它的帶權(quán)路徑長(zhǎng)度為(B)。A.24 B.71C.48D.5310. 一個(gè)具有 767 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)， 其葉子結(jié)點(diǎn)個(gè)數(shù)為 (B)。A.382B.384 C.385 D.38611. 在一棵具有 35 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中， 該樹(shù)的深度為(A)。A.6 B.7 C.5D.8 12.由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹(shù)，共有(B)種不同的結(jié)構(gòu)。A.3 B.4 C.5 D.613.深度為k的二叉樹(shù)至多有(2K-1)個(gè)結(jié)點(diǎn)(k1)。A

20、.2k B.2k-1 C.2k-1 D.2k三、簡(jiǎn)答題1.已知一棵二叉樹(shù)的先序遍歷和中序遍歷，則該二叉樹(shù)的后序遍歷是什么？ 先序遍歷：A，B，C，D，E，F(xiàn)，G，H，I，J 中序遍歷：C，B，A，E，F(xiàn)，D，I，H，J，G 解：后序遍歷：C,B,F,E,I,J,H,G,D,A2.如下圖的森林轉(zhuǎn)化為二叉樹(shù)。解：此題沒(méi)法寫(xiě) 略略略3. 已 知 某 二 叉 樹(shù) 的 前 序 序 列 為 EBADCFHGI ， 中 序 序 列 為ABCDEFGHI，請(qǐng)給出二叉樹(shù)且寫(xiě)出二叉樹(shù)的后序序列。解：二叉樹(shù)略 后序序列:A,C,D,B,G,I,H,F,E 4. 試用權(quán)集合6，4，8，3，7，5，10，8，2，1，1

21、1，構(gòu)造 哈夫曼(Huffman)樹(shù)。 (1)畫(huà)出這棵哈夫曼樹(shù)；(2)分別計(jì)算該哈夫曼樹(shù)的路徑長(zhǎng)度和帶權(quán)路徑長(zhǎng)度。解：(1)略 (2)路徑長(zhǎng)度為：1x2+2x4+3x8+4x3+5x2=60; 帶權(quán)路徑長(zhǎng)度為：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)中元素的排 列次序，將所有元素插入一棵初始為空的二叉排序樹(shù)中，使之 仍是一棵二叉排序樹(shù)。(1)試畫(huà)出插入完成之后的二叉排序樹(shù)； (2)若查找元素2，它將依次與二叉排序樹(shù)中哪些元素比較大小? (3)對(duì)該樹(shù)進(jìn)行中序遍歷，試寫(xiě)出中序遍歷序列。解：(1)略

22、 (2)10,9,2 (3)2,5,6,9,10,15,18,19,20,25 6.已知一棵二叉樹(shù)的順序存儲(chǔ)表示如下，其中0表示空，請(qǐng)分別寫(xiě)出二叉的先序、中序、后序遍歷序列。1234567891011121320846515300001018035解：先序序列：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.將如下圖的一般樹(shù)轉(zhuǎn)化為二叉樹(shù)。8.將下圖中的二叉樹(shù)轉(zhuǎn)換成森林。AEBCGKFDHLIJ四、論述題1.由分別帶權(quán)為3，12，9，2，5，7的葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)，并

23、計(jì)算該樹(shù)的帶權(quán)路徑長(zhǎng)度。 解:帶權(quán)路徑長(zhǎng)度為:91圖狀結(jié)構(gòu)一、填空題1.若一個(gè)圖的頂點(diǎn)集為a，b，c，d，e，f，邊集為(a，b)， (a，c)，(b，c)，(d，e),則該圖含有(3)個(gè)連通分量。 2.具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為(45)。3.圖的廣度優(yōu)先搜索遍歷類似于樹(shù)的(按層次)遍歷的過(guò)程。4.在無(wú)向圖G的鄰接矩陣A中，若Aij等于1，則Aji等于(1)。5.圖的(深度)優(yōu)先搜索遍歷算法是一種遞歸算法，圖的(廣度) 優(yōu)先搜索遍歷算法需要使用隊(duì)列二、選擇題1.一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有(C)條邊。A.n B.n(n-1) C.n(n-1)/2 D.2n2. 在一個(gè)無(wú)向圖中， 所

24、有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 (B)倍。A.3 B.2 C.1 D.1/23.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，若具有e條邊，則所有頂點(diǎn)的度數(shù)之為(D)。A.n B.e C.n+e D.2e三、簡(jiǎn)答題1.給出如下圖所示的無(wú)向圖G的鄰接矩陣存儲(chǔ)結(jié)構(gòu)。（答案略）2.畫(huà)出下圖的鄰接表存儲(chǔ)結(jié)構(gòu)。（答案略）3.給出下圖從A點(diǎn)出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列。解：深度優(yōu)先遍歷：AECDB 廣度優(yōu)先遍歷：AEBDC5.給出從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 v6 v

25、8 v9四、論述題1.寫(xiě)出下面帶權(quán)有向圖的的關(guān)鍵路徑。解：(1)1-2-5-8-92.設(shè)將整數(shù)1、2、3、4依次進(jìn)棧，請(qǐng)回答下述問(wèn)題：1）若入、出棧順序?yàn)镻ush(1)，Pop()，Push(2)，Push(3)， Pop()，Pop()，Push(4)，Pop()，則出棧的數(shù)字序列是什么？ 2）能否得到出棧序列1432和1423？并說(shuō)明為什么不能得到或者如何得到？解：(1):1324(2):可以得到1432 不能得到1423 得到1432的過(guò)程為：Push(1),pop(),push(2),push(3),push(4),pop(),pop(),pop(), 不能得到1423 無(wú)法執(zhí)行此操作3.求出下圖的最小生成樹(shù)。（答案略） 4.求出下圖的最小生成樹(shù)。（答案略）查找一、簡(jiǎn)答題1.關(guān)鍵字集合19，01，23，14，55，68，11，82，36，哈希函數(shù)為：H(key)=keyMOD9構(gòu)建哈希表，采用開(kāi)放定址法解決沖突。（答案略）2.關(guān)鍵字集合19，14