数据结构java语言描述课后答案

数据结构java语言描述课后答案【篇一：数据机构第一章一一java语言描述第1章绪论习题参考答案】概念题试述下列各组概念：⑴数据、数据兀素、数据项⑵数据结构、数据的逻辑结构、数据的存储结构⑶数据类型、数据操作⑷算法、算法的时间复杂度、算法的空间复杂度参考答案：略试述数据结构研究的3个方面的内容。参考答案：数据结构研究的3个方面分别是数据的逻辑结构、数据的存储结构和数据的运算(操作)。3.试述集合、线性结构、树型结构和图型结构四种常用数据结构的特性。参考答案：集合结构：集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其它关系，它们之间的关系是松散性的。线性结构：线性结构中数据元素之间存在“一对一”的关系。即若结构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且仅有一个前驱和一个后继。树形结构：树形结构中数据元素之间存在“一对多”的关系。即若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可以有多个后继。图形结构：图形结构中数据元素之间存在“多对多”的关系。即若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。4.设有数据的逻辑结构的二元组定义形式为b=(d,r)，其中d={a1,a2,?,an}，r={ai,ai+1|i=1,2,?，n-1}，请画由此逻辑结构对应的顺序存储结构和链式存储结构的示意图。参考答案：顺序存储结构示意图如下：012?n-2n-1链式存储结构示意图如下：w!==5•设一个数据结构的逻辑结构如图1.9所示，请写出它的二元组w!==图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⑼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!nn8.试确定下列程序段中有标记符号“*的语句行的语句频度(其中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;//*}参考答案：1100log3n二、算法设计题1.有一个包括100个数据元素的数组，每个数据元素的值都是实|=>最|=>最据元素的值及其下标的算法，并分析算法的时间复杂度。参考答案：voidmax(double[]a){doublemax=a[0];//初始化最大值为数组中的第一个元素intindex=0;//for(inti=0;ia.length;i++){if(maxa[i]){max=a[i];index=i;}}=J

最system.out.println(最大的实数为：+max+\n=J

最为：+index);}此算法的时间复杂度为o(n)，其中n为数组的长度。2.试编写一个求一元多项式pn(x)??axii?0ni的值pn(x0)的算法，并确定算法中每一条语句的执行次数和整个算法的时间复杂度。输入是ai(i=0J1,2,?,n-1)和x0，输出为pn(x0)。参考答案：0doublegetpolynomialresult(double[]a,doublex)(//a是多项式中系数数组doubleresult=0;doublepowx=1;//临时变量，用于减少计算x幂的计算次数for(inti=0;ia.length;i++){4result+=a[i]*powx;5powx*=x;}returnresult;8}语句1~7的执行次数分别是:1、1、a.length+1、a.length、length、1、1此算法的时间复杂度为o(a.length)，其中a.length也是多项式中的项数。三、上机实践题1.编写一个实现将整型数组中的数据元素按值递增的顺序进行排序的java程序。参考答案:packagech01exercise;publicclassexercise1_3_1{publicint[]bubblesort(int[]a){//a为待排序的整数数组intn=a.length;booleanisexchange=true;//交换标志■=j最for(inti=0;in-1isexchange;i++){//最多做n-1■=j最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个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。编写获取和修改复数的实部和虚部的成员函数。编写实现复数的减法、乘法运算的成员函数。设计一个测试主函数，使其实际运行验证类中各成员函数的正确性。参考答案：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!=rearc.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、（）不是算法的主要特性。金・输入性》输出性c・有穷性d.高效性13、串是一种特殊的线性表，其特殊性体现在（）。a・可以顺序存储b,数据元素是一个字符3、（）不是线性表的存储结构。c,可以链式存储d・数据元素可以是多个字符a・叉链表b.单链表c,双向链表d.循环链表14、假设s="abcaabcaaabca”，t="bca”，s.indexof（t,3）（其中3为索引号，索引号从0开始编号）4、线性表是：果是（）一个有限序列，可以为空；b.一个有限序列，不能为空；a.15c.10d.0c.一个无限序列，可以为空；d.一个无序序列，不能为空15、二叉树的数据结构描述了数据之间的（）关系。5、用链表表示线性表的优点是（）。a・链接关系b.层次关系便于随机存取c.网状关系d・随机关系b・花费的存储空间较顺序存储少c,便于插入和删除16、（）遍历方法在遍历它的左子树和右子树后再遍历它自身。d,数据元素的物理顺序与逻辑顺序相同先序遍历b.后序遍历c.中序遍历d.层次遍历6、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。17、在构造哈夫曼树的过程中说法正确的是（）。a.单链表b.仅有头指针的单循环链表c.双链表d.仅有尾指针的单循环链表使权值越大的叶结点越远离根结点，而权值越小的叶结点越靠近根结点使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点7、栈中元素的进出原则是（）=j最终是带权路径长度最大的二叉树=ja.先进先出b.后进先出c.栈空则进d.栈满则出构造的过程是一次到位8、若已知一个栈的入栈序列是1,2,3,?,n,其输出序列为pl,p2,p3,?,pn,若p1=n，则pi为（）18■=j最、55为最第一趟快速排序的基准值，执行一趟快速排序能够得到的序列是（a■=j最[12,27,45,41]55[34,63,72]a.ib.n=ic.n-i+1d.不确定[45,34,12,41]55[72,63,27][63,12,34,45,27]55[41,72]9、若依次输入数据元素序列{a,b,c,d,e,f,g}进栈，出栈操作可以和入栈操作间隔进行，则下列哪个[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,345,则下列序列中不可能的出栈序列是（）b・以链接方式存储以链接方式存储，且结点按关键字有序排序第1页共2页的结d・以顺序方式存储，且结点按关键字有序排序20、在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值（）。a.一定都是同义词b.一定都不是同义词C.不一定都是同义词都相同二、 判断题（共10题，每题2分,共20分，正确打《错误的打乂）三、 1-5WXXW-10X炽炽1、 数据元素是组成数据的基本单位，数据项是组成数据元素的基本单位。（）2、 数据的逻辑结构是从逻辑的角度来观察数据，分析数据，与数据的存储位置无关。（）3、链式存储结构是把数据元素存放在地址连续的存储单元里，借助元素在存储器中的相对位置来表示数据元

素之间逻辑关系。（）4、单链接表可以按双向遍历线性表中的每一个数据元素。（）5、链表中删除和插入操作比顺序表快，但是出”，队列的主要特点是“后进先出”。（）7、stringbuilder是非线程安全，stringbuffer是线程安全的。（）元素的访问速度比顺序表要慢。（）元素的访问速度比顺序表要慢。（）6、栈的主要特点是“先进先8、前序遍历是首先遍历根结点的左子树，再遍历根结点的右子树，最后访问根结点。（）9、插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。（）10、二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。（）三、简答题（共2题，每题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,串是字符的有限序列空串是由空格构成的串c・模式匹配是串的一种重要运算d串既可以采用顺序存储，也可以采用链式存储串的长度是指（a）a.串中包含的字符个数b.串中包含的不同字符个数串中除空格以外的字符个数d.串中包含的不同字母个数设有两个串p和q,其中q是p的子串，求q在p中首次出现的位置的算法称为（c）a・求子串6联接^模式匹配d・求串长设主串的长度为n，模式串的长度为m，则串匹配的kmp算法时间复杂度是（c）。串也是一种线性表，只不过（a）。a.数据元素均为字符b.数据元素是子串c.数据元素数据类型不受限制d.表长受到限制设有一个10阶的对称矩阵2，采用压缩存储方式，以行序为主进行存储，all为第一元素，其存储地址为1,每个元素占一个地址空间，则a85的地址为（b）。a.13b.33c.18d.40有一个二维数组a[1..6,0..7]，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（d）个字节。a.48b.96c.252d.288设有数组a[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址ba开始以列序为主序顺序存放，则数组元素a[5,8]的存储首地址为（b）。a.ba+141b.ba+180c.ba+222d.ba+225稀疏矩阵的三元组存储表示方法（b）实现转置操作很简单，只需将每个三元组中行下标和列下标交换即可矩阵的非零元素个数和位置在操作过程中变化不大时较有效是一种链式存储方法比十字链表更高效用十字链表表示一个稀疏矩阵，每个非零元素一般用一个含有（a）域的结点表示。a.5b.4c.3d.2二、填空题1.2.串长度为03.4.模式串t=ababaab的next[]nextval[]数组值为。设数组a[1・・5,1・・6]的基地址为1000，每个元素占5个存储单元，若以行序为主序顺序存储，则元素a[5,5]7.在稀疏矩阵的三元组顺序表存储结构中，除表示非零元的三元组表以外，还需要表示矩阵的行数、列数和的对称矩阵，如果以相同的元素只存储一次的原则进行压缩存储，则其元素压910.三、算法设计题编写基于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;}编写基于seqstring类的成员函数replace(begin,s1,s2)。要求在当前对象串中，从下标begin开始，将所有的si子串替换为s2串。参考答案：//beginint开始位置;s1string原始字符串；s2string目标字符串；publicseqstringreplace(intbegin,seqstringsi,seqstrings2){if(si==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;}编写基于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;}编写基于seqstring类的成员函数deleteallchar(ch)。要求从当前对象串中删除其值等于ch的所有字符。参考答案：publicseqstringdeleteallchar(charch){seqstrings1=newseqstring(string.valueof(ch));if(s1==null){returnnull;}seqstringss=newseqstring();〃产生空串seqstringsource=this;//当前串赋值到sourseintindex=-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=this.curstr;intcount=0,begin=0;intindex;while((index=source.indexof(str,begin))!=-1)(count++;begin=index+str.length();}returncount;}6.鞍点是指矩阵中的元素aij是第i行中值最小的元素，同时又是第j列中值最大的元素。试设计一个算法求矩阵a的所有鞍点。参考答案：//存放矩阵中鞍点的类classresult(triplenodedata[];//三元组表，存放鞍点的行、列、值intnums;//鞍点个数publicresult(intmaxsize){〃构造方法data=newtriplenode[maxsize];〃为顺序表分配maxsize个存储单元for(inti=0;idata.length;i++){data[i]=newtriplenode();}nums=0;}}//返回矩阵中的所有鞍点publicresultallsaddlepoint(int[][]ar)(inti,j,flag,m,n;resultre=newresult(ar.length);for(i=0;iar.length;i++)(m=i;n=0;flag=1;//假设当前结点是鞍点for(j=0;jar[i].length;j++)(if(ar[i][j]ar[m][n])(n=j;}}for(j=0;jar.length;j++)(if(ar[j][n]ar[m][n])(flag=0;//不是鞍点}}i