二级公共基础知识辅导讲义(2011年面授版)

《二级公共基础知识辅导讲义(2011年面授版)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、全国计算机等级考试二级——公共基础知识教程（2011年版）作者：王欣前言全国计算机等级考试（NationalComputerRankExamination，简称NCRE）是经原国家教育委员会（现教育部）批准，由教育部考试中心主办，面向社会，用于考察应试人员计算机应用知识与技能的全国性计算机水平考试体系。全国计算机等级考试设四个等级。它不以评价教学为目的，考核内容不是按照学校要求设定，而是根据社会不同部门应用计算机的不同程度和需要、国内计算机技术的发展情况以及中国计算机教育、教学和普及的现状而确定的；它以应用能力为主，划分等级，分别考核，为人员择业、人才流动

2、提供其计算机应用知识与能力水平的证明。全国计算机等级考试二级是目前参考人数最多的一个等级。二级考试设置了多个考试科目：C语言程序设计、VisualBasic语言程序设计、VisualFoxPro数据库程序设计、Access数据库程序设计、C++语言程序设计、Java语言程序设计、Delphi语言程序设计等。考试形式为“理论+上机”，必须理论考试和上机考试均合格才认作通过考试。不管考生选考二级哪个科目，理论考试中都要考公共基础知识，且试题均一样，占30分，在试卷中为选择题的1-10题，填空题的1-5题。公共基础知识多数考题考察的都是基本原理与基本概念，要求考

3、生实记。目前在网络上流行的《全国计算机等级考试——二级公共基础知识辅导讲义》为我在2008年编写的，本次改版根据最新的考试大纲，结合教育部考试中心所编的教程和近年来的数份真题，重新对某些知识点进行了归纳，全面符合最新的考试命题特点。本书分为四章，排序按照教育部考试中心所编的教程设定，第一章为“数据结构与算法”；第二章为“程序设计基础”；第三章为“软件工程基础”；第四章为“数据库设计基础”。考生只要把本书中的要点掌握，并做几份近几年的公共基础知识真题后，应对公共基础知识应该没有太大问题。III本版书中的标记符仍然继承了上一版的标记符，在这里给大家做个解释：□

4、代表需要掌握的概念；代表需要掌握的重要考点；*后的语句代表重要语句，需要大家掌握；若某个字或词下面有“小黑点”，则表示该字或词为重点，提醒大家注意。由于本人水平有限，书中难免有错误或不妥之处，欢迎广大读者给予批评指正。作者联系邮箱：njwangx@163.com。王欣2011年7月于绿海III目录第一章数据结构与算法1本章应考点拨11.1算法11.2数据结构的基本概念11.3线性表及其顺序存储结构31.4栈和队列41.5线性链表51.6树与二叉树61.7查找技术91.8排序技术10第二章程序设计基础12本章应考点拨122.1程序设计风格122.2结构化程序

5、设计（面向过程的程序设计方法）132.3面向对象的程序设计13第三章软件工程基础16本章应考点拨163.1软件工程基本概念163.2结构化分析方法193.3结构化设计方法213.4软件测试243.5程序的调试27第四章数据库设计基础28本章应考点拨284.1数据库系统的基本概念284.2数据模型324.3关系代数364.4数据库设计方法和步骤37III第一章数据结构与算法本章应考点拨：本章内容在笔试中会出现5-6个题目，是公共基础知识部分出题量比较多的一章，所占分值也比较大，约10分。1.1算法1、算法是指解题方案的准确而完整的描述。换句话说，算法是对特定

6、问题求解步骤的一种描述。*：算法不等于程序，也不等于计算方法。程序的编制不可能优于算法的设计这是因为：在编写程序时要受到计算机系统运行环境的限制，程序通常还要考虑很多与方法和分析无关的细节问题。。2、算法的基本特征（1）可行性。针对实际问题而设计的算法，执行后能够得到满意的结果。（2）确定性。每一条指令的含义明确，无二义性。并且在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出。（3）有穷性。算法必须在有限的时间内完成。有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。（4）拥有足够的情报。算法中各种运算总是

7、要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这就是算法执行的起点或依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法将无法执行或执行有错。一般说来，当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。*：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。3、算法复杂度主要包括时间复杂度和空间复杂度。（1）算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运

8、算的执行次数来度量。（2）算法空间复杂度是指执行这个算法所需要的内