數(shù)據(jù)結構 習題 第七章 圖

1、第七章 圖一、選擇題1圖中有關路徑的定義是（ ）?！颈狈浇煌ù髮W 2001 一、24 （2分）】A由頂點和相鄰頂點序偶構成的邊所形成的序列 B由不同頂點所形成的序列C由不同邊所形成的序列 D上述定義都不是2設無向圖的頂點個數(shù)為n，則該圖最多有（ ）條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En2【清華大學 1998 一、5 （2分）】【西安電子科技大 1998 一、6 （2分）】【北京航空航天大學 1999 一、7 （2分）】3一個n個頂點的連通無向圖，其邊的個數(shù)至少為（ ）?！菊憬髮W 1999 四、4 (4分)】An-1 Bn Cn+1 Dnlogn；4要連通具有n個

2、頂點的有向圖，至少需要（ ）條邊?！颈本┖娇蘸教齑髮W 2000 一、6(2分）】An-l Bn Cn+l D2n5n個結點的完全有向圖含有邊的數(shù)目（）。【中山大學 1998 二、9 （2分）】An*n n（n） Cn2 Dn*（nl）6一個有n個結點的圖，最少有（ ）個連通分量，最多有（ ）個連通分量。A0 B1 Cn-1 Dn【北京郵電大學 2000 二、5 （20/8分）】7在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)（ ）倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（ ）倍?！竟枮I工業(yè)大學 2001 二、3 （2分）】A1/2 B2 C1 D48用有向無環(huán)圖描述表達式

3、(A+B)*（A+B）/A），至少需要頂點的數(shù)目為( )?！局猩酱髮W1999一、14】A5 B6 C8 D9 9用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印相應的頂點，則輸出的頂點序列是( )。A逆拓撲有序 B拓撲有序 C無序的 【中科院軟件所 1998】10下面結構中最適于表示稀疏無向圖的是（ ），適于表示稀疏有向圖的是（ ）。A鄰接矩陣 B逆鄰接表 C鄰接多重表 D十字鏈表 E鄰接表 【北京工業(yè)大學 2001 一、3 (2分)】11下列哪一種圖的鄰接矩陣是對稱矩陣？（ ）【北方交通大學 2001 一、11 （2分）】A有向圖 B無向圖 CAOV網(wǎng) DAOE網(wǎng)12 從鄰接陣矩可以

4、看出，該圖共有（）個頂點；如果是有向圖該圖共有（） 條??；如果是無向圖，則共有（）條邊?！局锌圃很浖?1999 六、2（3分）】A9 B3 C6 D1 E以上答案均不正確A5 B4 C3 D2 E以上答案均不正確A5 B4 C3 D2 E以上答案均不正確13當一個有N個頂點的圖用鄰接矩陣A表示時，頂點Vi的度是（ ）?！灸暇├砉ご髮W1998一、4(2分）】A B C D+ 14用相鄰矩陣A表示圖，判定任意兩個頂點Vi和Vj之間是否有長度為m 的路徑相連，則只要檢查（ ）的第i行第j列的元素是否為零即可。【武漢大學 2000 二、7】AmA BA CAm DAm-115. 下列說法不正確的是（

5、 ）。【青島大學 2002 二、9 （2分）】A圖的遍歷是從給定的源點出發(fā)每一個頂點僅被訪問一次 C圖的深度遍歷不適用于有向圖B遍歷的基本算法有兩種：深度遍歷和廣度遍歷 D圖的深度遍歷是一個遞歸過程16無向圖G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是（ ）。【南京理工大學 2001 一、14 （1.5分）】Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b17. 設圖如右所示，在下面的5個序列中，符合深

6、度優(yōu)先遍歷的序列有多少？（ ）【南京理工大學 2000 一、20 （1.5分）】a e b d f c a c f d e b a e d f c b a e f d c b a e f d b cA5個 B4個 C3個 D2個 第17題圖 第18題圖18.下圖中給出由7個頂點組成的無向圖。從頂點1出發(fā)，對它進行深度優(yōu)先遍歷得到的序列是( )，而進行廣度優(yōu)先遍歷得到的頂點序列是（ ）?！局锌圃很浖?1999 六、2-（1）（2分）】A B C D E以上答案均不正確A B Cl D E以上答案均不正確 19下面哪一方法可以判斷出一個有向圖是否有環(huán)（回路）：【東北大學 2000 4、2（4分）

7、】A深度優(yōu)先遍歷 B. 拓撲排序 C. 求最短路徑 D. 求關鍵路徑20. 在圖采用鄰接表存儲時，求最小生成樹的 Prim 算法的時間復雜度為( )。A. O(n) B. O(n+e) C. O(n2) D. O(n3)【合肥工業(yè)大學 2001 一、2 （2分）】21. 下面是求連通網(wǎng)的最小生成樹的prim算法：集合VT，ET分別放頂點和邊，初始為（ 1 ），下面步驟重復n-1次: a：（ 2 ）；b：（ 3 ）；最后：（ 4 ）。【南京理工大學 1997 一、11_14 （8分）】（1）AVT，ET為空 BVT為所有頂點，ET為空 CVT為網(wǎng)中任意一點，ET為空 DVT為空，ET為網(wǎng)中所有邊

8、（2）A. 選i屬于VT，j不屬于VT，且（i，j）上的權最小 B選i屬于VT，j不屬于VT，且（i，j）上的權最大 C選i不屬于VT，j不屬于VT，且（i，j）上的權最小 D選i不屬于VT，j不屬于VT，且（i，j）上的權最大（3）A頂點i加入VT，（i,j）加入ET B. 頂點j加入VT，（i,j）加入ET C. 頂點j加入VT，（i,j）從ET中刪去 D頂點i,j加入VT，（i,j）加入ET（4）AET 中為最小生成樹 B不在ET中的邊構成最小生成樹 CET中有n-1條邊時為生成樹，否則無解 DET中無回路時，為生成樹，否則無解22. (1). 求從指定源點到其余各頂點的迪杰斯特拉（Di

9、jkstra）最短路徑算法中弧上權不能為負的原因是在實際應用中無意義；(2). 利用Dijkstra求每一對不同頂點之間的最短路徑的算法時間是O(n3 ) ；（圖用鄰接矩陣表示）(3). Floyd求每對不同頂點對的算法中允許弧上的權為負，但不能有權和為負的回路。上面不正確的是（ ）?！灸暇├砉ご髮W 2000 一、21 （1.5分）】A(1),(2),(3) B(1) C(1),(3) D(2),(3)23當各邊上的權值( )時，BFS算法可用來解決單源最短路徑問題。【中科院計算所2000一、3 (2分）】A均相等 B均互不相等 C不一定相等24. 求解最短路徑的Floyd算法的時間復雜度為(

10、 )?！竞戏使I(yè)大學 1999 一、2 （2分）】AO（n） B. O（n+c） C. O（n*n） D. O（n*n*n）25已知有向圖G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,G的拓撲序列是（ ）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V7【北京航空航天大學 2000 一、7 （2分）】26若一個有向圖的鄰接距陣中,主對角線以下的元素均為零,則該圖的拓撲有序序列（ ）。 A存在 B不存在【中科院計算所1998 二、6 (2分）】【中

11、國科技大學 1998二、6（2分）】27一個有向無環(huán)圖的拓撲排序序列（ ）是唯一的?！颈本┼]電大學 2001 一、3 （2分）】A一定 B不一定28. 在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是（ ）。 AG中有弧 BG中有一條從Vi到Vj的路徑 CG中沒有弧 DG中有一條從Vj到Vi的路徑 【南京理工大學 2000 一、9 （1.5分）】29. 在用鄰接表表示圖時，拓撲排序算法時間復雜度為( )。A. O(n) B. O(ne) C. O(n*n) D. O(n*n*n) 【合肥工業(yè)大學 2000 一、2 （2分）】【南京理工大學 2001 一、9 （1.5分

12、）】【青島大學 2002 二、3 （2分）】30. 關鍵路徑是事件結點網(wǎng)絡中（ ）?！疚靼搽娮涌萍即髮W 2001應用 一、4 （2分）】A從源點到匯點的最長路徑 B從源點到匯點的最短路徑C最長回路 D最短回路31. 下面關于求關鍵路徑的說法不正確的是（ ）。【南京理工大學 1998 一、12 （2分）】 A求關鍵路徑是以拓撲排序為基礎的 B一個事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相同 C一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差 D關鍵活動一定位于關鍵路徑上32下列關于AOE網(wǎng)的敘述中，不正確的是（ ）。A關鍵活動不按期完成就會影響整個工

13、程的完成時間B任何一個關鍵活動提前完成，那么整個工程將會提前完成C所有的關鍵活動提前完成，那么整個工程將會提前完成D某些關鍵活動提前完成，那么整個工程將會提前完成【北方交通大學 1999 一、7 （3分）】【北京工業(yè)大學 1999 一、1 (2分)】二、判斷題1.樹中的結點和圖中的頂點就是指數(shù)據(jù)結構中的數(shù)據(jù)元素。（ ）【青島大學 2001 四、1 （1分）】2在n個結點的無向圖中，若邊數(shù)大于n-1,則該圖必是連通圖。（ ）【中科院軟件所1997一、4(1分）】3對有n個頂點的無向圖，其邊數(shù)e與各頂點度數(shù)間滿足下列等式e=。（ ）【南京航空航天大學 1996 六、4 （1分）】4. 有e條邊的無

14、向圖，在鄰接表中有e個結點。（ ）【南京理工大學 1998 二、5 （2分）】5. 有向圖中頂點V的度等于其鄰接矩陣中第V行中的1的個數(shù)。（ ）【合肥工業(yè)大學2001二、7(1分）】6強連通圖的各頂點間均可達。（ ）【北京郵電大學 2000 一、3 （1分）】7強連通分量是無向圖的極大強連通子圖。（ ）【北京郵電大學 2002 一、7 （1分）】8連通分量指的是有向圖中的極大連通子圖。（ ）【燕山大學 1998 二、4 （2分）】9鄰接多重表是無向圖和有向圖的鏈式存儲結構。（ ）【南京航空航天大學 1995 五、5 （1分）】10. 十字鏈表是無向圖的一種存儲結構。（ ）【青島大學 2001

15、四、7 （1分）】11. 無向圖的鄰接矩陣可用一維數(shù)組存儲。（ ）【青島大學 2000 四、5 （1分）】12用鄰接矩陣法存儲一個圖所需的存儲單元數(shù)目與圖的邊數(shù)有關。（ ）【東南大學 2001 一、4 （1分）】 【中山大學 1994 一、3 （2分）】13有n個頂點的無向圖, 采用鄰接矩陣表示, 圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半。（ ）【北京郵電大學 1998 一、5 （2分）】14. 有向圖的鄰接矩陣是對稱的。（ ）【青島大學 2001 四、6 （1分）】15無向圖的鄰接矩陣一定是對稱矩陣，有向圖的鄰接矩陣一定是非對稱矩陣。（ ）【東南大學 2001 一、3 （1分）】【哈爾濱工

16、業(yè)大學 1999 三、4】16. 鄰接矩陣適用于有向圖和無向圖的存儲，但不能存儲帶權的有向圖和無向圖，而只能使用鄰接表存儲形式來存儲它。（ ）【上海海運學院 1995 一、9（1分） 1997 一、8（1分） 1998 一、9（1分）】17. 用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中結點個數(shù)有關，而與圖的邊數(shù)無關。（ ）【上海海運學院 1996 一、8 （1分） 1999 一、9 （1分）】18一個有向圖的鄰接表和逆鄰接表中結點的個數(shù)可能不等。（ ）【上海交通大學 1998 一、12】19需要借助于一個隊列來實現(xiàn)DFS算法。（ ）【南京航空航天大學 1996

17、 六、8 （1分）】 20. 廣度遍歷生成樹描述了從起點到各頂點的最短路徑。（ ）【合肥工業(yè)大學 2001 二、8 （1分）】21任何無向圖都存在生成樹。（ ）【北京郵電大學 2000 一、1 （1分）】22. 不同的求最小生成樹的方法最后得到的生成樹是相同的.（ ）【南京理工大學 1998 二、3 （2分）】23帶權無向圖的最小生成樹必是唯一的。（ ）【南京航空航天大學 1996 六、7 （1分）】24. 最小代價生成樹是唯一的。（ ）【山東大學 2001 一、5 （1分）】25一個網(wǎng)（帶權圖）都有唯一的最小生成樹。（ ）【大連海事大學 2001 一、14 （1分）】26連通圖上各邊權值均不

18、相同，則該圖的最小生成樹是唯一的。（ ）【哈爾濱工業(yè)大學 1999 三、3】27帶權的連通無向圖的最?。ù鷥r）生成樹（支撐樹）是唯一的。（ ）【中山大學 1994 一、10（2分）】28. 最小生成樹的KRUSKAL算法是一種貪心法（GREEDY）。（ ）【華南理工大學 2002 一、6（1分）】29. 求最小生成樹的普里姆(Prim)算法中邊上的權可正可負。（ ）【南京理工大學 1998 二、2 （2分）】30帶權的連通無向圖的最小代價生成樹是唯一的。（ ）【東南大學 2001 一、5（1分）】31. 最小生成樹問題是構造連通網(wǎng)的最小代價生成樹。（ ）【青島大學 2001 四、10（1分）】

19、32. 在圖G的最小生成樹G1中，可能會有某條邊的權值超過未選邊的權值。（ ）【合肥工業(yè)大學 2000 二、7（1分）】33. 在用Floyd 算法求解各頂點的最短路徑時，每個表示兩點間路徑的pathk-1I,J一定是pathk I,J的子集(k=1,2,3,n)。（ ）【合肥工業(yè)大學 2000 二、6 （1分）】34拓撲排序算法把一個無向圖中的頂點排成一個有序序列。（ ）【南京航空航天大學1995五、8（1分）】35拓撲排序算法僅能適用于有向無環(huán)圖。（ ）【南京航空航天大學 1997 一、7 （1分）】36. 無環(huán)有向圖才能進行拓撲排序。（ ）【青島大學 2002 一、7 （1分）2001

20、一、8 （1分）】37. 有環(huán)圖也能進行拓撲排序。（ ）【青島大學 2000 四、6 （1分）】38拓撲排序的有向圖中，最多存在一條環(huán)路。（ ）【大連海事大學 2001 一、6（1分）】39任何有向圖的結點都可以排成拓撲排序，而且拓撲序列不唯一。（ ）【上海交通大學1998 一、13】40. 既使有向無環(huán)圖的拓撲序列唯一，也不能唯一確定該圖。（ ）【合肥工業(yè)大學 2001 二、6（1分）】41若一個有向圖的鄰接矩陣對角線以下元素均為零，則該圖的拓撲有序序列必定存在。（ ）【中科院軟件所 1997 一、5 （1分）】42AOV網(wǎng)的含義是以邊表示活動的網(wǎng)。（ ）【南京航空航天大學 1995 五、7

21、 （1分）】43對一個AOV網(wǎng)，從源點到終點的路徑最長的路徑稱作關鍵路徑?！灸暇┖娇蘸教齑髮W1995五、9(1分）】44. 關鍵路徑是AOE網(wǎng)中從源點到終點的最長路徑。（ ）【青島大學 2000 四、10（1分）】45. AOE網(wǎng)一定是有向無環(huán)圖。（ ）【青島大學 2001 一、9 （1分）】46. 在表示某工程的AOE網(wǎng)中，加速其關鍵路徑上的任意關鍵活動均可縮短整個工程的完成時間。（ ）【長沙鐵道學院 1997 一、2 (1分)】47在AOE圖中，關鍵路徑上某個活動的時間縮短，整個工程的時間也就必定縮短。（ ）【大連海事大學 2001 一、15 （1分）】48在AOE圖中，關鍵路徑上活動的時

22、間延長多少，整個工程的時間也就隨之延長多少。（ ） 【大連海事大學 2001 一、16 （1分）】49當改變網(wǎng)上某一關鍵路徑上任一關鍵活動后，必將產(chǎn)生不同的關鍵路徑。【上海交通大學1998 一、14】三、填空題1.判斷一個無向圖是一棵樹的條件是_。2有向圖G的強連通分量是指_?！颈本┛萍即髮W 1997 一、7】3一個連通圖的_是一個極小連通子圖。【重慶大學 2000 一、1】4具有10個頂點的無向圖，邊的總數(shù)最多為_?！救A中理工大學 2000 一、7 （1分）】5若用n表示圖中頂點數(shù)目，則有_條邊的無向圖成為完全圖。【燕山大學1998 一、6（1分）】6. 設無向圖 G 有n 個頂點和e 條邊

23、，每個頂點Vi 的度為di（1=i=n，則e=_【福州大學 1998 二、2 (2分)】7G是一個非連通無向圖，共有28條邊，則該圖至少有_個頂點。【西安電子科技大 2001軟件一、8 （2分）】8. 在有n個頂點的有向圖中，若要使任意兩點間可以互相到達，則至少需要_條弧?！竞戏使I(yè)大學 2000 三、8 （2分）】9在有n個頂點的有向圖中，每個頂點的度最大可達_?！疚錆h大學 2000 一、3】10設G為具有N個頂點的無向連通圖，則G中至少有_條邊?！鹃L沙鐵道學院 1997 二、2 (2分)】11n個頂點的連通無向圖，其邊的條數(shù)至少為_?！竟枮I工業(yè)大學 2000 二、2（1分）】12如果含n

24、個頂點的圖形形成一個環(huán)，則它有_棵生成樹?！疚靼搽娮涌萍即髮W 2001軟件 一、2 （2分）】13N個頂點的連通圖的生成樹含有_條邊?！局猩酱髮W 1998 一、9 （1分）】14構造n個結點的強連通圖，至少有_條弧?！颈本┹p工業(yè)學院 2000 一、4（2分）】15有N個頂點的有向圖，至少需要量_條弧才能保證是連通的?！疚髂辖煌ù髮W 2000 一、3】16右圖中的強連通分量的個數(shù)為（ ）個?！颈本┼]電大學 2001 二、5 （2分）】17N個頂點的連通圖用鄰接矩陣表示時,該矩陣至少有_個非零元素。【中科院計算所1998 一、6（1分）】【中國科技大學1998 一、6（15/6分）】18在圖G的鄰

25、接表表示中，每個頂點鄰接表中所含的結點數(shù)，對于無向圖來說等于該頂點的_；對于有向圖來說等于該頂點的_?！狙嗌酱髮W 2001 二、5 （3分）】19. 在有向圖的鄰接矩陣表示中，計算第I個頂點入度的方法是_?！厩鄭u大學 2002 三、7 （2分）】20. 對于一個具有n個頂點e條邊的無向圖的鄰接表的表示，則表頭向量大小為_，鄰接表的邊結點個數(shù)為_。【青島大學 2002 三、8 （2分）】21. 遍歷圖的過程實質上是_，breath-first search遍歷圖的時間復雜度_；depth-first search遍歷圖的時間復雜度_，兩者不同之處在于_，反映在數(shù)據(jù)結構上的差別是_?！緩B門大學 1

26、999 一、3】22. 已知一無向圖G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現(xiàn)用某一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abecd，則采用的是_遍歷方法。【南京理工大學 1996 二、2 （2分）】23. 一無向圖G（V，E），其中V（G）=1,2,3,4,5,6,7，E（G）=（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）,對該圖從頂點3開始進行遍歷，去掉遍歷中未走過的邊，得一生成樹G(V，E）,V（G）=V（G），E（G）=（1,3），（3,6），（7,3），（1,2），

27、（1,5），（2,4），則采用的遍歷方法是_?！灸暇├砉ご髮W 1997 三、6 （1分）】24. 為了實現(xiàn)圖的廣度優(yōu)先搜索，除了一個標志數(shù)組標志已訪問的圖的結點外，還需_存放被訪問的結點以實現(xiàn)遍歷?！灸暇├砉ご髮W 1999 二、9 （2分）】25. 按下圖所示，畫出它的廣度優(yōu)先生成樹_和深度優(yōu)先生成樹_?！疚靼搽娮涌萍即髮W 1998 三、6 （5分）】26構造連通網(wǎng)最小生成樹的兩個典型算法是_?！颈本┛萍即髮W 1998 一、5】27求圖的最小生成樹有兩種算法，_算法適合于求稀疏圖的最小生成樹?！灸暇├砉ご髮W 2001 二、6（2分）】28. Prim（普里姆）算法適用于求_的網(wǎng)的最小生成樹；k

28、ruskal（克魯斯卡爾）算法適用于求_的網(wǎng)的最小生成樹?！緩B門大學 1999 一、4】29克魯斯卡爾算法的時間復雜度為_,它對_圖較為適合?！局锌圃河嬎闼?1999 二、3 （2分）】30對于含N個頂點E條邊的無向連通圖，利用Prim算法生成最小代價生成樹其時間復雜度為_，利用Kruskal算法生成最小代價生成樹其時間復雜度為_?！鹃L沙鐵道學院 1998 二、2 (4分)】31下面描述的是一種構造最小生成樹算法的基本思想。設要處理的無向圖包括n個節(jié)點V1，V2，Vn，用相鄰矩陣A表示，邊的權全是正數(shù)。請在下列劃線處填上正確敘述。（1）若（Vi，Vj）是邊，則A（i，j）的值等于_，若（Vi，

29、Vj）不是邊，則A（i，j）的值是一個比任何邊的權_， 矩陣的對角線元素全為0。 （2）構造最小生成樹過程中，若節(jié)點Vi已包括進生成樹，就把相鄰矩陣的對角線元素A（i，i）置成_，若（Vi，Vj）已包括進生成樹，就把矩陣元素A（i，j）置成_。（3）算法結束時，相鄰矩陣中_的元素指出最小生成樹的_?！旧綎|工業(yè)大學1998二、4(6分）】32. 有一個用于n個頂點連通帶權無向圖的算法描述如下：（1）設集合T1與T2，初始均為空；（2）在連通圖上任選一點加入T1；（3）以下步驟重復n-1次：a.在i屬于T1，j不屬于T1的邊中選最小權的邊；b.該邊加入T2。上述算法完成后，T2中共有_條邊，該算法

30、稱_算法，T2中的邊構成圖的_?！灸暇├砉ご髮W 1999 二、7 （4分）】33. 有向圖G可拓撲排序的判別條件是_。【長沙鐵道學院 1998 二、9(2分)】34. Dijkstra最短路徑算法從源點到其余各頂點的最短路徑的路徑長度按_次序依次產(chǎn)生，該算法弧上的權出現(xiàn)_情況時，不能正確產(chǎn)生最短路徑?！灸暇├砉ご髮W 1999 二、8（4分）】35. 求從某源點到其余各頂點的Dijkstra算法在圖的頂點數(shù)為10，用鄰接矩陣表示圖時計算時間約為10ms,則在圖的頂點數(shù)為40，計算時間約為_ms。【南京理工大學 2000 二、3 （1.5分）】36求最短路徑的Dijkstra算法的時間復雜度為_。

31、【哈爾濱工業(yè)大學 2001 一、5 （2分）】37.有向圖G=(V,E),其中 V(G)=0,1,2,3,4,5，用三元組表示弧及弧上的權d.E(G)為,，則從源點0到頂點3的最短路徑長度是_，經(jīng)過的中間頂點是_?！灸暇├砉ご髮W 1998 三、6 （4分）】38. 上面的圖去掉有向弧看成無向圖則對應的最小生成樹的邊權之和為_?！灸暇├砉ご髮W 1998 三、7（4分）】39設有向圖有n個頂點和e條邊，進行拓撲排序時，總的計算時間為_。【西安電子科技大學 1999軟件 一、7 （2分）】【武漢大學 2000 一、7】40AOV網(wǎng)中,結點表示_,邊表示_。AOE網(wǎng)中,結點表示_,邊表示_?！颈本├砉?/p>

32、大學 2001 七、3 （2分）】41在AOE網(wǎng)中，從源點到匯點路徑上各活動時間總和最長的路徑稱為_?！局貞c大學2000一、2】42在 AOV網(wǎng) 中，存在環(huán)意味著_，這是_的；對程序的數(shù)據(jù)流圖來說，它表明存在_。【廈門大學 1999 一、2】43. 當一個AOV網(wǎng)用鄰接表表示時，可按下列方法進行拓撲排序。（1）查鄰接表中入度為_的頂點，并進棧；（2）若棧不空，則輸出棧頂元素Vj，并退棧；查Vj的直接后繼Vk，對Vk入度處理，處理方法是_；（3）若?？諘r，輸出頂點數(shù)小于圖的頂點數(shù)，說明有_，否則拓撲排序完成?！灸暇├砉ご髮W 1996 二、3 （6分）】44已知圖的鄰接表結構為： CONST vt

33、xnum=圖的頂點數(shù) TYPE vtxptr=1.vtxnum; arcptr=arcnode; arcnode=RECORD adjvex:vtxptr; nextarc:arcptr END; vexnode=RECORD vexdata:和頂點相關的信息；firstarc:arcptr END;adjlist=ARRAYvtxptrOF vexnode; 本算法是實現(xiàn)圖的深度優(yōu)先遍歷的非遞歸算法。其中，使用一個順序棧stack。棧頂指針為top。visited為標志數(shù)組。PROC dfs(g:adjlist;v0:vtxptr); top=0; write(v0); visitedv0:

34、=ture; p:=gv0.firstarc; WHILE (top0)OR(pNIL)DOWHILE(1)_DOv:=p.adjvex;IF(2)_ THEN p:=p.nextarcELSE write(v); visitedv:=true; top:=top+1; stacktop:=p; (3)_ IF top0 THENp:=stacktop; top:=top-1; (4)_ ENDP.同濟大學 2000 二、2 (10分)】45下面的算法完成圖的深度優(yōu)先遍歷，請?zhí)羁铡?PROGRAM graph_traver; CONST nl=max_node_number; TYPE vtx

35、ptr=1.nl; vtxptr0=0.nl; arcptr=arcnode; arcnode=RECORD vexi ,vexj: vtxptr; nexti, nextj: arcptr; END;vexnode=RECORD vexdata: char; firstin，firstout: arcptr; END;graph=ARRAYvtxptr0 OF vexnode ;VAR ga:graph; n: integer; visited: ARRAYvtxptr0 OF boolean ; FUNC order (g: graph; v: char): vtxptr; (1)_; i

36、:=n;WHILE gi.vexdatav DO i:=i-1;order:=i;ENDF；PROC creat(var g: graph); readln(n,e);FOR i:= 1 TO n DO readln(gi.vexdata); gi.firstin :=NIL ; gi.firstout:=NIL;FOR k:= 1 TO e DO readln (vt,vh); i:=order (g,vt); j:=order (g,vh); new (p); p.vexi:=i ; p.vexj:=jp.nextj:= _(2)_; _(3)_ :=p;p.nexti:=: _(4)_;

37、 _(5)_ :=p;ENDP;FUNC firstadj(g:graph; v:char): vtxptr0; i:=order(g,v); p:=gi.firstout; IF pNIL THEN firstadj:=(6)_ELSE firstadj:=0;ENDF;FUNC nextadj(g:graph; v:char; w:char): vtxptr0; i:=order(g,v); j:=order(g,w); p:=(7)_; WHILE(pNIL ) AND (p.vexjj) DO(8)_; IF (9)_AND(10)_THEN nextadj:=p.nexti.vexj

38、 ELSE nextadj:=0;ENDF;PROC dfs(g:graph; v0:char); write(v0:2); visitedorder(g,v0):=true; w:=(11)_; WHILE w0 DO IF (12)_ THEN dfs(g,gw.vexdata); w:=(13)_;ENDP;PROC traver(g:graph);FOR i:=1 TO n DO visitedi:=false; FOR i:=1 TO n DO IF NOT visitedi THEN dfs(g,gi.vexdata);ENDP;BEGINcreat(ga); traver(ga)

39、;END. 【北方交通大學 1999 三（20分）】46n個頂點的有向圖用鄰接矩陣array表示，下面是其拓撲排序算法，試補充完整。注：（1）圖的頂點號從 0開始計； （2）indegree 是有n個分量的一維數(shù)組，放頂點的入度；（3）函數(shù) crein 用于算頂點入度； （4）有三個函數(shù)push(data),pop( ),check( )其含義為數(shù)據(jù) data進棧，退棧和測試棧是否空（不空返回1，否則0）。 crein( array ,indegree,n) for (i=0;in;i+) indegreei= (1)_) for(i=0,in;i+) for (j=0;jn; j+) ind

40、egreei+=array(2)_(3)_; topsort (array,indegree,n) count= (4)_) for (i=0;in;i+) if (5)_) push(i) while (check( ) vex=pop( ); printf(vex); count+; for (i=0;in;i+) k=array(6)_ if (7)_ ) indegreei-; if (8)_ ) push(i); if( countn) printf(“圖有回路”)； 【南京理工大學 2000 三、4 （6分）】 47假設給定的有向圖是用鄰接表表示，作為輸入的是圖中頂點個數(shù)n和邊的個

41、數(shù)m, 以及圖的m條邊。在下面的程序中，我們用readdata程序過程輸入圖的信息，并建立該圖的鄰接表；利用topol程序過程獲得圖中頂點的一個拓撲序列。PROGRAM topol_order(input , output) ; CONST maxn=20 ; TYPE nodeptr=nltype ; nltype=RECORD num : integer ; link : nodeptr END ; chtype=RECORD count : integer ; head : nodeptr END ; VAR ch : ARRAY 1 . maxn OF chtype ; m , n ,

42、 top : integer ; PROCEDURE readdata ;VAR i , j , u , v : integer ; p : nodeptr ;BEGIN write (input vertex number n= ); readln (n) ; write (input edge number m= ); readln(m) ; FOR i:=1 TO n DO BEGIN chi.count:= 0; chi.head:=NIL END; writeln(input edges :); FOR j:= 1 TO m DO BEGIN write( j :3 , : ) ;

43、readln( u , v ) ; new( p ) ; chv.count:=chv.count+1; p.num:=v; (1) _ ; (2) _; ENDEND ;PROCEDURE topol ; VAR i, j, k: integer; t: nodeptr ; BEGIN top:= 0 ; FOR i := 1 TO n DO IF chi.count=0 THEN BEGIN chi.count := top ;top := i END; i:= 0 ; WHILE (3) _ DO BEGIN (4) _; (5) _ ; write(j : 5) ;i:= i + 1

44、;t:=chj.head ; WHILE tNIL DO BEGIN k := t.num ; chk.count:=chk.count1 ; IF chk.count=0 THEN BEGIN chk.count:=top; top:=k END; (6) _ ; END END ; writeln; IF in THEN writeln (the network has a cycle!) END;BEGIN readdata ; writeln (output topol order : ); topolEND. 【復旦大學 1995 三 （18分）】V1V2V3V4V5V648如下為拓

45、撲排序的C程序，（1）列出對右圖執(zhí)行該程序后的輸出結果。（2）在程序空白處填上適當語句。void topsort(hdnodes graph ,int n)int i,j,k,top; node_pointer ptr ; top=-1; for (i=0; in; i+) if (!graphi.count)graphi.count=top; top=i; for (i=0; ilink)k=ptr-vertex; graphk.count-; if(3)_) graphk.count=top; top=k; 【浙江大學 2000 六(15分)】四、 應用題1（1）如果G1是一個具有n個頂點的連通無向圖，那么G1最多有多少條邊？G1最少有多少條邊？（2）如果G2是一個具有n個頂點的強連通有向圖，那么G2最多有多少條邊？G2最少有多少條邊？（3）如果G3是一個具有n個頂點的弱連通有向圖，那么G3最多有多少條邊？G3最少有多少條邊？ 【復旦大學 1997 一（9分）】2n個頂點的無向連通圖