二级Access复习(A版)章节.docVIP

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