顺序表习题详解：地址计算与链式结构特点

本资源主要针对严蔚敏版的第2章线性表进行了深入解析，涉及一系列选择题，有助于理解和掌握线性表的相关概念和操作。 1. 选择题（1）考察了顺序表的地址计算。顺序表中，元素按顺序连续存储，第5个元素的地址计算公式为：起始地址 + (元素长度 * (元素位置 - 1))。在这个例子中，第一个元素地址是100，每个元素长度为2，第5个元素的位置为5，因此地址为100 + 2 * (5-1) = 108。 2. （2）题目关注了顺序表的操作时间复杂度。访问第i个节点和求第i个节点的直接前驱在顺序表中是常数时间复杂度O(1)，因为可以直接通过下标访问。其他选项如插入和删除通常具有较高的时间复杂度，如O(n)或O(n2)。 3. （3）涉及顺序表插入操作的平均移动元素数量。对于127个元素的顺序表，插入一个新元素时，平均情况下需要移动元素个数为总元素的一半，即63.5个，但由于是整数处理，答案选63。 4. （4）链接存储的存储结构特点。链表中每个结点包含数据和指向下一个结点的指针，所以存储结构分为两部分，一部分存放结点值，另一部分存放指针。 5. （5）线性表的链式存储结构与内存地址的关系。链式存储可以是连续的，也可以是不连续的，取决于具体实现，答案为D。 6. （6）链式结构适用场景。当需要频繁进行删除和插入操作时，链表的优势明显，因为不需要移动大量数据，只需调整指针。 7. （7）单链表的存储密度。单链表由于每个结点包含数据域和指针域，因此存储密度小于1，表示数据本身所占空间与整个结点占用空间的比例。 8. （8）归并两个有序表的问题。归并两个已排序的表最少的比较次数是线性表合并过程中的理想情况，即每次比较都将较小的元素添加到结果列表，这个过程需要n-1次比较。 这些题目帮助学习者理解线性表的不同结构（顺序表和链表）、基本操作（地址计算、时间复杂度、插入与删除等）以及它们在实际应用中的优缺点。通过解答这些问题，可以提升对线性表数据结构的理解和操作能力。