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

1、第 1 章 緒論習(xí)題1簡(jiǎn)述以下概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ) 結(jié)構(gòu)、抽象數(shù)據(jù)類型。2試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，表達(dá)其邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩方面的含義和相互關(guān)系。3簡(jiǎn)述邏輯結(jié)構(gòu)的四種根本關(guān)系并畫(huà)出它們的關(guān)系圖。4存儲(chǔ)結(jié)構(gòu)由哪兩種根本的存儲(chǔ)方法實(shí)現(xiàn)？5選擇題 1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成。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) 2與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的。A. 存儲(chǔ)結(jié)構(gòu)B存儲(chǔ)實(shí)現(xiàn)C.邏輯結(jié)構(gòu)D運(yùn)算實(shí)現(xiàn) 3通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著

2、。A .數(shù)據(jù)具有同一特點(diǎn)B. 不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致C. 每個(gè)數(shù)據(jù)元素都一樣D. 數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等 4以下說(shuō)法正確的選項(xiàng)是。A. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位B. 數(shù)據(jù)項(xiàng)是數(shù)據(jù)的根本單位C. 數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合D. 一些外表上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)5以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是。A. 順序隊(duì)列B. 鏈表C.有序表D.鏈棧 6以下數(shù)據(jù)結(jié)構(gòu)中， 是非線性數(shù)據(jù)結(jié)構(gòu)A.樹(shù) B .字符串C .隊(duì) D.棧6.試分析下面各程序段的時(shí)間復(fù)雜度。 1 x=90; y=100;whiley0ifx100x=x-10;y-;e

3、lse x+;2for i=0; in; i+for j=0; jm; j+aij=0;3s=0;for i=0; in; i+for(j=0; j n; j+)s+=Bij；sum=s;(4) i=1； while(i=n)i=i*3;(5) x=0;for(i=1; in; i+)for (j=1; jnext=p-next; p-next=s-next;D. s-next=p-next; p-next=s;(14) 在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針()。A. p-next_prior=p_prior; p-prior-next=p-next;B. p_next=p-ne

4、xt-next; p_next-prior=p;C. p-prior-next=p; p_prior=p_prior-prior;D. p-prior=p-next-next; p-next=p-prior-prior;(15) 在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的操作是()。A. p_next=q; q-prior=p; p_next-prior=q; q_next=q;B. p_next=q; p_next-prior=q; q-prior=p; q_next=p-next;C. q-prior=p; q_next=p-next; p_next-prio

5、r=q; p_next=q;D. q-prior=p; q_next=p-next; p_next=q; p_next-prior=q;2.算法設(shè)計(jì)題(1)將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原來(lái)兩 個(gè)鏈表的存儲(chǔ)空間，不另外占用其它的存儲(chǔ)空間。表中不允許有重復(fù)的數(shù)據(jù)。void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)pa=La-n ext; pb=Lb-n ext;Lc=pc=La;想摘除棧頂結(jié)點(diǎn)，并將刪除結(jié)點(diǎn)的值保存到操作(A.C.(5)中,那么應(yīng)執(zhí)行)x=top-data;top=top-li nk

6、x=top;top=top-li nk；設(shè)有一個(gè)遞歸算法如下int fact(i nt n) B . top=top-link;x=top-link D . x=top-link ;線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))僅修改尾指針D.頭、尾指針可能都要修改A0.m中，那么入隊(duì)時(shí)的操作為(B. rear=(rear+1)%(m-1)D.rear=(rear+1)%(m+1)曰D.(11) 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)(A.僅修改頭指針C.頭、尾指針都要修改(12) 循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A. rear=rear+1C. rear=(rear+1)%m(13) 最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，

7、隊(duì)頭是front，那么隊(duì)空的條件是()B.C. rear+1=frontD. (rear-l)% n=front都是先進(jìn)后出D.沒(méi)有共同點(diǎn)終止條件和遞歸局部 終止條件和迭代局部14 棧和隊(duì)列的共同點(diǎn)是。A.都是先進(jìn)先出B.C.只允許在端點(diǎn)處插入和刪除元素15 個(gè)遞歸算法必須包括。A.遞歸局部B.C.迭代局部D.2回文是指正讀反讀均相同的字符序列，如“abba和abdba均是回文，但“good不是回文。試寫(xiě)一個(gè)算法判定給定的字符向量是否為回文。提示：將一半字符入棧根據(jù)提示，算法可設(shè)計(jì)為：10110100 B. 10010110 C. IIIOIOIO D. IIIOOIOO 通過(guò)對(duì)的分析，寫(xiě)出一

8、個(gè)算法，判定所給的操作序列是否合法。假設(shè)合法，返回true，否那么返回false 假定被判定的操作序列已存入一維數(shù)組中。 A和D是合法序列，B和C是非法序列。 設(shè)被判定的操作序列已存入一維數(shù)組A中。int Judge char AM-1實(shí)現(xiàn)循環(huán)隊(duì)列，其中M是隊(duì)列長(zhǎng)度。設(shè)隊(duì)頭指針front和隊(duì)尾指針rear，約定front指向隊(duì)頭元素的前一位置，rear指向隊(duì)尾元素。定義front=rear時(shí)為隊(duì)空，rear+1%m=fro nt為隊(duì)滿。約定隊(duì)頭端入隊(duì)向下標(biāo)小的方向開(kāi)展，隊(duì)尾端入隊(duì)向下標(biāo)大的方向開(kāi)展。1 #define M隊(duì)列可能到達(dá)的最大長(zhǎng)度typedef struct elemtp data

9、M;int fron t,rear; cycqueue;2elemtp delqueue cycqueue Q:n+1當(dāng) = D當(dāng) e円山刊時(shí) 100,仁100，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10,那么LOC5,5=。A. 808B . 818C . 1010D. 10207 設(shè)有數(shù)組 Ai,j，數(shù)組的每個(gè)元素長(zhǎng)度為 3字節(jié)，i的值為1到8，j的值為1 到10，數(shù)組從內(nèi)存首地址 BA開(kāi)始順序存放，當(dāng)用以列為主存放時(shí)， 元素A5,8的存儲(chǔ)首地 址為。A. BA+141B . BA+180 C . BA+222 D . BA+2258 設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)?/p>

10、主存儲(chǔ)，an為第一元素，其存儲(chǔ)地址為1,每個(gè)元素占一個(gè)地址空間，那么a85的地址為。A. 13B . 33C . 18D. 409 假設(shè)對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑匕ㄖ鲗?duì)角線上所有元素依次存放于一維數(shù)組 B1.nn+1/2中，那么在B中確定am ij 的位置k的關(guān)系為()。A. i*(i-1)/2+jB. j*(j-1)/2+iC . i*(i+1)/2+j D. j*(j+1)/2+i(10) AN, N是對(duì)稱矩陣，將下面三角(包括對(duì)角線)以行序存儲(chǔ)到一維數(shù)組TN(N+1)/2(1)模式串nextval 函數(shù)值。t= abcaabbabcab 寫(xiě)出用 KMP法求得的每

11、個(gè)字符對(duì)應(yīng)的next 和中，那么對(duì)任一上三角兀素aij對(duì)應(yīng)Tk的下標(biāo)k是()。A. i(i-1)/2+jB .j(j-1)/2+iC.i(j-i)/2+1D.j(i-1)/2+1(11)設(shè)二維數(shù)組A1.m,1. n(即m行n列)按行存儲(chǔ)在數(shù)組B1. m*n中，那么二維數(shù)組兀素Ai,j 在一維數(shù)組B中的下標(biāo)為()。A. (i-1)*n +jB.(i-1)* n+j-1 C.i*(j-1)D.j*m+i-1(12)數(shù)組A0.4,-1.-3,5.7中含有元素的個(gè)數(shù)()。A. 55B. 45C.36D.16(13)廣義表A=(a,b,(c,d),(e,(f,g)，那么 Head(Tail(Head(T

12、ail(Tail(A)的值為()。A. (g)B. (d)C.cD. d(14)廣義表(a,b,c,d)的表頭是(),表尾是()。A. aB. ( )C.(a,b,c,d)D . (b,c,d)(15)設(shè)廣義表L=(a,b,c)，貝U L的長(zhǎng)度和深度分別為()。A. 1 和 1 B . 1 和 3C . 1 和 2D . 2 和 3模式串t的next和nextval值如下:j1 2 3 4 5 6 7 8 9 10 11 12t串a(chǎn) b c a a b b a b c a bn extj0 1 1 1 2 2 3 1 2 3 4 5n extvalj0 1 1 0 2 1 3 0 1 1 0

13、5(2) 設(shè) 目標(biāo)為 t= “ abcaabbabcabaacbacba ,模式為 p= “ abcabaa 計(jì)算模式p的naxtval函數(shù)值； 不寫(xiě)出算法，只畫(huà)出利用KMP算法進(jìn)行模式匹配時(shí)每一趟的匹配過(guò)程。 p的nextval函數(shù)值為 0110132。 ( p的next函數(shù)值為 0111232 )。 利用KMP改良的nextval)算法，每趟匹配過(guò)程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配

14、：abcaabbabcabaac bacba(成功)abcabaa(i=15,j=8)(3)數(shù)組A中，每個(gè)元素Ai,j的長(zhǎng)度均為32個(gè)二進(jìn)位，行下標(biāo)從-1到9，列下標(biāo)從1到11,從首地址S開(kāi)始連續(xù)存放主存儲(chǔ)器中，主存儲(chǔ)器字長(zhǎng)為16位。求： 存放該數(shù)組所需多少單元？ 存放數(shù)組第 4 列所有元素至少需多少單元？ 數(shù)組按行存放時(shí)，元素A7,4 的起始地址是多少？ 數(shù)組按列存放時(shí)，元素A4,7 的起始地址是多少？每個(gè)元素 32 個(gè)二進(jìn)制位，主存字長(zhǎng) 16 位，故每個(gè)元素占 2 個(gè)字長(zhǎng)，行下標(biāo)可平移至 1 到 11。(1) 242(2)22(3)s+182( 4) s+1 42 請(qǐng)將香蕉banana用工

15、具H( ) Head( )，T( ) Tail() 從L中取出。 L=(apple,(orange,(strawberry,(banana),peach),pear)H( H(T( H( T( H( T( L)(5)寫(xiě)一個(gè)算法統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件(字 符串中的合法字符為 A-Z 這 26 個(gè)字母和 0-9 這 10個(gè)數(shù)字)。void Count ()是字符串輸入結(jié)束標(biāo)志InvertStore(A);Ai+ = ch; m, 1.n含有 m*n 個(gè)整數(shù)。 寫(xiě)一個(gè)算法判斷 a 中所有元素是否互不相同 ?輸出相關(guān)信息 (yes/no) ； 試分析算法的時(shí)間復(fù)雜度。

16、 題目分析 判斷二維數(shù)組中元素是否互不相同，只有逐個(gè)比擬 , 找到一對(duì)相等的元素， 就可結(jié)論為不是互不相同。 如何到達(dá)每個(gè)元素同其它元素比擬一次且只一次？在當(dāng)前行，每個(gè)元素要同本行后面的元素比擬一次(下面第一個(gè)循環(huán)控制變量 p 的 for 循環(huán))，然后同第 i+1 行及以后各行元素比擬一次，這就是循環(huán)控制變量 k 和 p 的二層 for 循環(huán)。 int JudgEqual(ing amn, int m,n)算法討論對(duì)數(shù)組中元素各比擬一次，比擬次數(shù)為n。最正確情況(已排好，正數(shù)在前，負(fù)數(shù)在后 ) 不發(fā)生交換，最差情況 ( 負(fù)數(shù)均在正數(shù)前面 ) 發(fā)生 n/2 次交換。用類 c 編寫(xiě)，數(shù)組界 偶是

17、0.n-1 ?？臻g復(fù)雜度為 O(1).第 5 章 樹(shù)和二叉樹(shù)1選擇題( 1)把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是()。A.唯一的E.有多種C.有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子D.有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子(2) 由 3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(shù)？()A. 2 B . 3 C . 4D. 5(3) 一棵完全二叉樹(shù)上有 1001 個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是( )。A. 250B . 500 C . 254 D. 501(4) 一個(gè)具有 1025 個(gè)結(jié)點(diǎn)的二叉樹(shù)的高 h 為( )。A. 11 B . 10C. 11至 1025之間 D . 10 至 1024 之間(5) 深度為h的滿

18、m叉樹(shù)的第k層有()個(gè)結(jié)點(diǎn)。(仁k=h)A. mk-1B . mk-1C. mh-1D . mh-1(6) 利用二叉鏈表存儲(chǔ)樹(shù)，那么根結(jié)點(diǎn)的右指針是()。A.指向最左孩子B.指向最右孩子C .空 D .非空(7) 對(duì)二叉樹(shù)的結(jié)點(diǎn)從 1 開(kāi)始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子 的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用()遍歷實(shí)現(xiàn)編號(hào)。A.先序B.中序C. 后序 D.從根開(kāi)始按層次遍歷( 8)假設(shè)二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹(shù)的位置，利 用( )遍歷方法最適宜。A.前序B .中序C .后序 D .按層次(9)在以下存儲(chǔ)形式中，

19、 ( )不是樹(shù)的存儲(chǔ)形式？A.雙親表示法 B .孩子鏈表表示法C .孩子兄弟表示法D.順序存儲(chǔ)表示法( 10)一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，那么該二叉樹(shù)一定滿足( )。A.所有的結(jié)點(diǎn)均無(wú)左孩子B.所有的結(jié)點(diǎn)均無(wú)右孩子C.只有一個(gè)葉子結(jié)點(diǎn)D.是任意一棵二叉樹(shù)( 11)某二叉樹(shù)的前序序列和后序序列正好相反，那么該二叉樹(shù)一定是()的二叉樹(shù)。A.空或只有一個(gè)結(jié)點(diǎn)B.任一結(jié)點(diǎn)無(wú)左子樹(shù)C.高度等于其結(jié)點(diǎn)數(shù)D.任一結(jié)點(diǎn)無(wú)右子樹(shù)(12) 假設(shè)X是二叉中序線索樹(shù)中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，那么X的前驅(qū)為()。A. X的雙親B. X的右子樹(shù)中最左的結(jié)點(diǎn)C. X的左子樹(shù) 中最右結(jié)點(diǎn)D

20、. X的左子樹(shù)中最右葉結(jié)點(diǎn)(13) 引入二叉線索樹(shù)的目的是()。A.加快查找結(jié)點(diǎn)的前驅(qū)或后 繼的速度 B .為了能在二叉樹(shù)中方便的進(jìn)行插入與刪 除C.為了能方便的找到雙親D.使二叉樹(shù)的遍歷結(jié)果唯一( 14)線索二叉樹(shù)是一種()結(jié)構(gòu)。A.邏輯B .(15)設(shè)F是一個(gè)森林, 右指針域?yàn)榭盏慕Y(jié)點(diǎn)有(A. n-1 B邏輯和存儲(chǔ)C .物理D .線性B是由F變換得的二叉樹(shù)。假設(shè) F中有n個(gè)非終端結(jié)點(diǎn)，那么 B中 )個(gè)。n+12應(yīng)用題(1)試找出滿足以下條件的二叉樹(shù)先序序列與后序序列相同先序序列與中序序列相同n+2中序序列與后序序列相同中序序列與層次遍歷序列相同先序遍歷二叉樹(shù)的順序是根一左子樹(shù)一右子樹(shù) 后序

21、遍歷順序是：(1)(2)(3)，中序遍歷“左子樹(shù)一根一右子樹(shù)“左子樹(shù)一右子樹(shù)一根，根據(jù)以上原那么，此題解答如下： 假設(shè)先序序列與后序序列相同，那么或?yàn)榭諛?shù)，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹(shù) 假設(shè)中序序列與后序序列相同，那么或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹(shù)的二叉樹(shù). 假設(shè)先序序列與中序序列相同，那么或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù).(4) 假設(shè)中序序列與層次遍歷序列相同，那么或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù)(2)設(shè)一棵二叉樹(shù)的先序序列：A B D F C E G H ，中序序列: 畫(huà)出這棵二叉樹(shù)。 畫(huà)出這棵二叉樹(shù)的后序線索樹(shù)。 將這棵二叉樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的樹(shù)(或森林)。nullAM

22、H(3(3)為丿 V ) ? ? ? ? ?(1)假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別? 試為這8個(gè)字母設(shè)計(jì)赫夫曼編碼。 試設(shè)計(jì)另一種由二進(jìn)制表示的等長(zhǎng)編碼方案。對(duì)于上述實(shí)例，比擬兩種方案的優(yōu)缺點(diǎn)。解：方案1;哈夫曼編碼 先將概率放大100倍，以方便構(gòu)造哈夫曼樹(shù)。w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)那么:32【(2,3 ), 6, (7,10)】,19, 21,(100(192132(28)(17)(11)710 6(5)23字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率1110020031111041110510方案比擬:方案 1 的 WPL= 2+4+5+=+=方案

23、2 的 WPA 3+=3結(jié)論：哈夫曼編碼優(yōu)于等長(zhǎng)二進(jìn)制編碼(4)以下字符AB、C、DE、F、G的權(quán)值分別為3、12、7、4、2、8，11，試填寫(xiě)出其對(duì)應(yīng)哈夫曼樹(shù) HT的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)。初態(tài):weightpare ntIchildrchild13000212000370004400052000680007110008000900010000110001200013000weightpare ntlchildrchild13800212120037100044900528006810007111100859519911481015123611201397122713210134701112終

24、態(tài)3.算法設(shè)計(jì)題以二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫(xiě)以下算法:(1)統(tǒng)計(jì)二叉樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)。int LeafNodeCou nt(BiTree T)if(T=NULL) return 0; D .圖C；隊(duì)列C.(9)用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常借助( A.棧B.隊(duì)列C.來(lái)實(shí)現(xiàn)算法。.圖(10)深度優(yōu)先遍歷類似于二叉樹(shù)的A.先序遍歷B .中序遍歷后序遍歷.層次遍歷(11)廣度優(yōu)先遍歷類似于二叉樹(shù)的A.先序遍歷B .中序遍歷后序遍歷D.層次遍歷(12)圖的BFS生成樹(shù)的樹(shù)高比 DFS生成樹(shù)的樹(shù)高(A.小B.相等C .小或相等大或相等(13)圖的鄰接矩陣如下圖，那么從頂點(diǎn)0出發(fā)按深度優(yōu)先遍

25、歷的結(jié)果是()。01111011001001A.0 2 4 3 1 5 61000100B.0 1 3 6 5 4 21100110C.0 1 3 4 2 5 61011010D.0 3 6 1 5 4 200011011100010圖鄰接矩陣0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是),按A. 0 1 3 2C. 0 3 2 1D. 0 1 2 3圖鄰接表15下面方法可以判斷出一個(gè)有向圖是否有環(huán)。A .深度優(yōu)先遍歷B.拓?fù)渑判駽 .求最短路徑2.應(yīng)用題1如下圖的有向圖，請(qǐng)給出: 每個(gè)頂點(diǎn)的入度和出度； 鄰接矩陣；鄰接表；逆鄰接表。.求關(guān)鍵路徑14圖的鄰接表如下圖，那么從頂點(diǎn) 深度優(yōu)先遍歷的結(jié)果是D(點(diǎn)23

26、4呂6A*321L22:出度0213130 0 0 0 O 1OO1OO 0 1 0 Q 0 1 0 0 10 11 1 0 0 0 0 0 J i 0 0 1 0.鄲接表連鄰接農(nóng)(2)如下圖的無(wú)向網(wǎng)，請(qǐng)給出: 鄰接矩陣； 鄰接表； 最小生成樹(shù)4 34553555 5976554976533226圖無(wú)向網(wǎng)a b c d efffffd5fd5fe7ff3Ag2Ah6Ag6A(3) 圖的鄰接矩陣如所示。試分別畫(huà)出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。00 D0圖有向網(wǎng)4有向網(wǎng)如下圖，試用迪杰斯特拉算法求出從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑,完成表。V、終 點(diǎn)i=1i=2i=3i

27、=4i=5i=6b15(a,b)15b)15(a,b)15(a,b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)eoo10(a,c,e)10(a,c,e)foo6(a,c,fLgcoco16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S終點(diǎn)集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b5試對(duì)圖所示的 AOE網(wǎng)： 求這個(gè)工程最早可能在什么時(shí) 間結(jié)束； 求每個(gè)活動(dòng)的最早開(kāi)始時(shí)間和 最遲開(kāi)始時(shí)間； 確定哪些活動(dòng)是關(guān)鍵活動(dòng)圖AOE-網(wǎng)【解答】按拓?fù)溆行虻捻樞?/p>

28、計(jì)算各個(gè)頂點(diǎn)的最早可能開(kāi)始時(shí)間Ve和最遲允許開(kāi)始時(shí)間VI。然后再計(jì)算各個(gè)活動(dòng)的最早可能開(kāi)始時(shí)間e和最遲允許開(kāi)始時(shí)間I，根據(jù)I - e = 0?來(lái)確定關(guān)鍵活動(dòng)，從而確定關(guān)鍵路徑。123456Ve01915293843Vl01915373843e00151919152938l170152719273738-e1700801280此工程最早完成時(shí)間為 43。關(guān)鍵路徑為3 算法設(shè)計(jì)題(1)分別以鄰接矩陣和鄰接表作為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)以以下圖的根本操作: 增添一個(gè)新頂點(diǎn)v, lnsertVex(G, v); 刪除頂點(diǎn)v及其相關(guān)的邊，DeleteVex(G , v); 增加一條邊 ,InsertArc(G ,v,w); 刪除一條邊 ,DeleteArc(G ,v,w)。dj)j.adj=1;+;return OK;dj=0;5return OK;Status Delete_Arc(MGraph &G,char v,char w)dj) j.adj=0;return OK; 余算法請(qǐng)自行寫(xiě)出 .Status Insert_Arc(ALGraph &G,char v,char w)irstarc;p;p=p