链表结构复习

AI悦创原创2024年5月20日大约 11 分钟...约 3289 字

1. 单链表练习

1.1 选择题

单链表的遍历结束的标志是：
- A. 链表为空
- B. 链表的当前节点为空
- C. 链表的当前节点的指针域为空
- D. 链表的头节点为空
在单链表中插入一个节点时，正确的操作是：
- A. 只需要修改新节点的指针
- B. 修改新节点的指针，然后修改前一个节点的指针
- C. 先修改前一个节点的指针，然后修改新节点的指针
- D. 无需修改指针

1.2 填空题

在单链表中删除一个节点时，需要将______的指针域指向______。
单链表的头指针指向链表的______节点。
如果单链表的头节点包含数据域和指针域，那么头节点的指针域指向链表的______节点。

1.3 编程题

编写一个函数，用于创建一个单链表，链表节点结构包含一个整型数据域和一个指向下一个节点的指针。
编写一个函数，用于在单链表的第i个位置插入一个值为x的新节点。
编写一个函数，用于删除单链表中所有值为x的节点。
编写一个函数，用于逆转一个单链表。
编写一个函数，用于合并两个已排序的单链表成一个新的已排序链表。

答案

选择题答案

C. 链表的当前节点的指针域为空
链表的遍历通常结束于当前节点的指针域指向NULL，表示没有更多的节点。
C. 先修改前一个节点的指针，然后修改新节点的指针
插入节点时，先将前一个节点的指针指向新节点，然后将新节点的指针指向原来前一个节点所指向的节点。

填空题答案

在单链表中删除一个节点时，需要将前一个节点的指针域指向被删除节点的下一个节点。
单链表的头指针指向链表的第一个节点。
如果单链表的头节点包含数据域和指针域，那么头节点的指针域指向链表的第一个实际节点。

编程题答案

以下是 C 语言代码示例：

创建单链表：

struct Node {
    int data;
    struct Node* next;
};

struct Node* createList(int* arr, int n) {
    struct Node *head = NULL, *temp = NULL, *p = NULL;
    for (int i = 0; i < n; i++) {
        temp = (struct Node*)malloc(sizeof(struct Node));
        temp->data = arr[i];
        temp->next = NULL;
        if (head == NULL) {
            head = temp;
        } else {
            p->next = temp;
        }
        p = temp;
    }
    return head;
}

在第i个位置插入值x：

void insertNode(struct Node** head, int i, int x) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->next = NULL;

    if (*head == NULL || i == 0) {
        newNode->next = *head;
        *head = newNode;
    } else {
        struct Node* temp = *head;
        for (int pos = 0; pos < i - 1 && temp != NULL; pos++) {
            temp = temp->next;
        }
        newNode->next = temp->next;
        temp->next = newNode;
    }
}

删除所有值为x的节点：

void deleteAllX(struct Node** head, int x) {
    struct Node *temp = *head, *prev = NULL;
    while (temp != NULL) {
        if (temp->data == x) {
            if (prev == NULL) {
                *head = temp->next;
            } else {
                prev->next = temp->next;
            }
            struct Node *next = temp->next;
            free(temp);
            temp = next;
        } else {
            prev = temp;
            temp = temp->next;
        }
    }
}

逆转单链表：

void reverseList(struct Node** head) {
    struct Node *prev = NULL, *current = *head, *next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *head = prev;
}

合并两个排序链表：

struct Node* mergeSortedLists(struct Node* l1, struct Node* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1->data < l2->data) {
        l1->next = mergeSortedLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeSortedLists(l1, l2->next);
        return l2;
    }
}

1.4 选择题2

单链表插入一个新节点的时间复杂度是：
- A. O(1)
- B. O(n)
- C. O(log n)
- D. O(n^2)
如果一个单链表的头节点不含任何数据，此种类型的链表被称为：
- A. 循环链表
- B. 双向链表
- C. 带头节点的链表
- D. 无头节点的链表
在单链表中，以下哪个操作不能在O(1)时间内完成？
- A. 删除头节点后的第一个节点
- B. 删除尾节点
- C. 在头节点后插入一个新节点
- D. 更改头节点的数据
当使用单链表存储稀疏矩阵时，通常使用什么结构来优化存储空间？
- A. 循环链表
- B. 双向链表
- C. 静态链表
- D. 十字链表
如果需要频繁地添加和删除链表的头部元素，应优先考虑使用：
- A. 单链表
- B. 双向链表
- C. 循环单链表
- D. 循环双向链表
对于一个无头节点的单链表，检测链表中是否存在环的算法是：
- A. 插入排序
- B. 归并排序
- C. 快慢指针
- D. 二分查找
单链表中删除指定值的所有节点最好的方法是：
- A. 使用一个辅助栈
- B. 在删除操作前后反转链表
- C. 使用双指针技术
- D. 递归删除
单链表的哪种操作可能会导致内存泄漏？
- A. 只删除节点，不释放内存
- B. 只修改指针，不移动节点
- C. 更新所有节点的数据域
- D. 遍历链表
使用单链表实现队列和使用数组实现队列的一个关键区别是：
- A. 单链表允许更快的随机访问
- B. 数组实现可以动态调整大小
- C. 单链表提供更灵活的内存使用
- D. 数组提供更快的插入操作
当前节点有两个指针，一个指向下一个节点，另一个随机指向链表中的任一节点或为空，这种链表类型是：
- A. 单链表
- B. 双向链表
- C. 循环链表
- D. 复杂链表

答案

选择题答案及解释

B. O(n)
- 插入一个新节点的时间复杂度通常是O(n)，因为需要遍历链表找到插入位置的前一个节点。如果插入位置是已知的（如头部或尾部），则时间复杂度可以是O(1)。
C. 带头节点的链表
- 带头节点的链表中，头节点不包含实际的数据，仅作为指向链表第一个实际数据节点的指针，这样可以简化链表操作，如插入和删除操作。
B. 删除尾节点
- 删除尾节点不能在O(1)时间内完成，因为需要遍历整个链表以找到倒数第二个节点，并修改其指针指向null。
D. 十字链表
- 稀疏矩阵通常使用十字链表存储，该结构可以有效地存储非零元素，减少空间浪费。
C. 循环单链表
- 对于频繁地添加和删除链表头部元素的场景，循环单链表是更好的选择，因为它允许从链表尾部直接访问头部，使得操作更为高效。
C. 快慢指针
- 快慢指针是检测链表中是否存在环的一种常用方法。快指针每次移动两步，慢指针每次移动一步，如果链表中存在环，它们最终会相遇。
C. 使用双指针技术
- 使用双指针（一个前导指针和一个当前操作指针）可以有效地在一次遍历中删除所有具有指定值的节点。
A. 只删除节点，不释放内存
- 如果删除节点后不释放其内存，可能会导致内存泄漏，特别是在频繁进行插入和删除操作的应用中。
C. 单链表提供更灵活的内存使用
- 单链表相较于数组，可以更灵活地使用内存，因为它不需要在创建时指定固定的大小，且可以根据需要动态地分配和释放内存。
D. 复杂链表
- 复杂链表或者叫做带有随机指针的链表，其中每个节点除了有一个指向下一个节点的指针外，还有一个指向链表中任意节点或空的随机指针。

2. 双向链表

2.1 选择题

在双链表中，每个节点包含几个指针？
- A. 1
- B. 2
- C. 3
- D. 4
在双链表中插入新节点的时间复杂度是多少？
- A. O(1)
- B. O(n)
- C. O(log n)
- D. O(n^2)
双链表的删除操作相比单链表的优势是什么？
- A. 更快的查找时间
- B. 更少的内存使用
- C. 不需要前驱节点的信息
- D. 更简单的实现
双链表允许哪种类型的遍历？
- A. 只能从头到尾
- B. 只能从尾到头
- C. 从头到尾或从尾到头
- D. 随机访问任何节点
双链表通常不适用于哪种情况？
- A. 需要双向遍历的情况
- B. 需要节省空间的情况
- C. 数据频繁插入和删除
- D. 实现一个队列
在一个空的双链表中插入第一个节点后, 头指针和尾指针会如何变化？
- A. 只有头指针指向新节点
- B. 只有尾指针指向新节点
- C. 头指针和尾指针都指向新节点
- D. 头指针和尾指针都不改变
如果要在双链表中删除尾节点，需要修改几个指针？
- A. 1
- B. 2
- C. 3
- D. 4
双链表的哪个特性使其在删除节点时比单链表更高效？
- A. 节点中包含数据大小
- B. 每个节点有两个指针，指向前一个和后一个节点
- C. 链表可以自动排序
- D. 链表中的节点数
为了实现一个双向循环链表，尾节点的next指针和头节点的prev指针应该如何设置？
- A. next指向NULL，prev指向NULL
- B. next指向头节点，prev指向尾节点
- C. next指向尾节点，prev指向头节点
- D. next和prev都指向自己
在双链表中，一个节点被删除后，其内存管理应该如何处理？
- A. 立即使用free()释放
- B. 标记为删除，稍后释放
- C. 保留以备后用
- D. 重用于链表中的其他节点

答案

答案: B - 双链表的每个节点包含两个指针，一个指向前一个节点，另一个指向后一个节点。
答案: A - 在双链表中插入新节点的时间复杂度是O(1)，因为只需修改几个指针，而不需要遍历整个链表。
答案: C - 双链表的删除操作的优势是不需要前驱节点的信息，因为每个节点已经包含了指向前驱节点的指针。
答案: C - 双链表允许从头到尾或从尾到头的遍历，因为每个节点都有指向前后节点的指针。
答案: B - 双链表通常不适用于需要节省空间的情况，因为每个节点需要额外的空间来存储两个指针。
答案: C - 在一个空的双链表中插入第一个节点后，头指针和尾指针都应指向这个新节点，因为它同时是链表的开始和结束。
答案: B - 删除双链表的尾节点需要修改两个指针：尾节点的前一个节点的next指针和尾节点指针自身。
答案: B - 双链表在删除节点时比单链表更高效，因为每个节点有两个指针，一个指向前一个节点，一个指向后一个节点，这使得无需遍历就能快速定位并修改相关指针。
答案: B - 在双向循环链表中，尾节点的next指针应指向头节点，头节点的prev指针应指向尾节点，从而形成一个闭环。
答案: A - 在双链表中，一个节点被删除后，应立即使用free()函数释放节点占用的内存，以防内存泄漏。

欢迎关注我公众号：AI悦创，有更多更好玩的等你发现！

公众号：AI悦创【二维码】

AI悦创·编程一对一

AI悦创·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Linux、Web 全栈」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然，还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线，随时响应！微信：Jiabcdefh

C++ 信息奥赛题解，长期更新！长期招收一对一中小学信息奥赛集训，莆田、厦门地区有机会线下上门，其他地区线上。微信：Jiabcdefh

方法一：QQ

方法二：微信：Jiabcdefh