首页 > 试题广场 >

设顺序表的长度为n，则顺序查找的平均比较次数为（ ）。

[单选题]

设顺序表的长度为n，则顺序查找的平均比较次数为（）。 

  • n
  • n/2
  • (n+1)/2
  • (n-1)/2
查看正确选项
添加回答
起个响亮的名字的吧头像 起个响亮的名字的吧
顺序查找时，若第一个即为待查找元素，则查找次数为1，若第二个是待查找元素，则查找次数为2，等等。 所以查找次数是1+2+3+4+5+....+n=(1+n)*n/2次，而每个元素是待查找数的概率是相等的，为1/n，那么评论查找次数就是总查找次数乘以每个元素是待查找元素的概率，即(n+1)/2次。
发表于 2018-04-12 08:32:11 回复(2)
dreamHuang头像 dreamHuang
累加求和sum＝(n＋1)*n/2 再求平均值sum/n
发表于 2017-06-13 09:03:15 回复(0)
傻妞妞-MM头像 傻妞妞-MM
顺序表查找来说，最好的就是一次就可以找到，时间复杂度是O（1）
最坏是要比较n次,O(n)
如果查找不成功，要进行n+1次比较
由于关键字在任何一个位置的概率都是相同的，所以平均查找次数是n+1/2，时间复杂度还是O（n）
发表于 2017-08-25 15:30:40 回复(4)
许愿建行拿到offer头像 许愿建行拿到offer
顺序查找时，若第一个元素为待查找元素，则查找次数为1，若第二个是待查找元素，则查找次数是1，依次类推，所有的查找次数是1+2+...+n=n(n+1)/2,而每个元素是待查找数的概率是相等的，为1/n,那么平均查找次数就是总查找次数乘以每个元素是待查找元素的概率，即(n+1)/2次。
发表于 2019-11-17 21:14:38 回复(0)
乌拉乌拉嘿哈头像 乌拉乌拉嘿哈

假设待查找元素为．第1个，则查找次数为1.假设待查找元素为第2个，则查找次数为：2，若待查找素为n，则查找次数为：n+n*（n-1)/2=sum则平均次数为：Sum/n

编辑于 2021-07-29 23:11:21 回复(0)
xhjiang头像 xhjiang
还有一个查找不成功
发表于 2019-06-05 09:31:35 回复(0)
BIRDMAN0908头像 BIRDMAN0908
出现在第一位，比较1次，出现在第n位比较n次，一共比较1+2+3+...+n=n(n+1)/2
平均比较次数为：一共比较次数（各种情况下）/各种情况（n种情况）=n(n+1)/2/n=(n+1)/2
编辑于 2018-12-13 23:29:14 回复(0)
9624头像 9624
第1个位置找到：1 第2个位置找到：2 …… 第n个位置找到：n 如果没找到：n 1+2+3+……+n=(n+1)/2
发表于 2018-10-03 12:54:26 回复(0)
提交观点

问题信息

查找
上传者：阿奻_
难度：
8条回答 16424浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号