數(shù)據結構第7章例題與答案
第七章 圖一、選擇題
1．圖中有關路徑的定義是（ ）�！颈狈浇煌ù髮W 2001 一、24 （2分）】
a．由頂點和相鄰頂點序偶構成的邊所形成的序列 b．由不同頂點所形成的序列
c．由不同邊所形成的序列 d．上述定義都不是
2．設無向圖的頂點個數(shù)為n，則該圖最多有（ ）條邊。
a．n-1 b．n(n-1)/2 c． n(n+1)/2 d．0 e．n2
【清華大學 1998 一、5 （2分）】【西安電子科技大 1998 一、6 （2分）】
【北京航空航天大學 1999 一、7 （2分）】
3．一個n個頂點的連通無向圖，其邊的.個數(shù)至少為（ ）。【浙江大學 1999 四、4 (4分)】
a．n-1 b．n c．n+1 d．nlogn；
4．要連通具有n個頂點的有向圖，至少需要（ ）條邊。【北京航空航天大學 2000 一、6(2分）】
a．n-l b．n c．n+l d．2n
5．n個結點的完全有向圖含有邊的數(shù)目（ �。�。【中山大學 1998 二、9 （2分）】
a．n*n ｂ．n（n＋１） c．n／2 d．n*（n－l）
6．一個有n個結點的圖，最少有（ ）個連通分量，最多有（ ）個連通分量。
a．0 b．1 c．n-1 d．n
【北京郵電大學 2000 二、5 （20/8分）】
7．在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)（ ）倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（ ）倍�！竟枮I工業(yè)大學 2001 二、3 （2分）】
a．1/2 b．2 c．1 d．4
8．用有向無環(huán)圖描述表達式(a+b)*（（a+b）/a），至少需要頂點的數(shù)目為( )�！局猩酱髮W1999一、14】
a．5 b．6 c．8 d．9
9．用dfs遍歷一個無環(huán)有向圖，并在dfs算法退棧返回時打印相應的頂點，則輸出的頂點序列是( )。
a．逆拓撲有序 b．拓撲有序 c．無序的 【中科院軟件所 1998】
10．下面結構中最適于表示稀疏無向圖的是（ ），適于表示稀疏有向圖的是（ ）。
a．鄰接矩陣 b．逆鄰接表 c．鄰接多重表 d．十字鏈表 e．鄰接表
【北京工業(yè)大學 2001 一、3 (2分)】
11．下列哪一種圖的鄰接矩陣是對稱矩陣？（ ）【北方交通大學 2001 一、11 （2分）】
a．有向圖 b．無向圖 c．aov網 d．aoe網
12． 從鄰接陣矩 可以看出，該圖共有（①）個頂點；如果是有向圖該圖共有（②） 條��；如果是無向圖，則共有（③）條邊�！局锌圃很浖� 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．當一個有n個頂點的圖用鄰接矩陣a表示時，頂點vi的度是（ ）�！灸暇├砉ご髮W1998一、4(2分）】
14．用相鄰矩陣a表示圖，判定任意兩個頂點vi和vj之間是否有長度為m 的路徑相連，則只要檢查（ ）的第i行第j列的元素是否為零即可�！疚錆h大學 2000 二、7】
a．ma b．a c．am d．am-1
15. 下列說法不正確的是（ ）�！厩鄭u大學 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)先遍歷，得到的頂點序列正確的是（ ）。【南京理工大學 2001 一、14 （1.5分）】
a．a,b,e,c,d,f b．a,c,f,e,b,d c．a,e,b,c,f,d d．a,e,d,f,c,b
17. 設圖如右所示，在下面的5個序列中，符合深度優(yōu)先遍歷的序列有多少？（ ）
【南京理工大學 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.fuchuonang.cn/
【數(shù)據結構第7章例題與答案】相關文章：
數(shù)據結構第2章例題與答案10-09
數(shù)據結構第5章例題與答案10-09
數(shù)據結構第11章例題與答案10-09
數(shù)據結構第3章例題與答案10-09
數(shù)據結構第6章例題與答案10-09
數(shù)據結構第8章例題與答案10-09
數(shù)據結構第1章例題與答案10-09
數(shù)據結構第4章例題與答案10-09
數(shù)據結構第9章例題與答案10-09