國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

九九年關務三等資料結構
一、假設運算子 (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分）