资源简介 (共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）程序的注释可有可无答案 A2.4 典型考题分析【例2-3】源程序的文档化不包括_________。A）符号名的命名要有实际意义B）正确的文档格式C）良好的视觉组织D）正确的程序注释答案 D2.4 典型考题分析【例2-4】注释一般为序言性注释和_______注释。答案 功能性2.4 典型考题分析【例2-5】在设计程序时，应采纳的原则之一是_______。A）程序结构应有助于读者理解B）不限制GOTO语句的使用C）减少或取消注解行D）程序越短越好答案 A2.4 典型考题分析【例2-6】下列选项中不属于结构化程序设计方法的是__________。（2006年4月）A）自顶向下B）逐步求精C）模块化D）可复用答案 D2.4 典型考题分析【例2-7】下列选项不符合良好程序设计风格的是__________。（2006年9月）A）源程序要文档化B）数据说明的次序要规范化C）避免滥用 GOTO 语句D）模块设计要保证高耦合、高内聚答案 D2.4 典型考题分析【例2-8】结构化程序设计的三种基本控制结构是__________。A）过程、子程序和分程序B）顺序、选择和重复C）递归、堆栈和队列D）调用、返回和转移答案 B2.4 典型考题分析【例2-9】结构化程序设计主要强调的是__________。A）程序的规模B）程序的易读性C）程序的执行效率D）程序的可移植性答案 B2.4 典型考题分析【例2-10】关于结构化程序设计原则和方法的描述错误的是__________。A）选用的控制结构只准许有一个入口和一个出口B）复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现C）不允许使用GOTO语句D）语言中所没有的控制结构，应该采用前后一致的方法来模拟答案 C2.4 典型考题分析【例2-11】采用面向对象技术开发的应用系统的特点是________。A）重用性更强B）运行速度更快C）占用存储量小D）维护更复杂答案 A2.4 典型考题分析【例2-12】在面向对象方法中，类的实例称为________。（2005年4月）答案 对象2.4 典型考题分析【例2-13】消息传递是对象间通信的手段，一个对象通过向另一个对象发送消息来请求其服务。一个消息通常包括_______。A）接收消息的对象的名称、消息标识符和必要的参数B）接收消息的对象的名称和消息标识符C）发送消息的对象的名称、调用的接收方的操作名和必要的参数D）消息标识符答案 A2.4 典型考题分析【例2-14】一个对象在收到消息时，要予以响应。不同的对象收到同一消息可以产生完全不同的结果，这一现象叫做对象的__________。A）继承性B）多态性C）抽象性D）封装性答案 B2.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数据语言的使用交互式命令语言宿主型语言常见的DBMSORACLE、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和DBMSB）DBMS包含DB和DBSC）DBS包含DB和DBMSD）没有任何关系答案 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∪SC）T=R×S D）T=R/S答案 C【例4-21】设有如下关系表:则下列操作中正确的是______。（2005年9月）A）T＝R∩S B）T＝R∪SC）T＝R×S D）T＝R/S答案 B【例4-22】设关系R是4元关系，关系S是一个5元关系，关系T是R与S的笛卡尔积，即T=R×S，则关系T是______元关系。A）9 B）11C）20 D）40答案 A【例4-23】关系数据库管理系统能实现的专门关系运算包括______。A）排序、索引、统计B）选择、投影、连接C）关联、更新、排序D）显示、打印、制表答案 B【例4-24】下列关系运算中，______不要求关系R和S具有相同的属性个数。A）R∪S B）R∩SC）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=11.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、A1.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）248B）247C）246D）244答案 D【例1-11】在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为 。A）n-i+1B）n-iC）iD）i-1答案 A【例1-12】在一个长度为n的顺序表中，删除第i（1≤i≤n）个元素时，需要移动的元素个数为 。A）n-i+1B）n-iC）iD）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+1B）n-1C）iD）哪个元素无所谓答案 A【例1-17】一个队列的入队序列是1、2、3、4，则队列的输出序列是 。A）4、3、2、1B）1、2、3、4C）1、4、3、2D）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）16B）32C）31D）10答案 C【例1-25】设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则T中的叶子结点为_______。A）8B）7C）6D）5答案 A【例1-26】某二叉树中度为2的结点有18个，则该二叉树中有 个叶子结点。（2005年4月）答案 19【例1-27】具有88个结点的二叉树，其深度至少为______。答案 7【例1-28】在深度为7的满二叉树中，叶子结点的个数为（2006年4月）A）32B）31C）64D）63答案 C【例1-29】设一棵完全二叉树共有700个结点，则在该二叉树中有________个叶子结点。答案 350【例1-30】对如图1-30所示的二叉树，进行后序遍历的结果为 。（2006年4月）A）ABCDEFB）DBEAFCC）ABDECFD）DEBFCA答案 D【例1-31】假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为 。答案：ABDEGHJCFI【例1-32】对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为_____。（2005年4月）A）log2nB）n/2C）nD）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）1B）2C）3D）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）3B）5C）7D）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，75B）97，26，34，75，19，56C）19，56，26，97，34，75D）19，75，34，26，97，56答案 A【例1-41】对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是_____。（2005年4月）A）冒泡排序为n/2B）冒泡排序为nC）快速排序为nD）快速排序为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．软件开发环境全面支持软件开发全过程的软件工具的集合计算机辅助软件工程：CASE3.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／ENDCASEPDL特征：有为结构化构成元素、数据说明和模块化特征提供的关键词语法；处理部分的描述采用自然语言语法可以说明简单和复杂的数据结构支持各种接口描述的子程序定义和调用技术。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）SDC）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）PADB）PFDC）N-SD）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 展开更多...... 收起↑ 资源列表 第1章 数据结构.ppt 第2章 程序设计基础.ppt 第3章 软件工程基础.ppt 第4章 数据库设计基础.ppt
资源列表