文档介绍：-
. z
第 1 章绪论
课后****题讲解
1. 填空
⑴〔〕是数据的根本单位，在计算机程序常作为一个整体进
⑷ 设循环体共执行T(n)次，每循环一次，循环变量y加1，最终T(n)=y，即：
(T(n)+1)2≤n，所以T(n)=O(n1/2)。
⑸ *++是根本语句，所以
5．设有数据构造〔D，R〕，其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。试画出其逻辑构造图并指出属于何种构造。
【解答】其逻辑构造图如图1-3所示，它是一种图构造。
6. 为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个根本操作，每个根本操作的接口需定义前置条件、输入、功能、输出和后置条件。
【解答】整数的抽象数据类型定义如下：
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
-
. z
7. 求多项式A(*)的算法可根据以下两个公式之一来设计：
⑴ A(*)=an*n+an-1*n-1+…+a1*+a0
⑵ A(*)=(…(an*+an-1)*+…+a1)*)+a0
根据算法的时间复杂度分析比拟这两种算法的优劣。
【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进展了优化，减少了不必要的乘法运算。
-
. z
8. 算法设计〔要求：算法用伪代码和C++描述，并分析最坏情况下的时间复杂度〕
⑴ 对一个整型数组A[n]设计一个排序算法。
【解答】下面是简单项选择择排序算法的伪代码描述。
下面是简单项选择择排序算法的C++描述。
分析算法，有两层嵌套的for循环，所以，。
⑵ 找出整型数组A[n]中元素的最大值和次最大值。
【解答】算法的伪代码描述如下：
算法的C++描述如下：
分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)。
学****自测及答案
1．顺序存储构造的特点是〔〕，存储构造的特点是〔〕。
【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，用指示元素存储地址的指针表示数据元素之间的逻辑关系。
2. 算法在发生非法操作时可以作出处理的特性称为〔〕。
【解答】强健性
3. 常见的算法时间复杂度用大Ｏ记号表示为：常数阶( )、对数阶( )、线性阶 ( )、平方阶( )和指数阶( )。
【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，