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

admin2021-08-17 87

问题表长为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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

现有3名学生S1、S2和S3上机实习，程序和数据都存放在同一磁盘上。若3人编写的程序分别为P1、P2和P3，要求这3个学生用自编的程序调用同一个数据文件A进行计算。试问：若文件A作为共享文件，系统应采用何种目录结构?画出示意图。
设有一个直接映像方式的Cache，其容量为8KB，每块的大小为16B，主存的容量为512KB，试回答以下问题：主存有多少个块?分为多少个区?
已知一个带有表头结点的单链表，结点结构为(data，next)，假设该链表只给出了头指针L，请设计一个时间和空间上尽可能高效的算法，将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。说明你所设计算法的时间复杂度与空间复杂度。
在一个段式存储管理系统中，逻辑地址为32位，其中高16位为段号，低16位为段内偏移，以下是段表(其中的数据均为十六进制，如表7-1所示)。以下是代码段的内容：试问：x的逻辑地址为10108，它的物理地址是多少?
以下说法正确的是()。Ⅰ．带头结点的循环双链表L为空的条件是：L->prior=L&&L->next==LⅡ．线性表的插入和删除总是伴随着大量数据的移动Ⅲ．只有删除静态链表的尾结点才不需要移动元素Ⅳ．若线性
以下有关拓扑排序的说法中，错误的是()。Ⅰ．如果某有向图存在环路，则该有向图一定不存在拓扑排序Ⅱ．在拓扑排序算法中，既可以使用栈，也可以使用队列Ⅲ．若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1
在含有15个结点的平衡二叉树上，查找关键字为28(存在该结点)的结点，则依次比较的关键字有可能是()。
设同一网络中有四台主机A，B，C，D，各个主机的IP地址和子网掩码，如下表所示：请回答下列问题：(1)给出四个主机所在的子网地址，并根据结果画出网络拓扑图。(2)现有一台机器E要加入当前网络，新加入的机器与主机D处于同一个子网内，那么主机E的IP地
下列说法中错误的是()。
假设某计算机的运算器框图如下图所示，其中ALU为16位的加法器(高电平工作)，SA、SB为16位锁存器，4个通用寄存器由D触发器组成，Q端输出，读控制写控制微指令字长12位，格式如下(末考虑顺序控制字段)：各字段意义如下：F1一读R0一R3

随机试题

柴油发动机动力不足的原因有哪些?
根据归经学说，用辅料炮制药物，醋制入
A．峰电位B．阈电位C．负后电位D．局部电位E．正后电位刺激引起兴奋的基本条件是使跨膜电位达到
因身体或精神功能减退，丧失了谋求和保持一个适于就业机会由于损伤造成能力的受限，使人不能正常进行活动
下列有关票据记载事项的说法中，正确的是：
调查报告只限于从自身的实践活动中选取材料，提炼论点。()
下列有关物质和运动的说法，错误的是()。
日常生活中，有些人在服药时为图省事，将药片放人口中后，不喝水或仅喝一口水，再用力一咽，就算是服完药了。有些人认为这种服药方式是不可取的。以下哪项如果为真，最能支持这些人的观点?()
决策
通常认为，决定局域网特性的主要技术有3种，它们是传输介质和(60)。

最新回复(0)

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

计算机408

学硕统考专业

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

在一个段式存储管理系统中，逻辑地址为32位，其中高16位为段号，低16位为段内偏移，以下是段表(其中的数据均为十六进制，如表7-1所示)。以下是代码段的内容：试问：x的逻辑地址为10108，它的物理地址是多少?

以下说法正确的是()。Ⅰ．带头结点的循环双链表L为空的条件是：L->prior=L&&L->next==LⅡ．线性表的插入和删除总是伴随着大量数据的移动Ⅲ．只有删除静态链表的尾结点才不需要移动元素Ⅳ．若线性

在含有15个结点的平衡二叉树上，查找关键字为28(存在该结点)的结点，则依次比较的关键字有可能是()。

下列说法中错误的是()。

柴油发动机动力不足的原因有哪些?

根据归经学说，用辅料炮制药物，醋制入

A．峰电位B．阈电位C．负后电位D．局部电位E．正后电位刺激引起兴奋的基本条件是使跨膜电位达到

因身体或精神功能减退，丧失了谋求和保持一个适于就业机会由于损伤造成能力的受限，使人不能正常进行活动

下列有关票据记载事项的说法中，正确的是：

调查报告只限于从自身的实践活动中选取材料，提炼论点。()

下列有关物质和运动的说法，错误的是()。

日常生活中，有些人在服药时为图省事，将药片放人口中后，不喝水或仅喝一口水，再用力一咽，就算是服完药了。有些人认为这种服药方式是不可取的。以下哪项如果为真，最能支持这些人的观点?()

决策

通常认为，决定局域网特性的主要技术有3种，它们是传输介质和(60)。