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

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

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

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

5、別為 n和 n-1。對于一個具有n個頂點e條邊的無向圖的鄰接表的表示，鄰接表的邊結點個數為2e已知一無向圖 G= (V, E),其中 V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現用某一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abecd,則采用的_深度 遍歷方法。當一個AOV網用鄰接表表示時，可按下列方法進行拓撲排序。.杳鄰接表中入度為0的頂點，并進棧:.若棧不空，則輸出棧頂元素,并退棧；查Vj的直接后繼Vk,對Vk入度處理，處理方法是Vk入度減1:.若?？諘r，輸出頂點數小于圖的頂點數，說明有 環，否則拓撲排序完成。1、已知一個無向圖如下圖所示，試求：寫出圖的鄰接矩陣利用Dijkstra算法求頂點V1到其他頂點間的最短