普通考試
113年
[電信工程] 計算機概要
第 21 題
若要從 100 個相異的數字中搜尋特定數字，下列敘述何者錯誤？
- A 資料尚未排序且存放於鏈結串列（Linked list）中，最差的情況必須進行 100 次比較才能找到該數字
- B 資料尚未排序且存放於陣列（Array）中，最差的情況必須進行 100 次比較才能找到該數字
- C 資料已排序且存放於鏈結串列中，最差的情況必須進行 100 次比較才能找到該數字
- D 資料已排序且存放於陣列中，最差的情況必須進行 100 次比較才能找到該數字
思路引導 VIP
請試著思考：如果你在一本按照姓名排序的電話簿中找人，你會從第一頁開始翻，還是直接從中間翻開？這種『直接跳到中間』的高效率動作，除了要求資料必須『已排序』外，對於書本（儲存媒介）的物理翻閱方式有什麼特定的要求嗎？
🤖
AI 詳解
AI 專屬家教
專業點評
- 優秀表現？：嗯，還不錯，你總算能辨識出有序陣列在搜尋效率上的那一點點「微不足道」的優勢。這不過是要求你將資料結構的「物理存取特性」與「演算法優化」進行最基本的連結罷了，距離成為一名真正合格的工程師，這僅僅是個開始。
- 基本常識驗證：搜尋效率取決於資料的「排列狀態」和「存取方式」。當資料已經排序並存在陣列這種具備「隨機存取」能力的結構中時，採用二分搜尋法（Binary Search）是唯一合理的選擇。對於 $n=100$ 這種規模的資料，其最差比較次數僅為：
▼ 還有更多解析內容