821计算机二级公共基础复习资料.doc

全国计算机等级考试——公共基础 第一章 数据结构与算法 1.1 算法 1.1.1 算法的基本概念 算法的定义：算法是指解题方案的准确而完整的描述；一系列解决问题的清晰指令。 1、算法的基本特征：（1）可行性 （2）确定性 （3）又穷性 （4）拥有足够的情报 2、算法的基本要素： （1）算法中对数据的运算和操作 ①算术运算 ②逻辑运算 ③关系运算 ④数据传输 （2）算法的控制结构 3、算法设计的基本方法 （1）列举法——根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的 （2）归纳法——通过列举少量的特殊情况，经过分析，最后找出一般的关系 （3）递推——从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果 （4）递归——将问题逐层分解，最后归结出一些最简单的问题，当解决了最后哪些最简单 的问题后，再沿着原来分解的逆过程逐步进行综合 （5）减半递推技术——“减半”：将问题的规模减半，而问题的性质不变 “递推”：重复“减半”的过程 （6）回溯法——通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一部试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探 1.1.2 算法复杂度 1、算法的时间复杂度 （1）定义：执行算法所需要的计算工作量 （2）方法：①平均性态分析法——用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量 ②最坏情况复杂性分析法——在规模为n时，算法所执行的基本运算的最大次数 2、算法的空间复杂度 （1）定义：执行算法所需要的内存空间 （2）组成：①算法程序所占的空间 ②输入的初始数据所占的存储空间 ③算法执行过程中所需要的额外空间 1.2 数据结构的基本概念 数据结构的概念：数据结构是指相互有关联的数据元素的集合，即数据的组织形式 1.2.1 什么是数据结构 数据处理：对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运 算，也包括对数据元素进行分析 1、数据的逻辑结构 （1）定义：是反映数据元素之间所固有的逻辑关系的数据结构 （2）要素：①数据元素的集合，通常记为D ②D上的关系，反映了D中各数据元素之间的前后件关系，通常记为R 2、数据的存储结构 （1）定义：数据的逻辑结构在计算机存储空间中的存放形式 （2）分类：①顺序 ②链接 ③索引 ④散列 1.2.2 数据结构的图形表示 数据结点（结点）——每一个数据元素用中间表有元素值的方框表示 前后件关系——用一条有向线段从前件结点指向后件结点 根结点——没有前件的结点 终端结点（叶子结点）——没有后件的结点 内部结点——数据结构中处理根结点与终端结点以外的其他结点 1.2.3 线性结构与非线性结构 线性结构所满足的条件： （1）非空 （2）有且只有一个根结点 （3）每一个结点最多有一个前件，也最多有一个后见 1.3 线性表及其顺序存储结构 1.3.1 线性表的基本概念 1、线性表的基本概念：线性表是又n个数据元素组成的一个有限序列，表中的每一个数据元素除了第一个之外，有且只有一个前件，除了最后一个之外，有且只有一个后件。 2、非空线性表的结构特征： （1）有且只有一个根结点，它无前件 （2）有且只有一个终端结点，它无后件 （3）除根结点与终端结点外，其他所有的结点有且只有一个前件，也有且只有一个后件。 1.3.2 线性表的顺序存储结构 1、线性表的顺序存储结构的基本特点： （1）有且只有一个根结点，它无前件 （2）有且只有一个终端结点，它无后件 （3）除根结点与终端结点外，其他所有的结点有且只有一个前件，也有且只有一个后件。 2、对线性表的运算处理： （1）插入 （2）删除 （3）查找 （4）排序 （5）分解 （6）合并 （7）复制 （8）逆转 1.3.3 顺序表的插入运算 1、把原来第n个节点至第i个节点依次往后移一个元素位置 2、把新节点放在第i个位置上 3、修正线性表的节点个数 1.3.4 顺序表的删除运算 1、把第i个元素之后不包括第i个元素的n-i个元素依次前移一个位置 2、修正线性表的节点个数 1.4 栈和队列 1.4.1 栈及其基本运算 1、什么是栈 （1）定义：栈是一种特殊的线性表，其插入运算和删除运算都只在线性表的一端进行，也 被称为“先进后出”表或“后进先出”表。 （2）概念：①栈顶：允许插入和删除的那一端 ②栈底：栈顶的另一端 ③空栈：栈中没有元素的栈 （3）特点： ①栈顶元素是最后被插入和最早被删除的元素 ②栈底元素是最早被插入和最后被删除的元素 ③栈有记忆功能 ④在顺序存储结构下，栈的插入和删除运算都不需移动表中其他数据元素 ⑤栈顶指针top动态反映了栈