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

第 1 題
給予一前序（preorder）表示式ABCD 和後序（postorder）表示式DCBA，
試畫出所有可能的二元樹。（25 分）

第 2 題
假設每個運算元都是一位整數，使用堆疊方法，模擬後序式2542+6+的
計算過程。（25 分）

第 3 題
假設現有五個字母A, B, C, D, E 的頻率分別為0.19, 0.09, 0.21, 0.12, 0.39，
請依步驟建構霍夫曼樹（Huffman Tree）。（25 分）

第 4 題
請逐步寫出下列使用遞迴函式的呼叫與輸出過程。（25 分）
#include <iostream>
using namespace std;
int A(int n, int c = 1) {
if (n == 0)
return c + 1;
return A(n - 2, c * n);
}
int main() {
cout << A(6) << endl;
return 0;
}
(6) << endl;
return 0;
}

第 5 題
下圖為一有向圖（Directed Graph）G。請完成下列各題：
（每小題4 分，共16 分）
㈠畫出圖G 的相鄰串列（Adjacency List）。
㈡畫出圖G 的相鄰矩陣（Adjacency Matrix）。
㈢從節點a 開始，寫出廣度優先搜尋（Breadth-First Search, BFS）的節點
拜訪順序。
㈣從節點a 開始，寫出深度優先搜尋（Depth-First Search, DFS）的節點
拜訪順序。

第 8 題
9
10
11
12
13
14
15
16
17
A(i)
40
30
70
10
--
50
90
--
20
--
--
--
60
80
--
--
--
㈢以下陣列儲存了一個二元搜尋樹，根節點為A(1)，若針對該二元樹刪
除30，請顯示該陣列的變化。（5 分）
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
A(i)
40
30
70
10
--
50
90
--
20
--
--
--
60
80
--
--
--
㈣以下陣列儲存了一個二元搜尋樹，根節點為A(1)，請列舉可依序插入
的五個數值，使得該二元樹成為完整二元樹（full binary tree）。（10 分）
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
A(i)
40
30
70
10
--
50
90
--
20
--
--
--
60
80
--
--
--
四、一個自動化工廠大量採用機器人協助裝箱作業。該工廠固定時間生產出
一組n 個不同大小的塑膠球並放到裝箱作業輸送帶上。輸送帶上配置數
個機器人，當輸送帶上的球經過時，機器人負責將眼前兩顆球將順序排
序正確，大的在前，小的在後。當輸送帶上的球經過了所有機器人後，
球的順序就完全由大排到小了。（每小題5 分，共25 分）
㈠若n = 6，且生產後放上裝箱輸送帶的球的大小為3, 2, 5, 6, 1, 4。請說明
若輸送帶配有4 個機器人是否足夠將球的順序完全由大排到小？
㈡若n = 20，且生產後放上裝箱輸送帶的球的大小為11, 12, 20, 16, 3, 1,
7, 15, 2, 18, 10, 5, 14, 6, 8, 13, 19, 4, 9, 17，請說明輸送帶上最少該配置
幾個機器人才能將球的順序由大排到小？
㈢若n = 6，且輸送帶上配有4 個機器人，請給一組放上裝箱輸送帶的球
的大小順序，使得其經過這4 個機器人後，整組球的順序仍未能排好。
㈣若每一組球生產後放上裝箱輸送帶的球的大小順序非固定順序，請說
明輸送帶上最少該配置幾個機器人才能每次都能將球的順序由大排
到小？
㈤若n = 10，且每一組球生產後放上裝箱輸送帶的球的大小順序非固定
順序。假設輸送帶上原本配置n 個機器人，若改成配置2n 個機器人，
整組球順序排好的速度可以加快多少？請說明。
(1) ，若針對該二元樹刪
除30，請顯示該陣列的變化。（5 分）
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
A(i)
40
30
70
10
--
50
90
--
20
--
--
--
60
80
--
--
--
㈣以下陣列儲存了一個二元搜尋樹，根節點為A（5 分）
(1) ，請列舉可依序插入
的五個數值，使得該二元樹成為完整二元樹（full binary tree）。（10 分）
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
A(i)
40
30
70
10
--
50
90
--
20
--
--
--
60
80
--
--
--
四、一個自動化工廠大量採用機器人協助裝箱作業。該工廠固定時間生產出
一組n 個不同大小的塑膠球並放到裝箱作業輸送帶上。輸送帶上配置數
個機器人，當輸送帶上的球經過時，機器人負責將眼前兩顆球將順序排
序正確，大的在前，小的在後。當輸送帶上的球經過了所有機器人後，
球的順序就完全由大排到小了。（每小題5 分，共25 分）
㈠若n = 6，且生產後放上裝箱輸送帶的球的大小為3, 2, 5, 6, 1, 4。請說明
若輸送帶配有4 個機器人是否足夠將球的順序完全由大排到小？
㈡若n = 20，且生產後放上裝箱輸送帶的球的大小為11, 12, 20, 16, 3, 1,
7, 15, 2, 18, 10, 5, 14, 6, 8, 13, 19, 4, 9, 17，請說明輸送帶上最少該配置
幾個機器人才能將球的順序由大排到小？
㈢若n = 6，且輸送帶上配有4 個機器人，請給一組放上裝箱輸送帶的球
的大小順序，使得其經過這4 個機器人後，整組球的順序仍未能排好。
㈣若每一組球生產後放上裝箱輸送帶的球的大小順序非固定順序，請說
明輸送帶上最少該配置幾個機器人才能每次都能將球的順序由大排
到小？
㈤若n = 10，且每一組球生產後放上裝箱輸送帶的球的大小順序非固定
順序。假設輸送帶上原本配置n 個機器人，若改成配置2n 個機器人，
整組球順序排好的速度可以加快多少？請說明。（10 分）

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