moea_joint_essay
106年
[資訊] 資訊管理、程式設計
第 二 題
📖 題組：
試以設計線上英文字典查詢的搜尋法為例，假設其資料分布均勻，請回答下列問題：（15 分） (一)常見之搜尋法中，哪一種最適合應用此搜尋，且搜尋時間最有效率（3 分）？並請說明此搜尋法的時間複雜度（3 分）。 (二)有一數列：15、1、3、100、50、44、58、46、27、38，如以 50 作為欲搜尋之鍵值，請以上述回答的搜尋法，依序列出於搜尋成功前，各次與鍵值比較的值為何。(未列出算式不計分)（9 分）
試以設計線上英文字典查詢的搜尋法為例，假設其資料分布均勻，請回答下列問題：（15 分） (一)常見之搜尋法中，哪一種最適合應用此搜尋，且搜尋時間最有效率（3 分）？並請說明此搜尋法的時間複雜度（3 分）。 (二)有一數列：15、1、3、100、50、44、58、46、27、38，如以 50 作為欲搜尋之鍵值，請以上述回答的搜尋法，依序列出於搜尋成功前，各次與鍵值比較的值為何。(未列出算式不計分)（9 分）
📝 此題為申論題，共 2 小題
小題 (二)
有一數列：15、1、3、100、50、44、58、46、27、38，如以 50 作為欲搜尋之鍵值，請以上述回答的搜尋法，依序列出於搜尋成功前，各次與鍵值比較的值為何。(未列出算式不計分)（9 分）
思路引導 VIP
使用內插搜尋法前需先將數列排序，然後依公式計算預測索引並比較。
小題 (一)
常見之搜尋法中，哪一種最適合應用此搜尋，且搜尋時間最有效率（3 分）？並請說明此搜尋法的時間複雜度（3 分）。
思路引導 VIP
已知資料分布均勻且用於字典查詢（已排序且可預估位置），應選擇內插搜尋法（Interpolation Search）。