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

《全国计算机等级考试二级公共基础知识考点》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、工程训练中心计算机等级考试辅导班内部资料全国计算机等级考试二级公共基础知识考点公共基础知识基本要求1．掌握算法的基本概念。2．掌握基本数据结构及其操作。3．掌握基本排序和查找算法。4．掌握逐步求精的结构化程序设计方法。5．掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。6．掌握数据库的基本知识，了解关系数据库的设计。考试内容一、基本数据结构与算法1．算法的基本概念；算法复杂度的概念和意义(时间复杂度与空间复杂度）。2．数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3．线性表的定义；线性表的顺序存储结构及其插入与删除运算。4．栈和队列的

2、定义；栈和队列的顺序存储结构及其基本运算。5．线性单链表、双向链表与循环链表的结构及其基本运算。6．树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7．顺序查找与二分法查找算法；基本排序算法(交换类排序，选择类排序，插入类排序)。二、数据库设计基础1．数据库的基本概念：数据库，数据库管理系统，数据库系统。2．数据模型，实体联系模型及E―R图，从E―R图导出关系数据模型。3．关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4．数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略三、程序设计基础1．程序设计方法与风格2．结构化程序设计。3

3、．面向对象的程序设计方法，对象，方法，属性及继承与多态性。四、软件工程基础1．软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2．结构化分析方法，数据流图，数据字典，软件需求规格说明书。3．结构化设计方法，总体设计与详细设计。4．软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5．程序的调试，静态调试与动态调试。全国计算机等级考试二级公共基础讲义之一算法与数据结构本章应考点拨：本章内容在笔试中会出现5-6个题目，是公共基础知识部分出题量比较多的一章，所占分值也比较大，约10分。1.1算法1、算法的基本概念：是指解题方案的准确而完整的描

4、述。21工程训练中心计算机等级考试辅导班内部资料算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。2、算法的基本特征（1）可行性针对实际问题而设计的算法，执行后能够得到满意的结果。（2）确定性每一条指令的含义明确，无二义性。并且在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出。（3）有穷性算法必须在有限的时间内完成。有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。（4）拥有足够的情报算法中各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这就是算法执行的起点或依据。因此，一个算法执行的结果总是与输入的

5、初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法将无法执行或执行有错。一般说来，当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。*：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。3、算法复杂度主要包括时间复杂度和空间复杂度。（1）算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量。同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的

6、。撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法"运行工作量"的大小，只依赖于问题的规模（通常用整数n表示），它是问题规模的函数。即算法的工作量=f（n）（2）算法空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。【算法习题】1、算法的时

7、间复杂度是指CA)执行算法程序所需要的时间B)算法程序的长度C)算法执行过程中所需要的基本运算次数D)算法程序中的指令条数2、算法的基本特征是可行性、确定性、有穷性和拥有足够的情报。3、算法的空间复杂度是指CA)算法程序的长度B)算法程序中的指令条数C)算法程序所占的存储空间D)执行过程中所需要的存储空间4、在计算机中，算法是指BA)加工方法B)解题方案的准确而完整的描述C)排序方法D)查询方法5