加載中. ..
PDF
106年特種考試地方政府公務人員考試試題 代號：33680 全一張
（正面）
等別： 三等考試
類科： 資訊處理
科目： 資料結構
考試時間 ： 2 小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
（請接背面）
一、給定一個以一維陣列 A[i]所表示的二元樹（binary tree）如下：（每小題 5分，共 30 分）
i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A[i] T S U B O G P X
請問該樹樹高為何？
請列舉該樹所有葉節點（leaf node）。
A[i]所代表的節點之左子節點（left-child node）應在陣列 A[.]的那一個位置？請寫
出公式。
請寫出該樹之後序遍歷（Postorder T raversal ）結果。
請寫出該樹之前序遍歷（Preorder Traversal）結果。
請寫出該樹之中序遍歷（Inorder Traversal）結果。
二、下表列出四種常見的資料結構，請填滿該表以顯示各資料結構在一般狀況下（average
case），搜尋（search）、插入（insertion）、刪除（deletion）資料之時間複雜度。陣列
的各項資料已事先填入作為範例。（每小題 5分，共 20 分）
搜尋
（search） 插入
（insertion）刪除
（deletion）
陣列 O(n) O(n) O(n)
佇列（queue）
雙向連結串列（doubly-linked list）
二元搜尋樹（binary search tree）
AVL樹（AVL tree）
106年特種考試地方政府公務人員考試試題 代號：33680 全一張
（背面）
等別： 三等考試
類科： 資訊處理
科目： 資料結構
三、給定如下圖所示之兩個環狀單向鏈結串列（circular singly linked list），並以 A，B分
別指向其中兩個串列中的一個節點，另有一個指標 C可以使用。請用類 C之虛擬語
言（C-like pseudo code）完成下列動作。
請用至多二行虛擬碼程式刪除 C所指向節點。結果必須維持環狀單向鏈結串列。（5分）
請用至多二行虛擬碼程式將 B所指向串列插入 A所指向串列。結果必須維持環狀
單向鏈結串列。（10 分）
請用至多四行虛擬碼程式寫出可將 B所指向節點插入至 A所指向節點之「前」，但
必須維持環狀單向鏈結串列。（15 分）
四、給定下列數列，若以快速排序法（Quick Sort）、選擇排序法（Selection Sort）、堆積
排序法（Heap Sort）、泡沫排序法（Bubble Sort）進行排序。請問下列數列是那一個
排序法排序過程的暫時結果，並說明之。（每小題 5分，共 20 分）
75 93 32 81 75 89 89 99 25 78 54 75 87 12 75 28
99 93 89 81 78 87 89 75 25 75 54 75 32 12 75 28
25 28 32 75 12 75 54 75 99 78 89 89 87 75 81 93
12 25 28 32 54 75 75 75 75 78 81 87 89 99 93 89
32 75 75 81 89 25 78 54 75 87 12 75 28 89 93 99
link link link
A
link
. . .
link link link
B
link
. . .
C