104年公務人員高等考試三級 資料結構
首頁
>
線上測驗
>
公職考試>高考/三等>資訊處理
> 104年公務人員高等考試三級 資料結構
年度
年度
106
105
104
103
101
100
99
98
1.
有位程式設計師在撰寫程式時遇到了一個難解的問題,後來發現有兩個演算法可以解這個難題:演算法A的時間複雜度為O(n
2
log(n!)),演算法B的時間複雜度為O(n
2
((log n)!))。假設輸入資料的個數n通常都很大,他應該選擇那個演算法比較好,原因何在?
題型:問答題
難易度:尚未記錄
2.
樹(tree)是一個很常用的資料結構。一個樹是指一個沒有迴圈(cycle)的聯通圖(connected graph)。
(一) 證明:每個具有n個節點(node)的樹,n >1,至少有2個分支度(degree)為1 的節點。(分支度就是指有多少邊以此節點為端點。)
(二) 用前項結果證明:每個具有n個節點的樹,n >1,恰好有n −1個邊(edge)。
題型:問答題
難易度:尚未記錄
3.
給定一個權重圖(weighted graph), ,其中每個邊(edge) 的權重w(e)都是正整數,為了簡單,假設V = {1,2,..., n}。任意點v與起始點s的距離可以用一個矩陣d [1..n]來表示。
(一) 設計一個只需O(n)空間的方法來記錄從s出發,到達每個點的最短路徑。
(二) 說明計算與印出從起始點s到任意點 的最短路徑的演算法。(解此小題時可參考Dijkstra或其他演算法來設計,且不須將Dijkstra或別的演算法做詳細的描述。)
題型:問答題
難易度:尚未記錄
4.
有個矩陣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)的時間內完成搜尋。
題型:問答題
難易度:尚未記錄
5.
假設有個矩陣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),直到堆疊沒有資料為止。
(一) 證明在最糟情況下,堆疊的高度可以達到n / 2。
(二) 設計一個好的演算法以降低stack 的高度,並證明堆疊的高度最多只需要log n +1。
題型:問答題
難易度:尚未記錄
購買題庫後,可使用那些功能?
可觀看題目詳解,並提供模擬測驗!(免費會員無法觀看研究所試題解答)