第2章 线性表习题参考答案.doc
《第2章 线性表习题参考答案.doc》由会员分享,可在线阅读,更多相关《第2章 线性表习题参考答案.doc(6页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、如有侵权,请联系网站删除,仅供学习与交流第2章 线性表习题参考答案【精品文档】第 6 页习题二参考答案一、选择题1. 链式存储结构的最大优点是( D )。A.便于随机存取B.存储密度高 C.无需预分配空间D.便于进行插入和删除操作 2. 假设在顺序表a0,a1,an1中,每一个数据元素所占的存储单元的数目为4,且第0个数据元素的存储地址为100,则第7个数据元素的存储地址是( D )。A. 106 B. 107 C.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(log2n) C. O(n) D. O(n2)7. 要将一个顺序表a0,a1,an-1中第i个数据元素ai(0in-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.setNe
4、xt(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所示
5、的单链表,下列表达式值为真的是( D )。ABCE headDP1P2图2.29 单链表head的存储结构图A. head.getNext().getData()=C B. head.getData()=BC. P1.getData()=D D. P2.getNext()=null二、填空题1. 线性表是由n(n0)个数据元素所构成的 有限序列 ,其中n为数据元素的个数,称为线性表的 长度 ,n=0的线性表称为 空表 。2. 线性表中有且仅有一个开始结点和终端结点,除开始结点和终端结点之外,其它每一个数据元素有且仅有一个 前驱 ,有且仅有一个 后继 。3. 线性表通常采用 顺序存储 和 链式存
6、储 两种存储结构。若线性表的长度确定或变化不大,则适合采用 顺序存储 存储结构进行存储。4. 在顺序表a0,a1,an-1中的第i(0in-1)个位置之前插入一个新的数据元素,会引起 n-i 个数据元素的移动操作。5. 在线性表的单链表存储结构中,每一个结点有两个域,一个是数据域,用于存储数据元素值本身,另一个是 指针域 ,用于存储后继结点的地址。6. 在线性表的顺序存储结构中可实现快速的随机存取,而在链式存储结构中则只能进行 顺序 存取。7. 顺序表中逻辑上相邻的数据元素,其物理位置 一定 相邻,而在单链表中逻辑上相邻的数据元素,其物理位置 不一定 相邻。8. 在仅设置了尾指针的循环链表中,
7、访问第一个结点的时间复杂度是 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
8、=curLen-1; i j; i+,j-) Object temp = listElemi;listElemi = listElemj;listElemj = 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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第2章 线性表习题参考答案 线性 习题 参考答案
限制150内