樹（tree）是一個很常用的資料結構。一個樹是指一個沒有迴圈（cycle）的聯通圖 （connected graph）。（每小題 10 分，共 20 分） (1)證明：每個具有 n 個節點（node）的樹， n > 1，至少有 2 個分支度（degree）為1 的節點。（分支度就是指有多少邊以此節點為端點。）

有位程式設計師在撰寫程式時遇到了一個難解的問題，後來發現有兩個演算法可以 解這個難題：演算法 A 的時間複雜度為 O(n2 log(n!)) ，演算法 B 的時間複雜度為 O(n2 ((log n)!)) 。假設輸入資料的個數n 通常都很大，他應該選擇那個演算法比較好， 原因何在？（20 分）

(2)用前項結果證明：每個具有n 個節點的樹，n > 1，恰好有n −1個邊（edge）。

給定一個權重圖（weighted graph），G = (V,E,w)，其中每個邊（edge）e的權重 w(e)都是正整數，為了簡單，假設V = {1,2,..., n}。任意點v與起始點s的距離可以用 一個矩陣d[1..n]來表示。（每小題10分，共 20分） (1)設計一個只需O(n)空間的方法來記錄從s出發，到達每個點的最短路徑。

(2)說明計算與印出從起始點s到任意點t ∈V 的最短路徑的演算法。（解此小題時可參考 Dijkstra 或其他演算法來設計，且不須將Dijkstra 或別的演算法做詳細的描述。）

有個矩陣A[1..n]，n的值很大。在矩陣A中存有n個正整數，且從小到大排列。給定 某個整數x，二分搜尋法（binary search）可以在O(log n)的時間內找出x在矩陣 A[1..n]的位置，或宣告在A[1..n]中沒有x。在某個應用中，已知絕大部分的x都會出 現在矩陣a[1..n]的前面m個元素，且 m 的值遠小於n，但是無法預知m的範圍。設 計一個演算法，可以在O(log m)的時間內完成搜尋。（20分）

假設有個矩陣A[1..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 stack if (m +1< r) push (m +1, r) into stack 一開始，堆疊中只有一組資料，(1,n)表示A[1..n]需要排序。如此反覆將堆疊最上面 的資料(l, r)移出，執行partition(A,l, r)，直到堆疊沒有資料為止。 （每小題 10 分，共20 分） (1)證明在最糟情況下，堆疊的高度可以達到n / 2。

(2)設計一個好的演算法以降低stack的高度，並證明堆疊的高度最多只需要 (log n +1)。

(五)若 n = 10，且每一組球生產後放上裝箱輸送帶的     球的大小順序非固定順序     。假設輸送帶上原本配置 n 個機器人，若改成配置 2n 個機器人， 整組球順序排好的速度可以加快多少？請說明。

(四)若每一組球生產後放上裝箱輸送帶的     球的大小順序非固定順序     ，請說明輸送帶上最少該配置幾個機器人才能每次都能將球的順序由大排到小？

(三)若 n = 6，且輸送帶上配有 4 個機器人，請給一組放上裝箱輸送帶的球的大小順序，使得其經過這 4 個機器人後，整組球的順序仍未能排好。

114年 - 114 地方政府公務特種考試_三等_資訊處理：資料結構#134706

114年 - 114 公務升官等考試_薦任_資訊處理：資料結構#133251

114年 - 114 高等考試_三級_資訊處理：資料結構#128753

114年 - 114 關務特種考試_三等_資訊處理（選試英文）：資料結構#126563

114年 - 114 身心障礙特種考試_三等_資訊處理：資料結構#126562

113年 - 113 地方政府公務、離島地區公務特種考試_三等_資訊處理：資料結構#124511

113年 - 113 高等考試_三級_資訊處理：資料結構#121217

113年 - 113 關務特種考試_三等_資訊處理（選試英文）：資料結構#119489

112年 - 112 地方政府特種考試_三等_資訊處理：資料結構#118368

112年 - 112 公務升官等考試_薦任_資訊處理：資料結構#117327