计算机等级考试二级指导教程公共基础知识

第1页共52页全国计算机等级考试指导教程（二级）——公共基础知识编著黄海军2013年9月第2页共52页目录前言..............................................................3二级考试中的公共基础知识的备考.......................................................................................3历年公共基础知识考点统计与分析.......................................................................................4第一章数据结构与算法..............................................51.1算法.....................................................................................................................................51.2数据结构的基本概念.........................................................................................................61.3线性表及其顺序存储结构.................................................................................................81.4栈和队列.............................................................................................................................91.5线性链表...........................................................................................................................111.6树与二叉树.......................................................................................................................131.7查找技术...........................................................................................................................181.8排序技术...........................................................................................................................19第二章程序设计基础..............................................202.1程序设计设计方法和风格...............................................................................................202.2结构化程序设计（面向过程的程序设计方法）...........................................................212.3面向对象的程序设计.......................................................................................................22第三章软件工程基础..............................................243.1软件工程基本概念..........................................................................................................243.2结构化分析方法..............................................................................................................283.3结构化设计方法..............................................................................................................303.4软件测试..........................................................................................................................343.5程序的调试......................................................................................................................37第四章数据库设计基础...........................................384.1数据库系统的基本概念..................................................................................................384.2数据模型..........................................................................................................................424.3关系代数...........................................................................................................................454.4数据库设计与管理..........................................................................................................48第3页共52页计算机等级考试二级指导教程公共基础知识前言二级考试中的公共基础知识的备考从2005年初开始，教育部对全国计算机等级考试进行了较大调整。二级考试的笔试包括基础知识和程序设计两部分，其中基础知识占30分。这次改革的思想就是将基础知识的内容由计算机常识（一级难度）调整为程序开发基础（三级难度），如果这部分知识内容没有掌握好，难以在等级考试中取得好成绩。因此，必须引起我们足够的重视，这部分因涉及四门课程知识，要求面广。实际上只要掌握了一定的备考技巧过关也不难的。大纲的二级基础知识分为数据结构与算法、程序设计基础、软件工基础、数据库设计基础四部分，下面分别说一下学习重点和方法：（1）数据结构与算法本章的知识用于提高程序的效率以及对较复杂的问题进行求解。本章内容在计算机专业基础课中也属于比较难的一门，学习本章的内容必须进行理解，死记硬背是无效的。对于等级考试，本章重点的考核点主要在二叉树，同时这也是本章的难点，考核形式主要为二叉树的遍历问题（如给图求遍历序列、给前序、中序遍历求后序遍历等）、二叉树的结点问题（如给出一些条件然后求叶子结点个数）；还有排序和查找考试中也经常会涉及到，排序主要以计算时间复杂度的形式考核，查找主要以计算最佳/最坏比较次数的方式考核。其余的知识点主要以概念的形式考察，考生需要仔细看书并理解。（2）程序设计基础与软件工程基础这两章以概述的形式简介了规范化开发软件的方法。与数据结构不同，这两章内容主要是记忆性的知识点。程序设计基础的内容与大纲改革前添加了面向对象程序设计的内容，考生可以对本章进行几次细读后了解即可；软件工程基础这章主要考核内容为结构化分析及结构化设计方法（即SA及SD，约占50%），信息量较大，其次是软件测试（约占20%），考生需要将相关的概念及规则背诵，在以后有机会进行程序开发时这些知识可以得到深刻理第4页共52页解。（3）数据库设计基础数据库是当前软件处理的信息核心，目前大部分软件都是基于数据库的，因此学习一下数据库知识对程序开发也是很有帮助的。本章主要的考核点是关系模型、关系代数及数据库系统的基本概念，其余的知识点了解即可，其中数据库的设计和管理可以结合着软件工程来看，考生会发现这两者有很多相似之处。除了关系代数会考一些简单的计算问题外，其余的都是以概念题的形式考核，考生需要仔细的阅读。以上为复习二级公共基础的方法，顺便提及一点考生在选购教材的时候应当特别注意，应当购买最近版的二级公共基础知识教程（指定教材由高等教育出版社出版），还有考生在备考时，除了应完成教材中的习题外还应当做一下近几年的真题，并且用其估计一下自己的知识欠缺以便更好的进行查漏补缺。历年公共基础知识考点统计与分析章节知识点2012下2012上2011下2011上2010下2010上2009下2009上2008下2008上2007下2007上2006下2006上2005下2005上数据结构与算法算法220020420+22+2数据结构的基本概念0200040002+22线性表及顺序存储0002+20000000栈和队列4442+20200+4242线性链表00000000202树与二叉树20+2220+22+24+2204+20+2查找技术20020002002排序技术002022000+220程序设计基础程序设计方法与风格00000004000结构化程序设计020+202000200面向对象程序设计0002020+200+200+2软件工程基础软件工程基本概念4+22+222+2602404+22结构化分析方法20+20200+400000结构化设计方法02202022022第5页共52页软件测试00+22+20+20+20+22+200+202程序调试20000200+2220+2数据库设计基础数据库的基本概念22+20+220+422+24+22+22+22数据模型2+222+22+222+2204+202+2关系代数22202022020数据库设计与管理2020+20+2002020第一章数据结构与算法1.1算法1、算法：是指解题方案的准确而完整的描述。算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。2、算法的基本特征（1）可行性；针对实际问题而设计的算法，执行后能够得到满意的结果。（2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，取能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。综上所述，所谓算法就是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。3、算法复杂度主要包括算法时间复杂度和算法空间复杂度。（1）算法时间复杂度是指执行