首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
判断下列说法是否正确:在长度都为n的有序单链表和顺序表上分别
[单选题]
判断下列说法是否正确:在长度都为n的有序单链表和顺序表上分别做顺序查找,若查找每个元素的概率相等,
则顺序查找表中任一元素的查找成功的平均查找长度相同。()
正确
错误
添加笔记
求解答(0)
邀请回答
收藏(1)
分享
纠错
3个回答
添加回答
1
别把我的紫青宝剑
答案:A
这个题比较关键的一点是理解最后一句话中的“顺序查找”。顺序查找的意思应当是按照这组数据从小到大(或从大到小)的顺序进行查找。
①有序单链表本质是单链表,单链表的访问只能是从第一个结点开始,用一个结点的next指针访问下一个结点,每访问一个结点就对比该结点中的数据是否是我们需要找的数据,如果是则说明找到然后停止查找,如果不是则依次访问下一个结点进行对比查找;因为该单链表有序,那么我们顺序查找这组数据时访问的次数依次是1,2,……,n-1,n(或者反之n,……,1),平均查找长度就是(n+1)/2。
②顺序表就相当于是一个数组,这组数据无序地存放在一个数组中,访问无序的数组的流程与访问单链表的类似,都是需要访问然后对比是否是所要找的数据,是则停止访问,否则访问下一个继续对比。因此平均查找长度也是
(n+1)/2。
发表于 2020-03-18 09:58:47
回复(0)
0
Finalize
答案是A
顺序查找情况下线性表都是一个方向查找的(只有顺序查找存储结构可以既是顺序表和链表),所以平均查找长度一定是一样的
发表于 2020-04-01 16:07:32
回复(0)
0
牛客110086
答案:A
解析:(1)由于链表不能随机访问,要访问某个结点,必须从它的直接前趋指针域出发才能找到。因此,链式存储的线性表,即使是有序表,也只能使用顺序查找。顺序查找时,从表中的第一个元素开始,将给定的值与表中逐个元素的关键字进行比较,直到两者相符,查到所要找的元素为止。
假设在每个位置查找概率相等,即P
1
=P
2
… =P
n
=1/n,若是从表头向表尾方向查找,则每个位置上查找比较次数为C
1
=1,C
2
=2,…,C
n
=n。于是,查找成功的平均查找长度为:1×1/n+2×1/n+...+n×1/n=(n+1)/2
(2)有序单链表和顺序表都是单链表,查找方式相同,因此平均查找长度也相同。
发表于 2020-03-10 20:01:11
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
查找
上传者:
zsw3
难度:
3条回答
1收藏
3764浏览
热门推荐
相关试题
假定一个待哈希存储的线性表为(32...
哈希
评论
(1)
5.下列判断正确的是( )
资料分析
言语理解与表达
资料分析
评论
(1)
《拳皇97》最后BOSS是谁?
游戏常识
评论
(1)
《魔兽世界》中,下列不属于玩家可以...
游戏常识
评论
(1)
你有没有崇拜的偶像,你欣赏他/她身...
通用能力
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题