單元8 測驗/搜尋 返回
使用二元搜尋法的條件是?
  • A. 資料數量須為偶數筆
    4.8% (1)
  • B. 資料一定要以二元樹存放
    4.8% (1)
  • C. 資料中不能有中文資料
    14.3% (3)
  • D. 資料必須先經過排序處理
    71.4% (15)
  • 未填寫
    4.8% (1)
解說:
答案是 (D) 資料必須先經過排序處理。
解釋:
二元搜尋法(Binary Search) 是一種高效的搜尋方法,通常用於在有序數列中查找某個元素。它的基本思想是通過不斷將搜尋範圍縮小一半來快速定位元素。
關於條件:
(A) 資料數量須為偶數筆:這不是二元搜尋法的必要條件。二元搜尋法無論資料數量是偶數還是奇數,都能正常運作。只要資料是有序的,它都能在 O(log n) 的時間內完成搜尋。
(B) 資料一定要以二元樹存放:這也是不正確的。二元搜尋法並不要求資料必須儲存在二元樹中,儘管二元搜尋樹(Binary Search Tree)是一個使用二元搜尋法的資料結構,但普通的線性數列(如陣列或列表)也可以使用二元搜尋法,只要資料是有序的。
(C) 資料中不能有中文資料:這是錯誤的。二元搜尋法適用於任何資料類型,只要資料能夠進行比較,包括數字、字母、甚至中文字符。重要的是資料能夠被排序並能夠進行比較,無論是中文還是其他語言的資料。
(D) 資料必須先經過排序處理:這是正確的。二元搜尋法的前提是資料必須是已經排序好的,因為它的搜尋過程依賴於資料的順序。若資料未排序,則無法有效使用二元搜尋法。
結論:
因此,正確答案是 (D) 資料必須先經過排序處理,因為二元搜尋法只能在已排序的資料中有效地運行。
答對率 : 71.4 %
有關循序搜尋法的敘述何者錯誤?
  • A. 資料不必先排序
    23.8% (5)
  • B. 尋磁碟之資料通常利用此法
    57.1% (12)
  • C. 尋之時間複雜度為O(n)
    9.5% (2)
  • D. 搜尋資料時,採一筆一筆逐一比對
    4.8% (1)
  • 未填寫
    4.8% (1)
解說:
循序搜尋法(Sequential Search) 是一種簡單的搜尋方法,它的基本思想是從資料的第一個元素開始,逐一比對每個元素,直到找到目標元素或者檢查完整個資料集。
分析每個選項:
(A) 資料不必先排序:
正確。循序搜尋不要求資料先排序。它直接逐一比較資料中的元素,因此資料是否排序對於循序搜尋並不影響。
(B) 搜尋磁碟之資料通常利用此法:
錯誤。搜尋磁碟資料通常會使用更高效的搜尋方法,特別是基於磁碟的結構(如索引、B樹或Hashing等),這些方法能夠大大提高搜尋效能。循序搜尋法在這些情況下不常用,因為它的時間複雜度是 O(n),對於大量資料的搜尋效率較低。
(C) 搜尋之時間複雜度為 O(n):
正確。循序搜尋的時間複雜度是 O(n),因為在最壞的情況下,它需要檢查每一個元素,直到找到目標元素或遍歷完整個資料集。
(D) 搜尋資料時,採一筆一筆逐一比對:
正確。循序搜尋的基本步驟就是從資料的第一個元素開始,逐一比較每個元素,直到找到目標元素或遍歷完整個資料集。
結論:
因此,選項 (B) 是錯誤的,因為在磁碟資料搜尋中,通常會使用更高效的搜尋方法,並不是循序搜尋。
答對率 : 57.1 %
在二元搜尋樹進行搜尋時,單次搜尋時間與以下何者成正比?
  • A. 樹的節點總數
    0% (0)
  • B. 樹的高度
    81% (17)
  • C. 樹葉節點的個數
    4.8% (1)
  • D. 最大鍵值與最小鍵值的差
    9.5% (2)
  • 未填寫
    4.8% (1)
解說:
在 二元搜尋樹(Binary Search Tree) 中進行搜尋時,每次搜尋會根據當前節點的值與目標值進行比較,然後決定繼續向左子樹或右子樹進行搜尋。這樣的操作在搜尋過程中會沿著樹的分支走,直到找到目標節點或遍歷完整棵樹。
解析選項:
(A) 樹的節點總數:
單次搜尋時間與樹的節點總數無直接關係。即使樹中有更多的節點,如果樹的高度保持不變,搜尋時間不會改變。因此,這不是正確答案。
(B) 樹的高度:
正確。在最壞情況下,二元搜尋樹的搜尋時間與樹的高度成正比。樹的高度決定了搜尋時需要沿著樹走的步數,這也決定了搜尋所需的時間。最好的情況是樹是平衡的,這時搜尋的時間複雜度是 O(log n),其中 n 是節點數。最差情況下,搜尋的時間複雜度將是 O(n),這時高度等於節點總數。
(C) 樹葉節點的個數:
樹葉節點的數量與搜尋的時間並無直接關係。搜尋過程是根據樹的結構來進行的,與樹葉節點的數量無關。
(D) 最大鍵值與最小鍵值的差:
最大鍵值與最小鍵值的差並不直接影響搜尋時間。二元搜尋樹的搜尋時間與樹的結構(即高度)有關,而不是與樹中元素的鍵值差異有關。
結論:
因此,單次搜尋時間與 樹的高度 成正比,正確答案是 樹的高度。
答對率 : 81 %
若使用二元搜尋法,在數列(5、13、29、33、42)中尋找數字「33」,請問需做幾次的比較才能找到? 
  • A. 1次
    0% (0)
  • B. 2次
    52.4% (11)
  • C. 3次
    33.3% (7)
  • D. 4次
    9.5% (2)
  • 未填寫
    4.8% (1)
解說:
我們使用 二元搜尋法 在數列中尋找「33」。二元搜尋法的基本步驟是:
首先找出數列的中間元素,然後將其與目標值進行比較。
如果中間元素等於目標值,則搜尋結束。
如果目標值小於中間元素,則繼續在左半部分進行搜尋。
如果目標值大於中間元素,則繼續在右半部分進行搜尋。
給定數列:[5, 13, 29, 33, 42]
第一次比較:
中間元素是數列的中間值,這裡的中間元素是 29(索引位置為 2)。
比較目標值 33 與中間元素 29:
33 > 29,所以我們接著搜尋右半部:[33, 42]。
第二次比較:
右半部分的中間元素是 33(索引位置為 3)。
比較目標值 33 與中間元素 33:
發現目標值 33 等於中間元素,搜尋結束。
結論:
在這個過程中,我們總共進行了 2次比較,因此正確答案是  2次。
答對率 : 52.4 %
某雜湊表(hash table)有七個空格可供存放數目。假設雜湊函數(hash function)為 h(k)=k mod 7,其中 k mod 7為 k除以 7的餘數。若產生碰撞(collision),則採用線性探測法( linear probing)依序往下尋找空格存放。依此方法,將 50,12,35,24,40,73,69等七個數目依序存入後,雜湊表內的數目順序為何? 
  • A. 50,12,35,24,40,73,69
    14.3% (3)
  • B. 35,50,69,24,73,12,40
    52.4% (11)
  • C. 12,24,35,40,50,69,73
    19% (4)
  • D. 73,69,50,40,35,24,12
    9.5% (2)
  • 未填寫
    4.8% (1)
解說:
解這個問題,我們需要一步一步地將每個數字根據給定的雜湊函數和線性探測法存入雜湊表。
問題條件:
雜湊表有 7 個空格(大小為 7)。
雜湊函數是 h(k)=kmod7,即取數字除以 7 的餘數。
如果發生碰撞,則使用線性探測法,依序向下尋找空格。
計算過程:
我們依照數字順序依次計算並插入每個數字。
1. 插入 50:h(50)=50mod7=1
位置 1 是空的,將 50 存入位置 1。
2. 插入 12:h(12)=12mod7=5
位置 5 是空的,將 12 存入位置 5。
3. 插入 35:h(35)=35mod7=0
位置 0 是空的,將 35 存入位置 0。
4. 插入 24:h(24)=24mod7=3
位置 3 是空的,將 24 存入位置 3。
5. 插入 40:h(40)=40mod7=5
位置 5 已經被 12 占據,發生碰撞。使用線性探測法,往下尋找空格。
位置 6 是空的,將 40 存入位置 6。
6. 插入 73:h(73)=73mod7=3
位置 3 已經被 24 占據,發生碰撞。使用線性探測法,往下尋找空格。
位置 4 是空的,將 73 存入位置 4。
7. 插入 69:h(69)=69mod7=6
位置 6 已經被 40 占據,發生碰撞。使用線性探測法,往下尋找空格。
位置 7 超過了表格的最大索引,因此回到位置 0,再往下探測。
位置 1 已經被 50 占據,位置 2 是空的,將 69 存入位置 2。
最終結果:
依照順序插入後,雜湊表內的數字排列為:
位置 0: 35
位置 1: 50
位置 2: 69
位置 3: 24
位置 4: 73
位置 5: 12
位置 6: 40
因此,雜湊表內的數字順序是 35, 50, 69, 24, 73, 12, 40。
正確答案:
(B) 35,50,69,24,73,12,40
答對率 : 52.4 %
下載答題分析