1.下列關于無向連通圖特性的叙述中，正确的是？
Ⅰ．所有頂點的度之和為偶數
Ⅱ．邊數大于頂點個數
Ⅲ．至少有一個頂點的度為1
-
隻有Ⅰ -
隻有Ⅱ -
Ⅰ和Ⅱ -
Ⅰ和Ⅲ
解析：A
1，每條邊連接配接兩個頂點，所有頂點的度之和等于邊數的2倍，是偶數，正确
2，如兩個頂點一條邊的圖就不滿足這個條件，錯
3，如三個頂點三條邊連成一個三角形的圖每個頂點度為2，錯
2.若無向圖 G 中含 7 個頂點，則保證圖 G 在任何情況下都是連通的，則需要的邊數
最少是（ ）
-
6 -
15 -
16 -
21
解析： 在任何情況下，意思就是說，隻要有給定的邊數則必定會連通，無論你的邊怎麼安排，怎麼放，圖G都能構成連通。
因為，隻需要n-1個頂點構成完全無向圖，再加上1條邊和剩下的頂點相連，就能讓n個頂點連通。
由題，n是7，是以6個頂點需要構成完成無向圖需要5+4+3+2+1=6*5/2=15，再加1是16條邊。
是以，隻要有16條邊，圖G一定會連通，不管你邊怎麼放。
是以選C。
至于A選項的6條邊，是圖 G 是連通的最少邊數，不是在任何情況下的。
3.對下圖進行拓 撲 排序，可以得到不同的拓 撲 序列的個數是（B）
-
4 -
3 -
2 -
1 - 解析：
拓撲排序的步驟：由AOV網構造拓撲序列的拓撲排序算法主要是循環執行以下兩步，直到不存在入度為0的頂點為止。
(1) 選擇一個入度為0的頂點并輸出之；
(2) 從網中删除此頂點及所有出邊。
循環結束後，若輸出的頂點數小于網中的頂點數，則輸出“有回路”資訊，否則輸出的頂點序列就是一種拓撲序列
4.下列關于圖的叙述中，正确的是 。
Ⅰ ．回路是簡單路徑
Ⅱ ．存儲稀疏圖，用鄰接矩陣比鄰接表更省空間
Ⅲ ．若有向圖中存在拓撲序列，則該圖不存在回路
-
僅Ⅱ -
僅Ⅰ、Ⅱ -
僅Ⅲ -
僅Ⅰ、Ⅲ
解析：
如果路徑上的各頂點均不互相重複，稱這樣的路徑為簡單路徑。如果路徑上的第一個頂點與最後一個頂點重合，這樣的路徑稱為回路(cycle)或環或圈。如在圖1中，回路有
等等 [1] 。
第一個頂點和最後一個頂點相同的路徑稱為回路；序列中頂點不重複出現的路徑稱為簡單路徑；回路顯然不是簡單路徑，故 Ⅰ 錯誤；稀疏圖是邊比較少的情況，此時用鄰接矩陣的空間複雜度為 O(n2) ，必将浪費大量的空間，而鄰接表的空間複雜度為 O(n+e) ，應該選用鄰接表，故 Ⅱ 錯誤。存在回路的有向圖不存在拓撲序列，若拓撲排序輸出結束後所餘下的頂點都有前驅，則說明隻得到了部分頂點的拓撲有序序列，圖中存在回路，故 Ⅲ 正确。
5.對有n 個頂點、 e 條邊且使用鄰接表存儲的有向圖進行廣度優先周遊，其算法的時間複雜度是（ ）。
-
O(n) -
O(e) -
O(n+e) -
O(n×e)
解析：
對于DFS,BFS周遊來說，時間複雜度和存儲結構有關：
1.若采用鄰接矩陣存儲，時間複雜度為O(n^2); 注意不是n*e
2.若采用鄰接連結清單存儲，時間複雜度為O(n+e);
6.若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關于該圖拓撲序列的結論是（）。
-
存在，且唯一 -
存在，且不唯一 -
存在，可能不唯一 -
無法确定是否存在
解析:
上三角矩陣說明有向圖隻有序号小的節點單向指向序号大的節點，是以存在拓撲序列。加上條件A[i][i+1]全為1才是唯一的，題目沒有說明這一點，是以是可能唯一 (很經典，唯一性)
7.如圖所示的有向帶權圖，若采用迪傑斯特拉（Dijkstra）算法求從源點a到其他各頂點的最短路徑，則得到的第一條最短路徑的目标頂點是b，第二條最短路徑的目标頂點是c，後續得到的其餘各最短路徑的目标頂點依次是（）。
-
d,e,f -
e,d,f -
f,d,e -
f,e,d
解析：從a到各頂點的最短路徑的求解過程：
| 頂點 | 第1趟 | 第2趟 | 第3趟 | 第4趟 | 對5趟 |
| b | (a,b) 2 | ||||
| c | (a,c) 5 | (a,b,c) 3 | |||
| d | ∞ | (a,b,d) 5 | (a,b,d) 5 | (a,b,d) 5 | |
| e | ∞ | ∞ | (a,b,c,f) 4 | ||
| f | ∞ | ∞ | (a,b,c,e) 7 | (a,b,c,e) 7 | (a,b,d,e) 6 |
| 集合S | {a,b} | {a,b,c} | {a,b,c,f} | {a,b,c,f,d} | {a,b,c,f,d,e} |
後續目标頂點依次為f,d,e，
【排除法】對于A，若下一個頂點為d，路徑a,b,d的長度5，而a,b,c,f的長度僅為4，顯然錯誤。同理可以排除B。将f加入集合S後，采用上述的方法也可以排除D。
8.下列關于最小生成樹的叙述中，正确的是（）。
Ⅰ．最小生成樹的代價唯一
Ⅱ．所有權值最小的邊一定會出現在所有的最小生成樹中
Ⅲ．使用普裡姆（Prim）算法從不同頂點開始得到的最小生成樹一定相同
Ⅳ．使用普裡姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹總不相同
-
僅Ⅰ -
僅Ⅱ -
僅Ⅰ、Ⅲ -
僅Ⅱ、Ⅳ
解析：
對于I，最小生成樹的樹形可能不唯一（這是因為可能存在權值相同的邊），但是代價一定是唯一的，I正确。對于II，如果權值最小的邊有多條并且構成環狀，則總有權值最小的邊将不出現在某棵最小生成樹中，II錯誤。對于III，設N個結點構成環，N-1條邊權值相等，則從不同的頂點開始普裡姆算法會得到N- 1中不同的最小生成樹，III錯誤。對于IV，當最小生成樹唯一時（各邊的權值不同），普裡姆算法和克魯斯卡爾算法得到的最小生成樹相同，IV錯誤。
9.設圖的鄰接矩陣A 如下所示。各頂點的度依次是（ ）。
-
1， 2， 1， 2 -
2， 2， 1， 1 -
3， 4， 2， 3 -
4， 4， 2， 2
解析：
無向圖的邊數組（鄰接矩陣）是對陣矩陣。各頂點的度為鄰接矩陣中對應行的元素之和。
有向圖的各頂點的度為出度加上入度之和。出度為對應頂點所在行的所有元素之和，入度為對應頂點所在列的所有元素之和。
該圖明顯為有向圖。是以各個頂點的度為其出度和入度之和，即所在行和列元素之和。
10.若對如下無向圖進行周遊，則下列選項中，不是廣度優先周遊序列的是（）。D
-
h， c， a， b， d， e， g， f -
e， a， f， g， b， h， c， d -
d， b， c， a， h， e， f， g -
a， b， c， d， h， e， f， g
解析：
第1步：通路A。
第2步：依次通路C,D,F。
在通路了A之後，接下來通路A的鄰接點。前面已經說過，在本文實作中，頂點ABCDEFG按照順序存儲的，C在"D和F"的前面，是以，先通路C。再通路完C之後，再依次通路D,F。
第3步：依次通路B,G。
在第2步通路完C,D,F之後，再依次通路它們的鄰接點。首先通路C的鄰接點B，再通路F的鄰接點G。
第4步：通路E。
在第3步通路完B,G之後，再依次通路它們的鄰接點。隻有G有鄰接點E，是以通路G的鄰接點E。
是以通路順序是：A -> C -> D -> F -> B -> G -> E
這題，a開始的話，接下來明顯是bhe，順序不分先後
11.下列AOE 網表示一項包含 8 個活動的工程。通過同時加快若幹活動的進度可以縮短整個工程的工期。下列選項中，加快其進度就可以縮短工程工期的是（ ）。
-
c 和 e -
d 和 e -
f 和 d -
f 和 h
關鍵路徑詳解：
解析：
這個網有三條關鍵路徑：
- b、d、c、g
- b、d、e、h
- b、f、h
縮短工期的活動要涵蓋三條路徑。
12.對如下所示的有向圖進行拓撲排序，得到的拓撲序列可能是 （D）
-
3,1,2,4,5,6 -
3,1,2,4,6,5 -
3,1,4,2,5,6 -
3,1,4,2,6,5
解析：
每次選取極大頂點（入度為0的頂點），并把它跟它的出度一起從圖中删掉
第一次删掉3
第二次删掉1
第三次删掉4
第四次可以删掉2或者6，若依據選項CD删掉2，那麼第五次删掉6，最後删掉5
314265，選D
13.設有向圖G=(V,E)，頂點集V={V0,V1,V2,V3}，邊集E={<v0,v1>，<v0,v2>，<v0,v3>，<v1,v3>}。若從頂點V0 開始對圖進行深度優先周遊，則可能得到的不同周遊序列個數是 。
-
2 -
3 -
4 -
5
解析：
畫出該有向圖圖形如下：
采用圖的深度優先周遊，共5種可能：<v0, v1, v3, v2>，<v0, v2, v3, v1>，<v0, v2, v1, v3>，<v0, v3, v2, v1>，<v0, v3, v1, v2>，選D。
14.求下面帶權圖的最小（代價）生成樹時，可能是克魯斯卡（Kruskal）算法第2次選中但不是普裡姆（Prim）算法（從V4開始）第2次選中的邊是 。 C
-
(V1,V3) -
(V1,V4) -
(V2,V3) -
(V3,V4)
解析：
Kruskal算法是按權值選邊，若選邊後不形成回路,則保留作為一條邊,若形成回路則除去
Prim算法是每次從目前的二叉樹節點向外延伸的，選擇權值最小的邊
克魯斯卡（Kruskal）算法 和 普裡姆（Prim）算法（從 V4 開始）第1次選中的邊都是(v4,v1) 。Kruskal算法第二次可以選擇(v1,v3), (v2,v3), (v3,v4); Prim算法第二次可以選擇(v1,v3), (v3,v4)
15.下列選項中，不是下圖深度優先搜尋序列的是 。D
-
V1, V5, V4, V3, V2 -
V1, V3, V2, V5, V4 -
V1, V2, V5, V4, V3 -
V1, V2, V3, V4, V5
解析：按深度優先搜尋就行，2不可以直接到3
16.若将n個頂點e條弧的有向圖采用鄰接表存儲，則拓撲排序算法的時間複雜度是 。
-
O(n) -
O(n+e) -
O(n2) -
O(n*e)
解析：
根據拓撲排序的規則，輸出每個頂點的同時還要删除以它為起點的邊，這樣對各頂點和邊都要進行周遊，故拓撲排序的時間複雜度為O(n+e)
17.連結：使用迪傑斯特拉（Dijkstra）算法求下圖中從頂點1到其他各頂點的最短路徑，依次得到的各最短路徑的目标頂點是 。B
-
5, 2, 3, 4, 6 -
5, 2, 3, 6, 4 -
5, 2, 4, 3, 6 -
5, 2, 6, 3, 4
解析：
根據Dijkstra算法，從頂點1到其餘各頂點的最短路徑如下表所示：
18.：帶權圖（權值非負，表示邊連接配接的兩頂點間的距離）的最短路徑問題是找出從初始頂點到目标頂點之間的一條最短路徑。假設從初始頂點到目标頂點之間存在路徑，現有一種解決該問題的方法：
① 設最短路徑初始時僅包含初始頂點，令目前頂點u為初始頂點；
② 選擇離u最近且尚未在最短路徑中的一個頂點v，加入到最短路徑中，修改目前頂點u=v；
③ 重複步驟②，直到u是目标頂點時為止。
請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明。
解析：該方法不一定能（或不能）求得最短路徑。（4分）
舉例說明：（6分）
圖A-4中，設初始頂點為1，目标頂點為4，欲求從頂點1到頂點4之間的最短路徑，顯然這兩點之間的最短路徑長度為2。利用給定方法求得的路徑長度為3，但這條路徑并不是這兩點之間的最短路徑。
圖A-5中，設初始頂點為1，目标頂點為3，欲求從頂點1到頂點3之間的最短路徑。利用給定的方法，無法求出頂點1到頂點3的路徑。
| | |
| 圖A-4 | 圖A-5 |
利用給定的方法，無法求出頂點1到頂點3的路徑。
【評分說明】①若考生回答“能求得最短路徑”，無論給出何種證明，均不給分。
② 考生隻要舉出類似上述的一個反例說明“不能求得最短路徑”或答案中展現了“局部最優不等于全局最優”的思想，均可給6分；若舉例說明不完全正确，可酌情給分。
題外話：最小生成樹與最短路徑的差別
最小生成樹能夠保證整個拓撲圖的所有路徑之和最小，但不能保證任意兩點之間是最短路徑。一般用 Kruskal 和 Prim算法
最短路徑是從一點出發，到達目的地的路徑最小 一般用 Dijkstra算法
19.已知有6個頂點（頂點編号為0～5）的有向帶權圖G，其鄰接矩陣A為上三角矩陣，按行為主序（行優先）儲存在如下的一維數組中。
| 4 | 6 | ∞ | ∞ | ∞ | 5 | ∞ | ∞ | ∞ | 4 | 3 | ∞ | ∞ | 3 | 3 |
要求：
（1）寫出圖G的鄰接矩陣A。
（2）畫出有向帶權圖G。
（3）求圖G的關鍵路徑，并計算該關鍵路徑的長度。
解析：（注意對角就是自己到自己，是以對角全0，就很好求了）
1）在上三角矩陣A[6][6]中，第1行至第5行主對角線上方的元素個數分别為5、4、3、2、1，由此可以畫出壓縮存儲數組中的元素所屬行的情況，如下圖所示。
用“平移”的思想，将前5個、後4個、後3個、後2個、後1個元素，分别移動到矩陣對角線（“0”）右邊的行上。圖G的鄰接矩陣A如下所示。
2）根據上面的鄰接矩陣，畫出有向帶權圖G，如下圖所示。
3）按照算法，先計算各個事件的最早發生時間，各個事件的最遲發生時間
事件最早發生時間 （左到右取最大值）通過前驅加邊
事件最遲發生時間 （右到左取最小值）通過後驅減邊
| i | 1 | 2 | 3 | 4 | 5 |
| ve(i) | 4 | 9 | 13 | 12 | 16 |
| vl(i) | 4 | 9 | 13 | 13 | 16 |
接下來計算所有活動的最早和最遲發生時間
活動的最早：取前驅事件最早
活動的最遲：取後驅事件最晚減邊
| a0→1 | a0→2 | a1→2 | a2→3 | a2→4 | a3→5 | a4→5 |
| e() | 4 | 9 | 9 | 13 | 12 | |
| l() | 3 | 4 | 9 | 10 | 13 | 13 |
| l-e | 3 | 1 | 1 |
滿足l()-e()=0的路徑就是關鍵路徑，是以關鍵路徑為a0→1、a1→2、a2→3、a3→5，如下圖所示（粗線表示），長度為4+5+4+3=16。
20.：某網絡中的路由器運作OSPF路由協定，題42表是路由器R1維護的主要鍊路狀态資訊（LSI），題42圖是根據題42表及R1的接口名構造出來的網絡拓撲。
題42表R1所維護的LSI
| R1的LSI | R2的LSI | R3的LSI | R4的LSI | 備注 | ||
| Router ID | 10.1.1.1 | 10.1.1.2 | 10.1.1.5 | 10.1.1.6 | 辨別路由器的IP位址 | |
| Link1 | ID | 10.1.1.2 | 10.1.1.1 | 10.1.1.6 | 10.1.1.5 | 所連路由器的RounterID |
| IP | 10.1.1.1 | 10.1.1.2 | 10.1.1.5 | 10.1.1.6 | Link1的基本IP位址 | |
| Metric | 3 | 3 | 6 | 6 | Link1的費用 | |
| Link2 | ID | 10.1.1.5 | 10.1.1.6 | 10.1.1.1 | 10.1.1.12 | 所連路由器的RounterID |
| IP | 10.1.1.9 | 10.1.1.13 | 10.1.1.10 | 10.1.1.14 | Link2基本IP位址 | |
| Metic | 2 | 4 | 2 | 4 | Link2費用 | |
| Net1 | Prefix | 192.1.1.0/24 | 192.1.6.0/24 | 192.1.7.0/24 | 192.1.7.0/24 | 直接網絡Net1的網絡字首 |
| Metric | 1 | 1 | 1 | 1 | 到達直連網絡Net1的費用 |
題42圖 R1構造的網絡拓撲
請回答下列問題。
（1） 本題中的網絡可抽象為資料結構中的哪種邏輯結構？
（2） 針對題42表中的内容，設計合理的鍊式存儲結構，以儲存題42表中的鍊路狀态資訊（LSI）。要求給對外連結式存儲結構的資料類型定義，并畫出對應題42表的鍊式存儲結構示意圖（示意圖中可僅以ID辨別節點）。
（3） 按照迪傑斯特拉（Dijikstra）算法的政策，依次給出R1到達題42圖中子網192.1.x.x的最短路徑及費用。
解析：
（1） 本題中的網絡可抽象為圖結構。
（2） 鍊式存儲結構的資料類型定義如下：
typedef struct LinkNode
{
unsigned int ID; //所連路由器的 Router ID
unsigned int IP; //本地 IP 位址
}LinkNode; //Link 的結構
typedef struct NetNode
{
unsighed int Prefix; //IP 前段
unsighed int Mask; //掩碼
}NetNode; //Net 的結構
typedef struct ArcNode
{
int Flag; //當 Flag=1 時， 表示 Link； 當 Flag=2 時，表示 Net
union
{
LinkNode Lnode;
NetNode Nnode;
}LinkORNet; //用 union 定義 Link 結點和 Net 結點
unsighed int Metric; //費用
struct ArcNode * Next; //用于指向下一個弧結點的指針
}ArcNode; //弧結點的結構
typedef struct HNode
{
unsighed int RouterID; //路由器的 Router ID
ArcNode * LN_link; //用于指向弧結點的指針
struct HNode * Next; //用于指向下一個表頭結點的指針
}HNode; //表頭結點的結構
對應題42 表的鍊式存儲結構示意圖如下。
21.已知含有5個頂點的圖G如下圖所示。
請回答下列問題：
1）寫出圖G的鄰接矩陣A（行、列下标從0開始）。
2）求A2，矩陣A2中位于0行3列元素值的含義是什麼？
3）若已知具有n（n≥2）個頂點的圖的鄰接矩陣為B，則Bm（2≤m≤n）中非零元素的含義是什麼？
解析：
1）圖G的鄰接矩陣A如下：
2）A2如下：
0行3列的元素值3表示從頂點0到頂點3之間長度為2（2次方是以長度為2）的路徑共有3（0行3列處為3.這條不确定，找不到這個定理出處）條。
3）Bm（2≤m≤n）中位于i行j列（0≤i，j≤n-1）的非零元素的含義是：圖中從頂點i到頂點j長度為m的路徑條數。（這條好像也是定理把，在書上找不到這條？）
22.如果一棵非空k（k≥2）叉樹T中每個非葉結點都有k個孩子，則稱T為正則k叉樹。請回答下列問題并給出推導過程。
（1）若T有m個非葉結點，則T中的葉結點有多少個？
（2）若T的高度為h（單結點的樹h=1），則T的結點數最多為多少個？最少為多少個？
解答：
（1）根據定義，正則k叉樹中僅含有兩類結點；葉結點（個數記為n0）和度為k的分支結點（個數記為n1）。樹T中的結點總數n=n0+nk=n0+m。樹中所含的邊數e=n-1，這些邊均為m個度為k的結點發出的，即e=m×k。整理得：n0+m=m×k+1，故n0=（k-1）×m+1。（3分）
（2）高度為h的正則k叉樹T中，含最多結點的樹形為：除第h層外，第1到第h-1層的結點都是度為k的分支結點；而第h層均為葉結點，即樹是“滿”樹。此時第j（1≤j≤h）層結點數為
，結點總數M1為：
（3分）
含最少結點的正則k叉樹的樹形為：第1層隻有根結點，第2到第h-1層僅含1個分支結點和k-1個葉結點，第h層有k個葉結點。即除根外第2到第h層中每層的結點數均為k，故T中所含結點總數M2為：
M2=1+(h-1)×k （2分）
【評分說明】
①參考答案僅給出一種推導過程，若考生采用其他推導方法且正确，同樣給分。②若考生僅給出結果，但沒有推導過程，則（1）、（2）的最高得分分别是2分和3分。若推導過程或答案不完全正确，酌情給分。