加載中. ..
PDF
108
年公務、關務人員升官等考試、
108
年交通
事業郵政、公路、港務人員升資考試試題
等 級：薦任
類科（別）：資訊處理
科 目：資料結構
考試時間 ：2小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號：
2
6260
頁次：
2
－
1
一、一般常用的算術運算式（Arithmetic Expression）有：中序運算式（Infix
Expression）、前序運算式（Prefix Expression）、後序運算式（Postfix
Expression）三種表示法，請回答下列問題：
考慮中序運算式
7
4
)
3
/
9
5
(
)
2
6
(
×
+
+
×
−
，請說明其前序與後序運算式
分別為何？（8分）
請說明為何中序運算式需要使用括號來輔助界定運算元的優先順序
而前序與後序運算式則無需括號？（7分）
請說明如何利用一個堆疊（Stack）結構計算出一個後序運算式的值，
並以後序運算式 a b ×c+d c /−為例，其中 a= 3, b= 5, c= 2, d= 6，
請逐步列出運算過程中堆疊的內容。（10 分）
二、以下是關於二元搜尋樹（Binary Search Tree）的問題：
請說明二元搜尋樹的定義？（5分）
是否可以使用一個二元搜尋樹對鍵值（Key）來進行排序（Sorting）？
如果不行，請解釋其原因。若可以，請描述作法及執行時間。（5分）
AVL 樹是一個基於二元搜尋樹的資料結構，請敘述 AVL 樹的定義
並說明為何一個有 n個節點（鍵值）的 AVL 樹其高度是 O（log n）。
（5分）
若將鍵值 36、25、14、27、55、30 以依序加入的方式建構一個 AVL
樹，請繪出每次加入後的 AVL 樹。（10 分）
三、優先佇列（
Priority Queue
提供的功能有：加入
（
有最高優先權的資料物件
有越高的優先權，
加入與移除功能分別命名為
請說明
如何利用優先佇列將資料物件以鍵值進行排序
二元堆積（
Binary Heap
定義。（6分）
若我們分別使用排序串列
二元堆積三種資料結構來實現有
三種方式在加入
insert
度。（6分）
在考慮鍵值低的資料物件有高的優先權的情況下
稱為最小堆積（
Minimum Heap
請說明如何輸出所有鍵值小於或等於
運算量）
與鍵值小於或等於
四、一個圖形結構（
Graph
一個有向圖（
Directed Graph
一個有向圖不具有迴圈
Acyclic Graph,
DAG
種不同的拓樸排序
（
若在圖 G
上由節點
請列出此一拓樸
排序並說明方法與所
一個有向圖若具有強連通性
點u與v
彼此可藉由不同路徑相互連通
否具強連通性的方法
a
d
g
Priority Queue
）
用來管理具有優先權順序的資料物件
（
Insert）任意資料物件，
以及移除
有最高優先權的資料物件
。我們在此假設鍵值（K
ey
加入與移除功能分別命名為
insert
()
如何利用優先佇列將資料物件以鍵值進行排序
Binary Heap
）
是一個實現優先佇列的資料結構
若我們分別使用排序串列
（Sorted List）、
未排序串列
二元堆積三種資料結構來實現有
n
個資料物件的優先佇列
insert
()與移除 remove_Min()
功能上所
在考慮鍵值低的資料物件有高的優先權的情況下
，
Minimum Heap
）。
若給定一個最小堆積與一個鍵值
請說明如何輸出所有鍵值小於或等於
k
的資料物件
，
與鍵值小於或等於
k
的資料物件之數量成線性比例
Graph
）中，
若所有的邊都具有方向
Directed Graph
）。
一個有向圖不具有迴圈
（Cycle）
則稱為一個有向非循環圖
DAG
），考慮下方的有向非循環圖
G
（
Topological Sort）？（7分）
上由節點
c開始進行拓樸排序，
並考慮字母順序進行排列
排序並說明方法與所
需
要的時間複雜度
一個有向圖若具有強連通性
（Strong Connectivity
）
彼此可藉由不同路徑相互連通
。
請提供一個驗證一有向圖是
否具強連通性的方法
，
並說明其正確性與時間複雜度
有向非循環圖
G
b
c
e
f
h
i
j
代號：
26260
頁次：
2
－
2
用來管理具有優先權順序的資料物件
，主要
以及移除
（Remove）具
ey
）越低的資料物件
()
及remove_Min()。
如何利用優先佇列將資料物件以鍵值進行排序
。（5分）
是一個實現優先佇列的資料結構
，請敘述其
未排序串列
（Unsorted List）、
個資料物件的優先佇列
，請比較這
功能上所
需的時間複雜
，
所使用的二元堆積
若給定一個最小堆積與一個鍵值
k，
的資料物件
，
而所花的時間（或
的資料物件之數量成線性比例
。（8分）
若所有的邊都具有方向
，則此圖形結構為
則稱為一個有向非循環圖
（Directed
G
，請說明 G共有幾
並考慮字母順序進行排列
，
要的時間複雜度
。（8分）
）
，則其中任意兩節
請提供一個驗證一有向圖是
並說明其正確性與時間複雜度
。（10 分）