c语言公共基础复习重点

《c语言公共基础复习重点》由会员分享，可在线阅读，更多相关《c语言公共基础复习重点（27页珍藏版）》请在金锄头文库上搜索。

1、第二部分二级公共基础历年试题分布： 数据结构与算法（3-5个选择题，一般4题；1-3个填空题，一般2题，约12分） 程序设计基础（1-2个选择题，一般1题；0-2个填空题，一般 0-1个，约4分） 软件工程基础（2-3个选择题，一般 2题；1-2个填空题，一般 2个，约8分） 数据库设计基础（2-3个选择题，一般 2题；1-2个填空题，一般 2个，约8分）第一章数据结构与算法第一部分算法大纲要求：算法的基本概念；算法复杂度的概念和意义（时间与空间复杂度）一、算法的基本概念算法：是指一组有穷的指令集，是解题方案的准确而完整的描述。通俗的说，算法就是计算机解题的过程注：程序的编制不可能优于算法。二

2、、算法的基本特征 （）1、可行性：能够得到满意的结果。2、确定性：算法的每一个步骤都必须有明确的定义。3、有穷性：一个算法必须在执行有穷步后结束，即算法必须能够终止。即必须能在有限的时间内做完。4、 拥有足够的情报（有零个输入或多个输入，有一个或多个输出）：算法是否有效，取决于算法提供的情报是 否足够。例：1算法的有穷性是指（）【08年4月】AA）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用三、算法设计基本方法1、列举法2、归纳法3、递推法4、递归法5、减半递推技术6、回溯法四、 算法复杂度 （时间复杂度和空间复杂度）（）1

3、、时间复杂度：执行算法所需要的计算工作量，也就是 耗费的时间量。是对算法时间效率的度量。2、空间复杂度：执行这个算法所 需要的内存空间， 是对算法所需存储空间的度量。3、 时间复杂度与空间复杂度是从两个方面对算法的效率进行度量，两者之间没有必然的联系。例：1算法的空间复杂度是指（）。【09年9月】 AA.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数2. 算法复杂度主要包括时间和 【05年9月】复杂度。3. 下列叙述中正确的是（）【06年9月】DA ） 一个算法的空间复杂度大，则其时间复杂度也必定大B ） 一

4、个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂必定小D）上述三种说法都不对第二部分数据结构大纲要求：数据结构的定义，数据的逻辑结构与存储结构，数据结构的图形表示；线性结构与非线性结构的概 念。一、数据结构的相关概念1、数据结构一一是指由某一数据对象及该对象中所有数据成员之间的关系组成的集合。通常也指带有结构的数据元素的集合。数据结构可分为数据的逻辑结构和数据的存储结构两种。2、 数据的逻辑结构一一反映数据元素之间逻辑关系的数据结构。（）3、数据的存储结构一一数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，即各数据元素在计算机中的存储关系。（）4

5、、数据存储结构不仅要存放各数据元素的信息，还要存放各数据元素之间的前后件关系的信息。5、逻辑结构与存储结构之间的关系（）一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的。例：1.下列描述中 正确的是（）【05年9月】DA）个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率2. 下列叙述正确的是（）【07年4月】BA ）算法的效率

6、只与问题的规模有关，而与数据的存储结构无关B）算法的时间复杂度是指执行算法所需要的计算工作量C） 数据的逻辑结构与存储结构是对应的（可以一对多）D）算法的时间复杂度与空间复杂度一定相关（ 不相关）3. 下列叙述中正确的是（）【07年9月】。A）数据的逻辑结构与存储结构必定是一一对应的B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构D）以上三种说法都不对4. 数据的存储结构是指（ ）【05年4月】DA）存储在外存中的数据B）数据在外存中的数据C）数据在计算机中的顺序存储方式D）数据的逻辑结构在计

7、算机中的表示如：一年四季的数据结构用图形表示为6、数据结构的符号表示：B=（ D，R）B :数据结构，D:数据元素的集合，R :数据元素之间的前后件关系。7、数据结构的图形表示：方框：表示数据兀素有向线段：表示数据兀素的前后件关系。（按逻辑结构的分类）（）8、根据数据结构各数据元素之间前后件关系的复杂程度，将数据结构分为: 线性结构非线性结构9、线性结构所满足的条件： 有且只有一个根结点； 每一个结点最多有一个直接前驱，也最多有一个直接后继；线性结构又称为线性表，如：线性表、栈、队列、循环对列、线性链表、循环链表等属线性结构。（）10、非线性结构：如果一个数据结构不是线性结构，则称之为非线性结

8、构。女口：树、二叉树等属非线性结构（）例：1.下列叙述中正确的是（）【06年4月】A）线性链表是线性表的链式存储结构B）栈与队列是非线性结构C）双向链表是非线性结构D）只有根结点的二叉树是线性结构2. 线性表的正确说法是（）【05年4月】BA）存储空间不一定连续，前件和后件可以任意排列B）存储空间不一定连续，前件必须排在后件的前面C）存储空间一定连续，前件和后件可以任意排列D）存储空间一定连续，前件必须排在后件的前面11、空的数据结构既可以是线性结构，也可以是非线性结构，要根据该结构进行的运算而定。二、线性表大纲要求：线性表的定义，线性表的顺序存储结构及其插入与删除运算1、线性表是最简单、最常

9、用的一种线性数据结构。2、 非空线性表有以下三个结构特征： 有且只有一个根结点，它无前件； 有且只有一个终端结点，它无后件； 除根结点与终端结点外，其他所有结点有且只有一个前件（直接前驱），也有且只有一个后件（直接后继）。3、线性表中结点的个数 n称为线性表的长度，当n=0时，称为空表。4、线性表的顺序存储结构具有以下两个基本特点： 线性表中所有元素 所占的存储空间是连续的 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的5、以顺序存储方式存储的线性表称为顺序表，顺序表的基本运算有： 插入运算要在第i （1=i=n ）个元素之前插入一个新元素时，首先要从最后一个元素开始，直到第i个元素之间

10、共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。 删除运算在一般情况下，要删除第i（ 1=i=n ）个元素，则原来第 i个元素之后的所有元素都必须依次往前移动一个位置。6、7、线性表的顺序存储结构适合小线性表或其中元素不常变动的线性表，对于元素经常需要变动的大线性 表就不太合适，因 为顺序存储的插入与删除的效率比较低。（）三、线性单链表大纲要求：线性单链表、双向链表的结构及其基本运算1、线性链表一一线性表的链式存储结构称为线性链表。2、 在线性链表中，用一个专门的指针HEAD指向线性链表中第一个数据元素的结点，线性链表中最后一个元素没有后件，因

11、此最后一个结点的指针域为空（用NULL或0表示），表示链表终止。3、线性链表中的每一个元素，一方面要存储数据元素的值；另一方面要存储各数据元素之间的前后件关系。即是将 存储空间的每一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号，即指向后件结点，称为指针域。HEADAB%3519* CD NULL4、线性单链表的基本运算：插入运算和删除运算 插入运算：首先给要插入的元素分配一个新结点，以便用于存储该元素的值，新结点可以从可利用栈中取得，然后将存放新元素值的结点链接到线性链表中指定的位置。 删除运算：首先要在线性链表中找到要删除的结点，然后

12、将要删除结点放回到可利用栈。注：线性链表中插入和删除元素时，不需要移动数据元素，因此插入和删除的效率比较高。（）四、双向链表1、双向链表一一对线性链表中的每个结点设置两个指针，一个称为左指针（Llink），用以指向其前驱结点;另一个称为右指针（Rlink），用以指向其后继结点，这样的链表称为双向链表。HEAD注：双向链表的突出特点是从某一结点出发能够找到它的前件。（）五、循环链表 大纲要求：循环链表的结构及其基本运算1、循环链表与线性单链表相比，循环链表具有以下特点： 循环链表中最后一个结点的指针域不是空，而是指向表头结点，即在循环链表中，所有结点的指针 构成了一个环状链。 在循环链表中增加了

13、一个表头结点，在任何情况下，表中至少有一个结点存在，从而使空表与非空表的运算得到统一。 在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点, 而线性单链表就不行。六、栈（它是一种特殊的线性表）大纲要求：栈的定义，栈的顺序存储结构及其基本运算。1、栈一一是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶（TOP），而不允许插入与删除的另一端称为栈底（BOTTOM）。（）2、 栈是按照“先进后出”或“后进先出”的原则来组织数据的。（）3、 栈具有记忆功能，因此可用于函数或过程调用。（）（m表示栈的最大容量,4、关于栈的进出和计算（*）top=

14、0表示栈空，top=m表示栈满）例：1.下列关于栈的描述正确的是（）【05年9月】CA）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素2. 按照”后进先出”原则组织数据的数据结构是（）【06年4月】B3下列关于栈的叙述正确的是（A ）栈按“先进先出”组织数据C）只能在栈底插入数据4. 一个栈的初始状态为空。现将元素 元素出栈的顺序是【08年9月】BA）队列B）栈C）双向链表D）二叉树）【08年4月】BB）栈按“先进后出”组织数据D）不能删除数据1、2、3、4、5、A、B、C、D E依次入栈，然后再依次出栈，则A）12345ABCDE B ） EDCBA54321 C ）ABCDE12345 D ） 54321EDCBA5. 支持子程序调用的数据结构是（）【09年4月】 AA ）栈B）树C）队列D）二叉树6. 假设用一个长度为 50的数组（数组元素的下标从 0到49）作为栈的存储空间，栈底指针 bottom指 向栈底元素，栈顶指针 top指向栈顶元素，如果 bottom=49，top=30 （数组下标），则栈中具有【09年4月】个元素。204、栈的基本运算有三种：