文档介绍：全国计算机等级考试
二级公共基础知识
公共基础知识
内容:
考试大纲
数据结构与算法
程序设计基础
软件工程基础
数据库设计基础
考试大纲
考试内容
一、基本数据结构与算法 1、算法的基本概念;算法复杂度的概念和意义(空间复杂度与时间复杂度)。 2、数据结构的定义;数据的逻辑结构和存储结构;数据结构的图形表示;线性结构与非线性结构的概念。 3、线性表的定义;线性表的顺序存储结构及其插入删除运算。 4、栈和队列的定义;栈和队列的顺序存储结构及其基本运算。 5、线性单链表,双向链表与循环链表的结构及其基本运算。 6、树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。 7、顺序查找与二分查找算法;基本排序算法(交换类排序、选择类排序、插入类排序)。
考试大纲
考试内容
二、程序设计基础 1、程序设计方法与风格。 2、结构化程序设计。 3、面向对象的程序设计方法,对象,方法,属性及继承与多态性。
考试大纲
考试内容
三、软件工程基础 1、软件工程的基本概念;软件生命周期概念;软件工具与软件开发环境。 2、结构化分析方法;数据流图,数据字典,软件需求规格说明书。 3、结构化设计方法; 总体设计,详细设计。 4、软件测试的方法;白盒测试,黑盒测试,测试用例设计;软件测试的实施;单元测试,集成测试,系统测试。 5、程序的调试,静态调试与动态调试。
考试大纲
考试内容
四、数据库设计基础 1、数据库的基本概念;数据库,数据库管理系统,数据库系统。 2、数据模型;实体联系模型及E-R图,从E-R图导出关系数据模型。 3、关系代数运算,包括集合运算及选择、投影、连接运算;数据库规范化理论。 4、数据库设计方法和步骤;需求分析、概念设计、逻辑设计和物理设计的相关策略。
数据结构与算法
关键考点
算法基本概念及算法复杂度
数据的存储结构
栈和队列
线性链表
二叉树基本概念及其特性
查找技术
第1节数据结构与算法
算法的基本概念
1、算法 算法是指解题方案的准确而完整的描述。 注意:算法与数学上的计算方法不是同一个概念。算法要考虑计算机的特点,要考虑计算方法的可行性。 算法也不等于程序。算法不考虑具体的机器及编程语言。解决问题时,总是先设计算法,然后进行编程。
2、算法的基本特征 可行性 确定性 有穷性 拥有足够的情报 算法是一个动态概念,强调实际的执行过程。 数学上的计算方法是一个静态概念,注重理论上的正确性。 数学上的计算方法是设计算法的基础。
例题:
算法的有穷性是指
1. 算法的基本概念
第1节数据结构与算法
算法的基本概念
3、算法的基本要素 算法中对数据的运算和操作 基本的运算和操作有:算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构 控制结构决定操作的执行顺序。要求符合结构化原则,强调易读性。
4、算法设计基本方法 列举法列举所有可能情况,检测其中符合条件的结果。 归纳法列举若干特殊情况,分析归纳出一般规律。 递推从已知初始条件出发,逐步推导出中间及最后结果。 递归将复杂问题归结为简单问题,在归结为更简单问题,…。 减半递推技术将问题规模“减半”,并重复该“减半”的过程。 回溯法分析问题,找出某些线索,沿线索逐步试探。若试探成功,则继续,若试探失败,则回退。直至问题解决。