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

admin2020-11-23 97

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

下面选项中关于位运算的叙述正确的是()。

设数据元素的集合D={1，2，3，4，5}，则满足下列关系R的数据结构中为线性结构的是()。

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

设有定义：charp[]={’1’，’2’，’3’)，*q=p；以下不能计算出一个char型数据所占字节数的表达式是()。

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

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

Theyareshockedtofind______waterhasbeenpolluted.

绒毛膜癌临床和声像图表现，下列哪一项不正确

某年某地的简略寿命表中0岁组的期望寿命为68岁，则1岁组的预期寿命

问卷调查的设计步骤包括()。

施工质量保证体系的运行，应以质量()为主线，以过程管理为重心。

下列关于支付结算的表述中，不正确的是()。

2000—2009年，我国城镇居民转移性收入增长幅度与工薪收入增长幅度相比，()。

通过网络发布虚假消息给他人名誉造成损害，责任完全由消息发布者承担。()

=__________．

YouworkintheCustomerServicesDepartmentofaninductioncookercompany.Youhavebeenaskedtoprepareareportforyourde