第二章 习题与参考解答
一 单选题 (请从下列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=s; D. s->next=p;s->next=p->next;p->next->prior=s;(p->next)=s; 11． 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）
存储方式最节省运算时间（B ）。 (A) 单链表 (B) 顺序表 (C) 双链表 (D) 单循环链表 12． 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，
则采用（D ）存储方式最节省运算时间。
(A) 单链表 (B) 仅有头指针的单循环链表 (C) 双链表 (D) 仅有尾指针的单循环链表
二 判断题
1．线性表的逻辑顺序与存储顺序总是一致的。× 2．顺序存储的线性表可以按序号随机存取。∨ 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 ×
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。∨
5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。× 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。∨ 7．线性表的链式存储结构优于顺序存储结构。×
8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。∨ 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。∨ 10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。×
11.静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个的元素的时间与i无关。×
12.线性表的特点是每个元素都有一个前驱和一个后继。×
三 算法设计题
1． 设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将
x 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。 Ⅰ、直接使用数组的写法：
2
#define MAXSIZE 30 #include \
void inte(int a[],int m,int x) {int i=m-1;
while(i>=0&&x 由于只有一重循环，查找x最多次数为n 故时间复杂度为O(n) void main() { int a[MAXSIZE],i,n,x; scanf(\ printf(\ for(i=0;i printf(\ } printf(\ scanf(\ inte(a,n,x); printf(\ for(i=0;i Ⅱ。使用线性表结构的程序： #include \ #include \ #define MAXSIZE 100 typedef struct {int data[MAXSIZE]; int last; }SeqList; SeqList *init_SeqList( ) { SeqList *L; L=malloc(sizeof(SeqList)); L->last=-1; return L; } 3 int Insert_SeqList(SeqList *L,int x) /*主要是这段函数的设计*/ {int j; if (L->last==MAXSIZE-1) { printf(\＂表满＂\表空间已满，不能插入*/ for(j=L->last;x main() {int i,j,x; SeqList *L; L=init_SeqList(); for(i=0;i<10;i++) {x=2*i; Insert_SeqList(L,x); } printf(\ for(i=0;i<=L->last;i++) printf(\ printf(\ scanf(\ Insert_SeqList(L,x); printf(\ for(i=0;i<=L->last;i++) printf(\ } 2． 已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同 的元素。 Ⅰ、直接使用数组的写法： #define MAXSIZE 30 #include \ int dele(int a[],int elenum) {int i,j; i=j=0; while(j 4 if(a[i]==a[j])j++; else a[++i]=a[j++]; return(i+1); } void main() { int a[MAXSIZE],i,n,x; scanf(\ printf(\ for(i=0;i printf(\ } printf(\ n=dele(a,n); printf(\ for(i=0;i printf(\} Ⅱ。使用线性表结构的程序： #include \ #include \ #define MAXSIZE 100 typedef struct {int data[MAXSIZE]; int last; } SeqList; SeqList *init_SeqList( ) { SeqList *L; L=malloc(sizeof(SeqList)); L->last=-1; return L; } int Insert_SeqList(SeqList *L,int x) {int j; if (L->last==MAXSIZE-1) 5