有一个长度为n的有序顺序表,采用折半查找,经过i次比较成功找到的最多元素个数是______。
A. 2^i
B. 2^i+1
C. 2^(i-1)
D. 2^i-1
N诺智能批改可自动批改答案并给出反馈,每次使用将消耗 1个诺币
您当前的诺币数量: 个
N诺正在智能批改,预计需要30秒,请稍候...
经过 i 次比较成功找到元素,说明元素位于判定树的第 i 层(根节点为第1层)。
对于一棵二叉树(折半查找判定树是二叉树的一种特殊形式),第 i 层最多的节点数为 2^(i-1) 个(假设根节点在第1层)。
这意味着经过 i 次比较成功找到的元素最多有 2^(i-1) 个,因为这些元素对应着判定树第 i 层的节点,而第 i 层最多能容纳 2^(i-1) 个节点。
题目读着真别扭,应该为一个满二叉树的节点数
举例并不恰当,自己评估一下,应该是每次只能查到一个,怎么可能是2的幂次方呢?@admin
admin 回复 amden: 这个要仔细审一下题,题目的意思是最多能找到几个元素,可以看一下右上角解析,增加了一个推导过程
题目读着这么别扭,不能理解出题人想表达什么意思。
选项改一下吧
有一个长度为n的有序顺序表,采用折半查找,经过i次比较成功找到的最多元素个数是2^(i-1)。
C
(画图举例子既可以出来了...
登录后提交答案