第二章 习题与参考解答
一 单选题 (请从下列A，B，C，D选项中选择一项) 1．线性表是( A ) 。
(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。
2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（A ）个元素。
(A) n/2 (B) n+1/2 (C) n -1/2 (D) n
3．线性表采用链式存储时，其地址( D ) 。
(A) 必须是连续的； (B) 部分地址必须是连续的； (C) 一定是不连续的； (D) 连续与否均可以。
4．用链表表示线性表的优点是 （ C）。
(A)便于随机存取 (B)花费的存储空间较顺序存储少
(C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同
5． 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则
采用(D )存储方式最节省运算时间。 (A)单链表 (B)双链表
(C)单循环链表 (D)带头结点的双循环链表
6． 下面关于线性表的叙述错误的是(B )。
(A) 线性表采用顺序存储，必须占用一片地址连续的单元； (B) 线性表采用顺序存储，便于进行插入和删除操作； (C) 线性表采用链式存储，不必占用一片地址连续的单元； (D) 线性表采用链式存储，不便于进行插入和删除操作；
7． 单链表中，增加一个头结点的目的是为了（C ）。
(A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置
（C）方便运算的实现 (D) 说明单链表是线性表的链式存储
8． 在一个单链表中p所指结点之后插入一个指针为s的结点，正确的操作是：（B）
A. p->next =s;s->next= p->next; B. s->next= p->next;p->next =s; C. p->next =s; p->next=s->next; D. s->next= s->next;p->next =s; 9． 在双向链表存储结构中，删除p所指结点时，必须修改指针（A）
A. (p->prior)->next =p->next;(p->next)->prior= p->prior; B. p->prior=(p->prior)->prior;(p->prior)->next= p;
1
C. (p-> next)-> prior =p;p->rlink=(p->next)->next;
D. p-> next=(p-> prior)->prior;p->prior=(p->next)->next; 10． 完成在双向链表结点p之后插入s的操作是（D）
A. p->next =s;s->prior= p;p->next->prior=s;s->next=p->next; B. p->next->prior=s;p->next=s;s->prior=p;s->next=p->next; C. s->prior=p;s->next=p->next;p->next=s;p->next->prior=