第二章线性表
1、描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。
2、对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。
(1)定位到第i个结点ai；
(2)定位到第i个结点的前驱ai-1；
(3)定位到尾结点；
(4)定位到尾结点的前驱。
3、已知L是有表头结点的单链表，且P结点既不是首元结点，也不是尾结点，试写出实现
下列功能的语句序列。
(1)在P结点后插入S结点；
(2)在P结点前插入S结点；
(3)在表首插入S结点；
(4)在表尾插入S结点
.p=head; p=head; j=0;
while ( p && jnext; j++;}
p=head; j=0;
while ( p && jnext; j++;}
p=head;
while ( p ->next ) p=p->next;
while ( p->next->next ) p=p->next;
（1）s->next=p->next; p->next=s;
（2）q=L;
while( q->next!=p) q=q->next;
s->next=p 或 q->next ;
q ->next=s;
(3 ) s->next=L->next; L->next=s;
（4）q=L;
while( q->next!=NULL) q=q->next;
s->next= q->next ; q->next=s;4、设计算法：在顺序表中删除值为e的元素，删除成功，返回1；否则，返回0。
5、设计一个算法，将一个带头节点的数据域依次为a1，a2，…，an（n≥3）的单链表的所
有节点逆置，即第一个节点的数据域变为an，…，最后一个节点的数据域为a1。（注意：先
用自然语言描述算法基本思想，然后用类C++语言描述）int Sqlist::DeleteElem( T e )
{ for (i=1; i<=length; i++) // 按值顺序查找 * i可从0开始
if (elem[i-1]= =e) // 找到，进行删除操作
一、选择题
1、用单链表方式存储的线性表，存储每个结点需要两个域，一个是数据域，另一个是（）
A、当前结点所在的地址域 B、指针域 C、空指针域 D、空闲域
2、不带头结点的单链表head为空的判断条件是（）
A、head==NULL B、head->next==NULL C、head->data==NULL D、head!=NULL
3、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则执行（）
A、s->next=p; q->next=s; B、p->next=s->next; s->next=p;
C、q->next=s->next; s->next=p; D、p->next=s; s->next=q;
4、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）
A、O（1） B、O（n） C、O（n2） D、O（nlog2n）
5、一个单链表中，若删除p所指结点的后续结点，则执行（）
A、p->next=p->next->next; B、p=p->next; p->next=p->next->next;
C、p->next=p; D、p=p->next->next;
6、已知一个顺序存储的基本线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1，则第i个结点的地址为（）
A、d1+(i-1)*m B、d1+i*m C、d1-i*m D、d1+(i+1)*m
7、在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）
A、访问第i个结点(1<=i<=n)和求第i个结点的直接前驱(2<=i<=n)
B、在第i个结点后插入一个新结点(1<=i<=n)
C、删除第i个结点(1<=i<=n)
D、将n个结点从小到大排序
8、下面给出的算法段是要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双向链表中，能正确完成要求的算法段是（）
《数据结构练习题》线性表
线性表及其实现
1设一顺序表中元素值递增有序。写一算法，将元素x插到表中适当的位置，并保持顺序表的有序性，且分析算法的时间复杂度。
2设有两个按元素值递增有序的顺序表A和B，编一程序将A 表和B表归并成一个新的递增有序的顺序表C（值相同的元素均保留在C表中）。
3按下面两种情况分别编写算法删除顺序表中值相同的多余
元素：
（1）顺序表元素值递增有序；
（2）顺序表元素值无序。
4已知L是无表头结点的单链表，且P结点既不是首结点，也不是尾结点，试从下列提供的语句中选出合适的语句序列。
(1) 在P结点后插入S结点：__________
(2) 在P结点前插入S结点：__________
(3) 在表首插入S结点：__________
(4) 在表尾插入S结点：__________
① P->next = S;
② P->next = P->next->next;
③ P->next = S->next;
④ S->next = P->next;
⑤ S->next = L;
⑥ S->next = P;
⑦ S->next = NULL;
⑧ Q = P;
⑨ while (P->next != Q) P = P->next;
while (Q->next != NULL) Q = Q->next;
P = Q;
P = L; L = S;
L = P;
5已知P结点是某双向链表的中间结点，试从下列提供的语句中选出合适的语句序列。
(1) 在P结点后插入S结点：______________
(2) 在P结点前插入S结点：______________
(3) 删除P结点的直接后继结点：______________
(4) 删除P结点的直接前驱结点：______________
(5) 删除P结点：______________
① P->next = P->next->next;
第2章 线性表一、 选择题
1. 表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ ），删除一个元素需要移动的元素个数为（ ）。【＊＊，★】
A. (N-1)/2 B. N C. N+1 D. N-1 E. N/2 F. (N+1)/2 G. (N-2)/2
2. 线性表是具有N 个（ ）的有限序列。【＊】
A、表元素 B、字符 C、数据元素 D、数据项 E、信息
3. “线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（ ）。【＊】
A、正确的 B、错误的 C、不一定，与具体结构有关。
4. 线性表采用链式存储结构时，要求内存中可用存储单元的地址（ ）。【＊，★】
A、必须是连续的 B、部分地址必须是连续的
C、一定是不连续的 D、连续或不连续都可以。
5. 带头结点的单链表为空的判定条件是（ ）。【＊】
A、head==NULL B、head->next==NULL
C、head->next==head D、head!=NULL
6. 不带头结点的单链表head 为空的判定条件是（ ）。【＊】
A、head==NULL B、head->next==NULL
C、head->next==head D、head!=NULL
7. 非空的循环单链表head 的尾结点P 满足（ ）。（注:带头结点）【＊】
A、P->NEXT=NULL B、p=NULL
C、p->next==head D、p==head
8. 在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）。【＊，★】
