CSP-J 卷

链表不具有的特点是（ ）。

链表和数组的区别包括（ ）。

假设有一个链表的节点定义如下：

01struct Node {
02    int data;
03    Node* next;
04};

现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员 data 的值为 42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？（ ）

在 C++ 中，通过恰当的实现，可以将链表首尾相接，形成循环链表。

如果将双向链表的最后一个结点的下一项指针指向第一个结点，第一个结点的前一项指针指向最后一个结点，则该双向链表构成循环链表。

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

链表的存储空间物理上可以连续，也可以不连续。

下面关于链表和数组的描述，错误的是（ ）。

在循环单链表中，节点的 next 指针指向下一个节点，最后一个节点的 next 指针指向（ ）。

单链表只支持在表头进行插入和删除操作。

链表不具备的特点是（ ）。

链表存储线性表时要求内存中可用存储单元地址是连续的。

与数组相比，链表在（ ）操作上通常具有更高的效率。

以下哪种情况使用链表比数组更合适？

以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）：（ ）。

有关下面代码的说法正确的是（ ）。

01#include <iostream>
02
03class Node {
04public:
05    int Value;
06    Node * Next;
07
08    Node(int Val, Node * Nxt = nullptr) {
09        Value = Val;
10        Next = Nxt;
11    }
12};
13
14int main() {
15    Node * firstNode = new Node(10);
16    firstNode->Next = new Node(100);
17    firstNode->Next->Next = new Node(111, firstNode);
18    return 0;
19}

有关下面 C++ 代码的说法正确的是（ ）。

01class Node
02{
03public:
04    int Value;
05    Node* Prev;
06    Node* Next;
07    Node(int Val, Node* Prv = NULL, Node* Nxt = NULL);
08};
09
10Node::Node(int Val, Node*Prv, Node* Nxt)
11{
12    this->Value = Val;
13    this->Prev = Prv;
14    this->Next = Nxt;
15}
16
17int main()
18{
19    Node firstNode = Node(10);
20    firstNode.Next = new Node(100, &firstNode);
21    firstNode.Next->Next = new Node(111, firstNode.Next);
22}

同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。

下面的代码片段用于在双向链表中删除一个节点。请在横线处填入（ ），使其能正确实现相应功能。

01void deleteNode(DoublyListNode*& head, int value) {
02    DoublyListNode* current = head;
03    while (current != nullptr && current->val != value) {
04        current = current->next;
05    }
06    if (current != nullptr) {
07        if (current->prev != nullptr) {
08            ____________ // 在此处填入代码
09        } else {
10            head = current->next;
11        }
12        if (current->next != nullptr) {
13            current->next->prev = current->prev;
14        }
15        delete current;
16    }
17}

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

小杨采用如下双链表结构保存他喜欢的歌曲列表：

01struct dl_node {
02    string song;
03    dl_node* next;
04    dl_node* prev;
05};

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

01dl_node* search(dl_node* head, string my_song) {
02    dl_node* temp = head;
03    while (temp != nullptr) {
04        if (temp->song == my_song)
05            return temp;
06        temp = temp->next;
07    }
08    return nullptr;
09}

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

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

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

01struct LinkedNode {
02    int val;
03    LinkedNode* next;
04    LinkedNode(int val):val(val), next(nullptr){}
05};
06
07void removeElements(LinkedNode* head, int val) {
08    if (head == nullptr) {
09        return;
10    }
11    LinkedNode* cur;
12    LinkedNode* dummyHead = new LinkedNode(0); //虚拟头节点
13    ____________      // 在此处填入代码
14
15    while(cur ->next ! = nullptr) {
16        if(cur->next->val == val) {
17            LinkedNode* tmp = cur->next;
18            cur->next = cur->next->next;
19            delete tmp;
20            tmp = nullptr;
21        }
22        else {
23            cur = cur ->next;
24        }
25    }
26    head = dummyHead->next;
27    delete dummyHead;
28    dummyHead = nullptr;
29}

二分查找仅适用于数组而不适合链表，因为二分查找需要跳跃式访问元素，链表中执行跳跃式访问的效率低。

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

假设双向循环链表包含头尾哨兵结点（不存储实际内容），分别为 head 和 tail，链表中每个结点有两个指针域 prev 和 next，分别指向该结点的前驱及后继结点。下面代码实现了一个空的双向循环链表，横线上应填的最佳代码是（ ）。

01// 链表结点
02template <typename T>
03struct ListNode {
04    T data;
05    ListNode* prev;
06    ListNode* next;
07    // 构造函数
08    explicit ListNode(const T& val = T())
09        : data(val), prev(nullptr), next(nullptr) {}
10};
11
12struct LinkedList {
13    ListNode<T>* head;
14    ListNode<T>* tail;
15};
16
17void InitLinkedList(LinkedList* list) {
18    list->head = new ListNode<T>;
19    list->tail = new ListNode<T>;
20    ____________      // 在此处填入代码
21}

要删除单链表中某个结点 p（非尾结点），但不知道头结点，可行的操作是将 p->next 的数据拷贝到 p 的数据，将 p->next 设置为 p->next->next，然后删除 p->next。

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

01// 节点结构体
02struct Node {
03    int data;
04    Node* prev;
05    Node* next;
06};
07
08// 双向链表结构体
09struct DoubleLink {
10    Node* head;
11    Node* tail;
12    int size;
13
14    DoubleLink() {
15        head = nullptr;
16        tail = nullptr;
17        size = 0;
18    }
19
20    ~DoubleLink() {
21        Node* curr = head;
22        while (curr) {
23            Node* next = curr->next;
24            delete curr;
25            curr = next;
26        }
27    }
28
29    // 判断链表是否为空
30    bool is_empty() const {
31        ____________
32    }
33};

在双向链表尾部增加新节点的 append() 函数中，横线上应填写（ ）。

01void append(int data) {
02    Node* newNode = new Node(data, nullptr, nullptr);
03
04    if (is_empty()) {
05        head = tail = newNode;
06    } else {
07        ____________
08    }
09    ++size;
10}

函数 removeElements 删除单链表中所有结点值等于 val 的结点，并返回新的头结点，其中链表头结点为 head，则横线处填写（ ）。

01// 结点结构体
02struct Node {
03    int val;
04    Node* next;
05    Node() : val(0), next(nullptr) {}
06    Node(int x) : val(x), next(nullptr) {}
07    Node(int x, Node *next) : val(x), next(next) {}
08};
09
10Node* removeElements(Node* head, int val) {
11    Node dummy(0, head);        // 哑结点，统一处理头结点
12    Node* cur = &dummy;
13    while (cur->next) {
14        if (cur->next->val == val) {
15            ____________        // 在此填入代码
16        }
17        else {
18            cur = cur->next;
19        }
20    }
21    return dummy.next;
22}

链表通过更改指针实现高效的结点插入与删除，但结点访问效率低、占用内存较多，且对缓存利用不友好。

对如下定义的循环单链表，横线处填写（ ）。

01// 循环单链表的结点
02struct Node {
03    int data;        // 数据域
04    Node* next;      // 指针域
05
06    Node(int d) : data(d), next(nullptr) {}
07};
08
09// 创建一个只有一个结点的循环单链表
10Node* createList(int value) {
11    Node* head = new Node(value);
12    head->next = head;
13    return head;
14}
15
16// 在循环单链表尾部插入新结点
17void insertTail(Node* head, int value) {
18    Node* p = head;
19    while (p->next != head) {
20        p = p->next;
21    }
22    Node* node = new Node(value);
23    node->next = head;
24    p->next = node;
25}
26
27// 遍历并输出循环单链表
28void printList(Node* head) {
29    if (head == nullptr) return;
30
31    Node* p = head;
32    ____________      // 在此处填入代码
33    cout << endl;
34}

$N$ 个节点的双向循环链，在其中查找某个节点的平均时间复杂度是（ ）。

有关下面 C++ 代码的说法正确的是（ ）。

01typedef struct LinkList {
02    int data;
03
04    LinkList* next;
05
06    LinkList* prev;
07
08}LinkList,LinkNode;
09bool ListInit(LinkList* &L) {
10
11    L = new LinkNode;
12    if (!L)return false;
13
14    L->next = NULL;
15    L->prev = NULL;
16    L->data = -1;
17
18    return true;
19
20}