2. 计算机
  3. 若对一个链表最常用的操作是在末尾插入节点和删除尾节点，则采用仅设尾指针的单向循环链表(不含头节点)时，(65)。

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

admin2017-09-14  8
问题 若对一个链表最常用的操作是在末尾插入节点和删除尾节点，则采用仅设尾指针的单向循环链表(不含头节点)时，(65)。
选项 A、插入和删除操作的时间复杂度都为O(1)
B、插入和删除操作的时间复杂度都为O(n)
C、插入操作的时间复杂度为O(1)，删除操作的时间复杂度为O(n)
D、插入操作的时间复杂度为O(n)，删除操作的时间复杂度为O(1)
答案C
解析 设尾指针的单项循环链表(不含头节点)如图8—4所示：

设节点的指针域为next，新节点的指针为s，则在尾指针所指节点后插入节点的操作为：
S一>next=t一>next；t一>next=S；t=S；
也就是插入操作的时间复杂度为O(1)。
要删除尾指针所指节点，必须通过遍历操作找到尾节点的前驱节点，其操作序列如下：
if(t一>next==t)free(t)；
eiSe{
P=t一>next；
whiie(p一>next!=t)
p=p一>next；
P一>next=t一>next；
free(t
转载请注明原文地址:https://kaotiyun.com/show/XARZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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