违法和不良信息举报 联系客服
免费注册 登录

在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是（）A、O（1）B、O（n）C、O（n2）D、O（log2n）

题目

在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是（）

  • A、O（1）
  • B、O（n）
  • C、O（n2）
  • D、O（log2n）
如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

建立一个长度为n的有序单链表的时间复杂度为()。

A、O(n)

B、O(1)

C、O(n)2

D、O(log2n)


参考答案：C

第2题：

在二叉排序树中插入一个结点的时间复杂度为()。

A、O(1)

B、O(n)

C、O(log2n)

D、O(n)


参考答案：B

第3题：

在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是()。

A、O(1)

B、O(n)

C、O(n㏒n)

D、O(n2)


正确答案:B

第4题：

在具有n个结点的单链表上查找值为y的元素时,其时间复杂度为()。

A、O(n)

B、O(1)

C、O(n2)

D、O(n-1)


参考答案：A

第5题：

在一个具有n个结点的有序顺序表中插入一个新结点并仍然保持有序的时间复杂度是()

A、O(1)

B、O(n)

C、O(n2)


参考答案：B

第6题：

●在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是 (53) 。

(53) A．O(1)

B．O(n)

C．O(nlogn)

D．O(n2)


正确答案：B

【解析】本题主要考核有序单链表上的插入操作及算法分析。对数据结构的任何操作都不能改变其原有的结构特性。因此，在有序单链表中插入一个新结点后，仍然要保持它的有序性。
插入操作的关键是查找插入位置，主要时间也是花在插入位置的查找上。n个结点的单链表，有，n+1个可能插入的位置，即第一个结点之前和每一个结点之后。在第一个结点之前插入，需比较一次；在第一个结点之后插入需比较两次；…；在第，n个结点之后插入需查找次。如果在每一个位置上作插入的概率相等，即 ，则在有序单链表上查找插入位置的平均比较次数为：


 

第7题：

创建一个包括n个结点的有序单链表的时间复杂度是()。

A.O(1)

B、O(n)

C、O(n2)

D、O(nlog2n)


参考答案：C
解释：单链表创建的时间复杂度是O(n)，而要建立一个有序的单链表，则每生成一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是O(n2)。

第8题：

在二叉排序树中插入一个结点的时间复杂度为()。

A、O(1)

B、O(n)

C、O(log2n)

D、O(n2)


参考答案：B

第9题：

在具有n个结点的顺序表上查找值为y的元素时,其时间复杂度为()。

A、O(n)

B、O(1)

C、O(n2)

D、O(log2n)


参考答案：A

第10题：

在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是()。

A、O(1)

B、O(n)

C、O(n的平方)

D、O(log2n)


参考答案：B

更多相关问题
相关内容