文档介绍：全国计算机等级考试二级公共基础部分
曾雪强
南昌大学计算中心
******@ncu.
数据结构考点
* * 1、算法特征:
可行性
确定性
有穷性
拥有足够的情报(输入输出)
2、算法的基本方法
穷举法(枚举法)
归纳法
递归法
递推法
回溯法等
* * 3、复杂度
时间复杂度:基于基本运算的次数,O(f(n))
平均情况
最坏情况
空间复杂度
4、数据结构
逻辑结构
物理(存储结构)
集合
线性结构:线性表,栈,队列
非线性结构:树、图
顺序存储:逻辑上相联,物理上也相联
链式存储:逻辑上相联,物理上
不一定相联
索引:函数映射
5、线性表,栈,队列
线性表:有序序列,一前驱,一后继
地址运算:ADR(ai)=ADR(a1)+(i-1)k
栈:后进先出,操作只在栈顶进行
队列:先进先出,删在队头,插在队尾
6、树和二叉树
二叉树的性质
性质一:第K层,最多2 k-1
性质二:深度为M最多2 m-1个
性质三:n0=n2+1
满二叉树,完全
二叉树
满:性质一二中最多结点的树
完全:(1)叶子结点只在最后两层
(2)编号与满一致(缺右不缺左)
遍历
前序遍历:先根再左再右
中序遍历:先左再根再右
后序遍历:先左再右再根
7、排序
交换类排序
冒泡排序:下沉排序,每趟保证最大的下沉
快速排序:分割排序每趟排序后,
前面比中间小,右边的比中间大
插入类排序
直接插入排序:无序的依次插入到有序的
希尔排序:整体划分部分子序列,
然后分别进行插入排序,增量递减
选择类排序
简单选择排序:每次选择最小的放置应有的位置
堆排序:
小顶堆:左右均大于等于根节点
大顶堆:左右均小于等你根节点
* 8、几种排序的时间复杂度比较
排序方法
平均时间
最坏情况
冒泡排序
O(n2)
O(n2)
快速排序
O(nlogn)
O(n2)
直接插入排序
O(n2)
O(n2)
希尔排序
O()
O()
简单选择排序
O(n2)
O(n2)
堆排序
O(nlogn)
O(nlogn)
程序设计方法考点
* 1、结构化程序设计方法:自顶向下,逐步求精,模块化
限制使用GOTO语句
* 2、面向对象程序
设计方法:
对象:客观的一个实体,类的实例化
类:对象的抽象
消息:对象之间交流的信息
继承:以原有的类为基础建立
新类,具有传递性,提高可重用性
多态:一个名字,多种语义或多个实现
手段。同样的消息不同对象接受导致不同行为。
封装:保证对象信息的隐蔽
软件工程考点
1、软件的概念:程序+数据+文档
2、软件危机:20世纪60年代。原因:成本、质量、生产率
3、软件工程3个要素
方法:提供技术手段
工具:支持开发
过程:控制管理
4、软件工程的4个基本活动
P:软件规格、功能说明
D:软件开发
C:软件确认
A:软件演进,变更需求
*5、软件生命周期
(提出-实现-
维护-停止)
定义阶段
可行性分析
需求分析
开发阶段
概要设计
详细设计
实现
测试
维护运行阶段
使用
维护
退役
* 6、软件工程研究的内容:软件开发技术和软件工程管理
7、软件工程的基本原则:抽象、信息隐蔽、模块化、局部化
确定性、一致性、完备性、可验证性
**8、需求分析
工作
需求分析
需求获取
编写需求规格说明书
需求评审
方法
结构化分析方法
面向对象分析方法(OA)
SA:(面向数据流)
Jackson(Jsd):(面向数据结构)
DSSD:面向数据结构的
结构化数据系统开发
**9、结构化分析方
法常用工具
数据流图(DFD):以图形元素进行组合
描述数据处理过程
数据字典(DD):对DFD中的
图形元素确切解释
判断树
判断表