5、在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n-i-1个元素，在插入操作中，移动元素的均值为（n+1）/2。
6、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单向链表和双向链表。
7、链式存储的特点是利用指针来表示数据元素之间的逻辑关系。 8、静态链表(线性表的游标实现)是指用数组下标表示单链表的指针。
9、在静态链表中，一般都有一个变量available表示的结点链，其中的结点为空闲结点。 10、在栈中，可进行插入和删除操作的一端称栈顶。
11、在进栈运算时，应先判别栈是否满。在出栈运算时应先判别栈是否空。当栈中元素为n个时，进栈运算时发生上溢，则说明该栈的最大容量为n。 12、设有一空栈，现有输入序列为1, 2, 3, 4, 5，经过push, push, pop, push, pop, push, push, pop, pop之后，输出序列为2354。
13、对于循环向量的循环队列，求队列长度的公式为（rear-front+n+1）%n。
14、栈的逻辑特点是先进后出。队列的逻辑特点是先进先出。两者的共同特点是只允许在它们的端点出插入和删除数据元素，区别是栈在栈顶进行插入删除，队列在两端操作，队尾插入，队首删除。
15、链队列LQ为空时，LQ->front->next=NULL.
16、在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为front.next==rear。
17、设串S=“Ilikecomputer”，T=“com”，则Length(S)=13。Index(S, T)=6。 18、在KMP算法中，next[j]只与子串有关，而与主串无关。 19、字符串“ababaab“的Next数组值是0112342。
20、稀疏矩阵一般压缩存储的方式有三种，分别是三原组存储、行指针链表和 十字链表。 21、二维数组M中每个元素的长度是3字节，行下标i从0~7，列下标j从0～9，从首地址&M[0][0]开始连续存放在存储器中。若按行优先的方式存放，元素M[7][5]的起始地址为 M[0][0]+225；若按列优先方式存放，元素M[7][5]的起始地址为M[0][0]+141。 22、广义表(a, (a, b), d, e, ((i, j), k))的长度是5，深度是3。
23、设广义表A((( ), (a, (b), c)))，则Cal(Cdr(Cal(Cdr(Cal(A))))=（b）
三、写一个算法合并两个已排序的线性表。（用两种方法：数组表示的线性表（顺序表）和指针表示的线性表（链表）） 要求：1、定义线性表节点的结构，并定义节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。
四、已知一个单向链表，试给出复制该链表的算法。
要求：1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作
3、在1，2的基础上，完成本题。 4、在main函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。
五、写出从一个带表头的单链表中删除其值等于给定值x的结点的算法函数： int delete(LIST &L, int x);如果x在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。 要求：1、定义线性表的节点的结构以及节点的型和位置的型。
2、定义线性表的基本操作
3、在1，2的基础上，完成本题。
4、在main函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。
三，四，五
#include
typedef int elementtype;//元素类型 struct celltype//链表节点 { elementtype elements; celltype *next; };
typedef celltype *LIST;
typedef celltype *position;//线性表的“型”与位置的“型”相同 position End(LIST L) //返回L中指向最后一个节点的指针 { position p; p=L;
while(p->next!=NULL) p=p->next; return p; }
void Insert(elementtype x, position p, LIST &L ) //创建元素x的节点插在p的后面 { position q q = new celltype q->elements = x q->next = p->next p->next = q
} //时间复杂性：O(1)
position Locate( elementtype x, LIST L ) //返回元素x在线性表中的位置 { position p p = L
while ( p->next != NULL ) if ( p->next->elements == x ) return p else
p = p->next; return p } //时间复杂性：O(n)
elementtype Retrieve( position p , LIST L ) {
return ( p->next ->elements ); } //时间复杂性：O(1)
void Delete( position p, LIST &L ) //删除位置p的下一个节点
{ position q
if ( p->next != NULL ) {
q = p->next p->next = q->next delete q }
} //时间复杂性：O(1)
position Previous ( position p, LIST L ) //返回位置p的前驱元素 { position q
if ( p == L->next )
cout<<”不存在前驱元素！\ else { q = L
while ( q->next != p ) q = q->next return q }
} //时间复杂度O(n)
position Next ( position p, LIST L ) //返回位置p的后驱元素 {
position q
if ( p->next == NULL )
cout<<\不存在后继元素！\else {
q = p->next; return q
}
} //时间复杂度O(1)
position MakeNull ( LIST &L ) {
L = new celltype
L->next = NULL; return L } //时间复杂性：O(1) position First ( LIST L )
{ return L; } //时间复杂性：O(1) void Travel( LIST L )//遍历线性表元素 { position p
p = L->next while ( p != NULL)
{
cout << p->elements<
//=================================================
void Merge(LIST &L,LIST L1,LIST L2) //合并两个线性表(链表)，将L1，L2合并到L中
{
position p1=0,p2=0,p3=0; for(p3=L1;p3;p3=p3->next) { p1=new celltype; p1->elements=p3->elements; If(L==0)
{
L=p1; p2=p1; } else {
p2->next=p1; p2=p1; } }
for(p3=L2;p3;p3=p3->next) { p1=new celltype; p1->elements=p3->elements;
if(L==0) { L=p1; p2=p1; }
else { p2->next=p1; p2=p1; } p2->next=NULL;
}
//============================================== //复制链表
void copy(LIST &L1,LIST L2) {
position p1=0,p2=0,p3=0; for(p3=L2;p3;p3=p3->next)
{
p1=new celltype;
p1->elements=p3->elements;
I f(L1==0) { L1=p1; p2=p1; }
else
{ p2->next=p1; p2=p1; }
}
p2->next=NULL;
} //===================================================== //删除指定元素的节点
}
int Delete(LIST &L,int x) {
int m=1;//指定元素在线性表中的位置 position p1=0,p2=0; if(L->elements==x) { p1=L;
L=L->next;
delete p1;
return m; } else {
p1=p2=L;
while(p1->elements!=x && p1->next!=NULL) {
p2=p1; m++;
p1=p1->next; }
p2->next=p1->next; delete p1;
return m; }
return -1;//不存在元素x }
void Read(LIST &L,int i) //输入数据 {
cout<<\请输入第\个线性表\LIST p1=0,p2=0; elementtype x; for(;;) {
cout<<\请输入数据(-1作为结束标志):\ cin>>x;
if(x==-1) break; p1=new celltype; p1->elements=x;
if(L==0) { L=p1; p2=p1; } else { p2->next=p1; p2=p1; } }
p2->next=NULL; }
void Write(LIST L) //输出 {
position p=L;