国家电网招聘
设一个有序的单链表中有n个节点，现要求插入一个新节点后使得单链表仍然保持有序，则该操作的时间复杂度为()。
题目
相似问题和答案
第1题：
在一个长度为n（n＞1）的单链表上，设有头和尾两个指针，执行()操作与链表的长度有关。
A.删除单链表中的第一个元素
B.删除单链表中的最后一个元素
C.在单链表第一个元素前插入一个新元素
D.在单链表最后一个元素后插入一个新元素
第2题：
A.O(1)
B、O(n)
C、O(n2)
D、O(nlog2n)
解释：单链表创建的时间复杂度是O(n)，而要建立一个有序的单链表，则每生成一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是O(n2)。
第3题：
A、O(1)
B、O(n)
C、O(n㏒n)
D、O(n2)
第4题：
A.删除单链表中的第一个元素
B.删除单链表中的尾结点
C.在单链表的第一个元素前插入一个新结点
D.在单链表的最后一个元素后插入一个新结点
第5题：
A、O(1)
B、O(n)
C、O(n的平方)
D、O(log2n)
第6题：
●在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是 (53) 。
(53) A．O(1)
B．O(n)
C．O(nlogn)
D．O(n2)
【解析】本题主要考核有序单链表上的插入操作及算法分析。对数据结构的任何操作都不能改变其原有的结构特性。因此，在有序单链表中插入一个新结点后，仍然要保持它的有序性。
插入操作的关键是查找插入位置，主要时间也是花在插入位置的查找上。n个结点的单链表，有，n+1个可能插入的位置，即第一个结点之前和每一个结点之后。在第一个结点之前插入，需比较一次；在第一个结点之后插入需比较两次；…；在第，n个结点之后插入需查找次。如果在每一个位置上作插入的概率相等，即
，则在有序单链表上查找插入位置的平均比较次数为：
第7题：
A、访问第i个节点(1≤i≤n)
B、在第i个节点后插入一个新节点(1≤i≤n)
C、访问值为x的节点
D、将n个节点从小到大排序
第8题：
A、O(n)
B、O(1)
C、O(n)2
D、O(log2n)
第9题：
若某链表最常用的操作是在最后一个节点之后插入一个节点和删除最后一个节点，则采用______存储方式最节省时间。
A．单链表
B．双链表
C．单循环链表
D．带头节点的双循环链表
第10题：
