【精品】计算机软件技术基础习题一解答.doc

《【精品】计算机软件技术基础习题一解答.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、习题解答3.设/7为正整数，分析下列各稈序段中加下划线的语句的执行次数。(1)for(inti=1;i<=n;for(intj=1;c[i][j]=0.0;for(intk=1;i++)■Jc[i][.j]二<=n;j++){<=n;k++)c[i][j]+a[i][k]*b[k][j];x二0;y=0;for(inti=1;i<=(intj=(intk二forforn;i++)1;1;<=i；j++)<=j；k++)intiwhilex二x+y;j二1;二1,(i<=n&&j〈二n){i二i+1;j二+i；}(4)*intdo{for(i

2、ntj=1;i二i+j;<=n;j++)}while(i<100+n);【解答】(1)nnni=lj=lk=lizii=Lij=zP(i+1)^I"1n—Vi2+—Vi=i=l乙i=l1n(n+I)(2n+I)26n(n+l)m+2)6⑶i=2时,=3时,=4时,11■1=1时，i=1■1二3,=4,5,2,j二j+i=l+2=2+丄,111二k时,二k+1,j=1+2,1+2+3,5+1+2+3+4,•・・j=(k+l)+工iWn1=1.•.(k+l)+3」2+3k+3“22解出满足上述不等式的k值，即为语句i二i+1的程序步数。(4)f

3、or语句每执行一次，语彳Ui=i+j将执行n次，而i的值会增加巴凹2因此，当f"语句执行k次后，i的值将变为2故最终for语句的执行次数k为满足屮也±12nioo+〃2的最小整数k,语句i=i+j的程序步数为n*k。4.试编写一个函数计算n!*2”的值，结果存放于数组A[arraysize]的第n个数组元索屮，0WnarraySize或者对于某一个k(0maxTnt时，应按出错处理。可有如下三种不同的出错处理方式：(1)用printf显

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

5、1;i〈n;i++){value*二i*2;T[i]=value;if(value>edge)return0;}value*二n*2;}T[n]=value;printf(，ZA[%d]=%d”,n,T[n]);return1;}voidmain(){intA[arraySize];inti;for(i=0;i

6、fstruct/*注惠typedef的使用*/{intdata[MAXSTZE];/*数据域*/intlength;/*表长*/}listtype;4.设有一个线性表(ao,ab…，an-2,an-i)存放在一个一维数组A[arraySize]屮的前n个数组元索位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为(an-i,an-2,…，ab血)。最后分析此算法的时间复杂度及空间复杂度。【解答】voidinverse(listtype*A){inttmp;intn二A->length;for(inti=0;i〈=(n~l

7、)/2;i++){tmp=A->data[i];A->data[i]=A->data[n-i-l];A->data[n-i-l]=tmp;}}时间复杂度：需进行n/2次循环，因此时间复杂度为0(n)；空间复杂度：使用一个整形辅助存储单元tmp,因此空间复杂度为0(1)。5.顺序表的插入和删除要求仍然保持备个元素原来的次序。设在等概率情形下，对有127个元素的顺序表进行插入，平均需要移动多少个元素？删除一个元素，又平均需要移动多少个元索？【解答】若设顺序表屮已有n个元素。又设插入或删除表屮备个元素的概率相等，则在插入时因有n+1个插入位置(可

8、以在表屮最后一个表项后面追加)，每个元索位置插入的概率为1/(n+1)，但在删除时只能在已有n个表项范用内删除，所以每个元索位置删除的概率为1/no插入时平均移动元素个数AMN(