數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)data答案

數(shù)據(jù)結(jié)構(gòu)與算法

課堂練習(xí)(3)

(答案)

11.一個(gè)n個(gè)頂點(diǎn)的連通圖，它的生成樹有

條邊。A．nB．n-1 C．n+1D．2*n2.Dijkstra算法是用來求

。A．從一個(gè)頂點(diǎn)到其余頂點(diǎn)的最短路徑 B．每對頂點(diǎn)之間的最短路徑C．拓?fù)湫蛄蠨．最小生成樹3.拓?fù)渑判蚰軌蜻M(jìn)行的前提條件（即能輸出一個(gè)拓?fù)湫蛄校┦窃揂OV網(wǎng)

。A.頂點(diǎn)數(shù)多于邊數(shù)B.邊數(shù)多于頂點(diǎn)數(shù)

C.

不存在回路D.有回路4.拓?fù)渑判蚰軌蜻M(jìn)行的前提條件（即能輸出一個(gè)拓?fù)湫蛄校┦窃揂OV網(wǎng)

。

A.

不存在回路B.有回路C.頂點(diǎn)數(shù)多于邊數(shù)D.邊數(shù)多于頂點(diǎn)數(shù)選擇題25.最小生成樹是指連通網(wǎng)（設(shè)每條邊上的權(quán)值均大于0）的各生成樹中

的生成樹。

A.邊數(shù)最少B.

生成樹的權(quán)最小C.不存在回路D.路徑最短6.當(dāng)AOV網(wǎng)滿足條件

時(shí)，它代表的工程才是可行的。A.是無向無環(huán)圖

B.是無向帶環(huán)圖

C.

是有向無環(huán)圖

D.是有向帶環(huán)圖7.求從一個(gè)頂點(diǎn)到其余頂點(diǎn)的最短路徑需用

。A.Prim算法

B.Floyd算法

C.Dijkstra算法D.Kruskal算法8.判斷一個(gè)有向圖是否存在回路，除了可以利用深度優(yōu)先遍歷算法外，還可以用

。A.求最短路徑的算法

B.

拓?fù)渑判蛩惴?/p>

C.求最小生成樹的算法

D.廣度優(yōu)先遍歷算法31.已知一個(gè)有向圖的鄰接矩陣存儲結(jié)構(gòu)如圖，畫出該圖形，并寫出從頂點(diǎn)V1出發(fā)的深度優(yōu)先和廣度優(yōu)先的頂點(diǎn)序列。解：圖形：

深度優(yōu)先的頂點(diǎn)序列為：

V1,V3,V5,V2,V4

廣度優(yōu)先的頂點(diǎn)序列為：

V1,V2,V3,V4,V5

0101000000110000000001110解答題V4V5V1V2V3V4V5V1V2V3V4V5V1V2V3111242.無向帶權(quán)圖G如下:

①從結(jié)點(diǎn)A出發(fā)，畫出根據(jù)普里姆算法產(chǎn)生圖G的最小生成樹的過程（即需要寫出得到各條邊的次序）。AFEGDBC1058119276146103解答題AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC5821435

②從結(jié)點(diǎn)A出發(fā)，畫出根據(jù)克魯斯卡爾算法產(chǎn)生圖G的最小生成樹的過程（即需要寫出得到各條邊的次序）。AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC1058119276146103AFEGDBC5821436解：圖結(jié)點(diǎn)按鄰接矩陣下標(biāo)由小到大排列

v0,v1,v2,v3,v4,v5,v6,v7,v9,v83．在下面有向網(wǎng)中，求出頂點(diǎn)V0點(diǎn)到其它頂點(diǎn)的最短路徑（寫出經(jīng)過的頂點(diǎn)和長度）。12V3V0V1V2V4830532541020解：V0->V13V0->V1->V311V0->V1->V3->V215V0->V1->V3->V423解答題4.一個(gè)AOV網(wǎng)的二元組表示為：V={0,1,2,3,4,5,6,7,8,9}E={<1,2>,<1,3>,<0,3>,<0,4>,<2,3>,<2,5>,<3,5>,<3,6>,<4,6>,<3,9>,<5,7>,<5,9>,<6,9>,<7,8>,<9,8>}①畫出該AOV網(wǎng)的示意圖。②若該AOV網(wǎng)采用鄰接矩陣存儲結(jié)構(gòu)，寫出按拓?fù)渑判蛩惴ǖ玫降耐負(fù)湫蛄?。V0V1V2V3V4V5V6V7V8V975.一個(gè)AOV網(wǎng)的二元組表示為：V={0,1,2,3,4,5,6,7,8}E={<0,1>,<0,3>,<0,4>,<1,2>,<1,3>,<2,3>,<2,5>,<3,5>,<3,6>,<3,8>,<4,6>,<5,7>,<5,8>,<6,8>,<8,7>}①畫出該AOV網(wǎng)的鄰接矩陣存儲結(jié)構(gòu)。②寫出按鄰接矩陣存儲結(jié)構(gòu)存儲時(shí)由拓?fù)渑判蛩惴ǖ玫降耐負(fù)湫蛄?。解?00000000001000011001101000000000000000000000011000000100000000000001001010001100432105678432105678000000000001000011001101000000000000000000000011000000100000000000001001010001100432105678432105678全0，無入度，輸出v0把1全改為0V0,V1,V2,V3,V4,V5,V6,V8,V7解答題86.一個(gè)AOV網(wǎng)的二元組表示為：V={0,1,2,3,4,5,6,7,8,9}E={<0,2>,<0,3>,<1,3>,<1,4>,<2,3>,<2,5>,<3,5>,<3,6>,<4,6>,<3,8>,<5,7>,<5,8>,<6,8>,<7,9>,<8,9>}①畫出該AOV網(wǎng)的示意圖。②若該AOV網(wǎng)采用鄰接表存儲結(jié)構(gòu)，且邊結(jié)點(diǎn)按鄰接點(diǎn)序號由大到小排序，寫出按拓?fù)渑判蛩惴ǖ玫降耐負(fù)湫蛄?。V0V1V2V3V4V5V6V7V8V9解答題V1,V4,V0,V2,V3,V6,V5,V8,V7,V997.下圖為一無向連通網(wǎng)絡(luò)，試按鄰接矩陣存儲結(jié)構(gòu)畫出從頂點(diǎn)1出發(fā)的深度優(yōu)先生成樹、廣度優(yōu)先生成樹、(普里姆算法\克魯斯卡爾)最小生成樹。解答題a.深度