全国计算机二级C语言(完整复习资料)#高等教育

1、计算机二级审核材料公共基础知识信息第1章数据结构和算法测试站点1算法的基本概念算法：指的是一组糟糕的指令集，是对解决方案的准确而完整的描述。算法不等于程序，也不等于计算方法。该算法的基本特征是：确定性，算法中的每一步都必须明确定义，不允许有歧义；由于性能较差，该算法必须能够在有限的时间内完成，也就是说，它可以在执行有限的步骤后终止。可行性，算法原则上可以准确执行；有足够的信息。算法元素：算法由两部分组成：数据对象的操作和操作及其控制结构。算法的基本操作和运算：算术运算、逻辑运算、关系运算、数据传输。该算法的基本控制结构是顺序、选择和循环。算法的基本设计方法包括枚举法、归纳法、递归法、递归法和减

2、半递归法。测试站点2算法的复杂性算法效率复杂度的度量：时间复杂度和空间复杂度。算法的时间复杂度：指执行算法所需的计算工作量。通常，算法使用的时间包括编译时间和运行时间。算法空间的复杂性：指执行该算法所需的内存空间。包括算法程序占用的空间、输入初始数据占用的空间以及算法执行过程中所需的额外空间。空间复杂性与时间复杂性无关。测试站点3数据结构的基本概念数据：数据是客观事物的象征性表现。它是可以输入计算机并被计算机程序识别和处理的符号的总称，如文件、声音、视频等。数据元素：数据元素是数据的基本单位。数据对象：数据对象是具有相同属性的数据元素的集合。数据结构：指由数据对象中所有数据成员之间的关系组成的

3、集合。测试站点4逻辑结构和存储结构数据结构可以分为数据的逻辑结构和存储结构。数据的逻辑结构是对数据元素之间逻辑关系的描述，独立于数据存储，面向问题，独立于计算机。它包括数据对象和数据对象之间的关系。数据的存储结构也称为数据的物理结构。它是计算机中数据的存储方法，是面向计算机的。它包括数据元素的存储方法和关系的存储方法。数据结构和逻辑结构的关系：数据的逻辑结构可以表示为多种存储结构，即数据的逻辑结构和存储结构不一定一一对应。常见的存储结构有：顺序、链接、索引等。不同存储结构的数据处理效率不同。测试点5线性结构和非线性结构线性结构(非空数据结构)的条件：(1)只有一个根节点；(2)每个节点最多有一

4、个前片和一个后片。非线性结构：不符合线性结构条件的数据结构。堆栈、队列和双链表是线性结构，而树和二叉树是非线性结构。测试站点6线性表及其顺序存储结构线性表由一组数据元素组成。数据元素的位置只取决于它们的序列号。元素之间的相对位置是线性的。在复杂的线性表中，由几项数据元素组成的数据元素称为记录。由多条记录组成的线性表称为文件。非零线性表的结构特征；(1)只有一个根节点a1，没有前件；(2)只有一个终端节点an，没有背板；(3)除了根节点和终端节点之外，所有其他节点都有且只有一个前部件，并且也有且只有一个后部件。节点数n称为线性表的长度，当n=0时，称为空表。线性表的顺序存储结构具有以下两个基本特

5、征：(1)线性表中所有元素占用的存储空间是连续的；(2)线性表中的每个数据元素以逻辑顺序存储在存储空间中。元素ai的存储地址是：ADR(ai)=ADR(a1) (i-1)*k，ADR(a1)是第一个元素的地址序列表的操作：查找、插入和删除。测试站点7线性链表线性链表是线性表的链式存储结构。数据结构中的每个节点对应一个存储单元。这个存储单元称为存储节点，简称节点。节点由两部分组成：(1)用于存储数据元素值，称为数据字段；(2)它用于存储指针，称为指针字段，并用于指向上一个或下一个节点。在链式存储结构中，存储数据结构的存储空间可以是不连续的，每个数据节点的存储顺序可以与数据元素之间的逻辑关系不一致

6、，数据元素之间的逻辑关系由指针字段决定。链式存储可以用来表示线性和非线性结构。在线性单链表中，头称为头指针，头=空(或0)称为空表。图1单链表的结构单链表的结构(图1)数据字段指针字段数据字段指针字段数据字段指针字段双向链表有两个指针：左指针(Llink)指向前节点，右指针(Rlink)指向后节点。研发中心图2双链表的结构研发中心研发中心循环链表：循环链表和单一链表的区别在于最后一个节点的指针字段指向第一个节点的指针，而单一链表存储空指针。图3循环链表的结构线性链表的基本操作：搜索、插入和删除。堆1.堆栈的基本概念堆栈是一个特殊的线性表，它只允许在表的一端插入和删除。插入，删除栈顶的一端，栈底

7、的另一端；当表中没有元素时清空堆栈。堆栈是后进先出(或后进先出)的线性表。堆栈具有存储功能。堆栈示例：列车调度、子弹夹。2.堆栈的存储结构顺序存储结构：一维阵列用于存储一组具有连续地址的存储单元；链式存储：使用线性链表存储；3.堆栈的基本操作(1)堆栈操作，在堆栈顶部插入元素；(2)去堆栈操作，删除元素(取出堆栈的顶部元素并将其分配给指定的变量)；(3)读取栈顶元素，将栈顶元素分配给指定的变量，此时指针不变。测试站点9队列1.队列的基本概念队列是一种特殊的线性表，只允许在表的一端插入，在另一端删除。允许插入的一端是后面，允许删除的一端是前面。当表中没有元素是空队列时；队列是先进先出的线性表。(

8、先进先出)2.队列的存储结构顺序存储：一维阵列。线性链表。3.排队操作：(1)队列操作：从队列末尾插入一个元素；(2)退出计算：从团队负责人中删除一个元素。队列的顺序存储结构一般采用循环队列的形式。循环队列s=0表示队列为空；S=1，front=reason表示团队已满。计算循环队列中的元素数量：“尾部指针减去头部指针”。如果是负数，增加它的容量。测试场地10树木的基本概念树是一种非线性结构，是n个节点的有限集合。n=0时为空树，n0时为非空树。节点度：节点拥有的子树数。叶节点：0度节点。分支节点：除叶节点以外的节点。节点层：根节点在第一层，同一层的左节点和右节点的子节点在下一层。树的深度：具

9、有最高级别的节点的级别。树的度：树中所有节点的度的最大值。测试站点11二叉树及其基本属性1.二叉树的概念二叉树是一种特殊的树形结构，每个节点最多有两个子树，左右部分不能交换。因此，二叉树有五种不同的形式，见教科书第12页。2.二叉树的性质性质1在二叉树的K级上，最多有2k-1个(k1)节点。属性2深度为m的二叉树最多有2m-1个节点。属性3在任何二叉树中，度为0的节点(叶节点)总是比度为2的节点多一个。性质4是具有n个节点的二叉树，其深度不小于log2n 1，其中log2n表示为log2n的整数部分。3.二叉树的存储结构：详见教科书第13-14页。测试站点12全二叉树和全二叉树全二叉树：除了最

10、后一层，每层的所有节点都有两个子节点。在全二叉树中，每层上的节点数达到最大，即在全二叉树的第k层上有2k-1个节点，在深度为m的全二叉树上有2m-1个节点完全二叉树是指除最后一层之外，每一层的节点数达到最大的二叉树。最后一层只有右边的几个节点缺失。完整的二叉树是完整的二叉树，而完整的二叉树通常不是完整的二叉树。测试站点13完整二叉树的属性性质1具有n个节点的完全二叉树的深度是log2n 1。在属性2的完全二叉树中，度为1的节点数为0或1。ABCEDGFH图4二叉树的遍历测试站点14二叉树的遍历先序遍历：首先访问根节点，然后遍历左子树，最后遍历右子树；此外，当遍历左和右子树时，仍然首先访问根节点

11、，然后遍历左子树，最后遍历右子树。前导码遍历图5以获得ABCDFHEG。有序遍历：首先遍历左子树，然后访问根节点，最后遍历右子树；此外，当遍历左和右子树时，仍然首先遍历左子树，然后访问根节点，最后遍历右子树。中间序列遍历图5以获得：BAFHDCGE。后顺序遍历：首先遍历左子树，然后遍历右子树，最后访问根节点；此外，当遍历左和右子树时，仍然首先遍历左子树，然后遍历右子树，最后访问根节点。以下序列遍历图5以获得：BHFDGECA。测试站点15顺序搜索顺序查找从表的一端开始，依次扫描表中的每个元素，并将其与要找到的数字进行比较。您只能在以下两种情况下使用顺序搜索：(1)如果线性表是无序表，无论是顺序

12、存储结构还是链式存储结构，都只能使用顺序搜索。(2)即使对于有序线性表，如果采用链式存储结构，也只能使用顺序搜索。测试站点16两点搜索二进制搜索的条件是：(1)顺序存储结构(2)线性表是有序表。寻找步骤：详见教科书第16页。对于长度为n的有序线性表，在最坏的情况下，二分法搜索只需要比较log2n次，而顺序搜索需要比较n次。测试地点17分类1.交换排序(1)气泡分选法。在最坏的情况下，气泡排序所需的比较次数是n (n-1)/2。(2)快速排序法。在最坏的情况下，快速排序所需的比较次数是n (n-1)/2。2、插入类排序方法：(1)简单的插入排序方法，最坏的情况需要n(n-1)/2次比较；(2)希

13、尔排序法，最坏的情况需要O(n1.5)比较。(大写的0表示算法的复杂性)3、选择排序方法：(1)简单选择排序方法，最坏的情况需要n(n-1)/2次比较；(2)堆排序方法，最坏的情况需要O(nlog2n)比较。与上述方法相比(希尔排序法除外)，堆排序法的时间复杂度最小。第二章程序设计的基础测试站点1编程方法和风格应该注意形成一个好的编程风格：(详见教科书第19页)。1、源程序文档；2.数据描述方法；3.句子结构；4.输入和输出。评论分为前言评论和功能评论。句子结构清晰是第一位的，效率是第二位的。测试站点2结构化编程方法的四个原则1.自上而下；2、逐步完善；3.模块化；4.限制goto语句的使用。

14、测试站点3结构化程序的基本结构序列结构：它是最基本、最常见的结构形式。它是根据程序中语句行的顺序逐个执行的。选择结构：也称为分支结构，它包括简单选择和多分支选择结构。循环结构：根据给定的条件，判断是否重复执行相同或相似的程序段。循环结构对应于两种类型的循环语句：首先判断然后执行的循环体称为等价循环结构；执行此操作的循环结构面向对象编程以对象为核心，强调对象的抽象、封装、继承和多态。面向对象方法的优势(1)人类思维方法的习惯是一致的；(2)稳定性好；(3)可重用性好；(4)易于开发大型软件产品；(5)良好的可维护性。测试站点5对象及其特征对象：面向对象方法中最基本的概念，它可以用来表示客观世界中

15、的任何实体。对象是实体的抽象。对象的基本特征：(1)身份的唯一性；(2)分类；(3)多态性；(4)封装；(5)模块独立性好。测试站点6属性、类和实例属性：即对象中包含的信息。它是在设计对象时确定的。通常，它只能通过执行对象的操作来更改。类：具有相似属性和操作的一组对象。类是对对象本质的描述。类是对象的抽象，对象是其相应类的实例。测试站点7新闻及其构成消息：信息在一个实例和另一个实例之间传递。对象之间的通信依赖于消息传递。它要求一个对象执行某个过程或回答某个需要的信息。它统一了数据流和控制流。消息的组成包括：(1)接收消息的对象的名称；(2)消息标识符，也称为消息名；(3)零个或多个参数。测试位

16、点8遗传和多态性继承：这是一种定义技术，它使用现有的类定义作为建立新类的基础。广义地说，它可以直接获得现有的属性和特性，而无需重复定义它们。继承是可传递的，一个类实际上继承了它上面所有基类的特征。继承分为单一继承和多重继承。单一继承意味着一个类只允许有一个父类，即类级别是树形结构；多重继承意味着一个类可以有多个父类。多态性：指同一消息被不同的对象接受时会导致完全不同的行为的现象。第三章软件工程基础测试站点1软件定义和软件特性软件是指计算机系统中与硬件相互依赖的另一部分，包括一整套程序、数据和相关文档。名字形容程序软件开发人员根据用户要求开发的一系列指令，用编程语言描述，适合计算机执行。数据一种使程序能够正常操作信息的数据结构。文档与程序的开发、维护和使用相关的图形材料软件的特性：软件是一个具有抽象性的逻辑实体。软件的生产不同于硬件的生产。它没有明显的生产过程。该软件在运行和使用过程中没有磨损和老化问题。软件的开发和运行依赖于计算机系统并受其限制，这就导致了软件移植的问题。该软件复杂度高，成本高。软件开发涉及许多社会因素。根据不同的应用目标，软件可分为应用软件、系统软件和支持软件(或工具软件)。名字形容应用软件为解决特定领域的应用而开发的软件，如办公自动化