习题二参考答案
一、选择题
1.链式存储结构的最大优点是（ D ）。
A.便于随机存取
B.存储密度高
C.无需预分配空间
D.便于进行插入和删除操作
2.假设在顺序表{a0,a1,……,a n－1}中，每一个数据元素所占的存储单元的数目为4，且第0
个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。
A.106
B. 107
C.124
D.128
3.在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ A ）存储方式。
A.顺序表
B. 带头结点的单链表
C.不带头结点的单链表
D. 循环单链表
4.在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜
采用（ C ）存储方式。
A.顺序表
B. 用头指针标识的循环单链表
C. 用尾指针标识的循环单链表
D. 双向链表
5.在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为S,则修改链的
java语句序列是（ D ）。
A.s.setNext(p); q.setNext(s);
B. p.setNext(s.getNext()); s.setNext(p);
C. q.setNext(s.getNext()); s.setNext(p);
D. p.setNext(s); s.setNext(q);
6.在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的
时间复杂度是（ C ）。
A.O(1)
B. O(log2n)
C. O(n)
D. O(n2)
7.要将一个顺序表{a0,a1,……,a n-1}中第i个数据元素a i(0≤i≤n-1)删除，需要移动（ B ）
个数据元素。
A.i
B. n-i-1
C. n-i
D. n-i+1
8.在带头结点的双向循环链表中的p结点之后插入一个新结点s，其修改链的java语句序
列是（ D ）。
A.p.setNext(s); s.setPrior(p); p.getNext().setPrior(s);
s.setNext(p.getPrior());
B.p.setNext(s); p.getNext().setPrior(s); s.setPrior(p);
s.setNext(p.getNext());
C.s.setPrior(p); s.setNext(p.getNext()); p.setNext(s);
p.getNext().setPrior(s);
D.s.setNext(p.getNext()); s.setPrior(p); p.getNext().setPrior(s);
p.setNext(s);
9.顺序表的存储密度是（ B ），而单链表的存储密度是（ A ）。
A．小于1 B. 等于1 C. 大于1 D. 不能确定
10.对于图2.29所示的单链表，下列表达式值为真的是（ D ）。
图2.29 单链表head的存储结构图
A. head.getNext().getData()=='C'
B. head.getData()=='B'
C. P1.getData()==’D’
D. P2.getNext()==null
二、填空题
1.线性表是由n（n≥0）个数据元素所构成的有限序列，其中n为数据元素的个数，称
为线性表的长度，n=0的线性表称为空表。
2.线性表中有且仅有一个开始结点和终端结点，除开始结点和终端结点之外，其它每一个
数据元素有且仅有一个前驱，有且仅有一个后继。
3.线性表通常采用顺序存储和链式存储两种存储结构。若线性表的长度确定或变化不
大，则适合采用顺序存储存储结构进行存储。
4.在顺序表{a0,a1,……,a n-1}中的第i(0≤i≤n-1)个位置之前插入一个新的数据元素，会引
起 n-i 个数据元素的移动操作。
5.在线性表的单链表存储结构中，每一个结点有两个域，一个是数据域，用于存储数据元
素值本身，另一个是指针域，用于存储后继结点的地址。
6.在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行
顺序存取。
7.顺序表中逻辑上相邻的数据元素，其物理位置一定相邻，而在单链表中逻辑上相邻的
数据元素，其物理位置不一定相邻。
8.在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是 O（1）。
9.在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到指定结点p
的前驱，其时间复杂度为 O（n）。
10.若将单链表中的最后一个结点的指针域值改为单链表中头结点的地址值，则这个链表就
构成了循环单链表。
三、算法设计题
1.编写一个顺序表类的成员函数，实现对顺序表就地逆置的操作。所谓逆置，就是把
（a1,a2,…,a n）变成（a n,a n-1,…,a1）；所谓就地，就是指逆置后的数据元素仍存储在原来顺序表的存储空间中，即不为逆置后的顺序表另外分配存储空间。
参考答案:
public void reverse() {
for (int i = 0,j=curLen-1; i < j; i++,j--) {
Object temp = listElem[i];
listElem[i] = listElem[j];
listElem[j] = temp;
}
}
2.编写一个顺序表类的成员函数，实现对顺序表循环右移k位的操作。即原来顺序表为
（a1,a2,…,a n-k,a n-k+1,…, a n），循环向右移动k位后变成（a n-k+1,…, a n ,a1,a2,…,a n-k）。
要求时间复杂度为O（n）。
参考答案:
public void shit(int k) {
