《Access-2010数据库基础与应用教学课件-第9章-全国计算机等级考试二级公共基础知识》由会员分享，可在线阅读，更多相关《Access-2010数据库基础与应用教学课件-第9章-全国计算机等级考试二级公共基础知识（96页珍藏版）》请在金锄头文库上搜索。
1、第9章全国计算机等级考试二级公共基础知识345软件工程基础数据库设计基础试题选解目 录CONTENTS2程序设计基础1基本数据结构与算法9.1 基本数据结构与算法9.1.1 数据和数据管理数据和数据管理 (1)算法:指解题方案的准确而完整的描述。算法不等于程序,也不等于计算机方法,程序的 编制不可能优于算法的设计。(2)算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确 的,此顺序将在有限的次数下终止。其特征如下:可行性。确定性。有穷性。拥有足够的情报。(3)算法的基本要素:一是对数据对象的运算和操作;二是控制结构。(4)指令系统:一个计算机系统能执行的所有指令的集合
2、。(5)基本运算:包括算术运算、逻辑运算、关系运算、数据传输。(6)算法的控制结构:顺序结构、选择结构、循环结构。(7)算法基本设计方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。(8)算法复杂度:算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要 的计算工作量,算法空间复杂度是指执行算法所需要的内存空间。9.1.2数据结构的基本概念数据结构的基本概念 (1)数据结构研究的3个方面。数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构。在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构。对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集
3、合。教学思想 (2)数据的逻辑结构。表示数据元素的信息。表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。(3)线性结构条件。有且只有一个根结点。每一个结点最多有一个前件,也最多有一个后件。(4)非线性结构:不满足线性结构条件的数据结构。9.1.3线性表及其顺序存储结构线性表及其顺序存储结构 (1)线性表是由一组数据元素构成的,数据元素的位置只取决于其自身的序号,元素之间的 相对位置是线性的。在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记 录构成的线性表又称为文件。(2)非空线性表的结构特征。有且只有一个根结点a1,它无前件。有且只有一个终端结点an,它无
4、后件。除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个 数n称为线性表的长度,当n=0时,称为空表。教学思想 (3)线性表的顺序存储结构具有以下两个基本特点:线性表中所有元素所占的存储空间是连续的。线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。(4)顺序表的运算:插入、删除。9.1.4栈和队列栈和队列 (1)栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插 入与删除的另一端称为栈底。栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据,栈具 有记忆作用。用top表示栈顶位置,用bottom表示栈底。(2)栈的基本运算
5、。插入元素称为入栈运算。删除元素称为退栈运算。读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。教学思想 (3)队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。rear指针 指向队尾,front指针指向队头。(4)队列是“先进行出”(FIFO)或“后进后出”(LILO)的线性表。9.1.5线性链表线性链表(1)数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结点 (2)结点由以下两部分组成:用于存储数据元素值,称为数据域。用于存放指针,称为指针域,用于指向前一个或后一个结点。教学思想 (3)在链式存储结构中,存储数据结构的存储空间可以不连
6、续,各数据结点的存储顺序与数 据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。(4)链式存储方式既可用于表示线性结构,也可用于表示非线性结构。(5)线性链表的基本运算:查找、插入、删除。9.1.6树与二叉树树与二叉树 (1)树是一种简单的非线性结构,所有元素之间具有明显的层次特性。(2)二叉树的特点。非空二叉树只有一个根结点。每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。(3)二叉树的基本性质。在二叉树的第k层上,最多有2k-1(k1)个结点。深度为m 的二叉树最多有2m-1个结点。度为0的结点(叶子结点)总是比度为2的结点多一个。教学思想 具有n个结
7、点的二叉树,其深度至少为log 2n+1,其中log 2n表示取log 2n的整数部分。具有n个结点的完全叉树的深度为log 2n+1。完全二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右 边的若干结点。二叉树存储结构采用链式存储结构,对于满二叉树与完全二叉树,可以按层序进 行顺序存储。教学思想 (4)二叉树的遍历。前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树。中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树。后序遍历(LRD),首先遍历左子树,然后遍历右子树,最后访问根结点。9.1.7查找技术查找技术 (1)顺序查找的使用情况
8、。线性表为无序表。表采用链式存储结构。(2)二分法查找只适用于顺序存储的有序表,对于长度为n的有序线性表,最坏情况只需比 较log 2n次。9.1.8排序技术排序技术 排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。(1)交换类排序法。冒泡排序法,需要比较的次数为n(n-1)/2。快速排序法。(2)插入类排序法。简单插入排序法,最坏情况需要n(n-1)/2次比较。希尔排序法,最坏情况需要O(n1.5)次比较(O为算法的时间复杂度为算法的时间复杂度)。(3)选择类排序法。简单选择排序法,最坏情况需要n(n-1)/2次比较。堆排序法,最坏情况需要O(n log 2n)次比较9.2 程序设
9、计基础 9.2.1 程序设计方法和风格程序设计方法和风格 (1)形成良好的程序设计风格的方法。源程序文档化。数据说明的方法。语句的结构。输入和输出。(2)注释分序言性注释和功能性注释,语句结构清晰第一、效率第二。9.2.2 结构化程序设计结构化程序设计 (1)结构化程序设计方法的4条原则。自顶向下。逐步求精。模块化。限制使用goto语句。(2)结构化程序的基本结构和特点。顺序结构:一种简单的程序设计,最基本、最常用的结构 选择结构:又称分支结构,包括简单选择和多分支选择结构,可根据条件,判断应该选择哪 一条分支来执行相应的语句序列。循环结构:可根据给定条件,判断是否需要重复执行某一相同程序段。
10、9.2.3面向对象的程序设计面向对象的程序设计 (1)面向对象的程序设计:20世纪60年代末 (2)面向对象方法的优点。与人类习惯的思维方法一致。稳定性好。可重用性好。易于开发大型软件产品。可维护性好。(3)对象是面向对象方法中最基本的概念,可以用来表示客观世界中的任何实体,对象是实 体的抽象。面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体,是构成 系统的一个基本单位,由一组表示其静态特征的属性和它可执行的一组操作组成。(4)属性即对象所包含的信息,操作描述了对象执行的功能,操作也称为方法或服务。(5)对象的基本特点。标识唯一性。分类性。多态性。封装性。模块独立性好。(6)类
11、是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象,对象是对应类的 一个实例。消息是一个实例与另一个实例之间传递的信息。(7)消息的组成。接收消息的对象的名称。消息标识符,也称消息名。零个或多个参数。(8)继承是指能够直接获得已有的性质和特征,而不必重复定义它们。继承分单继承和多重 继承。单继承指一个类只允许有一个父类,多重继承指一个类允许有多个父类。多态性是指同 样的消息被不同的对象接收时可导致完全不同的行动的现象。9.3 软件工程基础 9.3.1软件工程的基本概念软件工程的基本概念 (1)计算机软件是包括程序、数据及相关文档的完整集合。(2)软件的特点如下:软件是一种逻辑实体。软件
12、的生产与硬件不同,它没有明显的制作过程。软件在运行、使用期间不存在磨损、老化问题。软件的开发、运行对计算机系统具有依赖性,受计算机系统的限制,这导致了软件移植的 问题。软件复杂性高,成本昂贵。软件开发涉及诸多的社会因素。(3)软件按功能分为应用软件、系统软件、支撑软件(或工具软件)。软件危机主要表现在成 本、质量、生产率等问题。(4)软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准 和工序。(5)软件工程包括3个要素:方法、工具和过程。(6)软件工程过程是把软件转化为输出的一组彼此相关的资源和活动,包含4种基本活动:P软件规格说明。D软件开发。C软件确认。A软件演
13、进。(7)软件周期:软件产品从提出、实现、使用维护到停止使用退役的过程。(8)软件生命周期3个阶段:软件定义、软件开发、运行维护。主要活动阶段如下:可行性研究与计划制订。需求分析。软件设计。软件实现。软件测试。运行和维护。(9)软件工程的目标和与原则。目标:在给定成本、进度的前提下,开发出具有有效性、可靠性、可理解性、可维护性、可重 用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。基本目标:付出较低的开发成本;达到要求的软件功能;取得较好的软件性能;开发软件易 于移植;需要较低的费用;能按时完成开发,及时交付使用。基本原则:抽象、信息隐蔽、模块化、局部化、确定性、一致性、完
14、备性和可验证性。(10)软件工程的理论和技术性研究的内容主要包括软件开发技术和软件工程管理。(11)软件开发技术包括软件开发方法学、开发过程、开发工具和软件工程环境。9.3.2结构化分析方法结构化分析方法 (1)结构化分析方法的核心和基础是结构化程序设计理论。(2)需求分析方法如下:结构化需求分析方法。面向对象的分析方法。从需求分析建立的模型特性来分:静态分析和动态分析。(3)结构化分析方法的实质:着眼于数据流,自顶向下,逐层分解,建立系统的处理流程,以数 据流图和数据字典为主要工具,建立系统的逻辑模型。(4)结构化分析的常用工具。数据流图:描述数据处理过程的工具,是需求理解的逻辑模型的图形表
15、示,它直接支持系 统功能建模。数据字典:对所有与系统相关的数据元素的一个有组织的列表,以及精确的、严格的定义,使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。判定树:从问题定义的文字描述中分清哪些是判定的条件、哪些是判定的结论,根据描述 材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系,根据它们构造判定树。数据字典是 结构化分析的核心。判定表:与判定树相似,当数据流图中的加工要依赖于多个逻辑条件的取值,即完成该加 工的一组动作是由于某一组条件取值的组合而引发的,使用判定表描述比较适宜。数据字典是 结构化分析的核心。(5)软件需求规格说明书的特点。正确性。无歧
16、义性。完整性。可验证性。一致性。可理解性。可追踪性。9.3.3结构化设计方法结构化设计方法 (1)软件设计的基本目标是用比较抽象的方式确定目标系统如何完成预定的任务,软件设计 是确定系统的物理模型。软件设计是开发阶段最重要的步骤,是将需求准确地转化为完整的软 件产品或系统的唯一途径。从技术观点来看,软件设计包括软件结构设计、数据设计、接口设计、过程设计。结构设计是定义软件系统各主要部件之间的关系。数据设计是将分析时创建的模型 转化为数据结构的定义。接口设计是描述软件内部、软件和协作系统之间及软件与人之间如何 通信。过程设计是把系统结构部件转换成软件的过程描述。从工程管理角度来看,软件设计分为概要设计和详细设计。软件设计的一般过程为:软件设 计是一个迭代的过程,先进行高层次的结构设计,后进行低层次的过程设计,穿插进行数据设计 和接口设计。(2)衡量软件模块独立性,可以使用耦合性和内聚性两个定性的度量标准。在程序结构中各 模块的内聚性越强,则耦合性越弱。优秀的软件应高内聚、低耦合。(3)软件概要设计的基本任务如下:设计软件系统结构。数据结构及数据库设计。编写概要设计文档。概要设计文档评审。
