day5, 2021 年 12 月 21 日，周二。

题目

在等概率情况下，顺序表的插入操作要移动__结点。
1. 全部
2. 一半
3. 三分之一
4. 四分之一

解析

什么是顺序表？

顺序表（顺序存储结构）及初始化过程详解：http://data.biancheng.net/view/158.html

顺序表，全名顺序存储结构，是线性表的一种。通过《线性表》一节的学习我们知道，线性表用于存储逻辑关系为“一对一”的数据，顺序表自然也不例外。

不仅如此，顺序表对数据的物理存储结构也有要求。顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙。

例如，使用顺序表存储集合 {1,2,3,4,5}，数据最终的存储状态如图 1 所示：

图 1 顺序存储结构示意图

由此我们可以得出，将“具有 ‘一对一’ 逻辑关系的数据按照次序连续存储到一整块物理空间上”的存储结构就是顺序存储结构。

通过观察图 1 中数据的存储状态，我们可以发现，顺序表存储数据同数组非常接近。其实，顺序表存储数据使用的就是数组。

顺序表的插入

在尾部插入元素的不需要移动元素；
在头部插入元素需要移动 N 个元素；
平均需要移动 N / 2 个元素；。