第二章 线性表：(1)线性表的顺序存储结构和链式存储结构的优缺点。(2)顺序表的插入和删除操作过程及其实现。(3)单链表的查找、插入和删除操作过程及其实现。(4)双链表的查找、插入和删除操作过程及其实现。(5)循环链表的查找、插入和删除操作过程及其实现。(6)有序表的二路归并算法的思路及其实现算法，以及该算法的时间复杂度分析。2.1线性表及其逻辑结构:(1)线性表是由个数据元素组成的有限序列，所有元素的性质相同，元素之间呈现线性关系，即除开始元素以外，每个元素只有唯一的前驱，除终端元素以外，每个元素只有唯一的后继。(2)在线性表中，通过序号来唯一标识一个元素，所以同一个线性表中可以存在值相同的元素。[单选题]线性表是具有n个（ ）的有限序列。
2.2线性表的顺序存储结构:(1)顺序表采用数组存放元素，既可以顺序查找，也可以随机查找（对于给定的序号i, 在常量时间内找到对应的元素值）。(2)分配给顺序表的所有内存单元地址必须是连续的。(3)当从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时需向前移动n-i个元 素，所以删除算法的时间复杂度为O(n)。(4)在一个长度为n的顺序表中插入第i个元素（1≤i≤n+1）时需向后移动n-i+1个元素，所以插入算法的时间复杂度为O(n)。
2.3线性表的链式存储结构:逻辑关系，每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的后继结点。(2)一个链表的所有结点的地址既可以连续，也可以不连续。(3)对链表只能顺序查找，不能随机查找，即给定序号i，不能在常量时间内找到对应的结点。(4)对链表插入或删除结点不需要移动结点，只需要调整相应结点的指针域。单链表只能按从前向后一个方向遍历。(5)双链表可以按从前向后、从后向前两个方向遍历。(6)循环链表分为循环单链表和循环双链表，循环单链表的结点构成一个查找环路， 循环双链表的结点构成两个查找环路。
2.4有序表:(1)有序表是一种按元素值有序排列的线性表，可以采用顺序表或链表存储。(2)长度分别为n、m的两个有序表采用二路归并方法合并成的一个有序表的时间复杂度为0(n+ m)，这是一种高效的方法。
数据元素
数据项
表元素
字符
答案：数据元素
[单选题]单链表又称为线性链表，在单链表上实施插入和删除操作（ ）。
只需移动结点，不需改变结点指针
既需移动结点，又需改变结点指针
不需移动结点，不需改变结点指针
不需移动结点，只需改变结点指针
答案：不需移动结点，只需改变结点指针
使单链表至少有一个结点
标识表结点中首结点的位置
方便运算的实现
说明单链表是线性表的链式存储
答案：方便运算的实现
p->next=q; q->next=p->next;
q->next=p->next; p->next=q;
q=p->next; p->next=q->next;
p->next=q->next; q=p->next;
答案：q->next=p->next; p->next=q;
可随机访问任一元素
所需空间与线性表长度成正比
不必事先估计存储空间
插入、删除不需要移动元素
答案：可随机访问任一元素
