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

( )。Р【解答】健壮性Р3. 常见的算法时间复杂度用大O记号表示为:常数阶( )、对数阶( )、线性阶( )、平方阶( )和指数阶( )。Р【解答】O(1),O(log2n),O(n),O(n2),O(2n)Р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+7n5, 2n/2, (3/2)n, n!Р5.试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。Р【解答】数据结构是指相互之间存在一定关系的数据元素的集合。而抽象数据类型是指一个数据结构以及定义在该结构上的一组操作。程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总称。抽象数据类型可以看成是对数据类型的一种抽象。Р6. 对下列用二元组表示的数据结构,试分别画出对应的逻辑结构图,并指出属于何种结构。 Р⑴ A=(D,R), 其中D={a1, a2, a3, a4},R={ } Р⑵ B=(D,R), 其中D={a, b, c, d, e, f},R={,,,,} Р⑶ C=( D,R),其中D={a,b,c,d,e,f},R={,,,,,} Р⑷ D=(D,R), 其中D={1, 2, 3, 4, 5, 6},РR={(1, 2),(1, 4),(2, 3),(2, 4),(3, 4),(3, 5),(3, 6),(4, 6)} Р【解答】⑴属于集合,其逻辑结构图如图1-4(a)所示;⑵属于线性结构,其逻辑结构图如图1-4(b)所示;⑶属于树结构,其逻辑结构图如图1-4(c)所示;⑷属于图结构,其逻辑结构图如图1-4(d)所示。