2011年计算机二级考试公共基础知识冲刺复习笔记.pdf

第1天 全部的基本概念 Point1 算法的基本概念 5 考点精讲 1 算法 是指解题方案的准确而完整的描述 1 算法不等于程序 也不等计算机方法 程序的编制不可能优于算法的设计 程序也 可以作为算法的一种描述 但程序通常还要考虑程序运行时的环境限制等 2 算法 是一组严谨地定义运算顺序的规则 并且每一个规则都是有效的 是明确的 此顺序将在有限的次数下终止 2 算法的基本特征 1 可行性 例如1012 1 1012的问题 2 确定性 算法中每一步骤都必须有明确定义 不允许有模棱两可的解释 不允许有 多义性 例在特殊情况时 数学公式是正确的 但计算机就是无法操作 3 有穷性 算法必须能在有限的时间内做完 即能在执行有限个步骤后终止 包括合 理的执行时间的含义 例如1 3的无理数问题 4 拥有足够的情报 所有的各种可能情况都要考虑到 3 一个算法的优劣将影响到算法乃至程序的效率 算法分析的目的在于选择合适算法 和改进算法 一个算法的评价主要从时间复杂度和空间复杂度来考虑 1 算法的时间复杂度是指执行算法所需要的计算工作量 可以执行算法的过程中所需 要的基本运算的执行次数来度量 分析算法工作量的方法有 平均性态分析 最坏情况分析 2 算法的空间复杂度是指执行这个算法所需要的内存空间 主要包括 算法程序所占 的空间 输入的初始数据所占的空间 算法执行过程中所需要的额外空间 真题分析 真题1 算法的有穷性是指 2008年4月 A 算法程序的长度是有限的 B 算法只能被有限的用户使用 C 算法程序的运行时间是有限的 D 算法程序所处理的数据量是有限的 解析 算法的有穷性 是指算法必须能在有限的时间内做完 即算法必须能在执行有限 个步骤之后终止 答案 C 真题2 问题处理方案的正确而完整的描述称为 5 2005年4月 解析 算法是问题处理方案正确而完整的描述 答案 算法 真题3 算法的空间复杂度是指 2009年9月 A 算法程序中的语句或指令条数 B 算法在执行过程中所需要的临时工作单元数 C 算法在执行过程中所需要的计算机内部存储空间 D 算法所处理的数据量 6 解析 算法的空间复杂度是指执行这个算法所需要的计算机内部存储空间 简称内 存空间 答案 C 真题4 下列叙述中正确的是 2007年3月 A 数据的逻辑结构与存储结构是一一对应的 B 算法的时间复杂度与空间复杂度一定相关 C 算法的效率只与问题的规模有关 而与数据的存储结构无关 D 算法的时间复杂度是指执行算法所需要的计算工作量 解析 1 算法的时间复杂度是指执行算法所需要的计算工作量 算法的工作量用算法所执行 的基本运算次数来度量 而算法所执行的基本运算次数是问题规模的函数 算法的空间复杂 度一般是指执行这个算法所需要的内存空间 2 算法的时间复杂度与空间复杂度并不相关 3 数据的逻辑结构就是数据元素之间的逻辑关系 它是从逻辑上描述数据元素之间的 关系 是独立于计算机的 数据的存储结构是研究数据元素和数据元素之间的关系如何在计 算机中表示 它们并非一一对应 4 算法的执行效率不仅与问题的规模有关 还与数据的存储结构有关 答案 D 真题5 下列叙述中正确的是 2006年9月 A 一个算法的时间复杂度大 则其空间复杂度必定小 B 三种说法都不对 C 一个算法的空间复杂度大 则其时间复杂度也必定大 D 一个算法的空间复杂度大 则其时间复杂度必定小 解析 1 时间复杂度是指一个算法执行时间的相对度量 空间复杂度是指算法在运行过程中 临时占用所需存储空间大小的度量 2 人们都希望选择一个既省存储空间 又节省执行时间的算法 然而 有时为了加快 算法的运行速度 不得不增加空间开销 有时为了能有效 地存储算法和数据 又不得不牺 牲运行时间 时间和空间的效率往往是一对矛盾 很难做到两全 但是 这不适用于所有的 情况 也就是说时间复杂度和空间复杂度 之间虽然经常矛盾 但是二者不存在必然的联系 答案 B 真题6 算法复杂度主要包括时间复杂度和 2 复杂度 2005年9月 解析 算法的复杂度主要包括时间复杂度和空间复杂度 所谓算法的时间复杂度 是指 执行算法所需要的计算工作量 一个算法的空间复杂度 一般是指执行这个算法所需要的内 存空间规模 答案 空间 真题7 算法的时间复杂度是指 2010年3月 A 算法程序中的语句或指令条数 7 B 算法在执行过程中所需要的基本运算次数 C 算法的执行时间 D 算法所处理的数据量 解析 算法复杂度包括时间复杂度和空间复杂度 是衡量一个算法好坏的度量 算法的 时间复杂度主要是基本运算次数 答案 B Point2Point2Point2Point2 软件工程基本概念 软件工程基本概念 考点精讲 1 计算机软件是包括程序 数据及相关文档的完整集合 是计算机系统中与硬件相互 依存的部分 软件按功能分为应用软件 系统软件 支撑软件 或工具软件 2 软件工程源自于软件危机 1 软件危机主要表现在成本 质量 生产率等问题 2 软件工程的主要思想是强调在软件开发过程中需要应用工程化原则 软件工程学的 主要研究对象包括软件开发与维护的技术 方法 工具和管理等方面 3 软件工程包括三个要素 即方法 工具和过程 3 通常把软件产品从提出 实现 使用 维护到停止使用 退役 的过程称为软件生命 周期 1 可以将软件生命周期分为软件定义 软件开发及软件运行维护三个阶段 2 软件生 命周期的主要活动阶段是 可行性研究与计划制定 需求分析 软件设计 软件实 现 软件测试 运行和维护 真题分析 真题1 软件按功能可以分为 应用软件 系统软件和支撑软件 或工具软件 下面 属于应用软件的是 2009年3月 A 教务管理系统 B 汇编程序 C 编译程序 D 操作系统 解析 编译程序和汇编程序属于支撑软件 操作系统属于系统软件 而教务管理系统属 于应用软件 答案 A 真题2 软件是指 2007年9月 8 A 算法和数据结构 B 程序 数据和相关文档的完整集合 C 程序 D 程序和文档 解析 计算机软件是指计算机系统中与硬件相互依存的另一部分 是程序 数据与相关 文档的完整集合 软件由两部分组成 一是机器可执行的程序和数据 二是机器不可执行的 与软件开发 运行 维护 使用等有关的文档 答案 B 真题3 下列描述中正确的是 2005年9月 A 软件工程的主要思想是强调在软件开发过程中需要应用工程化原则 B 软件工程只是解决软件开发中的技术问题 C 软件工程只是解决软件项目的管理问题 D 软件工程主要解决软件产品的生产率问题 解析 软件工程学是研究软件开发和维护的普遍原理与技术的一门工程学科 所谓软件工程是指 采用工程的概念 原理 技术和方法指导软件的开发与维护 软件 工程学是研究软件开发和维护的普遍原理与技术的一门工程学科 所谓软件工程是指 采用 工程的概念 原理 技术和方法指导软件的开发与维护 软件工程学的主要研究对象包括软件开发与维护的技术 方法 工具和管理等方面 答案 A 真题4 下列描述中正确的是 2005年4月 A 软件既是逻辑实体 又是物理实体 B 软件是程序 数据与相关文档的集合 C 程序就是软件 D 软件开发不受计算机系统的限制 解析 计算机软件是计算机系统中与硬件相互依存的另一部分 包括程序 数据及相关 文档的完整集合 答案 B 真题5 软件按功能可以分为 应用软件 系统软件和支撑软件 或工具软件 下面 属于系统软件的是 2010年3月 A 教务管理系统 B 浏览器 C 编辑软件 D 操作系统 解析 只有操作系统是系统软件 答案 D 9 真题6 软件是 4 数据和文档的集合 2010年3月 解析 软件 程序 数据 相关文档 答案 程序 真题7 软件工程三要素包括方法 工具和过程 其中 3 支持软件开发的各个 环节的控制和管理 2008年9月 解析 软件工程包括的3个要素是方法 工具和过程 方法是完成软件工程 项目的技术手段 工具支持软件的开发 管理 文档生成 过程支持软件开发 的各个环节的控制 管理 答案 过程 真题8 软件生命周期可分为三个阶段 一般分为定义阶段 开发阶段和维护阶段 编码和测试属于 4 阶段 2007年3月 解析 通常将软件产品从提出 实现 使用 维护到停止使用退役的过程称为 软件生命周期 软件生命周期分为软件定义 软件开发和软件运行维护三个阶 段 定义阶段包括可行性研究 初步项目计划和需求分析两个活动阶段 开发 阶段包括概要设计 详细设计 编码实现 测试四个活动阶段 维护阶段包括 使用 维护 退役三个活动阶段 答案 开发 真题9 下面描述中 不属于软件危机表现的是 2010年9月 A 软件质量难以控制 B 软件成本不断提高 C 软件过程不规范 D 软件开发生产率低 解析 在软件开发中遇到的问题找不到解决办法 使问题积累起来 形成了尖锐的矛盾 因而导致了软件危机 软件危机表现在以下几个方面 1 经费预算经常突破 完成时间一再拖延 2 开发的软件不能满足用户要求 3 开发的软件可维护性差 4 开发的软件可靠性差 5 软件开发费用不断增加 6 软件开发生产效率低下 答案 C 真题10 软件生命周期是指 2010年9月 A 软件的开发过程 B 软件的运行维护过程 C 软件产品从提出 实现 使用维护到停止使用退役的过程 D 软件从需求分析 设计 实现到测试完成的过程 10 解析 软件生命周期是指从软件定义 开发 使用 维护到报废为止的整个过程 一般包括问题定义 可行性分析 需求分析 总体设计 详细设计 编码 测试和维护等阶 段 答案 C Point3Point3Point3Point3 数据库的基本概念 数据库的基本概念 考点精讲 1 数据库的基本概念 1 数据 实际上就是描述事物的符号记录 数据的特点 有一定的结构 有型与值之 分 如整型 实型 字符型等 而数据的值给出了符合 给定型的值 如整型值15 2 数据 库 DataBase 简称为 DB 是数据的集合 具有统一的结构形式并存放于统一的存储介质 内 是多种应用数据 的集成 并可被各个应用程序共享 数据库存放数据是按数据所提供 的数据模式存放的 具有集成与共享的特点 数据库技术的根本目标是要解决数据的共享问 题 2 数据库系统 DataBaseSystem 简称为 DBS 由数据库 数据 数据库管理系统 软件 数据库管理员 人员 硬件平台 硬件 软件平台 软件 五个部分构成 1 数据库管理系统提供以下的数据语言 数据定义语言 DDL 负责数据的模式定义与数据的物理存取构建 数据操纵语言 负责数据的操纵 如查询与增加 删除 修改等 数据控制语言 负责数据完整性 安全性的定义与检查以及并发控制 故障恢复等 2 数据库系统的特点 数据的集成性 数据高共享性与低冗余性 数据独立性 数据独立性是数据与程序之间互不依赖 也就是数据的逻辑结构 存储 结构与存取方式的改变不会影响应用程序 3 据库管理系统 DataBaseManagementSystem 简称为 DBMS 是系统软件 负责对数 据库的数据组织 数据操纵 数据维护 控制及保护和数据服务等 数据库管理系统是数据 库系统的核心 4 数据管理经历了人工管理 文件系统 数据库系统三个阶段 文件系统阶段的特点 是数据满足一个特定格式而存储 不同程序中使用的数据仍会出现重复存储 也会导致数据 冗余 数据库技术的主要目的是有效地管理和存取大量的数据资源 数据库系统阶段的数据 独立性最高 5 数据独立性包括物理独立性和逻辑独立性 11 1 物理独立性 数据的物理结构 如存储设备更换 物理存储方式 的改变 不影响 数据库的逻辑结构 也不引起应用程序的变化 2 逻辑独立性 数据库整体逻辑结构 如修改数据 增加新数据类型 改变数据间联系 等 改变 不需要修改应用程序 6 数据库系统在其内部具有三级模式 概念模式 内部模式与外部模式 1 概念模式 它是数据库系统中全局数据逻辑结构的描述 是全体用户 应用 的公 共数据视图 概念模式主要描述数据的概念记录类型以及它们之间的关系 它还包括一些数 据间的语义约束 对它的描述可用 DBMS 中的 DDL 语言定义 2 内部模式 又称物理模式 它给出了数据库物理存储结构与物理存取方法 如数据 存储的文件结构 索引 集簇及 hash 等存取方式与 存取路径 内模式的物理特性主要体现 在操作系统及文件级上 它还未深入到设备级 如磁盘及磁盘操作 上 DBMS 一般提供相关 的内模式描述语言 内模式 DDL 3 外部模式 也称子模式或用户模式 它是用户的数据视图 也就是用户所见到的数 据模式 它由概念模式推导而出 在一般的 DBMS 中都提供相关的外模式描述语言 外模式 DDL 7 数据库系统的两级映射 概念模式到内部模式的映射 外部模式到概念模式的映射 1 数据的物理独立性 当数据库的存储结构发生变 化时 通过修改 概念模式到内部模式 的映射 使得数据库的概念模式不变 其外模式不变 应用程序不用修改 保证了数据的 物理独立性 2 数据的逻辑独立性 当概念模式发生变化时 通过修改 外部模式到概念模式的映 射 使得用户所用的外模式不变 从而应用程序也不用修改 保证了数据的逻辑独立性 真题分析 真题1 数据库管理系统是 2009年9月 A 一种编译系统 B 一种操作系统 C 操作系统的一部分 D 在操作系统支持下的系统软件 解析 数据库管理系统是运行在操作系统之上的支撑软件 是数据库系统的核心 答案 D 真题2 数据库系统的核心是 4 系统 2009年3月 解析 数据库管理系统是数据库的结构 它是一种系统软件 负责数据库中数据组织 数据操纵 数据维护 控制及保护和数据服务等 数据库管理系统是数据库系统的核心 答案 数据库管理 12 真题3 在数据管理技术发展的三个阶段中 数据共享最好的是 2008 年9月 A 数据库系统阶段 B 三个阶段相同 C 人工管理阶段 D 文件系统阶段 解析 数据管理技术的发展经历了三个阶段 人工管理阶段 文件系统阶段和数据库系 统阶段 人工管理阶段无共享 冗余度大 文件管理阶段共享性差 冗余度大 数据库系统 管理阶段共享性大 冗余度小 答案 A 真题4 在数据库管理系统提供的数据定义语言 数据操纵语言和数据控制语言中 5 语言负责数据的模式定义与数据的物理存取构建 2008年4月 解析 在数据库管理系统提供的数据定义语言 数据操纵语言和数据控制语言中 数据 定义语言负责数据的模式定义与数据的物理存取构建 数 据操纵语言负责数据的操纵 包 括查询及增 删 改等操作 数据控制语言负责数据完整性 安全性的定义与检查以及并发 控制 恢复等功能 答案 数据定义 真题5 下列叙述中正确的是 2007年9月 A 数据库管理系统就是数据库系统 B 三种说法都不对 C 数据库系统是一个独立的系统 不需要操作系统的支持 D 数据库技术的根本目标是要解决数据共享的问题 解析 数据库系统由如下几个部分组成 数据库 数据 数据库管理系统 软件 数据 库管理员 人员 系统平台的硬件平台 硬件 系统平台的软件平台 软件 这五个部分构成 了一个以数据库为核心的完整的运行实体 称为数据库 系统 数据库技术的根本目的是要解决数据的共享问题 数据库中的数据具有 集成 共享 之特点 亦即数据库集中了各种应用的数据 进行 统一地构造与存储 从而使它们可被不同应用程序所使用 数据库管理系统 DatabaseManagementSystem 简称 DBMS 是一种系统软件 负责数据 库中的数据组织 数据操作 数据维护 控制及保护和数据服务等 它是数据库系统的核心 答案 D 真题6 下列叙述中错误的是 2007年3月 A 数据库设计是指在已有数据库管理系统的基础上建立数据库 B 数据库系统需要操作系统的支持 C 在数据库系统中 数据的物理结构必须与逻辑结构一致 D 数据库技术的根本目标是要解决数据的共享问题 Point4Point4Point4Point4 程序设计方法与风格 程序设计方法与风格 考点精讲 1 养成良好的程序设计的设计风格 主要应考虑下述因素 1 源程序文档化 符号名的命名有一定含义 便于理解 正确的注释帮助读者理 解程序 程序层次清晰 16 2 数据说明的方法 数据说明的次序规范化 说明语句中变量安排有序化 使 月注释来说明复杂数据结构 3 语句的结构 程序应该简单易懂 语句构造应该简单直接 4 输入和输出 2 注释分序言性注释和功能性注释 语句结构清晰第一 效率第二 真题分析 真题1 下列选项不符合良好程序设计风格的是 2006年9月 A 避免滥用 goto 语句 B 模块设计要保证高耦合 高内聚 C 源程序要文档化 D 数据说明的次序要规范化 解析 编程风格是在不影响性能的前提下 有效地编排和组织程序 以提高可读性和可 维护性 更直接地说 风格就是意味着要按照规则进行编程 这些规则包括 编程风格是在 不影响性能的前提下 有效地编排和组织程序 以 提高可读性和可维护性 更直接地说 风格就是意味着要按照规则进行编程 1 程序文档化 就是程序文档包含恰当的标识符 适当的注解和程序的视觉组织等 2 数据说明 出于阅读理解和维护的需要 最好使模块前的说明语句次序规范化 此 外 为方便查找 在每个说明语句的说明符后 数据名应按照字典顺序排列 3 功能模块化 即把源程序代码按照功能划分为低耦合 高内聚的模块 4 注意 goto 语句的使用 合理使用 goto 语句可以提高代码的运行效率 但 goto 语句的 使用会破坏程序的结构特性 因此 除非确实需要 否则最好不使用 goto 语句 答案 B 真题2 下列叙述中 不符合良好程序设计风格要求的是 2007年9月 A 程序中要有必要的注释 B 输入数据前要有提示信息 C 程序的效率第一 清晰第二 D 程序的可读性好 解析 一般来讲 程序设计风格是指编写程序时所表现出的特点 习惯和逻辑思路 程 序设计风格总体而言应该强调简单和清晰 程序必须是可以理解的 著名的 清晰第一 效 率第二 的论点已成为当今主导的程序设计风格 答案 C Point5Point5Point5Point5 结构化程序设计 结构化程序设计 考点精讲 1 结构化程序设计的主要目的是使程序结构良好 易读 易理解 易维护 它的原则 主要包括 自顶向下 逐步求精 模块化 限制使用 goto 语句 2 结构化程序设计方法可用三种基本结构实现 顺序结构 选择结构 重复结 构 3 在结构化程序设计的具体实施中 要注意把握如下要素 1 使用程序设计语言中的顺序结构 选择结构 循环结构等控制结构来表示程序的控 制逻辑 2 选用的控制结构只准许有一个入口和一个出口 3 程序语句组成容易识别的程序块 每块只有一个入口和一个出口 4 复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现 5 语言中所没有的控制结构 应该采用前后一致的方法来模拟 6 严格控制 goto 语句的使用 真题分析 真题1 下列选项中不属于结构化程序设计原则的是 2009年9月 A 模块化 B 逐步求精 C 可封装 D 自顶向下 解析 结构化程序设计的原则主要包括 自顶向下 逐步求精 模块化 限制 使用 goto 语句 答案 C 真题2 符合结构化原则的三种基本控制结构是 选择结构 循环结构和 3 结构 2009年3月 解析 结构化程序设计的3种基本控制结构是 选择结构 分支结构 循环 结构 顺序结构 答案 顺序 真题3 结构化程序设计的基本原则不包括 2008年4月 A 模块化 B 逐步求精 C 多态性 D 自顶向下 18 解析 结构化程序设计方法的主要原则可以概括为 自顶向下 逐步求精 模块化 和限制使用 GOTO 语句 其中不包括多态性 答案 C 真题4 下列选项中不属于结构化程序设计方法的是 2006年4月 A 模块化 B 可复用 C 自顶向下 D 逐步求精 解析 结构化程序设计方法的主要原则有四点 自顶向下 先从最上层总目标开始设计 逐步使问题具体化 逐步求精 对于复杂问题 设计 一些子目标作为过渡 逐步细化 模 块化 将程序要解决的总目标分解为分目标 再进一步分解为具体的小目标 每个小目标作 为一个模块 限制使用 GOTO 语句 不存在可复用原则 答案 B 真题5 仅由顺序 选择 分支 和重复 循环 结构构成的程序是 4 程序 2010 年9月 解析 本题主要考查结构化程序的基本概念 仅由顺序 选择 分支 和重复 循 环 结构构成的程序是结构化程序 答案 结构化 Point6Point6Point6Point6 面向对象的程序设计方法 面向对象的程序设计方法 考点精讲 1 对象 object 对象用来表示客观世界中的任何实体 面向对象的程序设计方法中涉 及的对象是系统中用来描述客观事物的一个实体 是构成系统的一个基本单位 它由一组表 示其静态特征的属性和它可执行的一组操作组成 2 类 class 和实例 instance 将属性 操作相似的对象归为类 类是具有共同属性 共 同方法的对象的集合 一个具体对象称为类的实例 3 消息 message 面向对象的世界是通过对象与对象间彼此的相互合作来推动的 对 象间的这种相互合作需要一个机制协助进行 这个机制称为消息 消息是一个实例与另一 个实例之间传递的信息 是请求对象执行某一处理或回答某一要求的信息 它统一了数据流 和控制流 19 4 继承 inheritance 继承是面向对象方法的一个主要特征 继承是使用已有的类作为 基础 直接获得已有的性质和特征 建立新类的定义技术 已有的类可以当做基类引用 则 新类可当做派生类引用 5 多态性 polymorphism 对象根据所接受的消息而作出动作 同样的消息被不同的对 象接受时可导致完全不同的行动 该现象称为多态性 真题分析 真题1 在面向对象方法中 不属于 对象 基本特点的是 2008年9月 A 多态性 B 标识唯一性 C 一致性 D 分类性 解析 对象具有如下特征 标识唯一性 分类性 多态性 封装性 模块独立 性 答案 C 真题2 在面向对象方法中 实现信息隐蔽是依靠 2007年9月 A 对象的封装 B 对象的分类 C 对象的继承 D 对象的多态 解析 对象的封装性是指从外部看只能看到对象的外部特征 即只需知道数据的取值范 围和可以对该数据施加的操作 而不需要知道数据的具体 结构以及实现操作的算法 对象 的内部 即处理能力的实行和内部状态 对外是不可见 的 从外面不能直接使用对象的处 理能力 也不能直接修改其内部状态 对象的内部状态只能由其自身改变 答案 A 真题3 在面向对象方法中 2 描述的是具有相似属性与操作的一组对象 2006 年4月 解析 在面向对象方法中 类描述的是具有相似属性与操作的一组对象 答案 类 真题4 在面向对象方法中 类的实例称为 2 2005年4月 解析 类描述的是具有相似性质的一组对象 例如 每本具体的书是一个对 象 而这具体的书都有共同的性质 它们都属于更一般的概念 书 这一类对象 一个具体的对象称为类的实例 答案 对象 20 真题5 下面选项中不属于面向对象程序设计特征的是 2007年3月 A 类比性 B 封装性 C 继承性 D 多态性 解析 向对象程序设计的三个主要特征是 封装性 继承性和多态性 1 封装性即只需知道数据的取值范围和可以对该数据施加的操作 而无需知道 数据的具体结构以及实现操作的算法 2 继承性是指使用已有的类定义作为基础建立新类的定义技术 3 对象根据所接受的消息而做出动作 同样的消息被不同的对象接受时可导致 完全不同的行动 该现象称为多态性 答案 A 真题6 面向对象方法中 继承是指 2010年9月 A 各对象之间的共同性质 B 类之间共亨属性和操作的机制 C 一组对象所具有的相似性质 D 一个对象具有另一个对象的性质 解析 继承性指的是一个新类可以从现有的类中派生出来 新类具有父类中所有的特性 直接继承了父类的操作和属性 同时也允许多个新类继承于一个父类 也可以实现多层继承 可以说继承是类之间共享属性和操作的机制 答案 B Point7Point7Point7Point7 基本排序与查找的算法 基本排序与查找的算法 考点精讲 1 查找 1 顺序查找是一种最基本和最简单的查找方法 它的思路是 从表中的第一个元素开 始 将给定的值与表中逐个元素的关键字进行比较 直 到两者相符 查到所要找的元素为 止 否则就是表中没有要找的元素 查找不成功 对于长度为 n 的有序线性表 在最坏情况 下 顺序查找需要比较 n 次 2 对于大的线性表来说 顺序查找的效率是很低的 虽然顺序查找的效率不高 但在 下列两种情况下也只能采用顺序查找 无序的线性表 即使是有序的线性表 如果采用链式存储结构 也只能顺序查找 21 3 二分查找是针对有序表进行查找的简单 有效而又较常用的方法 其基本思想是 首先选择有序表中间位置的记录 将其关键字 与给定关键字 k 进行比较 若相等 则查找 成功 否则 若 k 值比该关键字值大 则要找的元素一定在表的后半部分 或称右子表 则 继续对右子表进行二分查 找 若 k 值比该关键字值小 则要找的元素一定在表的前半部分 左子表 同样应继续对左子表进行二分查找 每进行一次比较 要么找到要查找的元素 要么将 查找的范围缩小一半 如此递推 直到查找成功或把要查找的范围缩小为空 查找失 败 4 显然 仅当有序线性表为顺序存储时才能用二分查找 并且 二分查找的效率要比 顺序查找高得多 可以证明 对于长度为 n 的有序线性表 在最坏情况下 二分查找只需要 比较 log2n 次 而顺序查找需要比较 n 次 2 排序是指将一个无序序列整理成按值非递减顺序排列的有序序列 常用的排序方法 1 交换类排序法 冒泡排序法 需要比较的次数为 n n 1 2 快速排序法 最坏情况需要比较的次数为 n n 1 2 2 插入类排序法 简单插入排序法 最坏情况需要 n n 1 2次比较 希尔排序法 最坏情况需要 O n1 5 次比较 3 选择类排序法 简单选择排序海最坏情况需要 n n 1 2次比较 堆排序法 最坏情况需要 O nlog2n 次比较 真题分析 真题1 下列排序方法中 最坏情况下比较次数最少的是 2009年3月 A 直接插入排序 B 堆排序 C 冒泡排序 D 简单选择排序 解析 冒泡排序 简单选择排序和直接插入排序法在最坏的情况下比较次数为 n n 1 2 而堆排序法在最坏的情况下需要比较的次数为 O nlog2n 答案 B 真题2 对长度为 n 的线性表排序 在最坏情况下 比较次数不是 n n 1 2的排序方法 是 2008年4月 A 直接插入排序 B 堆排序 C 快速排序 D 冒泡排序 22 解析 排序方法中最坏情况下需要比较的次数分别为 冒泡排序 n n 1 2 快速排序 n n 1 2 简单插入排序 n n 1 2 希尔排序 O n 1 5 简单选择排序 n n 1 2 堆排序 O nlog2n 答案 B 真题3 冒泡排序在最坏情况下的比较次数是 2007年9月 A n n 1 2 B n 2 C n n 1 2 D nlog2n 解析 对 n 个结点的线性表采用冒泡排序 在最坏情况下 冒泡排序需要经过 n 遍的从 前往后的扫描和 n 1 2遍的从后往前的扫描 需要的比较次数为 n n 1 2 答案 A 真题4 对长度为10的线性表进行冒泡排序 最坏情况下需要比较的次数为 1 2006年4月 解析 在冒泡排序中 最坏情况下 需要比较的次数为 n n 1 2 也就是 10 10 1 2 45 答案 45 真题5 对于长度为 n 的线性表 在最坏情况下 下列各排序法所对应的比较次数中 正确的是 2005年4月 A 快速排序为 n B 快速排序为 n n 1 2 C 冒泡排序为 n 2 D 冒泡排序为 n 解析 假设线性表的长度为 n 在最坏情况下 冒泡排序和快速排序需要的比 较次数为 n n 1 2 答案 B 真题6 在长度为 n 的有序线性表中进行二分法查找 最坏情况下需要比较的次数是 2008年9月 A O log2n B O nlog2n C O n D O n 2 解析 对于长度为 n 的有序线性表 在最坏情况下 二分法查找只需比较 log2n 次 而 顺序查找需比较 n 次 答案 A 23 真题7 在长度为64的有序线性表中进行顺序查找 最坏情况下需要比较的次数 为 2006年9月 A 6 B 7 C 63 D 64 解析 在长度为64的有序线性表中 其中的64个数据元素是按照从大到小或从小到大的 顺序排列有序的 在这样的线性表中进行顺序查找 最坏的情况就是查找的数据元素不在线 性表中或位于线性表的最后按照线性表的顺序查找算法 首先用被查找的数据和线性表的第一个数据元素进行比较 若相等 则查找成功 否则 继续进行比较 即和线性表的第二个数据元素进行比较 同样 若相等 则查找成功 否则 继续进行比较 依次类推 直到在线性表中查找到该数据或查找到线性表的最后一个元素 算法才结束 因此 在长度为64的有序线性表中进行顺序查找 最坏的情况下需要比较64次 答案 D 真题8 下列数据结构中 能用二分法进行查找的是 2005年9月 A 二叉链表 B 有序线性链表 C 顺序存储的有序线性表 D 线性链表 解析 二分查找只适用于顺序存储的有序表 在此所说的有序表是指线性表中的元素按 值非递减排列 即从小到大 但允许相邻元素值相等 的 答案 C 真题9 对长度为 n 的线性表进行顺序查找 在最坏情况下所需要的比较次数为 2005年4月 A n B n 1 C log2n D n 2 解析 在长度为 n 的线性表中进行顺序查找 最坏情况下需要比较 n 次 答案 A 真题10 下列叙述中正确的是 2010年3月 A 对长度为 n 的有序链表进行对分查找 最坏情况下需要的比较次数为 log2n B 对长度为 n 的有序链表进行对分查找 最坏情况下需要的比较次数为 nlog2n C 对长度为 n 的有序链表进行查找 最坏情况下需要的比较次数为 n D 对长度为 n 的有序链表进行对分查找 最坏情况下需要的比较次数为 n 2 解析 二分查找要求线性表中的结点必须按关键字值的递增或递减的顺序排序 它首先 把要查找的关键字 K 与中间位置的结点关键字相比较 若 相等 则查找成功 若不相等 则缩小范围 根据关键字与中间结点关键字的比较大小确定下一步查找哪个子表 这样一直 递归下去 直到找到满足条件的结点或者 确认表中没有这样的结点为止 对分查找即二分 法查找 二分法查找只能适用于顺序存储的有序表 答案 C 真题11 在长度为 n 的线性表中 寻找最大项至少需要比较 2 次 2010年9 月 解析 本题我们分两种情况说明 一种是无序的线性表 在这种情况下 要找 n 个数据 中值最大的数据 应该要和其他所有元素进行一次比较才 能确定其值是最大的 如果有一 个元素没比较 那么也不能确定当前元素是值最大的元素 因此至少需要比较的次数是 n 1 次 另一种是有序的线性表 在这种情 况下 不管是升序还是降序线性表 其最大值的位 置都是确定的 无须比较 当然本题考查的应该是第一种情况 因此答案为 n 1 答案 n 1 第第 2 2 2 2 天 软件工程与数据库设计天 软件工程与数据库设计 Point1Point1Point1Point1 数据模型 数据模型 考点精讲 1 数据模型的概念 是数据特征的抽象 从抽象层次上描述了系统的静态特征 动态 行为和约束条件 为数据库系统的信息表与操作提供一个抽象的框架 描述了数据结构 数 据操作及数据约束 2 数据模型分为三种 1 概念数据模型 简称概念模型 是对客观世界复杂事物的结构描述及它们之间的内 在联系的刻画 主要有 E R 模型 扩充的 E R 模 型 面向对象模型及谓词模型等 2 逻 辑数据模型 又称物理模型 是一种面向数据库系统的模型 该模型着重于在数据库系统一 级的实现 主要有 层次模 型 网状模型 关系模型 面向对象模型等 3 物理数据模型 又称物理模型 它是一种面向计算机物理表示的模型 此模型给出 25 了数据模型在计算机上物理结构的表示 3 E R 模型 1 E R 模型的基本概念 实体 现实世界中的事物 属性 事物的特性 联系 现实世界中事物间的关系 2 实体集的关系有一对一 一个学校和一个校长 一对多 学生和宿舍 多对多 老 师与学生 的联系 两个实体集间联系可分为 一对一联系 onetoonerelationship 简记为1 1 一对多联系 onetomanyrelationship 简记为1 m 或 m 1 多对多联系 monytomanyrelationship 简记为 m n 3 E R 模型三个基本概念之间的联接关系 实体是概念世界中的基本单位 属性有属性 域 每个实体可取属性域内的值 一个实体的所有属性值叫元组 4 E R 模型的图示法 实体集表示法 在矩形内写上实体集的名字 属性表示法 在椭圆形内写上属性的名称 联系表示法 用菱形内写上联系的名称 实体集与属性的联接关系 用无向线段来表示 实体集与联系间的联接关系 E R 模型由实体 属性 联系这三个基本概念细成 只 有实体 联系 属性三者结合起来才能表示一个现实世界 4 关系模型 1 在关系模型中 把数据看成一个二维表 每一个二维表称为一个关系 表中的每一 列称为一个属性 相当于记录中的一个数据项 对属性的命名称为属性名 表中的一行称为 一个元组 相当于记录值 2 在二维表中凡能唯一标识元组的最小属性称为键或码 从所有侯选健中选取一个作 为用户使用的键称主键 表 A 中的某属性是某表 B 的键 则称该属性集为 A 的外键或外码 3 关系中的数据约束 实体完整性约束 约束关系的主键中属性值不能为空值 参照完全性约束 是关系之间的基本约束 用户定义的完整性约束 它反映了具体应用中数据的语义要求 4 关系模型的数据操作即是建立在关系上的数据操作 一般有查询 增加 删除和修 改四种操作 真题分析 真题1 在 E R 图中 用来表示实体联系的图形是 2009年9月 A 菱形 B 三角形 C 椭圆形 D 矩形 26 解析 在 E R 图中 用矩形表示实体集 用椭圆形表示属性 用菱形 内部写 上联系名 表示联系 答案 A 真题2 在 E R 图中 图形包括矩形框 菱形框 椭圆框 其中表示实体联系的是 5 框 2009年3月 解析 在 E R 图中 用菱形框来表示实体之间的联系 矩形框表示实体集 椭 圆形框表示属性 答案 菱形 真题3 将 E R 图转换为关系模式时 实体和联系都可以表示为 2009年 3月 A 关系 B 域 C 属性 D 键 解析 将 E R 图转换为关系模式时 实体和联系都可以表示为关系 答案 A 真题4 一间宿舍可住多个学生 则实体宿舍和学生之间的联系是 2008 年9月 A 多对一 B 多对多 C 一对一 D 一对多 解析 两个实体集间的联系可以有下面几种 一对一的联系 一对多或多对一 联系 多对多 由于一个宿舍可以住多个学生 但一个学生只能住在一个宿 舍 所以它们的联系是一对多联系 答案 D 真题5 在 E R 图中 矩形表示 5 2007年9月 解析 矩形表示实体 椭圆形表示属性 菱形表示联系 答案 实体 Point2Point2Point2Point2 软件定义阶段 软件定义阶段 考点精讲 1 软件定义阶段 包括制定计划与需求分析 可行性研究与计划制定 确定总目标 可行性研究 探讨解决方案 制定开发计划 2 需求分析 对待开发软件提出的需求进行分析并给出详细的定义 主要工作是编写 软件需求规格说明书及用户手册 1 需求分析的任务是导出目标系统的逻辑模型 解决 做什么 的问题 2 需求分析一般分成4个阶段 需求获取 需求分析 编写需求规格说明书 需求评审 3 软件需求规格说明书 SRS 是需求分析阶段的最后成果 是软件开发中的重要文 档之一 该说明把在软件计划中确定的软件范围加 以展开 制定出完整的信息描述 详细 的功能说明 恰当的检验标准以及其他与要求有关的数据 其特点有 正确性 无岐义 性 完整性 可验证性 一 致性 可理解性 可追踪性 4 需求分析的方法 结构化分析方法 包括面向数据流的结构化分析方法 SA 面向数据结构的 Jackson 方法 JSD 和面向数据结构的结构化数据系统开发方法 DSSD 面向对象的分析的方法 OOA 从需求分析建立的模型的特性来分 静态分析和动 态分析 3 结构化方法的核心和基础是结构化程序设计理论 结构化分析方法的实质 面向数 据流 自顶向下 逐层分解 建立系统的处理流程 以数据流图和数据字典为主要工具 建 立系统的逻辑模型 数据字典是结构化分析的核心 1 结构化分析的常用工具有 数据流图 数据字典 判定树 判定表 2 数 据流图 DFD 描述数据处理过程的工具 是 需求理解的逻辑模型的图形表示 它直接支 持系统功能建模 建立数据流图的步骤 由外向里 自顶向下 逐层分解 完善求精 数据 流图的主要图形元素 椭圆 代表加工 转换 输入数据经加工变换产生输出 箭头 代表数据流 沿箭头方向传送数据的通道 一般在旁边标注数据流名 双横线 代表存储文件 数据 表示处理过程中存入各种数据的文件 矩形 代表源 潭 表示系统和环境的接口 属系统之外的实体 3 数据字典 是结构化分析的核心 是对所有与系统相关的数据元素的一个有组织的 列表 以及精确的 严格的定义 使得用户和系统分析员对于输入 输出 存储成分和中间 计算结果有共同的理解 概括地说 数据字典是对 DFD 中出现的被命名的图形元素的确切 解释 4 判定树 是从问题定义的文字描述中分清哪些是判定的条件 哪些是判定的结论 根据描述材料中的连接词找出判定条件之间的从属关系 并列关系 选择关系 根据它们构 造判定树 5 判定表 与判定树相似 当数据流图中的加工要依赖于多个逻辑条件的取值 即完 成该加工的一组动作是由于某一组条件取值的组合而引发的 使用判定表描述比较适宜 真 题分析 真题1 数据流图中带有箭头的线段表示的是 2008年9月 A 模块调用 B 数据流 C 控制流 D 事件驱动 解析 数据流图是从数据传递和加工的角度 来刻画数据流从输入到输出的移动变换过 程 其中 带箭头的线段表示数据流 沿箭头方向传递数据的通道 一般在旁边标注数据流 名 答案 B 真题2 在软件开发中 需求分析阶段可以使用的工具是 2008年9月 A PAD 图 B 程序流程图 C N S 图 D DFD 图 解析 在软件开发中 需求分析阶段常使用的工具有数据流图 DFD 数据字典 DD 判断树和判断表 答案 D 真题3 在结构化分析使用的数据流图 DFD 中 利用 5 对其中的图形元素 进行确切解释 2007年3月 解析 数据字典 DataDictionary 简称 DD 的作用是对 DFD 中出现的被命名图形元素进 行确切解释 通常数据字典包含的信息有名称 别名 何处使用 如何使用 内容描述 补 充信息等 答案 数据字典 真题4 数据流程图 DFD 图 是 2010年3月 A 结构化方法的需求分析工具 B 面向对象方法的需求分析工具 C 软件概要设计的工具 D 软件详细设计的工具 解析 数据流图 DataFlowDiagram DFD 用来描绘系统的逻辑模型 它以图形的方式 描绘数据在系统中流动和处理的过程 反映系统必须完成的逻辑功能 DFD 是结构化分析 的工具 结构化分析是需求分析的一种方法 答案 A Point3Point3Point3Point3 关系代数 关系代数 考点精讲 1 关系模型的基本运算 并 差 交 广义笛卡尔积 投影 选择 连接 除 关系 是有序组的集合 可将关系操作看成是集合的运算 2 并 差 交 1 并运算 R S 2 差运算 R S 3 交运算 交运算是将两个关系中共有元组表示为 R S 3 广义笛卡尔积 除 1 广义笛卡尔积 笛卡儿积运算 两个关系的合并操作可用笛卡儿积表示 设有 n 元 关系 R 及 m 元关系 R 它们分别有 p q 个元组 则 R 与 S 的笛卡儿积为 R S 该关系是 一个 n m 元关系 元组个数是 p q 2 除运算 将一个关系中元组去除另一个关系中元组 表示为 R S 4 投影运算 投影运算是一个一元运算 一个关系通过投影运算后仍为一个关系 R R 是这样一个关系 它是 R 中投影运算所指出的那些域的列所组成的关系 5 选择运算 选择运算是一个一元运算 关系 R 通过选择运算后仍为一个关系 这 个关系是由 R 中那些满足逻辑条件的元组所组成 6 连接运算 真题分析 真题1 有如下三个关系 R S 和 T 有如下三个关系 R S 和 T 其中关系 T 由关系 R 和 S 通过某种操作得到 该操作为 2009年9月 A 交 B 并 C 选择 D 投影 解析 给定两个相同类型的关系 A 和 B 两者的并是相同类型的一个关系 关系的主 体由出现在 A 中或 B 中或同时出现在两者之中的所有元组组成 答案 B 真题2 有两个关系 R S 如下 有两个关系 R S 如下 由关系 R 通过运算得到关系 S 则所使用的运算为 2009年3月 A 插入 B 连接 C 选择 D 投影 解析 一个关系 R 通过投影运算后仍为一个关系 R R 是由 R 中投影运算所指出的那 些域的列所组成的关系 所以题目中关系 s 是由关系 R 经过投影运算所得 选择运算主要 是对关系 R 中选择由满足逻辑条件的元组所组成的一个新关系 答案 D 真题3 有三个关系 R S 和 T 如下 有三个关系 R S 和 T 如下 由关系 R 和 S 通过运算得到关系 T 则所使用的运算为 2008年9月 A 并 B 自然连接 C 笛卡尔积 D 交 解析 在实际应用中 最常用的连接是自然连接的特例 它满足下面的条件 两关系 间有公共字段 通过公共字段的相等值进行连接 通过观察二个关系 R S T 的结果可知 关系 T 是由关系 R 和 S 进行自然连接得到的 答案 B 真题4 在下列关系运算中 不改变关系表中的属性个数但能减少元组个数的是 2007年3月 A 投影 B 笛卡儿乘积 C 并 D 交 解析 关系 R 与 S 经交运算后所得到的关系是由那些既在 R 内又在 S 内的有序组所组 成 记为 R S 形式 定义如下 R S t R t S R R S 所以不改变关系表中的属性 个数 但能减少元组个数的是关系之间的交操作 答案 D Point4Point4Point4Point4 软件设计阶段 软件设计阶段 考点精讲 1 软件设计是软件工程的重要阶段 是一个把软件需求持换为软件表示的过程 软件 设计的基本目标是用比较抽象慨括的方式确定目标系统如何完成预定的任务 即软件设计是 确定系统的物理模型 1 需求分析主要解决 做什么 问题 软件设计解决 怎么做 的问题 从技术观点来看 软件设计包括软件结构设计 数据设计 接口设计 过程设计 结构设计 定义软件系统各主要部件之间的关系 数据设计 将分析时创建的模型转化为数据结构的定义 接口设计 描述软件内部 软件和协作系统之间以及软件与人之间如何通信 过程设计 把系统结构部件转换成软件的过程描述 2 从工程管理角度来看 软件设计包括 概要设计和详