22年国二考试安排（国二常考公共考点及对应真题解析）

时间已经到了3月中旬，还有十天左右全国计算机等级考试（NCRE）就将拉开序幕。为了帮助各位考生在国二的考试中取得好的成绩，我将持续为大家分享一些国二C语言（笔者考的就是C语言，其他的太多，时间有限，所以后期推送主要还是针对二级C语言）的考点总结已经真题分析，希望能对各位考生有所帮助。

【考点1】算法的基本概念

（1）概念：算法是指一系列结局问题的清晰指令。

（2）4个基本特征：可行性，确定性，有穷性，拥有足够的情报

（3）2个基本要素：对数据对象的运算和操作；算法的控制结构（运算和操作时间的顺序）。

（4）设计的基本方法：列举法，归纳法，递归法，减半递推技术和回溯法。

【真题举例】

1.下列叙述中正确的是（ ）

A）所谓算法就是计算方法

B）程序可以作为算法的一种描述方法

C）算法设计只需要考虑得到计算结果

D）算法设计可以忽略算法的运算时间

【真题解析】

由上面我们给大家讲解的算法的概念可以知道，算法是一系列的解决问题的指令，并不完全等同于数学上的计算方法，所以A错，B正确。算法的特征有穷性告诉我们算法要具有操作步骤有限，能在有限时间内完成的特点。如果一个算法执行耗费的时间太长，就算能得到结果，有什么意义呢？所以C错，D错。这些都是要综合考虑的。一般而言看见C选项这种”只“限定的可以优先考虑排除。

【考点2】算法的复杂度

（1）时间复杂度：执行算法所需要的计算工作量

（2）空间复杂度：执行算法所需要的内存空间

【真题举例】

下列叙述中正确的是（ ）

A.算法的时间复杂度与计算机的运行速度有关

B.算法的时间复杂度与运行算法时特定的输入有关系

C.算法的时间复杂度与算法程序中的语句条数成正比

D.算法的时间复杂度与算法程序编制者的水平有关

【真题解析】

不知道大家还记得高中时候我们学生物，学化学，老师一直在强调的”控制变量法

“吗，在这里我们一定要有这个想法。我们评价一个算法当然是评价算法本身，一个好的算法给一台几十年前几乎报废了的电脑来运行，也会很慢，电脑配置，电脑运行速率我们要控制变量，算法的评价不应该和电脑，编制者等等有关系，A,D排除。C选项很容易知道错误，语句的数量怎么能反映他的时间复杂度呢。就好比一个矮个子和一个高个子赛跑，你就怎么能保证高个子腿长就一定跑的快呢？

【考点3】数据结构的基本概念

数据结构是指相互有关联的数据元素的集合，即数据的组织形式。其中逻辑结构反映数据元素之间的逻辑关系。存储结构为数据的逻辑结构在计算机存储空间中的存放形式，有顺序存储，链式存储。索引存储和散列存储4种方式。

数据结构按各元素之间前后件关系的复杂度可划分为以下两种：

（1）线性结构：有且只有一个根节点，且每个节点最多有一个直接前驱和一个直接后继的非空数据结构。

（2）非线性结构：不满足线性结构的数据结构。

【真题举例】

设数据结构B=(D,R),其中D={a,b,c,d,e,f}，R={（f,a）,(d,b),(e,d),(c,e),(a,c)}，该数据结构为（ ）

A.线性结构

b.循环队列

C.循环链表

D.非线性结构

【真题解析】

首先来解答大家对于B,D,R三个英文字母是什么意思的疑问：D是数据元素的集合，R反映了D中各元素之间的前后件关系，B表示数据结构。B=（D,R）可以理解为数据结构=（数据元素的集合 各数据元素之间的前后件关系），明白了这一点，接下来我们来看一张示意图。

（f,a）表示f是a的前件，a是f的后件，我们用箭头连起来：f→a；（a,c）表示a是c的前件，我们把a→c连起来，最终可以形成一个开环f→a→c→e→d→b，显然这是一个线性结构，所以选A。

【考点4】循环队列及其运算

所谓的循环队列就是将队列存储空间的最后一个位置绕道第一个位置，形成逻辑上的环状空间。

入队运算是指在循环队列的对胃加入一个新元素。当循环队列非空（s=1）且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算，这种情况称为“上溢”

退队运算是指在循环队列的队头位置退出一个元素并赋给指定的变量。首先将队头指针进一，然后将排头指针指向的元素赋给指定的变量。当循环队列为空（s=0）时，不能进行退队运算，这种情况称为“下溢”。

【真题举例】

设循环队列的存储空间为 Q(1:50），初始状态为front=rear=50.现经过一系列入队与退队操作后，front=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为（ ）

A.3

B.1

C.2

D.52

【真题解析】

从他的存储空间（1:50）可以知道在初始状态，即front=rear=50这一条件意味着循环队列为空，按照题目说的进行一系列操作之后末态是front=rear=1，搞了半天最后还是个空的队列，最后呢，题目说又正常的加入了两个元素，那么答案不就出来了，空→一系列操作→空→加两个元素，那队列里不就只有两个元素了吗，所以选C。

【考点5】二叉树的定义及基本性质

<1>二叉树的定义

二叉树是一种非线性结构，是有限的节点集合，该集合为空或由一个根节点及两颗互不相交的左右二叉子树组成。可分为满二叉树和完全二叉树，其中满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

二叉树具有如下两个特点：

1.二叉树可为空，空的二叉树无节点，非空二叉树有且只有一个根节点

2.每个节点最多有两颗子树，称为左子树和右子树。

<2>二叉树的基本性质

性质1：在二叉树的第k层上至多有2的k 1次方个节点（k≥1）

性质2：深度为m的二叉树至多有2的m次方减1个节点。

性质3：对任何一颗二叉树，度为0的节点总是比度为2的节点多一个

性质4：具有n个节点的二叉树的深度至少为[log2 n] 1，其中log2 n表示log2 n的整数部分。（注log2 n是以2为底，n的对数，由于手机上暂时无法打出数学格式，所以注以文字说明，望各位读者谅解）

<3>满二叉树与完全二叉树

（1）满二叉树：满二叉树是这样的一种二叉树：除最后一层外，每一层上的所有节点都有两个字节点，满二叉树在其第i层上有2的i-1次方个节点

（2）完全二叉树：完全二叉树是指这样的二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点。

<4>二叉树的存储结构

二叉树通常采用链式存储结构，存储节点由数据域和指针域（左指针域和右指针域）组成，二叉树的链式存储结构也称二叉树链表，对满二叉树和完全二叉树可按层次进行顺序存储。

【真题举例】

深度为7的二叉树共有127个结点，则下列说法中错误的是（ ）

A.该二叉树有一个度为1的结点

B.该二叉树是满二叉树

C.该二叉树是完全二叉树

D.该二叉树有64个叶子结点

【真题解析】

在树的结构中，一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。在上面我们已经复习了满二叉树和完全二叉树的概念，完全二叉树是除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。满二叉树指除最后一层外，每一层上的所有结点都有两个子结点的二叉树。

再来读题，深度为7的二叉树，假设前6层一共有2的6次方-1=64-1=63个结点，那么第7层就有127-63=64个叶子结点，即第7层结点数达到了最大值。我们再看看上面的定义，好像既是满二叉树（2的6次方计算时我们认为除最后一层外，每一层上的所有结点都有两个子结点），又是完全二叉树（最后一层缺少若干结点），那么B,C,D都对，所以错的就选A了。树的度指的是一个节点所拥有的后件个数称为该节点的度，所有节点最大的度称为树的度，显然这个树没有度为1的节点。

由于篇幅原因，本期国二计算机公共基础考点总结（含真题解析）就先到这里，剩下的线性链表，查找技术，排序技术以及堆栈相对简单，大家可以自行查阅相关资料，对照真题题库，多多练习，这样，公共基础知识相关的10道选择题就能很轻松的拿下了。后面还会继续推送国二C语言的考点总结，想看的话可以加一波关注，在这里也预祝各位读者国二考试称为过儿，看了文章的各个都能过。

,