资源描述：
《第2章线性表习题参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、个人收集整理勿做商业用途习题二参考答案一、选择题1.链式存储结构的最大优点是（D )。A.便于随机存取Ｂ.存储密度高C．无需预分配空间ﻩD.便于进行插入和删除操作2.假设在顺序表｛a0，a1，……，ａn-1｝中,每一个数据元素所占的存储单元的数目为４,且第0个数据元素的存储地址为１00，则第７个数据元素的存储地址是(D）。A.106 B．1０７ C.124 Ｄ.１283.在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（A)存储方式。A.顺序表ﻩﻩﻩB．带头结点的单链表C．不带头结点的单链表ﻩﻩﻩD.循环单链表4.在
2、链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用( C)存储方式。A.顺序表ﻩB. 用头指针标识的循环单链表C.用尾指针标识的循环单链表D.双向链表5.在一个单链表中的ｐ和q两个结点之间插入一个新结点,假设新结点为S，则修改链的ｊavａ语句序列是（D )。A.s.seｔNext（p);q.sｅｔNexｔ(s）; Ｂ. p.setNｅxt(s.gｅtNexｔ());ｓ.setNext(ｐ）;C．q.sｅtNeｘt(s.getNext（))；s.setNｅｘt(p)；D.ｐ．ｓetNext（ｓ）; s．se
3、tNｅxｔ(q);6.在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是(C)。A.Ｏ(１) B．O(ｌoｇ2n） C．O(n) D.O(n2）7.要将一个顺序表{a0,a1,……,ａn-1}中第i个数据元素ai(０≤i≤ｎ-1)删除，需要移动(B）个数据元素。A.i Ｂ．n-i-1 C．n-ｉ D．n-i+18.在带头结点的双向循环链表中的p结点之后插入一个新结点ｓ,其修改链的jａｖa语句序列是(Ｄ)。A.p.setNeｘｔ(ｓ);ｓ．setＰrior(p);ｐ.getＮext().se
4、tPriｏｒ(s);s.setNexｔ（ｐ.gｅtPrior(）);B.p．ｓｅtＮext(s); p.gｅtＮext()．ｓetPrior(s)；ｓ.setPrior（p）;s．sｅtNｅxｔ(p．geｔNext（));C.ｓ.ｓetPriｏr(ｐ）；s.seｔNext(p.getNext()）； p.setNext(ｓ);ｐ.getＮexｔ().sｅtPｒior(s);D.s．setNext(ｐ.getＮext（));s．seｔPｒiｏr(p);p．getNｅxt()．ｓｅtPｒｉor(s）； p．setNexｔ(s);9.顺序
5、表的存储密度是（ Ｂ)，而单链表的存储密度是（Ａ ）。Ａ．小于１B．等于１ Ｃ.大于1Ｄ．不能确定10.对于图2.29所示的单链表，下列表达式值为真的是（D ）。ABCEheadDP1P2图2.29单链表head的存储结构图A.heaｄ.getNext().geｔＤaｔa（)＝＝'C' B．ｈeａd.getData()=='Ｂ'C.P1．gｅtＤａta()==’D’ D．P2.geｔNｅxt()==null二、填空题1.线性表是由n(n≥0）个数据元素所构成的有限序列，其中n为数据元素的个数，称为线性表的长度个人收集整
6、理勿做商业用途，ｎ=０的线性表称为空表 。1.线性表中有且仅有一个开始结点和终端结点，除开始结点和终端结点之外，其它每一个数据元素有且仅有一个前驱,有且仅有一个后继 。2.线性表通常采用顺序存储 和链式存储两种存储结构。若线性表的长度确定或变化不大，则适合采用顺序存储存储结构进行存储。3.在顺序表｛a0,ａ1,……,an－1}中的第i(0≤i≤n-1）个位置之前插入一个新的数据元素，会引起n-ｉ个数据元素的移动操作。4.在线性表的单链表存储结构中，每一个结点有两个域，一个是数据域,用于存储数据元素值本身，另一个是指针域，用于存储后继
7、结点的地址。5.在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行顺序存取。7.顺序表中逻辑上相邻的数据元素，其物理位置一定相邻,而在单链表中逻辑上相邻的数据元素，其物理位置 不一定相邻。8.在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是O（1) 。9.在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到指定结点ｐ的前驱,其时间复杂度为 O(n） 。10.若将单链表中的最后一个结点的指针域值改为单链表中头结点的地址值,则这个链表就构成了循环单链表。三、算法设计题1.编写一个顺序表类的
8、成员函数,实现对顺序表就地逆置的操作。所谓逆置，就是把(a1,ａ2,…,an）变成（ａn，an-1，…，a1）;所谓就地，就是指逆置后的数据元素仍存储在原来顺序表的存储空间中,即不为逆置后的顺序表另外分配存储空间。参考答案:publｉ
