Python

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

在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.设计算法，在顺序表中删除所有奇数位序的元素。

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

2.设计算法，将顺序表中存放的元素循环左移p位。即L（a_o,a_1,a_2···.a_p···..a_n-1变为L= (a_p·a_p+1····.a_n-1.a_o····a_p-1)。

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

3.设计算法，将整数顺序表所有元素划分为两部分，其中前面部分的元素都小于等于x,后面部分的元素都大于x.

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

4.设计尽可能高效的算法，删除顺序表中所有值为x的元素。

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

5.设在某顺序表中，有一个整数在该表中的出现次数为奇数，其余整数的出现次数均为偶数。设计尽可能高效的算法，寻找出现次数为奇数的整数。例如：（1, 2. 5, 2,5. 1. 5)中，出现次数为奇数的整数为5

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

6.设计算法，将有序顺序表中position位置的元素值替换为item,要求替换后的表仍保持有序。