全国计算机2级公共基础知识+近三次考试真题

二级公共基础知识总结(30分：前10名选择前5名填空)以下内容分为四个部分。标有三个星号的文本表明它非常重要，而且基本上每个考试都是必修的。标有两个星号或一个星号的也很重要，而且容易测试。括号中的内容表明应该非常准确地记住。对于整份文件中的五页，建议在考试前仔细记住。第一部分是算法和数据结构(多年来占41%)1.算法对问题处理方案的正确而完整的描述称为算法。算法分析的目的是分析算法的效率，以改进算法。该算法的基本特征是可行性，确定性，贫困和有足够的信息。算法的有限性意味着算法程序的运行时间是有限的。算法的复杂度是对算法质量的一种度量，分为时间复杂度和空间复杂度。时间复杂度是指执行算法所需的计算工作量。算法的空间复杂度是指算法执行过程中所需的存储空间。无法推断算法的时间复杂度或空间复杂度。2.数据结构数据结构分为逻辑结构和存储结构。线性结构和非线性结构属于逻辑结构。序列、链和索引属于存储结构(物理结构)。循环队列属于“存储结构”。数据的存储结构，也称为物理结构，是计算机存储空间中数据逻辑结构的存储形式。一个逻辑结构可以有多个存储结构，各种存储结构影响数据处理的效率。程序执行的效率与数据的存储结构密切相关。数据结构分为线性结构和非线性结构。带链队列属于“线性结构”。线性表的存储结构主要分为顺序存储结构和链式存储结构。顺序存储结构的存储必须是连续的，链式存储的存储空间不一定是连续的。有序线性表可以采用顺序存储结构，也可以采用链式存储结构。队列是一种特殊的线性表。循环队列按照“先进先出”的原则组织数据。循环队列是队列的顺序存储结构。数据独立性分为“物理独立性”和“逻辑独立性”。当数据的存储结构发生变化时，其逻辑结构可以保持不变。因此，基于逻辑结构的应用可以不加修改地称为“物理独立”。3.堆栈和队列堆栈是一个线性表，只能在一端插入和删除。它的特点是后进先出堆栈具有存储功能；在插入和删除堆栈的操作中，不需要更改堆栈底部指针。假设元素a，b，c，d，e，f一个接一个地堆叠，堆叠的顺序是：f，e，d，c，b，a。堆栈模型队列是一个线性表，只允许在表的前面删除，在表的后面插入。执行插入操作的末端称为队列末端，执行删除操作的末端称为队列头。当队列中没有元素时，称为空队列。堆栈和队列都是线性结构，树是非线性结构。支持子程序调用的数据结构是堆栈。堆栈和队列的共同点是只允许在端点插入和删除元素。堆栈只能顺序存储的描述是错误的。堆栈可以以两种方式存储：顺序存储和链式存储。队列是一个线性表，允许在一个部分插入，在另一端删除。它的特点是“先进先出”。循环队列中元素的数量由团队头指针和团队尾指针共同决定。如果循环队列的头指针在前，尾指针在后，容量为maxSize，则循环队列中的元素数为“尾指针减去头指针”。如果是负数，增加它的容量。4.线性链表线性链表是线性表的链式存储结构。使用链表来表示线性表的优点是它很容易插入和删除。线性链表的存储空间不一定是连续的，元素的存储顺序也是如此树是一种简单的非线性结构，其存储结构采用链式存储结构，其所有元素都具有明显的层次特征。在树形结构中，一个节点所拥有的后继数称为该节点的度，所有节点中最大的度称为树的度。二叉树每个节点的度数只能取值0、1和2，不能是其他值。LDr最简单的二叉树模型只有一个没有前因的节点，称为树的根节点，简称树的根，非空二叉树只有一个根节点。二叉树中的每个节点最多可以有两个后继节点，称为节点的子节点，分别称为节点的左子树和右子树。没有后继的节点称为叶节点。树的最大高度称为树的深度。全二叉树是指除最后一层外，每层的所有节点都有两个子节点，因此k层有2k-1棵节点深度为m的全二叉树，2m-1棵节点。完整的二叉树意味着除了最后一层，每层的节点数达到最大值，只有右边的几个节点在最后一层丢失。对于任何二叉树，叶节点的数量比比率为2的节点的数量多一个，即n0=n2 1全二叉树的K层节点数为2K-1；深度为k的全二叉树，节点总数为2K-1。二叉树的第一(一)阶遍历、中间阶遍历和后续遍历：第一、中间和最后三个字是相对于根的。前序遍历：访问根节点，按顺序遍历左子树，按顺序遍历右子树。中间顺序遍历：以中间顺序遍历左子树，访问根节点，并以中间顺序遍历右子树。后顺序遍历(L R D):以后顺序遍历左子树，以后顺序遍历右子树，并访问根节点。LDrLDrLDr在先序遍历中，先序遍历后是先序遍历二叉树的遍历是一个递归过程，一阶遍历的步骤如下图所示：从大到小：把B和它的子节点看作一个整体，称为B，C和它的子节点是C，那么一阶遍历是Abc，在B和C的进一步一阶遍历之后，B是BdE，C是CFG，然后D是DHI，那么最后的结果是ABDHIECFG，或者从小到大。6.搜索技术对于长度为n的线性表，有必要比较n次，以找出最差的情况。(没有有序数据的要求)。顺序搜索的查询数最好是1，最差是n，平均为(1 n)/2。对于长度为n的有序线性表，二分法在最坏的情况下只需要比较log2n次。(数据必须有序)可以用二分法搜索的是顺序存储的有序线性表。7.分拣技术排序是指将一个无序的序列排序为一个有序的序列，该序列按值的非递减顺序排列。交换排序法：(1)冒泡排序法，需要比较的次数为n(n-1)/2；(2)快速排序法。插入排序方法：(1)简单的插入排序方法，最坏的情况需要n(n-1)/2次比较；(2)希尔排序法，最坏的情况需要O(n1.5)比较。排序方法的选择：(1)排序方法的简单选择，最坏的情况需要n(n-1)/2次比较；(2)堆排序方法，最坏的情况需要O(nlog2n)比较。与上述方法相比(希尔排序法除外)，堆排序法的时间复杂度最小。如果你不记得了，写n(n-1)/2，这更有可能。众所周知，数据表A中的每个元素都离最终位置不远。为了节省时间，要采用的算法是直接插入排序。选择排序、插入排序、快速排序和合并排序，并且合并排序具有最大的内存需求。第二部分是软件工程的基础(多年来占27%)1.软件工程的基本概念软件是一套完整的程序、数据和相关文档。软件是一种逻辑产品。软件工程的三个要素包括方法、工具和过程，其中过程支持软件开发的所有方面的控制和管理。软件工程的核心思想：将软件产品视为工程产品，强调“工程”原则在软件开发过程中的应用。从工程管理的角度来看，软件设计一般分两步完成，即“概要设计”和“详细设计”。软件生命周期可以分为多个阶段，一般分为“定义”阶段、“开发”阶段和“维护”阶段。编码和测试属于“开发阶段”。需求分析阶段生成的主要文档是“软件需求规范”。软件需求的规范应该是完整的、明确的、正确的、可验证的和可修改的，其中最重要的是正确性。2.结构分析和设计需求分析的分布包括：结构化需求分析方法和面向对象分析方法。数据流图(DFD)是需求分析阶段可以使用的工具之一。结构分析常用工具：数据流图(DFD)；数据字典；决策树；决策表。当数据流程图(DFD)用于结构分析时，使用数据字典准确解释图形元素。数据字典是结构分析的核心。有两种典型的数据流类型，交换性和事务性。常用的工艺设计工具包括：图形工具(程序流程图、南北、PAD、HIPO)、表格工具(决策表)和语言工具(PDL伪代码)。内聚力是指模块之间的内部连接以及耦合模块之间相互连接的紧密程度。目标是模块之间具有高度的内聚性和弱耦合性。即高内聚力和低耦合。程序流程图中带箭头的线段代表控制流程。平行四边形代表输入和输出，矩形代表处理，菱形代表判断(注意数据流图中的箭头代表数据流)。符合结构原理的三种基本控制结构是：序列结构、选择结构和循环结构。3.软件测试和维护软件测试的目的是发现程序中尽可能多的错误，但不包括纠正错误。(软件调试的目的是纠正错误)软件测试分为静态测试和动态测试，其中静态测试指的是不执行程序，而只是检查程序文本。软件的动态测试主要包括黑盒测试和白盒测试。黑盒测试方法包括等价类划分法、边值分析法、误差估计法和因果图。白盒测试的主要方法包括逻辑覆盖和基本路径测试。(在考试中给出一个方法的名称，你需要知道它是白盒还是黑盒)白盒测试的原则之一是确保被测模块的每个独立路径至少执行一次。白盒测试将程序视为一组路径。软件测试通常分四个步骤进行：单元测试、集成测试、验收测试和系统测试。集成测试应该在单元测试之后进行。在模块测试中，需要为每个被测模块设计驱动模块和接收模块。驱动模块的功能是将测试数据传输到测试模块并显示结果。测试用例是为某个目标编译的一组测试输入、执行条件和预期结果。测试用例包括输入值集和输出值集。诊断和纠正程序中的错误称为程序调试(或软件调试)，也通常称为调试。软件调试可以分为静态调试和动态调试。软件交付使用后，修改软件以纠正错误或满足新需求的过程称为“软件维护”。请注意，软件维护不是软件生命周期开发阶段的任务。第三部分是数据库设计基础(历年24%)1.数据库系统的基本概念数据库设计的基本目标是解决“数据共享问题”。在数据库管理技术发展的三个阶段中，“数据库系统阶段”是数据共享的最佳阶段。数据独立性最高的阶段是数据库系统阶段。数据库系统和文件系统的区别在于前者有特定的数据模型。数据库系统中常见的数据模型包括层次模型、网络模型和关系模型。数据库系统的核心是数据库管理系统。数据库应用系统的核心是数据库维护。数据库系统包括数据库和数据库管理系统。数据库系统数据库由数据库数据库、数据库管理系统数据库、数据库管理员数据库、硬件平台和软件平台组成。数据库系统的三级模式结构：内部模式处于最低层次，反映了数据在计算机物理结构中的实际存储形式；概念模型位于中间层，它显示了设计者的数据全局逻辑需求，与软件和硬件环境无关。外部模式位于最外层，反映了用户对数据的需求。在数据库系统中，用户看到的数据模式是外部模式。数据库设计的四个阶段是：需求分析、概念设计、逻辑设计和物理设计。将电子病历图转换成关系数据模型属于逻辑设计阶段。数据库管理系统提供的数据语言：数据定义语言DDL、数据操作语言DML和数据控制语言DCL。SQL的全称是结构化查询语言，中文意思是“结构化查询语言”。2.数据模型其中实体之间的关系由树结构表示的模型是分层模型。二维表用于表示关系模型。在关系数据库中，数据被表示为二维表，每个二维表被称为“关系”。在关系数据库中，用来表示实体之间关系的是关系。当E-R图转换为关系模型时，实体和关系都可以表示为关系。判断两个实体是一对一、一对多还是多对多的方法是选择实体A，看是否有多个实体B与之对应；选择实体b，查看是否有多个实体a与之对应。例如，在“学生学习课程”中，有两个实体，学生和课程，一个学生可以学习多个课程，一个课程可以由多个学生学习，因此两者是多对多的关系。在电子病历图中，用来表示实体的图形是矩形。用来表示属性的图形是一个椭圆。用钻石来代表联系。关系表的行称为“元组”(或记录)，列称为“属性”(或字段)。在二维表中，元组的组件不能进一步分成更小的数据行。为了建立关系，必须首先构建数据的“逻辑关系”。3.关系代数在交集、差和投影中，是交集操作，它不改变关系表中的属性数，但可以减少元组数。关系操作的规则(下面描述的7个操作中的一个通常会在考试中被检查，并且必须被记住)(1)联合操作RS:联合操作是两个表行的组合，重复的行只出现一次。(2)交集运算：交集运算是选择两个表中的公共行。(3)差异操作R-S:差异操作是从表r中删除出现在r和s中的行。(4)选择操作：选择二维表的部分行称为选择操作。(5)投影操作：选择二维表格的部分列称为投影操作。(6)连接操作：根据两个表的公共属性值连接这两个表，而不移除公共属性。如果删除了重复属性，则称为自然连接。(7)笛卡儿积：依次排列并组合关系为R的每一行和关系为S的每一行。注意：除了选择操作和投影操作在一个表上操作之外，所有其他元计算都需要两个表(两个关系)。其中，并运算、交运算和差运算要求两个