全国计的算机二级公共基础知识汇总.pdf

公共基础知识 二级公共基础知识总结(30 分：10 选择+5 填空) 复习及应试建议： 1．考生的复习必须遵守：“80/20 的原则” 二级考试的公共知识部分的覆盖面广，至少涵盖了计算机应用专业的四门核心课程：算 法及数据结构、程序设计基础、软件工程基础和数据库。事实上，这些课程本身的涉及面就 很广，难度系数较大。因此，这些课程甚至也是计算机专业学生最头疼的课程，对大多数考 生来说其难度之大不言而喻。 所以，考生应把80%的时间用在20% 的重点知识点上，争取用20% 的重点知识点来答对 80%的考题，这是考生复习二级考试的公共知识部分的总体思路。 2 ．复习的关键是考生必须准确判断和掌握常见考点 考生必须能够准确判断和掌握常见考点，例如：算法部分主要考查算法的概念及算法的 复杂度；数据结构部分主要考查最基本的概念、最典型的数据结构和最常见的操作；程序设 计部分主要考查程序设计风格的基本要求、结构化程序设计的最基本知识和面向对象程序设 计的最常见概念；软件工程基础部分主要考查软件工程的基本概念及软件生命周期的各个阶 段的基础知识；数据库基础部分主要考查数据库基本概念、数据模型、关系代数基础知识、 数据库设计方法和步骤。对常见考点的准确把握会使考生避免盲目学习，从而能够轻松面对 考试。 二级考试中要求的知识点都是最基本的、最简单的，真正需要“灵活”掌握的考点极少。 很多考生在考试过程中可能已经发现，该部分的题目“会做就是不懂”。所以建议在复习过程 中不要急于“灵活”，其实等到把基本的知识点掌握后自然就“灵活”了。 公共知识部分仅占30%分，题目相对简单。因此，在答题过程中，这部分要争取速度快、 准确度高。 总的原则是如果一道题在两分钟内没有任何思路，就应该跳过此题，把时间给后面的题 目。记住：二级考试是一种合格考试，不是竞赛，及格就行了。 使用说明： 公共基础的复习没有技巧，就是背诵、背诵、再背诵，就是要把这10 页纸背下来。 划线字体是至关重要的部分，框起来的字体为填空题的常考词汇，一定要背熟牢记，这里面 有 100 分里30 分的原题。 第一章 数据结构与算法 1.1 算法 算法：是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解 题的过程。算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。 算法是一组严谨地定义运算顺序的规则，每一个规则都是有效的，且是明确的，此顺序将在 有限的次数下终止。所以其四个基本特征包括： （1）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义 性； （2）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止； 1 公共基础知识 （3）可行性，算法原则上能够精确地执行； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的三种基本控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。 算法效率的度量—算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度：指执行算法所需要的计算工作量。即算法执行过程中所需要的基本运算次 数。通常，一个算法所用的时间包括编译时间和运行时间。 算法空间复杂度：指执行这个算法所需要的内存空间。包括算法程序所占的空间，输入的初 始数据所占的空间，算法执行过程中所需的额外空间。 1.2 数据结构的基本概念 数据结构：指相互有关联的数据元素的集合。 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据的逻辑结构应包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系(指逻辑关系，与存储位置无关)。 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构,也称数据物理结构。 数据的存储结构有顺序、链接、索引等。 线性结构的条件，(一个非空数据结构)： （1）有且只有一个根结点； （2）每一