全国计算机等级考试二级公共基础知识(教师版).ppt

全国计算机等级考试;2011年3月二级公共基础知识点分布;第一章 数据结构与算法(30%);一.算法的基本概念;一.算法的基本概念;一.算法的基本概念;一.算法的基本概念;一.算法的基本概念;一.算法的基本概念AQ21;典型例题;二.数据结构;数据结构简单实例;数据的逻辑结构;数据的存储结构;典型例题;线性结构和非线性结构;线性表 ;线性表的顺序存储;线性表的插入和删除运算;栈;栈的顺序存储及运算;栈;队列;循环队列 ;单链表;单链表;单链表的插入和删除;双向链表和循环链表;回顾：;树及其基本概念;树的主要术语;二叉树;二叉树的基本性质;满二叉树和完全二叉树;二叉树的基本性质;;二叉树的链式存储结构;二叉树的链式存储结构;二叉树的遍历;二叉树的遍历;二叉树的遍历;二叉树的遍历;例：;查找;二分查找(折半查找);折半查找;例题：;排序 ;交换类排序;冒泡排序示例;快速排序;快速排序;;插入类排序;简单插入排序示例;希尔排序;希尔排序;选择类排序;简单选择排序示例;排序时间复杂度汇总（基数空间为O（rd);**从上表应当看出：;第二章 程序设计基础(15%);知识点归纳;程序设计风格;程序设计风格（4个方面）;;程序设计风格;程序设计风格;结构化程序设计;结构化程序设计的基本结构和特点;例：结构化程序设计的基本思想是采用自顶向下，逐步求精的程序设计方法和单入口单出口的控制结构。 ;面向对象程序设计; 面向对象方法的基本概念;对象的特点;对象的特点; 例：有三个栈（对象），分别放数值型、字符型、日期型数据，队列（对象）向三个栈发送同样的“读取”消息，则产生的结果不一样。;2.方法 方法也可称为操作或服务，它描述了对象执行的功能，若通过消息传递，还可为其他对象使用。 3.消息：面向对象系统中的对象之间是通过消息机制彼此相互合作的。消息由三部分组成： 消息标识符、零个或多个参数、接受消息对象的对象名 ;面向对象程序设计的特点;;第三章 软件工程基础;软件定义和特点;软件危机;软件工程;软件工程过程;软件工程目标与原则;软件开发工具与软件开发环境;软件生命周期;需求分析阶段的主要工作;软件需求;需求分析阶段典型例题;**结???化分析方法（SA）;*数据流图;数据流图的基本符号的意思 矩形表示数据的外部实体（数据源或终点）； 圆角的矩形表示变换数据的处理（加工），加工过程至少要有一个输入流和输出流。 少右面的边矩形表示数据存储； 箭头表示数据流，是数据的流向。 ;例：数据流图（DFD）;数据字典;结构化设计（SD）;由上面的数据流图转化的SC图;详细设计即过程设计。功能是为软件结构图（SC）中的每一个模块确定采用的算法，模块内数据结构，用某种选定的表达工具（如N-S图等）给出清晰的描述。 常用工具有：程序流程图、N-S图、PAD图、过程设计语言PDL(伪码)。 ;由SC图中的’密码验证’得到的N-S图 （右边是N-S图，左边是根据图写的代码）; 需求分析的工具： （不要与方法弄混了，也不要与结构化分析工具弄混！！！） 问题分析图 （ PAD ）、程序流程图 （PFD ）、 N-S （也是一种流程图）也称为盒图，是程序流程图的一种改进 。 程序流程图（PFD）中的箭头代表的是：控制流 数据流图中的箭头代表：数据的流向 结构图（sc):箭头代表模块的调用 ;软件设计阶段典型例题;软件设计阶段典型例题;软件测试;测试技术与方法综述;测试技术与方法综述;软件测试的实施;程序调试;软件维护;维护的副作用;软件测试维护阶段典型例题;测试与维护阶段典型例题;测试与维护阶段典型例题;第四章 数据库设计基础;知识点归纳;计算机数据管理技术发展的三个阶段;数据库管理系统(DBMS);数据库系统;数据库系统的内部体系结构;数据模型;一个学生实体转换为关系模型;数据模型;ER模型的基本概念;ER图;物理数据模型 与逻辑数据模型;层次模型;网状模型;关系模型的概念;关系模型的基本概念;关系的基本性质;关系模型的数据操作;参照完整性例子;关系运算;笛卡尔乘积 ;数据库设计;数据库设计;数据库设计;数据库管理;谢谢！