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

admin2020-11-23 50

问题在长度为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全国计算机二级

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

下列给定程序中，函数fun的功能是建立一个N×N的矩阵。矩阵元素的构成规律是：最外层元素的值全部为1；从外向内第2层元素的值全部为2；第3层元素的值全部为3，……以此类推。例如，若N=5，生成的矩阵为：111111222

设循环队列为Q(1：m)，其初始状态为fronront=rear=m。经过一系列入队与退队为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为()。

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

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

C语言程序中，运算对象必须是整型数的运算符是()。

设二叉树共有375个结点，其中度为2的结点有187个。则度为1的结点个数是

用于检测红细胞膜是否有缺陷的试验是

()是要解决过去完全没有或仅部分出现过的问题，往往缺乏类似问题处理经验。

刑事责任包括警告、管制、拘役、有期徒刑、无期徒刑、死刑以及罚款、剥夺政治权利、没收财产等刑罚。()

依据企业所得税的相关规定，下列表述中，正确的是()。(2009年原制度)

原因和结果是我们思维的创造物”“在自然界中，既没有原因，也没有结果”。对这句话理解正确的有()。

根据所给资料，回答以下问题。2016年6月中国出口稀土3849吨，与去年同期相比增长19．6％，出口金额2．86千万美元，同比下降34．7％。2016年1—6月中国出口稀土23213吨，与去年同期相比增长67．2％；出口金额达17．16千万美元，

运算结果不是2010的表达式是