阿摩線上測驗 登入

96年 - 096年升官等 薦任升官等-技術類資料結構#50809

科目：公職◆資料結構 | 年份：96年 | 選擇題數：0 | 申論題數：14

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (14)

⑴請簡要描述二元搜尋法的原理。（5 分）
⑵設 f (n) 為二元搜尋法的執行時間，請分析 f (n) 和 n 的關係。提示：設 n=2k， 且每次搜尋的資料筆數為前次的一半。（15 分）
⑴將一筆新的資料 40 存入 A 中，其位置介於資料 10 和 50 之間。請畫出存入 40 後 的狀態。（5 分）
⑵承上題⑴，將 10 從 A 中刪除，請畫出刪除後的狀態。（5 分）
⑶承上題⑵，將 60 存入 A 中，使其成為第一筆資料，請畫出存入後的狀態。（5 分）
⑷承上題⑶，請畫出將 50 刪除後的狀態。（5 分）
⑴現有一數 X，其值大於 B 但小於 H，將 X 加入此樹，請畫出加入後的二元搜尋樹。 （5 分）
⑵承上題⑴，今欲將 A 刪除，請畫出刪除後的二元搜尋樹。注意：我們規定一個數 被刪除後，會被其左子樹（left subtree）的最大數取代。（5 分）
⑶承上題⑵，請寫出此二元樹的中序追蹤（inorder traversal）為何？（5 分）
⑷承上題⑵，請寫出此二元樹的後序追蹤（postorder traversal）為何？（5 分）
⑴假設有 8 個整數：95、55、70、90、30、65、80、85，依序存入 A[1]至 A[8]中。 利用父母－子女（parents-children）節點交換的方式，將此 8 個整數所形成的完 全二元樹轉化為一個最小堆積（min-heap），並列出 A[1]到 A[8]的值。（15 分）
⑵承上題⑴，將最小整數 30 刪除，並將 A[8]放入 A[1]中，利用父母－子女節點交換 的方式，將 A[1]至 A[7]調整成一個最小堆積，並列出 A[1]到 A[7]的值。（5 分）
⑴請將上述資料建成一棵 3 次的 B－樹（B-tree of order 3）。（15 分）
⑵承上題⑴，將 70 從此樹刪除，請畫出刪除後的 B－樹。假設一個數被刪除後， 會被其右子樹（right subtree）的最小數取代。（5 分）