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

第 1 題
大學生只剩5 天準備4 科X1, X2, X3, X4，估計的成績點數如下表所示，每
1 科準備至少1 天，使用窮舉法（exhaustive search）有幾種可能？如何最
適化？最適成績s =？（20 分）
天數
科目
X1
X2
X3
X4
1（天）
3
5

第 2 題
4
2
5
6
4
4

第 3 題
6
8
7
5
二、㈠求下列遞迴函數值
(3)
f
？（10 分）
int f(int n){if(n == 0)return 0；else return f(n-1)+n*n;}
㈡求遞迴函數f(n) ？,nN（10 分）
三、k
N-{1}，若有一棵k 元樹（k_ary tree）其中分支度（degree）為i 的節
點數為i 個，i = 1, 2, ..., k，請問該k 元樹其葉節點數L(k)為何？（15 分）
(3) f
？（10 分）
int f(int n){if(n == 0)return 0；else return f(n-1)+n*n;}
㈡求遞迴函數f(n) ？,nN（10 分）
三、k
N-{1}，若有一棵k 元樹（k_ary tree）其中分支度（degree）為i 的節
點數為i 個，i = 1, 2, ..., k，請問該k 元樹其葉節點數L(k)為何？（15 分）（10 分）

第 4 題
密文（Cipher text or Cypher text）：明請到家玩天你我來，應用環狀串列
（circular linked list），請問明文（Plain text or Clear text）為何？（15 分）

第 5 題
㈠如下圖設背包限重100，有A、B、C、D、E 共五個不可分割物件，請
問依貪婪策略（Greedy Algorithm），0_1 整數背包問題（knapsack
problem）/貨物裝載問題（cargo loading problem）其最大利益為何？其
對應的0_1 整數規劃為何？（20 分）
㈡有A、B、C、D、E 共五個可分割物件，請問依貪婪策略，0_1 分數背
包其最大利益為何？（10 分）
物件
重量
利益
A
10
20
B
20
30
C
30
66
D
40
40
E
50
60

第 6 題
1
2
3
4
5
6

第 8 題
9
10
11
四、給予如下之加權雙向圖，邊上的加權值表示此邊的成本。
a
b
c
e
f
d
7
3
8
2
10
5
6
9
4
㈠使用Kruskal’s algorithm 找最小成本擴張樹（Minimal Cost Spanning
Tree, MST）。執行過程中，將邊（edge）逐步加入此MST 之順序為何？
請以邊所對應的兩端節點表示此邊。（5 分）
㈡使用Prim’s algorithm 找出最小成本擴張樹（MST），從節點a 出發。
執行過程中，將邊（edge）逐步加入此MST 之順序為何？請以邊所對
應的兩端節點表示此邊。（5 分）
㈢使用Dijkstra’s algorithm 找出從節點a（來源節點）到其五個節點（目
的節點）之最短路徑（shortest path）。執行過程中，逐步找出最短路徑
的目的節點順序為何？從節點a 到目的節點之最短路徑被找出表示演
算法不再檢視此目的節點之其它可能最短路徑。（10 分）
㈣來源節點a 出發到其他五個目的節點之最短路徑走法與成本分別為
何？（10 分）

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