-线性表习题参考答案_第1页
-线性表习题参考答案_第2页
-线性表习题参考答案_第3页
-线性表习题参考答案_第4页
免费预览已结束,剩余1页可下载查看

付费下载

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

2、点,则宜采用( 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 个结点的有序单链表中插入一个新结点, 使单链表仍

3、然保持有序的算法的时间复杂度是 ( C )。 A. O(1) B.O(log 2n) C. O(n) D. O(n2)7. 要将一个顺序表 a 0,a 1, ,a n-1 中第i 个数据元素 ai (0 i n-1)删除,需要移动( B )个数据元素。 A. i B. n-i-1 C. 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.set

4、Next(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.

5、29 所示的单链表,下列 表达式值为真 的是( D )。图 2.29 单链表 head 的存储结构图A. head.getNext().getData()= C B. head.getData()= BC. P1.getData()= D D. P 2.getNext()=null二、填空题1. 线性表是由 n( n0)个数据元素所构成的 有限序列 ,其中 n 为数据元素的个数,称为线性表的 长度 ,n=0 的线性表称为 空表 。2. 线性表中有且仅有一个开始结点和终端结点,除开始结点和终端结点之外,其它每一个数据元素有且仅有一 个 前驱 ,有且仅有一个 后继 。3. 线性表通常采用 顺序存储

6、 和 链式存储 两种存储结构。 若线性表的长度确定或变化不大, 则适合采用 顺序 存储 存储结构进行存储。4. 在顺序表 a 0,a 1, ,a n-1 中的第 i (0 i n-1) 个位置之前插入一个新的数据元素,会引起 n-i 个数据元素 的移动操作。5. 在 线性表的单链表存储结构中, 每一个结点有两个域, 一个是数据域, 用于存储数据元素值本身, 另一个是 指 针域 ,用于存储后继结点的地址。6. 在线性表的顺序存储结构中可实现快速的随机存取,而在链式存储结构中则只能进行 顺序 存取。7. 顺序表中逻辑上相邻的数据元素,其物理位置 一定 相邻,而在单链表中逻辑上相邻的数据元素,其物理

7、位 置 不一定 相邻。8. 在仅设置了尾指针的循环链表中,访问第一个结点的时间复杂度是O(1) 。9. 在含有 n个结点的单链表中,若要删除一个指定的结点p,则首先必须找到 指定结点 p 的前驱 ,其时间复杂度为 O( n) 。10. 若将单链表中的最后一个结点的指针域值改为单链表中头结点的地址值,则这个链表就构成了 循环单链 表。三、算法设计题1. 编写一个顺序表类的成员函数,实现对顺序表就地逆置的操作。所谓逆置,就是把(a1,a 2, ,a n)变成( an,a n-1 , ,a 1);所谓就地,就是指逆置后的数据元素仍存储在原来顺序表的存储空间中,即不为逆置后的 顺序表另外分配存储空间。

8、参考答案 :public void reverse() for (int i = 0,j=curLen-1; i j; i+,j-) Object temp = listElemi; listElemi = listElemj; listElemj = temp;2. 编写一个顺序表类的成员函数, 实现对顺序表循环右移 k 位的操作。 即原来顺序表为 (a1,a 2, ,a n-k,a n-k+1, , an),循环向右移动 k 位后变成( an-k+1, , a n ,a 1,a2, ,a n-k )。要求时间复杂度为 O(n)。 参考答案 :public void shit(int k)

9、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;ilistElem6, listElem6-listElem12, listElem12- listElem3, listElem3- listElem9, listElem9- listElem0.第二条链 : listElem1-listElem7, listElem7-listElem13, listElem13- listElem4, listElem4-listElem10, listElem10-

10、listElem1.第三条链 : listElem2- listElem8, listElem8- listElem14, listElem14-listElem5, listElem5-listElem11, listElem11-listElem2.恰好使所有元素都右移一次 . 虽然未经数学证明 , 但相信上述规律应该是正确的 .3. 编写一个单链表类的成员函数,实现在非递减的有序单链表中插入一个值为 x 的数据元素,并使单链表仍保 持有序的操作。参考答案 (方法一 ):public void insert(int x) Node p = head.getNext();/p 指向首结点No

11、de 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 指向首结点w

12、hile (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,a 2, ,a n)变成( an,a n-1, ,a 1);所谓就地,就是指逆置后的结点仍存储在原来单链表的存储空间中,只不过通过修改 链来改变

13、单链表中每一个结点之间的逻辑位置关系。参考答案 :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 i

14、nt 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;/ 计数器的值增 1if (p!=null&q=null) / 删除的是单链表中的首结点 head=p.getNext();else if (p != null) /删除

15、的是单链表中的非首结点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) /从单链表中的首结点

16、开始对整个链表遍历一次if (p.getData().equals(x) q.setNext(p.getNext();+j;/ 计数器的值增 1 elseq = 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 da

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论