计算机二级考试C语言资料 全

1、目录国家计算机等级考试二级公共基础知识辅导讲义1第1章数据结构和算法1第二章编程基础7第3章软件工程基础9第4章数据库设计的基础16第1章数据结构和算法1.1算法1.算法是指对解决方案的准确而完整的描述。换句话说，算法是对解决特定问题的步骤的描述。*:算法不等于程序或计算方法。编程不可能比算法设计更好。这是因为，在编程时，它受到计算机系统运行环境的限制，并且程序通常不得不考虑许多与方法和分析无关的细节。2.算法的基本特征(1)可行性。针对实际问题设计的算法实施后可以得到满意的结果。(2)确定性。每条指令的含义都是清晰明确的。在任何情况下，算法只有一条执行路径，即相同的输入只能产生相同的输出。(

2、3)贫穷。该算法必须在有限的时间内完成。有两个含义，一个是算法中的操作步骤有限，另一个是每一步都可以在有限的时间内完成。(四)信息充分。在该算法中，所有类型的运算总是必须应用于所有操作数，并且这些操作数可能具有一些初始状态，这是算法执行的起点或基础。因此，算法的结果总是与输入的初始数据相关，不同的输入会产生不同的结果。当输入不足或错误时，算法不会被执行或执行错误。一般来说，当它有足够的智能时，这个算法是有效的。当提供的信息不够时，算法可能无效。*:总而言之，所谓的算法是一组严格定义操作顺序的规则，每个规则都是有效和清晰的，并且这个顺序将在有限的次数内终止。3.算法复杂度主要包括时间复杂度和空间

3、复杂度。(1)算法时间复杂度是指执行算法所需的计算工作量，可以通过执行算法所需的基本操作数来衡量。(2)算法空间复杂度是指执行该算法所需的内存空间。1.2数据结构的基本概念1.数据结构是指相互关联的数据元素的集合。2.数据结构主要研究和讨论以下三个方面：(1)数据集中数据元素之间的内在逻辑关系，即数据的逻辑结构。数据的逻辑结构包括：1)表示数据元素的信息；2)表示数据元素之间的上下文关系：一般来说，在具有相同特征的数据元素集合中，数据元素之间存在一定的关系(即连接)，这反映了集合中数据元素的固有结构。在数据处理领域，数据元素之间的这种内在关系通常简单地用先行关系来描述(即，直接前置关系和直接后

4、续关系)。(2)处理数据时，计算机中各数据元素的存储关系，即数据的存储结构。数据的存储结构包括序列、链接、索引等。1)顺序存储。它将逻辑上相邻的节点存储在物理上相邻的存储单元中，节点之间的逻辑关系通过存储单元的相邻性来体现。产生的存储表示称为顺序存储结构。2)链接存储。它不要求逻辑上相邻的节点在物理上相邻，节点之间的逻辑关系由一个附加的指针字段表示。产生的存储表示称为链式存储结构。3)索引存储：除了存储节点信息，还建立一个附加的索引表来标识节点的地址。*:数据的逻辑结构反映了数据元素之间的逻辑关系，数据的存储结构(也称为数据的物理结构)是数据在计算机存储空间中的逻辑结构的存储形式。逻辑结构相同

5、的数据可以采用不同的存储结构，但会影响数据处理效率。(3)对各种数据结构的操作。3.数据结构的图形表示一个数据结构不仅可以用二元关系表示，还可以用图形直观地表示。在数据结构的图形表示中，数据集D中的每一个数据元素都用一个中间标有元素值的方框来表示，这个方框一般称为数据节点，简称为节点；为了进一步表示数据元素之间的先行关系，对于关系R中的每个二进制，使用有向线段从先行节点指向后续节点。4.数据结构可以分为两种类型：线性结构和非线性结构。(1)线性结构(非空数据结构)条件：1)数据结构中只有一个根节点，没有前因的节点称为根节点。；2)每个节点最多有一个前部和一个后部。*:常见的线性结构包括线性表、

6、堆栈、队列和线性链表。(2)非线性结构：不满足线性结构条件的数据结构。*:常见的非线性结构包括树、二叉树和图。1.3线性表及其顺序存储结构1.线性表由一组数据元素组成，这些数据元素的位置仅取决于它们自己的序列号，并且这些元素之间的相对位置是线性的。线性表是由n(n0)个数据元素组成的有限序列。除了第一个，表中的每个数据元素只有一个前件，除了最后一个，只有一个后件。线性表中数据元素的数量称为线性表的长度。线性表可以是空表。*:线性表是一种存储结构，它的存储方法是顺序和链式的。2.线性表的顺序存储结构有两个基本特征：(1)线性表中所有元素占用的存储空间是连续的；(2)线性表中的每个数据元素以逻辑顺

7、序存储在存储空间中。*:由此可见，在线性表的顺序存储结构中，前、后元素在存储空间中是相邻的，前元素必须存储在后元素的前面，因此第I个节点的存储地址可以由计算机直接确定。3.插入和删除序列表(学习独家手稿)(1)序列表的插入操作：一般来说，要在第i(1in)个元素之前插入一个新元素，必须从最后一个(即第n个)元素开始，直到总共n-i个元素依次向后移动一个位置。在移动之后，第I个位置被空出，然后新元素被插入到第I个项目中。插入后，线性表格的长度增加1。*:插入符合性表时需要移动元素。在同等概率下，平均需要移动n/2个元素。(2)顺序表的删除操作：一般来说，要删除第i(1in)个元素，必须从第i(1

8、)个元素开始，直到第n (n)个元素依次向前移动一个位置。删除后，线性表的长度减少1。*:删除符合性表时需要移动元素，在概率相等的情况下，平均需要移动(n-1)/2个元素。插入和删除操作不方便。1.4堆栈和队列1.堆栈及其基本操作堆栈是一个线性表，仅限于一端的插入和删除操作。在堆栈中，允许插入和删除的一端称为堆栈的顶部，不允许插入和删除的另一端称为堆栈的底部。顶部元素始终是最后插入的元素，底部元素始终是第一个插入的元素。也就是说，堆栈根据“先进先出”或“后进先出”的原则组织数据。堆栈具有存储功能。堆栈的基本操作：1)插入元素称为堆栈操作；2)删除元素被称为堆栈回操作；3)读取栈顶元素就是将栈顶

9、元素分配给一个指定的变量，此时指针不变。堆栈以两种方式存储，即顺序堆栈和链式堆栈，类似于线性表。2.队列及其基本操作队列是指一个线性表，允许在一端(队列的末端)插入，在另一端(队列的头部)删除。后指针指向队列末尾的元素，前指针指向队列首元素的前一个位置。队列是“先进先出”或“后进先出”的线性表。队列操作包括：1)队列操作：从队列末尾插入一个元素；2)退出队列：从队列头删除一个元素。循环队列及其操作：所谓的循环队列将队列存储空间的最后一个位置包裹在第一个位置周围，形成一个逻辑环形空间供队列循环使用。在循环队列中，尾部指针后部用于指向队列中的尾部元素，头部指针前部用于指向头部元素的前一个位置。因此

10、，所有元素都在队列中，从头指针前面的位置到尾指针后面的位置。*:循环队列中的元素数量=前后。1.5线性链表(学习、学习、独家稿件)1.线性表格顺序存储的缺点(向独家稿件学习):(1)插入或删除的操作效率很低。在顺序存储的线性表中，插入或删除数据元素时需要移动大量的数据元素；(2)在线性表的顺序存储结构下，线性表的存储空间不便于扩展；(3)线性表的顺序存储结构不利于存储空间的动态分配。2.线性链表：线性表的链式存储结构称为线性链表，它是物理存储单元上不连续、不连续的存储结构，数据元素的逻辑顺序是通过链表中指针的链接来实现的。因此，在链存储模式中，每个节点由两部分组成：一部分用于存储数据元素的值，

11、称为数据字段；另一部分用于存储指针，称为指针字段，用于指向该节点的前一个或后一个节点(即前一个或后一个)，如下图所示：线性链表分为三种类型：单链表、双链表和循环链表。在单个链表中，每个节点只有一个指针字段，这个指针只能找到它的后继节点，而不能找到它的前一个节点。因此，在某些应用程序中，为线性链表中的每个节点设置了两个指针，一个称为左指针，指向它的前一个节点；另一个称为右指针，它指向它的下属节点。该链表称为双链表，如下图所示：3.线性链表的基本运算(1)在线性链表中包含指定元素的节点前插入一个新元素。*:在线性链表中插入元素时，不需要移动数据元素，只需要修改相关的节点指针，不会溢出。为线性表分配

12、顺序存储结构后，如果线性表的存储空间已满，但需要插入新元素，则会发生溢出。“现象(学习，学习，独家稿件)。(2)删除线性链表中包含指定元素的节点。*:删除线性链表中的元素时，不需要移动数据元素，只需要修改相关的节点指针。(3)根据需要将两个线性链表合并成一个线性链表。(4)根据需要分解线性链表。(5)反转线性链表。(6)复制线性链表。(7)线性链表的排序。(8)搜索线性链表。*:线性链表不能在链表中随机访问。即使您知道被访问节点的序列号1，也不能像序列表中那样根据序列号1直接访问该节点。相反，您只能从链表的头指针开始，一个接一个地搜索链域，直到找到ith节点。因此，链表不是随机存储结构。4.循

13、环链表及其基本操作在线性链表中，虽然插入和删除都很方便，但仍然存在一个问题。在操作过程中，空表和第一个节点必须分开考虑，这使得空表和非空表的操作不一致。为了克服线性链表的这一缺点，我们可以采用另一种链接方式，即循环链表。与上述线性链表相比，循环链表具有以下两个特点：1)链表中增加了一个头节点，其数据字段是任意的或根据需要设置的，指针字段指向线性链表第一个元素的节点，循环链表的头指针指向头节点；2)循环链表中最后一个节点的指针字段不是空的，而是指向头节点。也就是说，在循环链表中，所有节点的指针形成一个循环下图a是非空循环链表，图b是空循环链表：循环链表的优点主要体现在两个方面：第一，在循环链表中

14、，你可以通过指出表中任何一个节点的位置来访问表中的所有其他节点，但是线性单链表不能做到这一点；第二，由于在循环链表中设置了一个头节点，所以在任何情况下循环链表中至少存在一个节点，从而统一了空表和非空表的操作。*:循环链表在单链表的基础上增加一个头节点，其插入和删除操作与单链表相同。但是，它可以从任何节点访问表中的所有其他节点，实现空表和非空表操作的统一。1.6树和二叉树(学习，学习，独家稿件)1、树的基本概念树是一个简单的非线性结构。在树的数据结构中，所有数据元素之间的关系具有明显的层次特征。在树形结构中，每个节点只有一个前身，称为父节点。只有一个没有先行词的节点，称为树的根节点。每个节点可以

15、有多个后件，这些后件被称为节点的子节点。没有后缀的节点称为叶节点。在树形结构中，一个节点所拥有的后继数称为该节点的度，所有节点的最大度称为该树的度。树的最大高度叫做树的深度。2.二叉树及其基本性质(1)什么是二叉树二叉树是一种有用的非线性结构，它有以下两个特点：1)非空二叉树只有一个根节点；2)每个节点最多有两个子树，分别称为节点的左子树和右子树。*:根据二叉树的概念，二叉树的度数可以是0(叶节点)、1(只有一个子树)或2(有两个子树)。(2)二叉树的基本性质(学习和学习专用手稿)属性1位于二叉树的第k级，最多有个节点。属性2中深度为m的二叉树最多有个节点。属性3在任何二叉树中，度为0的节点(

16、即叶节点)总是比度为2的节点多一个。属性4是一个有n个节点的二叉树，其深度至少为，取整数部分。3.全二叉树和全二叉树全二叉树：除最后一级外，每一级的所有节点都有两个子节点。完整二叉树：除最后一层外，每层节点数达到最大值；在最后一层，只有右边的几个节点丢失了。*:根据完全二叉树的定义，1度的节点数为0或1。下图a显示了完整的二叉树，下图b显示了完整的二叉树：完整的二叉树也有以下两个特点：财产5。有n个节点的完整二叉树的深度是。在属性6中，假设在完整的二叉树中有n个节点。如果根据从根节点开始的顺序(从每层的左到右)，用自然数1，2，n对节点进行编号，则对于编号为k(k=1，2，n)的节点可以得出以

17、下结论：(1)如果k=1，则该节点是根节点，并且它没有父节点；如果为k1，则该节点的父节点数为INT(k/2)。(2)如果2kn，编号为k的左子节点是2k；否则，该节点没有左子节点(显然，它也没有右子节点)。如果2k 1n，编号为k的右子节点为2k1否则，该节点没有正确的子节点。4.二叉树的存储结构在计算机中，二叉树通常采用链式存储结构。与线性链表相似，用于存储二叉树中每个元素的存储节点也由两部分组成：数据字段和指针字段。然而，在二叉树中，因为每个元素可以有两个后缀(即两个子节点)，所以有两个指针字段用于存储二叉树的存储节点：一个是指向节点的左子节点的存储地址，称为左指针字段；用于指向该节点的右子节点的另一个存储地址称为右指针字段。*:一般二叉树通常采用链式存储结构。对于全二叉树和全二叉树，可以按顺序存储，不仅节省了存储空间，而