2017全国计算机等级考试二级C语言知识点超全整(打印版).docx

全国计算机 等级考试

目录

第-部分公共基础知识

第1章算法与数据结构 .................... 1

考点1算法 ........................... I 考点2数据结构 ....................... 1 考点3线性表及英顺序存储结构 ......... 1 考点4栈和队列 ....................... 1 考点5线性链表 ....................... 2 考点6树与二叉树 ..................... 2 考点7查找技术 ....................... 3 考点8排序技术 ....................... 3 第2章程序设计基础 ...................... 4

考点I程序设计方法与风格 ............. 4 考点2结构化程序设计 ................. 5 考点3面向对象的程序设计 ............. 5 第3章软件工程基础 ...................... 5

考点1软件工程基本概念 ............... 5 考点2软件分析方法 ................... 6 考点3结构化设计方法 ................. 7 考点4软件测试 ....................... 8 考点5程用的调试 ..................... 9 笫4帝数据库设计基础 .................... 9

考点1数据库系统的基本概念 ........... 9 考点2数据带系统的基木概念 .......... 10 考点3关系代数 ...................... 12 考点4数据库设计与管理 .............. 12

第二部分二级C语言

笫1章程序设汁基本概念 ................. 14 考点1程序设计 ...................... 14 考点2 C程序的结构和格式 ............ 14 考点3常鱼和变蛍 .................... 14 考点4算术表达式 .................... 15 考点5赋值表达式 .................... 16 考点6自加.口减和逗号运算 ........... 16 第2章顺疗结构 ......................... 17

考点1字符型常屋与变虽 .............. 17 考点 2 putchar 与 gclchar 函数 ......... 17 考点3 printf函数 ..................... 17 考点4 scanf函数 ..................... 18 考点5位运算的含义和应用 ............ 18 第3章选择结构 ......................... 19

考点1关系运算符和关系表达式 ........ 19 考点2逻轉运算符和逻辑表达式 ........ 19

考点3 if语句及其构成的选择结构………19

考点4 switch语句与break语句 ......... 20 第4章循环结构 ......................... 20

考点1 while循环结构 ................. 20 考点2 do-while循环结构 .............. 21 考点3 for循环结构 ................... 21 考点4嵌套循环语句 .................. 21 第5章函数 ............................. 21

考点I库函数 ........................ 21 考点2函数的调用 .................... 22 考点3参数传递 ...................... 22 考点4函数的递归调用 ................ 23 考点5局部、全局变量和存储分类…….23 第6章地址与指针 ...................... 23 考点1变量的地址和指针 .............. 23 考点2抬针变量的操作 ................ 24 考点3函数之间地址的传递 ............ 24 第7章数组 ............................. 24

考点1 一维数组的定义及元素的引用??24 考点2函数对-维数组及元素的引用??25 考点3二维数组的定义 ................ 25 考点4二维数组和指针 ................ 25 考点5二维数组名和指针数组作为实参???26 第8章字符串 .............................. 26

考点|用-?维字符数组存放字符出?……26 考点2使指针指向字符串 .............. 26 考点3字符串的输入和输出 ............ 26 考点4字符串数组 .................... 27 考点5用于字符串处理的函数 .......... 27 第9章 编译预处理和动态存储分配 ........ 27

考点I編译预处理 .................... 27 考点2宏替换 ........................ 27 考点3文件包含处理 .................. 28 考点4动态存储分配 .................. 28 第10章 结构体.共用体和用戸定义类型28

考点1结构体 ........................ 28 考点2共用体 ........................ 29 考点3用户定义类型 .................. 29 第11章文件 ............................ 29

考点1文件指针 ...................... 29 考点2文件的读写 .................... 30

第一部分公共基础知识 第1章算法与数据结构

结构有顺序、链式存储结构。

考点3线性表及其顺序存储结构

考点1算法 1. 线性表的基本概念 1. 什么是算法 线性表是由n个数据元索组成的冇限序 列，

算法是指对解题方案的准确而完整的描述。 是故简单、最常用的数据结构。其中的数 据元素冇

着广泛的含义，可以是一个单独的数 字或字母，可计算机程序本质上就是一个算法，它告诉计算 机

以是矩阵中的一行或一列向量， 也可以是二维表中确切的步骤來执行一个指定的任务。

的一条记录。线性表是一种 线性结构。数拯元索在（1） 算法的基本特征

线性表中的位買，只収 决于它们口己的序号，即数

i般来说，算法应具有：可行性.确定性、 有

据元素Z间的相对 位置是线性的。

穷性、拥冇足够的惜报这儿个特征。

2. 线性表的顺序存储结构

（2） 算法的组成要素

-?种数据的逻辑结构根据需要可以农示成多

通常，一个算法曲两部分组成：一?是对数拯

対象的运算和操作，二是算法的控制结构。

2. 算法的复杂度 算法的复杂度是算法规模的度童，一个算法 的复杂度高低体现在运行该算法所需要的计算机 诜源的女少，所需的资源越幺，就说明该算法的 复杂度越乐反之，所需的资源越少，则该算袪 的复杂度

越低。算法复杂度包括算法的时间复杂 度和算法的空间复杂度。

考点2数据结构

1. 数据结构的概念

所谓数据结构是指由某一数据对彖及该对象

中所有数据成员乙间的关系组成的集合。成员Z 间

的关系有很多种，最常见的是前后件关系。

2. 数据的逻辑结构

（1） 逻辑结构的定义 数据的逻辑结构.是指反映数据Z间逻辑 关系的数据结构。对于电脑上的数据而言，逻 辑结构就是能够用眼睹看到的数据形式，包括 在屏幕上看到的文木.图片.视频等。 （2） 逻辑结构的分类 根据数据结构中各元素之间前后关系的复 杂程度,将数据的逻辑结构分成线性结构和非 线性结构。一个非空的线性结构如果满足以下 两个条件：①冇且只冇一个根结点：②每一个 结点最多有一个前件，也最多有一个后件。 3. 数据的存储结构

数据的存储结构也称为数据的物理结构， 是

指数据在计算机中存放的方式，包括数据元 索的

存储和关系的存储。通常，一种数据的逻 辑结构

根据需要可以表示成名种存储结构，常 用的存储

种存储结构。线性表的存储结构常用的是顺序存 储，

也称为顺序分配。线性农的顺序存储结构具 有以下

两个基本特点：①线性表中所有元索所占 的存储空

间是连续的；

②线性农中各数据元素在 存储空间中是按逻辑顺序依次存放的。 3 ?顺序表的插入

所们“顺序表”指的是使用顺序存储结构的 线性表。在顺序表中插入一个新的数据元索，就 像

是在排队买票的时候进来了一个插队的人。 4 ?顺序表的删除 在顺序表屮删除-个数据元素，就像是在排 队买票的时候其中的一个人离开了。在平均惜况 下?

要在线性表中删除一个元素，需耍移动线性 表中-?半的数据元索。

考点4栈和队列

1. 栈及其基本运算

（1）什么是栈 栈是一种特殊的线性表。在这种特殊的线 性农中，其插入和删除运算都只能在线性表的 一端进行。一端是封闭的，不允许插入和删除 数据尤素；另一端是敞开的，允许插入和删除 数据元

素。 在栈中，允许插入和删除数据元素的-端 称为栈顶，而不允许插入和删除数据元素的一 端称为栈底。栈顶元索总会是被鼠后插入的元 索，从而也是最先被删除的元索；栈底元素总 是最先被插入的元素，从而也是最后才能彼删 除的元素。

即栈足按照\先进后出”或“后进 先出”的原则组织数据的。栈具冇记忆的功能， 支持了程序的调

用。通常用指针gp來指示栈顶位 置，用指针

bottom來指示栈底的位置。往栈中 插入一个元素

称为入栈运算，从栈中删除-个元素称为退栈运算。通过栈顶指针top来反反 映两部分：一部分用于存储数据元索的 值，称为数拯

域；另一部分用于存储该数据元 素的存储序号（存栈屮元素的动态变化情况。

储结点的地址，即指向后件 结点），称为指针域。 （2）栈的基木运算

（2） 线性链表的查找 栈的基本运算有3种：入栈、退栈与读栈 顶元

在非空的线性链表中查找指定元素的操 作：索。①入栈运算。入栈运算是指在栈顶位 逍插入一

个新元索。这个运算有两个基本操 作：首先将栈顶从头指针指向的结点开始往后沿着指针进行 打描，指针进一（即lop加1）,然后 将新元素插入到栈顶如果找到要查找的内容.则查找成功：如 果没有对指针指向的位買。②退栈 运算。退栈运算是指取出的要查找的元索，则查找失败。为了 弥补线性单链栈顶元素并賦给指定 的变臺。这个运算有两个基本表的这个缺点，对线性链表中的每 个结点设買两个操作：首先将栈 顶元素赋值给一个指怎的变量，然指针，一个称为左指针

后将栈顶指 针退一（即top减1〉。③读栈顶元素。（Llink）,用以指向其前件结点；另一个称为 右指读栈顶 元索是指将栈顶元素賦给一个指定的变量，针（RIink）,用來指向其后件结点。这样 的线性表但 是不删除栈顶元索。因此，在这个运算中，栈 顶称为双向链表。 指针不会改变。当栈顶指针为0时，说明栈 空，读（3） 线性链表的插入 不到栈顶元索。 在向线性链表中插入一个新元索之前，我 们

先要给该元索分配一个新结点，其中包括值 域和指2. 队列及其基本运算

针域以便用于存储该元素的值。然厉找 到插入位（1） 什么是队列

队列是指允许在表的一端进行插入、而在另 買，将插入位置前件的指针指向新结点, 将新接点

的指针指向插入位垃后件的结点。 一端进行删除的线性表。允许插入的一端称为队

（4） 线性链衣的删除 尾，通常用一个队尾指针（real-）指向队尾元素,

要从线性农中删除」个元素，首先将要删除 队尾指针总是指向最后被插入的元索；允许删 除的

-?端称为排头（也称为队头），通常也用一 个排元素的前后件两个指针断开，然后把要删除结点 的

前件的指针，指向删除结点后的数据元索。 头指针（front）指向排头元素的前一个位 So

（2） 循环队列及其运算

队列的顺用存储结构-?般采用循环队列 的形

式。所谓的循环队列，就是将队列的存储 空间的最后一个位買绕到第一个位買，形成逻 辑上的环状空间，供队列循环使用。

① 入队运算。入队运算是指在循坏队列的 队尾加入一个新元素。这个运算有两个基木操 作：首先将队尾指针进一（即rear=rera+l）,并 当

rear-〃汁1时置rcar-1；然后将新元素插入到 队尾指针指向的位置。②退队运算。退队运算是 指在循环队列的排头位呂退出一个元素并赋值给 指定的变呈。这个运算冇两个皋本操作：首先将 III-头指针进一（即front=fiont4-1 ）,并当 fi*ont=〃rH时览front=l；然片将^头指针指向的 元素賦给指宦的变量。

考点5线性链表

1. 线性链表

（1）线性链表

2 ?循环链表

循坏链表与单链表唯-?的不同，就是最厉 一个结点的指针域中的值不同。单链表的最后 一个结点的指针域存放的是一个空指针，而循 环链表的最后一个结点的指针域存放的是指向 第个结点的指针。 考点6树与二叉树

1. 树的基本概念

树是一种比较简单的非线型结构。在树中所 冇的数据元素Z间具冇明显的层次关系。Z所以 将这种数据结构命名为\树”,是因为其结构 看上去像一棵倒长着的树。在树的图形表示中. 上端的结点是前件，下端的结点是厉件。

2. 二叉树及基本性质

（I）二叉树

二叉树是一种特殊的树，是一种很冇用的非 线型结构。所冇树结构上的术语都可以川在二义 树上。二叉树具有以卜'两个特征：①非空二叉树只 有一个根结点；②每个结点最多有两棵子树，

线性表的链式〃储结构称为线性链表。在 线性链表中，存储空间上的每一个存储结点都 要分成

几分别称为该结点的左子树和右子树。在二.义树 左子树：③前序遍历右子树。

（2） 中序遍历（LDR） 中，每个结点的度最大为2,所有的左子树和右 子树

首先遍历左子树，然后访问根结点，最后遍 历也均是二叉树。同时，在二叉树中所有的结 点可以

没冇左子树，也可以没冇右子树。即没冇 左子树又右子树：在遍历左、右子树时?也按上述的顺 序执

行。可见中序遍历二叉树也是…个递归的过 程。对没有右子树的结点是叶子结点。

于二叉树的中序遍历,具有的规则:①对 于空的二叉（2）满二叉树

树，不进行操作返回空值。②对于非 空的二义树的

所谓满二叉树足指：除扱后一层外，每一层 上

遍历按下列顺序执行：中序遍历左 子树；访问根结

的所有结点都有两个子结点。这就是说■在满 二义

点；中序遍历右子树°

树中，每一层上的结点数都达到赧大值，即 满二叉

（3） 后序遍历＜LRD）

树的第k层上有 步 个结点，且深度为m 的满二叉

首先遍历左子树,然后遍历右子树,最后 访问根m

树冇2-l个结点。

结点；在遍历左、右子树时，也按上述 的顺序执行。

（3〉完全二叉树

可见片序遍历二叉树同样也是一 个递归的过程。对

所谓的完全二叉树是指：除最后一层外， 侮

于二叉树的后序遍场，具有 的规则：①对于空的二

一层上的结点数均达到最大值，最后一层上 只缺少

叉树，不进行操作返回 空值。②对于非空的二叉树

右边的若干个结点。

的遍历按下列顺序 执行：后序遍历左子树；后序遍

完全二叉树就是去抻城后一层若干个右 边结

历右子树；访 问根结点。

点的满二叉树。

考点7查找技术

（4）二叉树的基本性质

査找就是从给定的一个数据结构中，找出指

① 二叉树的基本性质。二叉树具冇以下几 个

定的数据元索。木节中我们只学习对线性表的查找.

基本性质：性质1：在二叉树的第K层上最 多有2“ （^1）

常用的査找方法冇顺序査找和分法査找。

个结点。性质2：深度为m 的二叉树垃多有2叫1个

结点。性质3：在任意 -棵一??义树中，叶子结点1 ?顺序査找

顺序査找的过程是：从线性表的第一个元索 （即度为0的结点），总 比度为2的结点名一个。

性质4：具有\个结点 的二叉树，其深度至少为开始，依次将线性农中的数据与要查找的数掘进 行

比较，如果找到了相等的数据，则査找成功， 停止[log2/:]+lfl

② 完全二叉树的两项特性。完全二叉树还 具向下査找；如果比较完了线性表中的所有数 据元有以下两项特性：性质5：具有〃个结点的 完全二素，没有找到相等的数据，则查找失败。 叉树，其深度为[log2n]+l。性质6：设 完全二叉树共2. 二分法查找 冇〃个结点。如果从根结点开始， 按层序（每一层2分矗杳找又称为折半查找，只能应用于 顺序存从左到右）用口然数 储的冇序表。冇序表是指线性表中的元 素已经按值2给结点进行编号。 非递减（从整体上看趕升序，但相 邻的元素的值可3. 二叉树的遍历 以相同〉排列。

三叉树的遍丿力是指按照一定的顺序访问 二叉考点8排序技术 树中的结点，每个结点只被访问一次。为 了保证所排序就是将一组无序的数据按照一定的顺 序排有结点彼不重不漏地访问?必须按照 一定的顺序进列起来。本节中所指的顺序是非递减顺序 （整体上行。 呈升序,但相邻的数据可以相等）,基 本排序算法主

（1）前序遍历（DLR） 要有交换类排序.插入类排序和 选择类排序3大类。 首先访问根结点，然厉遍历左子树，最斤遍 1. 交换类排序 历右子树；在遍历左.右子树时，也按I谜的顺序 交换排序就是借助数据元索之间的互相交 换进执行。可见前序遍历二叉树是…个递川的过和 对于 行排序的方法。常用的交换推序方法有冒 泡排序和二叉树的前序遍历，具有如下的规则：对于空的 二快速排序。 叉树，不进行操作返回空值。对于非空的二叉 树的（1）冒泡排序 遍〃j按下列顺序执彳f：伽问根结点； ②前序遍历诃泡排序的过程简单，它的基本思想是通