2. 计算机
  3. 单向循环链表如下图所示，以下关于单向循环链表的叙述中，正确的是_________。

单向循环链表如下图所示，以下关于单向循环链表的叙述中，正确的是_________。

admin2021-03-24  74
问题 单向循环链表如下图所示，以下关于单向循环链表的叙述中，正确的是_________。
      
选项 A、仅设头指针时，遍历单向循环链表的时间复杂度是O(1)
B、仅设尾指针时，遍历单向循环链表的时间复杂度是O(1)
C、仅设头指针时，在表尾插入一个新元素的时间复杂度是O(n)
D、仅设尾指针时，在表头插入一个新元素的时间复杂度是O(n)
答案C
解析 在单链表存储结构中，任何情况下实现遍历(即遍访表中的所有元素)时间复杂度都是O(n)。
    在单链表任何位置插入或删除结点，首先需要找到插入位置，该查找运算的时间复杂度可能是O(n)或D(1)，然后用O(1)复杂度的运算实现插入。
    在单向循环链表的表尾插入一个新元素时，需要修改表尾结点的指针域，若仅设头指针时，则需要遍历表中所有结点才能找到表尾结点，因此时间复杂度为O(n)。
    在单向循环链表的表头插入一个新元素时，需要修改表头结点(含头结点时)或表尾结点(不含头结点时)的指针域，仅设尾指针时，可以通过简单运算(即时间复杂度O(1))获得第一个结点的指针信息，再进行插入结点操作。
转载请注明原文地址:https://kaotiyun.com/show/v6NZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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