全国级基础知识义.docVIP

全国二级C语言辅导班材料  NUMPAGES 25- PAGE 25 2011年11月 全国二级公共基础知识 从05年开始全国二级考试增设了公共基础知识，在理论考试中，分值30分，题型为选择10题，填空5题。 数据结构 时间选择题数填空题数总题数2005年4月5272005年9月3362006年4月4152006年9月3252007年4月4152007年9月4262008年4月3252008年9月415一、算法 1、算法的基本特征 （1）可行性。针对实际问题而设计的算法，执行后能够得到满意的结果。 （2）确定性。每一条指令的含义明确，无二义性。 （3）有穷性。算法必须在有限的时间内完成。有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。 （4）拥有足够的情报。 2、算法复杂度 算法复杂度主要包括时间复杂度和空间复杂度。我们通常讨论最坏情况复杂度。 （1）算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量。它与所使用的算法、问题的规模等有关。 （2）算法空间复杂度是指执行这个算法所需要的内存空间。 二、数据结构的基本概念 1、数据结构是指相互有关联的数据元素的集合。 2、数据结构主要研究和讨论以下三个方面的问题： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。数据的逻辑结构有线性（主要有线性表、栈、队列等）、非线性（主要有树、图等）。 （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。 数据的存储结构有顺序、链接、索引等。 数据的逻辑结构反映数据元素之间的逻辑关系，数据的存储结构（也称数据的物理结构）是数据的逻辑结构在计算机存储空间中的存放形式。同一种逻辑结构的数据可以采用不同的存储结构，但影响数据处理效率。 （3）对各种数据结构进行的运算。 3、数据的逻辑结构还可表示为（D，R），D：数据元素的集合；R：各数据元素之间的关系的集合； 三、线性表 1、线性表是由n个具有相同特性的数据元素组成的线性序列。 2、逻辑结构：线性结构 3、存储结构：顺序存储结构/链式存储结构 顺序存储结构的线性表需要一组连续的存储单元依次存储元素，因此知道存储的起始地址以及每个元素所占空间即可求出第I个元素的存储地址，而链式存储结构的线性表则无需连续空间，因此也无法计算其地址，即无法随机存取； 链式存储结构的线性表进行插入、删除等运算时不需要移动其他结点，而顺序存储结构的线性表则不然； 4、顺序存储结构的线性表的运算 插入、删除以及其算法分析 （1）顺序表的插入运算：在一般情况下，要在第i（1≤i≤n）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。 顺性表的插入运算时需要移动元素，在等概率情况下，平均需要移动n/2个元素。 （2）顺序表的删除运算：在一般情况下，要删除第i（1≤i≤n）个元素时，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了1。 进行顺性表的删除运算时也需要移动元素，在等概率情况下，平均需要移动（n-1）/2个元素。插入、删除运算不方便。 5、链表的运算 插入、删除以及其算法分析 6、循环链表 7、双向链表 四、栈 1、栈是一种特殊的 HYPERLINK /datastructure/basic/list/chapter1.htm 表，这种表只在表头进行插入和删除操作，且进行插入删除操作时不需要移动表中其他元素。我们称表头为栈顶，表尾为栈底。不含任何元素的栈称为空栈。栈的修改是按“后进先出”（LIFO）或“先进后出”的原则进行的。top指示着栈顶位置；bottom指向栈底。 2、逻辑结构：线性结构 3、存储结构：顺序存储结构/链式存储结构 4、栈的运算（顺序存储结构/链式存储结构）： 栈空的判别条件 进栈、出栈、读栈顶元素 五、队列 1、队列是一种特殊的 HYPERLINK /datastructure/basic/list/chapter1.htm 线性表。对这种线性表，删除操作只在表头(称为队头，用front指向队头元素的前一个位置)进行，插入操作只在表尾(称为队尾，用rear指向队尾元素)进行。队列的修改是按先进先出的原则进行的，所以队列又称为先进先出(First In First Out)表，简称FIFO表。 2、逻辑结构：线性结构 3、存储结构：顺序存储结构/链