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

《第2章 线性表习题参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、用头指针标识的循环单链表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

3、)7.要将一个顺序表{a0,a1,……,an-1}中第i个数据元素ai(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

4、(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．小于1B.等于1C.大于1D.不能确定10.对于图2.29所示的单链表，下列表达式值为真的是（D）。ABCEheadDP1P2图2.29单链表head的存储结构图A.head.getNext().getData()=='C'B.head.getDa

5、ta()=='B'C.P1.getData()==’D’D.P2.getNext()==null二、填空题1.线性表是由n（n≥0）个数据元素所构成的有限序列，其中n为数据元素的个数，称为线性表的长度，n=0的线性表称为空表。1.线性表中有且仅有一个开始结点和终端结点，除开始结点和终端结点之外，其它每一个数据元素有且仅有一个前驱，有且仅有一个后继。2.线性表通常采用顺序存储和链式存储两种存储结构。若线性表的长度确定或变化不大，则适合采用顺序存储存储结构进行存储。3.在顺序表{a0,a1,……,an-1}中的第i(0≤i≤n-1)个位置之前插入一个新的数据元素，会引起n-i个数据元素的

6、移动操作。4.在线性表的单链表存储结构中，每一个结点有两个域，一个是数据域，用于存储数据元素值本身，另一个是指针域，用于存储后继结点的地址。5.在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行顺序存取。7.顺序表中逻辑上相邻的数据元素，其物理位置一定相邻，而在单链表中逻辑上相邻的数据元素，其物理位置不一定相邻。8.在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是O（1）。9.在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到指定结点p的前驱，其时间复杂度为O（n）。10.若将单链表中的最后一个结点的指针域值改为单链表中头结点的地址值

7、，则这个链表就构成了循环单链表。三、算法设计题1.编写一个顺序表类的成员函数，实现对顺序表就地逆置的操作。所谓逆置，就是把（a1,a2,…,an）变成（an,an-1,…,a1）；所谓就地，就是指逆置后的数据元素仍存储在原来顺序表的存储空间中，即不为逆置后的顺序表另外分配存储空间。参考答案:publicvoidreverse(){for(inti=0,j=curLen-1;i