全部知识点

逆置单链表适合用头插法，逆置顺序表适合用首尾交换法（）

在长度为n的顺序表中删除i号数据元素，需要移动表中______个元素(0≤i

对于一个长度为n的顺序表，将值为x的元素插入在表中的i号位置，需向后移动的元素个数为______，i的合法范围为______

在顺序表中，按位序访问任一元素的时间复杂度均为______，因此顺序表也称为______的数据结构

顺序表中逻辑次序相邻的元素的物理位置______相邻。单链表中逻辑次序相邻的元素的物理位置______相邻。（填写：“一定”或“不一定”）

在单链表中，除了首元素结点外，任一结点的存储位置由______指示

在n个结点的单链表中要删除已知结点p，需找到它的______，其时间复杂度为______

链式存储的特点是利用_____来表示数据元素之间的逻辑关系

在单链表中，指针p所指结点有后继结点的条件是______

对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______

在n个结点的单循环链表中，若仅设头指针，则访问首结点和尾结点的时间复杂度分别为______、______；若仅设尾指针，则访问首结点和尾结点的时间复杂度分别为______、______

在n个结点的双向循环链表中，若仅设尾指针，则访问首结点和尾结点的时间复杂度分别为______、______

当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度按序号存取线性表的元素时，应采用______存储结构

给定两个有序顺序表A和B，设A表的长度为m，B表的长度为n，将两个有序表合并成有序表C，最坏情况下需进行______次比较

以下算法的时间复杂度分别是多少？请用大O记号表示

（1）将长度为n的顺序表置成空表。______；

（2）将长度分别为m和n的递增有序单链表A和B合并成递减有序单链表C。（假设可以通过头指针直接访问链表的结点）______

说明顺序表和链表的优缺点和适用场合

线性表的顺序存储结构具有三个弱点：其一，在进行插入或删除操作时，需移动元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量较难扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。

线性表有两类存储结构，一是顺序表，二是链表。如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，同时线性表的总数也会不断改变。在此情况下，应选用哪种存储结构？为什么？

在线性表的以下链式存储中，若链表头结点的地址未知，仅已知p指针指向的结点，能否从中删除该结点？为什么？

（1)单链表；

（2)双链表；

要求将算法1~6设计为3. 3. 4节定义的顺序表DynamicArrayList类的方法。

1.设计算法，在顺序表中删除所有奇数位序的元素。