2. 考研
  3. 用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

admin2019-07-18  60
问题 用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为(          )。
选项 A、 
B、 
C、 
D、 
答案D
解析 根据折半查找的过程，由于需要栈结构实现递归算法，栈的容量应该保证能存放查找失败时所有未完成运行的算法的活动记录。
    第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为n；
    第二次调用时，无论是在前半区还是后半区查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／2；第三次调用时，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／4；依次类推，当所确定的查找区间中的元素为0时，递归调用该算法的次数为Llog2n」+1次，查找结束。
转载请注明原文地址:https://kaotiyun.com/show/WRCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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