阿摩線上測驗
登入
首頁
>
公職◆資料結構
> 109年 - 109 地方政府特種考試_三等_資訊處理：資料結構#94833
109年 - 109 地方政府特種考試_三等_資訊處理：資料結構#94833
科目：
公職◆資料結構 |
年份：
109年 |
選擇題數：
0 |
申論題數：
12
試卷資訊
所屬科目：
公職◆資料結構
選擇題 (0)
申論題 (12)
一、請設計演算法複製一棵二元樹（copy a binary tree）。
二、(一)請描述 order 為 m 的 B-tree 之特性。
⑴最多有幾個節點？最多有幾個 Key？
⑵最少有幾個節點？最少有幾個 Key？
三、請利用 Double Hashing 將下列 key 值放入 hash table of size 13中（如表 1）：
{24, 53, 17, 46, 14, 32, 37, 92}
h
1
(k)=k mod 13，h2(k)=1+(k mod 11)，
h(k,i)=(h1(k)+i*h
2
(k)) mod 13 (i=0, 1,…, 12)
⑴高度為6之 AVL tree 最多 可能有幾個 nodes？最少可能有幾個 nodes？（假設 root 之 h=0）
⑵假設此樹共有45個 nodes。請問此 AVL tree 可能最高之高度及最矮 之高度各為何？
(二)請將下列數字{17, 60, 24, 5, 7}逐步插入圖1的 AVL tree 中，並平衡之。
五、請利用堆積排序法（Heap Sort）將圖2逐步建立成 Min Heap，並將數字從小到大逐一列舉。
六、(一)請利用 KMP（Knuth, Morris, Pratt）演算法寫出失敗函數（failure function)之定義。
(二)找出 pattern “abcdabcabcdabcdabc”之失敗函數（failure function）值（請 填入表2 failure value 中）。
(三)假設(二)之 pattern 嘗試在 string “abcdabcabcdabcabcda…..”找出 pattern。 當 pattern 從 index 0開始比對到 index 13都一樣，而在 index 14時發現字母不一樣，請問 pattern 如何利用 failure function 所得之結果很快找 到下一個要對應之位置？也就是 pattern 的那一位置的值要位移到 string 的那一對應位置。
阿摩線上測驗
登入
