电子课件全国计算机等级考试二级 MS Office高级应用第9章

1、 内容可修改电子课件全国计算机等级考试二级 MS Office高级应用第9章第9章计算机基础（全国计算机等级考试二级 MS Office高级应用与设计精讲版）COMPUTER数据库与程序设计基础目录CONTENTS计算机基础（全国计算机等级考试二级 MS Office高级应用与设计精讲版）9.1算法与数据结构9.2程序设计基础9.3软件工程基础9.4数据库设计基础9.1.1算法的基础知识1算法的基本特征算法是一组严谨定义运算顺序的规则，每一个规则都是有效且明确的，与此同时，该顺序将在有限的次数下终止。因此，算法具备以下 4 项基本特征。可行性有穷性确定性拥有足够的情报9.1.1算法的基础知识2

2、算法的复杂度算法复杂度是指算法在编写成可执行程序后，运行时所需要的时间资源和内存资源。因此，评价算法复杂度主要可从时间复杂度和空间复杂度两个方面来考虑。算法的时间复杂度是指执行算法所需要的计算工作量。时间复杂度空间复杂度空间复杂度是指执行算法期间所需要占用的内存空间，包括算法程序所占用的空间、输入的初始数据所占用的存储空间，以及算法执行过程中所需要的额外空间。9.1.2数据结构的基础知识1数据的逻辑结构数据的逻辑结构是反映数据元素间逻辑关系的数据结构，其一般表现形式为 B=(D, R)，其中，B 代表数据结构，D 代表数据元素的集合，R 代表 D 中各元素间的前后件关系。 线性结构 非线性结构

3、9.1.2数据结构的基础知识2数据的存储结构数据的存储结构是数据逻辑结构在计算机存储空间中的存储方式，数据的存储结构不仅存放了各数据元素的信息，还存放了数据元素之间前后件关系的信息。常见的数据存储结构包括以下两种。链式存储结构借助指示元素存储地址的指针来表示数据元素之间的逻辑结构。链式存储结构顺序存储结构借助数据元素之间的相对位置来表示数据元素之间的逻辑结构。顺序存储结构9.1.3线性表线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。1线性表顺序存储结构线性表的顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素。元素ai 的存储地址为 AD

4、R（ai）=ADR(a1)+(i-1)*k，其中，ADR（a1）为第一个元素的地址，k 代表每个元素所占的字节数。2线性表上的常用运算插入算法 ：假设线性表中含有 n 个数据元素，在进行插入操作时。删除算法 ：假设线性表中含有 n 个数据元素，在进行删除操作时，若假设删除每个元素的可能性均等，则平均移动元素的个数为 (n-1)/2。9.1.4栈和队列1栈栈是一种特殊的线性表，它只允许在表的一端插入或删除元素，因此此种结构被称为后进先出表。栈的基本计算包括以下3种。入栈运算退栈运算 读栈顶元素2队列队列简称队，它也是一种操作受限的线性表，限定只能在表的一端进行插入 , 在表的另一端进行删除，因此

5、此种结构被称为先进先出表，如图所示。9.1.4栈和队列3循环队列循环队列是将队列存储空间的最后一个位置绕到第一个位置 , 形成逻辑上的环状空间，以供队列循环使用。循环队列的基本运算有以下两种。入队运算入队运算是指在循环队列的队尾处加入一个新数据元素。入队的运算方法为：首先将队尾指针加 1，即 rear=rear+ 1, 然后在 rear 指针指向的位置插入新数据元素。退队运算退队运算是指在循环队列的排头处退出一个数据元素，为其赋给指定变量。退队的运算方法为 ：首先将排头指针加 1，即 front= front+1, 然后删除 front 指针指向位置的数据元素。9.1.5线性链表线性表由一组数

6、据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。1链表的结构链表的结构可分为线性单链表、双向链表和循环链表3种，如图所示。2链表的运算链表的运算主要包括查找、插入、删除、合并等，其中，链表的查找、插入和删除是常用的操作。下图所示为插入运算。9.1.6树与二叉树1二叉树的概述二叉树是一种特殊的树形结构，每个非空二叉树只有一个根结点，且每个结点最多有两棵子树，即左子树和右子树，因此每一个结点的度最大为 2。二叉树具有以下 4 个性质。在二叉树的第 k 层上最多有 2k-1（k 1）个结点。深度为 m 的二叉树最多有 2m-1（m 1）个结点。对于任何一个二叉树而言，度为

7、0（叶子结点）的结点总是比度为 2 的结点多一个。具有 n 个结点的二叉树深度至少为 log2n+1，其中，log2n 表示取 log2n 的整数部分。9.1.6树与二叉树2二叉树的遍历遍历是二叉树的重要运算，是指按一定的次序访问二叉树中的每一个结点，使每个结点被访问一次且只被访问一次。在先左后右的原则下，根据访问根结点的次序不同，可将二叉树的遍历分为前序遍历、中序遍历和后序遍历。前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树。中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。9.1.6树与二叉树3查找与排序技术（1）查找技

8、术查找技术分为以下两种。（2）排序技术排序是指将一组杂乱无章的数据按一定的规律顺次排列起来。排序技术包括以下3种。交换排序插入排序选择排序顺序查找二分查找目录CONTENTS计算机基础（全国计算机等级考试二级 MS Office高级应用与设计精讲版）9.1算法与数据结构9.2程序设计基础9.3软件工程基础9.4数据库设计基础9.2.1程序设计方法与风格程序设计方法是研究如何进行系统构造的软件方法学，是指设计、编制和调试程序的方法和过程，并且需要相应的理论、技术、方法和工具来支持。常用的程序设计方法有结构化的程序设计方法和面向对象的程序设计方法。程序设计风格是指一个人编写程序时所表现出的特点、习

9、惯和逻辑思路，为了便于测试和维护程序，程序设计风格应以简明清晰、易读易懂为主。如源程序文档中符号名的命名应直观、易懂，以便于他人理解程序功能。9.2.2结构化程序设计结构化程序设计基本原则可以概括为自顶向下、逐步求精、模块化和限制使用 goto 语句 4 种。1结构化程序设计的基本原则（4）限制使用 goto 语句（3）模块化（1）自顶向下（2）逐步求精9.2.2结构化程序设计1966 年，Boehm 和 Jacopini 证明了程序设计语言只需使用顺序结构、选择结构和循环结构这 3 种基本控制结构就能表达出各种其他形式结构的程序设计方法。2结构化程序的基本结构 顺序结构 选择结构 循环结构

10、9.2.2结构化程序设计在结构化程序设计的具体实施中，需注意以下 6 点。3结构化程序设计的注意事项使用程序设计语言的顺序结构、选择结构、循环结构等优先的控制结构来表示程序的控制逻辑。选用的控制结构只能有一个入口和一个出口。使用程序语句组成容易识别的块，每块只有一个入口和一个出口。复杂结构应该应用嵌套的基本控制结构进行组合嵌套来实现。应采用前后一致的方法模拟语言中没有的控制结构。严格控制 goto 语句的使用。9.2.3面向对象的程序设计方法面向对象的软件开发于 20 世纪 60 年代后期首次提出。20 世纪 80 年代，美国加州的Xerox 研究中心推出了 Smalltalk 语言和环境，完

11、善了面向对象的程序设计方法。面向对象的程序设计方法涵盖以下5个基本要素。对象消息多态性类和实例继承目录CONTENTS计算机基础（全国计算机等级考试二级 MS Office高级应用与设计精讲版）9.1算法与数据结构9.2程序设计基础9.3软件工程基础9.4数据库设计基础9.3.1软件工程概述计算机软件是计算机系统中与硬件相互依存的一部分，它是包括程序、数据及相关文档的集合。软件具有以下 6 个特点。1软件的定义与特点（1） 软件是逻辑实体，因此它与具有物理实体的工程对象有显著差异，人们能够将其记录在存储介质上，但无法看到软件本身的形态，只有运用逻辑思维才能了解它的功能、性能等特性。（2）与硬件

12、生产不同，软件一旦研制成功，便可通过拷贝得到大量相同的副本。9.3.1软件工程概述1软件的定义与特点（3）软件不存在物理实体，不会出现物理上的磨损、老化现象，但在软件生存周期中，为了适应硬件、环境及需求的变化，需要对软件进行修改，从而不可避免地引入错误，导致软件失效率升高，致使软件退化。（4）软件的开发、运行受计算机系统的限制，导致软件的移植性差。（5）软件开发涉及人类社会的各行各业，以及众多不同领域的知识，因此需要投入大量、高强度的脑力劳动，成本高、风险大。（6）软件的开发和运行可能涉及企业管理方式，甚至涉及人们的观念和心理、软件知识产权等问题。9.3.1软件工程概述2软件的生命周期通常把用

13、户要求转变成软件产品的过程称为软件开发的过程。软件的生命周期可分为以下3个阶段。软件定义阶段确定软件开发工作的目标，并确认目标的可行性。1软件开发阶段完成在定义阶段设计好的软件，通常包括总体设计、详细设计、编码和测试。2软件维护阶段维护软件 , 使其能够长期满足用户的需求。39.3.1软件工程概述3软件工程（1）软件工程的目标软件工程的目标是指在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性以及可操作性且满足用户需求的产品。（2）软件工程的原则软件在开发过程中，需要遵守软件工程的8条基本原则，这些原则适用于所有软件项目。抽象局部化信

14、息隐蔽确定性模块化一致性完备性可验证性9.3.1软件工程概述4软件的开发工具和开发环境现代软件工程方法之所以得以实施，其重要前提是软件开发工具和开发环境的保证，使软件在开发效率、维护效率和软件质量等多方面得到了改善。（1）软件开发工具软件开发工具是辅助软件进行开发工作的工具，它从单项工具的开发逐步向集成工具发展，促进了软件的开发速度，提高了软件的质量。（2）软件开发环境软件开发环境 ( 软件工程环境 ) 是全面支持软件开发过程的软件工具集合。9.3.2结构化分析方法1需求分析方法常见的需求分析方法有结构化分析方法和面向对象分析方法两种。结构化分析方法的实质是着眼于数据流，自顶向下，逐层分解，建

15、立系统的处理流程，并以数据流图和数据字典为主要工具，以建立系统的逻辑模型。面向对象分析方法是采用面向对象的风格进行系统分析和需求定义的方法。结构化分析方法面向对象分析方法9.3.2结构化分析方法2结构化分析常用工具常用的结构化分析工具包括以下4种。（3）判定树（4）判定表（1）数据流图（DFD）（2）数据字典（DD）9.3.2结构化分析方法3软件需求规格说明书（SRS）软件需求规格说明书既是描述需求中的重要文档，又是软件需求分析的主要成果。一份合格的软件需求规格说明书至少应满足以下 5 项要求。正确性无歧义性完整性可验证性一致性9.3.3结构化设计方法1概要设计概要设计也称为总体设计，其基本任

16、务包括以下4种。设计软件系统结构 数据结构及数据库设计 编写概要设计文档 概要设计文档评审9.3.3结构化设计方法2面向数据流设计方法面向数据流的设计方法定义了一些不同的映射方法，利用这些映射方法可以把数据流图变换成用结构图表示的软件结构。典型的数据流类型有以下2种（1）变换型信息沿输入通路进入系统，同时由外部形式变为内部形式，通过变换中心加工处理后，从输出通路转换为外部形式然后离开软件系统。（2）事务型软件引用中能够引发一个或多个处理，以完成某作业要求功能的作业数据流称为事务流，这种数据流图称为事务型数据流图。9.3.3结构化设计方法3详细设计详细设计的任务是为软件结构图中的每一个模块确定实

17、现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。常见的过程设计工具及其简介如表所示。9.3.4软件测试与调试1软件测试GB/T11457- -2006信息技术软件工程术语中对软件测试的定义表明软件测试是一个过程。（1）软件测试方法（2）软件测试过程单元测试确认测试集成测试系统测试白盒测试方法黑盒测试方法软件测试是一个过程，主要包含以下4个步骤。从是否需要执行被测软件的角度出发，软件测试可以分为静态测试和动态测试。主要包括以下2种方法。9.3.4软件测试与调试2程序调试在对程序进行了成功的测试之后将进入程序调试阶段，程序调试主要是在开发阶段进行，其任务是诊断和改正程序中的错误

18、。程序调试活动分为两步。第一步是找到程序中错误的确切性质、原因和位置第二步是对程序进行修改，以排除错误目录CONTENTS计算机基础（全国计算机等级考试二级 MS Office高级应用与设计精讲版）9.1算法与数据结构9.2程序设计基础9.3软件工程基础9.4数据库设计基础9.4.1数据库的基本概念1数据库管理系统数据库管理系统（Database Management System,DBMS）是管理数据库的机构，是一个负责数据库中数据的组织、操纵、维护、控制以及保护的系统软件。数据库管理系统属于系统软件，它既是数据库系统的核心，也是用户与操作系统之间的重要桥梁。9.4.1数据库的基本概念2数据

19、库系统数据库系统（Database System，DBS）由数据库、数据库管理系统、数据库管理员、硬件平台和软件平台 5 个部分组成，它是指引进数据库技术后的整个计算机系统，既能实现有组织地、动态地存储大量相关数据，又能提供数据处理和信息资源共享。 数据库系统的三级模式结构 ：数据库系统在其内部可分为三级模式，即概念模式、内模式和外模式。 数据库系统的两级映射 ：数据库系统在三级模式之间提供了两级映射，即外模式 / 概念模式的映射、概念模式 / 内模式的映射。9.4.2数据模型1E-R模型E-R 模型（实体联系模型）可将现实世界的要求转化成实体联系、属性等基本概念，以及它们之间的两个基本连接关系，并用 E-R 图将其直观地表示出来。实体间的联系分为以下3种类型。1一对一联系2一对多联系3多对多联系9.4.2数据模型3网状模型层次模型是用树形结构表示实体以及实体之间联系的模型。在层次模型中，