国家计算机c语言二级公共基础知识.doc

数据结构与算法 算法的基本特征 可行性 确定性 有穷性（在有限时间内做完） 拥有足够情报 算法的基本要素 对数据对象的运算和操作 算法的控制结构 算法设计基本方法 列举法 归纳法 递推法 递归 减半递推技术 回溯法 算法复杂度 时间复杂度（执行算法所需要的计算工作量） 空间复杂度（执行算法所需要的内存空间） 数据结构 逻辑结构 储存结构（物理结构） 数据结构（根据数据元素前后件关系的复杂度） 线性结构（根节点唯一 每个节点最多只有一个前件一个后件） 非线性结构 线性表是一种线性结构 线性表的顺序储存结构（储存空间连续 按逻辑依次存放） 栈是一种特殊的线性表（先进后出） 队列是一种特殊的线性表（先进先出） 循环队列 链式储存结构 既可用于表示线性结构 也可用于表示非线性结构 线性链表（线性表的链式储存结构） 带链的栈 带链的队列 循环链表 树是一种简单的非线性结构（根 结点 叶子结点 度 深度） 二叉树 第k层最多2^(k-1)个结点 深度为m的二叉树最多2^m-1个结点 叶子结点总比度为2的结点多一个 n个结点深度至少为[log2 n]+1 满二叉树 完全二叉树 二叉树通常采用链式储存结构 二叉树的历遍（前序历遍 中序历遍 后序历遍） 查找技术 顺序查找（n） 二分法查找（只适用于顺序储存的有序表log2 n） 排序技术 交换类排序 冒泡排序法（n(n-1)/2） 快速排序法（nlog2 n） 插入类排序法 简单插入排序法（n(n-1)/2） 希尔排序法（O（n^1.5）） 选择类排序法 简单选择排序法（n(n-1)/2） 堆排序法（O （nlog2 n）） 第二章 面向对象的程序设计 程序设计风格考虑因素 源程序文档化 数据说明的方法 语句的结构（清晰第一 效率第二 信息屏蔽 模块化） 输入和输出 结构化程序设计的原则 自顶向下 逐步求精 模块化 限制使用goto语句 结构化程序的基本结构 顺序结构 选择结构 重复结构（循环结构） 面向对象的程序设计优点 与人类习惯的思维方法一致 稳定性好 可重用性好 易于开发大型软件产品 可维护性好 面向对象的程序设计要素 对象及对象属性（标识唯一性 分类性 多态性 封装性 模块独立性好） 类和实例 消息 继承 多态性 第三章 软件工程基础 计算机软件 程序 数据 相关文档 软件特点 逻辑实体具有抽象性 没有明显制作过程 不存在磨损老化问题 开发与运行受计算机系统限制 复杂性高 成本昂贵 软件按功能分类 应用软件 系统软件（如操作系统 编译程序 汇编程序 网络软件 数据库管理系统） 支撑软件（工具软件 如需求分析工具软件 实际工具软件 编码工具软件 测试工具软件 计划进度管理工作软件 过程控制软件 质量管理及配置管理工具软件） 软件危机（成本 质量 生产率） 软件需求的增长得不到满足 开发成本和进度无法控制 质量难以保证 不可维护或维护程度低 成本提高 开发生产率的提高赶不上硬件的发展和应用的增长 软件工程三要素 方法 工具 过程 软件生命周期 软件定义（可行性研究 需求分析） 软件开发（概要设计 详细设计 实现 测试） 软件运行维护（使用 维护 退役） 软件工程的目标 在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。 软件工程的理论和技术性研究的内容 软件开发技术 软件工程管理 软件开发技术 软件开发方法学 开发过程 开发工具 软件工程环境 软件工程管理 软件管理学 软件工程经济学 软件心理学 软件工程原则 抽象 信息屏蔽 模块化 局部化 确定性 一致性 完备性 可验证性 软件开发方法 分析方法 设计方法 程序设计方法 需求分析 需求获取 需求分析 编写需求规格说明书 需求评审 需求分析方法（又分为静态分析方法和动态分析方法） 结构化分析方法（面向数据流的结构化分析方法SA 面向数据结构的Jackson方法JSD 面向数据结构的结构化数据系统开发方法DSSD） 面向对象的分析方法（OOA） 结构化分析的常用工具 数据流图（DFD 加工 数据流 储存文件（数据源） 源，潭） 数据字典（DD） 判定树 判定表 软件需求规格说明书作用 便于用户、开发人员进行理解和交流 反映用户问题的结构，可以作为软件开发工作的基础的依据 作为确认测试和验收的依据 结构化设计 按技术观点：软件结构设计 数据设计 接口设计 过程设计 按工程管理角度：概要设计 详细设计 软件设计的基本原理 抽象 模块化 信息屏蔽 模块独立性 内聚性（偶然内聚 逻辑内聚 时间内聚 过程内聚 通信内聚 顺序内聚 功能内聚） 耦合性（内容耦合 公共耦合 外部偶合 控制偶合 标记耦合 数据偶合 非直接耦合） 概要设计基