加載中. ..
PDF
109年公務人員特種考試關務人員、身心障礙人員考試及
109年國軍上校以上軍官轉任公務人員考試試題
考 試 別
：
身心障礙人員考試
等 別
：
三等考試
類 科
：
資訊處理
科 目
：
資料結構
考試時間：2小時 座號：
※注意：禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號：
30860
頁次：
2
－
1
一、假設
1:
A n
是一個矩陣，存有
n
個不同的整數，且已依序從小到大排列。
給定一個整數
s
，設計一個線性時間（linear time）的演算法，找出在
1:
A n
中是否存在兩個相異之
A i
和
A j
，使得
A i A j s
。若存在，則印出
任一組符合條件之
i
和
j
；若不存在，則印出 0。（須詳述或證明所設計程
式之正確性及其計算複雜度，否則不計分）（25 分）
二、令 G = (V,E)為一點數（number of vertexes）
V
> 2 的連通（connected）無
向圖（undirectedgraph），w：E→Ｚ為權重（weight）函數。令 T=(
Ｖ
,E')，
E'
E，是 G的一個最小權重擴張樹（minimum spanning tree）。假設每
個邊（edge）的權重都是正整數，且都不相同。判定下列敘述的正確性。
若敘述是正確的，請說明理由；若敘述是錯的，請舉一個反例。（僅有答
案，未說明理由或未舉出反例者，不予計分）
若e是所有邊中權重最大者，則 e
E'。（也就是 e不會在任一個 G
的最小權重擴張樹中）（10 分）
假設 G是2-連通（2-connected）。（也就是去掉任一條邊 G仍是連通
的）此時，若 e是所有邊中權重最大者，則 e
E'。（15 分）
代號：
30860
頁次：
2
－
2
三、斐波那契數（Fibonacci number）Fn的定義為：F0= 0, F1= 1, Fn=Fn-1 +Fn-2 ,
n> 1。下面是一個計算斐波那契數 Fn的演算法，以類似 C語言的函數（C
function）表示，其中資料型態integer 表示整數。
integer Fib(n)
{
if (n == 0) return 0;
if (n == 1) return 1;
return Fib(n- 1) ＋Fib(n- 2);
}
假設輸入的整數 n
0。證明此程式的計算複雜度 T(n) > Fn。在分析計
算複雜度時，可將“==”, “=”, “+”和“return”當作只需要一個單位時間的
運算。（25 分）
四、假設有個矩陣
1:
A n
儲存 n個整數。本題將設計 heap 排序演算法（heap
sort）之重要部分，將矩陣
1:
A n
變成一個 max-heap。
說明
1:
A n
是一個 max-heap 之定義。（5分）
設計一個副程式 sift(A,r,n)其輸入參數 A是一個矩陣，n是矩陣 A的
大小，1
r
n是一個指標。副程式 sift(A,r,n)的功能是將
A r
為
樹根的子樹變成 heap。（在呼叫 sift(A,r,n)之前，
A i
的所有子樹必
須已經是 heap）並分析其計算時間確實是 O(h(r))，其中 h(r)是以
A r
為樹根的子樹的高度。（10 分）
利用 sift(A,r,n)設計一個線性時間的演算法，將矩陣
1:
A n
變成 heap，
並證明所設計的演算法的時間複雜度為線性。（10 分）