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

习题一参考答案一、概念题1.试述下列各组概念：⑴数据、数据元素、数据项⑵数据结构、数据的逻辑结构、数据的存储结构⑶数据类型、数据操作⑷算法、算法的时间复杂度、算法的空间复杂度参考答案:略2．试述数据结构研究的3个方面的内容。参考答案:数据结构研究的3个方面分别是数据的逻辑结构、数据的存储结构和数据的运算（操作）。3．试述集合、线性结构、树型结构和图型结构四种常用数据结构的特性。参考答案:集合结构：集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其它关系，它们之间的关系是松散性的。线性结构：线性结构中数据元素之间存在“一对一”的关系。即若结构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且仅有一个前驱和一个后继。树形结构：树形结构中数据元素之间存在“一对多”的关系。即若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可以有多个后继。图形结构：图形结构中数据元素之间存在“多对多”的关系。即若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。4．设有数据的逻辑结构的二元组定义形式为B=(D,R)，其中D={a1,a2,…,an}，R={ai,ai+1|i=1,2,…，n-1}，请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。参考答案:顺序存储结构示意图如下：a1a2a3anan-1012…n-2n-1…链式存储结构示意图如下：a1a2a3an^…5．设一个数据结构的逻辑结构如图1.9所示，请写出它的二元组定义形式。K2K1K4K5K3K8K6K7K9图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)。证明：因为存在c=6，N=1，对所有的n≥N，0≤3n2-n+4≤6×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(9)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++;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;//*}参考答案:指定语句行的语句频度分别为：（1）n-1(2)当n≤1时语句频yac为1，当n1时语句频度为n-1(3)n-1(4)n(n+1)/2(5)n(6)n取整(7)1100(8)log3n二、算法设计题1．有一个包括100个数据元素的数组，每个数据元素的值都是实数，试编写一个求最大数据元素的值及其下标的算法，并分析算法的时间复杂度。参考答案:voidmax(double[]a){doublemax=a[0];//初始化最大值为数组中的第一个元素intindex=0;//for(inti=0;ia.length;i++){if(maxa[i]){max=a[i];index=i;}}System.out.println(最大的实数为：+max+\n其在数组中的下标为：+index);}此算法的时间复杂度为O(n)，其中n为数组的长度。2．试编写一个求一元多项式niiinxaxP0)(的值Pn(x0)的算法，并确定算法中每一条语句的执行次数和整个算法的时间复杂度。输入是ai(i=0,1,2,…,n-1)和x0，输出为Pn(x0)。参考答案:0doublegetPolynomialResult(double[]a,doublex){//a是多项式中系数数组1doubleresult=0;2doublepowX=1;//临时变量，用于减少计算x幂的计算次数3for(inti=0;ia.length;i++){4result+=a[i]*powX;5powX*=x;6}7returnresult;8}语句1~7的执行次数分别是:1、1、a.length+1、a.length、a.length、1、1此算法的时间复杂度为O(a.length)，其中a.length也是多项式中的项数。三、上机实践题1．编写一个实现将整型数组中的数据元素按值递增的顺序进行排序的Java程序。参考答案:packagech01Exercise;publicclassExercise1_3_1{publicint[]bubbleSort(int[]a){//a为待排序的整数数组intn=a.length;booleanisExchange=true;//交换标志for(inti=0;in-1&&isExchange;i++){//最多做n-1趟排序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)在复数内部用双精度浮点数定义其实部和虚部。(2)实现3个构造函数：第1个构造函数没有参数；第2个构造函数将双精度浮点数赋给复数的实部，虚部为0；第3个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。(3)编写获取和修改复数的实部和虚部的成员函数。(4)编写实现复数的减法、乘法运算的成员函数。设计一个测试主函数，使其实际运行验证类中各成员函数的正确性。参考答案:packagech01Exercise;//复数类classComplex{privatedoublereal;//实部privatedoubleimag;//虚部//无参构造函数publicComplex(){this(0,0);}//带一个参数的构造函数publicComplex(doublereal){this(real,0);}//带两个参数的构造函数publicComplex(doublereal,doubleimag){this.real=real;this.imag=imag;}publicdoublegetReal(){returnreal;}publicvoidsetReal(doublereal){this.real=real;}publicdoublegetImag(){returnimag;}publicvoidsetImag(doubleimag){this.imag=imag;}publicvoidadd(ComplexZ){if(Z!=null){real+=Z.getReal();imag+=Z.getImag();}}//计算与另一复数的差,其中Z是减数publicvoidminus(ComplexZ){if(Z!=null){real-=Z.getReal();imag-=Z.getImag();}}//计算与另一复数的乘积,其中Z是乘数publicvoidmultiply(ComplexZ){if(Z!=null){doubletemp=(real*Z.getReal()-imag*Z.getImag());imag=(real*Z.getImag()+imag*Z.getReal());real=temp;}}}//测试类publicclassExercise1_3_2{publicstaticvoidmain(String[]args){Complexc1=newComplex(2,3);System.out.println(修改前c1的实部为：+c1.getReal()+虚部为：+c1.getImag());c1.setReal(1);c1.setImag(2);System.out.println(修改后c1的实部为：+c1.getReal()+虚部为：+c1.getImag());Complexc2=newComplex(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());}}运行结果: