niusouti.com

在有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．

题目

在有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位于数组中间位置

相似考题

1.●在长度为n的线性表中顺序查找值为x的元素时，查找成功的平均查找长度为 (49) 。(49) A．nB．n／2C．(n+1)／2D．(n-1)／2

2.N个有序整数数列已放在一维数组中，给定下列程序中，函数fun()的功能是：利用折半查找算法查找整数m在数组中的位置。若找到，则返回其下标值：反之，则返回-1。折半查找的基本算法是：每次查找前先确定数组中待查的范围：low和high(low＜high)，然后把m与中间位置(mid)中元素的值进行比较。如果m的值大于中间位置元素中的值，则下一次的查找范围放在中间位置之后的元素中；反之，下次查找范围落在中间位置之前的元素中。直到low＞high，查找结束。请改正程序中的错误，使它能得出正确的结果。注意：不要改动main函数，不得增行或删行，也不得更改程序的结构。试题程序：include ＜stdio.h＞define N 10/*************found*********************/void fun(int a[],int m){ int low--0,high=N-l,mid;while (low＜=high){ mid=(low+high)/2;if(m＜a[mid])high=mid-1;/*************found*********************/else if(m＞=a [mid])low=mid+1;else return(mid);}return(-1);}main (){ int i,a[N]={-3,4,7,9,13,24,67,89,100,180},k,m;printf ("a数组中的数据如下: ");for(i=0;i＜N;i++) printf("%d",a[i]);printf ("Enter m: "); scanf ("%d", &m);k=fun (a,m);if (k＞=0) printf ("m=%d, index=%d\n",m, k);else printf("Not be found!\n");}

3.在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时的平均查找长度(即x与元素的平均比较次数,假定查找每个元素的概率都相等)为().AnBn/2C(n+1)/2D(n-1)/2

4.阅读下面程序，则程序的执行结果为【19】。#include "stdio.h"fun（int k,int *p）{ int a,b;if（k==1||k==2）*p=1;else{ fun（k-1,&a）;fun（k-2,&b）;*p=a+b;}}main（）{ int x;fun（6, &x）;printf（ "%d＼n",x）;}

更多“在有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 查找失败; 本算法与二分查找（折半查找）算法相比，有可能具有更少比较次数的情形是：”相关问题

  • 第1题：

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

    A．

    B．

    C．

    D．


    正确答案：D
    解析：折半查找法每次将序列划分成两个部分，故最差情况下查找成功的递归调用次数是。

  • 第2题：

    有一排好序的线性表，长度大于2，对给定的K值，分别用顺序查找和二分查找一个与K值相等的元素，比较的次数分别是X和Y。在查找不成功的情况下，正确的X和Y的关系是

    A．X，Y

    B．X＜Y

    C．X=Y

    D．与K大小有关


    正确答案：D
    解析：顺序查找没有要求线性表按关键字值排序。本题要求对排好序的线性表进行查找，不论线性表是升序或降序，k值大小都决定了性表的位置。

  • 第3题：

    若对大小为N的有序顺序表进行顺序查找，当查找不成功时，平均查找长度为(59)；当查找成功且表中仅有一个关键字等于欲查找的元素时，平均查找长度为(60)。

    A．N

    B．N+1

    C．N/2

    D．(N+1)/2


    正确答案：A
    解析：当查找不成功时，会查找至最后一个元素，故平均查找长度为N。

  • 第4题：

    下面程序的运行结果是#include "stdio.h" void fun(int k，int *p) { int a，b； if(k==1|| k==2) *p=1； else { fun(k-1，&a)； fun(k-2，&b)； *p=a+b； } }main(){ int x； fun(6，&x)； printf("%d\n"，x)；}


    正确答案：8
    本题主要考查函数的递归调用。在本题中，程序首先定义了一个无返回类型的fun函数，该函数带有一个整型变量的形参和一个指针型的变量形参。从函数体中我们可以看出，该递归函数的出口是形参k的值等于1或2，如果运行到函数出口，则指针变量形参p的值等1。
    在主函数中，首先定义了一个整型变量x，然后调用fun函数，传递的实参分别为6和变量x的地址，然后程序运行fun函数，在fun函数中，首先定义了两个整型变量a和b，然后判断形参变量k的值是否到达函数出口，这时，k的值为6，没有到达出口，然后程序分别递归执行fun(5，&a)和fun(4，&b)。从程序中可以看出，p的值为分别调用两个函数的p值的和。
    首先执行fun(5，&a)时，k=5，没有到达出口，又进行一次递归，分别执行fun(4，&a)和fun(3，&b)，由于都没达到出口，分别执行fun(3，&a)和fun(2，&b)，fun(2，&a)和fun(1，&b)，由于fun(2，&a)和fun(1，&b)返回的p值都为1，那么fun(3，&a)返回p的值为2，fun(4，&a)返回的p值就等于fun(3，&a)和fun(2，&b)之和，为3，同理可以得出fun(5，&a)返回的p值为5，fun(6，&a)返回的p值为8。因此，最后题目要求输出的结果为8。

  • 第5题：

    阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。

    [说明]

    已知r[1...n]是n个记录的递增有序表，用折半查找法查找关键字为k的记录。若查找失败，则输出“failure",函数返回值为0；否则输出“success”，函数返回值为该记录的序号值。

    [C函数]

    int binary search(struct recordtype r[],int n,keytype k)

    { intmid,low=1,hig=n;

    while(low＜=hig){

    mid=(1);

    if(k＜r[mid].key) (2);

    else if(k==r[mid].key){

    printf("succesS\n");

    (3);

    }

    else (4);

    }

    printf("failure\n");

    (5);

    }


    正确答案：(1) (low+hig)/2 (2) hig=mid-1 (3) returnmid (4) low=mid+1 (5) return 0
    (1) (low+hig)/2 (2) hig=mid-1 (3) returnmid (4) low=mid+1 (5) return 0 解析：折半查找法也就是二分法：初始查找区间的下界为1，上界为len，查找区间的中界为k=(下界+上界)/2。所以(1)应填“(low+hig)/2”。中界对应的元素与要查找的关键字比较。当kr[mid].key时，(2)填“hig=mid-1”；当k==r[mid].key时，(3)填“return mid”；当k＞r[mid].key时，(4)填“low=mid+1”。如果low＞hig时循环终止时，仍未找到需查找的关键字，那么根据题意返回0，即空(5)填“return 0”。

  • 第6题：

    在长度为n的线性表中顺序查找值为x的元素时，查找成功的平均查找长度为(49)。

    A．n

    B．n/2

    C．(n+1)/2

    D．(n-1)/2


    正确答案：C
    解析：假设在每个位置查找的概率相等，即有pi=1/n；若是从表尾往表头方向查找，则在每个位置上的查找比较次数为Cn=1，Cn-1=2,...C1=n。因此，查找成功的平均查找长度为

  • 第7题：

    从一个具有N个结点的单链表中查找其值等于X结点时，查找成功的情况下，需平均比较()结点。

    A.N
    B.N/2
    C.(N-1)/2
    D.(N+1)/2

    答案：D
    解析：

  • 第8题：

    对于n个元素的顺序表采用顺序查找，且使用监视哨。若查找成功，则比较关键字的次数最多为（）次；若查找失败，则比较关键字的次数最少为（）


    正确答案:n；n+1

  • 第9题：

    在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度（）

    • A、n/2
    • B、（n-1）／2
    • C、（n+1）／2
    • D、n

    正确答案:C

  • 第10题：

    在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为（）。

    • A、n
    • B、n/2
    • C、（n+1）/2
    • D、（n-1）/2

    正确答案:C

  • 第11题：

    单选题
    在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为（）。
    A

    n

    B

    n/2

    C

    （n+1）/2

    D

    （n-1）/2


    正确答案： C
    解析： 暂无解析

  • 第12题：

    单选题
    从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个元素结点。
    A

    n/2

    B

    n

    C

    （n+1）/2

    D

    （n-1）/2


    正确答案： D
    解析： 暂无解析

  • 第13题：

    顺序查找n个元素的顺序表,若查找成功,则比较关键字的次数最多为()次。

    A、n/2

    B、(n+1)/2

    C、(n-1)/2

    D、n


    参考答案：D

  • 第14题：

    从一个具有n个结点的单链表中查找其值等于k的结点时，在查找成功的情况下，需平均比较 ______个结点。

    A．n

    B．n/2

    C．(n-1)/2

    D．(n+1)/2


    正确答案：D
    解析：在n个结点的单链表中，查找第i个结点需要比较关键词的次数是i，所以，在查找成功的情况下，需平均比较的结点个数为(1+2+…+n)/n，即(n+1)/2。

  • 第15题：

    ● 对 n 个元素的有序表 A[1..n]进行二分（折半）查找，则成功查找到表中的任意一个元素时，最多与A 中的 （39） 个元素进行比较。

    （39）


    正确答案：D

  • 第16题：

    有一排好序的线性表，长度大于2，对给定的k值，分别用顺序查找和二分查找查找一个与k值相等的元素，比较的次数分别为x和y。在查找不成功的情况下，正确的x和y的关系是 ______。

    A．x＞y

    B．总是x＜y

    C．x＝y

    D．与k值的大小有关


    正确答案：D
    解析：顺序查找没有要求线性表按关键字值排序。本题要求对排好序的线性表进行查找，不论线性表是升序或降序，则k值大小决定了性表的位置，所以应选择D。

  • 第17题：

    有一个排好序的线性表，长度大于2，对给定的k值，分别用顺序查找和二分查找查找一个与k值相等的元素，比较的次数分别为x和y。在查找不成功的情况下，正确的x和y的关系是______。

    A．x＞y

    B．总是x＜y

    C．x＝y

    D．与k值大小有关


    正确答案：D
    解析：顺序查找没有要求线性表按关键词值排序。本题要求对排好序的线性表进行查找，不论线性表是升序或降序，则k值大小决定了线性表的位置，所以应选择D。

  • 第18题：

    从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。

    A．n

    B．n/2

    C．(n-1)/2

    D．(n+1)/2


    正确答案：D

  • 第19题：

    以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格。

    略

  • 第20题：

    在索引查找中，若用于保存数据元素的主表的长度为n，它被均分为k个子表，每个子表的长度均为n/k，则索引查找的平均查找长度为（）。

    • A、 n+k
    • B、 k+n/k
    • C、 （k+n/k）/2
    • D、 （k+n/k）/2+1

    正确答案:D

  • 第21题：

    顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为（）次；当使用监视哨时，若查找失败，则比较关键字的次数为（）。


    正确答案:n；n+1

  • 第22题：

    从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个元素结点。

    • A、n/2
    • B、n
    • C、（n+1）/2
    • D、（n-1）/2

    正确答案:C

  • 第23题：

    填空题
    顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为（）次；当使用监视哨时，若查找失败，则比较关键字的次数为（）。

    正确答案： n,n+1
    解析： 暂无解析

  • 第24题：

    填空题
    对于n个元素的顺序表采用顺序查找，且使用监视哨。若查找成功，则比较关键字的次数最多为（）次；若查找失败，则比较关键字的次数最少为（）

    正确答案： n,n+1
    解析： 暂无解析

相关内容