申論 1假設輸入的資料是：7341, 3123, 1673, 4919, 4304, 9179, 1369，使用的雜湊函數（hashfunction）是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 分）
本卷皆為申論題，點「看答案與解析」查看擬答。
弱點分析
未作答的題目不計分。看我的紀錄
申論 2本題是討論循序找尋（sequential search）方法。假設陣列一共有n 個元素，而循序找尋的演算法如下所示：ALGORITHM Sequential Search (A[0.. n-1], key)i ← 0while (i < n and A[i] ≠ key) doi ← i + 1endif i < n return ielse return −1㈠請寫出成功找尋的平均比較次數是多少？（5 分）㈡已知成功找尋的機率是p，請寫出成功與失敗的平均找尋次數是多少？（7 分）㈢若已知陣列中每一個元素的被讀取次數，例如：第一個元素被讀取5 次，第二個元素被讀取12 次，餘類推。請問如何可以減少成功找尋的平均比較次數？（8 分）
申論 3㈠給予一個串列資料：9, 5, 8, 12, 3, 10, 4, 7，請依序建造出2-3 樹（2-3 tree），並寫出建造的過程。（10 分）㈡若規定2-3 樹的高度（height）是從樹根（root）到樹葉（leaf）的最長路徑。請寫出一個高度為h 的2-3 樹，能夠儲存的最多資料數目是多少？能夠儲存的最少資料數目是多少？（10 分）類 科： 資訊處理科 目： 資料結構
申論 4快速排序法（Quick sort）是利用分割（Partitioning）技術，以遞迴方式做排序的一種高等排序方法。請回答下列的問題。㈠說明分割技術的一般做法。（10 分）㈡快速排序法的最壞情況（worst case）需要O (n2)的時間，有一種改進方法可避免發生最壞情況，請說明這個改進做法。（10 分）
申論 5一個鏈結串列使用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 = ____㈤______ ;}