加載中. ..
PDF
110 年特種考試地方政府公務人員考試試題
等 別
：
三等考試
類 科
：
資訊處理
科 目
：
資料結構
考試時間
：
2
小時
座號
：
※注意：禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號：
34280
頁次：
3
－
1
A
B
G
C
F
D
E
H
K
一、請分別寫出下圖二元樹的前序走訪法（preorder traversal）、中序走訪法
（inorder traversal）、後序走訪法（postorder traversal）的結果（6分）
請在無法預知二元樹的節點數條件下，設計在程式中表示二元樹的資
料結構。再假設二元樹已依前述結構儲存在程式，設計一副程式（或
函式）的演算法，在提供樹根給此副程式（或函式）後，其執行二元
樹中序走訪法的程序並輸出走訪結果。此副程式（或函式）不可使用
遞迴呼叫技術但可添加其他資料結構，演算法的時間複雜度和空間複
雜度須均為 O(n)，n為二元樹的節點個數。演算法可以虛擬碼（pseudo-
code）或以高階語言如 C呈現。需分析說明副程式（或函式）演算法
的時間複雜度和空間複雜度均為 O(n)。（提醒：若用遞迴呼叫技術設
計，演算法部分不給分）（13 分）
請分別說明在程式執行過程，以第子題非遞迴呼叫技術設計相較於
以遞迴呼叫技術設計在時間與空間的效能優勢各為何？（6分）
代號：
3
4280
頁次：
3
－
2
二、二維方陣 A大小為 nn，方陣中的元素除了主對角線之元素以及緊鄰它的
上下兩條對角線之元素的值可能不為零外，方陣 A其他元素之值一定為
零，以 55方陣為例如下圖。請以一維陣列 B設計儲存此方陣 A之結構，
陣列 B之索引值自 0開始，且陣列 B的元素數量須小於或等於 3n-2。設
計的結構須包含如何有效率地決定儲存方陣 A之元素 aij 以及如何自陣
列B中取得或決定方陣中元素 aij 值，其中 0 i, jn-1 而i與j分別為元
素在方陣 A中之列號與行號。（20 分）
00 01
10 11 12
21 22 23
32 33 34
43 44
0 0 0
0 0
0 0
0 0
0 0 0
a a
a a a
a a a
a a a
a a
三、請畫出下圖以鏈結串列（link list）為基礎的相鄰串列（adjacency list）
結構表示之結果。（5分）
請運用一維陣列設計一資料結構採循序串列（sequential list）架構，其
仍舊以類似子題相鄰串列策略表示無向圖（undirected graph）節點
與邊的關係，但僅以一維陣列呈現第子題之相鄰串列概念。圖之節
點與邊的關係僅以此一維陣列元素記錄並呈現，不可使用其他資料結
構，另外，陣列中亦需記錄此陣列中用來記錄與圖相關資訊之元素個
數；除了說明資料結構外，也請寫出下圖以此資料結構表示之一維陣
列結果。（8分）
請列出兩項在程式中以第子題之以鏈結串列（link list）表示圖比以
第子題一維陣列表示圖適合的應用情境或效能優勢。另外，也請列
出兩項在程式中以第子題一維陣列表示圖比以第子題鏈結串列
（link list）表示圖適合的應用情境或效能優勢。（12 分）
0
1
2
3
4
代號：
3
4280
頁次：
3
－
3
四、區間堆積（interval heap）是一種優先佇列（priority queue），請回答下列
相關的問題。
從一個沒有元素的區間堆積開始，依序插入 40, 30, 60, 15, 14, 19, 80,
12, 90 等元素。請畫出最後區間堆積的樹狀結構圖。（9分）
請自第子題建構的區間堆積中刪除元素 12，並畫出刪除該元素後區
間堆積的樹狀結構圖。（3分）
請以一維陣列設計資料結構儲存區間堆積，該資料結構可以透過節點
對應之陣列索引值 index 構成的數學式計算出其父節點 parent、左子
節點 left、右子節點 right 與兄弟節點 brother 等在陣列中的索引值。假
設此一維陣列之起始索引值為 0，請列出由 index 構成的計算 parent、
left、right、brother 的數學式。並請畫出以此一維陣列儲存第子題建
構完成的區間堆積的結果。（12 分）
舉例並說明一既需要提供最高優先元素，也需要提供最低優先元素的
優先佇列的應用實例或系統。（6分）