數(shù)據(jù)結(jié)構(gòu)第7章例題與答案
第七章 圖一、選擇題
1．圖中有關(guān)路徑的定義是（ ）�！颈狈浇煌ù髮W(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 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)的有向圖，至少需要（ ）條邊。【北京航空航天大學(xué) 2000 一、6(2分）】
a．n-l b．n c．n+l d．2n
5．n個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目（ �。��！局猩酱髮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è)連通分量。
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 （2分）】
a．1/2 b．2 c．1 d．4
8．用有向無環(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)，則輸出的頂點(diǎn)序列是( )。
a．逆拓?fù)溆行? b．拓?fù)溆行? c．無序的 【中科院軟件所 1998】
10．下面結(jié)構(gòu)中最適于表示稀疏無向圖的是（ ），適于表示稀疏有向圖的是（ ）。
a．鄰接矩陣 b．逆鄰接表 c．鄰接多重表 d．十字鏈表 e．鄰接表
【北京工業(yè)大學(xué) 2001 一、3 (2分)】
11．下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？（ ）【北方交通大學(xué) 2001 一、11 （2分）】
a．有向圖 b．無向圖 c．a(chǎn)ov網(wǎng) d．a(chǎn)oe網(wǎng)
12． 從鄰接陣矩 可以看出，該圖共有（①）個(gè)頂點(diǎn)；如果是有向圖該圖共有（②） 條弧；如果是無向圖，則共有（③）條邊。【中科院軟件所 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)一個(gè)有n個(gè)頂點(diǎn)的圖用鄰接矩陣a表示時(shí)，頂點(diǎn)vi的度是（ ）�！灸暇├砉ご髮W(xué)1998一、4(2分）】
14．用相鄰矩陣a表示圖，判定任意兩個(gè)頂點(diǎn)vi和vj之間是否有長(zhǎng)度為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．圖的遍歷是從給定的源點(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é) 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個(gè)序列中，符合深度優(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個(gè) b．4個(gè) c．3個(gè) d．2個(gè)
http://m.dgxbdz.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