第2章线性表习题参考答案.doc

习题二参考答案
一、选择题
1. 链式存储结构的最大优点是（ D ）。
A.便于随机存取 B.存储密度高
C.无需预分配空间 D.便于进行插入和删除操作
2. 假设在顺序表{a0,a1,……,an－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,……,an-1}中第i个数据元素ai(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 ）。
A
B
C
E
head
D
P1
P2

图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,……,an-1}中的第i(0≤i≤n-1)个位置之前插入一个新的数据元素，会引起 n-i 个数据元素的移动操作。
5. 在线性表的单链表存储结构中，每一个结点有两个域，一个是数据域，用于存储数据元素值本身，另一个是 指针域 ，用于存储后继结点的地址。
6. 在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行
顺序 存取。
7. 顺序表中逻辑上相邻的数据元素，其物理位置 一定 相邻，而在单链表中逻辑上相邻的数据元素，其物理位置 不一定 相邻。
8. 在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是 O（1） 。
9. 在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到 指定结点p的前驱 ，其时间复杂度为 O（n） 。
10. 若将单链表中的最后一个结点的指针域值改为单链表中头结点的地址值，则这个链表就构成了 循环单链表 。
三、算法设计题
1. 编写一个顺序表类的成员函数，实现对顺序表就地逆置的操作。所谓逆置，就是把（a1,a2,…,an）变成（an,an-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,…,an-k,an-k+1,…, an），循环向右移动k位后变成（an-k+1,…, an ,a1,a2,…,an-k）。要求时间复杂度为O（n）。
参考答案:
public void shit(int k) {
int n=curLen,p=0,i,j,l;
Object temp;
for(i=1;i<=k;i++)
if(n%i==0&&k%i==0) //求n和k的最大公约数p
p=i;
for(i=0;i<p;i++){
j=i;
l=(i+n-k)%n;
temp=listElem[i];
while(l!=i){
listElem[j]=listElem[l];
j=l;
l=(j+n-k)%n;
}// 循环右移一步
listElem[j]=temp;
}
}
分析：
要把数组listElem的元素循环右移k位,则listElem[0]移至listElem[k], listElem[k]移至listElem[2k]......直到最终回到listElem[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以listElem[0], listElem[1],... listElem[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个"循环链"上面.举例如下:
n=15,k=6,则p=3.
第一条链: listElem[0]->listElem[6], listElem[6]->listElem[12], listElem[12]-> listElem[3], listElem[3]-> listElem[9], listElem[9]-> listElem[0].
第二条链: listElem[1]->listElem[7], listElem[7]->listElem[13], listElem[13]-> listElem[4], listElem[4]->listElem[10], listElem[10]-> listElem[1].
第三条链: listElem[2]-> listElem[8], listElem[8]-> listElem[14], listElem[14]->listElem[5], listElem[5]->listElem[11], listElem[11]->listElem[2].
恰好使所有元素都右移一次.
虽然未经数学证明,但相信上述规律应该是正确的.

3. 编写一个单链表类的成员函数，实现在非递减的有序单链表中插入一个值为x的数据元素，并使单链表仍保持有序的操作。
参考答案(方法一):
public void insert(int x) {
Node p = head.getNext();//p指向首结点
Node q = head;// q用来记录p的前驱结点
int temp;
while (p != null) {
temp = ((Integer) p.getData()).intValue();
if (temp < x) {
q = p;
p = p.getNext();
} else
break;
}

Node s = new Node(x); // 生成新结点
s.setNext(p);// 将s结点插入到单链表的q结点与p结点之间
q.setNext(s);
}
参考答案(方法二):
public void insert(int x) {
Node p = head.getNext(); //p指向首结点
while (p.getNext()!= null&&((Integer) p.getNext().getData()).intValue()<x) {
p = p.getNext();
}
Node s = new Node(x); // 生成新结点
s.setNext(p.getNext());// 将s结点插入到单链表的q结点与p结点之间
p.setNext(s);
}

4. 编写一个单链表类的成员函数，实现对带头结点的单链表就地逆置的操作。所谓逆置，就是把（a1,a2,…,an）变成（an,an-1,…,a1）；所谓就地，就是指逆置后的结点仍存储在原来单链表的存储空间中，只不过通过修改链来改变单链表中每一个结点之间的逻辑位置关系。
参考答案:
public void reverse() { //实现对单链表就地逆置(采用的是头插法)
Node p = head.getNext();
head.setNext(null);
Node q;
while (p != null) {
q = p.getNext();
p.setNext(head.getNext());
head.setNext(p);
p = q;
}
}

5. 编写一个单链表类的成员函数，实现删除不带头结点的单链表中数据域值等于x的第一个结点的操作。若删除成功，则返回被删除结点的位置；否则，返回-1。
参考答案:
public int remove(Object x) {
Node p = head;// 初始化,p指向首结点
Node q=null; //q用来记录p的前驱结点
int j = 0; //j为计数器
// 从单链表中的首结点元素开始查找，直到p.getData()指向元素x或到达单链表的表尾
while (p != null && !p.getData().equals(x)) {
q=p;
p = p.getNext();// 指向下一个元素
++j;// 计数器的值增1
}
if (p!=null&&q==null) //删除的是单链表中的首结点
head=p.getNext();
else if (p != null) {// 删除的是单链表中的非首结点
q.setNext(p.getNext());
}
else
return -1;//值为x的结点在单链表中不存在
return j;
}

6. 编写一个单链表类的成员函数，实现删除带头结点的单链表中数据域值等于x的所有结点的操作。要求函数返回被删除结点的个数。
参考答案:
public int removeAll(Object x) {
Node p = head.getNext();// 初始化,p指向首结点,j为计数器
Node q = head; // 用来记录p的前驱结点
int j = 0;// 用来记录被删除结点的个数
while (p != null) { // 从单链表中的首结点开始对整个链表遍历一次
if (p.getData().equals(x)) {
q.setNext(p.getNext());
++j;// 计数器的值增1
} else
q = p;
p = p.getNext();// 指向下一个元素
}
return j;// 返回被删除结点的个数
}
7. 编写一个多项式类的成员函数，实现将一个用循环链表表示的稀疏多项式分解成两个多项式的操作，并使两个多项式中各自仅含奇次项或偶次项。要求利用原来循环链表中的存储空间构成这两个链表。
参考答案:
public CircleLinkList [] separatePolyn(CircleLinkList cList) {
CircleLinkList cList1 = new CircleLinkList();// 含奇次项的多项式
Node p1 = cList1.getHead();// p2指向奇次项多项式的头结点
CircleLinkList cList2 = new CircleLinkList();// 含偶次项的多项式
Node p2 = cList2.getHead();// p2指向偶次项多项式的头结点
Node p = cList.getHead().getNext();// 原多项式的首结点
while (p!=cList.getHead()) {
PolynNode data = (PolynNode) p.getData();
int expn = data.getExpn();
if (expn % 2 != 0) {// 加入奇次项多项式
p1.setNext(p);
p1 = p;
} else {// 加入偶此项多项式
p2.setNext(p);
p2 = p;
}
p = p.getNext();
}
p1.setNext(cList1.getHead());
p2.setNext(cList2.getHead());
CircleLinkList[] polyns = { cList1, cList2 };
return polyns;
}