一、单选题（50分，每小题10分）

1. 关于单链表，下列说法正确的是（　）。 {{ select(1) }}

• 单链表支持随机访问任意位置的元素
• 单链表的插入操作需要移动大量元素
• 单链表中每个结点包含数据域和指向下一个结点的指针
• 单链表的存储空间必须是连续的

2. 在带头结点的循环单链表中，判断链表是否为空的条件是（　）。 {{ select(2) }}

• head == NULL
• head->next == NULL
• head->next == head
• head == head->next

3. 已知待删除结点指针时，双向链表和单向链表删除操作的时间复杂度说法正确的是（　）。 {{ select(3) }}

• 双链表删除是O(1)，单链表删除是O(1)
• 双链表删除是O(n)，单链表删除是O(1)
• 双链表删除是O(1)，单链表删除是O(n)
• 双链表删除是O(n)，单链表删除是O(n)

4. 以下程序创建了一个只有一个结点的循环单链表，横线处应填写（　）。

struct Node { int data; Node* next; };
Node* createList(int value) {
    Node* head = new Node;
    head->data = value;
    ______;
    return head;
}

{{ select(4) }}

• head->next = nullptr
• head->next = head
• head = head->next
• head->next = NULL

5. 在双向循环链表中，要在结点p之前插入新结点s（均非空），以下指针操作正确的是（　）。 {{ select(5) }}

• s->next = p; s->prev = p->prev; p->prev->next = s; p->prev = s;
• s->next = p; p->prev = s; p->next = s; s->prev = p
• s->prev = p; s->next = p->next; p->next->prev = s; p->next = s
• s->prev = nullptr; s->next = p; p->prev = s

二、多选题（20分，每小题10分）

6. 以下关于链表的说法，正确的有（　）。 {{ multiselect(6) }}

• 单链表每个结点只存储指向下一个结点的指针
• 双向链表每个结点存储指向前一个和后一个结点的指针
• 循环链表的尾结点指向头结点
• 链表支持随机访问

7. 关于二分答案（二分枚举法），以下说法正确的有（　）。 {{ multiselect(7) }}

• 二分答案适用于答案具有单调性的问题
• 二分答案只能用于数组查找
• 使用二分答案前需要确定答案的上下界
• 二分答案可以用于求解最大值最小化或最小值最大化问题

三、判断题（30分，每小题10分）

8. 在单链表中，已知待删除结点指针，且不允许复制后继结点数据、需要释放被删结点内存时，可以在 O(1) 时间内完成删除。（　） {{ select(8) }}

• 正确
• 错误

9. 正确实现的循环链表中不存在空指针。（　） {{ select(9) }}

• 正确
• 错误

10. 以下递归函数的调用 f(5) 会返回 15。

int f(int n)
{ 
  if(n==0) 
    return 0; 
  return n+f(n-1); 
}

{{ select(10) }}

• 正确
• 错误