1．關鍵路徑是指AOE(Activity On Edge)網中________。
A. 最長的回路 B. 最短的回路
C. 從源點到匯點(結束頂點)的最長路徑
D. 從源點到匯點(結束頂點)的最短路徑
答案：C
解析：AOE網是一個有向圖，通常用來估算工程的完成時間，圖中的頂點表示事件，有向邊表示活動，邊上的權表示完成這一活動所需的時間。AOE網沒有有向回路，存在唯一的入度為零的開始頂點，及唯一的出度為零的結束頂點。對AOE網最關心的兩個問題：完成整個工程至少需要多少時間？那些活動是影響工程進度的關鍵？這就引出兩個概念：關鍵路徑和關鍵活動。從開始頂點到結束頂點的最長路徑是關鍵路徑，路徑的長度也是工程完成的最少時間。關鍵路徑上的所有活動是關鍵活動，關鍵活動的最大特征是：該活動的最早開始時間等于該活動所允許的最遲開始時間。關鍵活動拖延時間，整個工程也要拖延時間。求關鍵路徑只需求出起點到終點的最長路徑即可，注意關鍵路徑不是唯一的。
復習提示：類似的考點還有：AOV網、最短路徑、最小生成樹。
2．以下序列中不符合堆定義的是________。
A．(102，87，100，79，82，62，84，42，22，12，68)
B．(102，100，87，84，82，79，68，62，42，22，12)
C．(12，22，42，62，68，79，82，84，87，100，102)
D．(102，87，42，79，82，62，68，100，84，12，22)
答案：D
解析：判斷堆的辦法就是把序列看成是一棵完全二叉樹，若樹中的所有非終端結點的值均不大于（或不小于）其左右孩子的結點的值，則該序列為堆。
復習提示：考生復習過程中對定義一定要清楚，這是拿分的關鍵。
3．一個具有767個結點的完全二叉樹，其葉子結點個數為____。
A. 383 B. 384 C. 385 D. 386
答案：B
解析：可以根據公式進行推導，假設n0是度為0的結點總數（即葉子結點數），n1是度為1的結點總數，n2是度為2的結點總數，由二叉樹的性質可知：n0＝n2＋1，則n= n0＋n1＋n2（其中n為完全二叉樹的結點總數），由上述公式把n2消去得：n= 2n0+n1－1，由于完全二叉樹中度為1的結點數只有兩種可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一個公式：n0＝?（n＋1）/2 ?，就可根據完全二叉樹的結點總數計算出葉子結點數。本題計算得：384。
復習提示：該記得公式要記住，臨時推導也可以，但容易耽誤時間。
4．若一個具有n個結點、k條邊的非連通無向圖是一個森林(n>k)，則該森林中必有____棵樹。
A. k B. n C. n-k D. n+k
答案：C
解析：假設該森林中有s棵樹：T1,T2,……,TS ，且每個Ti有ni 個結點，ki條邊(i=1,2,……，S),由樹的等價條件可知： ki＝ni－1，則k＝k1+k2+……+ks=（n1－1）+（n2－1）＋……＋（ns－1）＝n－s,故s=n－k,所以該森林中必有n－k棵樹。
復習提示：該題如果清楚樹的等價條件，可以很容易的解出。若不清楚，則無法下手。不過考生也可以畫出一個具體的非連通無向圖的森林，如：5個結點3條邊2棵樹的森林，也可幫助判斷。抽象問題具體化是作選擇題的一個重要方法。
5. 將兩個長度為 n 的遞增有序表歸并成一個長度為 2n 的遞增有序表，最少需要進行關鍵字比較____次。
A. 1 B. n-1 C. n D. 2n
答案：C
解析：考生首先要明白兩個前提：一是要歸并的兩個表都是遞增有序的且長度都為n，二是題目問的是最少的關鍵字比較次數，即最好的情況下的比較次數。而最好的情況應該是：一個表的所有關鍵字都大于（或小于）另一個表的所有關鍵字，如：（1 2 3 4）與（5 6 7 8）。比較的時候有兩個指針分別指向兩個表的第一個元素，由于一個表的關鍵字要都大于另一個表的關鍵字，所以關鍵字小的表中的元素挨個與關鍵字大的表的第一個元素比較后，先被并入到新表中，這時關鍵字大的表的指針還是指向第一個元素沒變，此時只需將關鍵字大的表復制到新表中即可。所以花費的比較次數就是關鍵字小的表長，也就是n。
6．已知AOE網中頂點v1～v7分別表示7個事件，弧al～a10分別表示10個活動，弧上的數值表示每個活動花費的時間，如下圖所示。那么，該網的關鍵路徑的長度為__（1）__，活動a6的松馳時間（活動的最遲開始時間-活動的最早開始時間）為__（2）__。
(1) A. 7 B. 9 C. 10 D. 11
(2) A. 3 B. 2 C. 1 D. 0
答案：（1）C （2）A
解析：（1）關鍵路徑就是從起點到終點最長的路徑。直接從圖中找即可，v1 v4 v5 v7就是一條，長度為10。（2）從關鍵路徑中可以看出，v1到v4需要花費的時間為6，活動a6至少要在經過時間2后才能開始，最晚開始時間為：6－2＝4 ，則活動a6的松馳時間是4－2＝2。
7．對n個元素進行快速排序時，最壞情況下的時間復雜度為____。
A．O(1og2n) B．O(n) C．O(nlog2n) D． O (n2)
答案：D
解析：若進行快速排序的n個元素按關鍵字有序或基本有序時，快速排序將退化為起泡排序，時間復雜度為O (n2)。
復習提示：這是一道概念題，也是考生的拿分題，考生對概念一定要清楚。
8．任何一個基于“比較”的內部排序的算法，若對6個元素進行排序，則在最壞情況下所需的比較次數至少為____。
A．10 B．11 C．21 D．36
答案：A
解析：內部排序中除了基數排序之外，都是基于“關鍵字間的比較”進行排序的。任何一個借助“比較”進行排序的算法，在最壞情況下所需的比較次數至少為é1og2(n!)ù，由此可解。具體解釋考生可參考嚴蔚敏、吳偉民的《數據結構》291頁。
文章來源于領測軟件測試網 http://www.kjueaiud.com/