2. 从业资格
  3. 若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环

若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环

资格题库2022-08-02  18
问题 若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环链表（不含头结点）时，（　　）。A.插入和删除操作的时间复杂度都为O（1）B.插入和删除操作的时间复杂度都为O（n）C.插入操作的时间复杂度为O（1），删除操作的时间复杂度为O（n）D.插入操作的时间复杂度为O（n），删除操作的时间复杂度为O（1）
选项 A.插入和删除操作的时间复杂度都为O（1）
B.插入和删除操作的时间复杂度都为O（n）
C.插入操作的时间复杂度为O（1），删除操作的时间复杂度为O（n）
D.插入操作的时间复杂度为O（n），删除操作的时间复杂度为O（1）
答案 C
解析 本题考查数据结构与算法基础知识。设尾指针的单向循环链表（不含头结点）如下图所示：设结点的指针域为next，新结点的指针为s，则在尾指针所指结点后插入结点的操作为：s->next＝t->next；t-＞next＝s；t＝s；也就是插入操作的时间复杂度为O(1)。要删除尾指针所指结点，必须通过遍历操作找到尾结点的前驱结点.其操作序列如下：If(t->next==t)free(t)；else｛p=t->next；while(P->next！=t)p=p->next；p->next=t->next;free(t);t=p；}也就是说，删除操作的时间复杂度为O(n)。
转载请注明原文地址:https://www.tihaiku.com/congyezige/2409460.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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