第 2 章习题
1、填空题
(1)一线性表表示如下：（ a1 ，a2 ，… ，an ），其中每个 ai 代表一个_______。a1 称为______结点，an 称为______结点，i 称为 ai 在线性表中的____。对任意一对相 邻结点 ai ，ai+1（ 1≤i≤n ），ai 称为 ai+1 的直接____ ，ai+1 称为 ai 的直接____。
(2)线性表 a 中数据元素长度为 4，在顺序存储结构下 LOC（a1 ）=1000 ，则
LOC（a3 ）= 。
(3) 线 性 表 L=（ a ， b ， c ， d ， e ）， 经 运 算 DELETE（ L ， 3 ）后 ，
L= ,再经过 INSERT（ L ，2，w）运算后，L= 。调用
函数 GET（ L ，3 ）的结果为 。
(4)在一个长度为 n 的顺序表中， 向第 i 个元素（ 1≤i≤n）之前插入一个新
元素时，需向后移动 个元素。
(5)在单链表中除首结点外，任意结点的存储位置都由 结点中的指针指 示。
(6)在单链表中设置头结点的作用是在插入和删除首结点时不必对 进行特 殊处理。
(7)设 rear 是指向非空、带头结点的循环单链表的尾指针，则该链表首结点的 存储位置是 。
(8)在带有头结点的单链表 L 中，若要删除第一个结点，则需执行下列三条 语句： ;L->next=U->next;free(U);
2、选择题
1.顺序表的一个存储结点仅仅存储线性表的一个（ ）。
A． 数据元素 B． 数据项
C． 数据 D． 数据结构
2.对于顺序表，以下说法错误的是（ ）。
A． 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的
绝对地址
B． 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依 次排列
C． 顺序表的特点是：逻辑结构中相邻的结点在存储结构中仍相邻
D． 顺序表的特点是：逻辑上相邻的元素，存储在物理位置也相邻的单
元中
3.L 是顺序表， 已知 LENGTH（ L ）的值是 5 ，经运算 DELETE（ L ，2 ）后 LENGTH（ L ）的值是（ ）。
A． 5 B． 0
C． 4 D． 6
4.带头结点的单链表 head 为空的判断条件是（ ）。
A． head==NULL B． head->next==NULL
C． head->next==head D． head!=NULL
5.若某线性表最常用的操作是取第 i 个元素和找第 i 个元素的前驱元素，则 采取（ ）存储方式最节省时间。
A． 单链表 B． 双链表
C． 单向循环链表 D． 顺序表
6.链表不具有的特点是（ ）。
A． 随机访问 B． 不必事先估计存储空间
C． 插入删除时不需移动元素 D． 所需的空间与线性表成正
比
7.在一个单链表中， 已知 q 所指结点是 p 所指结点的直接前驱，若在 p ，q 之间插入 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;
3、判断题
1.顺序表可以方便的随机存取表中的任一元素。 ( )
2.顺序表上插入一个数据元素的操作的时间复杂度为 O（ 1 ）。 (
)
3.顺序表中作删除操作时不需移动大量数据元素。 ( )
4.线性表的链式存储结构，表中元素的逻辑顺序与物理顺序一定相同。 ( )
5.对双向链表来说， 结点*p 的存储位置既存放在其前驱结点的后继指针域 中，也存放在它的后继结点的前驱指针域中。
( )
6.在顺序表和单链表上实现读表元运算的平均时间复杂度均为 O(1) 。 (
)
4、应用题
1.试述顺序表的优缺点。
2.对以下单链表分别执行下列各程序段，画出结果示意图。
5
R S
（ 1 ） Q=P->next;
（ 2 ） L=P->next;
（ 3 ） R->data=P->data;
（ 4 ） R->data=P->next->data;
（ 5 ） P->next->next->next->data=P->data;
（ 6 ） T=P;
while(T!=NULL){T->data=T->data*2;T=T->next;}
（ 7 ） T=P;
while(T->next!=NULL){T->data=T->data*2;T=T->next;}
3.已知带表头结点的非空单链表 L，指针 P 指向 L 链表中的一个结点（非首 结点、非尾结点），试从下列提供的答案中选择合适的语句序列。
（ 1 ）删除 P 结点的直接后继结点的语句是 ；
（ 2 ）删除 P 结点的直接前驱结点的语句序列是 ；
（ 3 ）删除 P 结点的语句序列是 ；
（ 4 ）删除首结点的语句序列是 ；
（ 5 ）删除尾结点的语句序列是 。
a) P=P->next;
b) P->next=P;
c) P->next=P->next->next;
d) P=P->next->next;
e) while(P!=NULL) P=P->next;
f) while(Q->next!=NULL) {P=Q;Q=Q->next;}
g) while(P->next!=Q) P=P->next;
h) while(P->next->next!=Q) P=P->next;
i) while(P->next->next!=NULL) P=P->next;
j) Q=P;
k) Q=P->next;
l) P=L;
m) L=L->next;
n) free(Q);
5、算法设计题
1. 已知一个顺序表中的元素按值非递减有序排列，试写一算法，删除表中 值相同的多余元素。
2.一个一年定期储蓄客户表如表 2.2 ，编写一算法实现客户的查找。要求输 入帐号 ，能够输出客户的所有信息。
表 2.2 一年定期储蓄客户表
帐 号 姓 名 金 额
230 李 500
01 明 0
230 贾 600
08 燕 0
231 王 210
90 昭 0
234 谢 450
51 永丰 0
3.设有两个线性表 A 和 B 均使用单链表结构存储， 同一表中元素各不相同， 且递增有序， 写一算法，构成一个新的线性表 C ，使 C 为 A 和 B 的交集 ，且 C 中元素也递增有序。
评论0