计算机二级C语言公共基础知识备考：数据结构与算法核心考点解析

如果你现在正在准备计算机二级C语言考试，我猜你的复习重心八成放在程序填空题、改错题和程序设计题上，毕竟操作题占了60分，谁也不敢掉以轻心。但我见过太多考生，C语言部分刷得飞起，结果选择题栽在“公共基础知识”这10道题上，一错就是4分起步，最后硬生生从“优秀”掉到“合格”边缘，非常可惜。

这10道公共基础题，考的是数据结构与算法、程序设计基础、软件工程基础、数据库设计基础这四块，都是选择题里的“硬骨头”。它们跟C语言语法本身关系不大，更像是一套独立的计算机通识知识，偏偏在考纲里占了固定席位。好消息是，这部分考纲多年稳定、题型套路清晰，只要把常考概念和经典题型吃透，是选择题里性价比最高的得分点，完全不需要死磕教材逐字背。

这篇内容是系列总结的第一篇，我按自己备考时的复习顺序，把数据结构与算法、程序设计基础这两块最核心的知识点，连同典型习题的解题思路完整梳理一遍。软件工程和数据库部分，会在下一篇里单独开讲。整篇内容以“应试能用”为第一目标，不堆砌晦涩理论，只讲考场上真正会遇到的判断标准和计算套路，配合我自己做题时的踩坑经历，帮你少走弯路。

1. 公共基础知识考什么：先搞清楚分值再安排复习

1.1 试卷结构决定了你必须重视选择题

计算机二级C语言的整套试卷，满分100分，其中选择题40题共40分，操作题3大题共60分。选择题里，公共基础知识一般占10题左右，也就是10分，剩下30题才是C语言语法、指针、函数、结构体这些内容。

很多人有个错觉，觉得10分而已，放弃也无所谓，靠操作题拉分就够了。但实际操作题里，程序填空和程序改错本身就有运气成分，碰上不熟悉的算法思路，可能卡半天写不出来。而公共基础的10道选择题，考纲范围明确、出题方式固定，属于“只要复习了就能拿分”的类型。我带过几个学弟学妹备考，凡是选择题能稳定拿35分以上的，操作题压力会小非常多，最后基本都能过；反倒是选择题徘徊在25分左右的，操作题稍一失误就悬了。

所以我的建议很直接：公共基础这部分不能放弃，但也不需要花太多时间，掌握考点后每天刷半小时题就够了，性价比远高于死磕某个冷门C语言语法点。

1.2 四大知识板块的难度层级和复习顺序

公共基础知识官方教材一般分成四章：数据结构与算法、程序设计基础、软件工程基础、数据库设计基础。从我实际做题的感受来看，难度排序大致是：数据结构与算法 > 数据库设计基础 > 软件工程基础 > 程序设计基础。

数据结构与算法难在需要理解概念之间的关系，还要会计算，比如二叉树节点数、循环队列元素个数、排序最坏情况比较次数等，属于“理解了就送分，不理解就瞎蒙”的典型。数据库设计基础难在概念多、术语多，需要区分关系模型、关系运算、各种键的概念。软件工程和程序设计基础则相对友好，考来考去就是生命周期阶段、开发模型特点、结构化设计原则、面向对象特性这些，背清楚就能拿分。

建议复习顺序是先啃数据结构与算法这块硬骨头，趁脑子清醒时把计算类题目搞定；碎片时间用来过程序设计基础和软件工程基础这些偏记忆的内容；数据库部分放在考前一周集中突击，因为概念容易忘，背早了反而混淆。

2. 数据结构与算法：最容易被吓跑、其实最有套路的拿分项

2.1 栈和队列：先进后出与先进先出必须形成条件反射

栈和队列是选择题里的“常驻嘉宾”，几乎每年必考。栈的核心特征是后进先出（LIFO），所有插入和删除操作都只能在栈顶进行，就像往箱子里叠衣服，先放进去的压在下面，要取只能先取最上面那件。队列的核心特征是先进先出（FIFO），数据从队尾入队、从队头出队，就像食堂打饭排队，先来的人先打到饭。

栈这边的常见考法有三种：一是判别某个出栈序列是否合法；二是计算栈顶指针的变化；三是栈的应用场景，比如函数调用、括号匹配、表达式求值、递归实现等。队列那边则喜欢考循环队列的元素个数计算，公式是(rear - front + m) % m，其中m为队列容量。这个公式看着简单，但很多人容易忘记加m再取模，导致当rear小于front时算出负数。

举个例子，设循环队列的容量为10，队头指针front=2，队尾指针rear=5，则队列中元素个数为(5 - 2 + 10) % 10 = 3。如果rear=1、front=8，容量还是10，那么元素个数为(1 - 8 + 10) % 10 = 3。这种题型就是把数字往公式里代，熟练后5秒钟能出答案，千万别在这种题上丢分。

再说一个栈的经典出栈序列题：若进栈序列为1、2、3，且进栈过程中可以随时出栈，则以下哪个不可能是出栈序列？答案是3、1、2。因为要让3先出栈，说明1、2都已经压入栈内，此时3出栈后栈顶是2，只能2先出，不可能轮到1。这一类题目只要记住“入栈出栈都只能动栈顶”这一条规矩，模拟一遍就能判断。

2.2 树与二叉树：三种遍历互相推是必考基本功

二叉树是公共基础知识里计算量最大的一块，但考点其实非常集中。需要背熟的性质主要有三个：第一，第k层上最多有2^(k-1)个节点；第二，深度为m的二叉树最多有2^m - 1个节点；第三，对任何一棵二叉树，叶子节点数等于度为2的节点数加1，即n0 = n2 + 1。

第三条性质用得最多。比如题目说某二叉树共有7个节点，其中叶子节点有3个，问度为1的节点有多少个。思路是先算n2 = n0 - 1 = 2，再用总节点数7减去叶子节点数3和度为2的节点数2，得到度为1的节点数为2。这种题只要记住公式，推导过程不超过十秒。

二叉树的遍历也是高频考点。前序遍历是根左右，中序遍历是左根右，后序遍历是左右根。常考题型是给前序遍历序列和中序遍历序列，让推出后序遍历序列。解题核心是先从先序遍历中确定根节点，再拿着根节点去中序遍历里把左子树和右子树切分出来，然后递归地处理左右子树。

举例来说，已知某二叉树的前序遍历序列是ABDEC，中序遍历序列是DBEAC，第一步根据前序可知根节点是A；第二步在中序里找到A，A左侧的DBE属于左子树，右侧的C属于右子树；第三步再看左子树，前序中B在D、E之前，说明左子树的根是B，中序中D在B左侧、E在B右侧，于是D是B的左孩子、E是B的右孩子。最终得出后序遍历序列为DEBCA。

做这类题我建议草稿纸上把树形结构画出来，画清楚再写序列，不要心算，心算容易漏节点。平时练习时养成画图的习惯，考试时虽然时间紧，但画一棵小树也就几十秒，比凭空推导靠谱得多。

另外还要了解二叉排序树和满二叉树、完全二叉树的概念。二叉排序树要求左子树所有节点值小于根节点、右子树所有节点值大于根节点，常考插入后的形态判别。完全二叉树的概念容易混淆的是“满二叉树是特殊的完全二叉树”，但完全二叉树不要求每一层都满，只要最后一层节点都集中在左侧连续位置即可。二级考试对完全二叉树通常只考节点编号相关的计算，比如深度为k的完全二叉树节点数范围，记住 2^(k-1) 到 2^k - 1 之间就行。

2.3 查找与排序：复杂度对比表就是送分题

查找和排序知识点，在选择题里最常见的考法是给出一句描述，让你判断对应哪种算法，或者直接问最坏情况下的比较次数。顺序查找最坏要比较n次，平均需要(n+1)/2次，适用于无序表；二分查找要求线性表必须有序，最坏情况下比较次数为log2n向上取整，比如8个元素最多比较3次，因为2^3 = 8。

排序这一块，复杂度对比表几乎每年都会涉及至少一道题。我自己备考时把这张表反复默写了很多遍，做题时直接对照，又快又准。考试主要关注时间复杂度最好情况、最坏情况、平均情况，以及算法是否稳定。所谓稳定，是指相等元素的相对顺序在排序前后不变。

我用一张表把这些关键信息整理出来，建议你抄在本子上，考前一周每天过一遍：

记忆的时候可以抓几个关键点：稳定的只有冒泡、插入、归并，这仨加上基数排序是稳定派；快排虽然名字带“快”，但最坏情况反而是O(n^2)，一般出现在序列基本有序的时候；堆排序和归并排序无论什么情况都是O(nlogn)，属于“优等生”。判断题里经常出现“快速排序在最坏情况下比其他排序算法都快”这种错误说法，看到直接排除。

还有一种常考题型是问某趟排序后的结果，比如给一组数字问冒泡排序第一趟结束后最大的数字排到哪里，或者简单选择排序第一趟选出什么。这种题只要知道每趟排序的逻辑就能做对：冒泡第一趟把最大值冒到最后一位，简单选择第一趟把最小值放到第一位，直接插入排序每一趟保证前几个元素有序，但整个序列未必全局有序。

3. 程序设计基础：听懂结构化与面向对象，选择题就稳了一半

3.1 结构化程序设计的三种基本结构

设计基础这一章，考试重点很明确，就是结构化程序设计和面向对象程序设计两个大方向。结构化程序设计强调“自顶向下、逐步求精、模块化”，核心思想是把大问题拆成小模块，每个模块用顺序、选择、循环这三种基本结构来表达。

三种基本结构分别是：顺序结构，按语句从上到下的顺序依次执行；选择结构，根据条件判断决定执行哪个分支，包括if-else、switch等；循环结构，在满足条件时重复执行某段代码，包括while、do-while、for。这里有个高频考点：结构化程序设计的三种基本结构不包括goto跳转，凡是选项里出现“goto”的，基本可以直接排除。

我备考时自己写过一段笔记：为什么强调三种基本结构？因为顺序、选择、循环各有一个入口和一个出口，控制流清晰，程序可读性和可维护性好。如果滥用goto，代码执行流程会像蜘蛛网一样乱，后期维护非常痛苦。二级选择题里经常用这种实际工程里的长期维护角度来出题，理解了原因，判断题就不容易掉坑。

还有一种考法是问结构化程序设计原则有哪些，常见选项包括自顶向下、逐步求精、模块化、限制使用goto语句。这是多选题型的常客，记忆口诀可以总结成“一顶一求精、模块限goto”，自顶向下加逐步求精，再加模块化和限制使用goto，四个关键字抓牢就够了。

3.2 面向对象的核心概念：对象、类、继承、多态

面向对象部分的概念辨析题也非常固定。对象是面向对象方法中最基本的概念，是系统中用来描述客观事物的一个实体，由一组属性和一组操作组成。类是对象的抽象，或者说对象的模板，而对象是类的具体实例。比如“学生”是一个类，而具体到“张三”就是一个对象、一个实例。

考试常考的几个概念定义，要能准确区分：封装是把对象的属性和操作结合成一个独立单位，并尽可能隐藏内部实现细节，只保留有限的对外接口；继承是让一个类获得另一个类已有属性和方法的机制，分为单继承和多继承；多态是指同一消息被不同对象接收后可能产生不同行为，最典型的体现是不同类对同一方法的不同实现。

选择题常这样出：“下列关于类的说法中正确的是”，然后给四个选项。正确项往往是“类是对象的抽象，对象是类的实例化”；错误项经常是“类是对象的实例”、“一个类只能有一个对象”这类说法，看到直接排除。还有一种考法和生命周期相关，比如“面向对象方法中，继承是指类之间共享属性和操作的机制”，这类判断题只要抓住两个关键词“类之间”“共享”就能对。

结构化设计与面向对象设计的对比也可能考到：结构化以功能为中心，面向对象以数据为中心；结构化围绕函数模块组织程序，面向对象围绕类和对象组织程序。这个对比点不难，列个两行就能记住：结构化搞的是“过程”，面向对象搞的是“对象”，各自的核心概念不同。

我个人的复习体会是，程序设计基础这块是四章里最简单的，概念不绕，题目也很直白，基本不需要大量刷题，把教材里的概念过一遍、再做十几道真题就足够了。但这一章的分数白白丢掉实在太可惜，因为它几乎等于送分题，花最少的时间就能拿全。

4. 经典公共基础习题精讲：这10道题你真的会吗

4.1 例题1到例题5：数据结构和程序设计基础的选择题拆解

下面这些题我都是从历年真题和模拟卷里筛选出来的高频经典题型，每题附上解题思路。这也是我在备考后期用来自查的题单，你可以先自己做一遍，再看我的分析，效果更好。

例题1：一个栈的入栈序列为1、2、3、4、5，下列哪个出栈序列是不可能出现的？
A. 5、4、3、2、1
B. 4、5、3、2、1
C. 4、3、5、1、2
D. 1、2、3、4、5

答案是C。分析过程：要出栈4，说明1、2、3已经在栈内，4出栈后栈顶为3，接着出栈3，此时栈顶为2，下一个要出栈5却需要先把5压入栈，但5还没入栈，所以可以先入栈5再出栈5，因此得到4、3、5之后栈里剩1、2，栈顶是2，下一步只能出2，不可能出1。所以C项4、3、5、1、2中的最后两步“1再2”顺序反了，不可能实现。

例题2：设循环队列容量为50，队头指针front=45，队尾指针rear=10，则该队列中元素个数为多少？
A. 5
B. 15
C. 35
D. 40

答案是B。套公式(rear - front + m) % m，即(10 - 45 + 50) % 50 = 15。很多人会错选C，因为直接用45减10得35，但循环队列里rear在front前面，说明队尾已经绕过数组末尾，到了头部区域。把公式记牢，这题没难度。

例题3：某二叉树共有13个节点，其中有4个度为1的节点，则叶子节点数为多少？
A. 3
B. 4
C. 5
D. 6

答案是C。设叶子节点数为n0、度为2的节点数为n2，根据二叉树性质n0 = n2 + 1，且总节点数n = n0 + n1 + n2 = 13，n1 = 4。代入可得n0 + n2 = 9，结合n0 = n2 + 1，解得n2 = 4，n0 = 5。这类题几乎是必考题型，公式用熟之后很稳。

例题4：下列排序方法中，最坏情况下时间复杂度最小的是哪一个？
A. 冒泡排序
B. 简单插入排序
C. 简单选择排序
D. 堆排序

答案是D。冒泡、简单插入、简单选择最坏情况都是O(n^2)，堆排序最坏也是O(nlogn)。这一题表面考复杂度，实际考的是对排序算法时间复杂度的熟悉程度，所以前面那张表一定要刻在脑子里。

例题5：下列关于类和对象的叙述中，正确的是？
A. 类是关于对象性质的描述，对象是类的具体实例
B. 类是对象的抽象，对象是类的属性
C. 对象是类的抽象，类是对象的实例
D. 类和对象没有关系

答案是A。其实B、C只是把话说反了，D更是无厘头干扰项。概念辨析题的关键就是精准掌握“类是模板、对象是实例”这层关系，不管选项怎么绕都能选对。

4.2 例题6到例题10：从遍历到排序再到面向对象的混合题型

例题6：已知二叉树前序遍历为ABCDEF，中序遍历为CBAEDF，则后序遍历为？
答案是CBEFDA。这里容易错的原因在于，有些同学会把前序的第一个字母A当成永远在左子树的节点，实际上A是根节点，在中序遍历中A左边的CB都是左子树节点，右边的EDF都是右子树节点。前序第二个字母是B，说明左子树根是B，中序中C在B左侧，所以C是B的左孩子，且B没有右孩子。再看右子树，前序此时是C、D、E、F，但C已经归到左子树了，按顺序下一个未归位的是D，所以右子树的根是D；在中序里D左侧的E属于D的左子树，D右侧F属于D的右子树。后序遍历得到CBEFDA。

例题7：对长度为12的有序表进行二分查找，在等概率情况下查找失败时最少比较次数为多少？
这类题更常见的是问查找成功时最坏比较次数。对于12个元素，因为2^3 = 8 < 12 < 16 = 2^4，所以最坏比较次数为4次。如果考平均查找长度，会稍复杂一点，需要画出判定树来计算，但二级很少考那么深。关键是记住二分查找的判定树深度为log2n向上取整。

例题8：下列叙述中正确的是？
A. 快速排序在平均情况下的性能优于堆排序
B. 快速排序在最坏情况下的性能优于堆排序
C. 堆排序在最坏情况下的性能优于快速排序
D. 简单插入排序在平均情况下的性能优于快速排序

答案是C。快速排序平均情况O(nlogn)确实很快，但最坏情况会退化到O(n^2)。堆排序最坏、平均都是O(nlogn)，综合来看堆排序的最坏情况性能更稳定。这类题目就是考“快排最坏会退化”这个特性，很多模拟题都喜欢在这个点上做文章。

例题9：在面向对象方法中，将属性与操作封装在一个对象中，并尽可能隐藏对象的内部细节，这体现的是哪个特性？
A. 继承
B. 封装
C. 多态
D. 抽象

答案是B。题干几乎把封装的定义原封不动念了一遍，属于概念对应的基础题。多态强调同一操作作用于不同对象会产生不同结果，继承强调类之间共享属性与方法，抽象则是从具体事物中提取共性特征的过程。平时理解每个特性的关键词，这类题不会丢分。

例题10：下列不属于结构化程序设计原则的是？
A. 自顶向下
B. 逐步求精
C. 模块化
D. 限制使用goto语句
E. 面向对象

答案是E。这是一个“找异类”的题，其实面向对象和结构化是并列的另一套设计理念，不属于结构化设计原则。做题时看到“面向对象”选项直接排除就行。

5. 备考避坑指南：公共基础失分点，其实都是能避开的

5.1 常见失分原因与应对方法

第一个失分原因是只背结论不理解推导过程。二叉树节点数计算这类题，公式背下来很简单，但如果题目换个问法，比如给叶子节点数和度为1的节点数求总节点数，有些人就懵了。应对方法是一开始就把推导逻辑走一遍，比如n0 = n2 + 1这个公式，本质上是因为每增加一个度为2的节点，会多占用两个子节点位置、同时增加一个分支节点，计数时叶子数就比度为2的节点数多1。理解了底层含义，不管题目怎么变都能推导。

第二个失分点是忽略“最坏情况下”和“平均情况下”的限定词。我见过不少同学看到“快速排序时间复杂度为O(nlogn)”就直接选，忽略了题干问的是最坏情况。这种粗心丢分在考场上最可惜，因为知识点你是会的。对策是读题时把“最坏”“平均”“最好”这些词圈出来，选项里再逐一对照。

第三个失分点是轻视概念题。很多人觉得概念题简单，考前突击翻两眼就行，结果上了考场发现很多选项看起来都对。实际上公共基础的10道选择题里，概念辨析和计算题大约对半分，概念题往往比计算题更抠字眼。比如“对象是类的实例”和“对象是类的属性”就是天壤之别。用我上面说的关键词记忆法，抓准每个概念的核心特征，比泛泛地看教材有效得多。

5.2 复习时间和刷题策略

很多考生问我要不要专门买教材啃，我的答案是不用，教材可以作为工具书查阅，但备考主力是真题和题库。我当时用的是小黑课堂计算机二级的题库刷选择题，它有按章节分类的模块，也有整套真题模拟，利用碎片时间刷上几组非常方便，还能自动记录错题，考前专门复习错题比盲目做新题效率高得多。

时间安排上，建议考前20到30天开始集中复习公共基础知识。每天花30分钟左右，前一周把数据结构与算法部分吃透，中间用碎片时间过程序设计基础和软件工程基础，最后一周专门攻克数据库概念并刷整套真题的选择题。刷题要有意识背错题，不仅是知道哪个选项对，还要清楚其他三个选项错在哪里，这样才能应对题库中大量“同知识点换说法”的变体题。

我在备考后半段会给自己定一个选择题正确率目标，公共基础10道题至少要对8道。说实话，一开始刷题的时候我经常只对5道，尤其是二叉树的遍历推导，连续错了好几次。后来我把每道错题涉及的知识点在教材目录上做个标记，发现错误高度集中在二叉树遍历和排序复杂度这两块，于是针对性地反复看例题、重新推导，正确率很快就上来了。

5.3 考场做题顺序和一些实用技巧

考场上的做题顺序也有讲究。选择题部分，我习惯先做C语言语法题，再做公共基础题。倒不是说公共基础有多难，而是计算题需要清醒的头脑，放在前面容易紧张出错。如果你平时测试时公共基础正确率很高，先做也完全没问题，以自己的习惯为准。

遇到不会的公共基础题，不要死磕超过2分钟。选择题每题分值差不多，卡在一道题上会导致后面的C语言题没时间思考。先标记一下跳过，等把所有题目做完后再回来看。实在不会就按第一感觉选，不要反复更改答案，我在多次模拟中吃过亏，改答案的题十有八九会把对的改错。

再分享一个小技巧：做题时养成用草稿纸画图的习惯。二叉树遍历、循环队列、出栈序列这些题目，光靠脑内推演很容易出错，但在草稿纸上画个示意图，几秒钟就能看清关系。我在考场上画了至少三棵二叉树草图，虽然看起来费时间，但正确率比心算高得多。

我个人在实际备考中最深的体会是：公共基础知识这个板块，付出和回报极其不成正比。认真复习两周就能拿稳8分以上，而C语言编程题想稳定提升10分可能需要反复敲几十道程序。如果你现在还在为选择题发愁，真的不用焦虑，按这篇文章梳理的考点逐个击破，再配合题库把错题刷透，把这个板块变成你的稳定得分项并不难。接下来的第二篇内容，会继续整理软件工程基础和数据库设计基础的考点与习题，到时候我们接着聊。