用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为()。
题目
相似考题
更多“用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为()。 ”相关问题
-
第1题：
使用二分查找算法在一个有序序列中查找一个元素的时间复杂度为()
A.O(N)
B.O(logN)
C.O(N*N)
D.O(N*logN)
正确答案：B
-
第2题：
将一个递归算法改为对应的非递归算法时，通常需要使用(44)。
A．优先队列
B．队列
C．循环队列
D．栈
正确答案：D
解析：将一个递归算法改为对应的非递归算法时，通常需要使用的数据结构是栈。 -
第3题：
用C语言写一个递归算法求N！；（华为面试题）
正确答案：
-
第4题：
● 对 n 个元素的有序表 A[1..n]进行二分（折半）查找，则成功查找到表中的任意一个元素时，最多与A 中的 （39） 个元素进行比较。
（39）
正确答案：D
-
第5题：
第四题 阅读以下说明、C函数和问题，回答问题1和问题2将解答填入答题纸的对应栏内。
【说明】
当数组中的元素已经排列有序时，可以采用折半查找（二分查找）法查找一个元素。下面的函数biSearch(int r[]，int low，int high，int key)用非递归方式在数组r中进行二分查找，函数biSearch_rec(int r[]，int low，int high，int key)采用递归方式在数组r中进行二分查找，函数的返回值都为所找到元素的下标；若找不到，则返回-1。
【C函数1】
int biSearch(int r[]，int low，int high，int key)
//r[low..high] 中的元素按非递减顺序排列
//用二分查找法在数组r中查找与key相同的元素
//若找到则返回该元素在数组r的下标，否则返回-1
{
int mid;
while(（1）) {
mid = (low+high)/2 ;
if (key ==r[mid])
return mid;
else if (key
else
（3）;
}/*while*/
return -1;
}/*biSearch*/
【C 函数 2】
int biSearch_rec(int r[]，int low，int high，int key)
//r[low..high]中的元素按非递减顺序排列
//用二分查找法在数组r中查找与key相同的元素
//若找到则返回该元素在数组r的下标，否则返回-1
{
int mid;
if(（4）) {
mid = (low+high)/2 ;
if (key ==r[mid])
return mid;
else if (key
else
return biSearch_rec(（6）,key);
}/*if*/
return -1;
}/*biSearch_rec*/ 问题：4.1 (12分）
请填充C函数1和C函数2中的空缺，将解答填入答题纸的对应栏内。 问题：4.2 (3分）
若有序数组中有n个元素，采用二分查找法查找一个元素时，最多与（ ）个数组元素进行比较，即可确定查找结果。
（7）备选答案：
A.[log2(n+1)] B.[n/2] C.n-1 D.n答案：解析：low<=high
（2）high=mid-1
（3）low=mid+1
（4）low<=high
（5）low,mid-1
（6）mid+1,high
（7）A
【解析】
本题考察折半查找。二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好，占用系统内存较少；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x
总共有n个元素，渐渐跟下去就是n,n/2,n/4,....n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。 -
第6题：
若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用__（1）__算法，因为__（2）__。空白（1）处应选择（）
- A、先递归后递推
- B、先递推后递归
- C、递归
- D、递推
正确答案:D -
第7题：
递归通常用（）来实现。
- A、有序的线性表
- B、队列
- C、栈
- D、数组
正确答案:C -
第8题：
以二分查找方法从长度为n的线性有序表中查找一个元素时，时间复杂度为（）。
正确答案:O（log2n） -
第9题：
数据结构里，栈的应用很广泛，递归问题的解决都要靠栈来完成，以下可以递归实现的有（）。
- A、斐波那契数列
- B、n！（n的阶乘）
- C、汉诺塔问题
- D、迷宫问题
正确答案:A,B,C,D -
第10题：
单选题若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用__（1）__算法，因为__（2）__。空白（2）处应选择（）A递推的效率比递归高
B递归宜于问题分解
C递归的效率比递推高
D递推宜于问题分解
正确答案： B解析： 暂无解析 -
第11题：
填空题以二分查找方法从长度为n的线性有序表中查找一个元素时，时间复杂度为（）。正确答案： O（log2n）解析： 暂无解析 -
第12题：
单选题递归通常用（）来实现。A有序的线性表
B队列
C栈
D数组
正确答案： B解析： 暂无解析 -
第13题：
若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用(14)算法，因为(15)。
A．先递归后递推
B．先递推后递归
C．递归
D．递推
正确答案：D
-
第14题：
用折半查找方式查找N个元素的数组，当查找成功时，其递归执行程序时递归调用的最大次数是(11)。
A．
B．
C．
D．
正确答案：D
解析：折半查找法每次将序列划分成两个部分，故最差情况下查找成功的递归调用次数是。 -
第15题：
对具有n个元素的有序表采用二分查找，则算法的时间复杂性为______。
A．O(n)
B． O(n2)
C． O(1)
D． O(log2n)
正确答案：D
解析： 参见有序表采用二分查找时，算法的时间复杂性定义。二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大，但允许相邻元素值相等) 。当有序线性表为顺序存储时才能采用二分法查找，并且二分法查找的效率要比顺序查找高得多。 -
第16题：
用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为______。
A．n
B．n/2
C．log2n
D．log2(n+1)
正确答案：D
解析：二分查找亦称折半查找，其基本思想：设查找表的元素存储在一维数组r[1..n]中，首先将待查的key值与表r中间位置上(下标为mid)的记录的关键字进行比较，若相等，则查找成功：若key＞r[mid]．key，则说明待查记录只可能在后半个子表r[mid+1..n](注意：是mid+1，而不是mid)中，下一步应在后半个子表中再进行折半查找，若keyr[mid].key，则说明待查记录只可能在前半个子表r[1..mid-1](注意：是mid-1，而不是mid)中，下一步应在前半个子表中再进行折半查找，这样通过逐步缩小范围，直到查找成功或予表为空时失败为止。
在表中的元素已经按关键字递增(或递减)的方式排序的情况下，才可进行折半查找。
等概率情况下顺序查找成功的平均查找长度为：
当n值较大时，ASLbs≈log2(n+1)-1。
-
第17题：
在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下：任意取一个元素r，用划分操作确定其在数组中的位置，假设元素r为第k小的数。若i等于k，则返回该元素值；若i小于k，则在划分的前半部分递归进行划分操作找第i小的数；否则在划分的后半部分递归进行划分操作找第k-i小的数。该算法是一种基于（）策略的算法。
- A、分治
- B、动态规划
- C、贪心
- D、回溯
正确答案:A -
第18题：
栈的应用很广泛，递归问题的解决都要靠栈来完成，以下可以递归实现的有（）。
- A、斐波那契数列
- B、n！（n的阶乘）
- C、汉诺塔问题
- D、迷宫问题
正确答案:A,B,C,D -
第19题：
将递归算法转换成对应的非递归算法时，通常需要使用（）来保存中间结果。
- A、队列
- B、栈
- C、链表
- D、树
正确答案:B -
第20题：
如果使用循环结构实现计算n！的算法是（）。
- A、递归
- B、迭代
- C、排序
- D、查找
正确答案:B -
第21题：
单选题如果使用循环结构实现计算n！的算法是（）。A递归
B迭代
C排序
D查找
正确答案： A解析： 暂无解析 -
第22题：
单选题若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用__（1）__算法，因为__（2）__。空白（1）处应选择（）A先递归后递推
B先递推后递归
C递归
D递推
正确答案： C解析： 暂无解析 -
第23题：
单选题对具有n个元素的有序表采用二分查找法，则算法的时间复杂性为（）AO（n）
BO（n2）
CO（1）
DO（log2n）
正确答案： B解析： 暂无解析