在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为( )。

admin2022-04-01 42

问题在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为( )。

选项 A、n
B、3n／4
C、n／2
D、n／4

答案B

解析在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为n。这是找到元素的情况。如果没有找到元素，则要比较n次。因此，平均需要比较：找到元素的情况×

+未找到元素的情况×

=(1+2+…+n)／n×

+n×

，大约为

。

转载请注明原文地址:https://kaotiyun.com/show/a6kp777K

本试题收录于：二级C语言题库NCRE全国计算机二级分类

二级C语言

NCRE全国计算机二级

相关试题推荐

随机试题

最新回复(0)

在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为( )。

二级C语言

NCRE全国计算机二级

有以下程序：#includemain(){inta=1，b=3，c=5；intp1=&a，p2=&b，P=&c；P=p1(*p2)；printf("％d＼n"，c)

若有以下程序#includeintf(ints,intt){intk;if(s＜t){k=s;s=t;t=k;}returns;}main(){inti=3,j=5,p=&i,q=&j,r;r=f(p,q);pr

下列程序中函数f的功能是：当flag为1时，进行由小到大排序；当flag为0时，进行由大到小排序voidflintb[]，intn，intflag)main(){inti，j，t；{inta[10]={5，4，3，2，1，6，7，8

有以下程序#include＜stdio．h＞inta=1，b=2；yoidfunl(inta，intb){printf(’’％d％d’’，a，b)；}yoidfun2(){a=3；b=4；}main(){funl(5，6)；

若变量已正确定义，则语句s=32；s^=32；printf("％d"，s)；的输出结果是()。

以下关于简单程序设计的步骤和顺序的说法中正确的是

以下程序调用fun函数求数组中最大值所在元素的下标。#includevoidfun(ints,intn,intk){inti;for(i=0,*k=i;i

下列定义变量的语句中错误的是

一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为

对如下二叉树进行后序遍历的结果为

Mostofyougraduatingtodaywillbeemployeesallyourworkinglife,workingforsomebodyelseandforapaycheck.Andsowill

初次注射胰岛素最常见的全身反应是过敏性休克。()

A、有效控制疟疾症状B、控制疟疾的复发和传播C、主要用于预防疟疾D、抢救脑型疟疾效果良好E、适用于耐氯喹恶性疟疾的治疗磷酸伯氨喹（）。

[2007年，第16题]微分方程cosydx+(1+e-x)sinydy=0满足初始条件的特解是()。

“学生在课堂上一边做笔记，一边思考”描述的是()。

国家机关工作人员甲通过电子邮件，将因工作便利获悉的国家经济秘密发送给某境外机构。甲的行为构成()(2012年一专一第18题)

"You"inthepassagewanttogototheschool."You"willfirstmmleft,andthenmmright.

A、Itisworthwhile.B、Itistooexpensive.C、Ittastesdelicious.D、Itishealthier.B

在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为( )。

二级C语言

NCRE全国计算机二级

有以下程序：#includemain(){inta=1，b=3，c=5；int*p1=&a，*p2=&b，*P=&c；*P=*p1*(*p2)；printf("％d＼n"，c)

若有以下程序#includeint*f(int*s,int*t){intk;if(*s＜*t){k=*s;*s=*t;*t=k;}returns;}main(){inti=3,j=5,*p=&i,*q=&j,*r;r=f(p,q);pr

下列程序中函数f的功能是：当flag为1时，进行由小到大排序；当flag为0时，进行由大到小排序voidflintb[]，intn，intflag)main(){inti，j，t；{inta[10]={5，4，3，2，1，6，7，8

有以下程序#include＜stdio．h＞inta=1，b=2；yoidfunl(inta，intb){printf(’’％d％d’’，a，b)；}yoidfun2(){a=3；b=4；}main(){funl(5，6)；

若变量已正确定义，则语句s=32；s^=32；printf("％d"，s)；的输出结果是()。

以下关于简单程序设计的步骤和顺序的说法中正确的是

以下程序调用fun函数求数组中最大值所在元素的下标。#includevoidfun(int*s,intn,int*k){inti;for(i=0,*k=i;i

下列定义变量的语句中错误的是

一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为

对如下二叉树进行后序遍历的结果为

Mostofyougraduatingtodaywillbeemployeesallyourworkinglife,workingforsomebodyelseandforapaycheck.Andsowill

初次注射胰岛素最常见的全身反应是过敏性休克。()

A、有效控制疟疾症状B、控制疟疾的复发和传播C、主要用于预防疟疾D、抢救脑型疟疾效果良好E、适用于耐氯喹恶性疟疾的治疗磷酸伯氨喹（）。

[2007年，第16题]微分方程cosydx+(1+e-x)sinydy=0满足初始条件的特解是()。

“学生在课堂上一边做笔记，一边思考”描述的是()。

国家机关工作人员甲通过电子邮件，将因工作便利获悉的国家经济秘密发送给某境外机构。甲的行为构成()(2012年一专一第18题)

"You"inthepassagewanttogototheschool."You"willfirstmmleft,andthenmmright.

A、Itisworthwhile.B、Itistooexpensive.C、Ittastesdelicious.D、Itishealthier.B

有以下程序：#includemain(){inta=1，b=3，c=5；intp1=&a，p2=&b，P=&c；P=p1(*p2)；printf("％d＼n"，c)

若有以下程序#includeintf(ints,intt){intk;if(s＜t){k=s;s=t;t=k;}returns;}main(){inti=3,j=5,p=&i,q=&j,r;r=f(p,q);pr

以下程序调用fun函数求数组中最大值所在元素的下标。#includevoidfun(ints,intn,intk){inti;for(i=0,*k=i;i