9. 下列說法不正確的是（ ）。
a．圖的遍歷是從給定的源點出發每乙個頂點僅被訪問一次
b．遍歷的基本演算法有兩種：深度遍歷和廣度遍歷
c．圖的深度遍歷不適用於有向圖
d．圖的深度遍歷是乙個遞迴過程
10．下面哪一方法可以判斷出乙個有向圖是否有環（迴路）：
a．深度優先遍歷 b. 拓撲排序 c. 求最短路徑 d. 求關鍵路徑
11. 在圖採用鄰接表儲存時，求最小生成樹的 prim 演算法的時間複雜度為( )。
a. o(nb. o(n+e) c. o(n2) d. o(n3)
12．已知有向圖g=(v,e)，其中v=，
e=,g的拓撲序列是（ ）。
a．v1,v3,v4,v6,v2,v5,v7b．v1,v3,v2,v6,v4,v5,v7
c．v1,v3,v4,v5,v2,v6,v7d．v1,v2,v5,v3,v4,v6,v7
13. 在有向圖g的拓撲序列中，若頂點vi在頂點vj之前，則下列情形不可能出現的是（ ）。
a．g中有弧b．g中有一條從vi到vj的路徑
c．g中沒有弧d．g中有一條從vj到vi的路徑
14. 關鍵路徑是事件結點網路中（ ）。
a．從源點到匯點的最長路徑 b．從源點到匯點的最短路徑
c．最長迴路d．最短迴路
15．下列關於aoe網的敘述中，不正確的是（ ）。
a．關鍵活動不按期完成就會影響整個工程的完成時間
b．任何乙個關鍵活動提前完成，那麼整個工程將會提前完成
c．所有的關鍵活動提前完成，那麼整個工程將會提前完成
d．某些關鍵活動提前完成，那麼整個工程將會提前完成
二、填空題
1．具有10個頂點的無向圖，邊的總數最多為______。
2. 設無向圖 g 有n 個頂點和e 條邊，每個頂點vi 的度為di（1<=i<=n），則e=______
3. 在有n個頂點的有向圖中，若要使任意兩點間可以互相到達，則至少需要______條弧。
4．下圖中的強連通分量的個數為______個。
5．n個頂點的連通圖用鄰接矩陣表示時,該矩陣至少有_______個非零元素。
6. 在有向圖的鄰接矩陣表示中，計算第i個頂點入度的方法是
7. 對於乙個具有n個頂點e條邊的無向圖的鄰接表的表示，則表頭向量大小為______，鄰接表的邊結點個數為______。
8. 已知一無向圖g=（v，e），其中v= e=現用某一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abecd，則採用的是______遍歷方法。
9．構造連通網最小生成樹的兩個典型演算法是
10. 有向圖g可拓撲排序的判別條件是
11. dijkstra最短路徑演算法從源點到其餘各頂點的最短路徑的路徑長度按次序依次產生，該演算法弧上的權出現情況時，不能正確產生最短路徑。
12.有向圖g=(v,e),其中 v(g)=，用三元組表示弧及弧上的權為，則從源點0到頂點3的最短路徑長度是______，經過的中間頂點是
13．aov網中,結點表示______,邊表示______。aoe網中,結點表示______,邊表示______。
14．在aoe網中，從源點到匯點路徑上各活動時間總和最長的路徑稱為
15．在 aov網中，存在環意味著這是的；對程式的資料流圖來說，它表明存在
16．如下為拓撲排序的c程式，
（1）．列出對右圖執行該程式後的輸出結果。
（2）．在程式空白處填上適當語句。
void topsort(hdnodes graph ,int n)
for (i=0; i if(1fprintf(stderr, "\ngraph has a cycle \n"); exit(1); }
else } }
}三、應用題
1．已知如圖所示的有向圖，請給出該圖的：
（1） 每個頂點的入度、出度；
（2） 鄰接矩陣；
（3） 鄰接表；
（4） 逆鄰接表；
（5） 強連通分量。
2．已知圖的鄰接矩陣為：
當用鄰接表作為圖的儲存結構，且鄰接表都按序號從大到小排序時，試寫出：
（1）．以頂點v1為出發點的唯一的深度優先遍歷；
（2）．以頂點v1為出發點的唯一的廣度優先遍歷；
（3）．該圖唯一的拓撲有序序列。
3．已知乙個無向圖如下圖所示，要求分別用prim和kruskal演算法生成最小樹（假設以①為起點，試畫出構造過程）。
4．已知世界六大城市為:北京(pe)、紐約(n)、巴黎(pa)、 倫敦(l) 、 東京(t) 、 墨西哥(m),下表給定了這六大城市之間的交通里程:
世界六大城市交通里程表(單位:百公里)
（1）．畫出這六大城市的交通網路圖;
（2）．畫出該圖的鄰接表表示法;
（3）．畫出該圖按權值遞增的順序來構造的最小(代價)生成樹.
5．下表給出了某工程各工序之間的優先關係和各工序所需時間
（1）．畫出相應的aoe網
（2）．列出各事件的最早發生時間,最遲發生時間
（3）．找出關鍵路徑並指明完成該工程所需最短時間.
四、演算法設計題
1．已知有向圖有n個頂點,請寫演算法,根據使用者輸入的偶對建立該有向圖的鄰接表。即接受使用者輸入的(以其中之一為0標誌結束),對於每條這樣的邊,申請乙個結點,並插入到的單鏈表中,如此反覆,直到將圖中所有邊處理完畢。提示：
先產生鄰接表的n個頭結點（其結點數值域從1到n）。
2．設已給出圖的鄰接矩陣，要求將鄰接矩陣轉換為鄰接表。
3．已知無向圖採用鄰接表儲存方式，試寫出刪除邊（i，j）的演算法。
4．假設以鄰接矩陣作為圖的儲存結構，編寫演算法判別在給定的有向圖中是否存在乙個簡單有向迴路，若存在，則以頂點序列的方式輸出該迴路（找到一條即可）。（注：圖中不存在頂點到自己的弧）
5．給定n個村莊之間的交通圖，若村莊i和j之間有道路，則將頂點i和j用邊連線，邊上的wij表示這條道路的長度，現在要從這n個村莊中選擇乙個村莊建一所醫院，問這所醫院應建在哪個村莊，才能使離醫院最遠的村莊到醫院的路程最短?試設計乙個解答上述問題的演算法，並應用該演算法解答如圖所示的例項。
6．對於乙個使用鄰接表儲存的有向圖g，可以利用深度優先遍歷方法，對該圖中結點進行拓撲排序。其基本思想是：在遍歷過程中，每訪問乙個頂點，就將其鄰接到的頂點的入度減一，並對其未訪問的、入度為0的鄰接到的頂點進行遞迴。
（1）．給出完成上述功能的圖的鄰接表定義（結構）。
（2）．定義在演算法中使用的全域性輔助陣列。
（3）．寫出在遍歷圖的同時進行拓撲排序的演算法。
第七章圖
一、單項選擇題
3．b4．a
5．b6．b
7．b c
8．b9．c
10．b
11. b
12．a
13. d
14. a
15．b
二、填空題
1．45
2. 略
3. n
4．35．2（n-1）
6. 第i列非零元素個數
7. n 2e
8. 深度優先
9．普里姆（prim）演算法和克魯斯卡爾（kruskal）演算法
10. 不存在環
11. 遞增負值
12. 50，經過中間頂點④
資料結構第七章習題答案
第七章圖 1 下面是乙個圖的鄰接表結構，畫出此圖，並根據此儲存結構和深度優先搜尋演算法寫出從c開始的深度優先搜尋序列。解答 a b f c d e c開始的深度優先搜尋序列 cdeabf 唯一的結果 2 假定要在某縣所轄六個鎮 含縣城 之間修公路，若鎮i和鎮j之間有可能通過道路連線，則wij表示這條...
第七章習題
第七章分配理論 一 填空題 1 生產要素的需求不僅是一種的需求，也是一種的需求或的需求。2 為了實現利潤最大化，廠商在使用一種可變生產要素時，必須使要素的等於要素的用公式表示即 3 在完全競爭的產品市場上，就單個廠商而言，p mr。與之相對應，要素的邊際收益產量等於要素的用公式表示即 4 在不完全競...
第七章習題答案
7.2 有一10kva 10 000 225 v的單相變壓器，如果在原繞組兩端加上額定電壓，在額定負載下測得副繞組端電壓為220v，求該變壓器的原 副繞組的額定電流和電壓調整率。7.4 有一台1000kva 10 6.3kv的三相變壓器，接法為y，d11，求原 副繞組的額定線電流和相電流。7.6 今...