阿摩線上測驗
登入
首頁
>
公職◆資料結構
> 102年 - 102年高考三級資料結構#44074
102年 - 102年高考三級資料結構#44074
科目：
公職◆資料結構 |
年份：
102年 |
選擇題數：
0 |
申論題數：
14
試卷資訊
所屬科目：
公職◆資料結構
選擇題 (0)
申論題 (14)
⑴請畫出完成資料輸入的二元搜尋樹。（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;
}
}
⑴加入資料 27。（6 分）
⑵加入資料 45。（6 分）
⑶加入資料 95。（6 分）
⑴請設計遞迴演算法，輸入非負整數 n，輸出 f (n)數值。（7 分）
⑵請設計非遞迴演算法，輸入非負整數 n，輸出 f (n)數值。（7 分）
⑶請分別說明⑴與⑵所設計演算法的時間複雜度（time complexity）。（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 分）
阿摩線上測驗
登入
阿摩線上測驗
登入