后置条件：整数a具有输入的值 Set

前置条件：存在一个整数a 输入：一个整数b

功能：修改整数a的值，使之与输入的整数值相同 输出：无

后置条件：整数a的值发生改变 Add

前置条件：存在一个整数a 输入：一个整数b

功能：将整数a与输入的整数b相加 输出：相加后的结果

后置条件：整数a的值发生改变 Sub

前置条件：存在一个整数a 输入：一个整数b

功能：将整数a与输入的整数b相减 输出：相减的结果

后置条件：整数a的值发生改变 Multi

前置条件：存在一个整数a 输入：一个整数b

功能：将整数a与输入的整数b相乘 输出：相乘的结果

后置条件：整数a的值发生改变 Div

前置条件：存在一个整数a 输入：一个整数b

功能：将整数a与输入的整数b相除

输出：若整数b为零，则抛出除零异常，否则输出相除的结果 后置条件：整数a的值发生改变 Mod

前置条件：存在一个整数a 输入：一个整数b

功能：求当前整数与输入整数的模，即正的余数

输出：若整数b为零，则抛出除零异常，否则输出取模的结果 后置条件：整数a的值发生改变 Equal

前置条件：存在一个整数a 输入：一个整数b

功能：判断整数a与输入的整数b是否相等 输出：若相等返回1，否则返回0 后置条件：整数a的值不发生改变 endADT

7. 求多项式A(x)的算法可根据下列两个公式之一来设计： ⑴ A(x)=anxn+an-1xn-1+…+a1x+a0 ⑵ A(x)=(…(anx+an-1)x+…+a1)x)+a0

根据算法的时间复杂度分析比较这两种算法的优劣。

【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。

8. 算法设计（要求：算法用伪代码和C++描述，并分析最坏情况下的时间复杂度）

⑴ 对一个整型数组A[n]设计一个排序算法。 【解答】下面是简单选择排序算法的伪代码描述。

下面是简单选择排序算法的C++描述。

分析算法，有两层嵌套的for循环，所以，

。

⑵ 找出整型数组A[n]中元素的最大值和次最大值。 【解答】算法的伪代码描述如下：

算法的C++描述如下：

分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)。 学习自测及答案

1．顺序存储结构的特点是（ ），链接存储结构的特点是（ ）。 【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，用指示元素存储地址的指针表示数据元素之间的逻辑关系。

2. 算法在发生非法操作时可以作出处理的特性称为（ ）。 【解答】健壮性

3. 常见的算法时间复杂度用大Ｏ记号表示为：常数阶( )、对数阶( )、线性阶 ( )、平方阶( )和指数阶( )。

【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)

4．将下列函数按它们在n 时的无穷大阶数，从小到大排列。

n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n 【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2, (3/2)n, n!

5．试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

【解答】数据结构是指相互之间存在一定关系的数据元素的集合。而抽象数据类型是指一个数据结构以及定义在该结构上的一组操作。程序设计语言中的数据类

型是一个值的集合和定义在这个值集上一组操作的总称。抽象数据类型可以看成是对数据类型的一种抽象。

6. 对下列用二元组表示的数据结构,试分别画出对应的逻辑结构图，并指出属于何种结构。

⑴ A=(D，R)， 其中D={a1, a2, a3, a4}，R={ } ⑵ B=(D，R)， 其中D={a, b, c, d, e, f}，R={,,,,} ⑶ C=( D，R)，其中D={a，b，c，d，e，f}，R={,,,,,} ⑷ D=(D，R)， 其中D={1, 2, 3, 4, 5, 6}，

R={(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6)}

【解答】⑴ 属于集合，其逻辑结构图如图1-4(a)所示；⑵ 属于线性结构，其逻辑结构图如图1-4(b)所示；⑶ 属于树结构，其逻辑结构图如图1-4(c)所示；⑷ 属于图结构，其逻辑结构图如图1-4(d)所示。

7. 求下列算法的时间复杂度。 count=0; x=1; while (x { x*=2; count++; }

return count; 【解答】Ｏ(log2n)