简介全国计算机等级考试二级公共基础知识教程是一份专门面向备考NCRE二级考生的系统复习资料旨在解决笔试公共基础知识部分约30分内容繁杂、考点分散、难以记忆的问题适用于C语言、Access、Java等多个科目同样适合在职考生利用碎片时间自学。资源为单份PDF电子文档体积仅737KB内容精炼可直接在电脑或手机上反复阅读目前已有2015人学习浏览。教程严格对照二级公共基础知识考纲分模块讲解基本数据结构与算法、程序设计基础、软件工程基础和数据库设计基础重点涵盖算法复杂度、线性表、栈与队列、树与二叉树遍历、顺序与二分查找、常用排序、结构化与面向对象方法、软件生命周期、白盒黑盒测试、关系代数及数据库设计步骤等核心考点并辅以示例分析尤其对二叉树遍历、白盒黑盒测试等易混淆概念做了清晰辨析便于考生快速建立知识框架。既适合零基础考生从头系统学习也适合考前查漏补缺是一份实用性很强的备考资料。1. 全国计算机等级考试二级公共基础这 30 分才是被低估的拉分项考二级的人多半把火力集中在 C 语言或 Access 的大题上却忽略了试卷开头那 10 道选择和 5 道填空——公共基础知识占 30 分考点覆盖算法、数据结构、软件工程和数据库设计四个模块。这部分题目规律性极强很多考点年年重复出现比如循环队列的判空判满、二叉树的遍历序列、二分查找的比较次数背过就有分没背就只能蒙。这份《全国计算机等级考试二级公共基础知识教程》就是围绕这四个模块的完整讲义既有概念定义也有运算示例适合备考时间紧、想用最短时间拿下这 30 分的考生也适合刚入行的开发人员补一遍数据结构与软件工程的基础。接下来我按考纲顺序拆一遍重点把每章真正要记的东西和容易翻车的细节都标出来。2. 数据结构与算法考纲里四个必拿分的模块2.1 从线性表到链表理解顺序存储的边界线性表是数据结构里最基础的结构考纲要求掌握它的顺序存储和链式存储两种形态。顺序存储的特点是逻辑上相邻的元素在物理内存里也相邻所以第 i 个元素的地址可以直接算出来访问任意元素的时间复杂度是 O(1)。但它有两个硬伤插入或删除元素时要移动大量数据且连续空间不够时就溢出。我一般会这样记顺序表插入元素必须从最后一个元素开始往后移删除元素则从被删位置开始往前移。比如长度为 n 的线性表在 i 位置插入一个元素需要移动 n - i 1 个元素。很多考生第一次写代码时习惯从前往后移动结果把后面的数据覆盖了这就是没理解先腾位置再赋值的顺序。链式存储把每个结点拆成数据域和指针域插入删除只需要改指针不需要搬数据但查找某个位置的元素必须从头遍历。线性链表有一个头指针 HEAD 指向第一个结点最后一个结点的指针域为空NULL。循环链表则把最后一个结点的指针指向表头结点这样从任意结点出发都能扫描到全表。判断一个链表是否为空就看头指针是否为 NULL。这里有个细节值得单独说带链的栈和带链的队列。考纲里提到可利用栈本质是把所有空闲存储结点串成一个链表需要新结点时从栈顶取释放结点时再压回栈顶。这个机制解决的就是顺序存储空间浪费和无法动态分配的问题考点常问链式存储插入删除是否需要移动元素答案始终是不需要改指针就行。2.2 栈与队列先进后出和先进先出的现场判断栈是限定在一端进行插入和删除的线性表允许操作的一端叫栈顶另一端叫栈底规则是先进后出。用顺序存储实现时需要两个关键变量栈底指针 bottom 和栈顶指针 top。top 0 表示栈空top m 表示栈满。入栈操作先把 top 加 1 再把元素放进 top 指向的位置退栈操作先把栈顶元素取出再让 top 减 1。队列则相反允许在一端插入队尾、另一端删除队首规则是先进先出。顺序存储的队列一般用循环队列把存储空间的最后一个位置绕回第一个位置形成逻辑环。循环队列里有两个指针front 指向队首元素的前一个位置rear 指向队尾元素因此队列中的元素位于 front 之后到 rear 之间的位置。循环队列最经典的考点是判空判满。初始状态 rear front m当 rear front 时队列可能为空也可能为满必须借助标志位 s 区分s 0 表示空s 1 且 front rear 表示满。入队时 rear 加 1若 rear m 1 则置 rear 1退队时 front 加 1若 front m 1 则置 front 1。向满队列插入元素会上溢向空队列删除元素会下溢。实际考试里这类题常见的问法是给一串入队出队操作让你判断最终队首队尾指针的位置或者问循环队列满的条件只要记住front rear 时还需配合 s 标志这个结论就能拿分。2.3 树与二叉树性质和遍历就是送分题树是一种非线性结构数据元素之间有明显的层次关系。树里一个结点可以有多个子结点所有结点中最大的子结点数称为该树的度叶子结点的度为 0根结点在第一层树的最大层次称为树的深度。二叉树比一般树更受考纲重视因为它结构规整且很多复杂树可以转化为二叉树来处理。二叉树的特点是每个结点最多有两个子结点且区分左右子树。四个性质必须背熟第 k 层最多有 2^(k-1) 个结点深度为 m 的二叉树最多有 2^m - 1 个结点任意二叉树中叶子结点度为 0比度为 2 的结点多一个具有 n 个结点的二叉树深度至少为 [log2n] 1。满二叉树指除最后一层外每层结点数都达到最大值完全二叉树指除最后一层外每层结点数都达到最大值最后一层只缺右边的若干结点。完全二叉树有个实用编号规则编号为 k 的结点父结点编号为 INT(k/2)左子结点为 2k右子结点为 2k 1——这个规则可以直接用于顺序存储。遍历方面前序遍历是先访问根结点、再左子树、后右子树中序遍历是先左子树、再根结点、后右子树后序遍历是先左子树、再右子树、最后根结点。我备考时的血泪经验是光背口诀没用必须动手走一遍。给定一棵具体的树从根结点开始逐层标注访问顺序多画几棵遍历序列自然就对了。2.4 复杂度计算用最坏情况做取舍依据算法复杂度分时间复杂度和空间复杂度。时间复杂度不是精确执行时间而是基本运算次数的量级常用平均性态和最坏情况两个指标衡量。平均性态是各种输入下运算次数的加权平均值最坏情况复杂度则是规模为 n 时基本运算的最大次数。考试更爱考最坏情况因为容易算、答案确定。一个典型例子是在 n 个元素的数列中查找某个数顺序查找最坏要比较 n 次二分查找最坏只要比较 [log2n] 次取整后加 1 的级别。空间复杂度则包括算法程序占用的空间、输入数据占用的空间和运行过程中的额外空间。对于备考来说不需要会推导复杂度的完整公式但需要记住常见算法的复杂度结论顺序查找 O(n)、二分查找 O(log2n)、冒泡排序和简单插入排序最坏 O(n^2)、快速排序平均 O(n log2n)、希尔排序大约 O(n^1.3)。这些结论在选择题里反复出现属于背下来就能拿分的项目。3. 查找与排序把二分法、冒泡和快排练成本能3.1 顺序查找与二分查找边界条件决定成败顺序查找就是从第一个元素开始逐个比较直到找到目标或遍历完整张表。它不要求表有序也不限制存储方式是顺序还是链式。最坏情况是目标在最后或不存在需要比较 n 次。这个算法本身没什么难度但考纲里明确强调即使是有序的线性表如果采用链式存储也只能用顺序查找——因为链表无法直接跳到中间位置。二分查找也叫折半查找它只适用于顺序存储的有序表按值非递减排列。基本思路是每次把待查区间对半分割将要查找的元素与中间元素比较相等则找到目标比中间元素大则到右半区间继续查比中间元素小则到左半区间继续查直到子表长度为 0。这里有两个边界条件值得注意中间元素的下标取法是 INT((low high) / 2)查找失败的判定是 low high 而不是 low high。我在讲二分查找时一般会提醒学员先写循环再写边界。最常见的问题是当目标不存在时死循环原因是更新边界时没有把 mid 排除在下一轮区间之外。正确的做法是查右半区间时 low mid 1查左半区间时 high mid - 1。下面是标准实现def binary_search(arr, target): low, high 0, len(arr) - 1 while low high: mid (low high) // 2 if arr[mid] target: return mid # 找到目标返回下标 elif arr[mid] target: low mid 1 # 目标在右半区间排除 mid else: high mid - 1 # 目标在左半区间排除 mid return -1 # 未找到逻辑说明mid 取区间中点比较后根据结果收缩区间。关键在于 low mid 1 和 high mid - 1 这两行它们保证每轮循环区间都在缩小不会死循环。返回 -1 表示目标不在数组中。值得注意的是边界情况数组长度为 0 时直接不进循环返回 -1目标在两端时也能正常找到。二分查找最坏情况的比较次数是 [log2n] 1 次这比顺序查找的 n 次快得多但前提是数据必须有序且顺序存储。3.2 三类排序算法从交换到插入再到选择考纲把排序分为交换类、插入类和选择类三大类。交换类排序的核心操作是交换元素位置代表是冒泡排序和快速排序。冒泡排序从表头开始逐次比较相邻元素前一个比后一个大就交换这样每一趟扫描会把当前子序列的最大值冒泡到末尾。做完整排序最多需要扫描 n - 1 趟但如果某一趟扫描中没有发生任何交换说明序列已经有序可以提前结束。快速排序是冒泡的改进版核心思想是选取一个基准元素 T把小于 T 的元素移到前面、大于 T 的移到后面一次分割把序列分成两个子表。然后对每个子表递归做同样的分割直到子表为空。注意快速排序的分割过程需要一个栈来暂存待处理的子表——实际情况是递归调用本身就隐式使用了函数调用栈考纲里的用栈实现指的就是这个。最坏情况下快排退化为 O(n^2)平均情况是 O(n log2n)。插入类排序的思路是把无序序列中的元素逐个插入到前面已经有序的子表中。简单插入排序从第二个元素开始每次把当前元素插入到前面有序序列的合适位置最坏需要 n(n - 1)/2 次比较。希尔排序是插入排序的改进先把序列按增量 h 分成若干子序列分别做插入排序再逐步减小 h最后 h 1 时做一次完整插入排序即可。选择类排序的思路是每趟从未排序部分选出最小元素放到已排序部分的末尾。简单选择排序对长度为 n 的序列需要扫描 n - 1 趟每趟找出剩余子表中的最小元素并与子表第一个元素交换。它不依赖初始序列的状态比较次数始终是 n(n - 1)/2。3.3 快速排序的递归实现与排序稳定性判断快速排序作为考纲重点值得单独写一段。它的关键在于分割函数选定基准后通过一次遍历把比基准小的元素放左边、比基准大的放右边返回基准的最终位置。然后递归处理左右两个子表。递归边界是子表长度为 0 或 1。这个流程可以写成递推的思路每次分割确定一个元素的最终位置这个位置不再改变然后处理两侧子表。判断排序算法稳定性也是常见考点。稳定排序指相等元素的相对顺序在排序前后保持不变。冒泡排序、简单插入排序是稳定的简单选择排序不稳定因为交换可能把相等元素的顺序打乱快速排序不稳定。希尔排序也不稳定因为分组后相等元素可能被分到不同子序列。选择题里如果问哪种排序是稳定的直接锁定冒泡和直接插入即可。我建议备考时把三个排序的代码都亲手敲一遍尤其冒泡和快排。不是为考试写代码而是为了理解移动元素和交换元素这两种操作的本质区别。顺序表插入删除要移动元素链表插入删除只改指针排序里的交换则是元素位置互换——把这三件事分清楚很多选择题的干扰项就自动排除了。4. 程序设计、软件工程与数据库职业视角串一遍考点4.1 结构化设计与面向对象两种思维的互补考纲的第二部分是程序设计基础内容不多但概念辨析题常考。结构化程序设计强调把一个大型程序分解为若干模块每个模块有明确的输入输出模块内部由顺序、选择、循环三种基本结构组成。它反对使用 goto 语句因为 goto 会破坏程序的控制流让代码难以阅读和测试。面向对象程序设计则换了一套思维把数据和操作数据的方法封装成对象通过消息传递来协作。三个核心特征是封装、继承和多态。封装把对象的属性和方法绑定在一起对外只暴露必要的接口继承允许子类复用父类的属性和方法多态允许不同对象对同一消息做出不同响应。备考时容易混的是结构化设计和面向对象设计的关系。这两者不是二选一——现实中很多系统先用结构化方法做模块划分再用面向对象思路设计类。考试问结构化程序设计的基本结构有哪些答案是顺序、选择、循环问面向对象方法的基本特征有哪些答案是封装、继承、多态。把这两组答案分开记基本不会失分。4.2 软件工程从数据流图到测试用例的一条线软件工程基础是第三部分的重点考试分值占比不小。核心概念是软件生命周期——一个软件从提出需求到退役的全过程包括可行性研究、需求分析、设计、编码、测试、运行维护等阶段。结构化分析方法用于需求分析阶段主要产出是数据流图DFD、数据字典和软件需求规格说明书。数据流图描述数据的流动和加工数据字典定义图中每个元素的含义。结构化设计方法把设计分成总体设计和详细设计两步。总体设计决定系统的模块结构和模块间的调用关系详细设计决定每个模块内部的算法和数据结构。这里有个考点常以选择题出现结构化设计的目标是高内聚、低耦合即模块内部联系紧密、模块之间联系尽量少。软件测试方面的考点很密集。按测试方法分白盒测试关注程序内部逻辑测试用例必须覆盖主要路径和条件组合黑盒测试只关注输入输出不关心内部实现。按测试阶段分单元测试针对单个模块集成测试检验模块间的接口系统测试把整个系统放在真实环境中验证。程序调试和测试是两回事测试是发现错误调试是定位并改正错误分静态调试和动态调试前者通过阅读代码找错后者通过运行程序观察行为。这个模块内容多且零散我一般建议用一条时间线来记忆需求分析数据流图数据字典→ 设计总体详细→ 编码 → 测试单元→集成→系统→ 维护。把每个阶段的核心产出和典型方法串在这条线上答题时按阶段定位不容易记混。4.3 数据库设计从 E-R 图到关系模型的转化规则第四部分是数据库设计基础也是 30 分里性价比很高的部分。基本概念要分清数据库是存储数据的仓库数据库管理系统DBMS是管理数据库的软件数据库系统则包括数据库、DBMS、应用程序和用户。数据模型分概念模型和逻辑模型概念模型用实体联系图E-R 图描述现实世界的实体及其联系逻辑模型则用关系表来描述。从 E-R 图导出关系数据模型的规则是每个实体转换为一个关系表实体的属性成为表的字段实体的主键成为表的主键实体间的联系也要转换为关系表联系的属性加上两端实体的主键构成新表的字段。一对一联系可以把一方的主键放到另一方表中一对多联系把一方的主键放入多方表中多对多联系则必须单独建一张联系表。考试最爱考的是多对多联系的处理记住了必须单独建表这个结论就能处理大部分题目。关系代数运算是另一个高频考点包括集合运算并、交、差和专门的关系运算选择、投影、连接。选择是从行方向筛选满足条件的元组投影是从列方向选取指定字段连接则是把两个表中的相关行拼接起来。选择题里给出一段自然语言描述让你选对应的运算符号这类题只要把选行选择、选列投影、跨表拼接连接记清楚就能快速作答。数据库设计的四个步骤也常考需求分析、概念设计、逻辑设计和物理设计。需求分析确定系统需要存储哪些数据概念设计产出 E-R 图逻辑设计把 E-R 图转换为关系表并做规范化处理物理设计决定表的存储结构和索引方式。另外关系数据库的规范化理论要求表中字段不可再分消除部分依赖和传递依赖这属于概念层面的考点理解每个字段只能存一个值、非主键字段必须完全依赖主键就够用了。5. 二级公共基础避坑指南五个最常见的翻车点5.1 循环队列判满判空front rear 怎么区分现象题目给出循环队列的 front rear问当前队列是空还是满不少考生直接答空丢分后还觉得答案有问题。原因循环队列在入队和退队过程中队尾指针 rear 追上队首指针 front 时表示满队首指针追上队尾指针时表示空。两种状态的指针位置完全相同单靠 front 和 rear 无法区分。考纲里明确要求借助标志位 s 来判断s 0 表示空s 1 且 front rear 表示满。解决做题时先看题目有没有给 s 标志或元素计数器。给了 s 就以 s 为准没给 s 但题目说经过若干次入队退队操作后 front rear通常需要自行判断队列里是否还有元素。最稳妥的办法是画出循环队列的示意图把 front 和 rear 的移动轨迹标出来。5.2 顺序表插入元素从后往前移动还是从前往后现象自己写顺序表插入代码插入完成后发现原位置后面的元素被覆盖数据丢失。原因插入操作必须先把插入位置及其后的所有元素向后移动一位腾出空位再写入新元素。如果从前往后移动前面的元素会覆盖后面的元素整个表就乱了。解决记住一个口诀插入从后往前移删除从前往后移。写代码时先定位插入位置 i从最后一个元素开始逐个把元素复制到后一个位置直到 i 位置腾空再写入新元素。同理删除元素时从 i 1 位置开始把元素逐个前移。5.3 二分查找的前提条件链式存储不能用现象题目给一个用链表存储的有序序列问能否用二分查找有考生直接选可以理由是有序就行。原因二分查找的核心操作是快速定位中间元素这要求存储结构支持随机访问。顺序存储可以通过下标直接算出中间位置的地址链表只能从头遍历取中间元素就要走一半的长度效率反而比顺序查找还差。解决记住结论——二分查找只适用于顺序存储的有序表。题目里如果出现链式存储链表字样无论是否有序都只能顺序查找。这个考点几乎年年出现属于送分题别再丢了。5.4 二叉树性质记反叶子结点和度为 2 的结点现象题目给出一棵二叉树有 n 个度为 2 的结点问叶子结点有多少个考生套公式时容易把关系记反算出的结果正好差 1。原因二叉树性质 3 是度为 0 的结点叶子结点总比度为 2 的结点多一个即 n0 n2 1。很多人记成度为 2 的结点比叶子结点多一个导致计算结果错误。解决用一个极端例子帮助记忆——一棵只有一个根结点的树叶子结点数为 1度为 2 的结点数为 0显然 n0 n2 1 成立。考试时如果时间充裕画一棵三层满二叉树数一下1 个根结点、2 个度为 2 的结点、4 个叶子结点直接验证公式。5.5 白盒测试和黑盒测试的对象混淆现象选择题问白盒测试主要用于测试什么选项里有系统功能用户界面程序内部逻辑系统性能有考生选了系统功能。原因白盒和黑盒的区别在于是否关注内部逻辑。白盒测试需要查看程序代码设计测试用例覆盖语句、分支和路径所以它测的是程序内部逻辑黑盒测试把程序当作黑匣子不管内部怎么实现只验证输入输出是否符合需求测的是功能。解决把黑白和内外绑定记忆——白盒看内部黑盒看外部。软件需求规格说明书里描述的功能用黑盒测试验证程序代码里的分支和路径用白盒测试覆盖。遇到类似的题先判断测试对象是代码逻辑还是外部功能答案基本就出来了。6. 冲刺阶段的两周刷法用真题把教材变成分数公共基础知识的特点是考点固定、重复率高因此备考策略和 C 语言大题完全不同。C 语言需要反复写代码练手感而公共基础更适合快速过教材 大量刷真题 针对性补漏的循环打法。我一般建议考前两周启动这个科目太早容易忘太晚来不及。第一轮用三天把这份教程通读一遍目标是建立知识框架不需要背任何结论。读的时候拿一支笔把每章的小标题圈出来在页边写下这个章节最核心的一个考点。比如读到循环队列就写frontrear 时看 s 标志读到二叉树就写n0n21。这一轮的价值在于让大脑知道考纲覆盖了哪些内容为后面的刷题提供索引。第二轮用五天刷近五年的真题只做公共基础那 10 道选择和 5 道填空。做题时不要翻书做完统一对答案。每道错题在教材目录里找到对应章节把相关知识点重新读一遍然后在错题旁边用红笔写出错误原因——是概念没记住还是计算过程出错。我见过太多人刷题只对答案不分析同一道题错三遍这就是在做无效劳动。第三轮用四天做错题重刷和模拟套题。把第二轮积累的错题重新做一遍仍然错的题目用小本子抄下来标注考点和正确思路。然后找两套完整的模拟试卷按真实考试时间限时完成重点训练选择题的做题速度——公共基础部分建议控制在 20 分钟以内把时间留给后面的大题。最后一两天只做一件事背高频结论。我把最常考的几个结论列成一个清单栈和队列的进出规则、循环队列判空判满条件、二叉树的四个性质、三种遍历顺序、二分查找的适用条件、三种排序的复杂度和稳定性、白盒黑盒测试的区别、E-R 图转关系模型的规则。这份清单在进考场前再看一遍比翻整本教材有效得多。关于要不要背算法的具体代码我的看法是考试不要求手写快排但强烈建议把冒泡和二分查找的代码自己敲一遍。不是为了应付笔试而是为了在面对某操作移动几次元素某算法最坏比较几次这类衍生题时脑子里有一个具体的执行过程可以推演。抽象地背结论很容易忘但如果你真的写过一遍代码这些结论就变成直觉了。我当年考二级时最失分的地方恰恰是循环队列那道题——教材上写的frontrear 时可能满也可能空我明明看过但做题时只想着指针相等就以为队列为空白白丢了两分。从那以后我每次复习数据结构都会强制自己把这类边界状态单独抄出来做成卡片考前专门过一遍。这份教程里类似的边界考点不少建议你也用这个方法整理一份自己的易错清单希望帮到你。本文还有配套的精品资源点击获取