数据结构Java版第二章习题.docx
《数据结构Java版第二章习题.docx》由会员分享，可在线阅读，更多相关《数据结构Java版第二章习题.docx（22页珍藏版）》请在冰点文库上搜索。
数据结构Java版第二章习题
（按照自己的情况选作部分习题，不要抄袭）
第二章习题
顺序存储线性表
一判断题
1．线性表的逻辑顺序与存储顺序总是一致的。
×
2．顺序存储的线性表可以按序号随机存取。
√
3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。
×
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。
√
5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
×
6．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。
√
二单选题（请从下列A，B，C，D选项中选择一项）
1．线性表是（A）。
（A）一个有限序列，可以为空；（B）一个有限序列，不能为空；
（C）一个无限序列，可以为空；（D）一个无序序列，不能为空。
2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。
插入一个元素时平均要移动表中的（A）个元素。
（A）n/2（B）n+1/2（C）n-1/2（D）n
三填空题
1．在顺序表中做插入操作时首先检查___表是否满了______________。
四算法设计题
1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。
试写一算法，将x插入到线性表的适当位置上，以保持线性表的有序性。
并且分析算法的时间复杂度。
2．已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。
3．编写一个函数，从一给定的顺序表A中删除值在x~y（x<=y）之间的所有元素，要求以较高的效率来实现。
提示：
可以先将顺序表中所有值在x~y之间的元素置成一个特殊的值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值的元素后，移动其后面的元素将其删除掉。
4．线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使R中的字符按字母字符、数字字符和其它字符的顺序排列。
要求利用原来的存储空间，元素移动次数最小。
（研54）
5．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。
即将线性表
（a1,a2,…,am,b1,b2,…,bn）改变为：
（b1,b2,…,bn,a1,a2,…,am）。
五上机实习题目
约瑟夫环问题
约瑟夫环问题：
设编号为1，2，3，……，n的n（n>0）个人按顺时针方向围坐一圈，每个人持有一个正整数密码。
开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。
如此下去，直到所有人全部出列为止。
令n最大值取30。
要求设计一个程序模拟此过程，求出出列编号序列。
package算法设计;
importjava.util.ArrayList;
importjava.util.List;
importjava.util.Scanner;
publicclassYueSeFu{
publicstaticvoidmain（String[]args）{
Scannerscan=newScanner（System.in）;
System.out.print（"请输入总人数：
"）;
inttotalNum=scan.nextInt（）;
System.out.print（"请输入报数的大小：
"）;
intcycleNum=scan.nextInt（）;
yuesefu（totalNum,cycleNum）;
scan.close（）;
}
publicstaticvoidyuesefu（inttotalNum,intcountNum）{
//初始化人数
Liststart=newArrayList（）;
for（inti=1;i<=totalNum;i++）{
start.add（i）;
}
//从第K个开始计数
intk=0;
while（start.size（）>0）{
k=k+countNum;
//第m人的索引位置
k=k%（start.size（））-1;
//判断是否到队尾
if（k<0）{
System.out.println（start.get（start.size（）-1））;
start.remove（start.size（）-1）;
k=0;
}else{
System.out.println（start.get（k））;
start.remove（k）;
}
}
}
}
链式存储线性表
一判断题
1．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
×
2．线性表的链式存储结构优于顺序存储结构。
×
3．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
√
4．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
×
二单选题（请从下列A，B，C，D选项中选择一项）
1．线性表是（A）。
（A）一个有限序列，可以为空；（B）一个有限序列，不能为空；
（C）一个无限序列，可以为空；（D）一个无序序列，不能为空。
2．线性表采用链式存储时，其地址（D）。
（A）必须是连续的；（B）部分地址必须是连续的；
（C）一定是不连续的；（D）连续与否均可以。
3．用链表表示线性表的优点是（C）。
（A）便于随机存取
（B）花费的存储空间较顺序存储少
（C）便于插入和删除
（D）数据元素的物理顺序与逻辑顺序相同
4.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（D）存储方式最节省运算时间。
（A）单链表
（B）双链表
（C）单循环链表
（D）带头结点的双循环链表
5．循环链表的主要优点是（D）。
（A）不在需要头指针了
（B）已知某个结点的位置后，能够容易找到他的直接前趋
（C）在进行插入、删除运算时，能更好的保证链表不断开
（D）从表中的任意结点出发都能扫描到整个链表
6．下面关于线性表的叙述错误的是（B）。
（A）线性表采用顺序存储，必须占用一片地址连续的单元；
（B）线性表采用顺序存储，便于进行插入和删除操作；
（C）线性表采用链式存储，不必占用一片地址连续的单元；
（D）线性表采用链式存储，不便于进行插入和删除操作；
7．单链表中，增加一个头结点的目的是为了（ C）。
（A）使单链表至少有一个结点（B）标识表结点中首结点的位置
（C）方便运算的实现（D）说明单链表是线性表的链式存储
8．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。
（A）单链表（B）仅有头指针的单循环链表
（C）双链表（D）仅有尾指针的单循环链表
9．若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省运算时间（C）。
（A）单链表（B）顺序表
（C）双链表（D）单循环链表
三填空题
1．带头结点的单链表H为空的条件是__H->next==NULL_____。
1．非空单循环链表L中*p是尾结点的条件是___p->next==L________。
3．在一个单链表中p所指结点之后插入一个由指针f所指结点，应执行s->next=__p->next___;和p->next=____s_________的操作。
4．在一个单链表中p所指结点之前插入一个由指针f所指结点，可执行以下操作：
s->next=_p->next_______;
p->next=s;
t=p->data;
p->data=___s->data________;
s->data=____t_______;
四算法设计题
1.已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x的结点插入到表L中，使得L仍然有序。
并且分析算法的时间复杂度。
packagexiti;
classLii{
intdata;
Liinext;
publicLii（）{
data=0;
}
publicLii（intid）{
data=id;
}
publicvoiddisplay（）{
System.out.print（data+""）;
}
}
classLii_2{
publicLiifirst;
publicLii_2（）{
first=newLii（）;
}
publicbooleanisEmpty（）{
return（first.next==null）;
}
publicbooleaninsert_2（intid）{
Liinewnode=newLii（id）;
Liip=first;
while（p.next!
=null&&p.next.datap=p.next;
newnode.next=p.next;
p.next=newnode;
returntrue;
}
publicvoidlistdisplay（）{
Liip=first;
System.out.println（"显示链表：
"）;
while（p!
=null）{
p.display（）;
p=p.next;
}
System.out.println（）;
System.out.println（"**************"）;
}
}
publicclassL{
publicstaticvoidmain（String[]args）{
Lii_2s1=newLii_2（）;
for（inti=1;i<=9;i=i+2）{
s1.insert_2（i）;
}
s1.listdisplay（）;
s1.insert_2
（2）;
s1.listdisplay（）;
}
}
时间复杂度：
O（elenum）
2.假设有两个已排序的单链表A和B，编写一个函数将他们合并成一个链表C而不改变其排序性。
packagexiti1;
classlink{
intdata;//数据域（结点关键字）
linknext;//指针域（指向下一结点）
publiclink（intid）{//结点构造方法
data=id;//结点构造方法
}
publicvoiddisplay（）{//显示自身的数据域
System.out.print（data+""）;
}
}
classlink_1{
linkfirst;//单链表的头指针
publiclink_1（）{//构造方法
first=null;//空单链表，头指针为空
}
//从单链表最前面插入一个新结点，作为第一个结点
publicbooleaninsert_1（intid）{
linknewLink=newlink（id）;
linkp;
if（first==null）
first=newLink;
else{
p=first;
while（p.next!
=null）p=p.next;p.next=newLink;}
returntrue;
}
publicintget（intindex）{
linkp=first;
if（p!
=null&&index>=0）{
intj=0;
while（p!
=null&&jj++;
p=p.next;
}
if（p!
=null）
returnp.data;
}
return0;
}
publicintLength（）{
linkp=first;
inti=0;
while（p!
=null）{
p=p.next;
i++;
}
returni;
}
//显示全部链表
publicvoidlistdisplay（）{
linkp=first;
System.out.println（"显示链表：
"）;
while（p!
=null）{
p.display（）;
p=p.next;
}
System.out.println（）;
System.out.println（"*****************"）;
}
}
publicclassAB{
publicstaticlink_1Merge（link_1A,link_1B）{
intl=A.Length（）+B.Length（）;
link_1C=newlink_1（）;
intj=0,iA=0,iB=0;
while（iAif（A.get（iA）C.insert_1（A.get（iA++））;
else
C.insert_1（B.get（iB++））;
}
for（;iAC.insert_1（A.get（iA++））;
for（;iBC.insert_1（B.get（iB++））;
returnC;
}
publicstaticvoidmain（String[]args）{
link_1s1=newlink_1（）;
link_1s2=newlink_1（）;
s1.insert_1（12）;
s1.insert_1（15）;
s1.insert_1（19）;
s1.insert_1（20）;
s1.insert_1（23）;
s1.listdisplay（）;
s2.insert_1（10）;
s2.insert_1（14）;
s2.insert_1（17）;
s2.insert_1（21）;
s2.insert_1（26）;
s2.listdisplay（）;
link_1s3=Merge（s1,s2）;
s3.listdisplay（）;
}
}
3.假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写一个函数删除该结点的前趋结点。
4.已知两个单链表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素递增的单链表形式存储。
packagexiti;
classlink{
publicintdata;//数据域（结点关键字）
publiclinknext;////指针域（指向下一结点）
publiclink（intid）{//结点构造方法
data=id;
}
publicvoidDisplay（）{//显示自身的数据域
System.out.print（data+""）;
}
}
classlinkList{
linkfirst;//单链表的头指针
publiclinkList（）{//构造方法
first=null;//空单链表，头指针为空
}
//在单链表尾部插入一个新结点
publicbooleaninsertBack（intid）{
linknewlink=newlink（id）;//诞生新结点newlink4
linkp;//辅助结点指针
if（first==null）
first=newlink;
else{
p=first;//指向第一结点
while（p.next!
=null）
p=p.next;//把p移到最后一个结点
p.next=newlink;//把新结点接在p所指结点的后面
}
returntrue;
}
publicvoidlistDisplay（）{//显示链表
linkp=first;//指向第一个结点
System.out.println（"显示链表：
"）;
while（p!
=null）{
p.Display（）;//显示结点
p=p.next;
}
System.out.println（"*******"）;
}
publiclinkListinterSection（linkListA,linkListB）{
linkListC;
linkpa,pb;
C=newlinkList（）;
pa=A.first;
pb=B.first;
while（pa!
=null）{
while（pb!
=null）{//和B链表的每个元素遍历
if（pa.data==pb.data）//相等的时候给C链表插入pa.fd
C.insertBack（pa.data）;
pb=pb.next;
}
pa=pa.next;
pb=B.first;
}
returnC;
}
}
publicclassABC{
publicstaticvoidmain（String[]args）{
linkListA=newlinkList（）;
linkListB=newlinkList（）;
linkListC=newlinkList（）;
A.insertBack（10）;
A.insertBack（12）;
A.insertBack（15）;
A.insertBack（18）;
A.listDisplay（）;
B.insertBack（13）;
B.insertBack（10）;
B.insertBack（12）;
B.insertBack（18）;
B.listDisplay（）;
C=C.interSection（A,B）;
C.listDisplay（）;
}
}
5.设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度freq域，在链表被起用之前，该域其值初始化为零。
每当在链表进行一次Locata（L,x）运算后，令值为x的结点中的freq域增1，并调整表中结点的次序，使其按访问频度的递减序列排列，以便使频繁访问的结点总是靠近表头。
试写一个算法满足上述要求的Locata（L,x）算法。
五上机实习题目
1．一元多项式的相加
提示：
（1）一元多项式的表示问题：
对于任意一元多项式：
Pn（x）=P0+P1X1+P2X2+…+PiXi+…+PnXn
可以抽象为一个由“系数-指数”对构成的线性表，且线性表中各元素的指数项是递增的：
P=（（P0,0）,（P1,1）,（P2,2）,…,（Pn,n））
（2）用一个单链表表示上述线性表，结点结构为：
typedefsturctnode
{floatcoef;/*系数域*/
intexp;/*指数域*/
structnode*next;/*指针域*/
}PloyNode;
package一元多项式的加法;
import一元多项式的加法.Elem.Node;
publicclassLinkedAdd{
publicNodeadd（Eleme1,Eleme2）{
Nodepre=e1.getNode（）;
Nodeqre=e2.getNode（）;
Nodep=pre.next;
Nodeq=qre.next;
Noderesult=p;
while（p!
=null&&q!
=null）{
if（p.exppre=p;
p=p.next;
}elseif（p.exp>q.exp）{
Nodetemp=q.next;
pre.next=q;
q.next=p;
q=temp;
}else{
p.coef=p.coef+q.coef;
if（p.coef==0）{
pre.next=p.next;
p=pre.next;
}else{
pre=p;
p=p.next;
}
qre.next=q.next;
q=qre.next;
}
}
if（q!
=null）{
pre.next=q;
}
returnresult;
}
publicstaticvoidmain（String[]args）{
Elemnode1=newElem（）;
node1.insert（7,0）;
node1.insert（12,3）;
node1.insert（2,8）;
node1.insert（5,12）;
Elemnode2=newElem（）;
node2.insert（4,1）;
node2.insert（6,3）;
node2.insert（2,8）;
node2.insert（5,20）;
node2.insert（7,28）;
LinkedAddl=newLinkedAdd（）;
Nodenode=l.add（node1,node2）;
while（node!
=null）{
System.out.println（"coef:
"+node.coef+"exp
升级会员 