全国计算机等级公共基础课程

全国计算机等级培训,二级公共基础知识,第一章算法与数据结构,第二章程序设计基础,第三章软件工程基础,第四章数据库设计基础,问题,方法和步骤,算法,数据及数据关系,数据结构,相应程序方法、结构和风格,数据管理,程序设计,数据库设计,相应开发方法、工具和过程,软件工程,第一章数据结构与算法,知识图样,算法及数据结构,算法,数据结构,定义,特征,复杂度：,可行性,确定性,有穷性,拥有足够的情报,时间复杂度、空间复杂度,数据逻辑结构,线性结构,非线性结构,数据存储结构,顺序存储,链式存储,索引存储,散列存储,数据运算,查找,修改,树,二叉树,树的遍历,线性表,（栈、队列）,（顺序查找、二分法查找）,排序,插入,删除、修改,（交换、插入、选择排序）,1.1算法1、定义：是指解题方案的准确而完整的描述。2、说明：算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。3、算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。,特征包括：（1）可行性：执行有限次来实现（2）确定性：算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（3）有穷性：算法必须能在有限的时间内做完，取能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。有零个或多个输入，有一个或多个输出。,4、算法复杂度：包含算法时间复杂和算法空间复杂度，用来衡量一个算法的优劣。（1）、算法时间复杂度：A、定义：是指执行算法所需要的计算工作量。B、记作：T(n)=o(f(n)C、说明：与问题规模成正比例；与特定问题规模的输入数据有关。（2）、算法空间复杂度是：A、定义：指执行这个算法所需要的内存空间。B、记作：S(n)=o(f(n)C、说明：与问题规模相关的存储空间；与之外的额外空间。,1、定义：数据结构是指相互有关联的数据元素的集合。,1.2数据结构的基本概念,2、数据结构研究的三个方面：（1）数据的逻辑结构：数据集合中和数元素之间所固有的逻辑关系。（2）数据的存储结构：在对数据进行处理时，各数据元素在计算机中的存储关系。（3）数据的运算：对各种数据进行运算。,3、数据的逻辑结构：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件固有的逻辑关系。,4、数据的存储结构：顺序、链接、索引等。,5、数据的运算：查找、排序、插入等。,6、数据结构表示：A、二元组：B=（D，R）D=数据1，数据2，数据nR=（数据1，数据2），B、图形：集合、线性结构、树型结构、图状结构。,7、数据逻辑结构中：A、线性结构：线性表、栈、队列、线性链表（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。B、非线性结构：树、二叉树、图等不满足线性结构条件的数据结构。,1.3线性表及其顺序存储结构,1、线性表：由若干个数据元素构成的有限序列，表中除了第1个元素外，有且只有一个前件，除最后1个元素外，有且只有一个后件。,2、非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。,3、说明：结点个数n称为线性表的长度，当n=0时，称为空表。,4、线性表的顺序存储结构具有以下两个基本特点：顺序表（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数元素在存储空间中是按逻辑顺序依次存放的。,5、说明：ai的存储地址为：ADR（ai）=ADR(a1)+（i-1）k，ADR（a1）为第一个元素的地址，k代表每个元素占的字节数。,6、运算：A、插入：要在第i(1=i=n)个元素之前插入1个元素，向后移动ni+1个位置。B、删除：要删除第i(11,则该结点的父结点编号为INT（k/2）；若2k=n,则编号为k的结点左子编号为2k；否则该结点无左子结点（也无右子结点）；若2k+1=n,则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。,5、满二叉树：是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2个结点深度为m的满二叉树有2-1个结点。6、完全二叉树：是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。,结论：满二叉树可以是完全二叉树，完全二叉树不可以是满二叉树。,7、二叉树存储结构：二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。,8、二叉树的遍历：,（1）、定义：是指不重复地访问二叉树中的所有结点。（2）、分类：A、前序：根左右（DLR）B、中序：左根右（LDR）C、后序：左右根（LRD）,1.7查找技术,1、顺序查找：（1）线性表为无序表；（2）有序表采用链式存储结构。（3）对于长度为n的有序链表或无序表，最坏情况下需要比较n次。2、二分法查找：（1）只适用于顺序存储的有序表。（2）对于长度为n的顺序存储的有序表，最坏情况只需比较log2n次。,1.8排序技术,1、排序：是指将一个无序序列整理成按值的有序表。,2、分类：（1）交换类：A、冒泡排序法：需要比较的次数为n(n-1)/2B、快速排序法：（2）插入类：A、直接插入法：最坏情况需要比较的次数为n(n-1)/2B、希尔排序法：最坏情况需要O（n1.5）次比较（3）选择类：A、简单排序法：最坏情况需要n(n-1)/2次比较B、堆排序法，最坏情况需要O（nlog2n）次比较,第二章程序设计基础,知识图样,程序设计基础,良好的程序设计风格,主导思想：清晰第一、效率第二,目体要求：源程序文档化、数据说明的方法、语句的结构、输入和输出,注释的写法,结构化程序设计方法,原则,基本结构,优缺点,应用,面向对象程序设计方法,定义,优缺点,基本概念（类、对象、属性、方法、实例、消息、继承、多态、重载）,一、程序设计风格：,1、总原则：,清晰第一，效率第二,2、包括：,源程序文档化：,数据说明的方法：易于理解和维护,语句的结构：清晰第一，效率第二，简单易懂,程序的输入和输出：方便用户的使用,符号命名的技巧,程序注释,序言性注释：一般在程序开头,功能性注释：嵌在源程序中,书写格式,二、结构化程序设计：,1、原则：,自顶向下,逐步求精,模块化,限制使用goto语句,A、用一个非结构化的程序设计语言支实现一个结构化的构造。,B、若不使用goto语句会使功能模糊。,C、在某种可以改善而不是损害程序可读性的情况下可用。,三、结构化程序设计的基本结构：,顺序结构,选择结构,重复结构（循环结构）,当型,直型,两路分支,多路分支,四、结构化程序设计的优缺点：,1、优点：,易于理解、使用和维护,提高了编程的工作效率，降低了软件开发成本,2、缺点：,由于内在的高耦合，低内聚性，对于大型复杂软件的开发出现软件危机，难以对系统进行维护。,五、结构化程序设计的应用中的把握：,使用三种结构等有限的控制结构表示程序的控制逻辑。,选用的控制结构只准许一个入口和一个出口。,复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现。,程序语句组成容易识别的块，每块只有一个入口和一个出口。,语言中所没有的控制结构，应采用前后一致的方法来模拟。,严格控制goto语句的使用。,六、面向对象程序设计：,1、面向对象方法：,1）、定义：,是一种运用对象、类、继承、封装、聚合、关联、消息、多态性等概念来构造系统的软件开发方法。,2）、面向对象的方法与技术开始走向实用的标志性语言：,Smalltalk,3）、对比：,A、传统结构化程序设计方法的核心是算法；,B、面向对象的核心是对象（类）。,2、面向对象方法的优缺点：,1）、与人类思维习惯一致；,2）、稳定性好；,3）、可重用性好；,4）、易于开发大型软件产品；,5）、可维护性好。,3、基本概念：,1）、对象：,是软件系统中用来描述客观事物的一个实体。由对象名、属性和操作三部分组成。,2）、类：,是具有相同属性和服务的一组对象的集合（抽象）。,注：类可以用来创建对象，对象是类的一个实例！,3）、封装：（对象）,是一种信息隐蔽技术。,目的：将对象的使用者和对象的设计者分开。,4）、继承：（类）,是指使用已经定义好的类来定义一个新类，原类与新类的关系是一般类与特殊类，被继承与继承的关系。,注：分为多重继承和单继承,5）、消息：,是指一个实例与另一个实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，统一了数据流和控制流。由“接收消息的对象名称”、“消息名”和“零个或多个参数”组成。,6）、多态与重载：,A、多态性是指同样的消息被不同的对象接收时可导致完全不同的行为。,B、要通过方法重载和方法重写来实现多态。,7）、关联与链：,A、关联：类之间的静态联系。,B、链：关联的实例。,第三章软件工程基础,知识图样,软件工程基础,软件工程的基本概念,软件工程的生命同期理论,软件（定义、分类）,软件危机,软件工程（定义、三个要素、核心思想、目标、研究内容、原则）,软件开发工具,软件开发环境,可行性研究与计划制定,需求分析（基本概念、常见方法、结构化分析方法、规格说明书）,软件设计（基本概念、基本原理、结构化设计方法、概要设计、详细设计）,软件实现,软件测试（基本概念、目的、准则、常用技术和方法、分类、步骤）,软件调试（基本概念、步骤、原则、方法、补丁程序）,运行和维护,一、软件工程：,1、软件：,1）、定义：,程序+数据+相关文档,2）、3种分类：,注：是一种逻辑产品！,应用软件、系统软件、支撑软件(工具软件),2、软件危机：,1）、定义：,是人们在软件开发、使用和维护过程中所遇到的一系列严重问题。,2）、时间：20世纪60年代末后。,3）、主要3方面：,成本、质量和生产,4）、主要原因：,软件开发和维护方法不正确,3、软件工程：,1）、定义：,就是试图用工程、科学和数学的原理与方法研制、维护计算机软件的有关技术及管理方法。,2）、3要素：,方法：,工具：,过程：,是完成软件工程项目的技术手段。,用于支持软件的开发、管理及文档生成。,用于支持软件开发的各个环节的控制和管理。,机器可执行的,机器不可执行的,二、软件过程：,1、定义：,是指把输入转化为输出的一组彼此相关的资源和活动。（资源+活动）,2、4个基本活动：,软件规格说明（P）、软件开发（D）、软件确认（C）、软件演进（A）,三、软件生命同期：,1、定义：,是指将软件产品从提出、实现、使用维护到停止使用退役的过程。,2、3个阶段：,软件定义期：,软件开发期：,软件维护期：,问题定义、可行性研究和需求分析。（SA）,系统设计（概要设计）、详细设计、编码和测试。,运行、维护。（核心周期）,四、软件工程的目标：,是在给定的成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。,五、软件工程的原则：8个原则。,抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。,六、软件工程的研究内容：,软件开发技术：,软件工程管理：,软件开发方法学、开发过程、开发工具和软件工程环境。,软件管理学、软件工程经济学、软件心理学等内容。,七、软件开发工具与环境：,软件开发工具：,软件开发环境：,最初的软件开发工具只包含纯程序设计语言，不含其他环节，如需求分析、软件设计等环节的工具支持。,是指全面支持软件开发全过程的软件工具集合。,八、需求分析：,1、定义：,是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。,2、主要工作：,需求获取、需求分析、软件需求规格说明书（SRS）、需求审评。,3、常用方法有两种：结构化分析方法、面向对象的分析方法（OOA）,1）、结构化分析方法：,主要包括：面向数据流的结构化分析方法，面向数据结构的Jackson方法（JSD），面向数据结构的结构化数据系统开发方法（DSSD）。,2）、面向对象的分析方法：,分为静态分析方法、动态分析方法。,九、结构化方法：,1、定义：,是比较成熟的软件开发方法。,2、3个方面：,分析法（SA）、设计法（SD）、程序设计方法（SP）。,3、核心和基础：,结构化程序设计理论,十、结构化分析方法（SA）：,1、定义：,是指结构化程序设计理论在软件需求分析阶段的应用。,2、实质：,着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。,3、常用工具：,数据流图（DFD）、数据字典（DD）、判定表和判定树。,十一、数据流图（DFD）：,1、定义：,从数据传递和加工的角度来刻画数据从输入到输出的移动变换过程。,2、功能：,描述数据处理过程，也是需求理解的逻辑模型的图形表示，直接支持系统的功能建模。,3、组成：,数据流、数据处理、数据存储、外部实体,十二、数据字典（DD）：,1、重要性：,是SA方法的核心。,2、作用：,对DFD中出现的被命名的图形元素的确切解释。,3、内容：,通常包含的信息有名称、别名、使用、内容描述与补充信息等。,十三、判定表：,1、前提：,当数据流图中的加工要依赖于多个逻辑条件的取值时。（即完成该加工的一组动作是由于某一组条件的组合引发的。）,2、组成：,基本条件、条件项、基本动作、动作项,3、图样：,基本条件,条件项,基本动作,动作项,十四、判定树：,1、前提：同判定表。,2、与判定表的比较：,1）、是判定表的变形。,2）、使用判定树进行描述，应先从问题定义的文字描述中分清哪些是判定的条件，哪些是材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们构造判定树。,十五、结构化设计方法（SD）：,1、基本目标：,用比较抽象概括的方式确定目标系统如何完成预定的任务。（软件设计是确定系统的物理模型。）,2、软件设计组成：,1）、,从工程管理角度分析：概要设计、详细设计（过程设计）,2）、从技术观点分析：软件结构设计、数据设计、接口设计、过程设计,3、软件设计的基本原理：,1）、抽象：,2）、模块化：,3）、信息隐蔽：,4）、模块独立性：,是思维工具，它的层次从概要设计到详细设计逐步降低。,把一个待开发的软件分解成若干小的、简单的部分。,主要通过封装来实现。,每个模块只完成系统要求的独立的子功能，与其他模块的联系少且接口简单。,十六、模块独立性：,1、作用：,模块的独立程度是评价设计好坏的重要标准。,2、衡量软件的模块独立性的方法：,1）、耦合性：,2）、内聚性：,模块间的紧密程度,模块内部的联系,（小）,（大）,十六、概要设计：,1、主要任务：,1）、设计软件系统结构,2）、设计数据结构及数据库,3）、编写概要设计文档,4）、概要设计文档的审评,2、常见的软件结构设计工具：,结构图（SC）=程序结构图,1）、定义：,用于描述软件系统的层次和分块结构关系，反映了整个系统的功能实现以及模块之间的联系和通讯，是未来程序中的控制层次体系。,2）、基本图形符号：,模块、调用、数据,数据信息,控制信息,3、典型的数据流类型：,1）、变换型,2）、事务型,十七、详细设计：,1、主要任务：,是为软件结构图中的每个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。,2、常见的详细设计工具有以下3种：,1）、图形工具：,2）、表格工具：,3）、语言工具：,PFD（程序流程图）、N-S、PAD（问题分析图）、HIPO,判定表,PDL（伪代码）,3、PFD：,1）、分类：,2）、5种基本控制结构：,粗流程图（抽象级流程图）,细流程图（实现流程图）,顺序结构、选择结构、多分支选择结构、当型循环结构、直到型循环结构,3）、基本图符：,处理框,起止框,判断框,输入与输出框,控制流,十八、软件测试：,1、测试的目的：,查找错误。,2、软件测试的过程：,静态测试：,动态测试：运行（以白箱法为主）,自动测试：利用工具,讨论,走查,静态分析工具,动态分析工具,综合测试评估工具,3、测试的层次：,模块测试（单元测试）：,整体测试：,高级测试：,驱动模块,承接模块,自顶向下,自底向上,功能测试：以黑箱法主,系统测试,验收测试,安装测试,4、测试用例的设计方法：,白箱法（白盒测试）、黑箱法（黑盒测试）,5、白箱法：又称逻辑覆盖测试,语句覆盖,分支覆盖,条件覆盖,组合条件覆盖,6、黑箱法：,等价分类法,边值分析法,因果图法,错误推测法（猜错法）,十九、软件调试：在测试成功后开始,1、调试的目的：发现后改正错误。,2、与测试的区别：二级公共基础教程P86,4、调试方法：,强行排错法、回溯法、原因排除法（演绎法、归纳法、二分法）,3、基本步骤：,错误定位、修改设计和代码,用于软件确认测试,用于测试结构,第四章数据库设计基础,知识图样,数据库设计基础,数据库基本概念,数据模型基础知识,关系代数基础知识,数据库设计方法与步骤,数据库,数据,数据库管理系统,数据库系统,数据的独立性,基本概念（定义、要素、分类）,概念模型、逻辑模型、物理模型,层次模型、网状模型、关系模型,1、传统的集合运算（并、差、交、广义笛卡尔积）,2、专门的关系运算（选择、投影、连接、除）,3、比较运算,4、逻辑运算,1、方法,2、步骤,需求分析、概念结构分析、逻辑结构分析、物理结构分析、数据库运行和管理,一、数据：,1、定义：是指存储在某一种媒体上能够识别的物理符号。（是描述客观事物的符号记录。）第一方面：描述事物特性的数据内容。第二方面：存储在某一种媒体上的数据形式。（形式多样化）,注：数据是数据库中存储的基本对象。,3、数据库中数据的特点：按照一定的数据模型来组织、描述和存储，具有较小的冗余度和较高的独立性和易扩展性，并为各种用户所共享。,2、分类：1）、文本形式：数字、字母、文字、其他特殊字符组成。2）、多媒体形式：图形、图像、动画、影像、声音等。,二、数据处理：,1、定义：将数据转换成信息的过程。,注：信息被加工成特定形式的数据，且存在意义。,2、处理图样：,数据,信息,数据管理,加工,管理（技术）,现实世界（客观世界）：原始形式,观念世界（信息世界）：头脑中反映主要对象实体,数据世界：数据模型来描述,1）、人工管理,2）、文件系统,3）、数据库系统,分布式数据库系统,面向对象数据库系统,3、数据管理：,1）、人工管理：,A、特点：数据与程序不具有独立性，一组数据对应一组程序。数据不长存且不共享，程序运行结束退出。（数据冗余）,B、图样：,应用程序1,数据组1,应用程序2,数据组2,2）、文件系统：,A、特点：有了程序文件和数据文件，数据文件可长存。一个程序文件可使用多个数据文件，不同的程序文件可用同一数据文件。（数据与程序有一定独立性）但数据文件各自孤立，数据不能共享，也产生冗余。,B、图样：,应用程序1,应用程序2,应用程序3,OS,数据文件1,数据文件2,数据文件3,3）、数据库系统：,A、特点：采用了数据库，运用数据库技术，使数据具有了整体的独立性，出现数据结构化，使充分共享，减少了冗余，数据与程序彼此独立，使数据有了安全性和完整性统一。,B、图样：,应用程序1,应用程序2,应用程序3,数据库（DB）,C、发展：,网络、层次数据库,关系数据库,集中式,分布式,面向对象,与网络,紧密结合,松散结合,第一代数据库系统,第二代,第三代,三、数据库：,1、定义：是指长期存储在计算机内的、有组织的、可共享的数据集合。（是存储在计算机存储设备上，结构化的相关数据集合。）,2、特点：具有最小的冗余度，却有最高的独立性。（程序与数据之间的独立性）,注：对数据处理应用的专门技术数据库技术,3、数据库技术的主要目标：,有效地管理和存取大量的数据资源。,提高数据的共享性,减少数据的冗余度,提供数据与应用程序的独立性,一致性,完整性,4、数据库技术的根本目标：,解决数据的共享问题。,数据是结构化的，是面向系统的。,数据具有独立性,保证了数据的完整性，安全性和并发性,物理独立性,逻辑独立性,DB,四、数据库管理系统：,DBMS,1、定义：为数据库的建立、使用和维护而配置的依赖于OS的软件。,2、特点：数据库系统的核心。有一套独立于OS的存取数据的命令，且数据存储空间的分配由自己完成。,五、数据库系统：,DBS,1、定义：是引进数据库技术后的计算机系统。,2、组成：,DBS,硬件系统,DB集合,DBMS,相关软件,OS,编译系统,应用开发工具,相关人员,DBA,用户,DBAS（数据库应用系统）,注：常用的DBMS有SQLServer、VisualFoxPro、Oracle、DB2等。,3、特点：,1）、,实现数据共享、减少冗余。,2）、,采用特定的数据模型，实现数据结构化。,3）、,出现很高的数据独立性。,4）、,有统一的数据控制功能。,4、内部体系结构组成：,从DBMS角度看,三级模式：,二级映象：,常用,用户级（外模式）：,概念级（概念模式）：,物理级（内模式）：,模式,子模式,存储模式,（即数据模型）,外模式/模式映象,模式/内模式映象,六、数据的独立性：,逻辑独立性：,物理独立性：,指数据库总体逻辑结构的改变。数据的逻辑结构的改变不影响程序。,指数据的物理结构（存储结构、存储方式等）的改变。数据的物理结构的改变不引起程序的变化。也不影响数据的逻辑结构的变化。,七、数据模型：,1、定义：,指模拟现实世界中的实物及其之间关系的方法。,2、三个要素：,数据结构（静态）、数据操作（动态）、数据约束条件。,3、按不同应用层次分：,物理数据模型（物理模型）：,概念数据模型（概念模型）：,逻辑数据模型（数据模型）：,一种面向客观世界、用户的。,一种面向数据库系统的。,一种面向计算机的物理表示。,E-R模型,4、概念数据模型分为：,E-R模型：,扩充的E-R模型：,面向对象模型：,实体、属性、联系三者抽象概念。（E-R图）,1）、图样：,2）、说明：,A、实体：,客观存在并可以区别的事物。（实体可以是具体的人、事、物，也可以是抽象的概念或联系。）还是若干属性的属性值的集合。,B、属性：,事物的性质的抽象。,C、联系：实体之间的关系。,实体内部各个属性之间的联系。,实体之间的联系,1：1,1：n,n：m,D、域：属性的取值范围。,3）、E-R图（实体-联系图）,矩形表示实体集,椭圆表示属性,菱形表示联系,无向边表示联接,5、逻辑数据模型分为：,层次模型：,网状模型：,关系模型：,有且仅有一个节点无父节点，每个父节点可以有许多个子节点。但每个子节点有且只有一个父节点。,1：1,1：n,允许子节点有多个父节点，也允许一个以上的节点无父节点。,1：n,n：m,二维表,八、关系模型数据库（关系模型）：,1、数据结构：关系模型中数据的逻辑结构是一张二维表。,2、关系：二维表,3、数