资源描述：
《二级access复习(a版)章节》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章数据结构与算法1.1算法#():解题方案准确而完整的描述(例如程序)（公共P1）#算法的特征(公共P1，口诀：有有定行)#算法的基本组成要素（）（）略作解释（公共P2）#算法复杂度（评价一个算法的两个标准）(公共P3)例题：真题P141#算法分析的目的：提高算法执行效率，降低上面两个度#算法设计方法:归纳列举递推递归减半递推回溯法#算法执行过程中所需要的存储空间不属于算法程序所占的存储空间(公共P7)#*顺序搜索法:长度为N,最好0，平均比较(N+1)/2次，最坏n次1.2数据结构的基本概念#数据结构(例如表、公共P13图形表示)1
2、)存储结构(逻辑结构在计算机中的表示,一种逻辑结构可能有多种存储结构)2)逻辑结构#数据结构作为一门学科,主要研究（数据的逻辑结构）（存储结构）（对各种数据结构的运算）#数据结构由数据元素组成(例如表中每一行(记录)),数据元素可以由若干数据项组成(例如表中每一行(记录)包含的内容).#表中也可以没有数据元素,称为空表.#一个数据存储结构应包含:1.表示数据元素的信息2.数据元素之间的前后件关系(真题P418)#家谱图,每一个人就是一个数据元素(结点).根结点没有前件,叶子结点没有后件.其余的结点叫做内部结点.结点之间的箭头代表前后件关系#前后件是
3、逻辑关系,和他们的存储位置无关.#对数据结构进行的两种基本运算（公共P14）1.3线性表及其顺序存储结构1.4栈和队列1.5线性链表#（考点P3考点8）顺序存储线性表的插入和删除运算:最坏情况下移动n个元素,最好0,平均n/2#线性表包括栈队列矩阵#栈:底指针不动,只能在一端插或删.有三种运算（公共P21）队列:尾指头空.在尾插,在头删.有两种运算（公共P23）队列的（）存储结构采取（）的形式（公共P22）.入尾进一,退头进一.(《公共》22页5段)（真题P41、9）#线性表的存储结构:1.顺序存储结构（随机存取）:存少的。内存空间连续前件一
4、定在后件的前面(真题P672顺序存储结构是把逻辑上相邻的结点存储在物理位置()的存储单元中)2.链式存储结构（顺序存取）:上面两个条件都是不一定.甚至可以存非线性结构。线性表的链式存储结构叫做线性链表。（真题P38、7）#链表的特点(真题P493)：1.一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。所以每个结点分为：数据域和指针域(数据间的逻辑关系由指针域确定)。2.各结点的存储序号不一定连续。3.存储结构和逻辑结构可以不一致。4.不可随机访问元素5.不必事先估计存储空间6.所需空间与线性表长度成正比(言外之意:浪费存储空间)
5、#1.线性链表(线性单链表、双向链表、带链的栈、带链的队列)。线性链表最后一个结点的指针域是空，头指针指向第一个数据元素的结点。插入删除不需移动元素(优点)，只需改变有关结点的指针。和栈结合（考点P4，真题P905）。2.循环链表循环链表与线性链表相比,有两个特点(看图:公共30页,真题84页2)1）在循环链表中,增加了一个表头结点其数据域().指针域指向线性表的第一个元素的结点.循环链表的头指针指向表头结点.2）循环链表中最后一个结点的指针域不是空,而是指向表头结点.即在循环链表中,所有结点的指针构成了一个环状链.#循环链表的主要优点是:从表中任
6、一结点出发都能访问到整个链表,而线性单链表做不到1.6树与二叉树#树是非线性（真题P102）#树的度（宽度）深度(高度)#树在计算机中通常用多重链表表示(公共P33)#既没有左子树，也没有右子树，这样的结点叫做叶子结点#在二叉树中，度为0的结点（叶子结点）比度为2的结点多1个#满二叉树、完全二叉树#完全二叉树深度公式int（log2n）+1（n是结点数）(真题P189)#二叉树的前序遍历（根左右）、中序遍历和后序遍历（公共39页）例题:真题P122、真题P49真题P26:树中度1、2、3、4、5、6的结点个数分别为643351,则L中叶子
7、结点的个数是1.7查找技术1.顺序查找适用于逻无或链储最坏次数(时间复杂度)n2.二分法查找适用于序序最坏log2n（真题P2311双数两边都查）1.8排序技术1.交换类排序法A冒泡排序法(交换相邻元素,将无序变成有序)B快速排序法(对线性表进行分割,靠栈来实现,从平均时间来看,该方法好,但最坏时不好)2.插入类排序法A简单插入排序法B希尔排序法(效率与所选取的增量序列有关)3.选择性排序法A简单选择排序法B堆排序法(适用于大规模线性表)#最坏:堆排序法最坏是O（nlog2n）外,前三种是n（n-1）/2(O：取小整)快速排序平均和堆排序最坏一样
8、最好情况:0#冒泡和简单插入适用于基本有序或个数较少时.效率相同(重要)#冒泡排序法:17,18,60,40,7,32,7
