计算机软件基础知识

(共41张PPT)
第2章 程序设计基础
内容提要
程序设计方法与风格
结构化程序设计
面向对象的程序设计方法，对象、方法、属性及继承与多态性
2.1 程序设计方法与风格
2.1.1 程序设计方法
结构化设计方法
模块内部程序各部分要按照自顶向下的结构划分
各程序部分应按功能组合
各程序之间的联系尽量通过调用子程序来实现，不用或少用GOTO方式
面向对象程序设计方法
2.1.2 程序设计风格
原则：清晰第一，效率第二
1. 源程序中的内部文档
符号名的命名：有一定实际含义
程序的注释：
序言性注释
功能性注释
程序的视觉组织：层次清晰
2. 数据说明
数据说明的次序规范化
说明语句中变量安排有序化
使用注释来说明复杂数据的结构
2.1.2 程序设计风格（续）
3．语句的结构
在一行内只写一条语句
程序编写应优先考虑清晰性
清晰第一，效率第二
在保证程序正确的基础上再要求提高效率
避免使用临时变量前使程序的可读性下降
避免不必要的转移
尽量使用库函数
避免采用复杂的条件语句
尽量减少使用“否定”条件语句
数据结构要有利于程序的简化
要模块化，使模块功能尽可能单一化
利用信息隐蔽，确保每一个模块的独立性
从数据出发去构造程序
不要修补不好的程序，要重新编写
2.1.2 程序设计风格（续）
4．输入和输出
对输入数据检验数据的合法性
检查输入项的各种重要组合的合理性
输人格式要简单，使得输入的步骤和操作尽可能简单
输人数据时，应允许使用自由格式
应允许缺省值
输入一批数据时，最好使用输入结束标志
在以交互式输入/输出方式进行输人时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中和输入结束时，应在屏幕上给出状态信息
当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式
3.2 结构化程序设计
基本思想
关于GOTO语句
工程思想
结构化思想
自顶向下，逐步求精，模块化，限制使用GOTO语句
2.2.1 结构化程序设计的原则
1．自顶向下
2．逐步求精
3．模块化
4．限制使用GOTO语句
2.2.2 结构化程序的基本结构与特点
三种基本结构
顺序结构
选择结构
重复结构
2.2.2 结构化程序的基本结构与特点(续)
顺序结构
2.2.2 结构化程序的基本结构与特点(续)
选择结构
又称分支结构
简单选择结构
多分支选择结构
2.2.2 结构化程序的基本结构与特点(续)
重复结构
又称为循环结构
当型
直到型
2.2.2 结构化程序的基本结构与特点(续)
特点
关系清晰、易读、易理解性好、易维护。
“自顶向下、逐步细化”，提高效率，降低成本
2.2.3 结构化程序设计原则和方法的应用
用有限的控制结构
一个入口和一个出口
每块只有一个入口和一个出口
使用嵌套
前后一致
避免GOTO语句
2.3 面向对象的程序设计
2.3.1 关于面向对象方法
对系统的复杂性进行概括、抽象和分类，使软件的设计与现实形成一个由抽象到具体、由简单到复杂这样一个循序渐进的过程，从而解决大型软件研制中存在的效率低、质量难以保证、调试复杂、维护困难等问题。
结构化的分解突出过程，即如何做(How to do) 它强调代码的功能是如何实现的；面向对象的分解突出现实世界和抽象的对象，即做什么(What to do)
2.3.1 关于面向对象方法（续）
主要优点
与人类习惯的思维方法一致
稳定性好
可重用性好
易于开发大型软件产品
可维护性好
2.3.2 面向对象方法的基本概念
1.对象(Object)
对象是基本的运行时认得实体，它既包括数据（属性），也包括作用于数据的操作（行为）。
一个对象把属性和行为封装为一个整体
一个对象通常可由对象名、属性和操作3部分组成
2.3.2 面向对象方法的基本概念（续）
对象特点
标识惟一性
分类性
多态性
封装性
模块独立性好
2.3.2 面向对象方法的基本概念（续）
2．类和实例
类是具有共同属性、共同操作方法的对象的集合，是对象的抽象
对象是其对应类的一个实例
2.3.2 面向对象方法的基本概念（续）
3．消息
对象之间进行通信的机制
三部分组成
接收消息的对象的名称
消息标识符（消息名）
零个或多个参数
2.3.2 面向对象方法的基本概念（续）
4.继承
继承是父类和子类之间共享数据的方法的机制
一个子类可以继承它的父类（或祖先类）中的属性和操作
子类中可以定义自己的属性和操作
单重继承、多重继承
2.3.2 面向对象方法的基本概念（续）
5.多态性
不同的对象收到同一消息可以产生完全不同的结构，这一现象叫做多态性
优点：灵活性、可重用性、可扩充性。
典型考题分析
2.4 典型考题分析
【例2-1】从程序设计方法和技术的发程序角度来说，程序设计主要经历了结构化设计和_____的程序设计阶段。
答案 面向对象
2.4 典型考题分析
【例2-2】对建立良好的程序设计风格，下面描述正确的是______。
A）程序应简单、清晰、可读性好
B）符号名的命名只要符合语法
C）充分考虑程序的执行效率
D）程序的注释可有可无
答案 A
2.4 典型考题分析
【例2-3】源程序的文档化不包括_________。
A）符号名的命名要有实际意义
B）正确的文档格式
C）良好的视觉组织
D）正确的程序注释
答案 D
2.4 典型考题分析
【例2-4】注释一般为序言性注释和_______注释。
答案 功能性
2.4 典型考题分析
【例2-5】在设计程序时，应采纳的原则之一是_______。
A）程序结构应有助于读者理解
B）不限制GOTO语句的使用
C）减少或取消注解行
D）程序越短越好
答案 A
2.4 典型考题分析
【例2-6】下列选项中不属于结构化程序设计方法的是__________。（2006年4月）
A）自顶向下
B）逐步求精
C）模块化
D）可复用
答案 D
2.4 典型考题分析
【例2-7】下列选项不符合良好程序设计风格的是__________。（2006年9月）
A）源程序要文档化
B）数据说明的次序要规范化
C）避免滥用 GOTO 语句
D）模块设计要保证高耦合、高内聚
答案 D
2.4 典型考题分析
【例2-8】结构化程序设计的三种基本控制结构是__________。
A）过程、子程序和分程序
B）顺序、选择和重复
C）递归、堆栈和队列
D）调用、返回和转移
答案 B
2.4 典型考题分析
【例2-9】结构化程序设计主要强调的是__________。
A）程序的规模
B）程序的易读性
C）程序的执行效率
D）程序的可移植性
答案 B
2.4 典型考题分析
【例2-10】关于结构化程序设计原则和方法的描述错误的是__________。
A）选用的控制结构只准许有一个入口和一个出口
B）复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现
C）不允许使用GOTO语句
D）语言中所没有的控制结构，应该采用前后一致的方法来模拟
答案 C
2.4 典型考题分析
【例2-11】采用面向对象技术开发的应用系统的特点是________。
A）重用性更强
B）运行速度更快
C）占用存储量小
D）维护更复杂
答案 A
2.4 典型考题分析
【例2-12】在面向对象方法中，类的实例称为________。（2005年4月）
答案 对象
2.4 典型考题分析
【例2-13】消息传递是对象间通信的手段，一个对象通过向另一个对象发送消息来请求其服务。一个消息通常包括_______。
A）接收消息的对象的名称、消息标识符和必要的参数
B）接收消息的对象的名称和消息标识符
C）发送消息的对象的名称、调用的接收方的操作名和必要的参数
D）消息标识符
答案 A
2.4 典型考题分析
【例2-14】一个对象在收到消息时，要予以响应。不同的对象收到同一消息可以产生完全不同的结果，这一现象叫做对象的__________。
A）继承性
B）多态性
C）抽象性
D）封装性
答案 B
2.4 典型考题分析
【例2-15】在面向对象程序设计中，从外面看只能看到对象的外部特征，而不知道也无需知道数据的具体结构以及实现操作的算法，这称为对象的______。
答案 封装性
2.4 典型考题分析
【例2-16】使用已经存在的类作为基础建立新类的定义，这种技术叫做类的________。
答案 继承
2.4 典型考题分析
【例2-17】一个类允许有多个父类，这种继承称为________。
答案 多重继承(共80张PPT)
第4章 数据库设计基础
内容提要
数据库的基本概念：数据库，数据库管理系统，数据库系统。
数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。
关系代数运算，包括集合运算及选择、投影、连接运算。
数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。
4.1 数据库系统的基本概念
4.1.1 数据、数据库、数据库管理系统(续)
1．数据
数据
描述事物的符号记录，用物理符号记录下来的可以鉴别的信息
物理符号：数字、文字、图形、图像声音及其他特殊符号。
多种表现形式：数字化
计算机中数据分为两部分：
临时性数据
持久性数据
数据有型（Type）与值（Value）之分
型：数据表示的类型，如整型、实型、字符型等
值：给出了符合给定型的值
4.1.1 数据、数据库、数据库管理系统(续)
2．数据库
数据库——Database，简称DB
数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序所共享
按数据所提供的数据模式存放的
特点：
较小的冗余度
较高的数据独立性
易扩展性
为多个用户所共享
4.1.1 数据、数据库、数据库管理系统(续)
3．数据库管理系统
数据库管理系统——Database Management System，简称DBMS
数据库的管理机构，职能是有效地组织、存储、获取和管理数据，接受及完成用户提出的访问数据的各种请求
数据库系统的核心
DBMS的功能
数据模式定义
数据存取的物理构建
数据操纵。
数据的完整性、安全性定义与检查
数据库的并发控制与故障恢复
数据的服务
4.1.1 数据、数据库、数据库管理系统(续)
3．数据库管理系统
数据库语言
数据定义语言DDL
数据操纵语言DML
数据控制语言DCL
数据语言的使用
交互式命令语言
宿主型语言
常见的DBMS
ORACLE、Sybase的PowerBuilder、IBM的DB2、微软的SQL Server
微软的Visual FoxPro、Access，功能简单
4.1.1 数据、数据库、数据库管理系统(续)
4．数据库管理员
数据库管理员——Database Administrator，简称DBA
对数据库的规划、设计、维护、监视等的人员
其主要工作有：
数据库设计
数据库维护
改善系统性能，提高系统效率
4.1.1 数据、数据库、数据库管理系统(续)
5．数据库系统
数据库系统——Database System，简称DBS
拥有数据库技术支持的计算机系统
实现有组织地、动态地存储大量相关数据，提供数据处理和资源共享服务
组成：
数据库（数据）
数据库管理系统（软件）
数据库管理员（人员）
用户
4.1.1 数据、数据库、数据库管理系统(续)
6．数据库应用系统
数据库应用系统——Database Application System，简称DBAS
组成：数据库系统+应用软件+应用界面
4.1.2 数据库系统的发展
人工管理阶段
4.1.2 数据库系统的发展
文件系统阶段
4.1.2 数据库系统的发展
数据库系统阶段
4.1.3 数据库系统的基本特点
数据的集成性
数据的高共享性与低冗余性
数据独立性
物理独立性
逻辑独立性
数据统一管理与控制
数据的完整性检查：
数据的安全性保护
并发控制
4.1.4 数据库系统的内部结构体系
三级模式
概念级模式
内部级模式
外部级摸式
二级映射
概念级到内部级的映射
外部级到概念级的映射
4.1.4 数据库系统的内部结构体系
l．数据库系统的三级模式
概念级模式
数据库中全体数据逻辑结构和特征的描述，是所有用户的公共数据视图
一个数据库只有一个概念模式
内部级模式
又称物理模式
数据库物理存储结构与物理存取方法
对一般用户是透明的，直接影响数据库的性能
一个数据库只有一个内模式。
外部级摸式
也称子模式或用户模式
数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述
用户的数据视图
一个数据库可以有多个外模式
4.1.4 数据库系统的内部结构体系
2．数据库系统的两级映射
概念模式／内模式的映射
存在于概念级和内部级之间
实现了概念模式到内模式之间的相互转换
保证数据具有很高的物理独立性
外模式／概念模式的映射：
存在于外部级和概念级之间
实现了外模式到概念模式之间的相互转换
保证数据具有较高的逻辑独立性
4.2 数据模型
4.2.1 数据模型的基本概念
数据模型，是对现实世界中数据的模拟和抽象。
数据模型的分类
概念模型：现实世界在人脑中的反映；
逻辑模型：按计算机系统的观点对数据建模；
物理模型：反映数据的存储结构。
数据模型的组成要素
数据结构：所研究的对象类型的集合；
数据操作：对数据库中各种对象的值允许执行操作的集合；
数据的约束条件：一组完整性规则的集合。
4.2.2 E-R模型
1.基本概念
实体
属性
联系
一对一（1：1）
一对多（1：M或M：1）
多对多（M：N）
2.三个基本概念之间的联接关系
实体集与属性间的联接关系
实体与联系
4.2.2 E-R模型
3．E-R型的图示法
实体集：用矩形表示，矩形框内写明实体名。
属性：用椭圆形表示，并用无向边将其与相应的实体连接起来。
联系：用菱形表示，实体集与属性间的联接关系：用无向线段表示
4.2.3 层次模型
一种树形结构
数据结构比较简单，操作简单
对于实体间联系是固定的、且预先定义好的应用系统，有较高的性能
可以提供良好的完整性支持
不适合表示非层次性的联系，对于插入和删除操作的限制比较多
4.2.4 网状模型
一个不加任何条件限制的无向图
优于层次模型
使用时设计系统内部的物理因素较多，用户操作不方便，其数据模式与系统实现不甚理想
4.2.5 关系模型
1．关系的数据结构
学号 姓名 性别 出生年月 籍贯
20054102 张洁然 男 07-07-87 上海
20054103 李一明 男 05-01-86 安徽合肥
20069301 王文燕 女 11-06-88 山东青岛
20069302 刘 宏 男 10-17-87 江苏南京
属性
元组
表框架
4.2.5 关系模型
主要术语
关系：一个关系就是一张二维表
元组：表中的一行
属性：表中的一个列
属性域：属性的取值范围
分量：元组中的一个属性值
主码：唯一地标识表中一个元组，主码属性不能取空值
外部关键字：与另一个关系的关键字相对应的属性组
关系模式：对一个关系的结构描述
关系名( 属性1, 属性2, ...... , 属性n )
4.2.5 关系模型
关系的性质
元组个数有限性
元组的惟一性
元组的次序无关性
元组分量的原子性
属性名惟一性
属性的次序无关性
分量值域的同一性
4.2.5 关系模型
2．关系操纵
数据查询
数据删除
数据插入
数据修改
4.2.5 关系模型
3．数据完整性约束
实体完整性约束
主键中属性值不能为空值
参照完整性约束
实体及实体间的联系
用户定义的完整性约束
具体应用要求来定义的约束条件
4.3 关系代数
4.3 关系代数
1.关系模型的基本操作
四种基本操作
插入、删除、修改和查询
进一步分解成六种基本操作
关系的属性指定
关系的元组的选择
两个关系的合并
关系的查询
关系元组的插入
关系元组的删除
4.3 关系代数
2．传统的集合运算
关系代数是以对关系的集合运算为基础，分为传统的集合运算和专门的关系运算，其运算对象是关系，运算结果也是关系。
传统的集合运算包括并、交、差、广义笛卡尔积四种运算。其中并、交、差要求参与运算的两个关系的属性个数相同，且相应的属性出自同一个域；广义笛卡尔积则无此限制。
4.3 关系代数
（1）并（Union）
关系R和S具有相同的关系模式，R和S的并是由属于R或属于S的元组构成的集合。可表示为：
（2）差（Difference）
关系R和S具有相同的关系模式，R和S的差是由属于R但不属于S的元组构成的集合。可表示为：
4.3 关系代数
（3）交（Intersection）
关系R和S具有相同的关系模式，R和S的交是由属于R且属于S的元组构成的集合。可表示为：
（4）广义笛卡尔积
设关系R和S的属性个数分别为n、m，则R和S的广义笛卡尔积是一个有（n+m）列的元组的集合。每个元组的前n列来自R的一个元组，后m列来自S的一个元组，记为R×S。
4.3 关系代数
例：有两个关系R和S，分别进行并、差、交和广义笛卡尔积运算。
4.3 关系代数
3．专门的关系运算
（1）选择（Selection）
在关系中选择满足某些条件的元组，即消去某些行，可表示为：
（2）投影（Projection）
在关系中选择某些属性列，即消去某些列，可表示为：
4.3 关系代数
例：在学生关系中
查询1980年以后出生的学生名单，表达式为：
查询所有学生的“姓名”、“性别”，表达式为：
4.3 关系代数
（3）连接（Join）
当一个查询需要来自两个或多个关系的数据时就要用连接操作。连接是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。可表示为：
其含义是，从关系R和S的广义笛卡尔积R×S中选取R关系在A属性组上的值与S关系在B属性组上的值满足比较关系θ的元组。
1）等值连接：当连接条件中的比较运算符θ为“=” 。可表示为：
2）自然连接：要求连接时两个关系中进行相等比较的分量必须是相同属性组，且在结果中将相同的属性列去掉。即若关系R和S具有相同属性组B，则自然连接可记作：
4.3 关系代数
例如，有两个关系R和S
关系T：条件为“R.学号>S.学号”的连接运算
关系U：条件为“R.学号=S.学号”的等值连接
关系V：进行自然连接
4.3 关系代数
4.3 关系代数
（4）除（Division）
笛卡尔乘积的逆运算
4.4 数据库设计与管理
4.4.1 数据库设计概述
设计一个能满足用户要求，性能良好的数据库
基本任务：根据用户对象的信息需求、处理需求和数据库的支持环境设计出数据模式
两种方法：
以信息需求为主，兼顾处理需求（面向数据的方法）
以处理需求为主，兼顾信息需求（面向过程的方法）
面向数据的设计方法已成为主流方法
4.4.1 数据库设计概述
一般采用生命周期法，分若干阶段
需求分析阶段
概念设计阶段
逻辑设计阶段
物理设计阶段
编码阶段
测试阶段
运行阶段
进一步修改阶段
在数据库设计中采用前四个阶段，并且重点以数据结构与模型的设计为主线
4.4.2 数据库设计的需求分析
任务：通过详细调查现实世界要处理的对象，充分了解原系统的工作概况，明确用户的各种需求，然后在此基础上确定新系统的功能
重点：是“数据”和“处理”
方法：结构化分析方法、和面向对象的方法
对数据库设计来讲，数据字典是进行详细的数据收集和数据分析所获得的主要结果
数据字典是在需求分析阶段建立，在数据库设计过程中不断修改、充实、完善的
4.4.3 数据库概念设计
概念设计的方法
集中式模式设计法
视图集成设计法
数据库概念设计的过程
选择局部应用
视图设计：
三种方法：自顶向下、由底向上、由内向外
视图集成:解决局部设计中的冲突
命名冲突
概念冲突
域冲突
约束冲突
4.4.4 数据库的逻辑设计
任务
概念模型进一步转化成相应的数据模型
主要步骤
从E-R图向关系模式转换
逻辑模式规范化及调整、实现
关系视图设计
4.4.5 数据库的物理设计
主要目标:
对数据库内部物理结构作调整并选择合理的存取路径，提高数据库访问速度及有效利用存储空间
物理设计的内容:
索引设计
集簇设计
分区设计
4.4.6 数据库管理
数据库的建立
数据模式的建立
数据加载
数据库的调整
数据库的重组
数据库安全性控制与完整性控制
数据库的故障恢复
数据库监控
典型考题分析
【例4-1】数据库技术的根本目标是要解决数据的______。（2006年9月）
A）存储问题
B）共享问题
C）安全问题
D）保护问题
答案 B
【例4-2】数据库DB，数据库系统DBS，数据库管理系统DBMS之间的关系是______。（2006年4月）
A）DB包含DBS和DBMS
B）DBMS包含DB和DBS
C）DBS包含DB和DBMS
D）没有任何关系
答案 C
【例4-3】数据库系统的核心是______。（2005年9月）
A）数据模型 B）数据库管理系统
C）数据库 D）数据库管理员
答案 B
【例4-4】DBA是数据库系统的一个重要组成，有很多职责。以下选项不属于DBA职责的是______。
A）定义数据库的存储结构和存取策略
B）定义数据库的结构
C）定期对数据库进行重组和重构
D）设计和编写应用系统的程序模块
答案 D
【例4-5】数据管理技术发展过程经过人工管理、文件系统和数据库系统三个阶段，其中数据独立性最高的阶段是______。（2005年9月）
答案 数据库系统
【例4-6】数据独立性是数据库技术的重要特点之一。所谓数据独立性是指______。（2005年4月）
A）数据与程序独立存放
B）不同的数据被存放在不同的文件中
C）不同的数据只能被对应的应用程序所使用
D）以上三种说法都不对
答案 D
【例4-7】数据独立性分为逻辑独立性与物理独立性，当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为______。（2006年4月）
答案 物理独立性
【例4-8】在数据库系统中，用户所见的数据模式为______。（2006年9月）
A）概念模式
B）外模式
C）内模式
D）物理模式
答案 B
【例4-9】数据库中对全部数据的整体逻辑结构的描述，作为数据库的______。
A）内模式
B）外模式
C）概念模式
D）子模式
答案 C
【例4-10】数据库的3级模式之间存在映射关系正确的是______。
A）外模式/内模式
B）外模式/概念模式
C）外模式/外模式
D）概念模式/概念模式
答案：B
【例4-11】数据库三级模式体系结构的划分，有利于保持数据库的______。
答案 数据独立性
【例4-12】用树形结构表示实体之间联系的模型是______。（2005年4月）
A）关系模型
B）网状模型
C）层次模型
D）以上三个都是
答案 C
【例4-13】“商品”与“顾客”两个实体集之间的联系一般是______。（2006年4月）
A）一对一
B）一对多
C）多对一
D）多对多
答案 D
【例4-14】在E-R图中，用来表示实体的图形是______。（2006年4月）
A）矩形
B）椭圆形
C）菱形
D）三角形
答案 A
【例4-15】在下面列出的数据模型中，______是概念数据模型。
A）关系模型 B）层次模型
C）网状模型 D）实体-联系模型
答案 D
【例4-16】在关系模型中，把数据看成是二维表，每一个二维表称为一个______。（2006年4月、2005年4月）
答案 关系
【例4-17】一个关系表的行称为______。（2006年9月）
答案 元组
【例4-18】如果在一个关系中，存在多个属性（或属性组）都能用来惟一标识该关系的元组，且其任何子集都不具有这一特性。这些属性（或属性组）都被称为该关系的______。
A）连接码
B）主码
C）外码
D）候选码
答案 D
【例4-19】设属性A是关系R的主属性，则属性A不能取空值（NULL）。这是______。
A）实体完整性规则
B）参照完整性规则
C）用户定义完整性规则
D）域完整性规则
答案 A
【例4-20】设有如下三个关系表
下列操作中正确的是______。（2006年9月）
A）T=R∩S B）T=R∪S
C）T=R×S D）T=R/S
答案 C
【例4-21】设有如下关系表:
则下列操作中正确的是______。（2005年9月）
A）T＝R∩S B）T＝R∪S
C）T＝R×S D）T＝R/S
答案 B
【例4-22】设关系R是4元关系，关系S是一个5元关系，关系T是R与S的笛卡尔积，即T=R×S，则关系T是______元关系。
A）9 B）11
C）20 D）40
答案 A
【例4-23】关系数据库管理系统能实现的专门关系运算包括______。
A）排序、索引、统计
B）选择、投影、连接
C）关联、更新、排序
D）显示、打印、制表
答案 B
【例4-24】下列关系运算中，______不要求关系R和S具有相同的属性个数。
A）R∪S B）R∩S
C）R－S D）R×S
答案 D
【例4-25】数据库设计的四个阶段是：需求分析、概念设计、逻辑设计和______。（2006年9月）
A）编码设计
B）测试阶段
C）运行阶段
D）物理设计
答案 D
【例4-26】在数据库设计中，将E-R图转换成关系模型的过程属于______。
A）需求分析阶段
B）逻辑设计阶段
C）概念设计阶段
D）物理设计阶段
答案 B
【例4-27】数据字典是数据设计需求分析阶段的最重要的工具之一，其最基本功能是______。
A）数据库定义
B）数据通信
C）数据定义
D）数据维护
答案 C
【例4-28】将E-R图转换到关系模式时，实体与联系都可以表示成______。
A）属性 B）关系
C）键 D）域
答案 B
【例4-29】在关系数据库设计中，设计视图（View）是______阶段的工作。
A）需求分析
B）物理设计
C）逻辑设计
D）概念设计
答案 C
【例4-30】设计数据库的存储结构属于数据库的______。
A）需求分析
B）概念设计
C）逻辑设计
D）物理设计
答案 D(共118张PPT)
二级公共基础知识
第一章 数据结构基础
内容提要
算法:算法的基本概念、算法复杂度
数据结构的基本概念：什么是数据结构、 数据结构的图形表示、 线性结构与非线性结构
线性表及其顺序存储结构：线性表的基本概念、 顺序存储结构、插入运算、删除运算
栈和队列：栈及其基本运算、队列及其基本运算
线性链表：基本概念、基本运算、循环链表及其基本运算
树与二叉树：树的基本概念、二叉树及其基本性质、 二叉树的存储结构、二叉树的遍历
查找技术： 顺序查找、二分法查找
排序技术：交换类排序法、 插入类排序法、选择类排序法
1.1 算法
1.1.1 算法的基本概念
算法是解题方案的准确而完整的描述，它不等于程序，也不等计算方法。
1．算法的基本特征
可行性(effectiveness)
确定性(definiteness)
有穷性(finiteness)
拥有足够的情报
2．算法的基本要素
算法中对数据的运算和操作
算术运算:包括加、减、乘、除等）
逻辑运算:包括“与”、“或”、“非”等运算）
关系运算:包括“大于”、“小于”、“等于”、“不等于”等）
数据传输:包括赋值、输入、输出等操作
算法的控制结构
1.1.1 算法的基本概念
3．算法设计的基本方法
列举法
归纳法
递推
递归
减半递推技术
回溯法
1.1.2 算法复杂度
算法复杂度：时间复杂度、空间复杂度
1．算法的时间复杂度
执行算法所需要的计算工作量
与下列因素有关：
书写算法的程序设计语言
编译产生的机器语言，代码质量
机器执行指令的速度
问题的规模
1.1.2 算法复杂度
问题的规模函数
算法的工作量=f(n)
算法中基本操作重复执行的频率T(n)，是问题规模n的某个函数f(n)，记作：
T(n)=O(f(n))
记号“O”读作“大O”。表示随问题规模n的增加，算法执行时间的增长率和f(n)相应增加。
常见算法复杂度：
O(1)：常数阶 O(n)：作线性阶 O(n2)：平方阶
O(n3)：立方阶 O(logn)：对数阶 O(2n)：指数阶
1.1.2 算法复杂度
n×n矩阵相乘算法：
时间复杂度为O(n3)。
1.1.2 算法复杂度
分析算法的工作量两种方法：
平均性态
最坏情况复杂性
1.1.2 算法复杂度
2．算法的空间复杂度
算法执行过程中所需的最大存储空间
存储量包括以下三部分
算法程序所占的空间
输入的初始数据所占的存储空间
算法执行过程中所要的额外空间
算法空间复杂度可定义为：
S(n)=O(f(n))
原地工作(in place)的算法：记作O(1)
压缩存储技术
1.2 数据结构的基本概念
1.2.1 什么是数据结构
1．数据结构研究的主要内容
数据的逻辑结构
数据的存储结构
对各种数据结构进行的运算
2．研究数据结构目的
提高数据处理的速度
尽量节省在数据处理过程中所占用的计算机存储空间
1.2.1 什么是数据结构
1．数据结构研究的主要内容
数据的逻辑结构
数据的存储结构
对各种数据结构进行的运算
2．研究数据结构目的
提高数据处理的速度
尽量节省在数据处理过程中所占用的计算机存储空间
1.2.1 什么是数据结构
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B．非线性结构
A 顺序存储
B 链式存储
线性表
栈
队
树形结构
图形结构
数据结构的三个方面
1.2.1 什么是数据结构
3．数据结构的定义
相互有关联的数据元素的集合
数据元素之间的关系可以用前后件关系来描述
一个数据结构应包含以下两方面信息：
表示数据元素的信息
表示各数据元素之间的前后件关系
1.2.1 什么是数据结构
4．数据的逻辑结构
对数据元素之间的逻辑关系的描述
只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关
两个要素：
数据元素的集合，通常记为D；
前后件关系，通常记为R
一个数据结构B可以表示为：
B=（D，R）
1.2.1 什么是数据结构
5．数据的存储结构
数据的逻辑结构在计算机存储空间中的存放形式，它包括数据元素的存储方式和关系的存储方式。
常用的存储结构：
顺序
链式
索引
一种数据结构可根据需要采用不同的存储结构。采用不同的存储结构，其数据处理的效率是不同
1.2.2 数据结构的图形表示
数据结点：用方框表示
根结点、终端结点
前后件关系：用有向线段表示
基本运算：
插入运算
删除运算
查找、分类、合并、分解、复制、修改、……
1.2.3 线性结构与非线性结构
空的数据结构：一个数据元素都没有
线性结构
如果一个非空数据结构满足下列两个条件：
有且只有一个根结点；
每一个结点最多有一个前件，也最多有一个后件。
常见的线性结构有：线性表、栈与队列、线性链表
非线性结构
如果一个数据结构不是线性结构
常见的非线性结构有：树、二叉树、图
1.3 线性表及其顺序存储结构
1.3.1 线性表的基本概念
线性表：由n(n≥0)个相同类型数据元素构成的有限序列：
n定义为线性表的表长；n=0 时的线性表被称为空表。称i为在线性表中的位序。
例如：
英文大写字母表
（A，B，C，D，E，F，…X，Y，Z）
同一花色的13张扑克牌
(2,3,4,5,6,7,8,9,10,J,Q,K,A)
1.3.1 线性表的基本概念
线性表的结构特征
数据元素在表中的位置由序号决定，数据元素之间的相对位置是线性的；
对于一个非空线性表，有且只有一个根结点a1，它无前件，有且只有一个终端结点an，它无后件，除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
线性表的存储结构
顺序存储
链式存储
1.3.2 线性表的顺序存储结构
两个基本特点：
线性表中所有元素所占的存储空间是连续的。
线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
存储示意图
1.3.3 顺序表的插入运算
1.3.4 顺序表的删除运算
顺序表的插入和删除分析
插入算法的分析
假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：
删除算法的分析
在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：
分析结论
顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑
1.4 线性链表
1.4.1 线性链表的基本概念
1．线性表顺序存储的缺点
插入或删除的运算效率很低。在顺序存储的线性表中，插入或删除数据元素时需要移动大量的数据元素。
线性表的顺序存储结构下，线性表的存储空间不便于扩充。
线性表的顺序存储结构不便于对存储空间的动态分配。
1.4.1 线性链表的基本概念
2．线性链表
线性表的链式存储结构
物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的
每个结点由两部分组成：数据域和指针域
1.4.1 线性链表的基本概念
双向链表：每个结点设置两个指针
左指针：指向其前件结点
右指针：指向其后件结点
1.4.2 线性链表的基本运算
插入
删除
合并
分解
逆转
复制
排序
查找
1.4.2 线性链表的基本运算
1．在线性链表中查找指定元素
链表不是随机存取结构
从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止
2．线性链表的插入
1.4.2 线性链表的基本运算
3．线性链表的删除
与顺序存储相比，链表的优点有：
插入和删除元素时，不需要移动数据元素，只需要修改指针即可
1.4.3 双向链表
双向链表：每个结点设置两个指针
左指针：指向其前件结点
右指针：指向其后件结点
1.4.4 循环链表及其基本运算
循环链表特点：
在链表中增加了一个表头结点
最后一个结点的指针域指向表头结点，构成了一个环状链
循环链表优点：
从任一结点出发来访问表中其他所有结点
空表与非空表的运算的统一
1.5 栈和队列
1.5.1 栈及其基本运算
1．栈的定义
栈（stack）：一种只允许在表的一端进行插入或删除操作的特殊的线性表
栈顶(top) ：允许进行插入与删除操作的一端
栈底(bottom)：不允许插入与删除操作的另一端
先进后出（FILO）或后进先出(LIFO)的线性表
1.5.1 栈及其基本运算
2．栈的顺序存储及其运算
top=0：栈空 top=m：栈满
栈的基本运算
入栈运算
退栈运算
读栈顶元素
1.5.1 栈及其基本运算
3．栈的链式存储结构——链栈
1.5.2 队列及其基本运算
1．队列的定义
限定只能在表的一端进行插入和在另一端进行删除操作的线性表
队尾(rear)：允许插入的一端
队头(front)：允许删除的另一端
先进先出（FIFO）表或后进后出（LILO）线性表
基本操作
入队运算：往队列的队尾插入一个元素，队尾指针rear的变化
退队运算：从队列的排头删除一个元素，队头指针front的变化
1.5.2 队列及其基本运算
2．循环队列及其运算
队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用
入队运算 ：队尾指针加1，并当rear=m+1时置rear=1
出队运算：队头指针加1，并当front=m+1时置front=1
1.5.2 队列及其基本运算
3．队列链式存储结构——链队列
1.6 树与二叉树
1.6 树与二叉树
1．树的定义
树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：
（1）有且仅有一个特定的称为根(Root)的结点；
（2）其余的结点可分为m(m≥0)个互不相交的子集T1，T2，T3，…，Tm，其中每个子集又是一棵树，并称其为子树。
1.6 树与二叉树
2．树中的基本概念
父结点与树的根：每个结点最多只允许有一个前件，称为该结点的父结点。没有前件的结点中有一个，称为树的根结点。
子结点与叶子结点：在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。
结点的度和树的度：一个结点所拥有后件个数称为该结点的度。一棵树中各个结点度数的最大值叫做这棵树的度。
层和树的深度：树结构是一种层次结构，根结点为第一层，根的子结点为第二层，其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度。
1.6.1 树的基本概念
树的特点
（1）树中只有根结点没有前件；
（2）除根外，其余结点都有且仅一个前件；
（3）树的结点，可以有零个或多个后件；
（4）除根外的其他结点，都存在唯一条从根到该结点的路径；
（5）树是一种分支结构（除根的结点外）每个元素都有且仅有一个直接前件，有且仅有零个或多个直接后件。
树的存储
用多重链表来表示
1.6.2 二叉树及其基本性质
1．二叉树的定义
一个二叉树是n个结点的有限集合（n≥0），此集合或者是空集（n=0），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成，并且左右子树都是二叉树。
特点：
非空二叉树只有一个根结点；
每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
1.6.2 二叉树及其基本性质
2．二叉树的性质
性质1 在二叉树的第k层上，最多有 个结点。
性质2 深度为m的二叉树最多有个 结点。
性质3 在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。即：
其中，n0表示度数为0的结点数，n2表示度数为2的结点数。
性质4 具有n个结点的二叉树的深度至少为 ，其中 表示取 的整数部分。
1.6.2 二叉树及其基本性质
3．满二叉树和完全二叉树
满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。
完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
1.6.2 二叉树及其基本性质
性质5 具有n个结点的完全二叉树深度为 。
性质6 设完全二叉树共有n个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号，则对于编号为k（k=1，2，…，n）的结点有以下结论：
①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点的编号为INT(k/2)。
②若2k≤n，则编号为k的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。
③若2k+1≤n，则编号为k的右子结点编号为2k+1；否则该结点无右子结点。
1.6.3 二叉树的存储结构
普通二叉树
采用链式存储结构
存储结点由两部分组成：数据域与指针域
两个指针域：
左指针域
右指针域
满二叉树与完全二叉树
采用顺序存储结构
1.6.4 二叉树的遍历
二叉树的遍历：不重复地访问二叉树中的所有结点
1．前序遍历（DLR）
首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
2．中序遍历（LDR）
首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树
3．后序遍历（LRD）
首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。
1.6.4 二叉树的遍历
前序遍历：
A、B、D、G、C、E、F
中序遍历：
D、G、B、A、E、C、F
后序遍历：
G、D、B、E、F、C、A
1.7 查找技术
1.7 查找技术
查找（Searching）：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
查找结果：
查找成功：找到
查找不成功：没找到
平均查找长度：查找过程中关键字和给定值比较的平均次数
1.7.1 顺序查找
基本思想：
从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。
平均要与表中一半以上元素进行比较，最坏情况下需要比较n次。
下列两种情况下只能采用顺序查找：
如果线性表是无序表（即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。
即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
1.7.2 二分法查找
思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。
前提：必须在具有顺序存储结构的有序表中进行。
查找过程：
1）若中间项的值等于x,则说明已查到。
2）若x小于中间项的值，则在线性表的前半部分查找；
3）若x大于中间项的值，则在线性表的后半部分查找。
特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。
1.7.2 二分法查找
例：查找元素22过程：
1.8 排序技术
1.8.1 交换类排序法
基本思想
两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。
方法
冒泡排序
快速排序
1.冒泡排序
基本思想
对存放原始数据的数组，按从后往前的方向进行多次扫描，当发现相邻两个数据的次序与排序要求的“递增次序”不符合时，即将这两个数据进行互换。这样，较小的数据就会逐单元向前移动，好象气泡向上浮起一样。
性能分析
假设线性表的长度n，则在最坏情况下，需要的比较次数为n(n-1)/2。
1.冒泡排序
2．快速排序
基本思想
任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。
快速排序的平均时间复杂度为O(nlog2n)。
2．快速排序
1.8.2 插入类排序法
基本思想：
每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
方法:
简单插入排序
希尔排序
1．简单插入排序法
基本思想：
把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
在最坏的情况下，需要n(n-1)/2次比较。
1．简单插入排序法
2．希尔排序
基本思想
先将整个待排元素序列分割成若干个子序列（由相隔某个增量h的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。
增量序列一般取 ，其中n为待排序序列的长度
在最坏情况下，希尔排序的时间复杂度为
2．希尔排序
1.8.3 选择类排序法
基本思想：
每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子序列的最后，直到全部记录排序完毕。
方法：
简单选择排序
堆排序
1．简单选择排序法
基本思想：
扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。
最坏情况下，需要比较n(n-1)/2次。
1．简单选择排序法
2．堆排序法
堆的定义
具有n个元素的序列，当且仅当满足
① 或 ②
时称之为堆。①称为大根堆；②称为小根堆 。
2．堆排序法
建堆
在建堆的过程中，总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。这个调整过程一直做到所有子树均为堆为止。
堆排序
（1）首先将一个无序序列建成堆。
（2）然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，将该子序列调整为堆。
反复做步骤（2），直到剩下的子序列空为止。
在最坏情况下，堆排序法需要比较的次数为O(nlog2n)。
各种排序法比较
典型考题分析
【例1-1】问题处理方案的正确而完整的描述称为 。（2005年4月）
答案 算法
【例1-2】算法复杂度主要包括时间复杂度和 复杂度。（2005年9月）
答案 空间
【例1-3】算法的时间复杂度是指_______。
A）执行算法程序所需要的时间
B）算法程序的长度
C）算法执行过程中所需要的基本运算次数
D）算法程序中的指令条数
答案　C
【例1-4】算法的空间复杂度是指_______。
A）算法程序的长度
B）算法程序中的指令条数
C）算法程序所占的存储空间
D）算法执行过程中所需要的存储空间
答案　D
【例1-5】下列叙述中正确的是 。（2006年9月）
A）一个算法的空间复杂度大，则其时间复杂度也必定大
B）一个算法的空间复杂度大，则其时间复杂度必定小
C）一个算法的时间复杂度大，则其空间可复杂度必定小
D）上述三种说法都不对
答案 D
【例1-6】下列叙述中正确的是 。（2005年9月）
A）一个逻辑数据结构只能有一种存储结构
B）数据的逻辑结构属于线性结构，存储结构属于非线性结构
C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率
D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率
答案 D
【例1-7】数据结构分为逻辑结构和存储结构，循环队列属于 结构。（2005年9月）
答案 逻辑
【例1-8】数据结构分为线性结构和非线性结构，带链的队列属于 。（2006年9月）
答案 线性结构
【例1-9】下列叙述中正确的是______。（2006年4月）
A）线性链表是线性表的链式存储结构
B）栈与队列是非线性结构
C）双向链表是非线性结构
D）只有根结点的二叉树是线性结构
答案 A
【例1-10】某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为200，则第12个元素的存储地址为 。
A）248
B）247
C）246
D）244
答案 D
【例1-11】在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为 。
A）n-i+1
B）n-i
C）i
D）i-1
答案 A
【例1-12】在一个长度为n的顺序表中，删除第i（1≤i≤n）个元素时，需要移动的元素个数为 。
A）n-i+1
B）n-i
C）i
D）i-1
答案 B
【例1-13】以下描述的中，不是线性表的顺序存储结构的特征的是 。
A）不便于插入和删除
B）需要连续的存储空间
C）可随机访问
D）需另外开辟空间来保存元素之间的关系
答案 D
【例1-14】下列关于栈的描述中错误的是______。（2005年4月）
A）栈是先进后出的线性表
B）栈只能顺序存储
C）栈具有记忆作用
D）对栈的插入与删除操作中，不需要改变栈底指针
答案 B
【例1-15】栈和队列的共同点是______。
A）都是先进先出
B）都是先进后出
C）只允许在端点处插入和删除元素
D）没有共同点
答案 C
【例1-16】栈的输入序列为1，2，3，…，n-1，n，输出序列的第1个元素为n，则第ｉ个输出元素为_________。
A）n-i+1
B）n-1
C）i
D）哪个元素无所谓
答案 A
【例1-17】一个队列的入队序列是1、2、3、4，则队列的输出序列是 。
A）4、3、2、1
B）1、2、3、4
C）1、4、3、2
D）3、2、4、1
答案 B
【例1-18】队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。允许插入的一端称作_______。
答案 队尾
【例1-19】下列对于线性链表的描述中正确的是 。（2005年4月）
A）存储空间不一定是连续，且各元素的存储顺序是任意的
B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面
C）存储空间必须连续，且各前件元素一定存储在后件元素的前面
D）存储空间必须连续，且各元素的存储顺序是任意的
答案 A
【例1-20】下列叙述中，错误的是 。
A）线性表是由n个数据元素组成的一个有限序列
B）线性表是一种线性结构。
C）线性表的所有结点有且只有一个前件和一个后件
D）线性表可以是空表。
答案 C
【例1-21】下列描述的不是链表的优点是_______。
A）逻辑上相邻的结点物理上不必邻接
B）插入、删除运算操作方便，不必移动结点
C）所需存储空间比线性表节省
D）无需事先估计存储空间的大小
答案 C
【例1-22】某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素。删除运算是指删除表头第一个元素，那么采用 存储方式最节省运算时间。
A）仅有尾指针的单向循环链表
B）仅有头指针的单向循环链表
C）单向链表
D）顺序存储
答案 A
【例1-23】一棵二叉树第六层（根结点为第一层）的结点数最多为 个。（2005年9月）
答案 32
【例1-24】深度为5的二叉树至多有_______个结点。
A）16
B）32
C）31
D）10
答案 C
【例1-25】设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则T中的叶子结点为_______。
A）8
B）7
C）6
D）5
答案 A
【例1-26】某二叉树中度为2的结点有18个，则该二叉树中有 个叶子结点。（2005年4月）
答案 19
【例1-27】具有88个结点的二叉树，其深度至少为______。
答案 7
【例1-28】在深度为7的满二叉树中，叶子结点的个数为（2006年4月）
A）32
B）31
C）64
D）63
答案 C
【例1-29】设一棵完全二叉树共有700个结点，则在该二叉树中有________个叶子结点。
答案 350
【例1-30】对如图1-30所示的二叉树，进行后序遍历的结果为 。（2006年4月）
A）ABCDEF
B）DBEAFC
C）ABDECF
D）DEBFCA
答案 D
【例1-31】假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为 。
答案：ABDEGHJCFI
【例1-32】对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为_____。（2005年4月）
A）log2n
B）n/2
C）n
D）n+l
答案 C
【例1-33】下列数据结构中，能用二分法进行查找的是 。（2005年9月）
A）顺序存储的有序线性表
B）线性链表
C）二叉链表
D）有序线性链表
答案 A
【例1-34】已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当使用二分法查找值为90的元素时，查找成功的比较次数为 。
A）1
B）2
C）3
D）9
答案 B
【例1-35】对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为 。（2006年4月）
答案 45
【例1-36】在排序算法中，两两比较待排序的记录，当发现不满意顺序要求时，变更它们的相对位置，这就是 排序。
A）希尔排序
B）交换排序
C）插入排序
D）选择排序
答案 B
【例1-37】设待排序关键码序列为（33，18，9，25，67，82，53，95，12，70），要按关键码值递增的顺序排序，采取以第一个关键码为基准元素的快速排序法，第一趟排序完成后关键码33被放到了第_______位置。
A）3
B）5
C）7
D）9
答案 B
【例1-38】对于给定的一组关键字（12，2，16，30，8，28，4，10，20，6，18），按照希尔排序（增量为 5 ）算法进行递增排序，第一趟排序后得到的结果是 。
答案 12，2，10，20，6，28，4，16，30，8，18
【例1-39】对数据元素序列（49，72，68，13，38，50，97，27）进行排序，前三趟排序结束时的结果依次为：第一趟：13，72，68，49，50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72。该排序采用的方法是_________。
A）简单插入排序法
B）冒泡排序法
C）简单选择排序法
D）快速排序法
答案 C
【例1-40】以下各组序列中，属于堆的是_______。
A）19，34，26，97，56，75
B）97，26，34，75，19，56
C）19，56，26，97，34，75
D）19，75，34，26，97，56
答案 A
【例1-41】对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是_____。（2005年4月）
A）冒泡排序为n/2
B）冒泡排序为n
C）快速排序为n
D）快速排序为n(n-1)/2
答案 D(共116张PPT)
第3章 软件工程基础
内容提要
软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。
结构化分析方法，数据流图，数据字典，软件需求规格说明书。
结构化设计方法，总体设计与详细设计。
软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。
程序的调试
3.1 软件工程基本概念
3.1.1 软件定义与软件特点
1．软件的定义和组成
定义：
计算机软件（Software）是计算机系统中与硬件相互依赖的另一部分。
组成：
程序
数据
文档
国标（GB）定义
与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。
3.1.1 软件定义与软件特点(续)
2．软件的特点
软件是一种逻辑实体，而不是具体的物理实体，具有抽象性
软件没有明显的制造过程。对软件的质量控制，必须在软件开发方面下功夫
软件不存在老化问题，但存在退化问题，必须要修改和维护
对计算机系统有着依赖性——软件移植的问题
软件复杂性高，开发和维护成本高
软件开发涉及诸多社会因素
3.1.1 软件定义与软件特点(续)
3．软件的分类
应用软件
系统软件
操作系统
数据库管理系统
设备驱动程序
……
支撑软件
3.1.2 软件危机与软件工程
1．软件危机
软件工程源自于软件危机
主要表现：
软件需求的增长得不到满足
软件开发成本和进度无法控制
软件质量难以保证
软件不可维护或维护程度非常低
软件成本不断提高
软件开发生产效率的提高赶不上硬件的发展和应用需求的增长
归结为成本、质量和生产率等问题
3.1.2 软件危机与软件工程
2．软件工程的产生与定义
软件工程学——工程学的新兴领域
定义：
国标（GB）：应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。
德国人Fritz Bauer：软件工程是建立并使用完善的工程化原则，以较经济的手段获取能在实际机器上有效运行的可靠软件的一系统方法。
IEEE：将系统的、规范的、可度量的方法应用于软件开发、运行和维护的过程，即将工程应用于软件中。
主要思想：在软件开发过程中需要应用工程化原则的重要性
3.1.2 软件危机与软件工程
2．软件工程的产生与定义
软件工程3个要素：
方法
工具
过程
3.1.3 软件工程过程与软件生命周期
1．软件工程过程
P（Plan）——软件规格说明
D（Do）——软件开发
C（Check）——软件确认
A（Action）——软件演进
3.1.3 软件工程过程与软件生命周期
软件产品从提出、实现、使用维护、停止使用到退役的过程
3个阶段
6个阶段工作
3.1.3 软件工程过程与软件生命周期
定义阶段
制定计划：”能做吗？“
需求分析：“做什么？”
开发阶段：
软件设计：“如何做？”，分为概要设计和详细设计两个阶段。
软件实现：“实现”，编码。
软件测试：”做的怎么样？“
运行维护阶段
使用，不断维护
3.1.4 软件工程的目标与原则
1．软件工程的目标
成功的项目：
成本
功能
移植
维护费用
按时
及时交付
目标：
在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品
3.1.4 软件工程的目标与原则
2．软件工程学的范畴
3.1.4 软件工程的目标与原则
3．软件工程的原则
抽象
信息隐蔽
模块化
局部化
确定性
一致性
完备性
可验证性
3.1.5 软件开发工具与软件开发环境
1．软件开发工具
协助开发人员进行软件开发活动所使用的软件或环境
需求分析工具、设计工具、编码工具、排错工具、测试工具等。
2．软件开发环境
全面支持软件开发全过程的软件工具的集合
计算机辅助软件工程：CASE
3.2 结构化分析方法
3.2.1 需求分析与需求分析方法
1．需求分析
定义：
任务：导出目标系统的逻辑模型，解决“做什么”的问题
全面理解用户的各项要求
准确地表达各项要求
主要工作：
需求获取
需求分析
编写需求规格说明书
需求审评
3.2.1 需求分析与需求分析方法
2．需求分析方法
结构化分析方法
面向数据流的结构化分析方法（SA）
面向数据结构的Jackson方法（JSD）
面向数据结构的结构化数据系统开发方法（DSSD）
面向对象分析方法（OOA）
静态分析方法
动态分析方法
3.2.2 结构化分析方法
1．关于结构化分析方法
结构化程序设计理论在需求分析阶段的运用
面向数据流进行需求分析的方法
自顶向下、逐层分解
主要工具：数据流图、数据字典
3.2.2 结构化分析方法
2．结构化分析的常用工具
数据流图（DFD）
数据字典
判定树
判定表
3.2.2 结构化分析方法
数据流图
3.2.2 结构化分析方法
数据流图：基本图形元素
3.2.2 结构化分析方法
数据流图：分层数据流图
3.2.2 结构化分析方法
2．结构化分析的常用工具
数据字典
结构化分析方法的核心
对数据流图中出现的被命名的图形元素的确切解释判定树
判定树
判定表
3.2.3 软件需求规格说明书
需求分析阶段的最后成果
作用：
便于用户、开发人员进行理解和交流；
反映出用户问题的结构，可以作为软件开发工作的基础和依据；
作为确认测试和验收的依据。
主要内容
概述、数据描述、功能描述、性能描述、参考文献、附录
特点：
①正确性；②无歧义性；③完整性；④可验证性；⑤一致性；⑥可理解性；⑦可修改性；⑧可追踪性。
3.3 结构化设计方法
3.3.1 软件设计的基本概念
1．软件设计的基础
开发阶段：设计、实现（编码）和测试
需求分析：主要解决“做什么”问题
软件设计：主要解决“怎么做”问题
3.3.1 软件设计的基本概念
1．软件设计的基础
重要性：
主要内容：
结构设计、数据设计、接口设计、过程设计
步骤：
概要设计和详细设计
3.3.1 软件设计的基本概念
2．软件设计的基本原理
抽象
一种思维工具
抽出事物本质的共同特点，不考虑细节
模块化
模块
模块化
信息隐蔽
每个模块的实现细节对于其它模块来说是隐蔽的
模块独立性
每个模块只涉及软件要求的具体的子功能和软件系统中其它的模块的接口是简单的
衡量指标：耦合性、内聚性
3.3.1 软件设计的基本概念
内聚性
度量一个模块功能强度的一个相对指标。
一个模块只做一件事
7种类型
3.3.1 软件设计的基本概念
耦合性
度量模块之间的相互联系程度
取决于接口的复杂程度、调用方式、哪些信息通过接口
模块连接方式有7种，构成耦合性的7种类型
3.3.2 概要设计
1．概要设计的基本任务
系统结构设计
主要任务：划分为模块
数据结构和数据库的设计
实现需求定义和规格说明过程中提出的数据对象的逻辑表示
编写概要设计文档
概要设计说明书、数据库设计说明书、用户手册和集成测试计划。
概要设计的评审
对概要设计文档中给出的设计方案可行性、正确性、有效性、一致性等进行审核
3.3.2 概要设计(续)
2．软件结构图
用来表示软件结构
基本图符
3.3.2 概要设计(续)
两个附加符号
3.3.2 概要设计(续)
系统结构图（SC）中的模块
原子模块
4种类型的模块
3.3.2 概要设计(续)
结构图的形态特征
深度、宽度、扇出、扇入
3.3.2 概要设计(续)
3．面向数据流的设计方法
数据流图（DFD）：需求分析工具
系统结构图（SC）：概要设计工作
主要任务：数据流图变换成结构图
数据流的类型
变换流
事务流
3.3.2 概要设计(续)
变换流
数据流图：取得数据、变换数据、给出数据
3.3.2 概要设计(续)
变换流
系统的结构图：输入、中心变换、输出
3.3.2 概要设计(续)
事务流
数据流图
3.3.2 概要设计(续)
事务流
系统的结构图：
3.3.2 概要设计(续)
实施要点与设计过程
分析、确认数据流图的类型，区分是事务型还是变换型
说明数据流的边界
数据流图映射为程序结构
根据设计准则把数据流转换成程序结构图
3.3.2 概要设计(续)
变换分析
确定数据流图是否具有变换特性
确定输入流和输出流的边界，划分出输入、变换和输出，独立出变换中心
第一级分解
按上述步骤如出现事务流的映射方式对各个子流进行逐级分解，直至分解到基本功能；
对每个模块写一个简要的说明
利用软件的设计原则对软件结构透一步转化
事务分析
与变换分析类似
主要差别：映射方法不同
3.3.2 概要设计(续)
4.设计准则
提高模块独立性
深度、宽度、扇度和扇出适度
使模块的作用域在该模块的控制域内
应减少模块的接口和界面的复杂性
设计成单入口、单出口的模块
设计功能可预测的模块
3.3.3 详细设计
详细设计的任务：
确定实现算法和局部数据结构
不同于编码或编程
详细设计的常用工具：
图形工具：程序流程图、N-S、PAD和HIPO
表格工具：判定表；
语言工具：PDL（伪码）
3.3.3 详细设计(续)
程序流程图
图形元素：
方框：处理步骤
菱形：逻辑条件
箭头：控制流
5种控制结构
顺序型
选择型
先判断重复型
后判断重复型
多分支选择型。
3.3.3 详细设计(续)
程序流程图
3.3.3 详细设计(续)
N-S图
流程图：随意性与灵活性
N-S图：限制了随意的控制转移，保证了程序的良好结构
5种基本控制结构：
3.3.3 详细设计(续)
N-S图
3.3.3 详细设计(续)
N-S图
特点：
每个构件具有明确的功能域
控制转移必须遵守结构化设计要求；
易于确定局部数据和（或）全局数据的作用域
易于表达嵌套关系和模块的层次结构
3.3.3 详细设计(续)
PAD图
PAD——问题分析图，Problem Analysis Diagram
表现程序逻辑结构的图形工具
5种基本控制结构
3.3.3 详细设计(续)
PAD图
3.3.3 详细设计(续)
PAD图
特征
结构清晰，结构化程度高
易于阅读
程序的纵线数等于程序的层次数
程序执行从PAD图最左主干线上端结点开始，自上而下、自左向右依次执行，程序终止于最左主干线
3.3.3 详细设计(续)
PDL（伪码）
PDL——过程设计语言，Program Design Language
混合语言，类似编程语言
常用词汇：
顺序：
条件：IF／THEN／ELSE／ETIDIF
循环：DOWHILE／ENDDO
循环：REPEAT UNTIL／ENDREPEAT
分支：CASE OF／WHEN／SELECT／WHEN／SELECT／ENDCASE
PDL特征：
有为结构化构成元素、数据说明和模块化特征提供的关键词语法；
处理部分的描述采用自然语言语法
可以说明简单和复杂的数据结构
支持各种接口描述的子程序定义和调用技术。
3.4 软件测试
3.4.1 软件测试的目的
检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别
Grenford J.Myers观点：
测试是程序的执行过程，目的在于发现错误
一个好的测试用例在于能发现至今未发现的错误
一个成功的测试是发现了至今未发现的错误的测试
3.4.2 软件测试的准则
所有测试都应追溯到需求
严格执行测试计划，排除测试的随意性
充分注意测试中的群集现象
程序员应避免检查自己的程序
穷举测试不可能
妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便
3.4.3 软件测试技术与方法综述
1．静态测试与动态测试
静态测试
人工评审软件文档或程序，借以发现其中的错误
主要方法：代码检查、静态结构分析、代码质量度量
动态测试
上机测试
关键：设计高效、合理的测试用例
分两类：白盒测试方法和黑盒测试方法
3.4.3 软件测试技术与方法综述(续)
2．白盒测试方法与测试用例设计
也称结构测试或逻辑驱动测试
测试用例是根据程序的内部逻辑来设计
主要用于单元测试
基本原则
保证所测模块中每一个独立路径至少执行一次
保证所测模块所有判断的每一个分支至少执行一次
保证所测模块每一个循环都在边界条件和一般条件至少执行一次
验证所有内部数据结构的有效性
主要方法：逻辑覆盖、基本路径测试
3.4.3 软件测试技术与方法综述(续)
逻辑覆盖测试
程序中的逻辑：判断、分支、条件
可分为：
语句覆盖：每一个语句都能执行一次
路径覆盖：所有的可能路径都至少经历一次
判定覆盖：每个判定至少都获得一次“真值”和“假值”的机会
条件覆盖：每个判定中每个条件都获得一次 “真”和“假”的机会
判断-条件覆盖：判定中的每个条件都能取得各种可能的“真”和“假”值，并且使每个判定都能取到“真”和“假”两种结果
强度顺序
语句覆盖<路径覆盖<判定覆盖<条件覆盖<判定-条件覆盖
3.4.3 软件测试技术与方法综述(续)
基本路径测试
把覆盖的路径数压缩到一定限度内
思想和步骤：
根据软件过程性描述中的控制流程确定程序的环路复杂性度量，用此度量定义基本路径集合，并由此导出一组测试用例对每一条独立执行路径进行测试
3.4.3 软件测试技术与方法综述(续)
3．黑盒测试方法与测试用例设计
也称功能测试或数据驱动测试
对软件已经实现的功能是否满足需求进行测试和验证
根据程序的功能说明来设计测试用例
主要用于确认测试
主要方法
等价类划分法
边界值分析法
错误推测法
3.4.3 软件测试技术与方法综述(续)
等价类划分法
有效等价类
无效等价类
边界值分析法
大量的错误是发生在输入或输出范围的边界上
错误推测法
根据经验或直觉推测程序易出错的地方
3.4.4 软件测试的实施
3.4.4 软件测试的实施(续)
1．单元测试
对象：针对程序模块，进行正确性检验的测试
目的：发现各模块内部可能存在的各种差错
依据：从程序的内部结构出发设计测试用例，其依据是详细的设计说明书和源程序
方法：以白盒测试为主，辅以黑盒测试
3.4.4 软件测试的实施(续)
1．单元测试
内容：
模块接口测试
局部数据结构测试
路径测试
错误处理测试
边界测试
步骤：
在编码阶段进行
源程序代码编制完成，经过评审和验证，确认没有语法错误之后
利用设计文档，设计可以验证程序功能、找出程序错误的多个测试用例
对于每一组输入，应有预期的正确结果
3.4.4 软件测试的实施(续)
1．单元测试
驱动模块、桩模块
3.4.4 软件测试的实施(续)
2．集成测试
任务：把模块在按照设计要求组装起来的同时进行测试
目的：发现与接口有关的错误
依据：集成测试的依据是概要设计说明书
内容：软件单元的接口测试、全局数据结构测试、边界条件和非法输入的测试
方式：非增量方式组装与增量方式组装。
3.4.4 软件测试的实施(续)
2．集成测试
非增量方式组装
也称为一次性组装方式
增量方式组装
也称渐增式集成方式
3种方式：
自顶向下
自底向上
自顶向与自底向上相结合
3.4.4 软件测试的实施(续)
自顶向下
3.4.4 软件测试的实施(续)
自底向上
3.4.4 软件测试的实施(续)
3．确认测试
又称有效性测试
目的：验证软件的功能和性能及其它特性是否与用户的要求一致
依据：软件需求规格说明书
方法：黑盒测试法
4．系统测试
任务：在实际运行（使用）环境下，对计算机系统进行一系列的组装测试和确认测试
目的：在于通过与系统的需求定义作比较，发现软件与系统定义不符合或与之矛盾的地方
依据： 需求分析规格说明来设计
内容：功能测试、性能测试、操作测试、配置测试、外部接口测试、安全性测试
3.5 程序的调试
3.5.1 基本概念
任务：诊断和改正程序中的错误
时机：调试主要在开发阶段进行
3.5.1 基本概念(续)
1.基本步骤
错误定位、纠正错误、回归测试
3.5.1 基本概念(续)
2．程序调试原则
确定错误的性质和位置的原则
用头脑去分析思考与错误征兆有关的信息
避开死胡同。
只把调试工具当作辅助手段来使用
避免用试探法，最多只能把它当作最后手段
修改错误的原则
在出现错误的地方，很可能还有别的错误
只修改了这个错误的征兆或这个错误的表现，而没有修改错误的本身。
当心修正一个错误的同时有可能会引入新的错误
修改错误的过程将迫使人们暂时回到程序设计阶段
修改源代码程序，不要改变目标代码
3.5.2 软件调试方法
1．强行排错法
通过内存全部打印来排错（Memory Dump）
在程序特定部位设置打印语句
自动调试工具
2．回溯法
3．原因排除法
演绎法
归纳法
二分法
典型考题分析
【例3-1】下列描述中正确的是______。（2005年4月）
A）程序就是软件
B）软件开发不受计算机系统的限制
C）软件既是逻辑实体，又是物理实体
D）软件是程序、数据与相关文档的集合
答案 D
【例3-2】下列描述中正确的是______。（2005年9月）
A）软件工程只是解决软件项目的管理问题
B）软件工程主要解决软件产品的生产率问题
C）软件工程的主要思想是强调在软件开发过程中需要应用工程化原则
D）软件工程只是解决软件开发中的技术问题
答案 C
【例3-3】下面不属于软件工程的3个要素的是______。
A）工具 B）过程
C）方法 D）环境
答案 D
【例3-4】下列叙述中正确的是______。（2005年9月）
A）软件交付使用后还需要进行维护
B）软件一旦交付使用就不需要再进行维护
C）软件交付使用后其生命周期就结束
D）软件维护是指修复程序中被破坏的指令
答案 A
【例3-5】下列选项中不属于软件生命周期开发阶段任务的是______。（2006年9月）
A）软件测试 B）概要设计
C）软件维护 D）详细设计
答案 C
【例3-6】软件工程学一般包括软件开发技术和软件工程管理两方面的内容。软件工程经济学是软件工程管理的技术内容之一，它专门研究______。
A）软件开发的方法学
B）软件开发技术和工具
C）软件成本效益分析
D）计划、进度和预算
答案 C
【例3-7】下面不属于软件工程原则的是______。
A）抽象 B）模块化
C）自底向上 D）信息隐蔽
答案 C
【例3-8】计算机辅助软件工程，简称为______。
A）SA B）SD
C）SC D）CASE
答案 D
【例3-9】需求分析阶段的任务是确定______。
A）软件开发方法
B）软件开发工具
C）软件开发费用
D）软件系统功能
答案 D
【例3-10】软件需求分析阶段的工作，可以分为四个方面：需求获取，需求分析，编写需求规格说明书，以及______。
A）阶段性报告
B）需求评审
C）总结
D）都不正确
答案 B
【例3-11】结构化分析方法是面向______的自顶向下逐步求精进行需求分析的方法。
A）对象
B）数据结构
C）数据流
D）目标
答案 C
【例3-12】下列工具中为需求分析常用工具的是______。
A）PAD
B）PFD
C）N-S
D）DFD
答案 D
【例3-13】数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下面图符号不属于数据流图的是______。
A）控制流
B）加工
C）数据存储
D）源和潭
答案 A
【例3-14】下列叙述中，不属于软件需求规格说明书的作用的是______。
A）便于用户、开发人员进行理解和交流
B）反映出用户问题的结构，可以作为软件开发工作的基础和依据
C）作为确认测试和验收的依据
D）便于开发人员进行需求分析
答案 D
【例3-15】Jackson方法是一种面向______的结构化方法。
答案 数据结构
【例3-16】从工程管理角度，软件设计一般分为两步完成，它们是______。（2006年9月）
A）概要设计与详细设计
B）数据设计与接口设计
C）软件结构设计与数据设计
D）过程设计与数据设计
答案 A
【例3-17】两个或两个以上模块之间关联的紧密程度称为______。（2006年4月）
A）耦合度
B）内聚度
C）复杂度
D）数据传输特性
答案 A
【例3-18】为了提高模块的独立性，模块之间最好是______。
A）控制耦合
B）公共耦合
C）内容耦合
D）数据耦合
答案 D
【例3-19】为了使模块尽可能独立，要______。（2005年4月）
A）模块的内聚程度要尽量高，且各模块间的耦合程度要尽量强
B）模块的内聚程度要尽量高，且各模块间的耦合程度要尽量弱
C）模块的内聚程度要尽量低，且各模块间的耦合程度要尽量弱
D）模块的内聚程度要尽量低，且各模块间的耦合程度要尽量强
答案 B
【例3-20】软件的结构化开发过程各阶段都应产生规范的文档，以下______不是在概要设计阶段应产生的文档。
A）集成测试计划
B）软件需求规格说明书
C）概要设计说明书
D）数据库设计说明书
答案 B
【例3-21】软件结构设计的图形工具是______。
A）DFD图 B）程序图
C）PAD图 D）N-S图
答案 B
【例3-22】下列软件系统结构图的宽度为______。（2006年9月）
答案 3
【例3-23】数据流图的类型有______和事务型。
答案 变换型
【例3-24】在软件设计中，不属于过程设计工具的是______。（2005年9月）
A）PDL(过程设计语言)
B）PAD图
C）N-S图
D）DFD图
答案 D
【例3-25】程序流程图(PFD）中的箭头代表的是______。
A）数据流
B）控制流
C）调用关系
D）组成关系
答案 B
【例3-26】为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来代替传统的程序流程图，通常也把这种图称为______。
A）PAD图
B）N-S图
C）结构图
D）数据流图
答案 B
【例3-27】下列对于软件测试的描述中正确的是______。（2005年4月）
A）软件测试的目的是证明程序是否正确
B）软件测试的目的是使程序运行结果正确
C）软件测试的目的是尽可能地多发现程序中的错误
D）软件测试的目的是使程序符合结构化原则
答案 C
【例3-28】为了提高测试的效率，应该______。
A）随机地选取测试数据
B）取一切可能的输入数据作为测试数据
C）在完成编码以后制定软件的测试计划
D）选择发现错误可能性大的数据作为测试数据
答案 D
【例3-29】程序测试分为静态分析和动态测试，其中______是指不执行程序，而只是对程序文本进行检查，通过阅读和讨论，分析和发现程序中的错误。（2006年4月）
答案 静态分析
【例3-30】使用白盒测试方法时，确定测试数据应根据______和指定的覆盖标准。
A）程序的内部逻辑
B）程序的复杂结构
C）使用说明书
D）程序的功能
答案 A
【例3-31】等价类型划分法是______测试常用的方法。
答案 黑盒
【例3-32】在进行模块测试时，要为每个被测试的模块另外设计两类模块：驱动模块和承接模块（桩模块）。其中______的作用是将测试数据传送给被测试的模块，并显示被测试模块所产生的结果。（2005年9月）
答案 驱动模块
【例3-33】检查软件产品是否符合需求定义的过程称为______。
A）系统测试
B）集成测试
C）验收测试
D）单元测试
答案 C
【例3-34】______的任务是诊断和改正程序中的错误。（2006年9月）
答案 调试
【例3-35】下列叙述中正确的是______。（2005年9月）
A）程序设计就是编制程序
B）程序的测试必须由程序员自己去完成
C）程序经调试改错后还应进行再测试
D）程序经调试改错后不必进行再测试
答案 A
【例3-36】以下所述中，______是软件调试技术。
A）错误推断
B）集成测试
C）回溯法
D）边界值分析
答案 C