《国家计算机c语言二级公共基础知识.doc》由会员分享，可在线阅读，更多相关《国家计算机c语言二级公共基础知识.doc（6页珍藏版）》请在金锄头文库上搜索。
1、第一章 数据结构与算法算法的基本特征可行性 确定性 有穷性（在有限时间内做完） 拥有足够情报算法的基本要素 对数据对象的运算和操作 算法的控制结构算法设计基本方法列举法 归纳法 递推法 递归 减半递推技术 回溯法算法复杂度时间复杂度（执行算法所需要的计算工作量） 空间复杂度（执行算法所需要的内存空间）数据结构逻辑结构 储存结构（物理结构）数据结构（根据数据元素前后件关系的复杂度）线性结构（根节点唯一 每个节点最多只有一个前件一个后件） 非线性结构线性表是一种线性结构 线性表的顺序储存结构（储存空间连续 按逻辑依次存放）栈是一种特殊的线性表（先进后出）队列是一种特殊的线性表（先进先出） 循环队列
2、链式储存结构 既可用于表示线性结构 也可用于表示非线性结构 线性链表（线性表的链式储存结构） 带链的栈 带链的队列 循环链表树是一种简单的非线性结构（根 结点 叶子结点 度 深度）二叉树第k层最多2(k-1)个结点 深度为m的二叉树最多2m-1个结点 叶子结点总比度为2的结点多一个 n个结点深度至少为log2 n+1 满二叉树 完全二叉树二叉树通常采用链式储存结构 二叉树的历遍（前序历遍 中序历遍 后序历遍）查找技术顺序查找（n） 二分法查找（只适用于顺序储存的有序表log2 n）排序技术交换类排序冒泡排序法（n(n-1)/2） 快速排序法（nlog2 n）插入类排序法 简单插入排序法（n(n
3、-1)/2） 希尔排序法（O（n1.5）选择类排序法简单选择排序法（n(n-1)/2） 堆排序法（O （nlog2 n）第二章 面向对象的程序设计程序设计风格考虑因素源程序文档化 数据说明的方法 语句的结构（清晰第一 效率第二 信息屏蔽 模块化） 输入和输出结构化程序设计的原则自顶向下 逐步求精 模块化 限制使用goto语句结构化程序的基本结构顺序结构 选择结构 重复结构（循环结构）面向对象的程序设计优点与人类习惯的思维方法一致 稳定性好 可重用性好 易于开发大型软件产品 可维护性好面向对象的程序设计要素对象及对象属性（标识唯一性 分类性 多态性 封装性 模块独立性好） 类和实例 消息 继承
4、多态性第三章 软件工程基础计算机软件程序 数据 相关文档软件特点 逻辑实体具有抽象性 没有明显制作过程 不存在磨损老化问题 开发与运行受计算机系统限制 复杂性高 成本昂贵 软件按功能分类应用软件 系统软件（如操作系统 编译程序 汇编程序 网络软件 数据库管理系统） 支撑软件（工具软件 如需求分析工具软件 实际工具软件 编码工具软件 测试工具软件 计划进度管理工作软件 过程控制软件 质量管理及配置管理工具软件）软件危机（成本 质量 生产率）软件需求的增长得不到满足 开发成本和进度无法控制 质量难以保证 不可维护或维护程度低 成本提高 开发生产率的提高赶不上硬件的发展和应用的增长软件工程三要素方法
5、 工具 过程软件生命周期软件定义（可行性研究 需求分析） 软件开发（概要设计 详细设计 实现 测试） 软件运行维护（使用 维护 退役）软件工程的目标在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。软件工程的理论和技术性研究的内容软件开发技术 软件工程管理软件开发技术 软件开发方法学 开发过程 开发工具 软件工程环境软件工程管理 软件管理学 软件工程经济学 软件心理学软件工程原则抽象 信息屏蔽 模块化 局部化 确定性 一致性 完备性 可验证性软件开发方法分析方法 设计方法 程序设计方法需求分析需求获取
6、 需求分析 编写需求规格说明书 需求评审 需求分析方法（又分为静态分析方法和动态分析方法）结构化分析方法（面向数据流的结构化分析方法SA 面向数据结构的Jackson方法JSD 面向数据结构的结构化数据系统开发方法DSSD） 面向对象的分析方法（OOA）结构化分析的常用工具数据流图（DFD 加工 数据流 储存文件（数据源） 源，潭） 数据字典（DD） 判定树 判定表软件需求规格说明书作用便于用户、开发人员进行理解和交流 反映用户问题的结构，可以作为软件开发工作的基础的依据 作为确认测试和验收的依据结构化设计按技术观点：软件结构设计 数据设计 接口设计 过程设计按工程管理角度：概要设计 详细设计
7、软件设计的基本原理抽象 模块化 信息屏蔽 模块独立性 内聚性（偶然内聚 逻辑内聚 时间内聚 过程内聚 通信内聚 顺序内聚 功能内聚） 耦合性（内容耦合 公共耦合 外部偶合 控制偶合 标记耦合 数据偶合 非直接耦合）概要设计基本任务设计软件系统结构 数据结构及数据库设计 编写概要设计文档 概要设计文档评审常用软件结构设计工具结构图（SC 也成程序结构图 箭头标识模块间调用关系）结构图四种模块类型（传入模块 传出模块 变换模块 协调模块）数据流类型变换型（输入 中心变换 输出） 事务型概要设计的准则 提高模块独立型 模块规模适中 顶层高扇出 底层高扇入 模块作用域在控制域内 减少模块的接口和界面的
8、复杂性 设计成单入口单出口的模块 设计功能可预测的模块详细设计常见工具图形工具：程序流程图（控制流 加工步骤 逻辑条件） N-S PAD HIPO表格工具：判定表语言工具：PDL（过程涉及语言也成结构化的英语和伪码）软件测试准则所有测试都应追溯到需求 严格执行测试计划，排除测试的随意性 充分注意测试中的集群现象 程序员应避免检查自己的程序 穷举测试不可能 妥善保存测试计划、测试用例、出错统计和最终分析报告软件测试分类按是否需要执行被测软件：静态测试（代码检查 静态结构分析 代码质量度量） 动态测试（不实际运行软件）按功能：白盒测试（逻辑覆盖（语句覆盖 路径覆盖 判定覆盖 条件覆盖 判断-条件覆
9、盖） 基本路径测试） 黑盒测试（等价类划分法 边界值分析法 错误推测法 因果图 主要用于软件确认测试）软件测试过程单元测试（对模块进行测试） 集成测试（发现与接口有关的错误） 验收测试（确认测试） 系统测试（功能测试 性能测试 操作测试 配置测试 外部接口测试 安全测试）程序调试基本步骤 错误定位 修改设计和代码 进行回归测试程序调试方法强行排错法 回溯法 原因排除法第四章 数据库设计基础数据库（DB）数据库管理系统（DBMS） 是数据库系统的核心 数据库管理系统功能数据模式定义 数据存取的物理构建 数据操纵 数据的完整性、安全性定义与检查 数据库的并发控制与故障恢复 数据的服务数据库管理系统
10、的数据语言数据定义语言(DDL) 数据操纵语言(DML) 数据控制语言(DCL) 数据库系统(DBS)数据库 数据库管理系统 数据库管理员 硬件平台 软件平台数据库应用系统（DBAS）数据库系统 应用软件 应用界面数据库系统的发展人工管理阶段 文件系统阶段 数据库系统阶段数据库系统基本特点数据的集成性 数据的高共享性与低冗余性 数据独立性（物理独立性：物理结构改变 不影响逻辑结构） 数据统一管理与控制(安全性控制 完整性控制 并发性控制 数据的恢复)数据库系统的三级模式概念模式 外模式（子模式或用户模式） 内模式（物理模式 真实存在于计算机外存中）数据库系统的两级映射 概念模式到内模式的映射
11、外模式到概念模式的映射数据模型概念数据模型（与计算机平台无关 E-R模型） 逻辑数据模型（层次模型 网状模型 关系模型 面向对象模型） 物理数据模型（面向计算机物理表示的模型）E-R模型实体 属性 联系 （一对一 一对多 多对多）层次模型 基本结构是树形结构关系模型采用二维表表示二维表：每行数据成为元组 二维表性质个数有限 均不相同 无序性 分量两个是不可分割的基本数据项 属性名唯一性 属性的无序性 分量值域同一性关系模型键或码 候选键或候选码 主键或主码 外键 关系中的数据约束实体完整性约束 参照完整性约束 用户定义的完整性约束关系模型的基本运算插入（并） 删除（差） 修改 查询（投影 选择 笛卡尔积）关系代数扩充运算交 除 连接与自然连接 数据库设计需求分析阶段 概念设计阶段 逻辑设计阶段 物理设计阶段 （编码阶段 测试阶段 运行阶段 进一步修改阶段）数据库概念设计方法 集中式模式设计法 视图集成设计法数据库概念设计的过程选择局部应用 视图设计 视图集成
