首页 > 试题广场 >

题目来源于王道论坛 已知一个长度为16的顺序表L,其元

[单选题]
题目来源于王道论坛

已知一个长度为16的顺序表L,其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素,则关键字的比较次数最多的是()。

  • 4
  • 5
  • 6
  • 7
推荐

折半查找法在查找成功时进行的关键字比较次数最多为ëlog2 +1,即判定树的高度;折半查找法在查找不成功时进行的关键字比较次数最多为ëlog2 +1。题中n=16,因此最多比较ëlog216û +1=5次。也可以画出草图求解。

思考:若本题题干改为求最少的比较次数呢?

发表于 2018-09-03 20:29:44 回复(1)
一个长度为32的有序表,若采用二分查找一个不存在的元素,则比较次数最多是6
类似的题,答案却不一样,到底要不要加1
发表于 2019-01-28 23:40:10 回复(1)
16之后的空指针比较不算吗?
发表于 2018-11-13 23:17:23 回复(0)
PYQ头像 PYQ
在拥有16个元素的顺序表中,可将其编号为0~15,第一次比较的下标为7,而7将顺序表L分为两个长度不相等的子数组,选择更长的一边,则比较的次数就为5,否则为4。
发表于 2019-10-09 18:39:09 回复(0)
有歧义,要不要加一次比较
发表于 2019-03-09 12:53:49 回复(0)

比较16之后还要比较一次吧

发表于 2018-11-04 11:28:12 回复(0)