數(shù)據(jù)結(jié)構(gòu)習(xí)題與答案圖

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

一、單選題

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

02、在一個(gè)有向圖中，全部頂點(diǎn)的入度之和等于全部頂點(diǎn)的出度之和的倍。

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

03、有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有條邊。

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

04、有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有條邊。

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

05、有8個(gè)結(jié)點(diǎn)的有向徹低圖有條邊。

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

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

A．棧B．隊(duì)列C．樹(shù)D．圖

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

A．棧B．隊(duì)列C．樹(shù)D．圖

08、一個(gè)含n個(gè)頂點(diǎn)和e條弧的有向圖以鄰接矩陣表示法為存儲(chǔ)結(jié)構(gòu)，則計(jì)算該有向圖中某個(gè)頂點(diǎn)出度的時(shí)光復(fù)雜度為。A．O(n)B．O(e)C．O(n+e)D．O(n2)

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

A．0243156B．0136542

C．0134256D．0361542

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

A．0243651B．0123456

C．0423156D．0134256

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

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

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

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

A．先序遍歷B．中序遍歷C．后序遍歷D．層次遍歷15、任何一個(gè)無(wú)向連通圖的最小生成樹(shù)。

A．惟獨(dú)一棵B．一棵或多棵

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

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

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

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

A．關(guān)鍵路徑B．最短路徑的DijkstraC．拓?fù)渑判駾．廣度優(yōu)先遍歷

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

A．圖中每個(gè)頂點(diǎn)的入度B．圖中每個(gè)頂點(diǎn)的出度

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

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

20、設(shè)圖G采納鄰接表存儲(chǔ)，則拓?fù)渑判蛩惴ǖ臅r(shí)光復(fù)雜度為。

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

21、帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中。

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

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

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

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

22、一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有條邊。

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

23、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采納鄰接矩陣表示，則該矩陣的大小是。

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

24、對(duì)某個(gè)無(wú)向圖的鄰接矩陣來(lái)說(shuō)，。

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

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

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

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

A．a(chǎn)becdfB．a(chǎn)cfebdC．a(chǎn)ebcfdD．a(chǎn)edfcb26、已知圖的表示如上題，若從頂點(diǎn)a動(dòng)身按廣度搜尋法舉行遍歷，則可能得到的一種頂點(diǎn)序列為。

A．a(chǎn)bcedfB．a(chǎn)bcefdC．a(chǎn)ebcfdD．a(chǎn)cfdeb

27、有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示，則按照有向圖的

深度遍歷算法，從頂點(diǎn)v1動(dòng)身得到的頂點(diǎn)序列是。

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

28、有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如上題所示，則按照有向圖的

廣度遍歷算法，從頂點(diǎn)v1動(dòng)身得到的頂點(diǎn)序列是。

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

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

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

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

30、以下不正確的說(shuō)法是。

A．無(wú)向圖中的極大連通子圖稱(chēng)為連通重量

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

的頂點(diǎn)

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

二、填空題

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

02、含n個(gè)頂點(diǎn)的無(wú)向連通圖中至少含有條邊。

03、圖的存儲(chǔ)結(jié)構(gòu)表示有、、十字鏈表、鄰接多重表等多種存

儲(chǔ)結(jié)構(gòu)。

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

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

等于頂點(diǎn)i的。

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

06、n個(gè)頂點(diǎn)e條邊的圖，若采納鄰接矩陣存儲(chǔ)，則空間復(fù)

雜度為。若采納鄰接表存儲(chǔ)，則空間復(fù)雜度為。

07、圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于圖。

08、已知一個(gè)圖的鄰接矩陣表示，刪除全部從第i個(gè)頂點(diǎn)出

發(fā)的辦法是。

09、圖采納鄰接矩陣表示，則計(jì)算第i個(gè)頂點(diǎn)入度的辦法是求。

10、用鄰接矩陣表示圖時(shí)，則推斷隨意兩個(gè)頂點(diǎn)vi和vj之

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

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

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

復(fù)雜度是。

12、對(duì)稀疏圖最好用算法求最小生成樹(shù)，對(duì)稠密圖最好用算

法來(lái)求解最小生成樹(shù)。

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

是按路徑長(zhǎng)度的次序來(lái)得到最短路徑的。

14、拓?fù)渑判蛩惴ㄊ峭ㄟ^(guò)重復(fù)挑選具有個(gè)前驅(qū)頂點(diǎn)的過(guò)程來(lái)

完成的。

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

于頂點(diǎn)i的。

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

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

19、在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)。

20、若一個(gè)有向圖的鄰接矩陣中對(duì)角線以下元素均為零，則該圖的拓?fù)渑判蛐蛄斜厝弧?存在/不存在)

三、簡(jiǎn)答題

01、寫(xiě)出下面有向圖的全部強(qiáng)連通重量。

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

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

04、如下圖，寫(xiě)出全部的拓?fù)湫蛄?，并求在添加什么邊之后僅可能有惟一的拓?fù)湫蛄小?/p>

05、已知如圖所示的有向圖，請(qǐng)給出該圖的:

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

鄰接表。

06、寫(xiě)出無(wú)向帶樹(shù)圖的鄰接矩陣，并按普里姆算法填寫(xiě)表格中的內(nèi)容，最后畫(huà)出最小生成樹(shù)；

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、寫(xiě)出無(wú)向帶樹(shù)圖的鄰接表，并按克魯斯卡爾算法寫(xiě)出求最小生成樹(shù)產(chǎn)生的邊序列。

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

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

盡頭

Dist

bcDefg

S(盡頭

集)

k=1

k=2

k=3

k=4

k=5

k=6

求利用表格給出求解過(guò)程。

11、設(shè)圖G=(V，E)，V={1，2，3，4，5，6}，E={，，，，，，}。畫(huà)出圖G，并寫(xiě)出圖G中頂點(diǎn)的全部拓?fù)湫蛄小?/p>

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

#defineMaxNum80

typedefstructnode

{intadjvex;//鄰接點(diǎn)域

structnode*next;//鏈指針域

}EdgeNode;//邊表結(jié)點(diǎn)結(jié)構(gòu)描述

typedefstruct

{charvertex;//頂點(diǎn)域

EdgeNode*firstedge;//邊表頭指針

}VertexNode;//頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)描述

typedefstruct

{VertexNodeadjlist[MaxNum];//鄰接表

intn,e;

}AlGraph;//鄰接表結(jié)構(gòu)描述

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

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);

___;}

___;}

}

四、算法設(shè)計(jì)題

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

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

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

提醒：要?jiǎng)h除全部從第i個(gè)頂點(diǎn)動(dòng)身的邊，即將鄰接矩陣的第i行所有置0。

04、有n個(gè)頂點(diǎn)的有向圖的鄰接表定義如下：

#defineMaxNum80

typedefstructArcNode

{intadjvex;//鄰接點(diǎn)域

structArcNode*nextarc;//鏈指針域

}ArcNode;//邊表結(jié)點(diǎn)結(jié)構(gòu)描述typedefstructVNode

{VertexTypedata;//頂點(diǎn)域

ArcNode*firstedge;//邊表頭指針

}VNode,AdjList[MaxNum];//頂點(diǎn)向量結(jié)點(diǎn)結(jié)構(gòu)描述typedefstruct

{AdjListvertices;//鄰接表

intvexnum,arcnum;

}AlGraph;//鄰接表結(jié)構(gòu)描述

設(shè)計(jì)算法分離實(shí)現(xiàn)以下要求

(1)求出圖G中每個(gè)頂點(diǎn)的出度；

(2)求出圖G中出度最大的一個(gè)頂點(diǎn)，輸出該頂點(diǎn)號(hào)及其信息；

(3)計(jì)算圖G中出度為0的頂點(diǎn)數(shù)；

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

05、試基于圖的深度優(yōu)先搜尋策略寫(xiě)一算法，判別以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)vi到頂點(diǎn)vj的路徑(i≠j)。注重：算法中涉及的圖的基本操作必需在此存儲(chǔ)結(jié)構(gòu)上實(shí)現(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、錯(cuò)誤

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

三、簡(jiǎn)答題

01、3個(gè)，分離是：a,bce,dfg

02、

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

克魯斯卡爾算法產(chǎn)生邊的序列：(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)每個(gè)頂點(diǎn)的入/出度(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、和上題類(lèi)似，求解過(guò)程略。

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)//從相鄰結(jié)點(diǎn)往下繼續(xù)深度搜尋

p=p->next//下一個(gè)未拜訪的相鄰結(jié)點(diǎn)

四、算法設(shè)計(jì)題

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

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

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

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

解：StatusBuild_AdjList(ALGraph

scanf("%d",

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

q->nextarc=p;

}

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

}//while

returnOK;

}//Build_AdjList

03、試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：DeleteArc(G,v,w)，即刪除一條邊的操作。(假如要?jiǎng)h除全部從第i個(gè)頂點(diǎn)動(dòng)身的邊呢？提醒：將鄰接矩陣的第i行所有置0)

解：//本題中的圖G均為有向無(wú)權(quán)圖。

StatusDelete_Arc(MGraph

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

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