第一章作业答案与注意事项.doc

1.1简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。1.4试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。解：ADTComplex{数据对象：D={r,i|r,i为实数}数据关系：R={<r,i>}基本操作：InitComplex(&C,re,im)操作结果：构造一个复数C，其实部和虚部分别为re和imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e返回复数C的第k元的值Put(&C,k,e)操作结果：改变复数C的第k元的值为eIsAscending(C)操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADTComplexADTRationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADTRationalNumber注意事项：1、在定义抽象数据类型数据关系时应该是用尖括号括起来的一个有序对，不要写成“s/m”这样的形式；2、抽象数据类型的定义包括数据对象、数据关系和操作三部分，缺一不可。1.8设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：(1)i=1;k=0;while(i<=n-1){@k+=10*i;i++;}(2)i=1;k=0;do{@k+=10*i;i++;}while(i<=n-1);(3)i=1;k=0;while(i<=n-1){i++;@k+=10*i;}(4)k=0;for(i=1;i<=n;i++){for(j=i;j<=n;j++)@k++;}(5)for(i=1;i<=n;i++){for(j=1;j<=i;j++){for(k=1;k<=j;k++)@x+=delta;}(6)i=1;j=0;while(i+j<=n){@if(i>j)j++;elsei++;}(7)x=n;y=0;//n是不小于1的常数while(x>=(y+1)*(y+1)){@y++;}(8)x=91;y=100;while(y>0){@if(x>100){x-=10;y--;}elsex++;}解：(1)n-1(2)n-1(3)n-1(4)n+(n-1)+(n-2)+...+1=(5)1+(1+2)+(1+2+3)+...+(1+2+3+...+n)===(6)n(7)向下取整(8)11001.9假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。intTime(intn){count=0;x=2;while(x<n/2){x*=2;count++;}returncount;}解：count=1.12设有以下三个函数：，，请判断以下断言正确与否：(1)f(n)是O(g(n))(2)h(n)是O(f(n))(3)g(n)是O(h(n))(4)h(n)是O(n3.5)(5)h(n)是O(nlogn)解：(1)对(2)错(3)错(4)对(5)错1.16试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值voidprint_descending(intx,int