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

admin2020-11-23 52

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

选项 A、(3＋n)/4
B、n
C、n/2
D、n/4

答案A

解析在长度为n的顺序表中查找一个元素，最好的情况是目标在第一个，一次找到；最坏的情况是目标在最后一个，n次找到。那么平均长度为：(1+2+...+n)/n=(n(n+1)/2)/n=(n+1)/2
本题需要查找的元素有一半的机会在表中，则在平均情况下需要比较的次数大约为((1+n)/2+1)/2=(3＋n)/4。所以选项A正确。

转载请注明原文地址:https://jikaoti.com/ti/lcD0FFFM

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

二级C语言

NCRE全国计算机二级

相关试题推荐

随机试题

最新回复(0)

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

二级C语言

NCRE全国计算机二级

设循环队列的存储空间为Q(1：m)，初始状态为空。现经过一系列正常的入队与退队操作后，front=m，rear=m-1，此后从该循环队列中删除一个元素，则队列中的元素个数为()。

若有以下程序段：doublex=5．16894；printf("％f＼n"，(int)(x*1000+0．5)／(double)1000)；则程序段的输出结果是()。

以下关于结构化程序设计的叙述中正确的是()。

下列数据结构中，能够按照“先进后出”原则存取数据的是()。

设已有定义：floatx．则以下对指针变量p进行定义且赋初值的语句中正确的是()。

下列给定程序中，函数fun的功能是：用选择法对数组中的n个元素进行升序排列。请修改程序中的错误，使它能得出正确的结果。注意：不得增行和删行，也不得更改程序的结构!试题程序：#include＜stdio．h＞

待排序的关键码序列为(15，20，9，30，67，65，45，90)，要按关键码值递增的顺序排序，采取简单选择排序法，第一趟排序后：关键码15被放到第()个位置。

关于地址和指针，以下说法中正确的是()。

A．生地黄B．山慈菇C．牡丹皮D．水牛角E．银柴胡以上药物中可消痈散结的是

A、灵芝B、松萝C、乳香D、苏合香E、茯苓药用地衣体的药材为

基本门如图7—6—2(a)所示，其中，数字信号A由图(b)给出，那么，输出F为()。[2011年真题]

下列可以适用代理的行为是()。[2008年11月二级真题]

下列关于红色预警法的说法，错误的是()。

下列关于经济资本的说法，正确的是()。

民事主体依法被宣告破产的资格，是指()。

关于法起源的一般规律，下列表述正确的是()。

A、 B、 C、 D、 B

结构化分析(SA)是软件开发需求分析阶段所使用的方法，以下选项中哪个不是SA所使用的工具?