数据结构(java语言版)-王学军主编-课后习题参考答案

第一章习题参考答案一、简答题1．【参考答案】：数据结构是计算机类专业的一门专业基础的课程，是学习操作系统、数据库原理等专业课的基础，所涉及的有数学范围的诸多知识；计算机硬件范围的编码理论、存取装置和存取方法等知识；软件范围的文件系统、数据的动态存储管理和信息管理等知识。所以说数据结构是介于数学、计算机硬件及软件三者之间的一门核心课程。2．【参考答案】：(1)学生管理系统中的学生信息顺序表、图书查询系统中的图书信息表、电话查询系统中的电话号码表中都表现了前后元素之间的线性关系，课本中【例1.2】也是线性结构。(2)计算机文件管理系统中目录的层次管理结构、家谱管理等都体现上一层次与下一层次元素之间的层次关系，即树形结构，课本中【例1.3】也是树形结构。(3)地图中城市之间的关系、同一地区不同城市之间的交通关系等都反映了不同元素之间复杂的网状结构，课本中【例1.4】也是网状结构。3.【参考答案】：数据元素（DataElement）是构成数据的基本单位。这些数据可由单个元素构成的，例如{1，4，7，100，……}中每个数字就是一个数据。另外有些数据是由一组元素构成的。数据项（DataItem）是数据结构中的最小单位。当数据元素由多个项构成时，其每个分项称为数据项，例如，{{1，100，’a’},{1,101,’b’,{3,102,’c’},……}中的每个元素都是有三个数据元素构成的。4．【参考答案】：不矛盾。算法的时间复杂度是指在计算机上运行该算法（或程序）所需要的时间。它与机器的性能、算法语言的选取、编译程序的效率、算法的选择等方面有关系。算法的空间复杂度是指程序从开始运行到结束运行所需的最大存储空间，其影响因素包括：输入数据所占空间；程序本身所占空间；辅助变量所占空间等。算法的时间复杂度和空间复杂度是反映算法优劣的两个方面，但是有时候会因为提高时间复杂度而降低空间复杂度，反之同理，但是这些并不说明它们之间是有矛盾的。5．【参考答案】：(1)学生管理系统中的学生信息顺序表是线性关系。每个学生的整体信息就是一个数据元素，体现每个学生具体信息的值为数据项，其前后之间的顺序关系就是线性关系的数据结构。(2)家谱管理系统中长辈和晚辈之间的关系就是一个树形层次结构，家谱中每个成员就是一个数据元素，其前后关系就是树形关系。(3)华北地区各城市之间构成了网状关系。每个城市就是一个数据元素，各城市之间的关系就是一个网状结构。6．【参考答案】：（1）数据类型(DataType)和数据结构之间有着密切的联系，在许多由高级语言编写的程序中，对于常量、变量或表达式都有一个所属的确定数据类型（即本身的数据特点）。（2）数据结构（DataStructure）是指具有某种联系的数据元素以及元素之间所构成的各种关系组成的集合。（3）逻辑结构（LogicalStructure）是指构成数据结构的数据元素相互之间本身具有的逻辑关系。（4）存储结构（或物理结构）是指构成数据结构的数据元素及其关系在计算机中的描述和表示。（5）线性结构的数据元素之间形成一对一的线性关系。（6）非线性结构包括树形结构、图形结构。7．【参考答案】：一个好的算法通常要达到以下的要求：首先，算法必须是正确的，即其执行结果应当满足预先规定的功能和性能要求；其次，一个可行的算法必须是可以被多个用户读懂的，应当思路清晰、层次分明、简单明了、易读易懂；再次，一个确定的算法每个步骤一定是确实可行的，不能产生二义性；最后，用户设计的算法一定是效率比较高的，对存储空间和时间效率的考虑一定要全面。8．【参考答案】：（1）时间复杂度：第1条语句定义并赋初值执行2次，第2条语句定义执行1次，第3条for循环语句执行2*11+2次，第4条循环体语句执行11次。空间复杂度：该题目在实现过程中使用了一个整型数组以及一个用于存放循环变量的整型变量。（2）时间复杂度：第1条语句定义并赋初值执行2次，第2条语句定义执行1次，第3条for循环语句执行2*8+2次，第4条for循环语句执行88次，第5、6条语句执行36次。空间复杂度：该题目三个整型变量。二、思考题1．【参考答案】：Java语言是面向对象的程序设计，本质是把数据和处理数据的过程当成一个整体——对象。对象=数据+方法（作用于这些数据上的操作）；描述数据结构的算法比较直观，用Java语言实现算法时，将数据成员和对成员函数操作的方法都封装在类中，表现形式和数据结构的抽象数据类型的定义形式一致，能够更深入的描述和刻画数据结构，因此Java语言更有利于实现数据结构中逻辑结构、存储结构以及算法的实现。面向过程的程序设计（如C语言），必须指定计算机执行的具体步骤，程序设计者不仅要考虑程序要“做什么”，还要解决“怎么做”的问题，根据程序要“做什么”的要求，写出一条条语句，安排好他们的执行顺序。这种对操作的描述即操作步骤，也就是算法。2．【参考答案】：数据结构（DataStructure）是指具有某种联系的数据元素以及元素之间所构成的各种关系组成的集合。包括两个方面：一方面是具有某种联系的数据元素；另一方面是数据元素之间具有的各种关系。数据元素不是孤立存在的，正因为在他们之间总存在某种相互关系，才构成了数据元素之间的各种关系，将这些关系称为结构。数据的结构可分为数据的逻辑结构和数据的物理结构。逻辑结构（LogicalStructure）是指构成数据结构的数据元素相互之间本身具有的逻辑关系。物理结构（或存储结构）是指构成数据结构的数据元素及其关系在计算机中的描述和表示。一种数据结构可对应一种或多种存储结构。例如，在“家谱关系”中，构成家谱中的每个成员A={a1,a2,a3,……}；而数据关系ai,aj,表明了ai与aj的辈分关系，表明了其逻辑结构，因此，在数据结构算法实现过程中，一定要即了解逻辑结构，同时还要考虑存储结构，二者缺一不可。3．【参考答案】：抽象数据类型（AbstractDataType，简称ADT）是对特定数学模型的数学描述，包括操作的数据，数据之间的关系，以及在该关系上可以实现的操作，即数据类型一般由元素、关系及操作三要素组成。抽象数据类型独立于各种操作的具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息隐藏。在Java中，可以用类的说明来表示ADT，用类的实现来实现ADT。抽象数据类型可描述如下：ADT抽象数据类型名{数据对象：（数据对象的定义）；数据关系：（数据关系的定义）；基本操作：（基本操作的定义）；};第二章习题参考答案一．简答题1．【参考答案】：面向对象程序设计三大基本特征是：封装、继承和多态。面向对象封装是把表示属性的数据和对数据的操作包装成一个对象类型，使得对数据的存取只能通过封装提供的接口进行。数据的封装是隐藏了数据的内部实现细节的结果，将数据抽象的外部接口与内部的实现细节清楚的分开。继承是类与类之间存在的一种关系，它使程序员可在已有类的基础上定义和实现新类。继承是构造可复用软件构件的有效机制。面向对象程序设计中的多态性是指不同的对象收到相同的消息时所产生多种不同的行为方式。多态性主要表现在对象引用的类型具有多种形态，通过对象引用方法也具有多种形态。2．【参考答案】：类是对象的模板，是对一组具有共同的属性特征和行为特征的对象的抽象。类和对象之间的关系是抽象和具体的关系。即对象的抽象是类，类的具体化就是对象。类也具有属性，它是对象状态的抽象，用数据结构来描述；类也具有方法，它是对象行为的抽象，用方法名和方法体来描述。类是定义相同类型对象的结构，是抽象数据类型的实现。对象是类的实例化，在类定义中指明了类包含对象的属性和方法。3．【参考答案】：一个子类只能继承其父类的可访问的成员，并且该子类没有覆盖或者说隐藏父类中的那些可访问成员。所以，一个类的成员就是指在这个类中所声明的属性和方法，再加上从其父类继承而来的属性和方法。也就是说，子类是不能继承父类的私有成员的。4．【参考答案】：构造方法是用在实例化对象的时候调用的，没有返回值，方法名必须与类名相同。构造方法可有可无,如果没有构造方法,JVM会调用默认的构造方法.方法分系统方法和用户自定义方法,方法名不能与类名相同，使用方法必须通过调用实现。也可以分为静态方法和非静态方法，静态方法可用类名直接调用，非静态方法要用对象调用，返回值可有可无，如果没有声明时要加void。5．【参考答案】：在Java中，除了可以使用抽象类来实现一定程度的抽象外，还可以定义一种特殊的“抽象类”——接口。接口是没有实现的方法和常量的集合。在接口中所有的方法都是抽象方法（只有方法定义，没有方法体）。在抽象类中，有些方法被实现，而有些方法只有方法的声明，没有方法的具体实现，而在接口中，所有的方法都没有被实现。和抽象类中的抽象方法不一样，这些没有被实现的方法不需要加上关键字abstract来将它们声明为抽象方法。6．【参考答案】：Java提供了对象的引用方式，实现数据的链式存储结构，这种方式避免直接使用“指针”带来的安全隐患，使Java语言可以实现面向对象的数据结构。举例参见2.5。二．选择题【1】B【2】B【3】C【4】A【5】B三．实验题1．【参考答案】：importjava.io.*;publicclassFactorial{publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderkeyin=newBufferedReader(newInputStreamReader(System.in));Stringst;intn;System.out.print(请输入n：);st=keyin.readLine();n=Integer.parseInt(st);System.out.println(n+的阶乘为：+fact(n));}staticintfact(intn){intresult;if(n==1)//规定1!等于1return1;result=fact(n-1)*n;//运算规则n!=(n-1)!*nreturnresult;}}2.【参考答案】：//提示：2N-2就是矩阵横纵坐标和的最大值publicclassMatrix{finalintN=4;intcount=1;int[][]matrix=newint[N][N];Matrix(){for(inti=0;i=2*N-2;i++){for(intj=0;j=i;j++){if(jN&&(i-j)N){if(i%2==1){//System.out.println((+j+,+(i-j)+)=+count);matrix[j][i-j]=count++;}else{//System.out.println((+(i-j)+,+j+)=+count);matrix[i-j][j]=count++;}}}}}publicvoidprintMatrix(){for(inti=0;iN;i++){for(intj=0;jN;j++){System.out.print(matrix[i][j]+);}System.out.println();}}publicstaticvoidmain(String[]args){Matrixm=newMatrix();m.printMatrix();}}四．思考题1.【参考提示】：结合数据结构是数据和数据元素之间的关系的集合和面向对象程序设计的封装特性去理解。2.【参考提示】：结合面向对象中类特性和数据结构的特性去理解。第三章习题参考答案一、简答题1．【参考答案】：（1）线性表是将多个具有相同类型的数据元素放在一起构成一组有限序列的结构。还可以理解为第一个元素无前驱，最后一个元素无后继，而其他元素都有惟一直接前驱和直接后继的表结构。（2）顺序表是指线性表在顺序存储形式下构成的表。线性表逻辑上相邻的数据元素（直接前驱和直接后继）在存储位置（或物理位置）上也相邻。（3）链表也是一种有