資訊處理 107 年資料結構考古題（共 5 題）
資料來源：考選部歷屆試題｜法律人 LawPlayer 整理
https://lawplayer.com/exam/information-processing/107-data-structures

第 1 題
計算正整數a 和b 的最大公因數gcd(a, b)的演算法，以類似C 語言表示
如下:
1
integer gcd(a, b) {

第 2 題
x = a; y = b;

第 3 題
while (y > 0) {r = x % y; x = y; y = r;}

第 4 題
return x;

第 5 題
}
其中資料型態integer 表示整數，x % y 表示x 除以y 的餘數。請回答下
列問題：（每小題10 分，共20 分）
㈠ 請證明：輸入任意兩個正整數，此程式執行一定時間後就會停止，不
會造成無窮迴圈。
㈡ 假設a > b，請證明此程式之while 迴圈（第3 行）至多只會被執行
2 log2 b +1 次。
二、 給定一個權重圖（weighted graph），G =(V, E, w)，假設V = {1, 2,...,n}，
且每個邊（edge）e 的權重w(e)都是正整數。令l(v)為以v 為端點的所有
邊中權重最小的邊。將這些邊集合起來稱作L，也就是
。
∪v
l
L =
)
(
V
v∈
（每小題5 分，共20 分）
㈠ 假設每個邊的權重都不相同。請證明由L 中這些邊所構成的子圖（edge
induced subgraph）G[L]沒有迴圈。
㈡ G[L]是否一定是G 的擴張樹（spanning tree）？若是請證明之，若不
一定是請給一個反例。
㈢ 用以上之結論，設計一個計算G 的最小權重擴張樹（minimum spanning
tree）的演算法。
㈣ 在一般的應用中，邊的權重可能會相同，請修正上述之演算法，使修
正後之演算法可以正確找出答案。

三、 假設陣列A[1..n]儲存n 個正整數x1, x2,..., xn。（每小題10 分，共20 分）
㈠ 已知所有的正整數xi ≤ M。請設計一個O(n + M )時間的演算法將這些
整數由小到大排列。
㈡ 已知所有的正整數xi ≤ n2。請設計一個O(n)時間的演算法將這些整數
由小到大排列，或證明這是不可行的。
四、 假設有個陣列A[1..n]儲存著n 個整數。可將A[1..n]看成二元樹，其中A[1]
是樹根。A[i]的左右子節點分別為A[2i]和A[2i + 1], i =1, 2, . . . , n/2。若
2i>n 或2i+1>n，則這些子節點是不存在的。若A 滿足A[i] ≥ max{A[2i],
A[2i + 1]},1 ≤ i ≤ n/2，則稱陣列A[1..n]是一個堆疊（heap）。假設有個副
程式sift(A, r, n)其輸入參數A 是一個陣列，n 是A 的大小，r ≤ n 是一個
指標，指向此子樹的樹根。副程式sift(A, r, n)的功能是將A[r]為樹根的
子樹變成heap。在呼叫sift(A, r, n)之前，它的左右子樹都已經是heap。
副程式sift(A, r, n)所需的計算時間是O(h(r))，其中h(r)是以A[r]為樹根
的子樹的高度，也就是從樹根到任一樹葉的最長距離。
（每小題10 分，共20 分）
㈠用sift(A, r, n)設計一個線性時間的演算法，將陣列A[1..n]變成heap。
㈡分析以上所設計演算法的計算複雜度為O(n)。
五、斐波納契數（Fibonacci number）Fn的定義是F0 = 0, F1 = 1, Fn = Fn－1+ Fn－2, n> 1。
計算Fibonacci number Fn 的演算法，以類似C 語言表示如下：
1   integer f [N];  // array of N integers
2   integer F(n) {
3       if ( f [n] < 0)
4          f [n]= F(n－1)+ F(n－2);
5       return f [n];
6  }
7   integer Fib(n) {
8       f [0] = 0; f [1] = 1;
9       for (i = 2; i ≤ n; i = i + 1)
10          f [i]=－1;
11      return F(n);
12 }
其中資料型態integer 表示整數。假設輸入的整數n>1。主程式執行
Fib(n)，則副程式F(n)第4 行之指令：
f [n]= F(n－1)+ F(n－2)會被執行幾次？請說明理由。（20 分）

題目為考試當年公告版本，實務標準請以現行規範為準。