文档介绍：精品文档
精品文档
1
精品文档
第1章绪论
课后****题讲解
填空
⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
【解答】数据元素
⑵（）是数据的最小单位，（）是讨论数据结=k+10*i，共执行了n次，所以T(n)=O(n)。
⑶分析条件语句，每循环一次，i+j整体加1，共循环n次，所以T(n)=O(n)。
⑷设循环体共执行 T(n)次，每循环一次，循环变量 y加1，最终
T(n)=y，即：
(T(n)+1)2≤n，所以T(n)=O(n1/2) 。
⑸x++是基本语句，所以
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所示，它是一种图结构。
为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个基本操作，每个基本操作的接
口需定义前置条件、输入、功能、输出和后置条件。【解答】整数的抽象数据类型定义如下：
ADTinteger
精品文档
精品文档
11
精品文档
Data
整数a：可以是正整数(1,2,3, )、负整数(-1,-2,-3, )和
零
Operation
Constructor
前置条件：整数 a不存在
输入：一个整数 b
功能：构造一个与输入值相同的整数
精品文档
精品文档
12
精品文档
输出：无
后置条件：整数 a具有输入的值
Set
前置条件：存在一个整数 a
输入：一个整数 b
功能：修改整数 a的值，使之与输入的整数值相同
输出：无
后置条件：整数 a的值发生改变
Add
前置条件：存在一个整数 a
输入：一个整数 b
功能：将整数a与输入的整数b相加
输出：相加后的结果
后置条件：整数 a的值发生改变
Sub
前置条件：存在一个整数 a
输入：一个整数 b
功能：将整数a与输入的整数b相减
输出：相减的结果
后置条件：整数 a的值发生改变
Multi
精品文档
精品文档
13
精品文档
前置条件：存在一个整数 a
输入：一个整数 b
功能：将整数a与输入的整数b相乘
输出：相乘的结果
后置条件：整数 a的值发生改变
Div
前置条件：存在一个整数 a
输入：一个整数 b
功能：将整数a与输入的整数b相除
输出：若整数b为零，则抛出除零异常，否则输出相除的结果
后置条件：整数 a的值发生改变
Mod
前置条件：存在一个整数 a
输入：一个整数 b
功能：求当前整数与输入整数的模，即正的余数
输出：若整数b为零，则抛出除零异常，否则输出取模的结果
后置条件：整数 a的值发生改变
Equal
前置条件：存在一个整数 a
输入：一个整数 b
功能：判断整数 a与输入的整数b是否相等
输出：若相等返回 1，否则返回0
精品文档
精品文档
14
精品文档
精品文档
精品文档
15
精品文档
后置条件：整数 a的值不发生改变
endADT
求多项式A(x)的算法可根据下列两个公式之一来设计：
⑴A(x)=anxn+an-1xn-1++a1x+a0
A(x)=((anx+an-1)x++a1)x)+a0
根据算法的时间复杂度分析比较这两种算法的优劣。
【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。
8. 算法设计（要求：算法用伪代码和 C++描述，并分析最坏情况下
的时间复杂度）
⑴对一个整型数组 A[n]设计一个排序算法。
【解答】下面是简单选择排序算法的伪代码描述。
精品文档
精品文档
16
精品文档
下面是简单选择排序算法的 C++描述。
精品文档
精品文档
164
精品文档
分析算法，有两层嵌套的 for循环，所以， 。
⑵找出整型数组A[n]中元素的最大值和次最大值。
【解答】算法的伪代码描述如下：
精品文档
精品文档
18
精品文档
算法的C++描述如下：
分析算法，只有一层循环，共执行 n-2次，所以，T(n)=O(n)。
学****自测