申論 1有位程式設計師在撰寫程式時遇到了一個難解的問題，後來發現有兩個演算法可以解這個難題：演算法A 的時間複雜度為O(n2log(n!))，演算法B 的時間複雜度為O(n2((logn)!))。假設輸入資料的個數n通常都很大，他應該選擇那個演算法比較好，原因何在？（20 分）
本卷皆為申論題，點「看答案與解析」查看擬答。
弱點分析
未作答的題目不計分。看我的紀錄
申論 2樹（tree）是一個很常用的資料結構。一個樹是指一個沒有迴圈（cycle）的聯通圖（connected graph）。（每小題10 分，共20 分）㈠證明：每個具有n個節點（node）的樹，n>1，至少有2 個分支度（degree）為1 的節點。（分支度就是指有多少邊以此節點為端點。）㈡用前項結果證明：每個具有n個節點的樹，n>1，恰好有n−1個邊（edge）。
申論 3給定一個權重圖（weighted graph），G =(V,E,w)，其中每個邊（edge）e的權重w(e)都是正整數，為了簡單，假設V ={2,1,...,n}。任意點v 與起始點s的距離可以用一個矩陣d1[..n]來表示。（每小題10 分，共20 分）㈠設計一個只需O(n)空間的方法來記錄從s出發，到達每個點的最短路徑。㈡說明計算與印出從起始點s到任意點t ∈V的最短路徑的演算法。（解此小題時可參考Dijkstra 或其他演算法來設計，且不須將Dijkstra 或別的演算法做詳細的描述。）
申論 4有個矩陣A1[..n]，n的值很大。在矩陣A中存有n個正整數，且從小到大排列。給定某個整數x ，二分搜尋法（binary search）可以在O(log n)的時間內找出x 在矩陣A1[..n]的位置，或宣告在A1[..n]中沒有x 。在某個應用中，已知絕大部分的x 都會出現在矩陣a1[..n]的前面m個元素，且m 的值遠小於n，但是無法預知m的範圍。設計一個演算法，可以在O(log m)的時間內完成搜尋。（20 分）
申論 5假設有個矩陣A1[..n]儲存n個整數。Quick sort 是一個排序演算法。假設有個副程式partition(A,l,r)其輸入參數A是一個矩陣，l,r,l<r<n，是兩個指標。其回傳的值m也是一個指標。這個副程式可將矩陣中從l 到r 的這一段資料A[l ..r]區分成兩段：A[l ..m]和A[m+1..r]，使得在A[l ..m]中的元素都小於或等於x ，而在A[m+1..r]中的元素都大於或等於x，其中x 是從A[l ..r]中隨機選擇的一個整數。接下來要在此兩段資料遞迴執行partition。避免這些遞迴計算可以用一個堆疊（stack）來處理。假設partition(A,l,r)回傳m，則執行：if (l <m) push (l ,m) into stackif (m+1<r) push (m +,1r) into stack一開始，堆疊中只有一組資料，,1( n )表示A1[..n]需要排序。如此反覆將堆疊最上面的資料(l ,r)移出，執行partition(A,l,r)，直到堆疊沒有資料為止。（每小題10 分，共20 分）㈠證明在最糟情況下，堆疊的高度可以達到n/2。㈡設計一個好的演算法以降低stack 的高度，並證明堆疊的高度最多只需要logn+1。