821计算机的二级-公共基础复习资料

《821计算机的二级-公共基础复习资料》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、--全国计算机等级考试——公共基础第一章数据结构与算法1.1算法1.1.1算法的基本概念算法的定义：算法是指解题方案的准确而完整的描述；一系列解决问题的清晰指令。1、算法的基本特征：（1）可行性（2）确定性（3）又穷性（4）拥有足够的情报2、算法的基本要素：（1）算法中对数据的运算和操作①算术运算②逻辑运算③关系运算④数据传输（2）算法的控制结构3、算法设计的基本方法（1）列举法——根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的（2）归纳法——通过列举少量的特殊情况，经过分析，最后找出一般的关系（3）递推——从已知的初始条件出发，逐次推出所要求的各中间结果

2、和最后结果（4）递归——将问题逐层分解，最后归结出一些最简单的问题，当解决了最后哪些最简单的问题后，再沿着原来分解的逆过程逐步进行综合（5）减半递推技术——“减半”：将问题的规模减半，而问题的性质不变“递推”：重复“减半”的过程（6）回溯法——通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一部试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探1.1.2算法复杂度1、算法的时间复杂度（1）定义：执行算法所需要的计算工作量（2）方法：①平均性态分析法——用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量②最坏情况复杂性分

3、析法——在规模为n时，算法所执行的基本运算的最大次数2、算法的空间复杂度（1）定义：执行算法所需要的内存空间（2）组成：①算法程序所占的空间②输入的初始数据所占的存储空间③算法执行过程中所需要的额外空间1.2数据结构的基本概念数据结构的概念：数据结构是指相互有关联的数据元素的集合，即数据的组织形式1.2.1什么是数据结构----数据处理：对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析1、数据的逻辑结构（1）定义：是反映数据元素之间所固有的逻辑关系的数据结构（2）要素：①数据元素的集合，通常记为D②D上的关系，反映了D中各数据元素之

4、间的前后件关系，通常记为R2、数据的存储结构（1）定义：数据的逻辑结构在计算机存储空间中的存放形式（2）分类：①顺序②链接③索引④散列1.2.2数据结构的图形表示数据结点（结点）——每一个数据元素用中间表有元素值的方框表示前后件关系——用一条有向线段从前件结点指向后件结点根结点——没有前件的结点终端结点（叶子结点）——没有后件的结点内部结点——数据结构中处理根结点与终端结点以外的其他结点1.2.3线性结构与非线性结构线性结构所满足的条件：（1）非空（2）有且只有一个根结点（3）每一个结点最多有一个前件，也最多有一个后见1.3线性表及其顺序存储结构1.3.1线性表的基本概念1、线性表

5、的基本概念：线性表是又n个数据元素组成的一个有限序列，表中的每一个数据元素除了第一个之外，有且只有一个前件，除了最后一个之外，有且只有一个后件。2、非空线性表的结构特征：（1）有且只有一个根结点，它无前件（2）有且只有一个终端结点，它无后件（3）除根结点与终端结点外，其他所有的结点有且只有一个前件，也有且只有一个后件。1.3.2线性表的顺序存储结构1、线性表的顺序存储结构的基本特点：（1）有且只有一个根结点，它无前件（2）有且只有一个终端结点，它无后件（3）除根结点与终端结点外，其他所有的结点有且只有一个前件，也有且只有一个后件。2、对线性表的运算处理：（1）插入（2）删除（3）查

6、找（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）特点：①栈顶元素是最

7、后被插入和最早被删除的元素②栈底元素是最早被插入和最后被删除的元素③栈有记忆功能④在顺序存储结构下，栈的插入和删除运算都不需移动表中其他数据元素⑤栈顶指针top动态反映了栈中元素的变化情况2、栈的顺序存储及其运算（1）入栈运算在栈顶位置插入一个新元素（2）退栈运算取出栈顶元素并赋给一个指定的变量（3）读栈顶元素将栈顶元素赋给一个指定的变量1.4.2队列及其基本运算1、什么是队列（1）定义：队列是指允许在一端进行插入，而在另一端进行删除的线性表，又称“先进先出”表。（2