1. 数据的逻辑结构与存储结构的基本概念；

1.1 数据的逻辑结构：

1. 数据的逻辑结构定义：
   数据结构是一个 二元组

   Data-Structure = （D，R）

   其中，D 是 数据元素的有限集合，R 是 D 上关系的集合。这种关系通常是指数据元素之间存在的逻辑关系，也称为 数据的逻辑结构。

2. 数据的逻辑结构分类：
   根据元素之间具有的不同关系，可以将数据的逻辑结构主要分为集合、线性结构 与 非线性结构。

• 集合："同属于一个集合" 关系。

• 线性结构："一对一"关系。除了第 1 个和最后一个元素，其他每一个数据元素有且仅有一个直接前驱元素和一个直接后继元素。

• 非线性结构：一般都是"一对多"、"多对一"关系。每个数据元素有且仅有一个直接前驱元素，但可以有多个后继元素。例如：图形结构（网状结构）："多对一"关系。树形结构："一对多"关系。

1.2 数据的存储结构：

1. 数据的存储结构定义：
   通常把数据结构在计算机中的表示（或者称映像）称为数据的物理结构，又称为 数据的存储结构，它包括 数据元素的表示 以及 关系 两个方面。

2. 数据的存储结构分类：
   由于映像的方式不同，同一种逻辑结构可以映像成不同的存储结构。主要分为 顺序存储结构、非顺序存储结构（链式存储结构、索引存储结构、散列存储结构）。

• 顺序存储结构：

  • 在计算机存储器中用一片地址连续的存储单元（即存储单元之间不能间隔）依次存放数据元素的信息，数据元素之间的逻辑关系通过数据元素的存储地址来直接反应。
  • 顺序存储结构中，逻辑上相邻的元素在物理地址上必然相邻。
  • 优点是：简单，易理解，且实际占用最少的存储空间。
  • 缺点是：需要占用一片地址连续的整块空间，并且存储分配要事先进行；对于一些操作的时间效率较低。

• 链式存储结构（链表结构）：

  • 在计算机存储器中用一片任意的（连续或者不连续的）存储单元依次存放数据元素的信息，一般称每个数据元素占用的若干存储单元的组合为一个链结点。
  • 每个链结点中不仅要存放一个数据元素的数据信息，还要存放一个指出这个元素在逻辑关系中的直接后继元素所在链结点的地址，该地址被称为指针。
  • 数据元素的逻辑关系通过指针间接反映。由于不要求存储地址连续，因此逻辑上相邻的数据元素在物理上不一定相邻。
  • 优点是：在需要存储空间时可以临时申请，不会造成存储空间的浪费。像插入和删除这样操作的时间效率采用链式存储远比采用顺序存储结构要高。
  • 缺点是：不仅数据元素本身的数据信息需要占用存储空间，而且指针也有存储空间的开销。链式存储结构要比顺序存储结构的空间开销大。

• 索引结构：

  • 利用数据元素的索引关系来确定数据元素存储位置的一种存储结构，由数据元素本身的数据信息以及索引表两个部分组成。

• 散列结构：

  • 由实现构造的散列函数关系及处理冲突的方法来确定数据元素在散列表中的存储位置。

1.3 数据结构主要研究内容：

1. 研究数据元素之间固有的客观联系（逻辑结构）。
2. 研究数据在计算机内部的存储方法（存储结构）。
3. 研究在数据的各种结构（逻辑和物理的）的基础上如何对数据实施有效的操作或处理（算法）。

2. 算法的定义、基本性质以及算法分析的基本概念，包括采用大O形式表示时间复杂度和空间复杂度。

2.1 算法的定义：

• 算法是用来解决某个特定课题的一些指令的集合。
• 人们组织起来准备加以实施的一系列有限的基本步骤。
• 算法就是解决问题的办法。
• 程序就是用计算机语言表述的算法，流程图是图形化的算法，公式也可以成为算法。

2.2 算法的分类：

分为数值和非数值两类：

• 数值算法：解决数值问题。科学与工程计算方面大部分算法：比如求解数值积分、代数方程、线性方程组及微分方程等。
• 非数值算法：解决非数值问题。数据处理方面大部分算法：比如查找算法、排序算法、插入或删除算法以及遍历算法。

分为递归和非递归两类：

• 理论上可以通过循环的方法，或者利用堆栈、队列等机制将递归算法转为非递归算法。

2.3 算法的基本特性：

5 个基本特性：输入、输出、有穷性、确定性、有效性：

• 输入：由算法外部提供 n（n ≥ 0）个有限量作为算法输入。也可以没有输入。
• 输出：至少有一个量作为算法的输出。
• 有穷性：算法必须在有限的步骤内结束。
• 确定性：组成算法的每一条指令必须有着清晰明确的含义，不能令读者在理解时产生二义性或者多义性。就是说，算法的每一个步骤都必须准确定义。
• 有效性：算法的每一套指令必须具有可执行性。也就是说，算法所实现的每一个动作都应该是基本和可以付诸实施的。

2.4 算法分析：

2.4.1 算法分析定义：

算法分析 是对一个算法质量优劣的评价。是对一个算法需要多少计算时间和存储空间作定量的分析。 算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。

2.4.2 算法分析所涉及的方面：

1. 正确性：当输入一组合理的数据时，能够在有限的运行时间内得出正确的结果；对于不合理的数据输入，能够给出警告提示信息（对不合理的数据输入的反应和处理能力，通常称为 算法的健壮性）。通过对数据输入的所有可能情况的分析以及上机调试，可以验证算法是否正确。
2. 时间复杂度：依据该算法编写的程序在计算机上运行时间的的度量。是一个算法（程序）运行时间的相对度量。
3. 空间复杂度：依据该算法编写的程序占用计算机存储空间多少的度量。
4. 其他方面：算法的可读性、简洁性、可移植性以及易测试性的好坏等。

2.5 时间复杂度

2.5.1 时间复杂度定义：

通常把算法中语句执行的次数作为算法时间多少的量度。只计算出算法大致的时间的数量级，不必精确计算出算法的时间。

2.5.2 大 O 形式表示时间复杂度：

• 当且仅当存在正整数 c 和 $n_0$ ，使得 $f(n) \leq cg(n)$ 对所有的 $n \geq n_0$ 成立，则称该算法的渐进时间复杂度为 $f(n) = O(g(n))$，即当实例特性 n 充分大时，算法的时间复杂度随 n 变化。
• 在最坏的情况下，若存在一个增长上界，即 $ng(n)$，则该算法的时间复杂度增长的数量级为 $g(n)$，计算法的渐进时间复杂度为 $O(g(n))$。
• 常见时间复杂度有：$O(1)、O(n)、O(n^{2})、O(log_{2}n)$ 等。

2.6 空间复杂度

空间复杂度定义：

根究算法编制的程序在计算机中运行时占用存储空间的度量。一般以数量级的形式给出，如 $O(1)、O(n)、O(n^{2})、O(log_{2}n)$ 等。