作者kiss99099 (kkk)
站內Examination
標題[考題] 100年中華電信計算機概論
時間Wed Mar 5 15:58:41 2014
[考題] 國考歷屆考題與考題觀念討論(書裡看到的選這個)請附上想法、出處
主要都是二元搜尋法的次數概念,
題目如下:
1).某一數列有1207筆資料,且資料已經排序,用2元搜尋法
於數列中找尋目標資料時,請問最多比對資料幾次 可以
得知結果?
a.10次 b.11次 c.12次 d.13次 答案是11次
從題目上可以判斷 搜尋的目標資料可能不一定在數列中
,所以答案是 log2的1027 取整數10 再加上1次比對
目標資料是否存在的意思麼?(也就是10+1 = 11次)
有一個很類似的題目 可以拿來做參考
93年身心4等
有8個資料已經排序好,並進行2元搜尋,
假設資料確定存在其中,則需要經過幾次比對
才能尋獲?
a.2次 b.3次 c.4次 d.8次 答案卻為b 也就是3次
而這個題目 我的想法是 最多應該要比對4次
,來能確定找到資料,而因為題目因為有提示資料確定存在
,所以在比對到第3次時,如果還找不到 就不用再比了
目標資料一定是剩餘的那個未比較的
兩個題目的差異,想問問版上的大大 ,小弟的想法正不正確
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.172.124.82
1F:推 qaz5620:1. 2的10次1024還不夠1207要2的11次才夠 03/05 16:10
2F:→ qaz5620:2. 2的3次剛好為8 所以3次就夠了 03/05 16:11
3F:推 Mewra:兩個答案都沒問題,其實可以試著建一個8節點的bst,然後隨便 03/05 16:19
4F:→ Mewra:丟個值進去試試 03/05 16:20