二级C语言公共基础知识

1公共基础全国计算机等级考试大纲要求，各种笔试除了要考70分的程序设计相关知识外，还要考30分的公共基础知识，包括基本数据结构与算法、程序设计基础、软件工程基础和数据设计基础。本章将介绍这些基础知识。1.1数据结构与算法1.1.1算法本节重点掌握算法的基本概念和典型算法的时间复杂度。1、基本考点1）算法基本概念算法：是指解题方案的准确而完整的描述。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：（1）可行性：通过已实现的基本运算执行有限次而完成；（2）确定性：算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（3）有穷性：算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度:指执行算法所需要的计算工作量。一般来说，算法的工作量用其执行的基本运算次数来度量，而算法执行的基本运算次数是问题规模的函数，用O（f(n)）表示。在同一个问题规模下，用平均性态和最坏情况复杂性来分析。一般情况下，用最坏情况复杂性来分析算法的时间复杂度。算法空间复杂度是指执行这个算法所需要的内存空间。2）查找算法顺序查找的使用情况：（1）线性表为无序表（不管是顺序存储结构还是链式存储结构）；（2）表采用链式存储结构（即使是有序线性表）。二分法查找只适用于顺序存储的有序表。对于长度为n的有序线性表，二分查找最坏情况只需比较log2n次，顺序查找需要比较n次。3）排序算法2排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。（1）交换类排序法：假设线性表的长度为n冒泡排序法：在最坏情况下，需要比较的次数为n(n-1)/2；快速排序法：在最坏情况下，需要比较的次数为n(n-1)/2（2）插入类排序法：简单插入排序法，最坏情况需要n(n-1)/2次比较；希尔排序法，最坏情况需要O(n1.5)次比较。（3）选择类排序法：简单选择排序法,最坏情况需要n(n-1)/2次比较；堆排序法，最坏情况需要O(nlog2n)次比较。2、重要考点详解(1)对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是______。A）冒泡排序为n/2B）冒泡排序为nC）快速排序为nD）快速排序为n(n-1)/2解析：国二级考试中涉及的排序算法（冒泡排序法、快速排序法、简单插入排序法、希尔排序法、简单选择排序、堆排序法），只有“堆”排序和“希尔”排序不是n(n-1)/2，其它都是n(n-1)/2。堆排序是O(nlog2n)，希尔排序是O(n1.5)。(2)对于长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为_______。A）log2nB）n/2C）nD）n+1解析：最坏的情况是要找的元素在最后一个或不在序列中，所以要把n个元都比较一下。(3)下列叙述中正确的是______。A）对长度为n的有链序表进行查找，最坏的情况需要比较次数为n。B）对长度为n的有链序表进行对分查找，最坏的情况需要比较次数为（n/2）。C）对长度为n的有链序表进行对分查找，最坏的情况需要比较次数为（log2n）。D）对长度为n的有链序表进行对分查找，最坏的情况需要比较次数为（nlog2n）。解析：二分查找（对分查找）只能用于顺序存储的有序表，所以只有A是对的。（4）对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为45。解析：n(n-1)/2=10*9/2=451.1.2数据结构1、基本考点本节主要内容是数据结构的三要素：数据的逻辑关系、在计算机中的存储关系、与存储关系对应的运算。栈、队列的数据结构（逻辑关系、存储关系、运算）。1）数据结构数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。数据结构是反映数据元素之间关系的数据元素集合的表示。3数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。（逻辑关系，与在计算机内的存储位置无关）一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系有可能不同。数据的存储结构是数据的逻辑结构在计算机存储空间中的存放形式。常用的存储结构有：顺序、链接、索引等。根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为：线性结构和非线性结构。线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。2）线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。如：一个N维向量、矩阵在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。非空线性表的结构特征：线性表：a1，a2，……an（1）有且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。顺序表的运算：插入、删除。3）栈栈是一种特殊的线性表，是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。栈的顺序存储：用一维数组S（1:m）作为栈的顺序存储空间，M为栈的最大容量。S(bottom)表示栈底元素，s(top)为栈顶元素，top=0表示栈空，top=m表示栈满。栈的基本运算：（1）插入元素称为入栈运算；（top=top+1;将新元素插入到栈顶指针指向的位置）,会出现上溢现象。（2）删除元素称为退栈运算；（将栈顶指针指向的元素赋给指定的变量，top=top-1），会出现下溢现象。（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。4）队列队列是一种特殊的线性表，队列是指允许在一端（队尾）进入插入，而在另一端（队头）4进行删除的线性表。Rear指针指向队尾，Front指针指向队头。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。队列的顺序存储：与栈类似，用一维数组Q（1：m）作为队列的顺序存储空间队列运算：（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。5）循环队列循环队列是队列是一种顺序存储结构，在循环队列结构中，当存储空间的最后一个位置已被使用而要进行入队运算时，只要存储空间的第一个位置空闲，就可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。从Front指针指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。循环队列的初始状态为空：rear=front=m当循环队列满时，rear=Front为区别队满还是队空，增加标志S。s=0表示队列空，s=1且front=rear表示队列满6）线性链表对于元素变动频繁的大线性表不宜采用顺序存储结构，而应采用链式存储结构。在链式存储结构中，数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。5在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。线性链表，HEAD称为头指针，HEAD=NULL（或0）称为空表，如果是两指针：左指针（Llink）指向前件结点，右指针（Rlink）指向后件结点。线性链表的基本运算：查找、插入、删除。2、重要考点详解(1)数据的存储结构是指_______。A）存储在外存中的数据B）数据所占的存储空间量C）数据在计算机中的顺序存储方式D）数据的逻辑结构在计算机中的表示解析：数据的存储结构是数据的逻辑结构在计算机中的表示，根据数据的逻辑关系和运算特点可以采取顺序存储或链式存储的方式，这些数据一般都是存储在内存中的。(2)下列关于栈的描述中错误的是_______。A）栈是先进后出的线性表B）栈只能顺序存储C）栈具有记忆作用D）对栈的插入与删除操作中，不需要改变栈底指针解析：栈是一种特殊的线性表，可以顺序存储，也可以用链式存储，所以B是错的；栈具有记忆作用，在过程的调用中就是利用这个功能，保存现场；对栈的操作都在栈顶上进行，不需要改变栈底的指针。(3)下列对于线性链表的描述中正确的是_______。A）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的解析：线性链表是线性表的链式存储结构，即数据在逻辑上是线性关系，在存储结构上是链式存储，存储有空间不一定连续，且各元素的存储顺序是任意的。（5）下列叙述中正确的是_______。）一个逻辑数据结构只能有一种存储结构）数据的逻辑结构属于线性结构，存储结构属于非线性结构）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率解析：逻辑数据结构是数据在逻辑上的线性或非线性结构，存储结构是逻辑结构在计算机中的表示，可以是链式存储，也可以顺序存储存，所以A、B是错的；同样的逻辑结构，储结构不同数据的处理效率也不同，如，线性表可以顺序存储，也可以链式存储，当向线性表中插入或删除数据时，链式存储的处理效率较高。(6)按照“后进先出”原则组织数据的数据结构是______。A）队列B）栈C）双向链表D）二叉树解析：按照“后进先出”原则的数据结构是线性结构，所以D不对；双向链表只是一种存储结构，并没有体现它的逻辑结构，所以在逻辑上不一定是线性结构，所以C不对。队列是“先进先出”的数据结构，所以A不对。（7）下列叙述中正确的是______。A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况6D）循环队列中元素的个数是由队头指针和队尾指针共同决定解析：队列是线性结构，循环队列是队列的链式存储结构，所以仍然是线性的数据结构，所以A是错的。队列的特点是“先进先出”，入队在队尾，出队在队头，所以队列中元素的动态变化取决于队头指针和队尾指针。所以D是对的。（8）设某循环队列的容量为50，头指针Front=5(指向队头元素的前一位置)，尾指针rear=29（指向队尾元素），则该循环队列中共有24个元素。解析：可以用公式进行计算：|rear-front+MAX|ModMAX＝|29-5+50|Mod50＝241.1.3树与二叉树1、基本考点树是一种简单的非线性结