數(shù)據(jù)結(jié)構(gòu)第7章例題與答案

　第七章 圖
一、選擇題
1．圖中有關(guān)路徑的定義是（ ）�！颈狈浇煌ù髮W(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 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個頂點的有向圖，至少需要（ ）條邊�！颈本┖娇蘸教齑髮W(xué) 2000 一、6(2分）】
a．n-l b．n c．n+l d．2n
5．n個結(jié)點的完全有向圖含有邊的數(shù)目（　　　）�！局猩酱髮W(xué) 1998 二、9 （2分）】
a．n*n ｂ．n（n＋１） c．n／2 d．n*（n－l）
6．一個有n個結(jié)點的圖，最少有（ ）個連通分量，最多有（ ）個連通分量。
a．0 b．1 c．n-1 d．n
【北京郵電大學(xué) 2000 二、5 （20/8分）】
7．在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)（ ）倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（ ）倍。【哈爾濱工業(yè)大學(xué) 2001 二、3 （2分）】
a．1/2 b．2 c．1 d．4
8．用有向無環(huán)圖描述表達式(a+b)*（（a+b）/a），至少需要頂點的數(shù)目為( )�！局猩酱髮W(xué)1999一、14】
a．5 b．6 c．8 d．9
9．用dfs遍歷一個無環(huán)有向圖，并在dfs算法退棧返回時打印相應(yīng)的頂點，則輸出的頂點序列是( )。
a．逆拓?fù)溆行? b．拓?fù)溆行? c．無序的 【中科院軟件所 1998】
10．下面結(jié)構(gòu)中最適于表示稀疏無向圖的是（ ），適于表示稀疏有向圖的是（ ）。
a．鄰接矩陣 b．逆鄰接表 c．鄰接多重表 d．十字鏈表 e．鄰接表
【北京工業(yè)大學(xué) 2001 一、3 (2分)】
11．下列哪一種圖的鄰接矩陣是對稱矩陣？（ ）【北方交通大學(xué) 2001 一、11 （2分）】
a．有向圖 b．無向圖 c．a(chǎn)ov網(wǎng) d．a(chǎn)oe網(wǎng)
12． 從鄰接陣矩 可以看出，該圖共有（①）個頂點；如果是有向圖該圖共有（②） 條弧；如果是無向圖，則共有（③）條邊。【中科院軟件所 1999 六、2（3分）】
①．a(chǎn)．9 b．3 c．6 d．1 e．以上答案均不正確
②．a(chǎn)．5 b．4 c．3 d．2 e．以上答案均不正確
③．a(chǎn)．5 b．4 c．3 d．2 e．以上答案均不正確
13．當(dāng)一個有n個頂點的圖用鄰接矩陣a表示時，頂點vi的度是（ ）�！灸暇├砉ご髮W(xué)1998一、4(2分）】
14．用相鄰矩陣a表示圖，判定任意兩個頂點vi和vj之間是否有長度為m 的路徑相連，則只要檢查（ ）的第i行第j列的元素是否為零即可�！疚錆h大學(xué) 2000 二、7】
a．ma b．a(chǎn) c．a(chǎn)m d．a(chǎn)m-1
15. 下列說法不正確的是（ ）�！厩鄭u大學(xué) 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)先遍歷，得到的頂點序列正確的是（ ）。【南京理工大學(xué) 2001 一、14 （1.5分）】
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,b
17. 設(shè)圖如右所示，在下面的5個序列中，符合深度優(yōu)先遍歷的序列有多少？（ ）
【南京理工大學(xué) 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 c
a．5個 b．4個 c．3個 d．2個

http://www.ardmore-hotel.com/

【數(shù)據(jù)結(jié)構(gòu)第7章例題與答案】相關(guān)文章：

數(shù)據(jù)結(jié)構(gòu)第2章例題與答案10-09

數(shù)據(jù)結(jié)構(gòu)第5章例題與答案10-09

數(shù)據(jù)結(jié)構(gòu)第11章例題與答案10-09

數(shù)據(jù)結(jié)構(gòu)第3章例題與答案10-09

數(shù)據(jù)結(jié)構(gòu)第6章例題與答案10-09

數(shù)據(jù)結(jié)構(gòu)第8章例題與答案10-09

數(shù)據(jù)結(jié)構(gòu)第1章例題與答案10-09

數(shù)據(jù)結(jié)構(gòu)第4章例題與答案10-09

數(shù)據(jù)結(jié)構(gòu)第9章例題與答案10-09