全国计算机等级考试二级公共基础考点.docVIP

第一部分 数结点1 杂1. 算法的基本概念 算法是对问题求解过程的精确描述。 算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。 算法的基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的3种基本控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法主要有：列举法、归纳法、递推、递归、减半递推技术、回溯法。 指令系统：一台计算机系统能执行的所有指令的集合。 2. 算法的复杂度 算法的复杂度包括时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量；空间复杂度是指执行算法所需要的内存空间。 典型题例 1．算法的有穷性是指 。 A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用 2．算法的空间杂 。 A）算法在执行过程中所需要的计算机存储空间 B）算法所处数 C）算法程序中的语条数 D执过临时单数3．算法的时间杂 。 A) 算法的执时间 B处数 C) 算法程序中的语条数 D4．下列叙述中正确的是 。 A）算法就是程序 B）设计算法时只需要考虑数据结构的设计 C）设计算法时只需要考虑结果的可靠性 D）以上三种说法都不对 5．算法的时间复杂度取决于 。 A）问题的规模 B）待处理的数据的初态 C）问题的难度 D）A）和B） 6．问题处理方案的正确而完整的描述称为 。算法 考点2 逻辑结储结1. 数据结构的基本概念 (1)数据结构：是指相互有关联的数据元素的集合。 (2)数据结构主要研究3个方面的内容：①数据集合中各数据元素之间的逻辑关系，即数据的逻辑结构；②在对资料进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；③对各种数据结构进行的运算。 2. 逻辑结构 数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。所以一个数据结构B可以表示成：B=(D，R) 例如，如果把一年四季看作一个数据结构，则可表示成：B=(D,R)，其中D={春季，夏季，秋季，冬季}，R={（春季，夏季）,（夏季，秋季），（秋季，冬季）}。 3. 存储结构 数据的逻辑结构在计算机存储空间中的存放形式称数据的存储（物理）结构。 数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储结构、链接存储结构。 顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。 链式存储结构就是在每个结点中至少包含一个指标域，用指标来体现数据元素之间逻辑上的联系。 考点 3 线结线结1. 线性结构 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。 如果一非空的数据结构满足：①有且仅有一个根结点；②每一个结点最多有一个前件，也最多有一件后件。则称该数据结构为线性结构或线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都是线性结构。 2. 非线性结构 如果一个数据结构不满足线性结构的两个条件的一个或两个，则该结构称为非线性结构。广义表、树和图等数据结构都是非线性结构。 3. 线性表的顺序存储结构具有以下两个基本特点 (1)线性表中所有元素所占的存储空间是连续的； (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 例如，对于线性表(a1,a2,…,ai,…,an)元素ai的存储位址为： ADR(ai)=ADR(a1)+(i-1)*k 其中，ADR(a1)是第一个元素的位址，k代表每个元素所占的位元组数。 4. 顺序表的运算 顺序表是指线性表的顺序存储结构，对顺序表的运算有：查找、插入、删除等。 典型题例 1．下列叙述中正确的是 。 A）顺序结构存储的存储一定是连续的，链式存储结构的存储空间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有序表 D）链式存储结构比顺序存储结构节省存储空间 2．下列数结属线结 。 A）循环队 B) 带链队 C) 二叉树 D）带链栈3．下列关于线性链表的叙述中，正确的是