1、数据结构java语言王学军主编课后测验参考完整答案第一章习题参考答案一、简答题1【参考答案】 ：数据结构是计算机类专业的一门专业基础的课程，是学习操作系统、数据库原理等专业课的基础，所涉及的有数学范围的诸多知识；计算机硬件范围的编码理论、存取装置和存取方法等知识；软件范围的文件系统、数据的动态存储管理和信息管理等知识。所以说数据结构是介于数学、计算机硬件及软件三者之间的一门核心课程。2 【参考答案】 ：(1)学生管理系统中的学生信息顺序表、图书查询系统中的图书信息表、电话查询系统中的电话号码表中都表现了前后元素之间的线性关系，课本中【例1.2】也是线性结构。(2)计算机文件管理系统中目录的层次
2、管理结构、家谱管理等都体现上一层次与下一层次元素之间的层次关系，即树形结构，课本中【例1.3】也是树形结构。(3)地图中城市之间的关系、同一地区不同城市之间的交通关系等都反映了不同元素之间复杂的网状结构，课本中【例1.4】也是网状结构。3. 【参考答案】 ： 数据元素（Data Element）是构成数据的基本单位。这些数据可由单个元素构成的，例如1，4，7，100， 中每个数字就是一个数据。另外有些数据是由一组元素构成的。数据项（Data Item）是数据结构中的最小单位。当数据元素由多个项构成时，其每个分项称为数据项，例如，1，100，a,1,101,b,3,102,c ,中的每个元素都是
3、有三个数据元素构成的。4 【参考答案】 ：不矛盾。算法的时间复杂度是指在计算机上运行该算法（或程序）所需要的时间。它与机器的性能、算法语言的选取、编译程序的效率、算法的选择等方面有关系。算法的空间复杂度是指程序从开始运行到结束运行所需的最大存储空间，其影响因素包括：输入数据所占空间；程序本身所占空间；辅助变量所占空间等。算法的时间复杂度和空间复杂度是反映算法优劣的两个方面，但是有时候会因为提高时间复杂度而降低空间复杂度，反之同理，但是这些并不说明它们之间是有矛盾的。5【参考答案】 ：(1)学生管理系统中的学生信息顺序表是线性关系。每个学生的整体信息就是一个数据元素，体现每个学生具体信息的值为数
4、据项，其前后之间的顺序关系就是线性关系的数据结构。(2)家谱管理系统中长辈和晚辈之间的关系就是一个树形层次结构，家谱中每个成员就是一个数据元素，其前后关系就是树形关系。(3)华北地区各城市之间构成了网状关系。每个城市就是一个数据元素，各城市之间的关系就是一个网状结构。6【参考答案】 ：（1）数据类型(Data Type)和数据结构之间有着密切的联系，在许多由高级语言编写的程序中，对于常量、变量或表达式都有一个所属的确定数据类型（即本身的数据特点）。（2）数据结构（Data Structure）是指具有某种联系的数据元素以及元素之间所构成的各种关系组成的集合。（3）逻辑结构（Logical St
5、ructure）是指构成数据结构的数据元素相互之间本身具有的逻辑关系。（4）存储结构（或物理结构）是指构成数据结构的数据元素及其关系在计算机中的描述和表示。（5）线性结构的数据元素之间形成一对一的线性关系。（6）非线性结构包括树形结构、图形结构。7【参考答案】 ：一个好的算法通常要达到以下的要求：首先，算法必须是正确的，即其执行结果应当满足预先规定的功能和性能要求；其次，一个可行的算法必须是可以被多个用户读懂的，应当思路清晰、层次分明、简单明了、易读易懂；再次，一个确定的算法每个步骤一定是确实可行的，不能产生二义性；最后，用户设计的算法一定是效率比较高的，对存储空间和时间效率的考虑一定要全面。
6、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语言是面向对象的程序设计，本质是把数据和处理数据的过程当成一个整体对象。对象=数据+方法（作用于这些数据上的操作）；描
7、述数据结构的算法比较直观，用Java语言实现算法时，将数据成员和对成员函数操作的方法都封装在类中，表现形式和数据结构的抽象数据类型的定义形式一致，能够更深入的描述和刻画数据结构，因此Java语言更有利于实现数据结构中逻辑结构、存储结构以及算法的实现。面向过程的程序设计（如C语言），必须指定计算机执行的具体步骤，程序设计者不仅要考虑程序要“做什么”，还要解决“怎么做”的问题，根据程序要“做什么”的要求，写出一条条语句，安排好他们的执行顺序。这种对操作的描述即操作步骤，也就是算法。2【参考答案】 ：数据结构（Data Structure）是指具有某种联系的数据元素以及元素之间所构成的各种关系组成的
8、集合。包括两个方面：一方面是具有某种联系的数据元素；另一方面是数据元素之间具有的各种关系。数据元素不是孤立存在的，正因为在他们之间总存在某种相互关系，才构成了数据元素之间的各种关系，将这些关系称为结构。数据的结构可分为数据的逻辑结构和数据的物理结构。逻辑结构（Logical Structure）是指构成数据结构的数据元素相互之间本身具有的逻辑关系。物理结构（或存储结构）是指构成数据结构的数据元素及其关系在计算机中的描述和表示。一种数据结构可对应一种或多种存储结构。例如，在“家谱关系”中，构成家谱中的每个成员A=a1,a2,a3,；而数据关系表明了ai与aj的辈分关系，表明了其逻辑结构，因此，在
9、数据结构算法实现过程中，一定要即了解逻辑结构，同时还要考虑存储结构，二者缺一不可。3【参考答案】 ：抽象数据类型（Abstract Data Type，简称ADT）是对特定数学模型的数学描述，包括操作的数据，数据之间的关系，以及在该关系上可以实现的操作，即数据类型一般由元素、关系及操作三要素组成。抽象数据类型独立于各种操作的具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息隐藏。在Java中，可以用类的说明来表示ADT，用类的实现来实现ADT。抽象数据类型可描述如下：ADT 抽象数据类型名 数据对象：（数据对象的定义）；数据
10、关系：（数据关系的定义）；基本操作：（基本操作的定义）；;第二章习题参考答案一简答题1【参考答案】：面向对象程序设计三大基本特征是：封装、继承和多态。面向对象封装是把表示属性的数据和对数据的操作包装成一个对象类型，使得对数据的存取只能通过封装提供的接口进行。数据的封装是隐藏了数据的内部实现细节的结果，将数据抽象的外部接口与内部的实现细节清楚的分开。继承是类与类之间存在的一种关系，它使程序员可在已有类的基础上定义和实现新类。继承是构造可复用软件构件的有效机制。面向对象程序设计中的多态性是指不同的对象收到相同的消息时所产生多种不同的行为方式。多态性主要表现在对象引用的类型具有多种形态，通过对象引用
11、方法也具有多种形态。2【参考答案】：类是对象的模板，是对一组具有共同的属性特征和行为特征的对象的抽象。类和对象之间的关系是抽象和具体的关系。即对象的抽象是类，类的具体化就是对象。类也具有属性，它是对象状态的抽象，用数据结构来描述；类也具有方法，它是对象行为的抽象，用方法名和方法体来描述。类是定义相同类型对象的结构，是抽象数据类型的实现。对象是类的实例化，在类定义中指明了类包含对象的属性和方法。3【参考答案】：一个子类只能继承其父类的可访问的成员，并且该子类没有覆盖或者说隐藏父类中的那些可访问成员。所以，一个类的成员就是指在这个类中所声明的属性和方法，再加上从其父类继承而来的属性和方法。也就是说
12、，子类是不能继承父类的私有成员的。4【参考答案】：构造方法是用在实例化对象的时候调用的 ，没有返回值 ，方法名必须与类名相同。构造方法可有可无,如果没有构造方法,JVM会调用默认的构造方法. 方法分系统方法和用户自定义方法,方法名不能与类名相同，使用方法必须通过调用实现。也可以分为静态方法和非静态方法 ，静态方法可用类名直接调用，非静态方法要用对象调用 ，返回值可有可无，如果没有声明时要加 void 。5【参考答案】：在Java中，除了可以使用抽象类来实现一定程度的抽象外，还可以定义一种特殊的“抽象类”接口。接口是没有实现的方法和常量的集合。在接口中所有的方法都是抽象方法（只有方法定义，没有方
13、法体）。在抽象类中，有些方法被实现，而有些方法只有方法的声明，没有方法的具体实现，而在接口中，所有的方法都没有被实现。和抽象类中的抽象方法不一样，这些没有被实现的方法不需要加上关键字abstract来将它们声明为抽象方法。6【参考答案】：Java提供了对象的引用方式，实现数据的链式存储结构，这种方式避免直接使用“指针”带来的安全隐患，使Java语言可以实现面向对象的数据结构。举例参见2.5。二选择题【1】B 【2】B 【3】C 【4】A 【5】B三实验题1【参考答案】：import java.io.*;public class Factorial public static void main
14、(String args)throws IOExceptionBufferedReader keyin=new BufferedReader(new InputStreamReader(System.in); String st; int n; System.out.print(请输入n：); st=keyin.readLine(); n=Integer.parseInt(st); System.out.println(n+的阶乘为：+fact(n); static int fact(int n) int result; if(n=1) /规定1!等于1 return 1; result=fa
15、ct(n-1)*n; /运算规则n!=(n-1)!*n return result; 2.【参考答案】：/提示：2N-2就是矩阵横纵坐标和的最大值public class Matrix final int N = 4; int count = 1; int matrix = new intNN; Matrix() for(int i = 0; i = 2*N - 2;i+) for(int j = 0; j = i; j+) if(j N & (i-j) N) if(i%2 = 1) /System.out.println(+j + , + (i-j)+)= + count); matrixj
16、i-j = count+; else /System.out.println(+(i-j) + , + j+)= + count); matrixi-jj = count+; public void printMatrix() for(int i = 0; i N; i+) for(int j = 0; j N; j+) System.out.print(matrixij + ); System.out.println(); public static void main(String args) Matrix m = new Matrix(); m.printMatrix(); 四思考题1.
17、【参考提示】：结合数据结构是数据和数据元素之间的关系的集合和面向对象程序设计的封装特性去理解。2.【参考提示】：结合面向对象中类特性和数据结构的特性去理解。第三章习题参考答案一、简答题1【参考答案】 ：（1）线性表是将多个具有相同类型的数据元素放在一起构成一组有限序列的结构。还可以理解为第一个元素无前驱，最后一个元素无后继，而其他元素都有惟一直接前驱和直接后继的表结构。（2）顺序表是指线性表在顺序存储形式下构成的表。线性表逻辑上相邻的数据元素（直接前驱和直接后继）在存储位置（或物理位置）上也相邻。 （3）链表也是一种有顺序的表，其内容可以存储在一组任意的存储单元中，所谓任意的存储单元，即这组存
18、储单元可以连续的，也可以不连续的，这就需要在存储元素本身信息的同时，还要存储下一个元素的位置，由此构成一个链状结构，称其为链表。（4）线性表的逻辑结构，即相临元素之间所满足的前驱和后继的逻辑关系。（5）一种逻辑结构可对应多种存储结构，而每种存储又有自己的存储特点和操作方式。2【参考答案】 ：顺序表的基本操作包括：建立、插入、删除、查找等（下面以插入和删除过程为例，讲解实现过程）。插入操作具体过程为：首先确定插入位置 i ，按照anai 的顺序由后至前依次将各元素向后移动，为新元素让出位置，将新元素 x 插入已经让出的第i 个位置，结束插入操作。在规定位置删除某元素，删除操作的具体过程为：首先确
19、定删除位置 i ，按照ai+1an 的顺序依次将各元素向前移动，将元素 ai 删除，结束删除操作。 3【参考答案】 ：语法错误：node * L 改为 node L其功能：在线性表中查找与给定值x相等的数据元素4【参考答案】 ： public int deleteAll(int T)/顺序表删除所有值为T的节点 int data = L.data; int ilen = data.length; int k = 0; for(int i = 0; i ilen; i +) if(T=datai) for(int j = i; j ilen-1; j +) L.dataj = L.dataj+1
20、; ilen-; i-; k +; return k; public int deleteAll(int T)/链式删除 int count = 0; while(root!=null) if(root.getData()=T) root = root.getNext(); else break; LinkNode tmp = root.getNext(); LinkNode tmp1 = root; while(tmp!=null) if(tmp.getData()=T) tmp = tmp.getNext(); count +; else tmp1.setNext(tmp); tmp1 =
21、 tmp1.getNext(); tmp = tmp.getNext(); return count; 5【参考答案】 ： 对链表操作时，操作顺序对操作结果有影响。因为链表有两个区域，数据域、指针域，指针域指向下一个元素的地址或位置，若操作顺序不正确，可能使链表断裂。如，进行链表插入操作时，操作顺序是绝对不能调换的。二、简答题1【参考答案】 ： public MultiItem add(MultiItem m) MultiItem rm = new MultiItem(); SingleItem sroot = null; SingleItem sr = null; SingleItem si
22、1 = this.getFirst(); SingleItem si2 = m.getFirst(); int i = 0; while(si1!=null) if(i = 0) sroot = new SingleItem(si1.getZhishu(),si1.getXishu()+si2.getXishu(); sr = sroot; else SingleItem si = new SingleItem(si1.getZhishu(),si1.getXishu()+si2.getXishu(); sr.setNext(si); sr = sr.getNext(); si1 = si1.
23、getNext(); si2 = si2.getNext(); i+; rm.setFirst(sroot); return rm; 2【参考答案】 ：class Node int data; int length; public Node() public void setLength(int data) this.length=data.length; public int getLength() return length; public static void set(int data,int k) int sum=0; for(int i=0;idata.length;i+) if(
24、datai=k) sum+; System.out.println(k+在该数组中出现的次数为：+sum); public class D public static void main(String args) Node L=new Node(); int data=26,35,45,57,3,4,5,26,89,26; L.set(data,26); 3 【参考答案】 ：public class H public static int sort(int a) int b; int ilen = a.length; int k = 0; if(ilen%2=0) b = new intile
25、n/2; else b = new intilen/2+1; for (int i = 0; i b.length; i+) bi = ak; k = k+2; return b; public static void main(String args) int a = 12, 23, 34, 45, 56, 67 ; int n = a.length; System.out.println(数组a的数为:); for (int i = 0; i a.length; i+) System.out.print(ai + ,); System.out.println(); int b = sort
26、(a); System.out.println(数组b的数为:); for (int i = 0; i b.length; i+) System.out.print(bi + ,); 4【参考答案】 ：略三、思考题1【参考答案】 ：线性表的顺序存储结构实现比较简单，容易实现；在算法实现过程中要移动大量元素，同时在存储过程中，对于数据长度控制不是很容易。链式存储结构节省存储空间，但是实现算法中不需要大量移动元素，但是算法实现不是很容易。2【参考答案】 ：对双向链表、循环链表以及单链表存储结构都是属于链表的特点，即由数据域和指针区域构成，操作时都需要使用指针去定位相邻结点的位置，在进行插入、删除等
27、操作时都需要进行链表的连接和删除操作，需要改变指针的位置以达到操作的目的；其不同点为单链表从头指针或者从某个固定位置开始，按顺序向后移动，双向链表可以从某个位置开始向两个方向进行操作，循环链表从某个位置开始，可以查找到该链表当中的任何结点。3【参考答案】 ：链表的头指针是一个和结点指针域相同类型的指针，它指向链表的头，头结点和其他结点的结构一样，它也指示链表开始的位置，上面的设置都为了更方便的对链表进行操作。4【参考答案】 ：普通的线性表可以在任何位置进行操作，但是类似停车场、排队等操作都是限制在一端进行操作的特殊的线性表，该内容将在下一章讲到，通过这些例子使学生思考，并引入下一章的内容。第四
28、章习题参考答案一、简答题1. 【参考答案】 ：栈是满足“LIFO后进先出”的特点，即只在线性表的一端进行插入、删除等操作的顺序表。队列是满足“FIFO后进先出”的特点，即可在线性表的一端进行插入、另一端进行删除操作的线性表。2【参考答案】 ：顺序栈的结构和高级语言中的数组一样，在存储结构方面都可用一段连续的空间存储栈中的各个元素。但是在操作时，数据可以对每个元素进行操作，而顺序栈只能在固定的栈顶元素进行操作。3【参考答案】 ：栈的两种存储结构分别为顺序栈和链栈。其应用如下:表达式求解、递归问题求解过程等。4【参考答案】 ：当top达到数组的最大值an时，表示栈满状态，此时，只能进行出栈操作，而
29、不能进行入栈操作。5【参考答案】 ：4辆车时，结果：001，002，003，004 001，004，003，002 001，002，004，003 001，003，002，004 001，003，004，002 002，001，003，004 002，001，004，003 002，003，004，001 002，003，001，004 002，004，003，001 003，002，001，004 003，004，002，001 003，002，004，001 004，003，002，0013辆车时，结果：001，002，003 001，003，002 002，001，003 002，003，001 003，002，0016【参考答案】 ：队列的两种存储结构分别为
