表长为n的顺序存储的线性表，当在任何位置上删除一个元素的概率相等时，删除一个元素所需移动元素的平均个数为( )。

admin2021-08-17 106

问题表长为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://www.kaotiyun.com/show/4D3i777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一
一台模型机共有7条指令，主频25MHz，各指令的使用频率与CPI如表2-4所示。该模型机有8位和16位两种指令字长，采用2-4扩展操作码。8位字长指令为寄存器-寄存器(R-R)二地址类型，16位字长指令为寄存器-存储器(R—M)二地址变址寻址类型(-128
现有3名学生S1、S2和S3上机实习，程序和数据都存放在同一磁盘上。若3人编写的程序分别为P1、P2和P3，要求这3个学生用自编的程序调用同一个数据文件A进行计算。试问：若该系统提供文件换名命令RENAME，试说明这一换名功能的实现技术，另外，也可以通
设有一个直接映像方式的Cache，其容量为8KB，每块的大小为16B，主存的容量为512KB，试回答以下问题：主存有多少个块?分为多少个区?
某双总线模型机如图8—3所示。双总线分别记为B1和B2；图8—3中连线的方向标明数据通路及流向，并注有相应的控制信号(微命令)；A、B、C、D为4个通用寄存器；X为暂存器；M为多路选择器，用于选择进入暂存器x的数据，存储器为双端口，分别面向总线B1和B2。
某操作系统支持页式虚拟存储管理，其中央处理器的周期是1μs。当不是处于同一页面时，访问另一个页面耗时1μs。一个页面含1K字。使用磁盘作为外存，其转速为3000r／min，传输率为1M字／s。还测得下列数据：磁盘平均寻道时间为19ms，1％的指令要访问不处
假设某计算机的主存地址空间大小为64KB，采用字节编址方式。其Cache数据区容量为4KB，采用4路组相联映射方式、LRU替换和回写(WriteBack)策略，块大小为64B，并且每块设置了1位有效位。请问：若Caclle初始为空，CPU依次从0号地
在一个单总线结构的计算机中，用一条总线连接了指令寄存器(IR)、程序计数器(PC)、存储器地址寄存器(MAR)、存储器数据寄存器(MDR)、通用寄存器(r0～r7)，ALU输入端寄存器(Y)，ALU以及ALU输出端寄存器(Z)。该计算机有以下指令：
一个公司有两个部门，研发部和市场部，研发部有29台计算机，市场部有11台计算机。现在，公司申请了一个C类地址212．112．32．0，规划的网络拓扑如图1一5所示。试问：如果路由器R1和R2都采用了路由信息协议(RoutingInformation
下面()寻址方式处理数组问题更为方便。

随机试题

资料的鉴别和利用应考虑的原则是()
下列各类项目中，属于服务项目的有（）。
生产者为防止需求不确定性和供应不确定陛带来的缺口而设置的一定数量的存货，被称为()。
()不是“神经症”的主要类型。
《中华人民共和国教育法》规定，教师拥有的权利包括：教育教学权、科学研究权、管理学生权、获取报酬待遇权、民主管理权和()权等六项。
追求个人特有潜能的充分发挥和个人价值的实现是()。
不同利益群体的特定体制中所受束缚与保护的程度是不同的，相对而言，束缚少而保障多的群体会觉得体制公平，反之会觉得不公平进而要求变革。转轨过程的情况与此类似，某个群体摆脱的束缚多于失去的保障，甚至是只摆脱束缚而不失去保障，他们会拥护改革并认为它公平；相反，摆脱
思维的特征包括()。
(南京大学2014)ABC银行有如下的资产负债表。试计算：市场利率同步上升1个百分点，该银行的权益市场价值将发生何种变化?
甲对乙有10万元债权，丙提供保证。现乙经甲同意，将该债务移转于丁承担，丙并不知情。则丙()

最新回复(0)

表长为n的顺序存储的线性表，当在任何位置上删除一个元素的概率相等时，删除一个元素所需移动元素的平均个数为( )。

计算机408

学硕统考专业

假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一

设有一个直接映像方式的Cache，其容量为8KB，每块的大小为16B，主存的容量为512KB，试回答以下问题：主存有多少个块?分为多少个区?

假设某计算机的主存地址空间大小为64KB，采用字节编址方式。其Cache数据区容量为4KB，采用4路组相联映射方式、LRU替换和回写(WriteBack)策略，块大小为64B，并且每块设置了1位有效位。请问：若Caclle初始为空，CPU依次从0号地

在一个单总线结构的计算机中，用一条总线连接了指令寄存器(IR)、程序计数器(PC)、存储器地址寄存器(MAR)、存储器数据寄存器(MDR)、通用寄存器(r0～r7)，ALU输入端寄存器(Y)，ALU以及ALU输出端寄存器(Z)。该计算机有以下指令：

一个公司有两个部门，研发部和市场部，研发部有29台计算机，市场部有11台计算机。现在，公司申请了一个C类地址212．112．32．0，规划的网络拓扑如图1一5所示。试问：如果路由器R1和R2都采用了路由信息协议(RoutingInformation

下面()寻址方式处理数组问题更为方便。

资料的鉴别和利用应考虑的原则是()

下列各类项目中，属于服务项目的有（）。

生产者为防止需求不确定性和供应不确定陛带来的缺口而设置的一定数量的存货，被称为()。

()不是“神经症”的主要类型。

《中华人民共和国教育法》规定，教师拥有的权利包括：教育教学权、科学研究权、管理学生权、获取报酬待遇权、民主管理权和()权等六项。

追求个人特有潜能的充分发挥和个人价值的实现是()。

思维的特征包括()。

(南京大学2014)ABC银行有如下的资产负债表。试计算：市场利率同步上升1个百分点，该银行的权益市场价值将发生何种变化?

甲对乙有10万元债权，丙提供保证。现乙经甲同意，将该债务移转于丁承担，丙并不知情。则丙()