文档介绍：⑸算法分析的目的是（），算法分析的两个主要方面是（ ）
第1 章绪论
课后****题讲解
填空
(1)()是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
【解答】数据元素
3()是数据的最小单位，()是讨论数据结=O(n)。
⑶分析条件语句，每循环一次，i+j整体加1，共循环n次，所以T(n)=O(n)。
⑷设循环体共执行T(n)次，每循环一次，循环变量 y加1，最终T(n)=y，即：
仃(n)+1)2 手所以 T(n)=0(n1/2)。
S X Sl= 0(刊
⑸x++是基本语句，所以 7叫】
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所示，它是一种图结构。
为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个基本操作，每个基本操作的接 口需定义前置条件、输入、功能、输岀和后置条件。
解答】整数的抽象数据类型定义如下：
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
求多项式A(x)的算法可根据下列两个公式之一来设计：
⑴ A(x)=anxn+an-1xn-1+…+a1x+a0
⑵ A(x)=(…(anx+ad)x+ …+a1)x)+a0
根据算法的时间复杂度分析比较这两种算法的优劣。
【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化, 减少了不必要的乘法运算。
算法设计(要求：算法用伪代码和 C++描述，并分析最坏情况下的时间复杂度)
⑴对一个整型数组A［n］设计一个排序算法。
【解答】下面是简单选择排序算法的伪代码描述。
对11个记录进行n-l趙简单选挥it序I
y ［i, 中选取最小记录，1SHT标黄index；
V ！
下面是简单选择排序算法的 C++描述。
简单选择排序算圧 Sei比搐ort [
^oid SdectSort.(ini r[ ], intn)
(
for (i=0J<n-lU+^) ranTi£录进行n・L趙简单选择排序
{
indeK^i,
for (j-i+lJ<X>+)丿莊无序区中选取摄小记录 if (tfj] <r[index]) index鬥；
if (indarM) r[i]* —r[in比関； 胶换元素
)
4? M-1 厲
r（n） = s Z1 =
分析算法，有两层嵌套的for循环，所以， --■'
⑵ 找岀整型数组A［n］中元素的最大值和次最大值。
【解答】算法的伪代码描述如下:
冲 将前两个元素进行比较’较大看放到m呕中，较小者顽到mmx中’ 粧‘