习题二参考答案一、选择题1. 链式存储结构的最大优点是（ D ）。

A.便于随机存取B.存储密度高C.无需预分配空间D.便于进行插入和删除操作2. 假设在顺序表{a 0,a 1,……,a n －1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。

A. 106B. 107C.124D.1283. 在线性表中若经常要存取第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 (log 2n)C. O (n)D. O (n2)7. 要将一个顺序表{a 0,a 1,……,a n-1}中第i 个数据元素a i (0≤i ≤n-1)删除，需要移动（ B ）个数据元素。

A. iB. n-i-1C. n-iD. n-i+18. 在带头结点的双向循环链表中的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. P 1.getData()==’D ’D. P 2.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) {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的最大公约数pp=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();} elsebreak;}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,…,a n）变成（a n,a n-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());}elsereturn -1;//值为x的结点在单链表中不存在return j;}6.编写一个单链表类的成员函数，实现删除带头结点的单链表中数据域值等于x的所有结点的操作。