发布时间 : 星期日 文章数据结构习题与答案更新完毕开始阅读4a06262cb1717fd5360cba1aa8114431b80d8ed4
【解答】整数的抽象数据类型定义如下： ADT integer Data
整数a：可以是正整数(1, 2, 3, … )、负整数(-1, -2, -3, …)和零 Operation Constructor
前置条件：整数a不存在 输入：一个整数b
功能：构造一个与输入值相同的整数 输出：无
后置条件：整数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++描述如下：