首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
表长为n的顺序存储的线性表,当在任何位置上删除一个元素的概率相等时,删除一个元素所需移动元素的平均个数为( )。
表长为n的顺序存储的线性表,当在任何位置上删除一个元素的概率相等时,删除一个元素所需移动元素的平均个数为( )。
admin
2021-08-17
108
问题
表长为n的顺序存储的线性表,当在任何位置上删除一个元素的概率相等时,删除一个元素所需移动元素的平均个数为( )。
选项
A、n
B、n/2
C、(n-1)/2
D、(n+1)/2
答案
C
解析
顺序表的删除运算时间主要消耗在移动表中元素上,删除第i个元素时,其后面的元素a
i+1
~a
n
都要向上移动一个位置,共移动了n一i个元素。在等概率情况下,即p
i
=1/n,则:
这说明顺序表上作删除运算时大约需要移动表中一半的元素,显然该算法的时间复杂度为O(n)。
转载请注明原文地址:https://kaotiyun.com/show/4D3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址,虚拟地址16位,物理地址12位,页大小为128B,TLB为4路组相连,共有16个页表项,L1DataCache采用直接映射方式,块大小为4B,共16行。在系统运行到某一
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
假定磁盘传输数据以32bit的字为单位,传输速率为1MB/s。CPU的时钟频率为50MHz。根据以上计算,可得出什么结论?
给出一个单车道的简易桥,如图8—4所示。车流如箭头所示。桥上不允许有两车交会,但允许同方向车依次通行(即桥上可以有多个同方向的车)。该桥最大可载重5辆汽车。用P,V操作实现交通管理,以防桥上交通堵塞。
关于FTP的工作过程,下面说法错误的是()。
一个公司有两个部门,研发部和市场部,研发部有29台计算机,市场部有11台计算机。现在,公司申请了一个C类地址212.112.32.0,规划的网络拓扑如图1一5所示。试问:请给出合理的子网规划,并说明理由,然后将规划填入表1-3。
某微型计算机的寻址范围为64KB,CPU外接8片8KB的RAM芯片(片号从O开始),存储芯片的片选信号为CS(低电平有效)。试回答以下问题:若发现第1、3、5、7片RAM始终不被选中,试分析故障原因。
有如图3—4所示的带权有向图G,试回答以下问题。给出从顶点1出发的深度优先遍历序列和广度优先遍历序列。
当客户端请求域名解析时,如果本地DNS服务器不能完成解析,就把请求发送给其他服务器,依次进行查询,直到把域名解析结果返回给请求的客户端,这种方式叫()。
已知x和y,用变形补码计算结果,同时指出结果是否溢出。(要求写出计算步骤)x=一0.1011,y=一0.1001求x+y,x—y=?
随机试题
TheNorthernLightsThesunisstormyandhasitsownkindofweather.ItissohotandactivethateventheSun’sgravity
正常人的血压标准是
观察法的优点主要有()。
________是工作排序确定的基础。
科学发展观要求经济社会协调发展,在经济发展的同时,促进社会全面进步。国家财政支出中与此相关的项目有()。
行政机关申请法院强制执行前()。
通用对话框中打开“颜色对话框”的方法是()。
【说明】请以英语系学生会的名义写一则海报。【时间】3月15日。【内容】为丰富课外活动,提高学生英语口语能力,学生会定于下周三下午1点半在主楼404教室举办全系英语演讲比赛。凡是愿意参加者在本周六以前向各班班长报名,届时将有英美外籍老师参加并进行评判。凡
Whatisthemaintopicofthispassage?FromtheresearchconductedbythecommunicationproviderInter-Tel,welearnthat_____
Bullyingisadistinctivepatternofharmingandhumiliatingothers.Thosewhoareinsomewaysmaller,weaker,youngerormore【
最新回复
(
0
)