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

1、第七章 圖一、選擇題 一、選擇題1．圖中有關(guān)路徑的定義是（ ） 。 【北方交通大學(xué) 2001 一、24 （2 分） 】A．由頂點和相鄰頂點序偶構(gòu)成的邊所形成的序列 B．由不同頂點所形成的序列C．由不同邊所形成的序列 D．上述定義都不是2．設(shè)無向圖的頂點個數(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．一個 n 個頂點的連通無向圖，其邊的個數(shù)至少為（ ）。【浙江大學(xué) 1999 四、4 (4分)】A．n-1 B．n C．n+1 D．nlogn；4．要連通具有 n 個頂點的有

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

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

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

6、頂點序列是( )。A．逆拓撲有序 B．拓撲有序 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．下面哪一方法可以判斷出一個有向圖是否有環(huán)（回路）：【東北大學(xué) 2000 4、2（4分） 】A．深度優(yōu)先遍歷 B. 拓撲排序 C. 求最短路徑 D. 求關(guān)鍵路徑20. 在圖采用鄰接表存儲時，求最小生成樹的 Prim 算法的時間復(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 分別放頂點和邊，初始為（ 1 ） ，下面步驟重復(fù) n-1 次: a：（ 2 ） ；b：（ 3 ） ；最后：（ 4 ） 。 【南京理工大學(xué) 1997 一、11_14 （8 分）

9、】（1） ．A．VT，ET 為空 B．VT 為所有頂點，ET 為空C．VT 為網(wǎng)中任意一點，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．頂點 i 加入 VT， （i,j）加入 ET B. 頂點 j 加入 VT， （i,j）加入 ETC. 頂點 j 加入 VT， （i,j）從 ET 中刪去 D．頂點 i,j 加入 VT， （i,j）加入ET（4） ．A．ET 中為最小生成樹 B．不在 ET 中的邊構(gòu)成最小生成樹C．ET 中有 n-1 條邊時為生成樹，否則無解 D．

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

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