102年公務人員高等考試三級考試試題 代號：36250 全一張
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：______________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、將整數資料80, 40, 19, 120, 94, 110, 115, 90, 88, 92, 98 依序存入一棵空的二元搜尋樹 (binary search tree)。
(一)請畫出完成資料輸入的二元搜尋樹。（6分）
(二)從(一)產生的二元搜尋樹中刪除 (delete) 資料94，請畫出完成刪除動作後的二元搜尋樹。（給出一個正確樹即可）（6分）
(三)請寫出自二元搜尋樹找到最大值資料所在節點 (node) 的演算法。（10分）
二、請寫出執行下列程式碼的時間複雜度，並敘明理由。（10分）
for (i = 1; i < n; i++){
a = 1;
b = n;
while( a < b ){
a = 3 * a;
b = b / 3;
}
}
三、下圖為一 AVL 樹 T，請依各小題要求加入指定新資料後，畫出新產生的AVL 樹。每小題各自獨立，都是對原先的 AVL 樹 T，加入資料。
(一)加入資料27。（6分）
(二)加入資料45。（6分）
(三)加入資料95。（6分）
四、函數 f(n) 定義如下，其中 n 為非負整數。
(一)請設計遞迴演算法，輸入非負整數n，輸出 f(n) 數值。（7 分）
(二)請設計非遞迴演算法，輸入非負整數n，輸出 f(n) 數值。（7 分）
(三)請分別說明(一)與(二)所設計演算法的時間複雜度 (time complexit)。（10分）
五、(一)依據下圖內容，請寫出它的相鄰矩陣 (adjacency matrix) 表示法。（4分）
(二)請定義生成樹 (spanning tree)。（6分）
(三)請畫出此圖的最小成本生成樹 (minimum cost spanning tree)，以及計算最小成本。（10分）
六、有一雜湊表格 (hash table) T 的記憶空間共含11 個桶 (buckets)，位址編號由0至10，每個桶有一個槽 (slot)。雜湊函數 h1 定義為 h1(key) = key % 11，當有碰撞 (collision) 發生時採二次雜湊開放定址法 (open addressing with double hashing) 處理，其函數定義為 h(key, j) = (h1(key)+j*h2(key))% 11，其中 j 為碰撞次數，j = 1, 2, 3, ..., 11，h2(key) = 1+(key%10)。欲將26放入雜湊表格 T，總共經過6次探測才成功找到存放位址。請問26在雜湊表格 T 的探測順序為何？（6分）
留言列表
國考資訊處理解答 (7)
