三、简答题（每题10分，共2道小题，总分值20分）1.顺序表[1]与链表[2]比较各自的优缺点是什么？（10分）

本题考查顺序表与链表这两种线性表存储结构的优缺点比较。解题核心在于理解两者的存储方式、访问特性及操作效率差异：

• 顺序表基于数组实现，存储连续，支持快速访问但插入删除效率低；
• 链表通过节点动态分配空间，插入删除高效但存储密度低、访问速度慢。

顺序表的优缺点

优点

1. 存储密度高：顺序表所有元素连续存储，空间利用率高。
2. 支持随机访问：通过索引可直接定位元素，时间复杂度为$O(1)$。

缺点

1. 存储空间需预先分配：初始需预留足够空间，空间不足时需整体搬迁。
2. 不适合动态变化：插入/删除操作需移动大量元素，时间复杂度为$O(n)$。

链表的优缺点

优点

1. 插入/删除方便：通过修改指针直接操作，时间复杂度为$O(1)$（假设已定位到操作位置）。
2. 动态分配空间：按需申请节点，无需预先分配存储空间。

缺点

1. 存储密度低：每个节点需额外存储指针，空间利用率低。
2. 非随机存储结构：只能顺序遍历访问元素，时间复杂度为$O(n)$。