數(shù)據(jù)結構習題與答案圖

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦數(shù)據(jù)結構習題與答案圖第7章圖

一、單選題

01、在一個圖中，全部頂點的度數(shù)之和等于圖的邊數(shù)的倍。A．1/2B．1C．2D．4

02、在一個有向圖中，全部頂點的入度之和等于全部頂點的出度之和的倍。

A．1/2B．1C．2D．4

03、有8個結點的無向圖最多有條邊。

A．14B．28C．56D．112

04、有8個結點的無向連通圖最少有條邊。

A．5B．6C．7D．8

05、有8個結點的有向徹低圖有條邊。

A．14B．28C．56D．112

06、用鄰接表表示圖舉行廣度優(yōu)先遍歷時，通常是采納來實現(xiàn)算法的。

A．棧B．隊列C．樹D．圖

07、用鄰接表表示圖舉行深度優(yōu)先遍歷時，通常是采納來實現(xiàn)算法的。

A．棧B．隊列C．樹D．圖

08、一個含n個頂點和e條弧的有向圖以鄰接矩陣表示法為存儲結構，則計算該有向圖中某個頂點出度的時光復雜度為。A．O(n)B．O(e)C．O(n+e)D．O(n2)

09、已知圖的鄰接矩陣，按照算法思想，則從頂點0動身按深度優(yōu)先遍歷的結點序列是。

A．0243156B．0136542

C．0134256D．0361542

10、已知圖的鄰接矩陣同上題，按照算法，則從頂點0動身，按廣度優(yōu)先遍歷的結點序列是。

A．0243651B．0123456

C．0423156D．0134256

11、已知圖的鄰接表如下所示，按照算法，則從頂點0動身按深度優(yōu)先遍歷的結點序列是。

A．0132B．0231C．0321D．012312、已知圖的鄰接表如下所示，按照算法，則從頂點0動身按廣度優(yōu)先遍歷的結點序列是。

A．0321B．0123C．0132D．031213、圖的深度優(yōu)先遍歷類似于二叉樹的。

A．先序遍歷B．中序遍歷C．后序遍歷D．層次遍歷14、圖的廣度優(yōu)先遍歷類似于二叉樹的。

A．先序遍歷B．中序遍歷C．后序遍歷D．層次遍歷15、任何一個無向連通圖的最小生成樹。

A．惟獨一棵B．一棵或多棵

C．一定有多棵D．可能不存在

()16、對于一個具有n個結點和e條邊的無向圖，若采納鄰接表表示，則頂點表的大小為，全部邊鏈表中邊結點的總數(shù)為。

A．n、2eB．n、eC．n、n+eD．2n、2e

17、推斷有向圖是否存在回路，可以利用算法。

A．關鍵路徑B．最短路徑的DijkstraC．拓撲排序D．廣度優(yōu)先遍歷

18、若用鄰接矩陣表示一個有向圖，則其中每一列包含的“1”的個數(shù)為。

A．圖中每個頂點的入度B．圖中每個頂點的出度

C．圖中弧的條數(shù)D．圖中連通重量的數(shù)目

19、求最短路徑的Dijkstra算法的時光復雜度是___。A．O(n)B．O(n+e)C．O(n2)D．O(n*e)

20、設圖G采納鄰接表存儲，則拓撲排序算法的時光復雜度為。

A．O(n)B．O(n+e)C．O(n2)D．O(n*e)

21、帶權有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中。

A．第i行非∞的元素之和

B．第i列非∞的元素之和

C．第i行非∞且非0的元素個數(shù)

D．第i列非∞且非0的元素個數(shù)

22、一個有n個頂點的無向圖最多有條邊。

A．nB．n(n-1)C．n(n-1)/2D．2n

23、對于一個具有n個頂點的無向圖，若采納鄰接矩陣表示，則該矩陣的大小是。

A．nB．(n-1)2C．n-1D．n2

24、對某個無向圖的鄰接矩陣來說，。

A．第i行上的非零元素個數(shù)和第i列的非零元素個數(shù)一定相等

B．矩陣中的非零元素個數(shù)等于圖中的邊數(shù)

C．第i行上，第i列上非零元素總數(shù)等于頂點vi的度數(shù)D．矩陣中非全零行的行數(shù)等于圖中的頂點數(shù)

25、已知圖的表示如下，若從頂點a動身按深度搜尋法舉行遍歷，則可能得到的一種頂點序列為。

A．abecdfB．acfebdC．aebcfdD．aedfcb26、已知圖的表示如上題，若從頂點a動身按廣度搜尋法舉行遍歷，則可能得到的一種頂點序列為。

A．abcedfB．abcefdC．aebcfdD．acfdeb

27、有向圖的鄰接表存儲結構如下圖所示，則按照有向圖的

深度遍歷算法，從頂點v1動身得到的頂點序列是。

A．v1,v2,v3,v5,v4B．v1,v2,v3,v4,v5C．v1,v3,v4,v5,v2D．v1,v4,v3,v5,v2

28、有向圖的鄰接表存儲結構如上題所示，則按照有向圖的

廣度遍歷算法，從頂點v1動身得到的頂點序列是。

A．v1,v2,v3,v4,v5B．v1,v3,v2,v4,v5

C．v1,v2,v3,v5,v4D．v1,v4,v3,v5,v2

29、一個圖中有n個頂點且包含k個連通重量，若按深度優(yōu)

先搜尋辦法拜訪全部結點，則必需調用次深度優(yōu)先遍歷算法。A．kB．1C．n-kD．n

30、以下不正確的說法是。

A．無向圖中的極大連通子圖稱為連通重量

B．連通圖的廣度優(yōu)先搜尋中普通要采納隊列來暫存剛拜訪過

的頂點

C．圖的深度優(yōu)先搜尋中普通要采納棧來暫存剛拜訪過的頂點D．有向圖的遍歷不行采納廣度優(yōu)先搜尋辦法

二、填空題

01、在有向圖中，以頂點v為盡頭的邊的數(shù)目稱為v的。

02、含n個頂點的無向連通圖中至少含有條邊。

03、圖的存儲結構表示有、、十字鏈表、鄰接多重表等多種存

儲結構。

04、遍歷圖的2種常見辦法是優(yōu)先遍歷和優(yōu)先遍歷。

04、有向圖G用鄰接表矩陣存儲，其第i行的全部元素之和

等于頂點i的。

05、假如n個頂點的圖是一個環(huán)，則它有棵生成樹。

06、n個頂點e條邊的圖，若采納鄰接矩陣存儲，則空間復

雜度為。若采納鄰接表存儲，則空間復雜度為。

07、圖的逆鄰接表存儲結構只適用于圖。

08、已知一個圖的鄰接矩陣表示，刪除全部從第i個頂點出

發(fā)的辦法是。

09、圖采納鄰接矩陣表示，則計算第i個頂點入度的辦法是求。

10、用鄰接矩陣表示圖時，則推斷隨意兩個頂點vi和vj之

間是否有路徑相連，只需要檢查即可。

11、用普里姆(Prim)算法求具有n個頂點e條邊的圖的最小

生成樹的時光復雜度為；用克魯斯卡爾(Kruskal)算法的時光

復雜度是。

12、對稀疏圖最好用算法求最小生成樹，對稠密圖最好用算

法來求解最小生成樹。

13、用Dijkstra算法求某一頂點到其余各頂點間的最短路徑

是按路徑長度的次序來得到最短路徑的。

14、拓撲排序算法是通過重復挑選具有個前驅頂點的過程來

完成的。

15、有向圖G用鄰接矩陣存儲，則第i行的全部元素之和等

于頂點i的。

16、有n個頂點的強連通有向圖G至少有條弧。17、設有向圖G的鄰接矩陣為A，假如圖中不存在弧，則A[i,j]的值為。

18、在n個頂點的無向圖中，若邊數(shù)>n-1，則該圖必是連通圖，此斷言是的。(正確/錯誤)

19、在有n個頂點的有向圖中，每個頂點的度最大可達。

20、若一個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓撲排序序列必然。(存在/不存在)

三、簡答題

01、寫出下面有向圖的全部強連通重量。

02、已知圖的鄰接表如下，畫出圖G的全部連通重量。

03、如下圖，分離用普里姆算法和克魯斯卡爾算法從頂點1開頭求最小生成樹，寫出按次序產生邊的序列。說明：邊用(i,j)方式表示。

04、如下圖，寫出全部的拓撲序列，并求在添加什么邊之后僅可能有惟一的拓撲序列。

05、已知如圖所示的有向圖，請給出該圖的:

(1)每個頂點的入/出度；(2)鄰接矩陣；(3)鄰接表；(4)逆

鄰接表。

06、寫出無向帶樹圖的鄰接矩陣，并按普里姆算法填寫表格中的內容，最后畫出最小生成樹；

VbcDeFghUV-U

Vexlowcosta

4

a

3

A

∞

a

∞

a

∞

a

∞

a

∞

{a}{bcdefgh}

Vex

lowcost

Vex

lowcost

Vex

lowcost

Vex

lowcost

Vex

lowcost

Vex

Lowcost

Vex

lowcost

07、寫出無向帶樹圖的鄰接表，并按克魯斯卡爾算法寫出求最小生成樹產生的邊序列。

08、已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分離畫出自頂點1動身舉行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。

09、利用Dijkstra算法填寫表格求圖中從頂點a到其他各頂點間的最短路徑，并寫出終于結果。

盡頭

Dist

bcDefg

S(盡頭

集)

k=1

k=2

k=3

k=4

k=5

k=6

求利用表格給出求解過程。

11、設圖G=(V，E)，V={1，2，3，4，5，6}，E={，，，，，，}。畫出圖G，并寫出圖G中頂點的全部拓撲序列。

12、已知圖的鄰接表表示的形式說明如下：

#defineMaxNum80

typedefstructnode

{intadjvex;//鄰接點域

structnode*next;//鏈指針域

}EdgeNode;//邊表結點結構描述

typedefstruct

{charvertex;//頂點域

EdgeNode*firstedge;//邊表頭指針

}VertexNode;//頂點表結點結構描述

typedefstruct

{VertexNodeadjlist[MaxNum];//鄰接表

intn,e;

}AlGraph;//鄰接表結構描述

下列算法輸出圖G的深度優(yōu)先生成樹(或森林)的邊，閱讀算法，并在空缺處填入合適的內容，使其成為一個完整的算法。

typedefenum{FALSE,TRUE}Boolean;

Booleanvisited[MaxNum];

voidDFSForest(AlGraph*G)

{for(i=0;in;i++)visited[i]=___;

for(i=0;in;i++)

if(!visited[i])DFSTree(G,i);}

voidDFSTree(AlGraph*G,inti)

{visited[i]=TRUE;

p=G->adjlist[i].firstedge;

while(p!=NULL)

{if(!visited[p->adjves])

{printf(G->adjlist[i].vertex,G->adjlist[p->adjvex].vertex);

___;}

___;}

}

四、算法設計題

01、編寫編歷算法，完成對圖的深度優(yōu)先搜尋和廣度優(yōu)先搜尋。

02、編寫算法，由依次輸入的頂點數(shù)目、弧的數(shù)目、各頂點的信息和各條弧的信息建立有向圖的鄰接表。

03、試在鄰接矩陣存儲結構上實現(xiàn)圖的基本操作：DeleteArc(G,v,w)，即刪除一條邊的操作。

提醒：要刪除全部從第i個頂點動身的邊，即將鄰接矩陣的第i行所有置0。

04、有n個頂點的有向圖的鄰接表定義如下：

#defineMaxNum80

typedefstructArcNode

{intadjvex;//鄰接點域

structArcNode*nextarc;//鏈指針域

}ArcNode;//邊表結點結構描述typedefstructVNode

{VertexTypedata;//頂點域

ArcNode*firstedge;//邊表頭指針

}VNode,AdjList[MaxNum];//頂點向量結點結構描述typedefstruct

{AdjListvertices;//鄰接表

intvexnum,arcnum;

}AlGraph;//鄰接表結構描述

設計算法分離實現(xiàn)以下要求

(1)求出圖G中每個頂點的出度；

(2)求出圖G中出度最大的一個頂點，輸出該頂點號及其信息；

(3)計算圖G中出度為0的頂點數(shù)；

(4)推斷圖G中是否存在弧。

05、試基于圖的深度優(yōu)先搜尋策略寫一算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點vi到頂點vj的路徑(i≠j)。注重：算法中涉及的圖的基本操作必需在此存儲結構上實現(xiàn)。

第7章圖

一、單選題01-10CBBCCBAACB11-20DAADBACACB21-30DCDADBCBAD

二、填空題

01、入度02、n-103、鄰接矩陣、鄰接表

04、深度、廣度04、出度05、n

06、O(n2)、O(n+e)07、有向08、將鄰接矩陣的第i行所有置009、矩陣第i列非0元素之和10、第i行第j列的元素是否為011、O(n2)、O(elog2e)12、克魯斯卡爾(Kruskal)、普里姆(Prim)

13、遞增14、015、出度

16、n17、018、錯誤

19、2(n-1)20、存在

三、簡答題

01、3個，分離是：a,bce,dfg

02、

03、普里姆算法產生邊的序列：(1,3),(3,4),(4,6),(6,5),(5,2)

克魯斯卡爾算法產生邊的序列：(4,6),(1,3),(4,3),(6,5),(2,5)

04、v1,v2,v3,v4

v1,v3,v2,v4

v2,v1,v3,v4

05、(1)每個頂點的入/出度(2)鄰接矩陣

(3)鄰接表(4)逆鄰接表

06、(1)鄰接矩陣為：

VbcdefghUV-U

Vexlowcosta

4

a

3

a

∞

a

∞

a

∞

a

∞

a

∞

{a}{b,c,d,e,f,g,h}

Vexlowcosta

4

0c

5

a

∞

a

∞

a

∞

c

5

{a,c}{b,d,e,f,g,h}

Vexlowcost00c

5

b

9

a

∞

a

∞

c

5

{a,c,b}{d,e,f,g,h}

Vexlowcost000d

7

d

6

d

5

d

4

{a,c,b,d}{e,f,g,h}

Vexlowcost000d

7

d

6

d

5

0{a,c,b,d,h}{e,f,g}

Vexlowcost000d

7

g

2

00{a,c,b,d,h,g}{f,e}

Vexlowcost000f

3

000{a,c,b,d,h,g,f}{e}

Vex

lowcost

0000000{a,c,b,d,h,g,f,e}{}

07、鄰接表為：

fg(2)→ac(3)→fe(3)→ab(4)→dh(4)→bd(5)→dg(5)08、

09、

a→c：2(a,c)

a→f：6(a,c,f)

a→e：10(a,c,e)

a→d：11(a,c,f,d)

a→g：14(a,c,f,d,g)

a→b：15(a,b)

10、和上題類似，求解過程略。

11、

1，2，3，6，5，4

1，3，2，6，5，4

1，3，6，2，5，4

12、

FALSE//初始化為未拜訪

DSFTree(G,p->adjvex)//從相鄰結點往下繼續(xù)深度搜尋

p=p->next//下一個未拜訪的相鄰結點

四、算法設計題

01、編寫編歷算法，完成對圖的深度優(yōu)先搜尋和廣度優(yōu)先搜尋。

深度優(yōu)先搜尋：課本P169算法7.4和算法7.5

廣度優(yōu)先搜尋：課本P170算法7.6

02、編寫算法，由依次輸入的頂點數(shù)目、弧的數(shù)目、各頂點的信息和各條弧的信息建立有向圖的鄰接表。

解：StatusBuild_AdjList(ALGraph

scanf("%d",

if(vnextarc;q=q->nextarc);

q->nextarc=p;

}

p->adjvex=j;p->nextarc=NULL;

}//while

returnOK;

}//Build_AdjList

03、試在鄰接矩陣存儲結構上實現(xiàn)圖的基本操作：DeleteArc(G,v,w)，即刪除一條邊的操作。(假如要刪除全部從第i個頂點動身的邊呢？提醒：將鄰接矩陣的第i行所有置0)

解：//本題中的圖G均為有向無權圖。

StatusDelete_Arc(MGraph

if((j=LocateVex(G,w))。

05、試基于圖的深度優(yōu)先搜尋策略寫一算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點vi到頂點vj的路徑(i≠j)。注