全国计算机等级考试--公共基础.ppt

《全国计算机等级考试--公共基础.ppt》由会员分享，可在线阅读，更多相关《全国计算机等级考试--公共基础.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、All rights reserved：2WDragon课程内容课程内容数据结构与算法数据结构与算法程序设计基础程序设计基础软件工程基础软件工程基础数据库设计基础数据库设计基础All rights reserved：2WDragon算法基本概念算法基本概念v什么是算法什么是算法算法是指用系统的方法描述解决问题的策略算法是指用系统的方法描述解决问题的策略机制。机制。v算法的基本特征算法的基本特征有穷性、确定性、可行性、拥有足够的情报有穷性、确定性、可行性、拥有足够的情报v算法的构成要素算法的构成要素对数据对象的运算和操作、算法的控制结构对数据对象的运算和操作、算法的控制结构All rights

2、reserved：2WDragon算法复杂度算法复杂度v时间复杂度时间复杂度执行算法所需要的计算工作量。执行算法所需要的计算工作量。算法的工作量是问题规模的函数，即算法的工作量是问题规模的函数，即算法的工作量算法的工作量f(n)1、最坏情况复杂性、最坏情况复杂性2、期望复杂性、期望复杂性All rights reserved：2WDragon算法复杂度算法复杂度v空间复杂度空间复杂度执行算法所需要的内存空间。执行算法所需要的内存空间。包括算法程序所占空间、输入初始数据所占包括算法程序所占空间、输入初始数据所占空间及算法执行中所需额外空间。空间及算法执行中所需额外空间。v时空复杂度时空复杂度返回

3、All rights reserved：2WDragon数据结构基本概念数据结构基本概念v什么是数据结构什么是数据结构(DataStructure)数据结构是研究数据元素数据结构是研究数据元素(DataElement)之间抽象之间抽象化的相互关系和这种关系在计算机中的存储表示化的相互关系和这种关系在计算机中的存储表示(即即所谓数据的所谓数据的逻辑结构逻辑结构和和物理结构物理结构)，并对这种结构定，并对这种结构定义义相应的运算相应的运算，设计出相应的算法，而且确保经过，设计出相应的算法，而且确保经过这些运算后这些运算后所得到的新结构仍然是原来的结构类型所得到的新结构仍然是原来的结构类型。为了叙述

4、上的方便和避免产生混淆，通常把为了叙述上的方便和避免产生混淆，通常把数据的数据的逻辑结构统称为数据结构逻辑结构统称为数据结构，把，把数据的物理结构统称数据的物理结构统称为存储结构为存储结构(StorageStructure)。All rights reserved：2WDragon栈和队列栈和队列v1栈的定义栈的定义栈栈(stack)是一种是一种只允许在一端只允许在一端进行插入和删除进行插入和删除的的操作受限的线性表操作受限的线性表。在表中只允许进行插入和。在表中只允许进行插入和删除的一端称为栈顶删除的一端称为栈顶(top)，另一端称为栈底，另一端称为栈底(bottom)。当栈中无数据元素时，

5、称为空栈。当栈中无数据元素时，称为空栈。根据栈的定义可知，栈也被称为根据栈的定义可知，栈也被称为“后进先出后进先出”的的线性表。线性表。All rights reserved：2WDragon栈和队列栈和队列v2栈的基本运算栈的基本运算(1)入栈入栈：在栈：在栈s的顶部插入元素的顶部插入元素x，若栈满，则，若栈满，则返回返回FALSE；否则，返回；否则，返回TRUE。(2)出栈出栈：若栈：若栈s不空，则返回栈顶元素，并从不空，则返回栈顶元素，并从栈顶中删除该元素；否则，返回空元素栈顶中删除该元素；否则，返回空元素NULL。(3)读取栈顶元素读取栈顶元素：若栈：若栈s不空，则返回栈顶元不空，则返

6、回栈顶元素；否则返回空元素素；否则返回空元素NULL。All rights reserved：2WDragon栈和队列栈和队列v3队列的定义队列的定义队列队列(queue)是一种是一种只允许在一端只允许在一端进行插入，而进行插入，而在另一端在另一端进行删除的线性表，它是一种进行删除的线性表，它是一种操作受限操作受限的线性表的线性表。在表中只允许进行插入的一端称为队尾在表中只允许进行插入的一端称为队尾(rear)，只允许进行删除的一端称为队头只允许进行删除的一端称为队头(front)。当队列。当队列中无数据元素时，称为空队列。队列也被称为中无数据元素时，称为空队列。队列也被称为“先进先出先进先出

7、”表。表。All rights reserved：2WDragon栈和队列栈和队列v循环队列循环队列将顺序队列的存储区假想为一个环状的空间，如图所示。我将顺序队列的存储区假想为一个环状的空间，如图所示。我们可假想们可假想q-queue0接在接在q-queueMAXNUM-1的后面。的后面。当发生假溢出时，将新元素插入到第一个位置上，这样做，当发生假溢出时，将新元素插入到第一个位置上，这样做，虽然物理上队尾在队首之前，但逻辑上队首仍然在前。入列虽然物理上队尾在队首之前，但逻辑上队首仍然在前。入列和出列仍按和出列仍按“先进先出先进先出”的原则进行，这就是循环队列。的原则进行，这就是循环队列。MAX

8、NUM-101rearfront循环队列示意All rights reserved：2WDragon栈和队列栈和队列仅凭仅凭q-front=q-rear不能判定队列是空还不能判定队列是空还是满。是满。012345frontrear(b)ABC012345frontrear(a)012345ABCDEFfrontrear(c)循环队列示意图循环队列示意图（a）队列空；（）队列空；（b）队列非空；）队列非空；(c)队列满队列满返回返回All rights reserved：2WDragon线性链表线性链表v线性链表是线性表的链式存储结构，是一种线性链表是线性表的链式存储结构，是一种物理存物理存储单

9、元上非连续、非顺序的存储结构储单元上非连续、非顺序的存储结构，数据元素的，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。因逻辑顺序是通过链表中的指针链接次序实现的。因此，在存储线性表中的数据元素时，一方面要存储此，在存储线性表中的数据元素时，一方面要存储数据元素的值，另一方面要存储各数据元素之间的数据元素的值，另一方面要存储各数据元素之间的逻辑顺序，为此，将每一个存储结点分为两部分：逻辑顺序，为此，将每一个存储结点分为两部分：一部分用于存储数据元素的值，称为一部分用于存储数据元素的值，称为数据域数据域；另一部分用于存放下一个数据元素的存储结点的地另一部分用于存放下一个数据元素的存储结点的

10、地址，即指向后继结点，称为址，即指向后继结点，称为指针域指针域。All rights reserved：2WDragon线性链表线性链表此种形式的链表因只含有一个指针域，又称此种形式的链表因只含有一个指针域，又称为单向链表，简称单链表。图为单向链表，简称单链表。图2-7(a)所示为一所示为一个空线性链表。图个空线性链表。图2-6(b)所示为一个非空线性所示为一个非空线性链表（链表（a0，a1，a2，an-1）。）。a0a1a an-n-1 1 head head (a)(b)图图2-7 线性链表的存储结构线性链表的存储结构All rights reserved：2WDragon树与二叉树树与二

11、叉树v树结构的基本术语树结构的基本术语（1）结点的度）结点的度(Degree)树中的一个结点拥有的子树数称为该结点的度树中的一个结点拥有的子树数称为该结点的度(Degree)。一棵树的度是指该树中结点的最大度数。一棵树的度是指该树中结点的最大度数。度为零的结点称为叶子度为零的结点称为叶子(Leaf)或终端结点。或终端结点。度不为零的结点称分支结点或非终端结点。度不为零的结点称分支结点或非终端结点。除根结点之外的分支结点统称为内部结点。除根结点之外的分支结点统称为内部结点。根结点又称为开始结点。根结点又称为开始结点。All rights reserved：2WDragon树与二叉树树与二叉树v树

12、结构的基本术语树结构的基本术语（2）结点的层数）结点的层数(Level)和树的高度（和树的高度（Height）结点的层数结点的层数(Level)从根起算：从根起算：根的层数为根的层数为1其余结点的层数等于其双亲结点的层数加其余结点的层数等于其双亲结点的层数加1。双亲在同一层的结点互为堂兄弟。双亲在同一层的结点互为堂兄弟。树中结点的最大层数称为树的高度树中结点的最大层数称为树的高度(Height)或深度或深度(Depth)注意：注意：很多文献中将树根的层数定义为很多文献中将树根的层数定义为0。All rights reserved：2WDragon树与二叉树树与二叉树v二叉树的重要性质二叉树的重

13、要性质性质1 二叉树第二叉树第i层上的结点数目最多为层上的结点数目最多为2i-1(i1)性质2 深度为深度为k的二叉树至多有的二叉树至多有2k-1个结点个结点(k1)性质3 在任意在任意-棵二叉树中，若终端结点的个数为棵二叉树中，若终端结点的个数为n0，度为，度为2的结点数为的结点数为n2，则，则n0=n2+1性质4 具有具有n个结点的二叉树的深度至少为个结点的二叉树的深度至少为All rights reserved：2WDragon树与二叉树树与二叉树1、满二叉树、满二叉树(FullBinaryTree)一棵深度为一棵深度为k且有且有2k-1个结点的二个结点的二又树称为满二叉树。又树称为满二

14、叉树。满二叉树的特点：满二叉树的特点：（1）每一层每一层(k)上的结点数都达上的结点数都达到最大值到最大值(2k-1)。即对给定的高度，。即对给定的高度，它是具有最多结点数的二叉树。它是具有最多结点数的二叉树。（2）满二叉树中不存在度数为满二叉树中不存在度数为1的结点，每个分支结点均有两棵的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最高度相同的子树，且树叶都在最下一层上。下一层上。ACBGFEDAll rights reserved：2WDragon树与二叉树树与二叉树2、完全二叉树、完全二叉树(CompleteBinaryTree)若一棵二叉树至多只有最下面的两层上结若一棵二叉树至

15、多只有最下面的两层上结点的度数可以小于点的度数可以小于2，并且最下一层上的，并且最下一层上的结点都集中在该层最左边的若干位置上，结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。则此二叉树称为完全二叉树。ACBFEDAll rights reserved：2WDragon树与二叉树树与二叉树v遍历算法遍历算法1先序遍历：先序遍历：根结点根结点左子树左子树右子树。右子树。2中序遍历：中序遍历：左子树左子树根结点根结点右子树右子树3后序遍历：后序遍历：左子树左子树右子树右子树根结点。根结点。All rights reserved：2WDragon树与二叉树树与二叉树ADBCFE先序序列

16、先序序列ABDCEF中序序列中序序列DBAECF后序序列后序序列DBEFCA返回返回All rights reserved：2WDragon查找技术查找技术v顺序查找基本思想顺序查找基本思想v折半查找（二分法）基本思想折半查找（二分法）基本思想All rights reserved：2WDragon排序技术排序技术v冒泡排序基本思想冒泡排序基本思想v直接插入排序基本思想直接插入排序基本思想v希尔排序希尔排序v选择排序选择排序All rights reserved：2WDragon排序技术排序技术v按平均时间将排序分为四类：按平均时间将排序分为四类：（1）平方阶）平方阶(O(n2)排序排序 例如

17、直接插入、直接选择和冒泡排序；例如直接插入、直接选择和冒泡排序；（2）线性对数阶）线性对数阶(O(nlgn)排序排序 如快速、堆和归并排序；如快速、堆和归并排序；（3）O(n1+)阶排序阶排序 是介于是介于0和和1之间的常数，即之间的常数，即01，如希尔排序；，如希尔排序；（4）线性阶）线性阶(O(n)排序排序 如桶、箱和基数排序。如桶、箱和基数排序。All rights reserved：2WDragon排序技术排序技术v各种排序最坏情况下的时间复杂度：各种排序最坏情况下的时间复杂度：冒泡排序冒泡排序快速排序快速排序简单插入简单插入简单选择简单选择希尔排序希尔排序堆排序堆排序顺序查找顺序查找

18、二分查找二分查找All rights reserved：2WDragon程序设计基础程序设计基础v结构化程序设计结构化程序设计v面向对象程序设计面向对象程序设计All rights reserved：2WDragon结构化程序设计结构化程序设计v设计原则设计原则1、自顶向下自顶向下：先考虑总体，后考虑细节2、逐步求精逐步求精：对复杂问题，可以设计子目标作过渡，逐步细化3、模块化模块化：把要解决的总目标分解为分目标，进一步分解为具体的小目标，把每个小目标称为一个模块4、限制使用限制使用goto语句语句All rights reserved：2WDragon结构化程序设计结构化程序设计v结构化程序

19、的基本结构结构化程序的基本结构结构化程序设计（Structured Programming，简称SP）方法是由E.Dijkstra等人于1972年提出来的，它建立在Bohm、Jacopini证明的结构定理的基础上。结构定理指出：任何程序逻辑都可以用顺序、任何程序逻辑都可以用顺序、选择和循环等三种基本结构来表示。选择和循环等三种基本结构来表示。All rights reserved：2WDragon面向对象程序设计面向对象程序设计v对象基本特点对象基本特点1、标识唯一性标识唯一性：指对象由内在本质是可以区分的：指对象由内在本质是可以区分的2、分类性分类性：指可以将相同属性和操作的对象抽象：指可以

20、将相同属性和操作的对象抽象成类成类3、多态性多态性：指同一个操作可以是不同对象的行为：指同一个操作可以是不同对象的行为4、封装性封装性：从外面只能看到对象的外部特征：从外面只能看到对象的外部特征5、模块独立性好模块独立性好：对象内部元素彼此结合紧密，：对象内部元素彼此结合紧密，内聚性强内聚性强All rights reserved：2WDragon软件工程基础软件工程基础v软件工程基本概念软件工程基本概念v结构化分析方法结构化分析方法v结构化设计方法结构化设计方法v软件测试软件测试v程序调试程序调试All rights reserved：2WDragon软件工程基本概念软件工程基本概念v软件定

21、义软件定义软件程序数据文档软件程序数据文档All rights reserved：2WDragon软件工程基本概念软件工程基本概念v软件功能分类软件功能分类1)应用软件应用软件事务处理软件、人工智能软件、嵌入式软件事务处理软件、人工智能软件、嵌入式软件2)系统软件系统软件操作系统、编译程序、数据库管理系统操作系统、编译程序、数据库管理系统3)支撑软件支撑软件编码软件工具、项目管理软件、过程控制软件编码软件工具、项目管理软件、过程控制软件All rights reserved：2WDragon软件工程基本概念软件工程基本概念v软件工程定义软件工程定义方法：完成软件工程项目的技术手段。方法：完成软

22、件工程项目的技术手段。工具：支持软件的开发、管理、文档的生成。工具：支持软件的开发、管理、文档的生成。过程：支持软件开发的各个环节的控制、管理。过程：支持软件开发的各个环节的控制、管理。软软件件工工程程三三要要素素All rights reserved：2WDragon软件工程基本概念软件工程基本概念v软件生命周期软件生命周期包含软件定义、软件设计、包含软件定义、软件设计、软件使用与维护三阶段，软件使用与维护三阶段，而又可以具体分成几个子而又可以具体分成几个子阶段。阶段。可行性研究可行性研究需求分析需求分析总体设计总体设计详细设计详细设计实现实现测试测试使用使用维护维护退役退役定定义义阶阶段段

23、开开发发阶阶段段维维护护阶阶段段All rights reserved：2WDragon软件工程基本概念软件工程基本概念v软件工程原则软件工程原则1)抽象抽象2)信息屏蔽信息屏蔽3)模块化模块化4)局部化局部化返回返回5)确定性确定性6)一致性一致性7)完备性完备性8)可验证性可验证性All rights reserved：2WDragon结构化分析方法结构化分析方法v需求分析阶段的工作需求分析阶段的工作1)需求获取：目的是确定对目标系统的各方面需求。需求获取：目的是确定对目标系统的各方面需求。2)需求分析：对获取的需求进行分析和综合，最终给出系需求分析：对获取的需求进行分析和综合，最终给出系

24、统的解决方案和目标系统的逻辑模型。统的解决方案和目标系统的逻辑模型。3)编写需求分析规格说明书：为各人员间交流提供方便和编写需求分析规格说明书：为各人员间交流提供方便和控制软件开发过程的进度。控制软件开发过程的进度。4)需求评审：需求分析最后一步，验证需求文档的一致性、需求评审：需求分析最后一步，验证需求文档的一致性、可行性、完整性和有效性。可行性、完整性和有效性。All rights reserved：2WDragon结构化分析方法结构化分析方法v常见需求分析方法常见需求分析方法结构化分析方法结构化分析方法：包括：包括面向数据流的结构化分析方法面向数据流的结构化分析方法(SA-Structu

25、redAnalysis)面向数据结构的面向数据结构的Jackson方法方法(JSD-JacksonSystemDevelopmentmethod)面向数据结构的结构化数据系统开发方法面向数据结构的结构化数据系统开发方法(DSSD-DataStructuredSystemDevelopmentmethod)面向对象的分析方法面向对象的分析方法(OOA-Object-Orientedmethod)All rights reserved：2WDragon结构化分析方法结构化分析方法v常用工具数据流图常用工具数据流图(DFD-DataFlowDiagram)v常用工具数据字典常用工具数据字典(DD-D

26、ataDictionary)v判定表判定表v判定树判定树All rights reserved：2WDragon结构化设计方法结构化设计方法v软件设计基本原理模块化软件设计基本原理模块化v软件设计基本原理信息屏蔽软件设计基本原理信息屏蔽v软件设计基本原理模块独立性（高内聚，软件设计基本原理模块独立性（高内聚，低耦合）低耦合）All rights reserved：2WDragon结构化设计方法结构化设计方法v概要设计概要设计All rights reserved：2WDragon结构化设计方法结构化设计方法v详细设计程序流程图详细设计程序流程图(PDF)v详细设计问题分析图详细设计问题分析图(

27、PAD)v详细设计详细设计N-S图图v详细设计过程设计语言详细设计过程设计语言(PDL)v详细设计判定表详细设计判定表v详细设计判定树详细设计判定树All rights reserved：2WDragon软件测试软件测试v软件测试定义软件测试定义为了发现程序中的错误。为了发现程序中的错误。All rights reserved：2WDragon软件测试v软件测试步骤1单元测试单元测试:又称模块测试。又称模块测试。2集成测试集成测试:将模块集成为系统的过程中可能出现的问题将模块集成为系统的过程中可能出现的问题3有效性测试：使用实际数据进行测试有效性测试：使用实际数据进行测试4.系统测试系统测试系

28、统测试是把通过有效性测试的软件，与整个系统的其系统测试是把通过有效性测试的软件，与整个系统的其他元素结合起来测试。他元素结合起来测试。第一种方法是黑盒测试，第二种方法是白盒测试。第一种方法是黑盒测试，第二种方法是白盒测试。白盒白盒测测路径，黑盒测功能。路径，黑盒测功能。All rights reserved：2WDragon程序调试程序调试v调试步骤调试步骤调试过程由两个部分组成：首先，确定程序中错误的确切性质和位置；调试过程由两个部分组成：首先，确定程序中错误的确切性质和位置；然后，对程序代码进行分析，确定问题的原因，并设法改正这个错误。然后，对程序代码进行分析，确定问题的原因，并设法改正这

29、个错误。All rights reserved：2WDragon程序调试程序调试v调试方法强行排错调试方法强行排错v调试方法回溯法调试方法回溯法v调试方法归纳法调试方法归纳法v调试方法演绎法调试方法演绎法All rights reserved：2WDragon数据库设计基础数据库设计基础v数据库系统基本概念数据库系统基本概念v数据模型数据模型v关系代数关系代数v数据库设计与管理数据库设计与管理All rights reserved：2WDragon数据库系统基本概念数据库系统基本概念v数据、数据库、数据库管理系统数据、数据库、数据库管理系统数据数据(data)数据库数据库(DB)数据库管理系统

30、数据库管理系统(DBMS)数据库系统数据库系统(DBS)All rights reserved：2WDragon数据库系统基本概念数据库系统基本概念v数据库系统的发展数据库系统的发展人工管理人工管理文件系统文件系统数据库数据库系统系统All rights reserved：2WDragon数据库系统基本概念数据库系统基本概念v数据库系统三级模式结构数据库系统三级模式结构1)外模式外模式(用户模式用户模式)：数据库用户看到的数据视图；：数据库用户看到的数据视图；2)概念模式概念模式(逻辑模式逻辑模式)：数据结构和特性的描述；：数据结构和特性的描述；3)内模式内模式(物理模式物理模式)：数据在数据

31、库内部的表示。：数据在数据库内部的表示。All rights reserved：2WDragon数据模型数据模型vE-R(Entity-Relationship)模型的基本概念模型的基本概念w实体：实体：客观存在并可相互区分的事物。客观存在并可相互区分的事物。w属性：属性：实体所具有的特性。实体所具有的特性。w联系：联系：实体之间及其内部的关联。实体之间及其内部的关联。All rights reserved：2WDragon数据模型数据模型v层次模型层次模型v网状模型网状模型v关系模型关系模型All rights reserved：2WDragon数据模型数据模型v关系模型完整性约束关系模型完

32、整性约束1)实体完整性约束实体完整性约束：任何实体具有的某种唯：任何实体具有的某种唯一性标识。一性标识。2)参照完整性约束参照完整性约束：某些属性的取值需要参：某些属性的取值需要参照其他关系的属性。照其他关系的属性。3)用户定义的完整性约束用户定义的完整性约束：某一具体应用所：某一具体应用所涉及的数据必须满足的语义要求。涉及的数据必须满足的语义要求。返回All rights reserved：2WDragon集合运算集合运算并并:R S=t|t RV t S差差:R-S=t|t R t SRSRSRSRS交交:RS=t|t R t S笛卡尔积笛卡尔积:RS=tr ts|tr R ts SAll

33、 rights reserved：2WDragon两种常用连接两种常用连接:等值连接等值连接自然连接自然连接在笛卡尔积中选取在笛卡尔积中选取A,B属性相等的些元组属性相等的些元组等值连中两个比较分量是相同的等值连中两个比较分量是相同的属性属性,且去掉重复的属性且去掉重复的属性R S=tr ts|tr R ts S tr A=ts BA=BR S=tr ts|tr R ts S tr B=ts B关系代数关系代数v关系运算关系运算选择选择(Selection)投影投影(Projection)连接连接(Jion)除除(division)All rights reserved：2WDragon数据库设计与管理数据库设计与管理v数据库设计概述数据库设计概述系统规划，需求分析，概念设计，逻辑设计，物系统规划，需求分析，概念设计，逻辑设计，物理设计和系统实施理设计和系统实施。