加載中. ..
PDF
102年公務人員升官等考試、102年關務人員升官等考試
102年交通事業郵政、港務、公路人員升資考試試題
代號：
26260
等別(級)： 薦任
類科(別)： 資訊處理
科 目： 資料結構
考試時間： 2小時
座號：
※注意：
可以使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
全一張
（
正面
）
一、解釋名詞：（每小題 5分，共 20 分）
資料結構（data structure）
資料型態（data type）
陣列（array）
堆積樹（heap tree）
二、請使用陣列實作堆疊，給予如下 C程式語言有關堆疊結構的宣告：
#define MAX_STACK 100;
typedef int ITEM_TYPE;
typedef struct stack_type {
ITEM_TYPE item[MAX_STACK];
int top;
} STACK_TYPE;
其中 ITEM_TYPE 可以是 0, 1, 2 等的整數值，可以定義成整數、字元等各種不同的
資料型態；請用 C語言或類似虛擬語言（pseudo code）實作如下兩個堆疊之運算：
（每小題 10 分，共 20 分）
void push（STACK_TYPE *stack, ITEM_TYPE new_item）; /*將new_item 加
到堆疊頂端 */
void pop（STACK_TYPE *stack, ITEM_TYPE *old_item）; /*將堆疊頂端資料
移出，並放在 old_item */
一開始，設定 stack -> top = -1；表示堆疊是空的。（註：符號 stack -> top 指到
堆疊頂端， stack -> item [stack -> top] 是堆疊頂端的資料）
三、
給予如下資料: 12, 8, 17, 4, 26, 6, 11, 請將這些資料建成一個二元搜尋樹（Binary
Search Tree）；如何利用此 binary search tree 來做資料之排序。（10 分）
有一個二元搜尋樹，其結構不清楚，節點的值為 1到10000，當搜尋“2013”的值
時，拜訪的節點值依序為：1396, 7248, k, 1523, 1865, 3152, 2013，請問 k值的範
圍為何？（10 分）
四、假設一生物 DNA 序列由 a, e, i, s, t, b, 和n基本單元所構成。已知某一微生物 DNA
序列之每一基本單元在此序列中出現之頻率如下：a, 10 次; e, 15 次; i, 12 次; s, 3 次;
t, 4 次; b, 13 次; n, 1 次。請設計一最佳編碼表編碼此序列，並計算出最小之編碼位
元數。（20 分）
102年公務人員升官等考試、102年關務人員升官等考試
102年交通事業郵政、港務、公路人員升資考試試題
代號：
26260
等別(級)： 薦任
類科(別)： 資訊處理
科 目： 資料結構
全一張
（
背面
）
五、給予如下之 Weighted Gr aph G：（每小題 10 分，共 20 分）
利用 Kruskal’s algorithm 來找最小擴張樹（Minimal spanning tree）。
在演算法中有一動作：選擇一最低成本的邊（edge），加入此邊（edge），如不
形成一迴圈（cycle），則加入此邊至最小擴張樹，請問運用何運算（operations）
或原理可完成此動作？