线性表习题参考答案

1、习题二参考答案一、选择题1. 链式存储结构的最大优点是( D )。A. 便于随机存取B.存储密度高C.无需预分配空间D.便于进行插入和删除操作2. 假设在顺序表ao,ai,，an1中，每一个数据元素所占的存储单元的数目为4,且第0个数据元素的存储地址为100,则第7个数据元素的存储地址是( D )。A. 106 B. 107C.124D.1283. 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用( A )存储方式。A.顺序表B.带头结点的单链表C.不带头结点的单链表D.循环单链表4. 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用(C )存储方式。A.

2、顺序表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

3、 2n) C. O(n) D. O(n2) 7.要将一个顺序表a0,a 1,，an-J中第i个数据元素a (0 < i < n-1)删除，需要移动(B )个数据元素。A. i B. n-i-1C. n-i D. 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

4、);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 )。D * E A5 / 5图2.29单链表head的存储结

5、构图A. head.getNext().getData()=C B. head.getData()='B'C. P1.getData()=''D. P 2.getNext()=null、填空题1. 线性表是由n (n0)个数据元素所构成的有限序列，其中n为数据元素的个数，称为线性表的长度，n=0的线性表称为空表。2. 线性表中有且仅有一个开始结点和终端结点，除开始结点和终端结点之外，其它每一个数据元素有且仅有一个前驱，有且仅有一个后继。3. 线性表通常采用顺序存储飞為式存储 两种存储结构。若线性表的长度确定或变化不大，则适合采用 顺序存储存储结构进行存储。4.

6、在顺序表a o,a i,a n-i中的第i (0 < i < n-1)个位置之前插入一个新的数据元素，会引起n-i个数据元素的移动操作。5. 在线性表的单链表存储结构中，每一个结点有两个域，一个是数据域，用于存储数据元素值本身，另一个是卫针域，用于存储后继结点的地址。6. 在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行顺序存取。7顺序表中逻辑上相邻的数据元素，其物理位置一定相邻，而在单链表中逻辑上相邻的数据元素，其物理位置不一定相邻。8. 在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是O (1)。9. 在含有n个结点的单链表中，若要删除一个指

7、定的结点p,则首先必须找到指定结点p的前驱，其时间复杂度为O (n)。10. 若将单链表中的最后一个结点的指针域值改为单链表中头结点的地址值，则这个链表就构成了循环单链表。三、算法设计题1. 编写一个顺序表类的成员函数，实现对顺序表就地逆置的操作。所谓逆置，就是把(a1,a 2, - ,an)变成(an,an-1,a 1);所谓就地，就是指逆置后的数据元素仍存储在原来顺序表的存储空间中，即不为逆置后的 顺序表另外分配存储空间。参考答案：public void reverse。for (int i = 0,j=curLe n_1; i < j; i+,j-) Object temp = l

8、istElemi;listElemi = listElemj; listElemj = temp;2. 编写一个顺序表类的成员函数，实现对顺序表循环右移k位的操作。即原来顺序表为(a1,a2,a n-k,a n-k+1,an),循环向右移动k位后变成(an-k+1,a n ,a 1",an-k )。要求时间复杂度为 O (n)。参考答案：public void shit(i nt k) int n=curLe n, p=0,i,j,l;Object temp;for(i=1;i<=k;i+)if(n%i=0&&k%i=0) /求n和k的最大公约数 pp=i;fo

9、r(i=0;i<p;i+)j=i;l=(i+n-k)% n;temp=listElemi;while(l!=i)listElemj=listEleml;j=l;l=(j+n-k)% n;/ 循环右移一步listElemj=temp;分析：要把数组listElem 的元素循环右移k位,则listElemO 移至listElemk, listElemk移至listElem2k 直到最终回到 listElem0. 然而这并没有全部解决问题 , 因为有可能有的元素在此过程中始终没有被访问过，而是被跳了过去分析可知，当n和k的最大公约数为p时,只要分别以listElemO,listElem1,.

10、listElemp-1为起点执行上述算法 , 就可以保证每一个元素都被且仅被右移一次 , 从而满足题目要求也就是说,A的所有元素分别处在p个”循环链"上面举例如下：n=15,k=6,则 p=3.第一条链 ： listElem0->listElem6, listElem6->listElem12, listElem12-> listElem3, listElem3-> listElem9, listElem9-> listElem0.第二条链 ： listElem1->listElem7, listElem7->listElem13, list

11、Elem13-> listElem4, listElem4->listElem10, listElem10-> listElem1.第三条链 ： listElem2-> listElem8, listElem8-> listElem14, listElem14->listElem5, listElem5->listElem11, listElem11->listElem2.恰好使所有元素都右移一次 .虽然未经数学证明 , 但相信上述规律应该是正确的 .3. 编写一个单链表类的成员函数，实现在非递减的有序单链表中插入一个值为x 的数据元素，并使单链

12、表仍保持有序的操作。参考答案 (方法一 )：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

13、(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. 编写一个单链表类的成员函数，实现对带头结点的单链表就地逆置

14、的操作。所谓逆置，就是把(ai,a2,an)变成(an,an-i,ai);所谓就地，就是指逆置后的结点仍存储在原来单链表的存储空间中，只不过通过修改 链来改变单链表中每一个结点之间的逻辑位置关系。参考答案 :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. 编写一个单链表类的成员函数，

15、实现删除不带头结点的单链表中数据域值等于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;/

16、计数器的值增 1if (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 指

17、向首结点 ,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. 编写一个多项式类的成员函数，实现将一个用循环链表表示的稀疏多项式分解成两个多项式的操作，并使两 个多项式中各自仅含奇次项或偶次项。要求利用原来循环链表

18、中的存储空间构成这两个链表。 参考答案 :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