加載中. ..
PDF
104
年公務人員高等考試三級考試試題 代號：26850
類 科： 資訊處理
科 目： 資料結構
考試時間： 2小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
全一頁
一、有位程式設計師在撰寫程式時遇到了一個難解的問題，後來發現有兩個演算法可以
解這個難題：演算法 A的時間複雜度為 ))!log(( 2nnO ，演算法 B的時間複雜度為
)))!((log( 2nnO 。假設輸入資料的個數n通常都很大，他應該選擇那個演算法比較好，
原因何在？（20 分）
二、樹（tree）是一個很常用的資料結構。一個樹是指一個沒有迴圈（cycle）的聯通圖
（connected graph）。（每小題 10 分，共 20 分）
證明：每個具有n個節點（node）的樹， 1>n，至少有 2個分支度（degree）為
1的節點。（分支度就是指有多少邊以此節點為端點。）
用前項結果證明：每個具有n個節點的樹， 1>n，恰好有 1−n個邊（edge）。
三、給定一個權重圖（weighted graph）， ),,( w
E
V
G
=，其中每個邊（edge）e的權重
)(ew 都是正整數，為了簡單，假設
}
,...,2,1
{
n
V
=。任意點v與起始點
s
的距離可以用
一個矩陣 ]..1[ nd 來表示。（每小題 10 分，共 20 分）
設計一個只需 )(nO 空間的方法來記錄從
s
出發，到達每個點的最短路徑。
說明計算與印出從起始點
s
到任意點
V
t
∈的最短路徑的演算法。（解此小題時可參考
Dijkstra 或其他演算法來設計，且不須將 Dijkstra 或別的演算法做詳細的描述。）
四、有個矩陣 ]..1[ n
A
，n的值很大。在矩陣
A
中存有n個正整數，且從小到大排列。給定
某個整數
x
，二分搜尋法（binary search）可以在 )(lo
g
nO 的時間內找出
x
在矩陣
]..1[ n
A
的位置，或宣告在 ]..1[ n
A
中沒有
x
。在某個應用中，已知絕大部分的
x
都會出
現在矩陣 ]..1[ na 的前面m個元素，且 m的值遠小於n，但是無法預知m的範圍。設
計一個演算法，可以在 )(lo
g
mO 的時間內完成搜尋。（20 分）
五、假設有個矩陣 ]..1[ n
A
儲存n個整數。Quick sort 是一個排序演算法。假設有個副程式
partition ),,(
r
l
A
其輸入參數
A
是一個矩陣， n
r
l
r
l<<,, ，是兩個指標。其回傳的值m
也是一個指標。這個副程式可將矩陣中從l到
r
的這一段資料 ]..[
r
l
A
區分成兩段：
]..[ ml
A
和]..1[
r
m
A
+，使得在 ]..[ ml
A
中的元素都小於或等於
x
，而在 ]..1[
r
m
A
+中的
元素都大於或等於
x
，其中
x
是從 ]..[
r
l
A
中隨機選擇的一個整數。接下來要在此兩段
資料遞迴執行 partition。避免這些遞迴計算可以用一個堆疊（stack）來處理。假設
partition ),,(
r
l
A
回傳m，則執行：
if )( ml < push ),( ml into stack
if )1(
r
m<+ push ),1(
r
m+ into stack
一開始，堆疊中只有一組資料， ),1( n表示 ]..1[ n
A
需要排序。如此反覆將堆疊最上面
的資料 ),(
r
l移出，執行 partition ),,(
r
l
A
，直到堆疊沒有資料為止。
（每小題 10 分，共 20 分）
證明在最糟情況下，堆疊的高度可以達到 2/n。
設計一個好的演算法以降低 stack 的高度，並證明堆疊的高度最多只需要 1log +n。