【正文】 1998 二、3 （2分）】23．帶權(quán)無向圖的最小生成樹必是唯一的。（ ）【南京航空航天大學(xué) 1996 六、8 （1分）】 20. 廣度遍歷生成樹描述了從起點(diǎn)到各頂點(diǎn)的最短路徑。（ ）【上海海運(yùn)學(xué)院 1996 一、8 （1分） 1999 一、9 （1分）】18．一個(gè)有向圖的鄰接表和逆鄰接表中結(jié)點(diǎn)的個(gè)數(shù)可能不等。（ ）【東南大學(xué) 2001 一、3 （1分）】【哈爾濱工業(yè)大學(xué) 1999 三、4】16. 鄰接矩陣適用于有向圖和無向圖的存儲(chǔ)，但不能存儲(chǔ)帶權(quán)的有向圖和無向圖，而只能使用鄰接表存儲(chǔ)形式來存儲(chǔ)它。（ ）【北京郵電大學(xué) 1998 一、5 （2分）】14. 有向圖的鄰接矩陣是對(duì)稱的。（ ）【青島大學(xué) 2000 四、5 （1分）】12．用鄰接矩陣法存儲(chǔ)一個(gè)圖所需的存儲(chǔ)單元數(shù)目與圖的邊數(shù)有關(guān)。（ ）【南京航空航天大學(xué) 1995 五、5 （1分）】10. 十字鏈表是無向圖的一種存儲(chǔ)結(jié)構(gòu)。（ ）【北京郵電大學(xué) 2002 一、7 （1分）】8．連通分量指的是有向圖中的極大連通子圖。（ ）【合肥工業(yè)大學(xué)2001二、7(1分）】6．強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)。（ ）【南京航空航天大學(xué) 1996 六、4 （1分）】4. 有e條邊的無向圖，在鄰接表中有e個(gè)結(jié)點(diǎn)。（ ）【青島大學(xué) 2001 四、1 （1分）】2．在n個(gè)結(jié)點(diǎn)的無向圖中，若邊數(shù)大于n1,則該圖必是連通圖?！灸暇├砉ご髮W(xué) 1998 一、12 （2分）】 A．求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的 B．一個(gè)事件的最早開始時(shí)間同以該事件為尾的弧的活動(dòng)最早開始時(shí)間相同 C．一個(gè)事件的最遲開始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差 D．關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上32．下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（ ）。A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n) 【合肥工業(yè)大學(xué) 2000 一、2 （2分）】【南京理工大學(xué) 2001 一、9 （）】【青島大學(xué) 2002 二、3 （2分）】30. 關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ ）?！颈本┼]電大學(xué) 2001 一、3 （2分）】A．一定 B．不一定28. 在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（ ）。A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7【北京航空航天大學(xué) 2000 一、7 （2分）】26．若一個(gè)有向圖的鄰接距陣中,主對(duì)角線以下的元素均為零,則該圖的拓?fù)溆行蛐蛄校? ）?！局锌圃河?jì)算所2000一、3 (2分）】A．均相等 B．均互不相等 C．不一定相等24. 求解最短路徑的Floyd算法的時(shí)間復(fù)雜度為( )。上面不正確的是（ ）。A. O(n) B. O(n+e) C. O(n2) D. O(n3)【合肥工業(yè)大學(xué) 2001 一、2 （2分）】21. 下面是求連通網(wǎng)的最小生成樹的prim算法：集合VT，ET分別放頂點(diǎn)和邊，初始為（ 1 ），下面步驟重復(fù)n1次: a：（ 2 ）；b：（ 3 ）；最后：（ 4 ）。從頂點(diǎn)1出發(fā)，對(duì)它進(jìn)行深度優(yōu)先遍歷得到的序列是( ① )，而進(jìn)行廣度優(yōu)先遍歷得到的頂點(diǎn)序列是（ ② ）?！厩鄭u大學(xué) 2002 二、9 （2分）】A．圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問一次 C．圖的深度遍歷不適用于有向圖B．遍歷的基本算法有兩種：深度遍歷和廣度遍歷 D．圖的深度遍歷是一個(gè)遞歸過程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)}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（ ）?！灸暇├砉ご髮W(xué)1998一、4(2分）】A． B． C． D．+ 14．用相鄰矩陣A表示圖，判定任意兩個(gè)頂點(diǎn)Vi和Vj之間是否有長度為m 的路徑相連，則只要檢查（ ）的第i行第j列的元素是否為零即可。A．鄰接矩陣 B．逆鄰接表 C．鄰接多重表 D．十字鏈表 E．鄰接表 【北京工業(yè)大學(xué) 2001 一、3 (2分)】11．下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？（ ）【北方交通大學(xué) 2001 一、11 （2分）】A．有向圖 B．無向圖 C．AOV網(wǎng) D．AOE網(wǎng)12． 從鄰接陣矩 可以看出，該圖共有（①）個(gè)頂點(diǎn)；如果是有向圖該圖共有（②） 條??；如果是無向圖，則共有（③）條邊。【中山大學(xué)1999一、14】A．5 B．6 C．8 D．9 9．用DFS遍歷一個(gè)無環(huán)有向圖，并在DFS算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是( )。A．0 B．1 C．n1 D．n【北京郵電大學(xué) 2000 二、5 （20/8分）】7．在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（ ）倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（ ）倍?！颈本┖娇蘸教齑髮W(xué) 2000 一、6(2分）】A．nl B．n C．n+l D．2n5．n個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目（　　?。．n1 B．n(n1)/2 C． n(n+1)/2 D．0 E．n2【清華大學(xué) 1998 一、5 （2分）】【西安電子科技大 1998 一、6 （2分）】【北京航空航天大學(xué) 1999 一、7 （2分）】3．一個(gè)n個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為（ ）。第七章 圖一、選擇題1．圖中有關(guān)路徑的定義是（ ）。【北方交通大學(xué) 2001 一、24 （2分）】A．由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列 B．由不同頂點(diǎn)所形成的序列C．由不同邊所形成的序列 D．上述定義都不是2．設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（ ）條邊。【浙江大學(xué) 1999 四、4 (4分)】A．n1 B．n C．n+1 D．nlogn；4．要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（ ）條邊?！局猩酱髮W(xué) 1998 二、9 （2分）】A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）6．一個(gè)有n個(gè)結(jié)點(diǎn)的圖，最少有（ ）個(gè)連通分量，最多有（ ）個(gè)連通分量?！竟枮I工業(yè)大學(xué) 2001 二、3 （2分）】A．1/2 B．2 C．1 D．48．用有向無環(huán)圖描述表達(dá)式(A+B)*（（A+B）/A），至少需要頂點(diǎn)的數(shù)目為( )。A．逆拓?fù)溆行? B．拓?fù)溆行? C．無序的 【中科院軟件所 1998】10．下面結(jié)構(gòu)中最適于表示稀疏無向圖的是（ ），適于表示稀疏有向圖的是（ ）?！局锌圃很浖?1999 六、2（3分）】①．A．9 B．3 C．6 D．1 E．以上答案均不正確②．A．5 B．4 C．3 D．2 E．以上答案均不正確③．A．5 B．4 C．3 D．2 E．以上答案均不正確13．當(dāng)一個(gè)有N個(gè)頂點(diǎn)的圖用鄰接矩陣A表示時(shí)，頂點(diǎn)Vi的度是（ ）?！疚錆h大學(xué) 2000 二、7】A．mA B．A C．Am D．Am115. 下列說法不正確的是（ ）?！灸暇├砉ご髮W(xué) 2001 一、14 （）】A．a(chǎn),b,e,c,d,f B．a(chǎn),c,f,e,b,d C．a(chǎn),e,b,c,f,d D．a(chǎn),e,d,f,c,b17. 設(shè)圖如右所示，在下面的5個(gè)序列中，符合深度優(yōu)先遍歷的序列有多少？（ ）【南京理工大學(xué) 2000 一、20 （）】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 cA．5個(gè) B．4個(gè) C．3個(gè) D．2個(gè) 第17題圖 第18題圖?！局锌圃很浖?1999 六、2（1）（2分）】①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均不正確②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正確 19．下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）：【東北大學(xué) 2000 2（4分）】A．深度優(yōu)先遍歷 B. 拓?fù)渑判? C. 求最短路徑 D. 求關(guān)鍵路徑20. 在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹的 Prim 算法的時(shí)間復(fù)雜度為( )?！灸暇├砉ご髮W(xué) 1997 一、11_14 （8分）】（1）．A．VT，ET為空 B．VT為所有頂點(diǎn)，ET為空 C．VT為網(wǎng)中任意一點(diǎn)，ET為空 D．VT為空，ET為網(wǎng)中所有邊（2）．A. 選i屬于VT，j不屬于VT，且（i，j）上的權(quán)最小 B．選i屬于VT，j不屬于VT，且（i，j）上的權(quán)最大 C．選i不屬于VT，j不屬于VT，且（i，j）上的權(quán)最小 D．選i不屬于VT，j不屬于VT，且（i，j）上的權(quán)最大（3）．A．頂點(diǎn)i加入VT，（i,j）加入ET B. 頂點(diǎn)j加入VT，（i,j）加入ET C. 頂點(diǎn)j加入VT，（i,j）從ET中刪去 D．頂點(diǎn)i,j加入VT，（i,j）加入ET（4）．A．ET 中為最小生成樹 B．不在ET中的邊構(gòu)成最小生成樹 C．ET中有n1條邊時(shí)為生成樹，否則無解 D．ET中無回路時(shí)，為生成樹，否則無解22. (1). 求從指定源點(diǎn)到其余各頂點(diǎn)的迪杰斯特拉（Dijkstra）最短路徑算法中弧上權(quán)不能為負(fù)的原因是在實(shí)際應(yīng)用中無意義；(2). 利用Dijkstra求每一對(duì)不同頂點(diǎn)之間的最短路徑的算法時(shí)間是O(n3 ) ；（圖用鄰接矩陣表示）(3). Floyd求每對(duì)不同頂點(diǎn)對(duì)的算法中允許弧上的權(quán)為負(fù)，但不能有權(quán)和為負(fù)的回路?！灸暇├砉ご髮W(xué) 2000 一、21 （）】A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3)23．當(dāng)各邊上的權(quán)值( )時(shí)，BFS算法可用來解決單源最短路徑問題?！竞戏使I(yè)大學(xué) 1999 一、2 （2分）】A．O（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={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7},G的拓?fù)湫蛄惺牵? ）。 A．存在 B．不存在【中科院計(jì)算所1998 二、6 (2分）】【中國科技大學(xué) 1998二、6（2分）】27．一個(gè)有向無環(huán)圖的拓?fù)渑判蛐蛄校? ）是唯一的。 A．G中有弧Vi，Vj B．G中有一條從Vi到Vj的路徑 C．G中沒有弧Vi,Vj D．G中有一條從Vj到Vi的路徑 【南京理工大學(xué) 2000 一、9 （）】29. 在用鄰接表表示圖時(shí)，拓?fù)渑判蛩惴〞r(shí)間復(fù)雜度為( )?！疚靼搽娮涌萍即髮W(xué) 2001應(yīng)用 一、4 （2分）】A．從源點(diǎn)到匯點(diǎn)的最長路徑 B．從源點(diǎn)到匯點(diǎn)的最短路徑C．最長回路 D．最短回路31. 下面關(guān)于求關(guān)鍵路徑的說法不正確的是（ ）。A．關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B．任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成C．所有的關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成D．某些關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成【北方交通大學(xué) 1999 一、7 （3分）】【北京工業(yè)大學(xué) 1999 一、1 (2分)】二、 判斷題。（ ）【中科院軟件所1997一、4(1