数据结构的定义 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。 数据结构：是指数据以及数据元素相互之间的联系,可以看作是相互之间存在着某种特定关系的数据元素的集合。 对数据结构的内容包括以下几个方面： ① 数据的逻辑结构，指数据元素之间的逻辑关系。 ② 数据的存储结构，指数据元素及其关系在计算机存储器中的存储方式，也称为数据的物理结构。 ③ 数据运算，指施加在数据上的操作。 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中，每一条指令表示一个或多个操作。 粗略地说，算法是为了求解问题而给出的一个指令序列，程序是算法的一种具体实现。 一个算法必须满足以下五个重要特性： 1. 有穷性 2. 确定性 3. 可行性 4. 有输入 5. 有输出 算法的重要特征 (1) 有穷性: 算法在有穷步之后结束，每一步在有穷时间内完成。 (2) 确定性: 算法中的每一条指令有明确的含义，无二义性。 (3) 可行性: 可通过已经实现的基本运算执行有限次来实现算法中的所有操作。 算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度。算法的执行时间主要与问题的规模有关。问题规模是一个与输入有关的量。 语句 频 度是指算法中该 语句 被 重复执行的次数。算法中所有语句 的频 度之和记 作Ｔ (n)，是该 算法所求解问题规模的函 数。当 问题规模趋 向 无穷大 时，Ｔ (n)的数量级 称为渐 进 时间复杂度，简 称时间复杂度，记 作Ｔ (n)=O(f(n))。 通常 采 用 算法中表示基本运算的语句 的频 度来分析算法的时间复杂度。 例 题： 1. 数据结构中的逻辑结构是指( )，物理结构是指（ ）。 2. 算法的基本特征包括有穷性、 ( )、 ( )、 有输入和输出 。 3. 算法的有穷性是指（ ）。 4. 算法的确定性是指（ ）。 5. 算法的可行性是指（ ）。 6. 算法分析的两个主要方面是分析算法的（ ） 和空间复杂度。 7. 语句 频 度是指（ 算法中该 语句 被 重复执行的次数 ）。 8. 设 n 为正 整 数，对下面的程序段 ，写 出语句 ① 、 ② 、 ③ 的频 度及该 程序段 的时间复杂度。 for (i=1; i <=n; i++) { s=0; ① n for (j=1; j <=n; j++) s=s+i× j; ② n2 if (s%2) ③ n print(s); } 第二章 线性表 本章内容： 2.1 线性表的基本概念 ...
