2.2链表（分层作业）-高中信息技术选修1数据与数据结构 分层作业

2.2 链表（分层作业） 【夯实基础】 1. 链表是一种____数据结构。 A. 顺序存储 B. 非顺序存储 C. 只能单向遍历 D. 静态分配内存 2. 下列哪项不是链表相对于数组的优势？（ ） A. 动态扩容 B. 插入和删除操作更快 C. 空间利用率高 D. 随机访问效率高 3. 单链表中的每一个节点包含哪些部分？（ ） A. 数据域 B. 指针域 C. 数据域和指针域 D. 数据域或指针域 4. 在单链表中，要访问某个节点，必须从____开始。 A. 头节点 B. 尾节点 C. 中间节点 D. 任一节点 5. 双向链表中的节点比单链表多了什么？（ ） A. 数据域 B. 指向前一个节点的指针 C. 指向后一个节点的指针 D. 头节点指针 6. 创建一个空链表时，通常会设置一个头节点，其目的是什么？（ ） A. 方便插入第一个元素 B. 标记链表的开始 C. 使链表操作统一 D. 以上都是 7. 在单链表中，要删除一个已知节点q，需要执行的操作是：（ ） A. q->data = q->next->data; q->next = q->next->next; B. q = q->next; C. q->next = NULL; D. 无法直接删除，需先找到q的前驱节点并修改其next指针 8. 在一个循环链表中，如何区分链表的尾部和头部？ A. 需要额外的标记或计数器来区分 B. 循环链表的尾节点的next指针指向头节点 C. 循环链表没有明确的尾部 D. 循环链表的头节点的next指针指向自身 【巩固提升】 9. 由n个节点链接成的单链表如图所示，其中head为头指针。 使用列表link模拟该链表结构，每个节点包含数据域和指针域，如图中最后一个节点可以表示为［98，-1］。现要删除指针p所指向的节点，可以实现该操作的语句有（     ） ① link[p][1] = - 1             ② link[head][1] = q ③ link[head][1] = link[p][1]       ④ head = link[p][1] A．①② B．①③ C．②③ D．②④ 10. 下列关于循环链表的说法错误的是：（ ） A. 循环链表的最后一个节点的next指向头节点 B. 便于实现约瑟夫问题等特定算法 C. 所有操作的时间复杂度都与链表长度成正比 D. 可以不需要头节点 11. 在链表的哪个位置添加新节点最快？ A. 开头 B. 中间 C. 末尾 D. 所有位置速度相同 12. 链表节点的插入操作中，需要改变几个节点的指针？（ ） A. 0 B. 1 C. 2 D. 取决于插入位置 13. 下列哪个操作在链表中比在数组中更高效？（ ） A. 查找指定值 B. 有序插入 C. 删除任意位置的元素 D. 访问索引为i的元素 【拓展应用】 填空题1：创建一个空链表实例时，可以设置头节点的next属性为_______。 填空题2：链表是一种在物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过每个元素的_______来实现的。 参考答案： 【夯实基础】 1. B. 非顺序存储 解析：链表中的节点在内存中可以不相邻存放，通过指针链接起来，故是非顺序存储。 2. D. 随机访问效率高 解析：链表访问元素需要从头节点逐个遍历，而数组可通过索引直接访问，因此数组的随机访问效率更高。 3. C. 数据域和指针域 解析：单链表节点由两部分组成：存储数据的数据域和指向下一个节点地址的指针域。 4. A. 头节点 解析：单链表的遍历通常从头节点开始，逐步通过next指针访问后续节点。 5. B. 指向前一个节点的指针 解析：双向链表的节点除了有指向后继节点的指针，还有指向前驱节点的指针。 6. D. 以上都是 解析：设置头节点既方便了插入第一个元素，也标记了链表的开始，且使得对链表的操作（如遍历）更为统一。 7. D. 无法直接删除，需先找到q的前驱节点并修改其next指针 解析：要删除链表中某节点q，必须先找到q的前驱节点，并将其next指针指向q的下一个节点，从而绕过q。 8. B. 循环链表的尾节点的next指针指向头节点 解析： 在循环链表中，区别于普通单向或双向链表的关键特征是其尾节点的next指针不再指向