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

admin2022-06-07 64

问题在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，1+2，…，n—1，都需要向后移动，所以时间复杂度为O(n)。

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

利用海明码纠正2比特的错误，那么海明距为()。

某机器字长为16位，主存容量为1M×16位，有63种指令，CPU有PC，IR，AR，DR4个基址寄存器和4个变址寄存器，16个通用寄存器。(1)请设计合适字长的二地址(RS型)指令，其中一个操作数有4种寻址方式；(2)说明各寄存器合适的位数

采用简单选择排序，比较次数与移动次数分别是()。

条件转移指令执行时所依据的条件来自()。

一个64位的计算机系统中，地址线宽为64位，实际使用的虚拟地址空间的大小是248，若采用虚拟页式存储管理，每页的大小为213，即8KB，页表表项长为8字节，采用多级页表进行管理，那么，多级页表的级次最小是()。

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

为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是____。

下列选项中，导致创建新进程的操作是____。I．用户登录成功Ⅱ．设备分配Ⅲ．启动程序执行

浮点加、减中的对阶应()。

在行政诉讼中，适用简易程序审理的行政案件，应当在立案之日起（）内审结。

输气场站的防护栏杆按涂色要求应为()色。

病毒性肺炎的特点不包括

三联根除Hp治疗失败者，应选用下列哪种方案

气滞心胸的胸痛特点是

低温长时间巴氏消毒法的起始温度是多少

金融市场上由于金融工具价格的波动而带来的风险称之为(　　)。

网络体育资源()

初中学生思维的特点属于()。

计算机408

学硕统考专业

利用海明码纠正2比特的错误，那么海明距为()。

某机器字长为16位，主存容量为1M×16位，有63种指令，CPU有PC，IR，AR，DR4个基址寄存器和4个变址寄存器，16个通用寄存器。(1)请设计合适字长的二地址(RS型)指令，其中一个操作数有4种寻址方式；(2)说明各寄存器合适的位数

采用简单选择排序，比较次数与移动次数分别是()。

条件转移指令执行时所依据的条件来自()。

一个64位的计算机系统中，地址线宽为64位，实际使用的虚拟地址空间的大小是248，若采用虚拟页式存储管理，每页的大小为213，即8KB，页表表项长为8字节，采用多级页表进行管理，那么，多级页表的级次最小是()。

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

为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是____。

下列选项中，导致创建新进程的操作是____。I．用户登录成功Ⅱ．设备分配Ⅲ．启动程序执行

浮点加、减中的对阶应()。

在行政诉讼中，适用简易程序审理的行政案件，应当在立案之日起（）内审结。

输气场站的防护栏杆按涂色要求应为()色。

病毒性肺炎的特点不包括

三联根除Hp治疗失败者，应选用下列哪种方案

气滞心胸的胸痛特点是

低温长时间巴氏消毒法的起始温度是多少

金融市场上由于金融工具价格的波动而带来的风险称之为( )。

网络体育资源()

初中学生思维的特点属于()。

金融市场上由于金融工具价格的波动而带来的风险称之为(　　)。