1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解：
ADT Complex{
数据对象：D={r,i|r,i为实数} 数据关系：R={
InitComplex(&C,re,im)
操作结果：构造一个复数C，其实部和虚部分别为re和im
DestroyCmoplex(&C)
操作结果：销毁复数C
Get(C,k,&e)
操作结果：用e返回复数C的第k元的值
Put(&C,k,e)
操作结果：改变复数C的第k元的值为e
IsAscending(C)
操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0
IsDescending(C)
操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0
Max(C,&e)
操作结果：用e返回复数C的两个元素中值较大的一个
Min(C,&e)
操作结果：用e返回复数C的两个元素中值较小的一个
}ADT Complex
ADT RationalNumber{
数据对象：D={s,m|s,m为自然数，且m不为0} 数据关系：R={
InitRationalNumber(&R,s,m)
操作结果：构造一个有理数R，其分子和分母分别为s和m
DestroyRationalNumber(&R)
操作结果：销毁有理数R
Get(R,k,&e)
操作结果：用e返回有理数R的第k元的值
Put(&R,k,e)
操作结果：改变有理数R的第k元的值为e
IsAscending(R)
操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0
IsDescending(R)
操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0
Max(R,&e)
操作结果：用e返回有理数R的两个元素中值较大的一个
Min(R,&e)
操作结果：用e返回有理数R的两个元素中值较小的一个
}ADT RationalNumber
注意事项：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++;
else i++;
}
(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--; } else x++; } 解：(1) n-1 (2) n-1 (3) n-1
(4) n+(n-1)+(n-2)+...+1=
n(n?1) 2 (5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)=
i(i?1) ?2i?1n1n1n21n21n =?i(i?1)??(i?i)??i??i
2i?12i?12i?12i?1 = (6) n (7)
111n(n?1)(2n?1)?n(n?1)?n(n?1)(2n?3) 12412?n? 向下取整
(8) 1100
1.9 假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。
第一章作业答案与注意事项
