2004上半年软设上午试题第64、65类比二分搜索算法
●，设计k分搜索算法（k为大于2的整数）如下：首先检查n/k处（n为被搜索集合的元素个数）的元素是否等于要搜索的值，然后检查2n/k处的元素，…，这样，或者找到要搜索的元素，或者把集合缩小到原来的1/k；如果未找到要搜索的元素，则继续在得到的集合上进行k分搜索；如此进行，直到找到要搜索的元素或搜索失败。此k分搜索算法在最坏情况下搜索成功的时间复杂度为__(64)__，在最好情况下搜索失败的时间复杂度为__(65)__。
答案为 64C. O(logkn) 65C. O(logkn)
我觉得是64为klogkn,不过没这选项,呵呵
请指点一下以上两题
多谢！
问题点数：0、回复次数：7Top
1 楼metaphor（真流星蝴蝶剑）回复于 2004-11-03 10:11:09 得分 0
完全同意你的观点，当k＝n时，按照它的复杂度它就等于O(1)了，实际上是O（n），
它忽略了比较所用的步骤
Top
2 楼zzb1984（zzb）回复于 2004-11-05 08:01:26 得分 0
但是没对上答案,考试也没辙啊
还有人对解以上两题有其他看法吗？
Top
3 楼zzb1984（zzb）回复于 2004-11-05 18:28:39 得分 0
有人指点吗？
Right here waitingTop
4 楼zzb1984（zzb）回复于 2004-11-05 19:28:41 得分 0
我顶！！！！Top
5 楼IT_jht（软件架构师）回复于 2004-11-05 21:40:26 得分 0
这其实是对题目的理解问题,64问的意思是最坏情况下搜索成功的时间,情况最坏也就是说可能是倒序了,这样的情况下要查找成功必然要查找完整棵K叉树了,自然查找的时间就是这棵树的树高logkn了.65问的意思也是要找到整棵树所以也是lonkn.Top
6 楼liudaqin（&& || ! 路漫漫其修远兮）回复于 2004-11-05 22:33:18 得分 0
二分查找：查找成功时比较次数最多为[log2n]+1。
查找不成功时比较次数最多也为[log2n]+1 。
该题为K分查找，所以应为O(logkn)。
我认为应该分清二分查找和二叉排序。Top
7 楼J2EE99（）回复于 2004-12-01 17:44:44 得分 0
2004年11月软考试题分析
http://www.ciu.net.cn/Article_Show.asp?ArticleID=1532
CIU 2005精彩软考复习资料下载
http://www.ciu.net.cn/Article_Show.asp?ArticleID=1525
相关内容
http://www.ciu.net.cn/hzzx/kspx.htm
以考带学,始于证书,止于无限,CIU竭诚为广大考生服务!
Top
