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

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

《第2章 线性表习题参考答案.docx》由会员分享，可在线阅读，更多相关《第2章 线性表习题参考答案.docx（21页珍藏版）》请在冰点文库上搜索。

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

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

二参考答案习题一、选择题

1.链式存储结构的最大优点是（D）。

A.便于随机存取B.存储密度高

C.无需预分配空间D.便于进行插入和删除操作

2.假设在顺序表{a,a,……,a}中，每一个数据元素所占10n1－的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（D）。

A.106B.107C.124D.128

3.在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（A）存储方式。

A.顺序表B.带头结点的单链表

C.不带头结点的单链表D.循环单链表

4.在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（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个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（C）。

A.O

（1）B.O（logn）C.O（n）D.O（n2）27.要将一个顺序表{a,a,……,a}中第i个数据元素a（0in-101

≤i≤n-1）删除，需要移动（B）个数据元素。

A.iB.n-i-1C.n-iD.n-i+1

8.在带头结点的双向循环链表中的p结点之后插入一个新结点s，其修改链的java语句序列是（D）。

A.p.setNext（s）;

s.setPrior（p）;

p.getNext（）.setPrior（s）;

s.setNext（p.getPrior（））;

p.getNext（）.setPrior（s）;

.setNext（s）;B.ps.setPrior（p）;

s.setNext（p.getNext（））;

s.setNext（p.getNext（））;s.setPrior（p）;C.

p.setNext（s）;

p.getNext（）.setPrior（s）;

s.setPrior（p）;

D.s.setNext（p.getNext（））;

p.getNext（）.setPrior（s）;

p.setNext（s）;

，而单链表的存储密度是序表的存储密度是（9.顺B））A。

（不1D.大于1C.等于1B.．小于A．

能确定的是表达式值为真对于图2.29所示的单链表，下列10.

。

（D）hea

D

A

B

C

P21head的存储结构图单链表图2.29

B.A.head.getNext（）.getData（）=='C'

'B'

head.getData（）==D.DPC..getData（）==''1.getNext（）==nullP2二、填空题，n线性表是由（n≥0）个数据元素所构成的有限序列1.的其中n为数据元素的个数，称为线性表的长度n=0，线性表称为空表。

性表中有且仅有一个开始结点和终端结点，除开始结2.线点和终端结点之外，其它每一个数据元素有且仅有一个。

，有且仅有一个后继前驱两种存储结和链式存储3.线性表通常采用顺序存储

顺序构。

若线性表的长度确定或变化不大，则适合采用

存储结构进行存储。

存储

个位置n-1）≤i≤……,,a顺序表4.在{a,a（0i中的第}n-110．

个数据元素的n-i之前插入一个新的数据元素，会引起移动操作。

线性表的单链表存储结构中，每一个结点有两个域，在5.指一个是数据域，用于存储数据元素值本身，另一个是

，用于存储后继结点的地址针域线性表的顺序存储结构中可实现快速的随机存取，而6.在在链式存储结构中则只能进行存取。

顺序相一定顺序表中逻辑上相邻的数据元素，其物理位置7.不邻，而在单链表中逻辑上相邻的数据元素，其物理位置

一定相邻。

仅设置了尾指针的循环链表中，访问第一个结点的时在8.

O

（1）。

间复杂度是个结点的单链表中，若要删除一个指定的结点n9.在含有，其时间复杂度指定结点p的前驱p，则首先必须找到。

（n）为O若将单链表中的最后一个结点的指针域值改为单链表10.

。

中头结点的地址值，则这个链表就构成了循环单链表

三、算法设计题

1.编写一个顺序表类的成员函数，实现对顺序表就地逆置的操作。

所谓逆置，就是把（a,a,…,a）变成n12（a,a,…,a）；所谓就地，就是指逆置后的数据元素仍1nn-1即不为逆置后的顺序表存储在原来顺序表的存储空间中，

另外分配存储空间。

参考答案:

publicvoidreverse（）{

for（inti=0,j=curLen-1;i

Objecttemp=listElem[i];

listElem[i]=listElem[j];

listElem[j]=temp;

}

}

2.编写一个顺序表类的成员函数，实现对顺序表循环右移k位的操作。

即原来顺序表为（a,a,…,a,a,…,a），nn-k12n-k+1循环向右移动k位后变成（a,…,a,a,a,…,a）。

n-kn-k+112n要求时间复杂度为O（n）。

参考答案:

publicvoidshit（intk）{

intn=curLen,p=0,i,j,l;

Objecttemp;

for（i=1;i<=k;i++）

if（n%i==0&&k%i==0）//求n和k的最大公约数p

p=i;

for（i=0;i

j=i;

l=（i+n-k）%n;

temp=listElem[i];

while（l!

=i）{

listElem[j]=listElem[l];

j=l;

l=（j+n-k）%n;

}//循环右移一步

listElem[j]=temp;

}

}

分析：

要把数组listElem的元素循环右移k位,则listElem[0]移至listElem[k],listElem[k]移至listElem[2k]......直到最终回到listElem[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以listElem[0],listElem[1],...listElem[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个循环链上面.举例如下:

n=15,k=6,则p=3.

第一条链:

listElem[0]->listElem[6],

listElem[6]->listElem[12],listElem[12]->

listElem[3],listElem[3]->listElem[9],

listElem[9]->listElem[0].

第二条链:

listElem[1]->listElem[7],

listElem[7]->listElem[13],listElem[13]->

listElem[4],listElem[4]->listElem[10],

listElem[10]->listElem[1].

第三条链:

listElem[2]->listElem[8],

listElem[8]->listElem[14],

listElem[14]->listElem[5],

listElem[5]->listElem[11],

listElem[11]->listElem[2].

恰好使所有元素都右移一次.

虽然未经数学证明,但相信上述规律应该是正确的.

3.编写一个单链表类的成员函数，实现在非递减的有序单链表中插入一个值为x的数据元素，并使单链表仍保持有序的操作。

参考答案（方法一）:

publicvoidinsert（intx）{

Nodep=head.getNext（）;//p指向首结点

Nodeq=head;//q用来记录p的前驱结点

inttemp;

while（p!

=null）{

temp

（（Integer）

=

p.getData（））.intValue（）;

if（temp

q=p;

p=p.getNext（）;

}else

break;

}

Nodes=newNode（x）;//生成新结点

s.setNext（p）;//将s结点插入到单链表的q结点与p结点之间

q.setNext（s）;

}

参考答案（方法二）:

publicvoidinsert（intx）{

Nodep=head.getNext（）;//p指向首结点while（p.getNext（）!

=null&&（（Integer）p.getNext（）.getData（））.intValue（）

p=p.getNext（）;

}

Nodes=newNode（x）;//生成新结点

s.setNext（p.getNext（））;//将s结点插入到单链表的q结点与p结点之间

p.setNext（s）;

}

4.编写一个单链表类的成员函数，实现对带头结点的单链表就地逆置的操作。

所谓逆置，就是把（a,a,…,a）变n21．

成（a,a,…,a）；所谓就地，就是指逆置后的结点仍存1n-1n储在原来单链表的存储空间中，只不过通过修改链来改变单链表中每一个结点之间的逻辑位置关系。

参考答案:

publicvoidreverse（）{//实现对单链表就地逆置（采用的是头插法）

Nodep=head.getNext（）;

head.setNext（null）;

Nodeq;

while（p!

=null）{

q=p.getNext（）;

p.setNext（head.getNext（））;

head.setNext（p）;

p=q;

}

}

5.编写一个单链表类的成员函数，实现删除不带头结点的单链表中数据域值等于x的第一个结点的操作。

若删除成功，则返回被删除结点的位置；否则，返回-1。

参考答案:

publicintremove（Objectx）{

指向首结点,p初始化Nodep=head;//

Nodeq=null;//q用来记录p的前驱结点

intj=0;//j为计数器

//从单链表中的首结点元素开始查找，直到p.getData（）指向元素x或到达单链表的表尾

while（p!

=null&&!

p.getData（）.equals（x））

{

q=p;

p=p.getNext（）;//指向下一个元素

++j;//计数器的值增1

}

if（p!

=null&&q==null）//删除的是单链表中的首结点

head=p.getNext（）;

elseif（p!

=null）{//删除的是单链表中的非首结点

q.setNext（p.getNext（））;

}

else

return-1;//值为x的结点在单链表中不存在

returnj;

}

6.编写一个单链表类的成员函数，实现删除带头结点的单链表中数据域值等于x的所有结点的操作。

要求函数返回被删除结点的个数。

．

参考答案:

publicintremoveAll（Objectx）{

Nodep=head.getNext（）;//初始化,p指向首结点,j为计数器

Nodeq=head;//用来记录p的前驱结点

intj=0;//用来记录被删除结点的个数

while（p!

=null）{//从单链表中的首结点开始对整个链表遍历一次

if（p.getData（）.equals（x））{

q.setNext（p.getNext（））;

++j;//计数器的值增1

}else

q=p;

p=p.getNext（）;//指向下一个元素

}

returnj;//返回被删除结点的个数

}

7.编写一个多项式类的成员函数，实现将一个用循环链表表示的稀疏多项式分解成两个多项式的操作，并使两个多项式中各自仅含奇次项或偶次项。

要求利用原来循环链表中的存储空间构成这两个链表。

参考答案:

[]

CircleLinkList

public

separatePolyn（CircleLinkListcList）{

CircleLinkList

cList1

=

new

CircleLinkList（）;//含奇次项的多项式

Nodep1=cList1.getHead（）;//p2指向奇次项

多项式的头结点

CircleLinkList

cList2

=

new

CircleLinkList（）;//含偶次项的多项式

Nodep2=cList2.getHead（）;//p2指向偶次项多项式的头结点

Nodep=cList.getHead（）.getNext（）;//原多项式的首结点

while（p!

=cList.getHead（））{

PolynNodedata=（PolynNode）p.getData（）;

intexpn=data.getExpn（）;

if（expn%2!

=0）{//加入奇次项多项式

p1.setNext（p）;

p1=p;

}else{//加入偶此项多项式

p2.setNext（p）;

p2=p;

}

p=p.getNext（）;

}

p1.setNext（cList1.getHead（））;

p2.setNext（cList2.getHead（））;

CircleLinkList[]polyns={cList1,cList2};

returnpolyns;

}