全国计算机等级考试二级公共基础知识考点

工程训练中心计算机等级考试辅导班内部资料1全国计算机等级考试二级公共基础知识考点公共基础知识基本要求1．掌握算法的基本概念。2．掌握基本数据结构及其操作。3．掌握基本排序和查找算法。4．掌握逐步求精的结构化程序设计方法。5．掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。6．掌握数据库的基本知识，了解关系数据库的设计。考试内容一、基本数据结构与算法1．算法的基本概念；算法复杂度的概念和意义(时间复杂度与空间复杂度）。2．数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3．线性表的定义；线性表的顺序存储结构及其插入与删除运算。4．栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5．线性单链表、双向链表与循环链表的结构及其基本运算。6．树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7．顺序查找与二分法查找算法；基本排序算法(交换类排序，选择类排序，插入类排序)。二、数据库设计基础1．数据库的基本概念：数据库，数据库管理系统，数据库系统。2．数据模型，实体联系模型及E―R图，从E―R图导出关系数据模型。3．关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4．数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略三、程序设计基础1．程序设计方法与风格2．结构化程序设计。3．面向对象的程序设计方法，对象，方法，属性及继承与多态性。四、软件工程基础1．软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2．结构化分析方法，数据流图，数据字典，软件需求规格说明书。3．结构化设计方法，总体设计与详细设计。4．软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5．程序的调试，静态调试与动态调试。全国计算机等级考试二级公共基础讲义之一算法与数据结构本章应考点拨：本章内容在笔试中会出现5-6个题目，是公共基础知识部分出题量比较多的一章，所占分值也比较大，约10分。1.1算法1、算法的基本概念：是指解题方案的准确而完整的描述。工程训练中心计算机等级考试辅导班内部资料2算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。2、算法的基本特征（1）可行性针对实际问题而设计的算法，执行后能够得到满意的结果。（2）确定性每一条指令的含义明确，无二义性。并且在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出。（3）有穷性算法必须在有限的时间内完成。有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。（4）拥有足够的情报算法中各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这就是算法执行的起点或依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法将无法执行或执行有错。一般说来，当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。*：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。3、算法复杂度主要包括时间复杂度和空间复杂度。（1）算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量。同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法运行工作量的大小，只依赖于问题的规模（通常用整数n表示），它是问题规模的函数。即算法的工作量=f（n）（2）算法空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。【算法习题】1、算法的时间复杂度是指CA)执行算法程序所需要的时间B)算法程序的长度C)算法执行过程中所需要的基本运算次数D)算法程序中的指令条数2、算法的基本特征是可行性、确定性、有穷性和拥有足够的情报。3、算法的空间复杂度是指CA)算法程序的长度B)算法程序中的指令条数C)算法程序所占的存储空间D)执行过程中所需要的存储空间4、在计算机中，算法是指BA)加工方法B)解题方案的准确而完整的描述C)排序方法D)查询方法5、算法的工作量大小和实现算法所需的存储单元多少分别称为算法的【1】时间复杂度和空间复杂度1.2数据结构的基本概念1、数据结构是指相互有关联的数据元素的集合。2、数据结构主要研究和讨论以下三个方面的问题：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。工程训练中心计算机等级考试辅导班内部资料3数据的逻辑结构有两个要素：一是数据元素的集合；二是此集合上的关系，它反映了数据元素之间的前后件关系（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。数据的存储结构有顺序、链接、索引等。1）顺序存储。它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里。由此得到的存储表示称为顺序存储结构。2）链接存储。它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。3）索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。同一种逻辑结构的数据可以采用不同的存储结构，而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。（3）对各种数据结构进行的运算。3、数据结构的图形表示一个数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。4、根据数据结构中各数据元素之间前后件关系的复杂程度，数据结构分为两大类型：线性结构和非线性结构。（1）线性结构（非空的数据结构）条件：有且只有一个根结点[wx3]；每一个结点最多有一个前件，也最多有一个后件。*：常见的线性结构有线性表（栈、队列是线性表的特例）（2）非线性结构：不满足线性结构条件的数据结构。*：常见的非线性结构有树、二叉树和图等。【数据结构基本概念习题】1、根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成A)动态结构和静态结构B)紧凑结构和非紧凑结构C)线性结构和非线性结构D)内部结构和外部结构2、数据结构包括数据的逻辑结构、数据的【2】以及对数据的操作运算。存储结构3、数据的基本单位是【5】。数据元素4、下列叙述中，错误的是A)数据的存储结构与数据处理的效率密切相关B)数据的存储结构与数据处理的效率无关C)数据的存储结构在计算机中所占的空间不一定是连续的D)一种数据的逻辑结构可以有多种存储结构5、数据的存储结构是指A）数据所占的存储空间C）数据在计算机中的顺序存储方式B）数据的逻辑结构在计算机中的表示D）存储在外存中的数据工程训练中心计算机等级考试辅导班内部资料46、顺序存储方法是把逻辑上相邻的结点存储在物理位置【2】的存储单元中。相邻7、数据处理的最小单位是A)数据B)数据元素C)数据项D)数据结构8、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及A)数据的存储结构B)计算方法C)数据映象D)逻辑存储9、数据结构中，与所使用的计算机无关的是数据的A)存储结构B)物理结构C)逻辑结构D)物理和存储结构10、数据的逻辑结构有线性结构和【1】两大类。非线性结构1.3线性表及其顺序存储结构1、线性表是由n(n≥0)个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个和最后一个外，有且只有一个前件、后件。线性表中数据元素的个数称为线性表的长度。线性表可以为空表。*：线性表有两种存储方式：顺序和链式。2、线性表的顺序存储结构（也称为顺序表）具有两个基本特点：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的，即顺序表中逻辑上相邻的元素的物理位置必定紧邻。（即逻辑结构和物理存储结构是一致的、一一对应的）3、顺序表的插入、删除运算（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个元素。插入、删除运算不方便。在长度为n的顺序表中插入、删除一个元素的时间复杂度都为O(n)。（3）即查找操作：可实现随机访问、随机存取元素在顺序表中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面，即顺序存储结构通过元素的相对存储地址来表示元素之间的关系，可以通过计算机直接确定第i个结点的存储地址。ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。线性表顺序存储的优点是可以随机访问、随机存取元素即实现查找操作比较方便，换句话说，顺序表是一种随机存取的存储结构。线性表顺序存储的缺点：（1）插入或删除数据元素时需要移动大量的数据元素，运算效率很低。；（2）顺序表的存储空间不便于扩充；（3）不便于对存储空间的动态分配工程训练中心计算机等级考试辅导班内部资料51.4线性链表线性表的链式存储结构称为线性链表，是一种物理存储单元上非连续、非顺序的存储结构（存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致），数据元素的逻辑关系是通过链表中的指针链接来实现的。因此，在链式存储方式中，每个结点由两部分组成：一部分用于存放数据元素的值，称为数据域；另一部分用于存放指针，称为指针域，用于指向该结点的前一个或后一个结点（即前件或后件）。线性链表分为单链表、双向链表和循环链表三种类型。在单链表（如下图）中，每一个结点只有一个指针域，由这个指针只能找到其后件结点，而不能找到其前件结点。因此，在某些应用中，对于线性链表中的每个结点设置两个指针，一个称为左指针，指向其前件结点；另一个称为右指针，指向其后件结点，这种链表称为双向链表，如下图所示：3、线性链表的基本运算（1）在线性链表中包含指定元素的结点之前插入一个新元素。*：在线性链表中插入元素时，不需要移动数据元素，只需要修改相关结点指针即可。（2）在线性链表中删除包含指定元素的结点。*：在线性链表中删除元素时，也不需要移动数据元素，只需要修改相关结点指针即可。（3）将两个线性链