本书依据《全国计算机等级考试二级公共基础知识考试大纲》而编写的，提炼官方指定考试教程内容，精析历年考题，以让考生能尽快掌握数据结构与算法、程序设计基础、软件工程以及数据库的相关知识。本书研究05年~12年考试真题的主要考点、要点和难点，汇集历年考题，提炼重要常考知识点，把握考试动向，以使考生能够从容应对全国计算机等级二级考试。

本书根据教育部考试中心颁布的最新版《全国计算机等级考试二级公共基础知识考试大纲》的要求而编写。
本书对考纲中规定的知识点进行了详细透彻的讲解，并且对2005年春季至2012年春季的所有考试真题进行了分析和总结，对考生参加全国计算机等级考试(二级）语言类考试具有指导性的作用和帮助。
全书共分5章，每章主要内容如下：
第1章主要介绍了数据结构和算法的概念、线性表的定义、特殊的线性表栈和队列的概念及其基本运算和性质、二叉树的基本概念和3种遍历方法、2种典型的查找方法——顺序查找和二分查找，最后介绍了算法中常用的几种排序方法。
第2章介绍了程序设计方法、结构化程序设计的思想及3种基本结构(即顺序结构、选择结构和循环结构）。
第3章介绍了软件工程的基本概念、结构化分析方法和结构化设计方法、软件测试和程序调试的常用方法。
第4章介绍了数据库相关知识。首先介绍了数据库的几个相关概念，其次介绍了概念模型、逻辑模型等内容，以及关系代数中常用的传统运算和关系运算。最后介绍了数据库设计的步骤。
第5章为各章节知识结构图及考试情况说明。
本书由孙勤红、刘粉香、沈凤仙、朱颖雯编著，其中第1～2章由孙勤红编写，第3章由沈凤仙编写，第4章由刘粉香编写，第5章和附录由朱颖雯编写。全书由孙勤红统稿，由顾洪老师主审。苏兆中老师为本书提出了很多宝贵意见和建议，单启成老师、陈林老师和张凤莲老师等为编写本书提供了很多帮助，在此表示感谢。同时感谢中国铁道出版社的各位编辑为本书的出版所提供的大力支持和帮助。
本书适用于参加全国计算机等级考试(二级）的各类计算机语言(如VFP、C语言、VC++、C++、VB、Access等科目）考试的读者，也可用于对计算机感兴趣的读者。
由于编者水平有限，书中疏漏或不妥之处在所难免，恳请广大读者批评指正。


编 者
2012年11月

第1章 数据结构与算法 1
1.1 数据结构的基本概念 1
1.2 算法 4
1.2.1 算法的基本概念 4
1.2.2 算法分析 6
1.3 线性表及其存储结构 9
1.4 栈和队列 15
1.4.1 栈的基本概述及基本运算 15
1.4.2 队列的基本概述及基本运算 20
1.5 树和二叉树 25
1.5.1 关于树和二叉树的基本术语和性质 25
1.5.2 满二叉树与完全二叉树 31
1.5.3 二叉树的遍历 32
1.6 查找技术 38
1.7 排序技术 40
第2章 程序设计基础 47
2.1 程序设计方法与风格 47
2.2 结构化程序设计 49
2.3 面向对象的程序设计 52
第3章 软件工程基础 55
3.1 软件工程的基本概念 55
3.1.1 软件的定义与特点 55
3.1.2 软件危机与软件工程 57
3.1.3 软件工程过程与软件生命周期 59
3.2 结构化分析方法 61
3.2.1 需求分析与需求分析方法 61
3.2.2 结构化分析方法 63
3.3 结构化设计方法 66
3.3.1 软件设计的基本概念 66
3.3.2 概要设计 68
3.3.3 详细设计 71
3.4 软件测试 74
3.4.1 软件测试的目的和原则 74
3.4.2 软件测试分类 76
3.5 程序的调试 78
第4章 数据库设计基础 81
4.1 数据库系统的基本概念 81
4.1.1 数据库技术的发展及组成 81
4.1.2 数据库系统的特点 84
4.1.3 数据库系统的内部结构体系 86
4.2 数据模型 87
4.2.1 数据模型的基本概念 87
4.2.2 概念模型和E-R模型 88
4.2.3 逻辑模型的分类 91
4.3 关系数据库 92
4.3.1 关系数据模型的数据结构 92
4.3.2 关系操作 94
4.3.3 关系的完整性 101
4.4 数据库设计 101
第5章 各章知识结构图及考试情况说明 105
5.1 各章知识结构图 105
5.2 考试情况 113
附录A 全国计算机等级考试二级公共基础知识考试大纲 115
附录B 最近两年考试真题 117
附录C 各章节重要知识点列表 125
参考文献 132

主要著译者顺序姓名学历职称学科专长通讯地址1孙勤红 硕士 计算机基础 工作单位三江学院计算机基础部 邮政编码 电话 2 工作单位 邮政编码 电话 3 工作单位 邮政编码 电话 审校者（主审者） 学历 工作单位 邮政编码 电话 职称 工作单位 邮政编码 电话

全国计算机等级二级考试用书