數(shù)據(jù)結(jié)構(gòu)-圖(練習(xí)1)

圖練習(xí)11設(shè)有8個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有（）條邊能確保是一個(gè)連通圖。

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

C2對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1,、出度為k2，則對(duì)應(yīng)鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為（）。

A．k1B．k2C．k1-k2D．k1+k2

B3對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1,、出度為k2，則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為（）。

A．k1B．k2C．k1-k2D．k1+k2

A4對(duì)于一個(gè)無(wú)向圖，若一個(gè)頂點(diǎn)的度為k，則對(duì)應(yīng)鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為（）。k5一個(gè)有n個(gè)頂點(diǎn)的無(wú)向連通圖，它所包含的連通分量個(gè)數(shù)為（）。

A．0B．1C．nD．n+1

B6已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的出度的方法是（）。

A．求矩陣第i列非零元素之和

B．求矩陣第i行非零元素之和

B7已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是（）。

A．求矩陣第i列非零元素之和

B．求矩陣第i行非零元素之和A8在無(wú)向圖G的鄰接矩陣A中，若A[i][j]等于1，則A[j][i]等于（）。

A．0B．1C．n

B9n個(gè)頂點(diǎn)的連通圖至少（）條邊

A．1B．n-1C．nD．n+1

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

A．nB．(n-1)*(n-1)C．n-1D．n*n

D11一個(gè)有n個(gè)頂點(diǎn)的有向完全圖有（）條邊。

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

B12具有4個(gè)頂點(diǎn)的無(wú)向完全圖有（）條邊。

A．6B．12C．16D．20

A13在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。

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

B14在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。

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

C15在一個(gè)無(wú)向圖中，若兩頂點(diǎn)之間的路徑長(zhǎng)度為k，則該路徑上的頂點(diǎn)數(shù)為()。A.k B.k+1 C.k+2 D.2kB16對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向連通圖，它包含的連通分量的個(gè)數(shù)為()。A.0 B.1 C.n D.n+1

B17在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，表示邊存在的元素（又稱為有效元素）的個(gè)數(shù)為()。A.n B.n

e

C.e D.2

eD18在一個(gè)具有n個(gè)頂點(diǎn)和e條