作者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