计算机软件技术基础-习题一解答

线性结构习题解答第1页共16页n1in1j3n1kn162)1)(nn(n21)n(n2161)1)(2nn(n21i21i2121)i(ij1n1in1in1i2n1ii1jn1ii1jj1k习题解答3.设n为正整数,分析下列各程序段中加下划线的语句的执行次数。(1)for(inti=1;i=n;i++)for(intj=1;j=n;j++){c[i][j]=0.0;for(intk=1;k=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}(2)x=0;y=0;for(inti=1;i=n;i++)for(intj=1;j=i;j++)for(intk=1;k=j;k++)x=x+y;(3)inti=1,j=1;while(i=n&&j=n){i=i+1;j=j+i;}(4)*inti=1;do{for(intj=1;j=n;j++)i=i+j;}while(i100+n);【解答】(1)(2)(3)i=1时，i=2，j=j+i=1+2=2+1，i=2时，i=3，j=j+i=(2+1)+3=3+1+2，i=3时，i=4，j=j+i=(3+1+2)+4=4+1+2+3，i=4时，i=5，j=j+i=(4+1+2+3)+5=5+1+2+3+4，……i=k时，i=k+1，j=j+i=(k+1)+(1+2+3+4+…+k)，解出满足上述不等式的k值，即为语句i=i+1的程序步数。n233kk21kk1kni1kj2k1i线性结构习题解答第2页共16页(4)for语句每执行一次，语句i=i+j将执行n次，而i的值会增加(1)2nn因此，当for语句执行k次后，i的值将变为(1)12nnk故最终for语句的执行次数k为满足(1)11002nnkn的最小整数k，语句i=i+j的程序步数为n*k。4.试编写一个函数计算n!*2n的值，结果存放于数组A[arraySize]的第n个数组元素中，0narraySize。若设计算机中允许的整数的最大值为maxInt，则当narraySize或者对于某一个k(0kn)，使得k!*2kmaxInt时，应按出错处理。可有如下三种不同的出错处理方式：(1)用printf显示错误信息及exit(1)语句来终止执行并报告错误；(2)用返回整数函数值0,1来实现算法，以区别是正常返回还是错误返回；(3)在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。【解答】#includestdio.hconstintarraySize=100;constintMaxInt=0x7fffffff;intcalc(intT[],intn){inti,value=1;T[0]=1;if(n!=0){intedge=MaxInt/n/2;for(i=1;in;i++){value*=i*2;T[i]=value;if(valueedge)return0;}value*=n*2;}T[n]=value;printf(A[%d]=%d\n”,n,T[n]);return1;}voidmain(){intA[arraySize];inti;for(i=0;iarraySize;i++)if(!calc(A,i)){printf(failedat%d.\n,i);break;线性结构习题解答第3页共16页}}/*---------顺序表结构的定义.为简化起见，表元素我们使用整型数据----------------------数据元素从data[0]处开始存储---------------------------------*/typedefstruct/*注意typedef的使用*/{intdata[MAXSIZE];/*数据域*/intlength;/*表长*/}listtype;5.设有一个线性表(a0,a1,…,an-2,an-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为(an-1,an-2,…,a1,a0)。最后分析此算法的时间复杂度及空间复杂度。【解答】voidinverse(listtype*A){inttmp;intn=A-length;for(inti=0;i=(n-1)/2;i++){tmp=A-data[i];A-data[i]=A-data[n-i-1];A-data[n-i-1]=tmp;}}时间复杂度：需进行n/2次循环，因此时间复杂度为O(n)；空间复杂度：使用一个整形辅助存储单元tmp，因此空间复杂度为O(1)。6.顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有127个元素的顺序表进行插入,平均需要移动多少个元素?删除一个元素,又平均需要移动多少个元素?【解答】若设顺序表中已有n个元素。又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/(n+1)，但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为1/n。插入时平均移动元素个数AMN(AveragyMovingNumber)为5.632n21)n(n1n1)01)1n(n(1n1in1n1AMNn0i删除时平均移动元素个数AMN为6321n21)n(nn10)12)(n1)((nn11)i(nn1AMN1n0i7.利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，并分析(2)与(3)的时间复杂度出现差异的原因。(1)从顺序表中删除具有给定值x的所有元素。(2)从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。线性结构习题解答第4页共16页(3)从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。(4)将两个有序顺序表la,lb合并成一个新的有序顺序表lc。(5)从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。【解答】(1)从顺序表中删除具有给定值x的所有元素。voidDelValue(listtype*L,intx){inti=0,j;while(iL-length)/*循环,寻找具有值x的元素并删除它*/if(L-data[i]==x){/*删除具有值x的元素,后续元素前移*/for(j=i;jL-length-1;j++)L-data[j]=L-data[j+1];L-length--;/*表长减1*/}elsei++;}(2)实现删除其值在给定值s与t之间（要求s小于t）的所有元素的函数如下：voidDelValue_s_to_t(listtype*L,ints,intt){inti,j;if(L-length==0||s=t){printf(“Listisemptyorparametersareillegal!\n”);exit(1);}i=0;while(iL-length)/*循环,寻找具有值x的元素并删除它*/if(L-data[i]=s&&L-data[i]=t){/*删除满足条件的元素,后续元素前移*/for(j=i;jL-length-1;j++)L-data[j]=L-data[j+1];L-length--;/*表长减1*/}elsei++;}(3)实现从有序顺序表中删除其值在给定值s与t之间的所有元素的函数如下：voidDelValue_s_to_t_1(listtype*L,intsintt){inti,j,k;if(L-length==0||s=t){printf(“Listisemptyorparametersareillegal!\n”);exit(1);}for(i=0;iL-length;i++)/*循环,寻找值≥s的第一个元素*/if(L-data[i]=s)break;/*退出循环时,i指向该元素*/if(iL-length){for(j=1;i+jL-length;j++)/*循环,寻找值t的第一个元素*/if(L-data[i+j]t)break;/*退出循环时,i+j指向该元素*/for(k=i+j;kL-length;k++)/*删除满足条件的元素,后续元素前移*/L-data[k-j]=L-data[k];L-length-=j;/*表长减j*/}}线性结构习题解答第5页共16页(4)实现将两个有序顺序表合并成一个新的有序顺序表的函数如下：listtype*Merge(listtype*LA,listtype*LB){/*合并有序顺序表LA与LB成为一个新的有序顺序表并由函数返回listtype*LC;intvalue1,value2;inti,j,k;initiatelist(LC);if(LA-length+LB-lengthMAXSIZE){printf(“表上溢/n”;exit(1);}i=0,j=0,k=0;value1=LA-data[i];value2=LB-data[j];while(iLA-length&&jLB-length){/*循环,两两比较,小者存入结果表*/if(value1=value2){LC-data[k]=value1;i++;value1=LA-data[i];}else{LC-data[k]=value2;j++;value2=LB-data[j];}k++;}while(iLA-length){/*当LA表未检测完,继续向结果表传送*/LC-data[k]=value1;i++;k++;value1=LA-data[i];}while(jLB-length){/*当LB表未检测完,继续向结果表传送*/LC-data[k]=value2;j++;k++;value2=LB-data[j];}LC-length=k;returnLC;}(5)实现从表中删除所有其值重复的元素的函数如下：voidDelDouble(listtype*L){inti,j,k;inttmp;if(L-length==0){printf(“表空\n”;exit(1);}i=0;while(iL-length){/*循环检测*/j=i+1;tmp=L-data[i];while(jL-length){/*对于每一个i,重复检测一遍后续元素*/if(tmp==L-data[j]){/*如果相等,删除此结点，后续元素前移*/for(k=j+1;kL-length;k++)L-data[k-1]=L-data[k];线性结构习题解答第6页共16页L-length--;/*表最后元素位置减1*/}elsej++;}i++;/*检测完L-data[i],检测下一个*/}}8.线性表可用顺序表或链表存储。试问：(1)两种存储表示各有哪些主要优缺点?(2)如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3)若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？【解答】(1)顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。链接存储表示的存储