1/2
一、名词解释
1. 线性表 2. 顺序表 3. 单链表 4. 循环单链表 5. 循环双向链表 二、选择题
1. 用单链表方式存储的线性表，存储每个结点需要两个域，一个是数据域，另一个是
_________ A. 当前结点的所在地址 B. 后继结点的所在地址 C. 空指针域 D. 空闲域
2. 不带头结点的单链表head为空的判定条件是__________ A. head==NULL
B. head?next==NULL C. head?next==head D. head!=NULL
3. 带头结点的单链表head为空的判定条件是__________ A. head==NULL
B. head?next==NULL C. head?next==head D. head!=NULL
4. 一个顺序表的第一个元素的存储地址是100，每个元素的长度为5，则第7个元素
的地址是____________ A. 130 B. 125 C. 120 D. 135
5. 非空的循环单链表head的尾结点（由p所指向）满足____________ A. p?next==NULL B. p==NULL C. p?next==head D. p==head
6. 设线性链表中结点的结构为(data, next)，已知指针q所指结点是指针结点p的直接
前驱，若在q与p之间插入结点s，则应执行_________操作 A. s?next=p?next; p?next=s; B. q?next=s; s?next=p;
C. p?next=s?next; s?next=p; D. p?next=s; s?next=q;
7. 设线性链表中结点的结构为(data, next)，已知指针p所指结点不是尾结点，若在p
之后插入结点s，则应执行_____操作 A. s?next=p; p?next=s;
B. s?next=p?next; p?next=s; C. s?next=p?next; p=s; D. p?next=s; s?next=p;
8. 设线性链表中结点的结构为(data, next)，若想删除结点p的直接后继，则应执行
2/2
______ A. p?next=p?next?next;
B. p=p?next; p?next= p?next?next C. p?next=p?next; D. p=p?next?next;
9. p指向线性链表中L的某一个结点，则在线性链表的表尾插入结点s的语句序列是
_________ A. while(p?next != NULL) p=p?next; p?next=s; s?next=NULL; B. while(p != NULL) p=p—next; p?next=s; s?next=NULL;
C. while(p?next != NULL) p=p?next; s?next=p; p?next=NULL; D. while(p!=NULL) p=p?next?next; p?next=s; s?next=p?next; 三、填空题
1. 按顺序存储方法存储的线性表称为________，按链式存储方法存储的线性表称为
________。 2. 在双向链表中，每个结点有两个指针域，一个指向________，另一个指向________。 3. 在一个长度为n的顺序表中的第i个元素之前(1≤i≤n)插入一个元素时，需要向后
移动________个元素。在顺序表中访问任意一结点的时间复杂度均为________。 4. 顺序表相对于链表的优点有________和________。 5. 链表相对于顺序表的优点有________和________。
6. 在n个结点的顺序表中插入一个结点需平均移动________个结点，具体的移动次数
取决于________。
7. 在n个结点的顺序表中删除一个结点需平均移动________个结点，具体的移动次数
取决于________。
8. 在n个结点的单链表中要删除已知结点p，需要找到________。其时间复杂度为
________。
9. 在单链表中，要在已知结点p之前插入一新结点，则需找到________，其时间复杂
度为________。
10. 顺序表中逻辑上相邻元素的物理位置________紧邻。单链表中逻辑上相邻元素的物
理位置________紧邻。
四、编程题
1. 有一个单链表，其头指针为head，编写一个函数来计算数据域为x的结点个数。 2. 用顺序表作为存储结构，实现将线性表(a1, a2, …, an)重新排列为以a1为界的两部分，
前一部分之会均小于a1，后一部分之值均大于a1（假设结点值可以比较大小）的一个算法。
3. 对给定的单链表L，编写一个删除L中值为x的结点的直接前驱结点的算法。 4. 编写一个倒置顺序存储的线性表的函数，要求用最少的附加存储空间完成。 5. 已知一个单链表，编写一个函数将该单链表复制一个拷贝。