数据结构答案第1章绪论学习指导

第1章 绪论1.1 知识点分析1．数据数据是信息的载体，是对客观事物的符号表示。数据是计算机化的现实世界的事物的抽象描述。凡是能被计算机识别、存取和加工处理的符号、字符、图形、图象、声音、视频信号等

1 第章绪论 1.1 知识点分析 1 ．数据 数据是信息的载体，是对客观事物的符号表示。数据是计算机化的现实世界的事物的抽 象描述。凡是能被计算机识别、存取和加工处理的符号、字符、图形、图象、声音、视频信 号等一切信息都可以称为数据。 2 ．数据元素 数据元素是对现实世界中某独立个体的数据描述，是数据的基本单位。数据元素也称为 结点，通常由若干数据元素组成。 3 ．数据项 数据项是数据不可分割的、具有独立意义的最小数据单位，是对数据元素属性的描述。 数据、数据元素、数据项反映了数据组织的三个层次，即数据可以由若干个数据元素组 成，数据元素又有若干数据项组成。 4 ．数据对象 数据对象是性质相同的数据元素的集合，是数据的一个子集。 5 ．数据结构 数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。简言之，数据结构 是指数据之间的关系，即数据的组织形式。数据结构包括以下三个方面： 1 （）数据的逻辑结构 指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立 GG=(DR)D 于计算机的。一个数据的逻辑结构可以用二元组，来表示，其中是数据元素的 RD 集合，是上所有数据元素之间关系的有限集合。 “” 线性结构是指数据元素之间存在一对一关系的逻辑结构，非线性结构是指数据元素之 “”“” 间存在一对多或多对多关系的逻辑结构。 2 （）数据的存储结构 数据元素及其关系在计算机存储器内的表示，称为数据的存储结构，也称为数据的物理 结构。数据的存储结构是数据的逻辑结构用计算机语言的实现，它依赖于计算机语言。 3 （）数据的运算 指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而运算的实现则是在 存储结构上进行的。 6 ．算法的描述和分析 数据的运算是通过算法来描述的，对于算法的说明可以使用不同的语言，对同一问题可 以有不同的算法。首选选用的算法必须是正确的。其次，主要考虑执行算法所耗费的时间（即 时间效率）和执行算法所耗费的存储空间（即空间效率）。 1 （）时间复杂度 通常把算法中所包含简单操作次数的多少叫做算法的时间复杂度。但是当一个算法比较 复杂时，其时间复杂度的计算会变得相当困难。一般情况下，算法中原操作重复执行的次数 nf(n)T(n)T(n)=O(f(n)) 是规模的某个函数，算法的时间复杂度的数量级可记作：。 T(n) 算法的时间复杂度是该算法的时间消耗，一个算法的时间耗费就是该算法中所有语 n→∞nT(n)“O” 句的执行次数（频度）之和。当时（即当相当大时），的数量级（阶），用大 limT(n)/f(n)=CC0T(n)=O(f(n))f(n)T(n) 记号表示。由于，是不为的常数，所以。其实，就是 中最高阶的那一项，是算法中频度最大的语句频度。 一般情况下，对于循环语句只需要考虑循环体中语句的执行次数，而忽略该语句中循环