算法与数据结构复习：线性表选择与填空详解

线性表是数据结构中一种重要的抽象数据类型，它是一系列按照特定顺序排列的元素集合。在数据结构复习中，涉及线性表的题目主要考察了不同类型的存储方式对操作效率的影响以及线性表的基本概念和性质。 1. 选择题部分: - 顺序存储结构的优点通常包括存储密度大（C），因为元素是连续存储的，没有额外的空间浪费；但插入和删除操作相对复杂，因为需要移动大量元素。 - 错误的描述是B，顺序存储虽然便于插入和删除，但在实际应用中，由于连续存储的要求，插入和删除效率较低。 - 线性表由n个数据元素组成（C），它们按照一定的顺序排列。 - 对于频繁存取指定序号元素和尾部操作的情况，顺序表（A）最节省时间，因为通过索引可以直接定位元素。 - 最常进行尾部插入和首部删除的操作时，单链表（A）最节省时间，因为无需移动元素。 - 末尾插入和删除操作，单链表（D）可能最高效，因为只需要修改尾指针。 - 存取第I个元素及其前后元素时，双向链表（B）最理想，因为它可以轻松访问前后节点。 - 头指针为NULL表示单链表为空（A），因为只有一个结点时，头结点的下一个指针会为空。 - 链表的特点包括无需移动元素进行插入和删除（A），但不能随机访问，因为元素位置不是连续的。 - 头结点的作用之一是标识表的起始位置（B），便于操作实现。 - 在单循环链表中，p指向尾部的条件是p->next->next==h，形成环路。 - 要求快速插入和删除且保持逻辑关系的线性表，应使用链式存储方式（B），因为这更灵活。 2. 填空题部分: - 在单链表中插入新节点到非首尾结点P之后，操作为：`p->next=s; s->next=p->next;`。 - 顺序表中逻辑相邻的元素物理上是连续的，而单链表则是不连续的。 - 顺序存储中插入平均移动元素个数与n有关，对于n个元素，平均移动 (n+1)/2 个元素。 - 在双向循环链表中插入p到q前，还需设置q->prior->next = p。 - 表尾插入s结点，可能的语句组合包括：`L->next=s; s->next=L;` 或 `p->next=s; s->next=p->next;` - 向向量插入元素，需要移动 (n-i+1) 个元素。 - 删除第i个元素，需要移动 i-1 个元素。 - 顺序表中插入/删除元素平均移动 n/2 个元素，具体移动取决于实际插入/删除位置。 总结：复习线性表时，重点理解顺序存储和链式存储的不同特点，如存储密度、插入/删除操作的效率、访问模式等，并掌握链表的常见操作，如单链表、双向链表、循环链表等的选择与应用。同时，填空题部分考察了实际操作和计算平均移动元素的问题，这些都是线性表理论和实践的重要组成部分。