在一个具有n个结点的有序单链表中插入一个新结点，并保持有序，其算法的时间复杂度为
A、n/2
B、n
C、O(n/2)
D、O(n)
【正确答案】：D
【题目解析】：本题考查数据结构基础知识。 在具有n个结点的有序单链表中插入一个新结点时，插入操作本身仅需要修改两个指针，时间主要消耗在顺序地比对需插入的元素与表中元素的大小，从而确定其插入位置。若要插入的元素小于表中的最小元素，则插入该元素时与表中的一个元素进行比较，若要插入的元素大于表中的最大元素，则需要与表中的n个元素全部比较一遍。 因此，单链表中参与比较的元素个数平均为(1+2+…+n+n)/(n+l)，即该操作的时间复杂度为O(n)。
