用折半查找方式查找N个元素的数组，当查找成功时，其递归执行程序时递归调用的最大次数是(11)。A．B．C．D．

题目

用折半查找方式查找N个元素的数组，当查找成功时，其递归执行程序时递归调用的最大次数是(11)。

A．

B．

C．

D．

相似考题

1.设有100个元素，用折半查找法进行查找时，最大比较次数是_____。A.25B.50C.10D.7

2.设有100个元素，用折半查找法进行查找时，最大比较次数是（）。 Ａ．25 B．8 C．10 D．7

3.在有n（n＞1000）个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示： k = 0; while （k＜n 且 A[k]＜x ) k = k+3; if （k＜n 且 A[k]==x ) 查找成功; else if （k-1＜n 且 A[k-1]==x ) 查找成功; else if （k-2＜n 且 A[k-2]==x ) 查找成功; else 查找失败; 本算法与二分查找（折半查找）算法相比，有可能具有更少比较次数的情形是：A．当x不在数组中B．当x接近数组开头处C．当x接近数组结尾处D．当x位于数组中间位置

4.第四题 阅读以下说明、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 （2）;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 return biSearch_rec(（5）,key);elsereturn 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

参考答案和解析
正确答案：D
解析：折半查找法每次将序列划分成两个部分，故最差情况下查找成功的递归调用次数是。
更多“ 用折半查找方式查找N个元素的数组，当查找成功时，其递归执行程序时递归调用的最大次数是(11)。A．B．C．D． ”相关问题

  • 第1题：

    在有 n（n＞1000）个元素的升序数组 A 中查找关键字 x 。查找算法的伪代码如下所示。 k=0; while （k＜n 且 A[k]＜x) k=k+3; if （k＜n 且 A[k]==x) 查找成功; else if （k-1＜n 且 A[k-1]==x) 查找成功; else if （k-2＜n 且 A[k-2]==x) 查找成功; else 查找失败; 本算法与折半查找算法相比，有可能具有更少比较次数的情形是（）。

    A．当 x 不在数组中

    B．当 x 接近数组开头处

    C．当 x 接近数组结尾处

    D．当 x 位于数组中间位置


    当x接近数组开头处

  • 第2题：

    长度为n的有序顺序表采用折半查找，查找成功的最少次数为（），查找成功的最大次数为（），查找失败的最大次数为（），所以折半查找的最坏时间复杂度为（）

    A．1,logn,logn,O(logn)

    B．1,n,n,O(n)

    C．1,n,logn,O(logn)

    D．1,logn,n,O(n)


    B

  • 第3题：

    （）设有100个元素，用折半查找法进行查找时，最大比较次数是7次。


    A

  • 第4题：

    1、在有 n（n＞1000）个元素的升序数组 A 中查找关键字 x 。查找算法的伪代码如下所示。 k=0; while （k＜n 且 A[k]＜x) k=k+3; if （k＜n 且 A[k]==x) 查找成功; else if （k-1＜n 且 A[k-1]==x) 查找成功; else if （k-2＜n 且 A[k-2]==x) 查找成功; else 查找失败; 本算法与折半查找算法相比，有可能具有更少比较次数的情形是（）。

    A．当 x 不在数组中

    B．当 x 接近数组开头处

    C．当 x 接近数组结尾处

    D．当 x 位于数组中间位置


    当x接近数组开头处

  • 第5题：

    100个元素进行折半查找，查找成功时最大的比较次数是（）。

    A．7

    B．6

    C．10

    D．8


    D

相关内容