在n个结点的线性表的数组表示中，以下算法的时间复杂度是O(1)的操作是( )。 Ⅰ．访问第i个结点(1＜=i＜=n)和求第i个结点的的直接前驱(2＜=i＜=n) Ⅱ．在最后一个结点后插入一个新的结点 Ⅲ．删除第一个结点 Ⅳ．在第i个结点后插入一个结点

admin2018-09-11 25

问题在n个结点的线性表的数组表示中，以下算法的时间复杂度是O(1)的操作是( )。
Ⅰ．访问第i个结点(1＜=i＜=n)和求第i个结点的的直接前驱(2＜=i＜=n)
Ⅱ．在最后一个结点后插入一个新的结点
Ⅲ．删除第一个结点
Ⅳ．在第i个结点后插入一个结点(1＜=i＜=n)

选项 A、仅Ⅰ
B、仅Ⅱ、Ⅲ
C、仅Ⅰ、Ⅱ
D、仅Ⅰ、Ⅱ、Ⅲ

答案C

解析 Ⅰ：由于线性表是用数组表示，即顺序存储，可以直接通过结点编号访问，所以Ⅰ的时间复杂度一定是O(1)。
Ⅱ：由于是在最后一个结点处插入一个结点，所以不需要移动元素，故时间复杂度为O(1)。
Ⅲ：删除第一个结点之后，需要将后续所有结点往前移动，所以时间复杂度为O(n)。
Ⅳ：由于i是不固定的，所以后续结点i+1，i+2，…，n-1，都需要向后移动，所以时间复杂度为O(n)。

转载请注明原文地址:https://kaotiyun.com/show/AvRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

在1875年宪法中关于法国立法权的叙述，不正确的是()。

1543年发表解剖学专著《人体结构论》的是()。

下列关于第二三次科技革命的说法，不正确的是()。

下面关于新经济政策的说法不正确的一项是()。

公元9～13世纪是西欧封建庄园的兴盛时期，典型的庄园采用()的剥削方式。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

某中央处理器的数据通路如图所示。MDR为内存数据寄存器，PC为程序计数器，IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释：为什么要设置T暂存器?(3)假定指

什么是单重分组和双重分组跳跃进位链?一个按3，5，3，5分组的双重分组跳跃进位链(最低位为第O位)，试问大组中产生的是哪几位进位?与4，4，4，4分组的双重分组跳跃进位链相比，试问产生全部进位的时间是否一致?为什么?

下列网络设备中，能够抑制广播风暴的是____。I．中继器Ⅱ．集线器Ⅲ．网桥Ⅳ．路由器

Herebothurbanandruralareashavegreatlyprofitedfromtherecenteconomicreforms.Mostoftheforeign-ownedbusinesses,

A．《内经》B．《金匮要略》C．《格致余论》D．《景岳全书·妇人归》E．《诸病源候论》

(　　)是将公司层次征收的公司税全部或部分地归集起来，减少股东个人就股息应缴纳的所得税。

在电子显微镜下，观察到植物细胞有丝分裂末期的赤道板位置聚集着许多小囊泡，这些小囊泡是()。

将n个人等可能地分配到N(n≤N)间房中去，试求下列事件的概率：A={某指定的n间房中各有1人}；B=(恰有n间房各有1人}；C={某指定的房中恰有m人}．

[*]

使用[【说明】中给出的词汇，将数据流图1-1中(1)～(4)处的数据流补充完整。数据流程图1-2中缺失了三条数据流，请指出这三条数据流的起点、终点和数据流名称。

软盘驱动器采用的磁头是(　　　)。

Whichofthefollowingsentencesexpressesapassivemeaning?

Ienjoyedmyselfsomuch_____IvisitedmyfriendsinParislastyear.

计算机408

学硕统考专业

在1875年宪法中关于法国立法权的叙述，不正确的是()。

1543年发表解剖学专著《人体结构论》的是()。

下列关于第二三次科技革命的说法，不正确的是()。

下面关于新经济政策的说法不正确的一项是()。

公元9～13世纪是西欧封建庄园的兴盛时期，典型的庄园采用()的剥削方式。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

某中央处理器的数据通路如图所示。MDR为内存数据寄存器，PC为程序计数器，IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释：为什么要设置T暂存器?(3)假定指

什么是单重分组和双重分组跳跃进位链?一个按3，5，3，5分组的双重分组跳跃进位链(最低位为第O位)，试问大组中产生的是哪几位进位?与4，4，4，4分组的双重分组跳跃进位链相比，试问产生全部进位的时间是否一致?为什么?

下列网络设备中，能够抑制广播风暴的是____。I．中继器Ⅱ．集线器Ⅲ．网桥Ⅳ．路由器

Herebothurbanandruralareashavegreatlyprofitedfromtherecenteconomicreforms.Mostoftheforeign-ownedbusinesses,

A．《内经》B．《金匮要略》C．《格致余论》D．《景岳全书·妇人归》E．《诸病源候论》

( )是将公司层次征收的公司税全部或部分地归集起来，减少股东个人就股息应缴纳的所得税。

在电子显微镜下，观察到植物细胞有丝分裂末期的赤道板位置聚集着许多小囊泡，这些小囊泡是()。

将n个人等可能地分配到N(n≤N)间房中去，试求下列事件的概率：A={某指定的n间房中各有1人}；B=(恰有n间房各有1人}；C={某指定的房中恰有m人}．

[*]

使用[【说明】中给出的词汇，将数据流图1-1中(1)～(4)处的数据流补充完整。数据流程图1-2中缺失了三条数据流，请指出这三条数据流的起点、终点和数据流名称。

软盘驱动器采用的磁头是( )。

Whichofthefollowingsentencesexpressesapassivemeaning?

Ienjoyedmyselfsomuch_____IvisitedmyfriendsinParislastyear.

　　Herebothurbanandruralareashavegreatlyprofitedfromtherecenteconomicreforms.Mostoftheforeign-ownedbusinesses,

(　　)是将公司层次征收的公司税全部或部分地归集起来，减少股东个人就股息应缴纳的所得税。

软盘驱动器采用的磁头是(　　　)。