|
二级计算机等级考试公共基础知识大纲要求
基本要求
掌握算法基本概念
掌握基本数据结构及其操作
掌握基本排序和查找算法
掌握逐步求精的结构化程序设计算法
掌握工程的基本算法,具有初步应用相关技术进行软件开发能力
考试内容
一 基本数据结构与算法
1 算法的基本概念,算法复杂度概念和意义(时间复杂度和空间复杂度)
2 数据结构的定义,数据的逻辑结构和存储结构,数据结构的图形表示,线性结构与非线性结构的概念
3 线性表的定义,线性表的顺序存储结构极其插入与删除的运算
4 栈和队列的定义:栈和队列的顺序存储结构及其基本运算
5 线性单链表多向链表与循环链表及其基本运算
6 树的基本概念,二叉树的定义及其存储结构,二叉树的前序,中序,后序遍历
7 顺序查找与二分法查找,基本排序算法(交换类,选择类,插入类)
二 程序设计基础
1 程序设计方法与风格
2 结构化程序设计
3 面向对象的程序设计方法,对象,方法,属性及继承与多态性
三 软件的工程基础
1 软件工程基本概念,软件声明周期概念,软件工具与软件开发环境
2 结构化分析方法,数据流图,数据字典,软件需求规格说明书
3 结构化程序设计方法总体设计与详细设计
4 软件测试方法:白盒测试与黑盒测试,测试用例设计,软件测试的实施,单元测试,集成测试和系统测试
5 程序的调试;静态调试与动态调试
四 数据库设计基础
1 数据库的基本概念;数据库,数据库管理系统,数据库系统,数据模型,E-R图,从导出关系数据模型
2 关系代数运算包括集合运算及选择,投影,连接运算,数据库规范化理论
3 数据设计方法和步骤;需求分析,概念设计,逻辑设计,和物理设计的相关策略
公共基础知识各章掌握重点归纳
一 数据结构与算法
算法定义：所谓算法是解题方案的准确而完整的描述
算法的特征：可行性、确定性、有穷性、拥有足够的情报
算法的二要素；一是对数据对象的控制和操作，二是算法的控制结构
算法的三种基本控制结构：顺序，选择，循环
算法复杂度包括时间复杂度和空间复杂度
时间复杂度是指执行算法所需要的计算工作量
------可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量
算法的空间复杂度是指执行这个算法所需要的内存空间
数据结构是指相互关联的数据元素的集合
------数据元素之间的前后件关系是指他们的逻辑关系，而与他们在计算机中的存储位置无关
数据的存储结构：数据的呒峁乖诩扑慊娲⒖占渲械拇娣判问匠莆莸拇娲⒔峁?BR>数据结构的两大类型：线性结构和非线性结构
线性结构与非线性结构都可以是空的数据结构
在计算机中存放线性表一种最简单的方法是顺序存储
栈是先进后出的线性表（栈顶top 栈底bottom）
队列是先进先出的线性（表排头指针front 尾指针rear）
链式存储方式中每个结点由两部分组成：数据域和指针域
当从线性链表中删除一个元素后该元素存储结点就变为空闲，应将该空闲结点送回到可利用栈
循环链表增加了一个表头结点
|
