2012年二级公共基础知识数据结构与算法重点讲解

　　数据结构与算法

　　◆算法的基本概念

　　1. 算法：是对问题处理方案的正确而完整的描述，是求解问题的方法，是指令的有效序列。

　　2. 具有5个特性：

　　(1) 有穷性(在有穷步后完成)算法程序的运行时间是有限的

　　(2) 确定性(每一步都有确定的含义)

　　(3) 可行性

　　(4) 输入(一个算法有零个或多个输入)

　　(5) 输出(一个算法有一个或多个输出)

　　3. 算法的复杂度

　　包括：时间复杂度和空间复杂度。 二者没有必然的联系。

　　时间复杂度：执行算法所需要的计算工作量或基本运算次数。

　　空间复杂度：算法所需要的空间的度量。

　　◆数据结构的定义

　　1. 数据结构包括数据的逻辑结构、数据的存储结构、数据的操作

　　数据的逻辑结构：数据的外部结构，指各数据元素之间的逻辑关系，反映人们对数据含义的解释。 包括：线性结构(线性表、栈、队列)和非线性结构(树和图)

　　数据的存储结构：数据的物理结构，指数据的逻辑结构在计算机中的表示。

　　一个逻辑结构可以有多种存储结构。

　　◆ 线性表：线性表中元素的个数n(n>=0)定义为线性表的长度。

　　顺序存储是线性表的一种最常用的存储方式。

　　线性表的顺序存储结构和线性表的链式存储结构分别是随机存取的存储结构和顺序存取的存储结构。

　　1.栈：是限定在表尾进行插入和删除操作的线性表。 具有记忆功能 只能顺序存储(错)

　　允许插入和删除的一端叫栈顶。另一端叫栈底。

　　后进先出的线性表

　　2队列：是限定在一端插入而在另一端删除，插入端叫队尾，删除端叫对头。

　　先进先出的线性表

　　3栈和队列的顺序存储结构

　　循环队列属于线性表存储结构中顺序存储结构和链式存储结构的前者。

　　◆ 树

　　1.定义:树的结点、度(结点的度)、叶子(终端结点)、数的度、深度、有序树和无序数

　　2.二叉树：结点至多有两棵子树，并且二叉树的子树有之分，次序不能颠倒。

　　性质：★在二叉树的第i层上至多有2i-1个结点

　　★ 深度为k的二叉树至多有2k-1个结点。

　　★ 对任一个二叉树T，如果其叶子(终端结点数)为n，度为二的结点数为m,则n=m+1.

　　★ 具有n个结点的完全二叉树的深度为k+1，其中k是㏒2n的整数部分。

　　2. 二叉树的遍历

　　▼先序遍历(根—左—右)

　　▼中序遍历(左—根—右)

　　▼后序遍历(左—右—根)

　　◆查找算法

　　(1)顺序查找

　　顺序查找的平均查找长度为(n+1)/2，最坏的情况下比较的次数为n

　　(2) 二分查找

　　限定于顺序存储的有序线性表

　　◆排序算法

　　(1)插入类排序

　　▲直接插入排序

　　▲折半插入排序

　　▲希尔排序

　　(2)交换类排序

　　▲冒泡排序 最坏情况下的比较次数n(n-1)/2

　　▲快速排序 最坏情况下的比较次数n(n-1)/2

　　(3)选择类排序

　　例题精选:

　　1. 设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为:350

　　2. 已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列为：cedba

　　3. 要求内存量最大的是：归并排序

　　4. 在数据结构中，与所使用的计算机无关的是数据的是：逻辑结构

　　5. 栈底至栈顶依次存放元素A.B.C.D,在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是：DCBEA

　　6. 已知数据表A 中每个元素距其最终位置不远，为节省时间，应采取的算法是：直接插入排序

　　7. 用链式表示线性表的优点是：便于插入和删除操作。