資訊處理 95 年資料結構考古題

請給予適當之變數型式（type）與宣告（declaration）以建立一個可儲存整數項目的 鏈結表列（linked list）（10 分）。利用前述之變數型式與宣告，請由下列之程式片 斷繪出其結果（20 分）。 new（p）； head：= p； p↑.data：= 1； for I：= 2 to 5 do Begin new（Q）； p↑.next：= Q； Q↑.data：= I； p：= p↑.next eEnd； p↑.next：= nil；

試利用深度優先搜尋（Depth First Search）及廣度優先搜尋（Breadth First Search）求出下圖的擴展樹（Spanning Tree），並分別列出各節點之優先搜尋順序。 （20 分）

假設輸入的資料是：7341, 3123, 1673, 4919, 4304, 9179, 1369，使用的雜湊函數（hash function）是f (x) =x mod 10，x 是輸入的資料，而雜湊表格（hash table）的大小有10 個位置，編號從0 到9，每一位置只能儲存一筆資料。請分別回答下列的問題： 上述資料經由雜湊函數後，寫出雜湊表格的內容（含溢位資料）。（4 分） 當溢位處理方法（overflow handling method）使用線性探測（linear probing）時， 請寫出雜湊表格的內容。（4 分） 當溢位處理方法使用平方探測（quadratic probing）時，計算過程為f (x) ± i2 mod 10， 請寫出雜湊表格的內容。（5 分） 當溢位處理方法使用雙重雜湊（double hashing）時，第二個雜湊函數是 g(x)=7–（x mod 7），請寫出雜湊表格的內容。（7 分）

請將下列中置法（infix）之表示式變更為後置法（postfix）之表示式，並條列說明 其過程。（15 分） 3 ＋ 7 ＊ 8 － 5 （3 ＋ 7）＊ 8 － 5 A － B ＊（C － D）÷ E

試寫出下列各種演算法的每一個階段（phase）之後，串列L={12, 2, 16, 30, 8, 28, 4, 10, 20, 6, 18}的狀態。（20 分） Insertion Sort Quick Sort Merge Sort Heap Sort

本題是討論循序找尋（sequential search）方法。假設陣列一共有n 個元素，而循序 找尋的演算法如下所示： ALGORITHM Sequential Search (A[0.. n-1], key) i ← 0 while (i < n and A[i] ≠ key) do i ← i + 1 end if i < n return i else return −1 請寫出成功找尋的平均比較次數是多少？（5 分） 已知成功找尋的機率是p，請寫出成功與失敗的平均找尋次數是多少？（7 分） 若已知陣列中每一個元素的被讀取次數，例如：第一個元素被讀取5 次，第二個元 素被讀取12 次，餘類推。請問如何可以減少成功找尋的平均比較次數？（8 分）

請繪一前序遊歷（preorder traversal）之樹狀圖以表示下列之前置（prefix）表示式。 （15 分） ＊ ＋ 25 ＋ 36 95 年公務人員特種考試關務人員考試試題 科 別： 資訊處理 全一張 （背面）

考慮n 個頂點之完整圖形，試證明：二個頂點間，路徑的數目最多為(n-1)!。（20 分）

給予一個串列資料：9, 5, 8, 12, 3, 10, 4, 7，請依序建造出2-3 樹（2-3 tree），並 寫出建造的過程。（10 分） 若規定2-3 樹的高度（height）是從樹根（root）到樹葉（leaf）的最長路徑。請寫 出一個高度為h 的2-3 樹，能夠儲存的最多資料數目是多少？能夠儲存的最少資料 數目是多少？（10 分） 95 年公務人員高等考試三級考試試題 類 科： 資訊處理 全一張 （背面）

請繪一圖以說明下列之程式片斷儲存之結果。（20 分） rewrite（file1）； for I：= 1 to 5 do begin if I mod 2：= 0 then file1↑：= 1 else file1↑：= I； ﹛end if﹜ put（file1） end；﹛for﹜

請說明以下四種搜尋（Search）方法的基本原理，並分別評估其效果。（20 分） 循序搜尋法（Sequential search） 二元搜尋法（Binary search） 內插搜尋法（Interpolation search） 費氏搜尋法（Fibonacci search）

快速排序法（Quick sort）是利用分割（Partitioning）技術，以遞迴方式做排序的一 種高等排序方法。請回答下列的問題。 說明分割技術的一般做法。（10 分） 快速排序法的最壞情況（worst case）需要O (n2)的時間，有一種改進方法可避免 發生最壞情況，請說明這個改進做法。（10 分）

解釋下列名詞：（20 分） 靜態資料結構（static data structure） 主記憶體（main memory） 堆疊（stack） 儲列（queue）

何謂Hashing？（5 分）它常用在那些地方？（5 分）使用Hashing 常會產生Collision （碰撞），何謂Collision？（5 分）試說明解決Collision 常用的循序法（Linear Method）。（5 分） V 1 V 2 V 3 V 4 V 5 V

一個鏈結串列使用C 語言宣告如下： typedef struct node{ int data; struct node *next; }NODE; NODE *new, *back, *pointer, *forward; 假設現在已經產生一個名叫new 的鏈結串列共有n 個節點，已知指標back 是指向 串列中間的某一個節點，而指標pointer 是指向back 的下一個節點。在下列的問題 中指令～分別為何？（每小題4 分，共20 分） 問題一：刪除pointer 所指向的節點。 ____________ = pointer -> next; free (pointer) ; 問題二：欲將pointer 所指向節點的指標做反轉（reverse），指向前一個節點，此迴 路 (loop)可逐漸完成整個串列的反轉。 while (pointer -> next ! = NULL) { forward = _____________ ; pointer -> next = _________ ; _________ = pointer; pointer = __________ ; }

V

V