早教吧考试题库频道 --> 计算机类考试 -->软考中级 -->
用递归算法实现n个相异元素构成的有序序列的二分查找,采用一个递归工作栈时,该栈的最小容量应为(
题目
用递归算法实现n个相异元素构成的有序序列的二分查找,采用一个递归工作栈时,该栈的最小容量应为(11)。
A.n
B.[n/2]
C.[log2n]
D.[log2(n+1)]
参考答案
正确答案:D
解析:根据二分查找的过程,由于需要栈结构实现递归算法,栈的容量应该要保证能存放查找失败时所有未完成运行的算法的活动记录。第一次调用该算法时,栈中加入了一条查找记录,表示待查有序表中元素的个数为n:第二次调用时,无论是在前半区还是在后半区进行查找,栈中又加入了一条查找记录,所确定的查找区间中的元素最多为n/2:第三次调用时,栈中又加入了—条查找记录,所确定的查找区间中的元素最多为n/4。依次类推,当所确定的查找区间中的元素为。时,递归调用该算法的次数为log2(n+1)次,查找结束。
解析:根据二分查找的过程,由于需要栈结构实现递归算法,栈的容量应该要保证能存放查找失败时所有未完成运行的算法的活动记录。第一次调用该算法时,栈中加入了一条查找记录,表示待查有序表中元素的个数为n:第二次调用时,无论是在前半区还是在后半区进行查找,栈中又加入了一条查找记录,所确定的查找区间中的元素最多为n/2:第三次调用时,栈中又加入了—条查找记录,所确定的查找区间中的元素最多为n/4。依次类推,当所确定的查找区间中的元素为。时,递归调用该算法的次数为log2(n+1)次,查找结束。
看了用递归算法实现n个相异元素构成...的网友还看了以下:
怀孕多久可以做b超?怀孕初期b超检查的最佳时间 怀孕 2020-03-29 …
孕前检查的最佳时间是什么时候? 怀孕 2020-03-29 …
恶劣(lie)应该是第几声,我在家查的字典是第四声,并且是唯一的一个音,但我孩子的老师说,查的最新 其他 2020-05-15 …
初步调查是可行性分析的第一步。一般来说,初步调查的最佳方式为( )。 A.收集统计报表 B. 计算机类考试 2020-05-23 …
37 】.关于信息系统开发初步调查的下列描述错误的是A .初步调查的最佳方式是与企业高层主管座谈B 计算机类考试 2020-05-23 …
初步调查是可行性分析的第一步。一般来说,初步调查的最佳方式为A.收集统计报表B.发调查表C.与企业 计算机类考试 2020-05-23 …
初步调查的最佳方式是()。A.首先与企业的高层主管座谈,确定系统目标、系统边界、资金投入、工期要求 计算机类考试 2020-05-24 …
关于信息系统开发初步调查的下列描述,错误的是A.初步调查的最佳方式是与企业高层主管座谈B.初步 计算机类考试 2020-05-24 …
初步调查是可行性分析的第一步。一般来说,初步调查的最佳方式为()。A.收集统计报表B.发调查表C.与 计算机类考试 2020-05-24 …
材料一:中国官方7月29日公布消息,周永康“涉嫌严重违纪”被立案审查.周永康是前中央政治局常委,前 政治 2020-06-22 …