2. 计算机
  3. 用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为(11)。

用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为(11)。

admin2013-05-11  6
问题 用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为(11)。
选项 A、n
B、[n/2]
C、[log2n]
D、[log2(n+1)]
答案D
解析 根据二分查找的过程，由于需要栈结构实现递归算法，栈的容量应该要保证能存放查找失败时所有未完成运行的算法的活动记录。第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为n：第二次调用时，无论是在前半区还是在后半区进行查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n/2：第三次调用时，栈中又加入了—条查找记录，所确定的查找区间中的元素最多为n/4。依次类推，当所确定的查找区间中的元素为。时，递归调用该算法的次数为log2(n+1)次，查找结束。
转载请注明原文地址:https://kaotiyun.com/show/N9RZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)