数据结构java语言描述课后答案.docx
《数据结构java语言描述课后答案.docx》由会员分享，可在线阅读，更多相关《数据结构java语言描述课后答案.docx（19页珍藏版）》请在冰点文库上搜索。
数据结构java语言描述课后答案
数据结构java语言描述课后答案
【篇一：
数据机构第一章——java语言描述第1章绪论习题参考答案】
概念题
1.试述下列各组概念：
⑴数据、数据元素、数据项
⑵数据结构、数据的逻辑结构、数据的存储结构
⑶数据类型、数据操作
⑷算法、算法的时间复杂度、算法的空间复杂度
参考答案:
略
2．试述数据结构研究的3个方面的内容。
参考答案:
数据结构研究的3个方面分别是数据的逻辑结构、数据的存储结构和数据的运算（操作）。
3．试述集合、线性结构、树型结构和图型结构四种常用数据结构的特性。
参考答案:
集合结构：
集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其它关系，它们之间的关系是松散性的。
线性结构：
线性结构中数据元素之间存在“一对一”的关系。
即若结构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且仅有一个前驱和一个后继。
树形结构：
树形结构中数据元素之间存在“一对多”的关系。
即若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可以有多个后继。
图形结构：
图形结构中数据元素之间存在“多对多”的关系。
即若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。
4．设有数据的逻辑结构的二元组定义形式为b=（d,r），其中
d={a1,a2,?
an}，r={ai,ai+1|i=1,2,?
，n-1}，请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。
参考答案:
顺序存储结构示意图如下：
012?
n-2n-1
链式存储结构示意图如下：
?
5．设一个数据结构的逻辑结构如图1.9所示，请写出它的二元组定义形式。
图1.9第5题的逻辑结构图
参考答案:
它的二元组定义形式为b=（d，r），其中d={k1,k2,k3,k4,k5,k6,k7,k8,k9}，
r=k1,k3,k1,k8,k2,k3k2,k4,k2,k5,k3,k9,k4,k6,k4,k7,k5,k6,k8,k9,k9,k7}。
6．设有函数f（n）=3n2-n+4，请证明f（n）=o（n2）。
书p16的定义可得f（n）=o（n2）。
7．请比较下列函数的增长率，并按增长率递增的顺序排列下列函数：
（1）2100
（2）（3/2）n（3）（4/3）n（4）nn（5）n2/3（6）n3/2（7）n!
（8）n
（9）n（10）log2n（11）1/log2n（12）log2（log2n）（13）nlog2n（14）nlog2n参考答案:
按增长率递增的排列顺序是:
1/log2n2100log2（log2n）log2nn1/2n2/3nnlog2nn3/2nlog2n（4/3）n（3/2）nn!
nn
8．试确定下列程序段中有标记符号“*”的语句行的语句频度（其中n为正整数）。
⑴i=1;k=0;
while（i=n-1）{
k+=10*i;//*
i++;
}
⑵i=1;k=0;
do{
k+=10*i;//*
i++;
}while（i=n-1）;
⑶i=1;k=0;
while（i=n-1）{
i++;
k+=10*i;//*
}
⑷k=0;
for（i=1;i=n;i++）{
for（j=1;j=i;j++）
k++;//*
}
⑸i=1;j=0;
while（i+j=n）{
if（ij）j++;//*
elsei++;
}
⑹x=n;y=0;//n是不小于1的常数
while（x=（y+1）*（y+1））{
y++;//*
}
⑺x=91;y=100;
while（y0）{
if（x100）{x-=10;y--;}//*
elsex++;
⑻a=1;m=1;
while（an）
{
m+=a;a*=3;//*
}
参考答案:
（7）1100
（8）log3n
二、算法设计题
1．有一个包括100个数据元素的数组，每个数据元素的值都是实数，试编写一个求最大数
据元素的值及其下标的算法，并分析算法的时间复杂度。
参考答案:
voidmax（double[]a）{
doublemax=a[0];//初始化最大值为数组中的第一个元素
intindex=0;//
for（inti=0;ia.length;i++）{
if（maxa[i]）{
max=a[i];
index=i;
}
}
system.out.println（最大的实数为：
+max+\n其在数组中的下标为：
+index）;}
此算法的时间复杂度为o（n），其中n为数组的长度。
2．试编写一个求一元多项式pn（x）?
?
axi
i?
0ni的值pn（x0）的算法，并确定算法中每一条语句
的执行次数和整个算法的时间复杂度。
输入是ai（i=0,1,2,?
n-1）和x0，输出为pn（x0）。
参考答案:
0doublegetpolynomialresult（double[]a,doublex）{//a是多项式中系数数组
1doubleresult=0;
2doublepowx=1;//临时变量，用于减少计算x幂的计算次数
3for（inti=0;ia.length;i++）{
4result+=a[i]*powx;
5powx*=x;
6}
7returnresult;
8}
语句1~7的执行次数分别是:
1、1、a.length+1、a.length、a.length、1、1
此算法的时间复杂度为o（a.length），其中a.length也是多项式中的项数。
三、上机实践题
1．编写一个实现将整型数组中的数据元素按值递增的顺序进行排序的java程序。
参考答案:
packagech01exercise;
publicclassexercise1_3_1{
publicint[]bubblesort（int[]a）{//a为待排序的整数数组
intn=a.length;
booleanisexchange=true;//交换标志
for（inti=0;in-1isexchange;i++）{//最多做n-1趟排序
isexchange=false;
for（intj=0;jn-i-1;j++）{//对当前无序区进行排序
if（a[j]a[j+1]）{//交换数据元素
inttemp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
isexchange=true;//发生了交换，故将交换标志置为真}
}
if（!
isexchange）
break;//本趟排序未发生交换，提前终止算法
}
returna;
}
publicstaticvoidmain（string[]args）{
int[]values={49,38,65,97,76,13,27,49};
system.out.println（排序前数组中数据元素：
4938659776132749）;system.out.print（排序后数组中数据元素：
）;
exercise1_3_1e=newexercise1_3_1（）;
values=e.bubblesort（values）;
for（inti=0;ivalues.length;i++）
system.out.print（values[i]+）;
}
}
运行结果
:
2．设计一个复数类，要求：
（1）在复数内部用双精度浮点数定义其实部和虚部。
给复数的实部，虚部为0；第3个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。
（3）编写获取和修改复数的实部和虚部的成员函数。
（4）编写实现复数的减法、乘法运算的成员函数。
设计一个测试主函数，使其实际运行验证类中各成员函数的正确性。
参考答案:
packagech01exercise;
//复数类
classcomplex{
【篇二：
《数据结构（java语言版）》试卷1】
考试科目：
《数据结构》考试形式：
闭卷适应班级：
软开1431-1439
a．2,3,4,1,5b．2,3,1,4,5c．5,4,1,3,2d．1,5,4,3,211、判断一个循环队列（m0为最大队列长度（以元素为单位），front和rear分别为队列的队头指针和队尾指针）为空队列的条件是（）。
a．front==rearb．front!
=rear
c．front==（rear+1）%m0d．front!
=（rear+1）%m0
一、单项选择（共20题，每题2分,共40分）12、判断一个循环队列（m0为最大队列长度（以元素为单位），front和rear分别为队列的队头指针和队尾指针）1、以下数据结构中哪一个是非线性结构？
（）为满队列的条件是（）。
a.队列b.栈c.二叉树d.线性表a．front==rearb．front!
=rearc．front==（rear+1）%m0d．front!
=（rear+1）%m02、（）不是算法的主要特性。
a．输入性b．输出性c．有穷性d．高效性13、串是一种特殊的线性表，其特殊性体现在（）。
a．可以顺序存储b．数据元素是一个字符3、（）不是线性表的存储结构。
c．可以链式存储d．数据元素可以是多个字符
a．叉链表b．单链表c．双向链表d．循环链表14、假设s=“abcaabcaaabca”，t=“bca”，s.indexof（t,3）（其中3为索引号，索引号从0开始编号）4、线性表是：
果是（）
a.一个有限序列，可以为空；b.一个有限序列，不能为空；a．1b．5c．10d．0c.一个无限序列，可以为空；d.一个无序序列，不能为空15、二叉树的数据结构描述了数据之间的（）关系。
5、用链表表示线性表的优点是（）。
a．链接关系b．层次关系
a.便于随机存取c．网状关系d．随机关系b.花费的存储空间较顺序存储少c.便于插入和删除16、（）遍历方法在遍历它的左子树和右子树后再遍历它自身。
d.数据元素的物理顺序与逻辑顺序相同a．先序遍历b.后序遍历c.中序遍历d.层次遍历6、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
17、在构造哈夫曼树的过程中说法正确的是（）。
a.单链表b.仅有头指针的单循环链表
c.双链表d.仅有尾指针的单循环链表
a.使权值越大的叶结点越远离根结点，而权值越小的叶结点越靠近根结点
b.使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点
7、栈中元素的进出原则是（）
c.最终是带权路径长度最大的二叉树
a.先进先出b.后进先出c.栈空则进d.栈满则出
d.构造的过程是一次到位
8、若已知一个栈的入栈序列是1，2，3，?
，n，其输出序列为p1，p2，p3，?
，pn，若p1=n，则pi为（）18
、55为最第一趟快速排序的基准值，执行一趟快速排序能够得到的序列是（a）。
a.[12，27，45，41]55[34，63，72]a．ib．n=ic．n-i+1d．不确定
b.[45，34，12，41]55[72，63，27]
c.[63，12，34，45，27]55[41，72]
9、若依次输入数据元素序列{a，b，c，d，e，f，g}进栈，出栈操作可以和入栈操作间隔进行，则下列哪个
d.[41，12，34，45，27]55[72，63]
元素序列可以由出栈序列得到？
（）
a．{c，d，b，e，g，a，f}b．{f，e，g，d，a，c，b}
19、对线性表进行二分查找时，要求线性表必须（）。
c．{e，f，d，g，b，c，a}d．{d，e，c，f，b，g，a}
a．以顺序方式存储
10、一个栈的入栈序列是1,2,3,4,5，则下列序列中不可能的出栈序列是（）
b．以链接方式存储
c．以链接方式存储，且结点按关键字有序排序
第1页共2页
的结
d．以顺序方式存储，且结点按关键字有序排序
20、在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值（）。
a．一定都是同义词b.一定都不是同义词Ｃ.不一定都是同义词d．都相同
二、判断题（共10题，每题2分,共20分，正确打√，错误的打╳）三、1-5√√╳╳√6-10╳√╳√╳
1、数据元素是组成数据的基本单位，数据项是组成数据元素的基本单位。
（）
2、数据的逻辑结构是从逻辑的角度来观察数据，分析数据，与数据的存储位置无关。
（）3、链式存储结构是把数据元素存放在地址连续的存储单元里，借助元素在存储器中的相对位置来表示数据元素之间逻辑关系。
（）4、单链接表可以按双向遍历线性表中的每一个数据元素。
（）5、链表中删除和插入操作比顺序表快，但是元素的访问速度比顺序表要慢。
（）6、栈的主要特点是“先进先出”，队列的主要特点是“后进先出”。
（）7、stringbuilder是非线程安全，stringbuffer是线程安全的。
（）
8、前序遍历是首先遍历根结点的左子树，再遍历根结点的右子树，最后访问根结点。
（）
9、插入排序的基本思想是：
每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。
（）10、二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。
（）三、简答题（共２题，每题10分，共20分）
1、设哈希表长m=14，哈希函数为h（k）=kmod11。
如果用二次探测再散列处理冲突，请将关键字为15、
38、49、61、84的记录填写在相应的存储单元中。
012345678910111213
初始关键字
先序遍历（abdgcef）、中序遍历（dgbaecf）、后序遍历（gdbefca）和层次遍历（abcdefg）。
四、编程题（共20分，第1和第2小题各8分，第3小题4分）给定一组数据：
1、编写冒泡排序算法publicint[]bubblesort（int[]data）,实现对该组数据的排序。
2、编写二分查找算法publicintbinsearch（int[]data,intkey），实现对关键字key的查找。
3、用给定的初始关键字编写测试程序，对两个算法进行测试。
2、请分别给出下图中先序遍历、中序遍历、后序遍历和层次遍历的结果。
第2页共2页
【篇三：
数据机构第四章——java语言描述第4章串与数组习题参考答案】
、选择题
1．下面关于串的叙述中，哪一个是不正确的？
（b）
a．串是字符的有限序列
b．空串是由空格构成的串
c．模式匹配是串的一种重要运算
d．串既可以采用顺序存储，也可以采用链式存储
2．串的长度是指（a）
a.串中包含的字符个数b.串中包含的不同字符个数
c.串中除空格以外的字符个数d.串中包含的不同字母个数
3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（c）
a．求子串b．联接c．模式匹配d．求串长
4．设主串的长度为n，模式串的长度为m，则串匹配的kmp算法时间复杂度是（c）。
5.串也是一种线性表，只不过（a）。
a.数据元素均为字符b.数据元素是子串
c.数据元素数据类型不受限制d.表长受到限制
6.设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主进行存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（b）。
a.13b.33c.18d.40
7.有一个二维数组a[1..6,0..7]，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（d）个字节。
a.48b.96c.252d.288
8.设有数组a[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址ba开始以列序为主序顺序存放，则数组元素a[5，8]的存储首地址为（b）。
a.ba+141b.ba+180c.ba+222d.ba+225
9.稀疏矩阵的三元组存储表示方法（b）
a.实现转置操作很简单，只需将每个三元组中行下标和列下标交换即可
b.矩阵的非零元素个数和位置在操作过程中变化不大时较有效
c.是一种链式存储方法
d.比十字链表更高效
10.用十字链表表示一个稀疏矩阵，每个非零元素一般用一个含有（a）域的结点表示。
a.5b.4c.3d.2
二、填空题
1.
2．串长度为0
3.
4.
5.模式串t=ababaab的next[]
nextval[]数组值为。
6.设数组a[1..5,1..6]的基地址为1000，每个元素占5个存储单元，若以行序为主序顺序
存储，则元素
a[5,5]
7．在稀疏矩阵的三元组顺序表存储结构中，除表示非零元的三元组表以外，还需要表示矩
阵的行数、列数和
的对称矩阵，如果以相同的元素只存储一次的原则进行压缩存储，则其元素压
9
10.
三、算法设计题
1．编写基于seqstring类的成员函数count（）,统计当前字符串中的单词个数。
参考答案:
publicintcount（）{
intwordcount=0;//单词个数
charcurrchar,prechar;
for（inti=1;ithis.length（）;i++）{
currchar=this.charat（i）;//当前字符
prechar=this.charat（i-1）;//前一个字符
if（（（int）（currchar）65||（int）（currchar）122
//当前字符不是字母
||（（int）（prechar）90（int）（prechar）97））（（（int）（prechar）=65（int）（prechar）=90）//当前字符的前一个字符是字母
||（（int）（prechar）=97（int）（prechar）=122）））{wordcount++;
}
}
returnwordcount;
}
2．编写基于seqstring类的成员函数replace（begin,s1,s2）。
要求在当前对象串中，从下
标begin开始，将所有的s1子串替换为s2串。
参考答案:
//beginint开始位置;s1string原始字符串;s2string目标字符串;
publicseqstringreplace（intbegin,seqstrings1,seqstrings2）{if（s1==null||s2==null）{
returnnull;
}
seqstringss=newseqstring（）;//产生空串
seqstringsource=this;
intindex=-1;
while（（index=source.indexof（s1,begin））!
=-1）{
ss.concat（source.substring（0,index））;//串连接
ss.concat（s2）;
source=（seqstring）source.substring（index+s1.length（））;
//取子串
}
ss.concat（source）;//串连接
returnss;
}
3．编写基于seqstring类的成员函数reverse（）。
要求将当前对象中的字符反序存放。
参考答案:
publicseqstringreverse（）{
for（inti=0,j=this.length（）-1;ij;i++,j--）{
chartemp=this.charat（i）;
setcharat（i,this.charat（j））;
setcharat（j,temp）;
}
returnthis;
}
4．编写基于seqstring类的成员函数deleteallchar（ch）。
要求从当前对象串中删除其值
等于ch的所有字符。
参考答案:
publicseqstringdeleteallchar（charch）{
seqstrings1=newseqstring（string.valueof（ch））;
if（s1==null）{
returnnull;
}
seqstringss=newseqstring（）;//产生空串
seqstringsource=this;//当前串赋值到sourse
intindex=-1;
while（（index=source.indexof（s1,0））!
=-1）{
ss.concat（source.substring（0,index））;//串连接source=（seqstring）source.substring（index+1）;//取子串}
ss.concat（source）;//串连接
returnss;
}
5．编写基于seqstring类的成员函数stringcount（str）。
要求统计子串str在当前对象串
中出现的次数，若不出现则返回0。
参考答案:
publicintstringcount（seqstringstr）{
seqstringsource=thi
升级会员 