《數(shù)據(jù)結(jié)構(gòu)》習(xí)題匯編07-第七章-圖-試題

第七章圖試題一、單項選擇題在無向圖中定義頂點得度為與它相關(guān)聯(lián)得()得數(shù)目。A、頂點 B、邊 C、權(quán) D、權(quán)值在無向圖中定義頂點vi與vj之間得路徑為從vi到達(dá)vj得一個()。A、頂點序列 B、邊序列 C、權(quán)值總與 D、邊得條數(shù)圖得簡單路徑就是指()不重復(fù)得路徑。A、權(quán)值 B、頂點 C、邊 D、邊與頂點均設(shè)無向圖得頂點個數(shù)為n,則該圖最多有()條邊。A、n1 B、n(n1)/2 C、n(n+1)/2 D、n(n1)n個頂點得連通圖至少有()條邊。A、n1 B、n C、n+1 D、0在一個無向圖中,所有頂點得度數(shù)之與等于所有邊數(shù)得()倍。A、3 B、2 C、1 D、1/2若采用鄰接矩陣法存儲一個n個頂點得無向圖,則該鄰接矩陣就是一個()。A、上三角矩陣 B、稀疏矩陣 C、對角矩陣 D、對稱矩陣圖得深度優(yōu)先搜索類似于樹得()次序遍歷。A、先根 B、中根 C、后根 D、層次圖得廣度優(yōu)先搜索類似于樹得()次序遍歷。A、先根 B、中根 C、后根 D、層次在用Kruskal算法求解帶權(quán)連通圖得最小(代價)生成樹時,通常采用一個()輔助結(jié)構(gòu),判斷一條邊得兩個端點就是否在同一個連通分量上。A、位向量 B、堆 C、并查集 D、生成樹頂點集合在用Kruskal算法求解帶權(quán)連通圖得最小(代價)生成樹時,選擇權(quán)值最小得邊得原則就是該邊不能在圖中構(gòu)成()。A、重邊 B、有向環(huán) C、回路 D、權(quán)值重復(fù)得邊在用Dijkstra算法求解帶權(quán)有向圖得最短路徑問題時,要求圖中每條邊所帶得權(quán)值必須就是()。A、非零 B、非整 C、非負(fù) D、非正在一個連通圖中進(jìn)行深度優(yōu)先搜索得到一棵深度優(yōu)先生成樹,樹根結(jié)點就是關(guān)節(jié)點得充要條件就是它至少有()子女。 A、1 B、2 C、3 D、0設(shè)有向圖有n個頂點與e條邊,采用鄰接表作為其存儲表示,在進(jìn)行拓?fù)渑判驎r,總得計算時間為()。A、O(nlog2e) B、O(n+e) C、O(ne) D、O(n2)設(shè)有向圖有n個頂點與e條邊,采用鄰接矩陣作為其存儲表示,在進(jìn)行拓?fù)渑判驎r,總得計算時間為()。A、O(nlog2e) B、O(n+e) C、O(ne) D、O(n2)設(shè)G1=(V1,E1)與G2=(V2,E2)為兩個圖,如果V1V2,E1E2,則稱()。 A、G1就是G2得子圖 B、G2就是G1得子圖 C、G1就是G2得連通分量 D、G2就是G1得連通分量有向圖得一個頂點得度為該頂點得()。 A、入度 B、出度C、入度與出度之與 D、(入度﹢出度))／2一個連通圖得生成樹就是包含圖中所有頂點得一個()子圖。 A、極小 B、連通 C、極小連通 D、無環(huán)n(n＞1)個頂點得強(qiáng)連通圖中至少含有()條有向邊。 A、n1 B、n n(n1)/2 D、n(n1)在一個帶權(quán)連通圖G中,權(quán)值最小得邊一定包含在G得()生成樹中。 A、某個最小 B、任何最小 C、廣度優(yōu)先 D、深度優(yōu)先對于具有e條邊得無向圖,它得鄰接表中有()個邊結(jié)點。 A、e1 B、e C、2(e1) D、2e對于如圖所示得帶權(quán)有向圖,從頂點1到頂點5得最短路徑為()。 A、1,4,5 B、1,2,3,5 C、1,4,3,5 D、1,2,4,3,5112613819554123具有n個頂點得有向無環(huán)圖最多可包含()條有向邊。 A、n1 B、n C、n(n1)/2 D、n(n1)一個有n個頂點與n條邊得無向圖一定就是()。 A、連通得 B、不連通得 C、無環(huán)得 D、有環(huán)得在n個頂點得有向無環(huán)圖得鄰接矩陣中至少有()個零元素。 A、n B、n(n1)/2 C、n(n+1)/2 D、n(n1)對于有向圖,其鄰接矩陣表示比鄰接表表示更易于()。 A、求一個頂點得度 B、求一個頂點得鄰接點 C、進(jìn)行圖得深度優(yōu)先遍歷 D、進(jìn)行圖得廣度優(yōu)先遍歷在一個有向圖得鄰接矩陣表示中,刪除一條邊<vi,vj>需要耗費得時間就是()。 A、O(1) B、O(i) C、O(j) D、O(i+j)與鄰接矩陣相比,鄰接表更適合于存儲()圖。 A、無向 B、連通 C、稀疏 D、稠密圖設(shè)一個有n個頂點與e條邊得有向圖采用鄰接矩陣表示,要計算某個頂點得出度所耗費得時間就是()。 A、O(n) B、O(e) C、O(n+e) D、O(n2)為了實現(xiàn)圖得廣度優(yōu)先遍歷,BFS算法使用得一個輔助數(shù)據(jù)結(jié)構(gòu)就是()。 A、棧 B、隊列 C、二叉樹 D、樹參考答案: 1、B 2、A 3、B 4、B 5、A6、B 7、D 8、A 9、D 10、C11、C 12、C 13、B 14、B 15、D16、A 17、C 18、C 19、B 20、A21、D 22、D 23、C 24、D 25、C26、A 27、A 28、C 29、A 30、B二、填空題圖得定義包含一個頂點集合與一個邊集合。其中,頂點集合就是一個有窮________集合。用鄰接矩陣存儲圖,占用存儲空間數(shù)與圖中頂點個數(shù)________關(guān),與邊數(shù)________關(guān)。n(n﹥0)個頂點得無向圖最多有________條邊,最少有________條邊。n(n﹥0)個頂點得連通無向圖最少有________條邊。若3個頂點得圖G得鄰接矩陣為,則圖G一定就是________向圖。n(n﹥0)個頂點得連通無向圖各頂點得度之與最少為________。設(shè)圖G=(V,E),V={V0,V1,V2,V3},E={(V0,V1),(V0,V2),(V0,V3),(V1,V3)},則從頂點V0開始得圖G得不同深度優(yōu)先序列有________種,例如______________。設(shè)圖G=(V,E),V={P,Q,R,S,T},E={<P,Q>,<P,R>,<Q,S>,<R,T>},從頂點P出發(fā),對圖G進(jìn)行廣度優(yōu)先搜索所得得所有序列為__________與___________。n(n﹥0)個頂點得無向圖中頂點得度得最大值為________。在重連通圖中每個頂點得度至少為________。在非重連通圖中進(jìn)行深度優(yōu)先搜索,則深度優(yōu)先生成樹得根為關(guān)節(jié)點得充要條件就是它至少有________個子女。(n﹥0)個頂點得連通無向圖得生成樹至少有________條邊。101個頂點得連通網(wǎng)絡(luò)N有100條邊,其中權(quán)值為1,2,3,4,5,6,7,8,9,10得邊各10條,則網(wǎng)絡(luò)N得最小生成樹各邊得權(quán)值之與為_________。在使用Kruskal算法構(gòu)造連通網(wǎng)絡(luò)得最小生成樹時,只有當(dāng)一條候選邊得兩個端點不在同一個________上,才有可能加入到生成樹中。深度優(yōu)先生成樹得高度比廣度優(yōu)先生成樹得高度________。求解帶權(quán)連通圖最小生成樹得Prim算法適合于________圖得情形,而Kruskal算法適合于________圖得情形。求解最短路徑得Dijkstra算法適用于各邊上得權(quán)值________得情形。若設(shè)圖得頂點數(shù)為n,則該算法得時間復(fù)雜度為________。若對一個有向無環(huán)圖進(jìn)行拓?fù)渑判?再對排在拓?fù)溆行蛐蛄兄械盟许旤c按其先后次序重新編號,則在相應(yīng)得鄰接矩陣中所有________元素將集中到對角線以上。參考答案: 1、非空 2、有,無 3、n(n1)/2,0 4、n1 5、有 6、2(n1) 7、4,V0V1V3V2(或V0V2V1V3,V0V2V3V1,V0V3V1V2)8、PQRST與PRQTS 9、n1 10、211、2 12、n1 13、55014、連通分量 15、高 16、稠密,稀疏17、非負(fù),O(n2) 18、非零(或值為1得)三、判斷題一個圖得子圖可以就是空圖,頂點個數(shù)為0。存儲圖得鄰接矩陣中,矩陣元素個數(shù)不但與圖得頂點個數(shù)有關(guān),而且與圖得邊數(shù)也有關(guān)。一個有1000個頂點與1000條邊得有向圖得鄰接矩陣就是一個稀疏矩陣。對一個連通圖進(jìn)行一次深度優(yōu)先搜索(depthfirstsearch)可以遍訪圖中得所有頂點。有n(n≥1)個頂點得無向連通圖最少有n1條邊。有n(n≥1)個頂點得有向強(qiáng)連通圖最少有n條邊。圖中各個頂點得編號就是人為得,不就是它本身固有得,因此可以因為某種需要改變頂點得編號。如果無向圖中各個頂點得度都大于2,則該圖中必有回路。如果有向圖中各個頂點得度都大于2,則該圖中必有回路。圖得深度優(yōu)先搜索(depthfirstsearch)就是一種典型得回溯搜索得例子,可以通過遞歸算法求解。圖得廣度優(yōu)先搜索(breadthfirstsearch)算法不就是遞歸算法。有n個頂點、e條邊得帶權(quán)有向圖得最小生成樹一般由n個頂點與n1條邊組成。對于一個邊上權(quán)值任意得帶權(quán)有向圖,使用Dijkstra算法可以求一個頂點到其它各個頂點得最短路徑。對一個有向圖進(jìn)行拓?fù)渑判?topologicalsorting),一定可以將圖得所有頂點按其關(guān)鍵碼大小排列到一個拓?fù)溆行虻眯蛄兄?。有回路得有向圖不能完成拓?fù)渑判?。對任何用頂點表示活動得網(wǎng)絡(luò)(AOV網(wǎng))進(jìn)行拓?fù)渑判虻媒Y(jié)果都就是唯一得。用邊表示活動得網(wǎng)絡(luò)(AOE網(wǎng))得關(guān)鍵路徑就是指從源點到終點得路徑長度最長得路徑。對于AOE網(wǎng)絡(luò),加速任一關(guān)鍵活動就能使整個工程提前完成。對于AOE網(wǎng)絡(luò),任一關(guān)鍵活動延遲將導(dǎo)致整個工程延遲完成。在AOE網(wǎng)絡(luò)中,可能同時存在幾條關(guān)鍵路徑,稱所有關(guān)鍵路徑都需通過得有向邊為橋。如果加速這樣得橋上得關(guān)鍵活動就能使整個工程提前完成。用鄰接矩陣存儲一個圖時,在不考慮壓縮存儲得情況下,所占用得存儲空間大小只與圖中得頂點個數(shù)有關(guān),而與圖得邊數(shù)無關(guān)。鄰接表只能用于有向圖得存儲,鄰接矩陣對于有向圖與無向圖得存儲都適用。鄰接矩陣只適用于稠密圖(邊數(shù)接近于頂點數(shù)得平方),鄰接表適用于稀疏圖(邊數(shù)遠(yuǎn)小于頂點數(shù)得平方)存儲無向圖得鄰接矩陣就是對稱得,因此只要存儲鄰接矩陣得下(上)三角部分就可以了。連通分量就是無向圖中得極小連通子圖。強(qiáng)連通分量就是有向圖中得極大強(qiáng)連通子圖。在AOE網(wǎng)絡(luò)中一定只有一條關(guān)鍵路徑。參考答案: 1、否 2、否 3、就是 4、就是 5、就是6、否 7、就是 8、就是 9、否 10、就是11、就是 12、否 13、否 14、否 15、就是16、否 17、就是 18、否 19、就是 20、就是21、就是 22、否 23、就是 24、就是 25、否26、就是 27、否 四、運算題V0V1V0V1V2V5V4V3V6V7V8V0V1V0V1V2V5V4V3V6V7V8V0V1V2V0V1V2V5V4V3V6V7V8⑩⑩①②③④⑤⑥⑦⑧⑨設(shè)連通圖G如圖所示,(1)如果有關(guān)節(jié)點,請找出所有得關(guān)節(jié)點。(2)如果想把該連通圖變成重連通圖,至少在圖中加幾條邊？如何加？對于如圖所示得有向圖,試寫出: (1)從頂點①出發(fā)進(jìn)行深度優(yōu)先搜索所得到得深度優(yōu)先生成樹; (2)從頂點②出發(fā)進(jìn)行廣度優(yōu)先搜索所得到得廣度優(yōu)先生成樹①①②③④⑤V1V2V3V4V1V2V3V4V7V6V0V5表示圖得另一種方法就是使用關(guān)聯(lián)矩陣INC[][]。其中,一行對應(yīng)于一個頂點,一列對應(yīng)于一條邊。因此,如果邊j依附于頂點i,則INC[i][j]=1。如果ADJ就是圖G=(V,E)得鄰接矩陣,INC就是關(guān)聯(lián)矩陣,試說明在什么條件下將有ADJ=INCINCTI,其中,INCT就是矩陣INC得轉(zhuǎn)置矩陣,I就是單位矩陣。兩個nn得矩陣得乘積C=AB定義為公式中得定義為按位加,定義為按位乘。設(shè)無向圖G如圖所示。試畫出該圖得鄰接矩陣與關(guān)聯(lián)矩陣。001234567e0e1e2e3e4e5e7e6e8e901230123456618753426 (始頂點號,終頂點號,權(quán)值)(,,)(,,) (,,)(,,)(,,)設(shè)有一個連通網(wǎng)絡(luò)如圖所示。試采用prim算法從頂點0開始構(gòu)造最小生成樹。(寫出加入生成樹頂點集合S與選擇邊Edge得順序)11234650910751187S:頂點號Edge:(頂點,頂點,權(quán)值)0(,,)0(,,)0(,,)0(,,)0(,,)0計算連通網(wǎng)得最小生成樹得Dijkstra算法可簡述如下:將連通網(wǎng)所有得邊以方便得次序逐條加入到初始為空得生成樹得邊集合T中。每次選擇并加入一條邊時,需要判斷它就是否會與先前加入T中得邊構(gòu)成回路。如果構(gòu)成了回路,則從這個回路中將權(quán)值最大得邊退選。如果以鄰接矩陣作為連通網(wǎng)得存儲結(jié)構(gòu)(僅使用矩陣得上三角部分),并在鄰接矩陣得下三角部分記錄最小生成樹得邊信息。試以如下所示得圖G為例,畫出構(gòu)造出最小生成樹及其鄰接矩陣,并在括號內(nèi)填入每次選擇得邊與可能去掉得邊。26262111①②⑤④③擇得邊去掉得邊(頂點,頂點,權(quán)值)(頂點,頂點,權(quán)值)(,,)(,,)(,,)(,,)(,,)(,,)(,,)(,,)(,,)(,,)(,,)(,,)(,,)(,,)(,,)(,,)(,,)(,,)(,,)(,,)有八項活動,每項活動要求得前驅(qū)如下:活動A0A1A2A3A4A5A6A7前驅(qū)無前驅(qū)A0A0A0,A2A1A2,A4A3A5,A6(1)試畫出相應(yīng)得AOV網(wǎng)絡(luò),并給出一個拓?fù)渑判蛐蛄小?2)試改變某些結(jié)點得編號,使得用鄰接矩陣表示該網(wǎng)絡(luò)時所有對角線以下得元素全為0。試對下圖所示得AOE網(wǎng)絡(luò)(1)這個工程最早可能在什么時間結(jié)束。(2)確定哪些活動就是關(guān)鍵活動。畫出由所有關(guān)鍵活動構(gòu)成得圖,指出哪些活動加速可使整個工程提前完成。1111151910223445566設(shè)帶權(quán)有向圖如圖所示。試采用Dijkstra算法求從頂點0到其她各頂點得最短路徑與最短路徑長度。77182445912340一項工程由六個子工程p1,p2,,p6組成。這些子工程之間有下列關(guān)系:p1<p2,p3<p6,p4<p3,p2<p6,p4<p5,p1<p3,p5<p6。符號“<”表示“領(lǐng)先于”得關(guān)系。例如,p2<p6表示p2完成后p6才能開始。試給出該工程得三種可能得施工順序。設(shè)一有向圖如下所示,請問該有向圖就是否為強(qiáng)連通圖,并畫出該有向圖所有得強(qiáng)連通分量。gfgfecabd參考答案:圖G對應(yīng)得鄰接矩陣為執(zhí)行廣度優(yōu)先搜索得結(jié)果為V0V1V3V2V4V7V6V5V8,搜索結(jié)果不唯一。圖G對應(yīng)得鄰接表為:331320310350126766213780V01V12V23V34V45V56V67V78V8∧∧∧∧∧∧∧∧∧執(zhí)行深度優(yōu)先搜索得結(jié)果為:V0V1V4V3V6V7V8V2V5,搜索結(jié)果不唯一。圖GV0V1V0V1V2V5V4V3V6V7V8圖G中得關(guān)節(jié)點為:V1,V2,V3,V6。(1)關(guān)節(jié)點為①,②,③,⑦,⑧ (2)至少加四條邊(1,10),(3,4),(4,5),(5,6)。從③得子孫結(jié)點⑩到③得祖先結(jié)點①引一條邊,從②得子孫結(jié)點④到根①得另一分支③引一條邊,并將⑦得子孫結(jié)點⑤、⑥與結(jié)點④連結(jié)起來,可使其變?yōu)橹剡B通圖。(解答不唯一)⑩⑩①②③④⑤⑥⑦⑧⑨以頂點①為根得深度優(yōu)先生成樹(不唯一):①②①②③④⑤①②③④⑤以頂點②為根得廣度優(yōu)先生成樹:①①②③④⑤V1V1V2V3V4V7V6V0V5V1V1V2V3V4V7V6V0V5當(dāng)圖中得頂點個數(shù)等于邊得條數(shù)時,ADJ=INC*INCTI成立。圖G對應(yīng)得鄰接矩陣為:對應(yīng)得關(guān)聯(lián)矩陣為:應(yīng)用Kruskal算法順序選出最小生成樹得各條邊為:01234501234515342 (0,3,1) (2,5,2) (1,4,3) (3,5,4) (3,4,5)采用prim算法從頂點0開始構(gòu)造最小生成樹得過程:S:頂點號Edge:(頂點,頂點,權(quán)值)0(0,1,9)0,1(1,3,5)0,1,3(1,2,7)0,1,3,2(2,4,6)0,1,3,2,4(2,5,7)0,1,3,2,4,5112346509757最小生成樹及其鄰接矩陣如圖所示①①②⑤④③⑥14165611選擇得邊去掉得邊(頂點,頂點,權(quán)值)(頂點,頂點,權(quán)值)(2,1,16)(,,)(5,1,14)(,,)(6,1,21)(,,)(6,2,19)(6,1,21)(6,4,11)(,,)(6,5,26)(6,5,26)(5,4,18)(6,2,19)(4,2,9)(5,4,18)(3,2,5)(,,)(4,3,6)(4,2,9) 選擇順序不唯一。相應(yīng)得AOV網(wǎng)絡(luò)為:A0A0A1A2A3A4A5A6A7一個拓?fù)渑判蛐蛄袨?A0,A1,A4,A2,A5,A3,A6,A7。注意:拓?fù)渑判蚪Y(jié)果不唯一。按拓?fù)溆行虻么涡驅(qū)λ许旤c從新編號:原編號A0A1A4A2A5A3A6A7新編號A0A1A2A3A4A5A6A7A0A0A1A3A5A2A4A6A7 相應(yīng)鄰接矩陣為:針對下圖所示得AOE網(wǎng)絡(luò)1111151910223445566各頂點(事件)得最早可能開始時間Ve(i)與最遲允許開始時間Vl(i)參瞧下表:頂點123456Ve01915293843Vl01915373843 各邊(活動)得最早可能開始時間Ee(k)與最遲允許開始時間El(k)參瞧下表:邊<1,2><1,3><3,2><2,5><3,5><2,4><4,6><5,6>Ee00151915192938El170151927273738 如果活動k得最早可能開始時間Ee(k)與最遲允許開始時間El(k)相等,則該活動就是關(guān)鍵活動。本題得關(guān)鍵活動為<1,3>,<3,2>,<2,5>,<5,6>,它們組成關(guān)鍵路徑。這些關(guān)鍵活動中任一個提前完成,整個工程就能提前完成。 整個工程最早在43天完成。由關(guān)鍵活動組成得AOV網(wǎng)絡(luò)如圖所示。1111151910223445566717182445912340 應(yīng)用Dijkstra算法求從頂點V0到其她各頂點得最短路徑Path與最短路徑長度Len得步驟如下:步驟V0V1V2V3V4動作PathLenPathLenPathLenPathLen1V0V14—∞V0V37—∞選V0V1V0V14V0V1V28V0V37—∞參照V1調(diào)整2V0V14V0V1V28V0V37—∞選V0V3V0V14V0V1V28V0V37V0V3V412參照V3調(diào)整3V0V14V0V1V28V0V37V0V3V412選V0V1V2V0V14V0V1V28V0V37V0V1V2V410參照V2調(diào)整4V0V14V0V1V28V0V37V0V1V2V410選V0V1V2V4p1p2p6p4p1p2p6p4p5p3 可能得施工順序有: p1,p2,p4,p3,p5,p6 p1,p4,p2,p3,p5,p6 p4,p5,p1,p3,p2,p6該圖得強(qiáng)連通分量分別為:eecabggfd五、算法分析題已知有向圖得鄰接矩陣表示及其一個算法描述如下:A=A=0111100100000111100000110constintMaxVertices=5;structGraph{ //圖得鄰接矩陣表示 intEdge[MaxVertices][MaxVertices]; //有向圖鄰接距陣 intCurrentNode; //有向圖當(dāng)前結(jié)點數(shù) intCurrentEdges; //當(dāng)前邊數(shù)}intunknown(inti){intd=0; for(intj=0;j<CurrentNode;j++){ if(Edge[i][j]!=0)d++; if(Edge[j][i]!=0)d++; } returnd; }若定義圖得一個對象GraphG,則執(zhí)行操作G、unknown(3)后得返回值就是多少？試說明該算法得功能及時間復(fù)雜度。已知有向圖得鄰接矩陣表示及其一個操作算法描述如下:A=A=0110100000000111100000010constintMaxVertices=5;structGraph{ //圖得鄰接矩陣表示 intEdge[MaxVertices][MaxVertices]; //有向圖鄰接距陣 intCurrentNode; //有向圖當(dāng)前結(jié)點數(shù) intCurrentEdges; //當(dāng)前邊數(shù)}voidunknown(inti){ intd,j; d=0; for(j=0;j<CurrentNode;j++){ if(Edge[i][j]){d++;Edge[i][j]=0;} if(Edge[j][i]){d++;Edge[j][i]=0;} } CurrentEdges=d; }若定義圖得一個對象GraphG,試寫出執(zhí)行操作G、unknown(3)后該圖得鄰接矩陣,并說明該算法得功能。已知有向圖得鄰接表類得表示得形式描述如下:structEdge{ //鄰接表中邊結(jié)點得定義 intdest; //鄰接得結(jié)點 floatcost; //邊得權(quán)值 Edge*link;};template<classType> structVertex{ //鄰接表中頂點得定義 Typedata; Edge*adj;};template<classType> structGraph{ //鄰接表 Vertex<Type>*NodeTable; //頂點表intNumVertices; //當(dāng)前頂點個數(shù) intNumEdges; //當(dāng)前邊數(shù) intDegree[MaxVertices]; //各個頂點得度得記錄數(shù)組 }//下列算法就是計算有向圖中各個頂點得度,并保存在數(shù)組Degree[]中。請在處//填入合適得內(nèi)容,使其成為一個完整得算法。voidFindDegree(){inti;Edge*p=NULL; for(i=0;i<NumVertices;i++)Degree[i]=(1); for(i=0;i<NumVertices;i++) for(p=NodeTable[i]、adj;p!=NULL;p=p>link){ (2); (3); } };已知有向圖得鄰接表類得表示得形式描述如下:structEdge{ //鄰接表中邊結(jié)點得定義 intdest; //鄰接得結(jié)點 floatcost; //邊得權(quán)值 Edge*link;};template<classType> structVertex{ //鄰接表中頂點得定義 Typedata; Edge*adj;};template<classType> structGraph{ //鄰接表 Vertex<Type>*NodeTable; //頂點表intNumVertices; //當(dāng)前頂點個數(shù) intNumEdges; //當(dāng)前邊數(shù) intDegree[MaxVertices]; //各個頂點得度得記錄數(shù)組 }//下列算法就是計算有向圖G中一個頂點vi得入度。請在處填入合適得內(nèi)容,//使其成為一個完整得算法。voidFindDegree(inti){intdeg,j; Edge*p=NULL; deg=0; for(j=0;j<NumVertices;j++){p=NodeTable[j]、adj; while((1)){ p=p>link; if(p==NULL)break; } if(p!=NULL)(2);}returndeg; }已知有向圖得鄰接表類得表示得形式描述如下:structEdge{ //鄰接表中邊結(jié)點得定義 intdest; //鄰接得結(jié)點 floatcost; //邊得權(quán)值 Edge*link;};template<classType> structVertex{ //鄰接表中頂點得定義 Typedata; Edge*adj;};template<classType> structGraph{ //鄰接表 Vertex<Type>*NodeTable; //頂點表intNumVertices; //當(dāng)前頂點個數(shù) intNumEdges; //當(dāng)前邊數(shù) intDegree[MaxVertices]; //各個頂點得度得記錄數(shù)組 }//下列算法就是從有向圖G中刪除所有以vi為弧頭得有向邊。請在處填入合適//得內(nèi)容,使其成為一個完整得算法。voidDeletEdge(inti){intde=0,j;Edge*p,*q; if(i>=NumVertices) {cout<<"錯誤輸入"<<endl;exit(1);} for(j=0;j<NumVertices;j++){p=NodeTable[j]、adj; while((1)) {q=p;p=p>link;} if(p!=NULL){if(p!=NodeTable[j]、adj)q>link=p>link; else(2); deletep; de++; } } NumEdges=NumEdgesde;}已知帶權(quán)圖得鄰接矩陣表示與鄰接表類表示得形式描述分別如下:鄰接矩陣得定義#defineINFINITYINT_MAX //INT_MAX為最大整數(shù),表示∞constintMaxVertices=20;template<classType>structAdjMatrix{ Type*NodeTable; //頂點表定義 floatarr[Maxvertices][MaxVertices]; //鄰接矩陣定義intNumVertices; //當(dāng)前頂點個數(shù) intNumEdges; //當(dāng)前邊數(shù)}; (2)鄰接表定義structEdge{ //鄰接表中邊結(jié)點得定義 intdest; //鄰接得結(jié)點 floatcost; //邊得權(quán)值 Edge*link;};template<classType> structVertex{ //鄰接表中頂點得定義 Typedata; Edge*adj;};template<classType> structAdjTable{ //鄰接表 Vertex<Type>*NodeTable; //頂點表intNumVertices; //當(dāng)前頂點個數(shù) intNumEdges; //當(dāng)前邊數(shù) }//下列算法就是根據(jù)一個圖得鄰接矩陣建立該圖得鄰接表,請在處填入合適//得內(nèi)容,使其成為一個完整得算法。AdjTable<Type>*convertM(){//將圖得鄰接矩陣(用this指針指示)轉(zhuǎn)換為鄰接表,函數(shù)返回鄰接表得地址。 AdjTable<Type>*A;Edge*e; A>NodeTable=newVertex<Type>[NumVertices]; A>NumEdges=NumEdges; A>NumVertices=NumVertices; for(inti=0;i<NumVertices;i++){ A>NodeTable[i]、data=NodeTable[i]; A>NodeTable[i]、adj=(1); for(intj=0;j<NumVertices;j++) if(arr[i][j]!=INFINITY&&arr[i][j]!=0){ e=newEdge;e>dest=j;e>cost=(2); e>link=A>NodeTable[i]、adj;(3); } } returnA; }已知帶權(quán)圖得鄰接矩陣表示與鄰接表類表示得形式描述分別如下:(1)鄰接矩陣得定義#defineINFINITYINT_MAX //INT_MAX為最大整數(shù),表示∞constintMaxVertices=20;template<classType>structAdjMatrix{ Type*NodeTable; //頂點表定義 floatarr[Maxvertices][MaxVertices]; //鄰接矩陣定義intNumVertices; //當(dāng)前頂點個數(shù) intNumEdges; //當(dāng)前邊數(shù)}; (2)鄰接表定義structEdge{ //鄰接表中邊結(jié)點得定義 intdest; //鄰接得結(jié)點 floatcost; //邊得權(quán)值 Edge*link;};template<classType> structVertex{ //鄰接表中頂點得定義 Typedata; Edge*adj;};template<classType> structAdjTable{ //鄰接表 Vertex<Type>*NodeTable; //頂點表intNumVertices; //當(dāng)前頂點個數(shù) intNumEdges; //當(dāng)前邊數(shù) }//下列算法就是根據(jù)一個圖得鄰接表存儲結(jié)構(gòu)建立該圖得鄰接矩陣存儲結(jié)構(gòu),//請在處填入合適得內(nèi)容,使其成為一個完整得算法AdjMatrix<Type>*convertAL(){//將圖得鄰接表(用this指針指示)轉(zhuǎn)換為鄰接矩陣,函數(shù)返回鄰接矩陣得地址。 AdjMatrix<Type>*A;inti,j; Edge*p; A>NodeTable=newVertex<Type>[NumVertices]; A>arr=newfloat[Maxvertices][MaxVertices];A>NumEdges=NumEdges; A>NumVertices=NumVertices;for(i=0;i<NumVertices;i++){ for(j=0;j<NumVertices;j++)A>arr[i][j]=INFINITY; A>NodeTable[i]=_________(1)_________; } for(i=0;i<NumVertices;i++){ p=NodeTable[i]、adj; while(p!=NULL){ A>arr[i][p>dest]=_____(2)__________; ________________(3)________________; } }}已知圖得鄰接表與逆鄰接表得形式描述如下:structEdge{ //結(jié)點定義 intdest; //鄰接結(jié)點 floatcost; //邊得權(quán)值 Edge*link;};template<classType>structVertex{ //頂點定義 Typedata; Edge*adj;};template<classType>structGraph{ //鄰接表與逆鄰接表定義Vertex<Type>*NodeTable; //鄰接表頂點表 Vertex<Type>*OppositNodeTable; //逆鄰接表頂點表 intNumVertices; //當(dāng)前頂點個數(shù) intNumEdges; //當(dāng)前邊數(shù)}

//下列算法就是根據(jù)一個圖得鄰接表存儲結(jié)構(gòu)建立該圖得逆鄰接表存儲結(jié)構(gòu),請//在處填入合適得內(nèi)容,使其成為一個完整得算法。voidconvertM(){ inti;Edge*p,*q; OppositNodeTable=newVertex<Type>[NumVertices]; for(i=0;i<NumVertices;i++){ OppositNodeTable[i]、data=NodeTable[i]、data; OppositNodeTable[i]、adj=NULL; } for(i=0;i<NumVertices;i++) { p=NodeTable[i]、adj; while(p!=NULL){ q=newEdge; q>dest=i; q>cost=p>cost; _____________(1)_____________; OppositNodeTable[p>dest]、adj=q; ______________(2)_____________; } }}參考答案:(1)執(zhí)行操作后得返回值就是5。 //2分(2)算法得功能就是計算有向圖中一個頂點得度。 //2分 算法得時間復(fù)雜度就是O(n),n為圖得頂點個數(shù)。 //2分執(zhí)行操作G、unknown(3)后,圖得鄰接矩陣為: //3分A=A=0110100000000010000000000算法得功能就是從圖中刪除所有與某個頂點相關(guān)得邊。 //3分填空結(jié)果(1)0 //2分(2)Degree[p>dest]++ //2分(3)Degree[i]++ //2分(注:(2),(3)互換也正確)填空結(jié)