清华大学数据结构习题答案详解：顺序与链表对比

本资源提供了清华大学出版社出版的数据结构课程习题答案，涵盖了单元练习2中的判断题和填空题，有助于学习者理解和巩固数据结构的基本概念和操作。 **单元练习2 - 判断题解析** 1. （×）线性表的链式存储结构不一定优于顺序存储。这是因为链式存储虽然灵活，但不保证连续存储，可能导致额外的指针开销，而顺序存储则在存储密度上占有优势。 2. （×）错误的表述，链表的每个结点可能包含多个指针域，比如双向链表就有两个指针。 3. （√）正确，链式存储允许元素之间逻辑相邻但物理上不相邻，这使得插入和删除操作更高效。 4. （×）顺序存储方式的确在存储密度上较大，但插入和删除操作的效率低，尤其是对于大型表。 5. （×）删除链表节点时，前后节点的更新需要手动完成，而不是由计算机自动完成。 6. （√）顺序表通常用于存储简单类型，而链表可以处理复杂类型，每个结点可以包含多个域。 7. （√）链式存储的一个优点是可以利用非连续的存储空间，适合数据元素不连续的情况。 8. （√）顺序表要求连续的存储空间，这是其局限性之一。 9. （×）顺序表适合顺序存取，而链表适合随机存取，但链表的存取速度取决于链表的结构，不是绝对的随机存取。 10. （√）插入和删除是数据结构的核心操作，但在数组中通常受限，如动态扩容等。 **填空题解答** 1. 顺序表中逻辑相邻的元素在物理位置上通常连续。 2. 线性表中的结点间是一对一的关系，形成线性结构。 3. 顺序表的优点除了节省存储外，还包括快速的随机存取，但插入删除成本高。 4. 链表的优点在于插入和删除速度快，但占用存储空间较大。 5. 采用连续存储结构的线性表被称为顺序表。 6. 顺序表的随机访问时间复杂度为O(n)，因为必须遍历。 7. 链表的插入和删除操作时间复杂度通常较低，但存储密度较小。 8. 双向链表删除节点的时间复杂度为O(1)，因为可以直接访问前驱和后继节点。 9. 在单链表中插入节点的时间复杂度为O(n)，需遍历找到合适位置。 10. 单链表遍历依赖头指针。 11. 顺序表的第一个元素没有直接前趋。 12. 删除顺序表中第i个元素需要移动n-i个元素。 13. 在顺序表中插入在第i个元素前需移动n-i+1个元素。 14. 单链表的存储结构中，头指针存储首节点地址，其余节点的地址存储在前驱节点中。 15. 当数据结构稳定且少变，顺序存储因其快速存取适合。 16. 链式存储通过指针连接元素，表示逻辑关系。 17. 双向链表的每个节点有两个指针，分别指向前一个和后一个节点，提供双向访问。 通过这些习题答案，学生可以加深对数据结构中顺序表和链表的理解，掌握它们各自的优缺点，并能熟练进行相关的操作。