问题 单项选择题

若对一个链表最常用的操作是在末尾插入结点和删除尾结点,则采用仅设尾指针的单向循环链表(不含头结点)时,______。

A.插入和删除操作的时间复杂度都为O(1)

B.插入和删除操作的时间复杂度都为O(n)

C.插入操作的时间复杂度为O(1),删除操作的时间复杂度为O(n)

D.插入操作的时间复杂度为O(n),删除操作的时间复杂度为O(1)

答案

参考答案:C

解析:本题考查数据结构与算法基础知识。 设尾指针的单向循环链表(不含头结点)如下图所示: 设结点的指针域为next,新结点的指针为s,则在尾指针所指结点后插入结点的操作为: 也就是插入操作的时间复杂度为O(1)。 要删除尾指针所指结点,必须通过遍历操作找到尾结点的前驱结点,其操作序列 如下: 也就是说,删除操作的时间复杂度为O(n)。

解答题
单项选择题 A3/A4型题