1圖中有關(guān)路徑的定義是(路徑

1、第七章 圖一、選擇題 一、選擇題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，則該圖最多有（ ）條邊。A．n-1 B．n(n-1)/2 C． n(n+1)/2

2、 D．0 E．n2【清華大學(xué) 1998 一、5 （2 分） 】 【西安電子科技大 1998 一、6 （2 分） 】【北京航空航天大學(xué) 1999 一、7 （2 分） 】3．一個(gè) n 個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為（ ）?！菊憬髮W(xué) 1999 四、4 (4分)】A．n-1 B．n C．n+1 D．nlogn；4．要連通具有 n 個(gè)頂點(diǎn)的有

3、向圖，至少需要（ ）條邊。 【北京航空航天大學(xué) 2000 一、6(2 分） 】A．n-l B．n C．n+l D．2n5．n 個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目（ ） 。 【中山大學(xué) 1998 二、9 （2 分） 】A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）6．一

4、個(gè)有 n 個(gè)結(jié)點(diǎn)的圖，最少有（ ）個(gè)連通分量，最多有（ ）個(gè)連通分量。A．0 B．1 C．n-1 D．n【北京郵電大學(xué) 2000 二、5 （20/8 分） 】7．在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（ ）倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（ ）倍。 【哈爾濱工業(yè)大學(xué) 2001 二、3 （

5、2分） 】A．1/2 B．2 C．1 D．48．用有向無環(huán)圖描述表達(dá)式(A+B)*（（A+B）/A） ，至少需要頂點(diǎn)的數(shù)目為( )。 【中山大學(xué) 1999 一、14】A．5 B．6 C．8 D．9 9．用 DFS 遍歷一個(gè)無環(huán)有向圖，并在 DFS 算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的

6、頂點(diǎn)序列是( )。A．逆拓?fù)溆行?B．拓?fù)溆行?C．無序的 【中科院軟件所 1998】10．下面結(jié)構(gòu)中最適于表示稀疏無向圖的是（ ） ，適于表示稀疏有向圖的是（ ） 。A．鄰接矩陣 B．逆鄰接表 C．鄰接多重表 D．十字鏈表 E．鄰接（1） （2 分） 】①．A．1354267 B．1347652 C．1534276

7、D．1247653 E．以上答案均不正確②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正確 19．下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）：【東北大學(xué) 2000 4、2（4分） 】A．深度優(yōu)先遍歷 B. 拓?fù)渑判?C. 求最短路徑 D. 求關(guān)鍵路徑20. 在圖采用鄰接表存儲時(shí)，求最小生成樹的 Prim 算法的時(shí)間復(fù)雜度為(

8、 )。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ù) n-1 次: a：（ 2 ） ；b：（ 3 ） ；最后：（ 4 ） 。 【南京理工大學(xué) 1997 一、11_14 （8 分）

9、】（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 不屬于

10、 VT，且（i，j）上的權(quán)最大（3） ．A．頂點(diǎn) i 加入 VT， （i,j）加入 ET B. 頂點(diǎn) j 加入 VT， （i,j）加入 ETC. 頂點(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 中有 n-1 條邊時(shí)為生成樹，否則無解 D．

11、ET 中無回路時(shí)，為生成樹，否則無解22. (1). 求從指定源點(diǎn)到其余各頂點(diǎn)的迪杰斯特拉（Dijkstra）最短路徑算法中弧上權(quán)不能為負(fù)的原因是在實(shí)際應(yīng)用中無意義；(2). 利用 Dijkstra 求每一對不同頂點(diǎn)之間的最短路徑的算法時(shí)間是 O(n3 ) ；（圖用鄰接矩陣表示）(3). Floyd 求每對不同頂點(diǎn)對的算法中允許弧上的權(quán)為負(fù)，但不能有權(quán)和為負(fù)的回路。上面不正確的是（ ） 。 【南京理工大學(xué) 2000 一、21 （

12、1.5 分） 】A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3)23．當(dāng)各邊上的權(quán)值( )時(shí)，BFS 算法可用來解決單源最短路徑問題。 【中科院計(jì)算所 2000一、3 (2 分） 】A．均相等 B．均互不相等 C．不一定相等24. 求解最短路徑的 Floyd 算法的時(shí)間復(fù)雜度為( )。 【合肥工業(yè)大學(xué) 1999 一、2 （2分） 】A