清华大学出版社数据结构（C++版）（第2版）课后习题答案最全整理

⑶ 分析条件语句，每循环一次，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所示，它是一种图结构。

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

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++描述如下：