链表（共 18 题）

单选题

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

• 在单链表中，若已知任意结点的指针，则可以在 O(1) 时间内删除该结点。
• 循环链表中一定不存在空指针。
• 在循环双链表中，尾结点的 next 指针一定为 nullptr。
• 在带头结点的循环单链表中，判定链表是否为空只需判断头结点的 next 是否指向自身。

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

• 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->next = p; s->prev = p->prev; p->prev->next = s; p->prev = s;
• s->next = p; s->prev = nullptr; p->prev = s;

3. 下面函数用“哑结点”统一处理删除单向链表中的头结点与中间结点。横线处应填（ ）。

   Node* eraseAll(Node* head, int x){
       Node dummy(0);
       dummy.next = head;
       Node* cur = &dummy;
       while(cur->next){
           if(cur->next->val == x){
               Node* del = cur->next;
               __________________;
               delete del;
           } else cur = cur->next;
       }
       return dummy.next;
   }
   

   {{ select(3) }}

• cur = cur->next;
• cur->next = del->next;
• del->next = cur->next;
• cur->next = nullptr;

4. 小杨想在头指针为 head 的双链表中查找他喜欢的某首歌曲，采用如下查询函数，该操作的时间复杂度为（ ）。

   dl_node* search(dl_node* head, string my_song) {
       dl_node* temp = head;
       while (temp != nullptr) {
           if (temp->song == my_song) return temp;
           temp = temp->next;
       }
       return nullptr;
   }
   

   {{ select(4) }}

• O(1)
• O(n)
• O(log n)
• O(n²)

5. 小杨想在双向链表中加入一首新歌曲。为了能快速找到该歌曲，他将其作为链表的第一首歌曲，则下面横线上应填入的代码为（ ）。

   void insert(dl_node *head, string my_song) {
       p = new dl_node;
       p->song = my_song;
       p->prev = nullptr;
       p->next = head;
       if (head != nullptr) {
           __________________;
       }
       head = p;
   }
   

   {{ select(5) }}

• head->next->prev = p;
• head->next = p;
• head->prev = p;
• 触发异常，不能对空指针进行操作。

6. 下面关于链表和数组的描述，错误的是（ ）。
   {{ select(6) }}

• 当数据数量不确定时，为了应对各种可能的情况，需要申请一个较大的数组，可能浪费空间；此时用链表比较合适，大小可动态调整。
• 在链表中访问节点的效率较低，时间复杂度为 O(n)。
• 链表插入和删除元素效率较低，时间复杂度为 O(n)。
• 链表的节点在内存中是分散存储的，通过指针连在一起。

7. 在循环单链表中，节点的 next 指针指向下一个节点，最后一个节点的 next 指针指向（ ）。
   {{ select(7) }}

• 当前节点
• nullptr
• 第一个节点
• 上一个节点

8. 为了方便链表的增删操作，一些算法生成一个虚拟头节点，方便统一删除头节点和其他节点。下面代码实现了删除链表中值为 val 的节点，横线上应填的最佳代码是（ ）。

   struct LinkedList {
       int val;
       LinkedList* next;
       LinkedList(int val):val(val), next(nullptr){}
       void removeElements(LinkedList* head, int val) {
           if (head == nullptr) return;
           LinkedList* cur;
           LinkedList* dummyHead = new LinkedList(0);
           __________________;
           while(cur->next != nullptr) {
               if(cur->next->val == val) {
                   LinkedList* tmp = cur->next;
                   cur->next = cur->next->next;
                   delete tmp;
                   tmp = nullptr;
               } else {
                   cur = cur->next;
               }
           }
           head = dummyHead->next;
           delete dummyHead;
           dummyHead = nullptr;
       }
   };
   

   {{ select(8) }}

• dummyHead->next = head; cur = dummyHead;
• dummyHead->next = head->next; cur = dummyHead;
• dummyHead->next = head; cur = dummyHead->next;
• dummyHead->next = head->next; cur = dummyHead->next;

9. 下面关于链表和数组的描述，错误的是（ ）。
   {{ select(9) }}

• 数组大小固定，链表大小可动态调整。
• 数组支持随机访问，链表只能顺序访问。
• 存储相同数目的整数，数组比链表所需的内存多。
• 数组插入和删除元素效率低，链表插入和删除元素效率高。

10. 通过（ ）操作，能完成在双向循环链表结点 p 之后插入结点 s 的功能（其中 next 域为结点的直接后继，prev 域为结点的直接前驱）。
    {{ select(10) }}

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

11. 链表不具备的特点是（ ）。
    {{ select(11) }}

• 可随机访问任何一个元素
• 插入、删除操作不需要移动元素
• 无需事先估计存储空间大小
• 所需存储空间与存储元素个数成正比

12. 双向链表中每个结点有两个指针域 prev 和 next，分别指向该结点的前驱及后继结点。设 p 指向链表中的一个结点，它的前驱结点和后继结点均非空。要删除结点 p，则下述语句中错误的是（ ）。
    {{ select(12) }}

• p->next->prev = p->next; p->prev->next = p->prev; delete p;
• p->prev->next = p->next; p->next->prev = p->prev; delete p;
• p->next->prev = p->prev; p->next->prev->next = p->next; delete p;
• p->prev->next = p->next; p->prev->next->prev = p->prev; delete p;

13. 与数组相比，链表在（ ）操作上通常具有更高的效率。
    {{ select(13) }}

• 随机访问元素
• 查找指定元素
• 在已知位置插入或删除节点
• 遍历所有元素

14. 下面 C++ 代码实现双向链表。函数 is_empty() 判断链表是否为空，如链表为空返回 true，否则返回 false。横线处不能填写（ ）。

    struct DoubleLink {
        Node* head;
        Node* tail;
        int size;
        bool is_empty() const {
            __________________;
        }
    };
    

    {{ select(14) }}

• return head == nullptr;
• return tail == nullptr;
• return head.data == 0;
• return size == 0;

15. 基于上题代码正确的前提下，填入相应代码完善 append()，用于在双向链表尾部增加新节点，横线上应填写（ ）。

    void append(int data) {
        Node* newNode = new Node(data, nullptr, nullptr);
        if (is_empty()) {
            head = tail = newNode;
        } else {
            __________________;
        }
        ++size;
    }
    

    {{ select(15) }}

• tail->next = newNode;
• newNode->prev = tail; tail = newNode;
• tail = newNode; newNode->prev = tail; tail->next = newNode;
• tail->next = newNode; newNode->prev = tail; tail = newNode;

判断题

16. 如果将双向链表的最后一个结点的 next 指针指向第一个结点，第一个结点的 prev 指针指向最后一个结点，则该双向链表构成循环链表。
    {{ select(16) }}

• 正确
• 错误

17. 数组和链表都是线性表，链表的优点是插入删除不需要移动元素，并且能随机查找。
    {{ select(17) }}

• 正确
• 错误

18. 单链表只支持在表头进行插入和删除操作。
    {{ select(18) }}

• 正确
• 错误

19. 链表的存储空间物理上可以连续，也可以不连续。
    {{ select(19) }}

• 正确
• 错误

20. 在操作系统中，需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
    {{ select(20) }}

• 正确
• 错误

21. 单链表和双链表都可以在常数时间内实现在链表头部插入或删除节点的操作。
    {{ select(21) }}

• 正确
• 错误

22. 在单链表中，已知指针 p 指向要删除的结点（非尾结点），想在 O(1) 删除 p，可行做法是用 p->next 覆盖 p 的值与 next，然后删除 p->next。
    {{ select(22) }}

• 正确
• 错误

---