數(shù)據(jù)結(jié)構(gòu)試題和答案第7章ans

1、下面關(guān)于圖的存儲(chǔ)的敘述中正確的是()。用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中邊數(shù)和結(jié)點(diǎn)個(gè)數(shù)都有關(guān)用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有關(guān)用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)答案：C對(duì)于具有e條邊的無向圖，它的鄰接表中有()個(gè)邊結(jié)點(diǎn)。A:e-1B:eC:2(e-1)D:2e答案：D，(vi,vj)以vi作為頭結(jié)點(diǎn)保存一次，以vj作為頭結(jié)點(diǎn)保存一次。圖的深度優(yōu)先搜索類似于樹的(A )次序遍歷。A:先序B:中序C:后序D:層次設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有()條

2、邊。A: n-1B: n(n-1)/2C: n(n+1)/2D: n(n-1)答案：最多邊時(shí)：完全圖。選B完全有向圖:n(n-1)對(duì)于有向圖，其鄰接矩陣表示比鄰接表表示更易于()。A:求一個(gè)頂點(diǎn)的度 B:求一個(gè)頂點(diǎn)的鄰接點(diǎn)C:進(jìn)行圖的深度優(yōu)先遍歷D:進(jìn)行圖的廣度優(yōu)先遍歷答案：B與鄰接矩陣相比，鄰接表更適合于存儲(chǔ)()。A:無向圖B連通圖C稀疏圖D稠密圖答案：C若用鄰接矩陣表示一個(gè)有向圖，則其中每一列包含的 1的個(gè)數(shù)為()A.圖中每個(gè)頂點(diǎn)的入度 B.圖中每個(gè)頂點(diǎn)的出度C.圖中弧的條數(shù)D.圖中連通分量的數(shù)目答案：A設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有()條邊。A. n-1B. n(n-1)/2 C.

3、 n(n+1)/2 D. 0E. n2 TOC o 1-5 h z 一個(gè)n個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為()。A. n-1B. nC. n+1D. nlogn；答案：極小連通圖，An個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目()。A. n*nB. n (n+1) C. n/2D. n* (nl)在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)(B)倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的(C )倍。A. 1/2B. 2C. 1D. 4在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹的Prim算法的時(shí)間復(fù)雜度為()。A. O(n)B. O(n+e)C. O(n2)D. O(n3)答案：C對(duì)于一個(gè)具

4、有n個(gè)頂點(diǎn)和e條邊的無向圖，當(dāng)分別采用鄰接矩陣和鄰接表表示時(shí)，求任 一頂點(diǎn)度數(shù)的時(shí)間復(fù)雜度分別為_O (n) 和O(e/n)。圖的優(yōu)先搜索遍歷算法是一種遞歸算法，圖的優(yōu)先搜索遍歷算法需要使用隊(duì)列。假定一個(gè)有向圖的頂點(diǎn)集為a,b,c,d,e,f，邊集為, , , , , ，則出度為0的頂點(diǎn)個(gè)數(shù)為，入度為1的頂點(diǎn)個(gè)數(shù)為。對(duì)于下圖，從頂點(diǎn) A 開始的深度優(yōu)先遍歷序列為ABCFEGHID。一個(gè)有n個(gè)結(jié)點(diǎn)的圖，至少有 1 個(gè)連通分量。設(shè)G(V,E)和G(V，E)是連通圖，如果V=V，E是保證G連通性的E的最小子集，那么G，被稱為G 生成樹。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù)分

5、別為 n和 n-1。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的無向圖的鄰接表的表示，鄰接表的邊結(jié)點(diǎn)個(gè)數(shù)為2e已知一無向圖 G= (V, E),其中 V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a開始遍歷圖，得到的序列為abecd,則采用的_深度 遍歷方法。當(dāng)一個(gè)AOV網(wǎng)用鄰接表表示時(shí)，可按下列方法進(jìn)行拓?fù)渑判颉?杳鄰接表中入度為0的頂點(diǎn)，并進(jìn)棧:.若棧不空，則輸出棧頂元素,并退棧；查Vj的直接后繼Vk,對(duì)Vk入度處理，處理方法是Vk入度減1:.若?？諘r(shí)，輸出頂點(diǎn)數(shù)小于圖的頂點(diǎn)數(shù)，說明有 環(huán)，否則拓?fù)渑判蛲瓿伞?、已知一個(gè)無向圖如下圖所示，試求：寫出圖的鄰接矩陣?yán)肈ijkstra算法求頂點(diǎn)V1到其他頂點(diǎn)間的最短