99年公務人員特種考試關務人員考試、99年公務人員特種考試經濟部專利商標審查人員考試、
99年第一次公務人員特種考試司法人員考試及99年國軍上校以上軍官轉任公務人員考試試題
代號：33560
等 別： 三等關務人員考試
類(科)別： 資訊處理
科 目： 資料結構


一、假設運算子（operator）的運算先後次序的規則（Precedence and Associativity）之優
先順序如下：指標（pointer,→）、乘除、加減、比大小；同等類的運算子按照運算
子在infix expression出現的優先次序（例如+、..為同一等類）。請列出如何利用堆
疊（stack）轉換infix expression： a+b/c>(d..>e * f+g)/h 成prefix表示法。（20分）


二、依序輸入下列6筆資料：L，C，E，P，S，A（英文字母代表的是key value，而字
母A的值是小於字母B的值）
(一)排成最大二元堆（max binary heap）後的堆積為何？（10分）
(二)刪除（delete）根節點（root）後，再加入新的值M後的堆積為何？（10分）


三、解釋名詞：
(一)軟體開發生命週期（software development lifecycle）至少包含五大重要階段
（phases），請寫出這些階段以及該階段的主要任務為何？（10分）
(二)在軟體開發上，必須要注意所謂的「安全容錯」（Fail-Safe），試述其意義？
（10分）


四、以下程式的時間複雜度（time complexity）Big-O為何？（20分）
int C(int N, int K)
{
if ((K == 0) || (K == N))
return 1;
else if (K > N)
return 0;
else
return C(N-1, K-1) + C(N-1, K);
}


五、拓樸排序（topological sorting）是一個在沒有迴圈的有向性圖形（directed graph）找
出節點順序（Linear order）。例如，如果有一條有向連結從節點u指向節點v，則
我們說u v的順序為u在v的前面。拓樸排序的演算法如下：
topSort（input Graph, output List）
s=createStack();
for (all vertices v in the graph)


if (v has no predecessors) {
Push v into s;
Mark v as visited;}


while (s is not empty) {
if (all vertices adjacent to the vertex v on the top of the stack have
been visited) {
Pop v out of s;
Output v;




} else {
Push each unvisited vertex u adjacent to vertex v into s and
mark u as visited; // 注意：當有一個以上的選擇時，永遠
優先選擇代號數字比較小的節點先放入堆疊


}
}

(一)以下為一個有向性圖形，請利用以上程式列出所找出的節點順序。（請列出執行
過程堆疊（stack）內的內容）（10分）

(二)如果有向性圖G=（V, E），節點集合的大小為N，請問此演算法的時間複雜度
（time complexity）Big-O為何？（請說明如何得到答案）（10分）