第七章資料結構作業
第七章圖
選擇題1．設無向圖的頂點個數為n，則該圖最多有（ ）條邊。
a．n-1 b．n(n-1)/2 c． n(n+1)/2 d．0 e．n2
2．乙個n個頂點的連通無向圖，其邊的個數至少為（ ）。
a．n-1b．nc．n+1d．nlogn；
3．乙個有n個結點的圖，最少有（ ）個連通分量，最多有（ ）個連通分量。
a．0b．1c．n-1d．n
4．在乙個無向圖中，所有頂點的度數之和等於所有邊數（ ）倍，在乙個有向圖中，所有頂點的入度之和等於所有頂點出度之和的（ ）倍。
a．1/2b．2c．1d．4
5．下列哪一種圖的鄰接矩陣是對稱矩陣？（ ）
a．有向圖b．無向圖c．aov網d．aoe網
6．當乙個有n個頂點的圖用鄰接矩陣a表示時，頂點vi的度是（ ）。
a． b． c． d．+
7．下面哪一方法可以判斷出乙個有向圖是否有環（迴路）：
a．深度優先遍歷 b. 拓撲排序 c. 求最短路徑 d. 廣度優先遍歷
8. 在圖採用鄰接表儲存時，求最小生成樹的 prim 演算法的時間複雜度為( )。
a. o(nb. o(n+e) c. o(n2) d. o(n3)
9. 求解最短路徑的floyd演算法的時間複雜度為( )。
a．o（n） b. o（n+c） c. o（n*n） d. o（n*n*n）
10．若乙個有向圖的鄰接距陣中,主對角線以下的元素均為零,則該圖的拓撲有序序列（ ）。
a．存在 b．不存在
11．乙個有向無環圖的拓撲排序序列（ ）是唯一的。
a．一定b．不一定
12. 在有向圖g的拓撲序列中，若頂點vi在頂點vj之前，則下列情形不可能出現的是（ ）。
a．g中有弧b．g中有一條從vi到vj的路徑
c．g中沒有弧d．g中有一條從vj到vi的路徑
13. 在用鄰接表表示圖時，拓撲排序演算法時間複雜度為( )。
a. o(nb. o(n＋e) c. o(n*n) d. o(n*n*n)
14. 關鍵路徑是事件結點網路中（ ）。
a．從源點到匯點的最長路徑 b．從源點到匯點的最短路徑 c．最長迴路 d．最短迴路
15．下列關於aoe網的敘述中，不正確的是（ ）。
a．關鍵活動不按期完成就會影響整個工程的完成時間
b．任何乙個關鍵活動提前完成，那麼整個工程將會提前完成
c．所有的關鍵活動提前完成，那麼整個工程將會提前完成
d．某些關鍵活動提前完成，那麼整個工程將會提前完成
判斷題1. 有e條邊的無向圖，在鄰接表中有e個結點。（ ）
2. 有向圖的鄰接矩陣是對稱的。（ ）
3．任何無向圖都存在生成樹。（ ）
4. 不同的求最小生成樹的方法最後得到的生成樹是相同的.（ ）
5. 有環圖也能進行拓撲排序。（ ）
6. 關鍵路徑是aoe網中從源點到終點的最長路徑。（ ）
填空題1．具有10個頂點的無向圖，邊的總數最多為______。
2. 在有n個頂點的有向圖中，若要使任意兩點間可以互相到達，則至少需要______條弧。
3．n個頂點的連通無向圖，其邊的條數至少為______。
4．n個頂點的連通圖用鄰接矩陣表示時,該矩陣至少有_______個非零元素。
5．構造連通網最小生成樹的兩個典型演算法是______。
6. 有乙個用於n個頂點連通帶權無向圖的演算法描述如下：
（1）．設集合t1與t2，初始均為空；
（2）．在連通圖上任選一點加入t1；
（3）．以下步驟重複n-1次：
a.在i屬於t1，j不屬於t1的邊中選最小權的邊；
b.該邊加入t2。
上述演算法完成後，t2中共有______條邊，該演算法稱______演算法，t2中的邊構成圖的______。
7．aov網中,結點表示______,邊表示______。aoe網中,結點表示______,邊表示______。
8. 當乙個aov網用鄰接表表示時，可按下列方法進行拓撲排序。
（1）．查鄰接表中入度為______的頂點，並進棧；
（2）．若棧不空，則①輸出棧頂元素vj，並退棧；②查vj的直接後繼vk，對vk入度處理，處理方法是______；
（3）．若棧空時，輸出頂點數小於圖的頂點數，說明有______，否則拓撲排序完成。
演算法應用題
1、對n個頂點的無向圖，採用鄰接矩陣表示，如何判別下列有關問題
1）圖中有多少條邊？
2）任意兩個頂點i和j是否有邊相連？
3）任意乙個頂點的度是多少？
2．設g=(v,e)以鄰接表儲存，試寫出深度優先和廣度優先序列。
3、已知一無向圖的鄰接矩陣如下，求該圖從頂點v1出發的廣度優先遍歷和深度優先遍歷序列。
0 0 1 0 0 1 0
0 0 0 1 0 0 1
1 0 0 1 0 1 0
0 1 1 0 1 1 1
0 0 0 1 0 0 0
1 0 1 1 0 0 1
0 1 0 1 0 1 0
4．下圖表示乙個地區的通訊網，邊表示城市間的通訊線路，邊上的權表示架設線路花費的代價，如何選擇能溝通每個城市且總代價最省的n-1條線路，畫出所有可能的選擇。
5、對下面的有向圖，試利用dijkstra演算法從頂點1到其它頂點的最短路徑，並寫出執行該演算法過程中每次迴圈的狀態。
6、對下面的aoe網，求出各項活動的最早開始時間e(i)和最遲開始時間l(i)，並回答：工程完成的最短時間是多少？哪些是關鍵活動？
7．下圖是帶權的有向圖g的鄰接表表示法，求：
（1）．以結點v1出發深度遍歷圖g所得的結點序列；
（2）．以結點v1出發廣度遍歷圖g所得的結點序列；
（3）．從結點v1到結點v8的最短路徑；
（4）．從結點v1到結點v8的關鍵路徑。
資料結構C語言版第2章練習題
第2章線性表練習題 一 填空 1.在順序表中插入或刪除乙個元素，需要平均移動元素，具體移動的元素個數 與有關。2.線性表中結點的集合是的，結點間的關係是的。3.向乙個長度為n的向量的第i個元素 1 i n 1 之前插入乙個元素時，需向後移動個元素。4.向乙個長度為n的向量中刪除第i個元素 1 i n...
資料結構 C語言版
考試大綱將陸續公布 計算機應用基礎考試大綱 主要考查計算機應用基礎知識，參考參考用書課後練習內容。其它同型別的計算機應用基礎教材均可作為複習用書 高等數學考試大綱 一 函式 二 極限 1 數列極限的概念 2 數列極限的性質 3 函式極限的概念 4 函式極限的定理 5 無窮小量和無窮大量 6 兩個重要...
資料結構C語言版第45章習題答案
第4 5章串和陣列自測卷答案 一 填空題 每空1分，共20分 1.不包含任何字元 長度為0 的串稱為空串 由乙個或多個空格 僅由空格符 組成的串稱為空白串。對應嚴題集4.1 簡答題 簡述空串和空格串的區別 2.設s a document mary.doc 則strlen s 20的字元定位的位置為 ...