第1章的绪论习题参考答案.doc

习题一参考答案一、概念题1. 试述下列各组概念： 数据、数据元素、数据项 数据结构、数据的逻辑结构、数据的存储结构 数据类型、数据操作 算法、算法的时间复杂度、算法的空间复杂度参考答案: 略2试述数据结构研究的3个方面的内容。参考答案: 数据结构研究的3个方面分别是数据的逻辑结构、数据的存储结构和数据的运算（操作）。3试述集合、线性结构、树型结构和图型结构四种常用数据结构的特性。参考答案: 集合结构：集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其它关系，它们之间的关系是松散性的。 线性结构：线性结构中数据元素之间存在“一对一”的关系。即若结构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且仅有一个前驱和一个后继。 树形结构：树形结构中数据元素之间存在“一对多”的关系。即若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可以有多个后继。 图形结构：图形结构中数据元素之间存在“多对多”的关系。即若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。4设有数据的逻辑结构的二元组定义形式为B=(D,R)，其中D=a1,a2,an，R=| i=1,2,，n-1，请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。参考答案: 顺序存储结构示意图如下： 链式存储结构示意图如下：5设一个数据结构的逻辑结构如图1.9所示，请写出它的二元组定义形式。图1.9 第5题的逻辑结构图参考答案: 它的二元组定义形式为B=（D，R），其中D=k1,k2,k3,k4,k5,k6,k7,k8,k9，R=, 。6设有函数f (n)=3n2-n+4，请证明f (n)=O(n2)。证明：因为存在c=6，N=1，对所有的nN ，0 3n2-n+46n2都是恒成立的，所以由书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)(9) n (10) log2n (11) 1/log2n (12)log2(log2n) (13)nlog2n (14) nlog2n参考答案: 按增长率递增的排列顺序是:1/log2n 2100log2(log2n)log2nn1/2n2/3nnlog2nn3/2nlog2n(4/3)n (3/2)n n!nn8试确定下列程序段中有标记符号“*”的语句行的语句频度（其中n为正整数)。 i=1; k=0; while ( i=n-1) k += 10 * i; /* i+;i+;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+jj ) j+ ; /* else i+ ; x=n; y=0; / n 是不小于1的常数while (x=(y+1)*(y+1) y+; /* x=91; y=100;while (y0 ) if (x100 ) x -= 10; y- -; /* else x+; a=1; m=1; while(a1时语句频度为n-1(3) n-1(4) n(n+1)/2(5) n(6) 取整(7) 1100(8) log3n二、算法设计题1有一个包括100 个数据元素的数组，每个数据元素的值都是实数，试编写一个求最大数据元素的值及其下标的算法，并分析算法的时间复杂度。参考答案:void max(double a) double max = a0;/ 初始化最大值为数组中的第一个元素 int index = 0; / for (int i = 0; i a.length; i+) if (max ai) max = ai;index = i; System.out.println(最大的实数为： + max + n其在数组中的下标为： + index); 此算法的时间复杂度为O(n) ，其中n为数组的长度。2试编写一个求一元多项式的值Pn(x0)的算法，并确定算法中每一条语句的执行次数和整个算法的时间复杂度。输入是ai(i=0,1,2,n-1)和x0，输出为Pn(x0)。参考答案:0 double getPolynomialResult(double a, double x) /a是多项式中系数数组1 double result = 0;2 double powX = 1;/ 临时变量，用于减少计算x幂的计算次数3 for (int i = 0; i a.length; i+) 4result += ai * powX;5 powX *= x;6 7 return result;8 语句17的执行次数分别是:1、1、a.length+1、a.length、a.length、1、1此算法的时间复杂度为O(a.length)，其中a.length也是多项式中的项数。三、上机实践题1编写一个实现将整型数组中的数据元素按值递增的顺序进行排序的Java程序。参考答案:package ch01Exercise;public class Exercise1_3_1 public int bubbleSort(int a) / a为待排序的整数数组int n = a.length;boolean isExchange = true; / 交换标志for (int i = 0; i n - 1&isExchange; i+) / 最多做n-1趟排序isExchange = false;for (int j = 0; j aj + 1) / 交换数据元素int temp = aj;aj = aj + 1;aj + 1 = temp;isExchange = true; / 发生了交换，故将交换标志置为真if (!isExchange)break; / 本趟排序未发生交换，提前终止算法return a;public static void main(String args) int values = 49, 38, 65, 97, 76, 13, 27, 49 ;System.out.println(排序前数组中数据元素：49 38 65 97 76 13 27 49);System.out.print(排序后数组中数据元素：);Exercise1_3_1 e = new Exercise1_3_1();values = e.bubbleSort(values);for (int i = 0; i values.length; i+)System.out.print(valuesi + );运行结果:2设计一个复数类，要求：(1) 在复数内部用双精度浮点数定义其实部和虚部。(2) 实现3个构造函数：第1个构造函数没有参数；第2个构造函数将双精度浮点数赋给复数的实部，虚部为0；第3个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。(3) 编写获取和修改复数的实部和虚部的成员函数。(4) 编写实现复数的减法、乘法运算的成员函数。设计一个测试主函数，使其实际运行验证类中各成员函数的正确性。参考答案:package ch01Exercise;/复数类class Complex private double real;/ 实部 private double imag; / 虚部 /无参构造函数 public Complex() this(0, 0); /带一个参数的构造函数 public Complex(double real) this(real, 0); /带两个参数的构造函数 public Complex(double real, double imag) this.real = real; this.imag = imag; public double getReal() return real; public void setReal(double real) this.real = real; public double getImag() return imag; public void setImag(double imag) this.imag = imag; public void add(Complex Z) if (Z != null) real += Z.getReal(); imag += Z.getImag(); /计算与另一复数的差,其中Z是减数 public void minus(Complex Z) if (Z != null) real -= Z.getReal(); imag -= Z.getImag(); / 计算与另一复数的乘积,其中 Z是乘数public void multiply(Complex Z) if (Z != null) double temp = (real * Z.getReal() - imag * Z.getImag(); imag = (real * Z.getImag() + imag * Z.getReal(); real = temp; / 测试类public class Exercise1_3_2 public static void main(String args) Complex c1 = new Complex(2, 3);System.out.println(修改前c1的实部为： + c1.getReal() + 虚部为： + c1.getImag();c1.setReal(1);c1.setImag(2); System.out.println(修改后c1的实部为： + c1.getReal() + 虚部为： + c1.getImag();Complex c2 = new Complex(4, 5);c1.add(c2);System.out.println(执行加法运算后c1的实部为： + c1.getReal() + 虚部为：+ c1.getImag();c1.minus(c2);System.out.println(执行减法运算后c1的实部为： + c1.getReal() + 虚部为：+ c1.getImag();c1.multiply(c2);System.out.println(执行乘法运算后c1的实部为： + c1.getReal() + 虚部为：+ c1.getImag();运行结果: