1.2 习题解答

1. 什么是数据？什么是数据元素？什么是数据项？什么是数据对象？

【解答】 数据是人们利用文字符号、数字符号以及其他规定的符号对客观现实世界的事物及其活动所做的抽象描述。它是计算机程序加工的“原料”。表示一个事物的一组数据称为一个数据元素，它是数据的基本单位，在计算机中通常作为一个整体来进行考虑和处理。一般情况下，一个数据元素由若干个数据项构成。数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：描述N个学生的有关信息的N个数据元素就构成了一个数据对象。

2. 什么是数据结构？

【解答】 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构、数据的存储结构(或称物理结构)和对数据所施加的一组操作。

3. 什么是数据的逻辑结构？什么是物理结构或存储结构？

【解答】 数据的逻辑结构是数据元素之间本身所固有的独立于计算机的一种结构，这种结构可以用数据元素之间固有的关系的集合来描述。数据的存储结构(或物理结构)是逻辑结构在计算机存储器中的具体存放方式的体现，是逻辑结构在计算机存储器中的映象。

4. 数据结构有哪几种基本结构？试对每一种基本结构举一个日常生活中的实际例子予以说明。

【解答】 根据数据元素之间存在的关系的不同特性，数据结构通常可以分为如下4类基本结构：

(1) 线性结构。元素之间存在一对一的线性关系，即除了第一个元素和最后一个元素外，每个元素都有一个直接前驱和一个直接后继，第一个元素有一个直接后继，最后一个元素有一个直接前驱。例如学生档案管理系统中学生记录之间的关系即为线性关系。

(2) 树形结构。数据元素之间存在着一个对多个的关系。例如，老师T指导3个硕士研究生G₁，G₂，G₃；每个研究生G_i(i=1,2,3)又分别指导3个本科生S_i1，S_i2，S_i3；则数据元素之间呈现树形结构。

(3) 图形结构或网状结构。数据元素之间存在多个对多个的关系。如城市交通网络中城市之间的交通道路的连接关系就是一个网状结构。

(4) 集合结构。数据元素之间无任何关系。

5. 什么是抽象数据类型？它与计算机高级语言中的数据类型有何关系？

【解答】 抽象数据类型通常是指由用户定义，用以表示实际应用问题的数据模型，一般由基本数据类型或其他已定义的抽象数据类型以及定义在该模型上的一组操作组成。在C语言或C++语言中，一般可用struc或直接用“类”来定义抽象数据类型。

6. 什么是算法？算法分析应包含哪些工作？

【解答】 算法(Algorithm)是对待定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法分析(Algorithm Analysis)的主要工作是从“时间”和“空间”两个方面来分析算法的效率。

7. 算法有哪些特性？算法设计有什么设计要求？

【解答】 算法应具有如下5个重要特性：

(1) 输入性；(2) 输出性；(3) 有限性；(4) 确定性；(5) 可行性。

算法设计应满足以下5个基本要求：

(1) 正确性；(2) 可读性；(3) 健壮性；(4) 高时间效率；(5) 高空间效率。

8. 下面是几个关于时间复杂度的估值问题：

(1) 当n为正整数时，n取何值能使2ⁿ＞n³？

(2) 给出5×+5logn的O值估计。

(3) 试说明2ⁿ+n³的同阶数量级是O(2ⁿ) 。

【解答】

(1) 当n=10时，有2¹⁰＞10³，而2⁹＜9³，故当n≥10时，有2ⁿ＞n³。

(2)O(n)。

(3) 因为当n趋向于无穷大时有lim((2ⁿ+n³)/ 2ⁿ)=1，所以2ⁿ+n³的同阶数量级是O(2ⁿ)。