二级C语言公共基础知识

1、公共基金会根据国家计算机等级考试大纲，各类笔试除了70分程序设计相关知识外，还应具备30分公共基础知识，包括基本数据结构与算法、程序设计基础、软件工程基础和数据设计基础。本章将介绍这些基础知识。1.1数据结构和算法1.1.1算法这一部分着重于掌握算法的基本概念和典型算法的时间复杂度。1.基本测试站点1)算法的基本概念算法：指对解决方案的准确和完整的描述。算法不等于程序或计算机方法，所以程序不能比算法的设计更好。该算法的基本特征是：它是一组严格定义操作顺序的规则，每个规则都是有效和清晰的，并且这个顺序将在有限的次数内终止。功能包括：(1)可行性：通过执行有限次数实现的基本操作来完成；(2)确定性

2、：算法中的每一步都必须明确定义，不允许有歧义的解释和多义性；(3)不确定性：算法必须在有限的时间内完成，也就是说，它可以在执行有限的步骤后终止，包括合理执行时间的含义；(四)有足够的信息。算法的基本要素：第一，数据对象的计算和操作；第二是算法的控制结构。基本运算包括算术运算、逻辑运算、关系运算和数据传输。算法的控制结构：顺序结构、选择结构和循环结构。算法的基本设计方法：枚举法、归纳法、递归法、递归法、半递归法和回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度：是指执行算法所需的计算工作量。一般来说，一个算法的工作量是由它执行的基本操作的数量来衡量的，它执行的基本操作的数量是问

3、题大小的函数，用O(f(n)来表示。在相同的问题规模下，平均行为和最坏情况的复杂性被用来分析它。一般来说，最坏情况下的复杂性用于分析算法的时间复杂性。算法空间复杂度是指执行该算法所需的内存空间。2)搜索算法顺序搜索的用法：(1)线性表是无序表(无论是顺序存储结构还是链式存储结构)；(2)表格采用链式存储结构(即使是有序的线性表格)。二分搜索法仅适用于按顺序存储的有序表。对于长度为n的有序线性表，最坏情况下二分搜索法只需要比较log2n次，顺序搜索需要比较n次。3)排序算法排序是指将一个无序的序列按值的非递减顺序排列成有序的序列。(1)交换类排序方法：假设线性表的长度为n气泡排序法：在最坏的情况

4、下，比较的次数是n(n-1)/2；快速排序法：在最坏的情况下，比较的次数是n(n-1)/2(2)插入类排序方法：简单的插入排序法，最坏的情况需要n(n-1)/2次比较；希尔的排序方法要求在最坏的情况下进行n1.5)比较。(3)选择一种分类方法：只需选择排序方法，最差情况需要n(n-1)/2次比较；在最坏的情况下，堆排序需要进行O(nlog2n)比较。2.重要测试地点的详细说明(1)对于长度为n的线性表，在最坏的情况下，对应于以下排序方法的正确比较次数是_ _ _ _ _。a)冒泡顺序为n/2 B)冒泡顺序为nc)快速排序为n D)快速排序为n(n-1)/2分析：国家二级考试涉及的排序算法(冒泡

5、排序法、快速排序法、简单插入排序法、希尔排序法、简单选择排序法、堆排序法)，只有“堆”排序和“希尔”排序不是n(n-1)/2，其他为n(n-1)/2。堆排序为O(nlog2n)，而山排序为O(n1.5)。(2)对于长度为n的线性表，最坏情况下所需的比较次数为_ _ _ _ _ _ _ _。a)对数2n B) n/2 C) n D) n 1分析：在最坏的情况下，你要寻找的元素在序列的最后或者不在序列中，所以比较所有的N个元素。(3)以下陈述正确为_ _ _ _ _。a)查找长度为n的链顺序表，在最坏的情况下，比较的次数为n。b)对长度为n的链顺序表进行二等分搜索，最差情况需要比较(n/2)。c)

6、对长度为n的链顺序表进行二等分搜索，最差情况需要比较(log2n)。d)对长度为n的链序表进行二等分搜索，最差情况需要比较(nlog2n)。解决方法：二分搜索法(二等分搜索)只能用于按顺序存储的有序表，因此只有A是正确的。(4)长度为10的线性表按冒泡排序，最差情况下需要的比较次数为45。分析：n(n-1)/2=10*9/2=451.1.2数据结构1.基本测试站点本节的主要内容是数据结构的三个要素：数据的逻辑关系、计算机中的存储关系以及与存储关系相对应的操作。堆栈和队列的数据结构(逻辑关系、存储关系、操作)。1)数据结构数据结构研究的三个方面：(1)数据集中数据元素之间的内在逻辑关系，即数据的

7、逻辑结构；(2)处理数据时，计算机中每个数据元素的存储关系，即数据的存储结构；(3)对各种数据结构的操作。数据结构是相互关联的数据元素的集合。数据结构是反映数据元素之间关系的数据元素集合的表示。数据的逻辑结构包括：(1)表示数据元素的信息；(2)表示数据元素之间的先行关系。(逻辑关系，与计算机中的存储位置无关)计算机存储空间中的数据结构中的每个数据元素的位置关系和逻辑关系可以不同。数据的存储结构是数据逻辑结构在计算机存储空间中的存储形式。常用的存储结构有：序列、链接、索引等。根据数据结构中数据元素之间先行关系的复杂性，数据结构一般分为线性结构和非线性结构。线性结构条件：(1)只有一个根节点；(

8、2)每个节点最多有一个前部和一个后部。非线性结构：不满足线性结构条件的数据结构。2)线性表及其顺序存储结构线性表由一组数据元素组成，这些数据元素的位置只取决于它们自己的序列号，元素之间的相对位置是线性的。例如：一个多维向量，矩阵在复杂的线性表中，由几个数据元素组成的数据元素称为记录，而由多个记录组成的线性表也称为文件。非空线性表的结构特征；线性表：a1，a2，an(1)只有一个没有先行词的根节点a1；(2)只有一个终端节点an，没有后继部分；(3)除了根节点和终端节点，所有其他节点只有一个前部和一个后部。节点数n称为线性表的长度，当n=0时，称为空表。线性表的顺序存储结构有以下两个基本特征：(

9、1)线性表中所有元素占用的存储空间是连续的；(2)线性表中的每个数据元素以逻辑顺序存储在存储空间中。ai的内存地址是ADR(ai)=ADR(a1) (i-1)k，ADR(a1)是第一个元素的地址，k代表每个元素占用的字节数。序列表操作：插入和删除。3)堆栈堆栈是一个特殊的线性表，它的一端仅限于插入和删除。允许插入和删除的一端称为堆栈顶部，不允许插入和删除的另一端称为堆栈底部。堆栈根据“FILO”或“LIFO”组织数据。堆栈具有存储功能。使用顶部作为堆栈的顶部，底部作为堆栈的底部。栈的顺序存储：一维数组S(1:m)作为栈的顺序存储空间，m是栈的最大容量。s(底部)是底部元素，s(顶部)是顶部元素

10、，top=0为空，top=m为满。堆栈的基本操作：(1)插入元素称为堆叠操作；(顶部=顶部1；在堆栈顶部指针所指向的位置插入一个新元素)，就会发生溢出。(2)删除元素被称为回栈操作；(将顶部指针指向的元素分配给指定的变量，top=top-1)，将发生下溢。(3)读取堆栈顶部元素是将堆栈顶部元素分配给指定的变量，此时指针没有变化。4)队列队列是一种特殊的线性表。队列是一个线性表，允许在一端(队列的末尾)插入，在另一端(队列的头)删除。后指针指向队列的末端，前指针指向队列的头部。队列是先进先出或后进先出的线性表。队列的顺序存储：与堆栈类似，一维数组Q (1: M)被用作队列的顺序存储空间队列操作：

11、(1)队列操作：从队列的末尾插入一个元素；(2)退出队列：从队列头删除一个元素。5)循环队列循环队列是一种队列，它是一种顺序存储结构。在循环队列结构中，当存储空间的最后一个位置已经被使用并且需要队列操作时，只要存储空间的第一个位置是空闲的，就可以将元素添加到第一个位置，即存储空间的第一个位置被用作队列尾部。从前端指针指向的最后一个位置到后端指针指向的位置，所有元素都在队列中。环形队列的初始状态为空：后=前=m。当环形队列已满时，后方=前方为了区分满队和空队，增加了符号S。S=0表示队列为空，s=1且前=后表示队列已满6)线性链表对于元素变化频繁的大型线性表，不应采用顺序存储结构，而应采用链式存

12、储结构。在链式存储结构中，数据结构中的每个节点对应一个存储单元，简称为存储节点。该节点由两部分组成：(1)用于存储数据元素值，称为数据字段；(2)用于存储指针，称为指针字段，用于指向前一个或下一个节点。在链式存储结构中，用于存储数据结构的存储空间可以是不连续的，并且每个数据节点的存储顺序可以与由指针字段确定的数据元素之间的逻辑关系不一致。链式存储可以用来表示线性和非线性结构。线性链表，HEAD称为头指针，HEAD=空(或0)称为空表。如果有两个指针，左指针(Llink)指向前一个节点，右指针(Rlink)指向后一个节点。线性链表的基本操作：搜索、插入和删除。2.重要测试地点的详细说明(1)数据

13、存储结构是指_ _ _ _ _ _ _ _ _。a)存储在外部存储器中的数据b)数据占用的存储空间量c)计算机中数据的顺序存储模式d)计算机中数据逻辑结构的表示分析：数据的存储结构是计算机中数据逻辑结构的表示。根据数据的逻辑关系和操作特点，可以采用顺序存储或链式存储。这些数据通常存储在内存中。(2)以下堆栈描述中的错误是_ _ _ _ _ _ _ _。a)堆栈是一个先进先出的线性表b)堆栈只能按顺序存储c)堆栈具有内存功能D)在堆栈的插入和删除过程中，不需要改变堆栈的底部指针分析：堆栈是一个特殊的线性表，可以按顺序或链存储，所以B是错误的；堆栈有一个内存函数，用来保存进程调用中的场景；堆栈上的

14、操作在堆栈的顶部执行，不需要改变堆栈底部的指针。(3)以下线性链表的描述正确为_ _ _ _ _ _ _ _。a)存储空间不一定是连续，且每个元素的存储顺序是任意的b)存储空间不一定是连续，且前一个元素必须存储在后一个元素之前c)存储空间必须是连续的，并且前置元素必须存储在后续元素的前面d)存储空间必须是连续的，每个元素的存储顺序是任意的分析：线性链表是线性表的链式存储结构，即数据逻辑上是线性的，存储结构是链式存储，存储空间不一定是连续的，每个元素的存储顺序是任意的。(5)下列陈述正确为_ _ _ _ _ _ _ _。a)一个逻辑数据结构只能有一个存储结构b)数据的逻辑结构属于线性结构，存储结

15、构属于非线性结构c)一个逻辑数据结构可以有多个存储结构，每个存储结构不影响数据处理的效率一个逻辑数据结构可以有多种存储结构，而多种存储结构会影响数据处理的效率分析：逻辑数据结构是逻辑中数据的线性或非线性结构，存储结构是计算机中逻辑结构的表示，可以是链式存储或顺序存储，所以A和B是错误的；在相同的逻辑结构和不同的存储结构下，数据的处理效率是不同的。例如，线性表可以按顺序或链式存储。当向线性表中插入或删除数据时，链式存储具有更高的处理效率。(6)按照“后进先出”原则组织的数据的数据结构是_ _ _ _ _ _ _ _。a)队列b)堆栈c)双链表d)二叉树分析：根据“后进先出”原则的数据结构是线性的

16、，所以d是错误的；双线性列表只是一种存储结构，并不反映其逻辑结构，所以在逻辑上不一定是线性结构，所以C错了。队列是“先进先出”的数据结构，所以a是错误的。(7)以下陈述正确为_ _ _ _ _ _ _ _。a)循环队列有两个指针，队列头和队列尾，因此循环队列具有非线性结构b)在循环队列中，只有头指针能够反映队列中元素的动态变化c)在循环队列中，只有尾部指针能够反映队列中元素的动态变化d)循环队列中的元素数量由头指针和尾指针决定分析：队列是线性结构，循环队列是队列的链式存储结构，所以它仍然是线性数据结构，所以A是错的。队列的特点是“先进先出”，入口在队列的末尾，出口在队列的头，所以队列中元素的动态变化依赖于头指针和尾指针。所以d是对的。(8)如果循环队列的容量为50，头指针前端=5(指向头元素的前一个位置)，尾指针后端=29(指向尾元素)，则循环队列中有24个元素。分析：可通过以下公式计算：|后-前最大|最大值=| 29-550 |最大值=241.1.3树和二叉树1.基本测试站点树是一种简单的非线性结构，所有元素都有明显的层次特征。DABCEFGiH在树结构中，每个节点只有一个前因，称为父节点，只有一个没有前因的节点，称为树的根节点。每个节点可以有多个post-pieces，它们被称为节点的子节点。没有后缀的节点称为叶节点。在树结构中，一个节点所拥有的余数称为节点的度