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

《计算机软件技术基础 习题一解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性结构习题解答习题解答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

2、+i;}(4)*inti=1;do{for(intj=1;j<=n;j++)i=i+j;}while(i<100+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的程序步数。第16页共16页

3、线性结构习题解答(4)for语句每执行一次，语句i=i+j将执行n次，而i的值会增加因此，当for语句执行k次后，i的值将变为故最终for语句的执行次数k为满足的最小整数k，语句i=i+j的程序步数为n*k。4.试编写一个函数计算n!*2n的值，结果存放于数组A[arraySize]的第n个数组元素中，0£n£arraySize。若设计算机中允许的整数的最大值为maxInt，则当n>arraySize或者对于某一个k(0£k£n)，使得k!*2k>maxInt时，应按出错处理。可有如下三种不同的出错处理方式：(1)用printf显示错

4、误信息及exit(1)语句来终止执行并报告错误；(2)用返回整数函数值0,1来实现算法，以区别是正常返回还是错误返回；(3)在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。【解答】#include constintarraySize=100;constintMaxInt=0x7fffffff; intcalc(intT[],intn){ inti,value=1;T[0]=1; if(n!=0){intedge=MaxInt/n/2;

5、for(i=1;iedge)return0;}value*=n*2;}T[n]=value;printf("A[%d]=%d”,n,T[n]);return1;}voidmain(){ intA[arraySize];inti;for(i=0;i

6、表元素我们使用整型数据----------------------数据元素从data[0]处开始存储---------------------------------*/typedefstruct/*注意typedef的使用*/{intdata[MAXSIZE];/*数据域*/intlength;/*表长*/}listtype;5.设有一个线性表(a0,a1,…,an-2,an-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为(an-1,an-2,

7、…,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.顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有

8、127个元素的顺序表进行插入,平均需要移动多少个元素?删除一个元素,又平均需要移动多少个元素?【解答】若设顺序表中已有n个元素。又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置(可以在表中最后一个表项