(完整版)第1章的绪论习题参考答案.pdf

《(完整版)第1章的绪论习题参考答案.pdf》由会员分享，可在线阅读，更多相关《(完整版)第1章的绪论习题参考答案.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题一参考答案 一、概念题 1.试述下列各组概念：数据、数据元素、数据项 数据结构、数据的逻辑结构、数据的存储结构 数据类型、数据操作 算法、算法的时间复杂度、算法的空间复杂度 参考答案:略 2试述数据结构研究的 3 个方面的内容。参考答案:数据结构研究的 3 个方面分别是数据的逻辑结构、数据的存储结构和数据的运算（操作）。3试述集合、线性结构、树型结构和图型结构四种常用数据结构的特性。参考答案:集合结构：集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其它关系，它们之间的关系是松散性的。线性结构：线性结构中数据元素之间存在“一对一”的关系。即若结构非空，则它有且仅有一个开始结

2、点和终端结点，开始结点没有前趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且仅有一个前驱和一个后继。树形结构：树形结构中数据元素之间存在“一对多”的关系。即若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可以有多个后继。图形结构：图形结构中数据元素之间存在“多对多”的关系。即若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。4设有数据的逻辑结构的二元组定义形式为 B=(D,R)，其中 D=a1,a2,an，R=|i=1,2,，n-1，请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。参考答案:顺序存储结构示意图如下：a1a

3、2a3anan-10 1 2 n-2 n-1 链式存储结构示意图如下：a1a2a3an 5设一个数据结构的逻辑结构如图 1.9 所示，请写出它的二元组定义形式。K2 K1 K4 K5 K3 K8 K6 K7 K9 图 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请比较下列函数的增长率

4、，并按增长率递增的顺序排列下列函数：(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/log2n 2100 log2(log2n)log2nn1/2 n2/3 n nlog2n n3/2 nlog2n(4/3)n (3/2)n n!nn 8试确定下列程序段中有标记符号“*”的语句行的语句频度（其中 n 为正整数)。i=1;k=0;while(i=n-1)k+=1

5、0*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、(6)n取整(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试编写一

7、个求一元多项式niiinxaxP0)(的值 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+)4 result+=ai*powX;5 powX*=x;6 7 return result;8 语句 17 的执

8、行次数分别是: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&isExcha

9、nge;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)

10、;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)编写获取和修改复数的实部和虚

11、部的成员函数。(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=

12、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(Compl

13、ex 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 Compl

14、ex(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();运行结果: