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

admin2020-11-23 74

问题在长度为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://kaotiyun.com/show/y53p777K

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

二级C语言

NCRE全国计算机二级

相关试题推荐

随机试题

最新回复(0)

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

二级C语言

NCRE全国计算机二级

以下叙述中错误的是()。

有如下程序：#include＜stdio．h＞#include~string．h＞main(){chara[]="1234"，*b="ABC"；printf("％d％d％d％d＼n"，s

下列数据结构中，属于非线性结构的是()。

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

某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为(假设根结点在第1层)()。

我们所写的每条C语句，经过编译最终都将转换成二进制的机器指令。关于转换以下说法错误的是

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

A．急性化脓性胆囊炎B．急性化脓性胆管炎C．急性坏死性胰腺炎D．急性化脓性阑尾炎E．绞窄性肠梗阻Murphy征出现于

PassageThreeWhomdoyouthinkthispassageisaddressedto?

正常生产时，影响精馏塔操作压力的主要因素有()。

A．补液试验后尿量无变化B．双肾B超，KUBC．逆行肾盂造影D．尿中大量红细胞管型E．尿比重＞1.030，尿钠＜20mmol/L

long-circulatingliposomes

某患者面部外伤造成右侧上唇部分缺损，缺损大小相当于上唇的1/5，伤口不甚干净，创面已不渗血。以下处理措施中，哪项是不必要的

已知某项目的年总成本费用为300万元，年销售费用、管理费用合计为总成本费用的10%，年折旧费为20万元，年摊销费为10万元，年利息支出为10万元，则该项目的年经营成本为()万元。

(2008年考试真题)在下列各项中，不属于滚动预算方法的滚动方式的是()。

Althoughinteriordesignhasexistedsincethebeginningofarchitecture,itsdevelopmentintoa【C1】______fieldisreallyquite

A、Mostwomenfindnewjobsthroughinformalrecruitment.B、Mostwomenfindnewjobsthroughformaljobsearch.C、Workexperience