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

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

admin2013-05-11  14
问题 在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(53)。
选项 A、O(1)
B、O(n)
C、O(nlogn)
D、O(n2)
答案B
解析 本题主要考核有序单链表上的插入操作及算法分析。对数据结构的任何操作都不能改变其原有的结构特性。因此，在有序单链表中插入一个新结点后，仍然要保持它的有序性。插入操作的关键是查找插入位置，主要时间也是花在插入位置的查找上。n个结点的单链表，有，n+1个可能插入的位置，即第一个结点之前和每一个结点之后。在第一个结点之前插入，需比较一次；在第一个结点之后插入需比较两次；……；在第，n个结点之后插入需查找次。如果在每一个位罩上作插入的概率相等，即则在有序单链表上查找插入位置的平均比较次数为：
转载请注明原文地址:https://kaotiyun.com/show/xERZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)