文档介绍：.
1 / 90.
第 1 章 绪 论
课后习题讲解
1. 填空
⑴（ ）是数据的根本单位，在计算机程序中通常作为一个整体进展考虑和处理。
【解答】数据元素
⑵（ ）是数据的最小单位，（ ）是探讨数据构造时涉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
功能：构造一个与输入值
.
4 / 90.
一样的整数
输出：无
后置条件：整数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
功能：
.
5 / 90.
推断整数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]中元素的最大值和次最大值。
【解答】算法的伪代码描绘如下：
.
6 / 90.
算法的C++描绘如下：
分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)。
学习自测及答案
1．依次存储构造的特点是（ ），链接存储构造的特点是（ ）。
【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，用指示元素存储地址的指针表示数据元素之间的逻辑关系。
2. 算法在发生非法操作时可以作出处理的特性称为（ ）。
【解答】强健性
3. 常见的算法时间困难度用大Ｏ记号表示为：常数阶( )、对数阶( )、线性阶 ( )、平方阶( )和指数阶( )。
【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)
.
7 / 90.
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+7