计算机二级复习总结资料.docx

算法基本特征算法：是指解题方案的准确而完整的描述（算法不等于程序）程序的设计不可能优于算法的设计可行性、确定性、有穷性、足够的情报算法的基本要素对数据对象的运算和操作：算术运算、逻辑运算、关系运算、数据传输算法的控制结构：算法中各操作之间的执行顺序；描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等；一个算法一般可以用顺序、选择（分支）、循环（重复）三种基本结构组合而成算法的时间复杂度：是指执行算法所需要的计算工作量，可以用算法所执行的基本运算次数度量算法的空间复杂度：是指执行算法所需要的内存空间。算法的时间复杂度和算法的空间复杂度相互独立数据结构数据结构是指相互有关联的数据元素的集合数据：需要处理的数据元素的集合，一般来说，这些数据元素，具有某个共同的特征数据元素是数据的基本单位，即数据集合中的个体有时一个数据元素可有若干数据项组成。数据项是数据的最小单位结构：是集合中各个数据元素之间存在的某种关系（或联系）数据结构的分类1、 逻辑结构：线性结构（线性表、栈、队列）；非线性结构（树、图）2、 存储结构：顺序存储；链式存储3、 运算：插入、删除、查找、排序数据结构的逻辑结构指反映数据元素之间的逻辑关系（即前后件关系）的数据结构分为线性结构和非线性结构线性结构（线性表）有且只有一个根节点，它无前件每一个节点最多有一个前件，也最多有一个后件非线性结构不满足以上两个条件的数据结构就称为非线性结构非线性结构主要是指树形结构和网状结构数据结构的存储结构又称为数据的物理结构，是数据的逻辑结构在计算机存储空间中的存放方式顺序存储结构：主要用于线性的数据结构链式存储结构：每一个结点至少包含一个指针域，用指针的指向来体现数据元素之间在逻辑上的联系一种逻辑结构可以有多种存储结构不同的UC拿出结构其数据处理的效率不同 线性表 线性表是n（n=0）个数据元素构成的有限序列，表中除第一个元素外的每一个元素，有且只有一个前件，除最后一个元素外，有且只有一个后件。 例如：英文字母表、地理学中的四向、表格 线性表的顺序存储结构 通常，线性表可以采用顺序存储和链式存储，但一般使用顺序存储结构 线性表的顺序存储又叫做顺序表（顺序分配） 特点：线性表中所有元素所占的存储空间是连续的；线性表中数据元素在存储空间中是按逻辑顺序依次存放的；可以随机访问数据元素；做插入、删除时需移动大量元素，因此线性表不便于插入和删除元素。 栈 栈是限定在一端进行插入和删除的线性表 特点： 1、 栈是只能在栈顶进行插入和删除； 2、 栈的修改原则是“先进后出”或“后进先出”； 3、 栈底指针boottom，栈顶指针top，入栈，栈满，出栈—栈第指针不变，栈中元素随栈顶指针的变化而动态变化 4、 栈具有记忆功能 5、 栈支持子程序调用 队列 队列是指允许在一端进行插入，而在另一端进行删除的线性表。原则是：先进先出（或后进后出）。 队头指针front 队尾指针rear 入队 出队 特点：1、队列只允许在队尾进行插入，而在队头进行删除 2、队列的修改原则是“先进先出”或“后进后出” 3、队列中元素随队头指针和队尾指针的变化而动态变化 循环队列 循环队列就是讲队列存储空间的最后一个位置绕道第一个位置，形成逻辑上的环状空间 1、 rearfront s=rear-front 2、 rearfront s=容量+rear-front 3、 rear=front s=1或者s=0  二叉树的遍历 （按照一定的顺序访问二叉树中的结点，每个结点只被访问一次） 前序遍历：访问根结点、前序遍历左子树、前序遍历右子树（根左右） 中序遍历：中序遍历左子树、访问根结点、中序遍历右子树（左根右） 后序遍历：后序遍历左子树、后序遍历右子树、访问根结点（左右根） 顺序查找 顺序查找：对于长度为n的线性表，平均要进行n/2次比较，在最坏的情况下进行n次比较。 顺序查找适用于无序表或链式线性表（不管无序还是有序）（适用于所有的线性表） 二分查找 二分查找：适用于顺序存储的有序表，对长度为n的线性表，在最坏的情况下进行log_2?n次比较。 注意：即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 排序 排序 平均时间 最坏情况 交换类 冒泡排序 n（n-1）/2 n（n-1）/2 快速排序 n（n-1）/2 n（n-1）/2 插入类 插入排序 n（n-1）/2 n（n-1）/2 希尔排序 nlog_2?n n^1.5 选择类 选择排序 n（n-1）/2 n（n-1）/2 堆排序 nlog_2?n nlog_2?n 快速排序 基本思想：在要排序的序列中找一个数作为基准数（通常为第一个数）；通过交换将这个序列中所有比基