内容发布更新时间 : 2024/10/25 1:26:51星期一 下面是文章的全部内容请认真阅读。

秋风清，秋月明,落叶聚还散,寒鸦栖复惊。

1、 2、 3、

算法是指解决方案的准确而完整的描述

算法的四个基本特性： 可行性 确定性 有穷性 拥有足够的情报

算法有两个基本的要素组成： 一、数据对象的运算和操作 二、算法的控制

结构 4、 5、

计算机中的基本操作 算术运算 逻辑运算 关系运算 数据运算

算法的控制结构给出了算法的基本框架，不仅决定了算法中各操作的执行顺序，

而且也直接反应了算法的设计是否符合结构化的原则。一个算法都可以用顺序、选择、循环3钟基本控制结构组成 6、 7、

算法的复杂度主要包括时间复杂度和空间复杂度

算法的时间复杂度是执行算法所需要的计算工作量。 他不仅应该与使用的计算

机、程序设计语言及程序编制者无关，而且应该与算法实现过程中的许多细节无关。 8、 9、

算法的空间复杂度是指执行这个算法所需要的内存空间。

如果一个数据结构中没有一个数据元素，则称该数据结构为空的数据结构。

10、 根据数据结构中个数据元素之间前后件关系的复杂程度，一般将数据结构分为 线性结构 和 非线性结构

11、 如果一个非空的数据结构满足 1、有且只有一个根结点； 2、 每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。线性结构又称线性表。

12、 在一个线性结构中插入或删除任何一个结点后还是线性结构。 13、 在计算机中存放线性表，一种最简单的方法是顺序存储。、

14、 线性表的顺序存储结构具有两个基本的特点：一、线性表中所有元素所占的存储空间是连续的。二、线性表中各数据在存储空间中是按逻辑顺序依次存放的。 15、 线性表的插入运算和删除运算 P.8-9

16、 栈是一种特殊的线性表，其插入和删除只能在表的一端进行。

17、 在栈中允许插入与删除的一端称为栈顶，而不允许插入与删除的一端称为栈底，栈的修改原则是先进后出或后进先出。

18、 入栈运算： 1、首先将栈顶指针进1，然后将新元素入到栈顶指针指向的位置。 19、 退栈预算：首先将栈顶元素赋予一个指定的变量，然后将栈顶指针退1。 20、 队列：是指允许在一端进行插入、而在另一端进行删除的线性表，允许插入的一端称为队尾，允许删除的一端称为排头。队列又称 先进先出 或 后进后出的线性表，体现了“先来先服务的原则”

21、 队列的顺序存储结构一般采用循环队列的形式。即 将队列的存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供列队循环使用。

22、 线性表的顺序存储结构具有简单、运算方便等优点。但是对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序的存储结构，二是采用链式存储结构 23、 链式存储结构中，要求每个结点有两部分组成： 一 用于存放数据元素值，称为数据域。 另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点。

24、 在链式存储结构中的存储空间可以不连续，各数据结点的存储结构与数据之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式既可以用于表示线性结构，也可以表示非线性结构 25、 线性链表： 线性表的链式存储结构称为线性链表。

26、 树： 树是一种简单的非线性结构。在树结构中，每一个结点只有一个前件，称为父结点，没有前结点的只有1个，称为根结点，简称为树的根。每一个结点可以有多个后件，他们都称为子结点。

27、 二叉树是一种重要的非线性结构。二叉树具有两个特点： 非空二叉树只有一个根结点。每个结点最多有两颗子树，且分别称为该结点的左子树与右子树。

28、 在二叉树的第K层上，最多有2k-1（k>=1）个结点

29、 深度为M 的二叉树最多有2M-1个结点。深度为M 的二叉树是指二叉树共有M 层。

30、 在任意一颗二叉树中，度为0的结点（即叶子结点）总比度为2的结点多一个。 31、 具有N个结点的二叉树，其深度至少为[log2n]+1,

32、 满二叉树，除了最后一层外，每一层上的所有结点都有两个子结点的二叉树为满二叉树。即深度为K 的满二叉树，其第K层上有2k-1个结点，且深度为M 的满二叉树共有2M-1个结点。

33、 在计算机中，二叉树通常采用链式存储结构。与线性链表类似，用于存储二叉树中各元素的存储结点也有两部分组成：数据域和指针域。 34、 二叉树的遍历可以分为三种： 前序遍历 中序遍历 后序遍历 35、 前序遍历： 首先访问根结点，然后遍历左子树，最后遍历右子树。 36、 中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树。 37、 后序遍历：首先遍历左子树，然后遍历右子树，最后访问根结点。

38、 顺序查找：又称顺序搜索，一般指在线性表中查找指定元素。对于大的线性表来说，顺序查找效率很低。但在以下两种情况只能用顺序查找： 1、如果线性表是无序的（即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能顺序查找。2、即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 39、 二分法查找: 二分法查找只能用于顺序存储的有序表。对于长度为N 的有序线性表，在最坏的情况下，二分查找只需要比较log2n次，而顺序查找则需要比较N 次。 40、 交换类排序法：是指借助数据元素之间的相互交换进行排序的一种方法。包括 冒泡排序法和 快速排序法。

41、 冒泡排序法：一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为N,则在最坏的情况下，冒泡排序需要经