计算机二级考试公共基础知识冲刺复习笔记.doc

《计算机二级考试公共基础知识冲刺复习笔记.doc》由会员分享，可在线阅读，更多相关《计算机二级考试公共基础知识冲刺复习笔记.doc（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机二级公共基础知识复习笔记全部的基本概念Point1：算法的基本概念1、算法：是指解题方案的准确而完整的描述。(1)算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。程序也可以作为算法的一种描述，但程序通常还要考虑程序运行时的环境限制等。(2)算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。2、算法的基本特征：(1)可行性(2)确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；例在特殊情况时，数学公式是正确的，但计算机就是无法操作。(3)有穷性，算法必须能在有限的时间内做完，即能在执行有限个

2、步骤后终止，包括合理的执行时间的含义。例如1/3的无理数问题。(4)拥有足够的情报。所有的各种可能情况都要考虑到。3、一个算法的优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。(1)算法的时间复杂度是指执行算法所需要的计算工作量，可以执行算法的过程中所需要的基本运算的执行次数来度量。分析算法工作量的方法有：平均性态分析、最坏情况分析。(2)算法的空间复杂度是指执行这个算法所需要的内存空间。主要包括：算法程序所占的空间；输入的初始数据所占的空间；算法执行过程中所需要的额外空间。Point2：软件工程基本概念考点精讲1、计

3、算机软件是包括程序、数据及相关文档的完整集合。是计算机系统中与硬件相互依存的部分。软件按功能分为应用软件、系统软件、支撑软件（或工具软件）。2、软件工程源自于软件危机。(1)软件危机主要表现在成本、质量、生产率等问题。(2)软件工程的主要思想是强调在软件开发过程中需要应用工程化原则，软件工程学的主要研究对象包括软件开发与维护的技术、方法、工具和管理等方面。(3)软件工程包括三个要素，即方法、工具和过程。3、通常把软件产品从提出、实现、使用、维护到停止使用(退役)的过程称为软件生命周期。(1)可以将软件生命周期分为软件定义、软件开发及软件运行维护三个阶段。(2)软件生命周期的主要活动阶段是：可行

4、性研究与计划制定；需求分析；软件设计；软件实现；软件测试；运行和维护。Point3：数据库的基本概念考点精讲1、数据库的基本概念(1)数据：实际上就是描述事物的符号记录。数据的特点：有一定的结构，有型与值之分，如整型、实型、字符型等。而数据的值给出了符合给定型的值，如整型值15。(2)数据库(DataBase，简称为DB)：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。数据库存放数据是按数据所提供的数据模式存放的，具有集成与共享的特点。数据库技术的根本目标是要解决数据的共享问题。2、数据库系统(DataBaseSystem，简称为DBS

5、)由数据库(数据)、数据库管理系统(软件)、数据库管理员(人员)、硬件平台(硬件)、软件平台(软件)五个部分构成。(1)数据库管理系统提供以下的数据语言：数据定义语言（DDL）：负责数据的模式定义与数据的物理存取构建；数据操纵语言：负责数据的操纵，如查询与增加、删除、修改等；数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。(2)数据库系统的特点：数据的集成性；数据高共享性与低冗余性；数据独立性：数据独立性是数据与程序之间互不依赖，也就是数据的逻辑结构、存储结构与存取方式的改变不会影响应用程序。3、据库管理系统(DataBaseManagementSystem，简称为D

6、BMS)是系统软件，负责对数据库的数据组织、数据操纵、数据维护、控制及保护和数据服务等。数据库管理系统是数据库系统的核心。4、数据管理经历了人工管理、文件系统、数据库系统三个阶段。文件系统阶段的特点是数据满足一个特定格式而存储，不同程序中使用的数据仍会出现重复存储，也会导致数据冗余。数据库技术的主要目的是有效地管理和存取大量的数据资源，数据库系统阶段的数据独立性最高。5、数据独立性包括物理独立性和逻辑独立性。-11-(1)物理独立性：数据的物理结构(如存储设备更换、物理存储方式)的改变，不影响数据库的逻辑结构，也不引起应用程序的变化。(2)逻辑独立性：数据库整体逻辑结构(如修改数据、增加新数据

7、类型、改变数据间联系等)改变，不需要修改应用程序。6、数据库系统在其内部具有三级模式：概念模式、内部模式与外部模式。(1)概念模式：它是数据库系统中全局数据逻辑结构的描述，是全体用户（应用）的公共数据视图。概念模式主要描述数据的概念记录类型以及它们之间的关系，它还包括一些数据间的语义约束，对它的描述可用DBMS中的DDL语言定义。(2)内部模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法，如数据存储的文件结构、索引、集簇及hash等存取方式与存取路径，内模式的物理特性主要体现在操作系统及文件级上，它还未深入到设备级(如磁盘及磁盘操作)上。DBMS一般提供相关的内模式描述语言(内模式

8、DDL)。(3)外部模式：也称子模式或用户模式，它是用户的数据视图，也就是用户所见到的数据模式，它由概念模式推导而出。在一般的DBMS中都提供相关的外模式描述语言(外模式DDL)。7、数据库系统的两级映射：概念模式到内部模式的映射，外部模式到概念模式的映射。(1)数据的物理独立性：当数据库的存储结构发生变化时，通过修改“概念模式到内部模式的映射”，使得数据库的概念模式不变，其外模式不变，应用程序不用修改，保证了数据的物理独立性。(2)数据的逻辑独立性：当概念模式发生变化时，通过修改“外部模式到概念模式的映射”，使得用户所用的外模式不变，从而应用程序也不用修改，保证了数据的逻辑独立性。Point

9、4：程序设计方法与风格考点精讲1、养成良好的程序设计的设计风格，主要应考虑下述因素：(1)源程序文档化：符号名的命名有一定含义，便于理解；正确的注释帮助读者理解程序；程序层次清晰。-16-(2)数据说明的方法：数据说明的次序规范化；说明语句中变量安排有序化；使月注释来说明复杂数据结构。(3)语句的结构：程序应该简单易懂，语句构造应该简单直接。(4)输入和输出。2、注释分序言性注释和功能性注释，语句结构清晰第一、效率第二。Point5：结构化程序设计考点精讲1、结构化程序设计的主要目的是使程序结构良好、易读、易理解、易维护。它的原则主要包括：自顶向下；逐步求精；模块化；限制使用goto语句。2、

10、结构化程序设计方法可用三种基本结构实现：顺序结构；选择结构；重复结构。3、在结构化程序设计的具体实施中，要注意把握如下要素：(1)使用程序设计语言中的顺序结构、选择结构、循环结构等控制结构来表示程序的控制逻辑。(2)选用的控制结构只准许有一个入口和一个出口。(3)程序语句组成容易识别的程序块，每块只有一个入口和一个出口。(4)复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现。(5)语言中所没有的控制结构，应该采用前后一致的方法来模拟。(6)严格控制goto语句的使用。Point6：面向对象的程序设计方法考点精讲1、对象(object)：对象用来表示客观世界中的任何实体。面向对象的程序设计方法

11、中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。2、类(class)和实例(instance)：将属性、操作相似的对象归为类，类是具有共同属性、共同方法的对象的集合；一个具体对象称为类的实例。3、消息(message)：面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制协助进行，这个机制称为消息。消息是一个实例与另一个实例之间传递的信息，是请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。4、继承(inheritance)：继承是面向对象方法的一个主要特征。继承

12、是使用已有的类作为基础（直接获得已有的性质和特征）建立新类的定义技术。已有的类可以当做基类引用，则新类可当做派生类引用。5、多态性(polymorphism)：对象根据所接受的消息而作出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。Point7：基本排序与查找的算法考点精讲1、查找(1)顺序查找是一种最基本和最简单的查找方法。它的思路是，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。对于长度为n的有序线性表，在最坏情况下，顺序查找需要比较n次。(2)对于大的线性表来说，顺

13、序查找的效率是很低的。虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找：无序的线性表；即使是有序的线性表，如果采用链式存储结构，也只能顺序查找。-21-(3)二分查找是针对有序表进行查找的简单、有效而又较常用的方法。其基本思想是：首先选择有序表中间位置的记录，将其关键字与给定关键字k进行比较，若相等，则查找成功；否则，若k值比该关键字值大，则要找的元素一定在表的后半部分(或称右子表)，则继续对右子表进行二分查找；若k值比该关键字值小，则要找的元素一定在表的前半部分(左子表)，同样应继续对左子表进行二分查找。每进行一次比较，要么找到要查找的元素，要么将查找的范围缩小一半。如此递推，直

14、到查找成功或把要查找的范围缩小为空(查找失败)。(4)显然，仅当有序线性表为顺序存储时才能用二分查找，并且，二分查找的效率要比顺序查找高得多。可以证明，对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。2、排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。常用的排序方法(1)交换类排序法：冒泡排序法，需要比较的次数为n(n-1)/2；快速排序法，最坏情况需要比较的次数为n(n-1)/2。(2)插入类排序法：简单插入排序法，最坏情况需要n(n-1)/2次比较；希尔排序法，最坏情况需要O(n1.5)次比较。(3)选择类排序法：简单选择排序海最坏

15、情况需要n(n-1)/2次比较；堆排序法，最坏情况需要O(nlog2n)次比较。软件工程与数据库设计Point1：数据模型考点精讲1、数据模型的概念：是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表与操作提供一个抽象的框架。描述了数据结构、数据操作及数据约束。2、数据模型分为三种：(1)概念数据模型：简称概念模型，是对客观世界复杂事物的结构描述及它们之间的内在联系的刻画。主要有：E-R模型、扩充的E-R模型、面向对象模型及谓词模型等。(2)逻辑数据模型：又称物理模型，是一种面向数据库系统的模型，该模型着重于在数据库系统一级的实现。主要有：层次模型、网

16、状模型、关系模型、面向对象模型等。(3)物理数据模型：又称物理模型，它是一种面向计算机物理表示的模型，此模型给出-25-了数据模型在计算机上物理结构的表示。3、E-R模型(1)E-R模型的基本概念实体：现实世界中的事物；属性：事物的特性；联系：现实世界中事物间的关系。(2)实体集的关系有一对一（一个学校和一个校长）、一对多（学生和宿舍）、多对多（老师与学生）的联系。两个实体集间联系可分为：一对一联系(onetoonerelationship)简记为1:1。一对多联系(onetomanyrelationship)简记为1:m或m:1。多对多联系(monytomanyrelationship)简记

17、为m:n。(3)E-R模型三个基本概念之间的联接关系：实体是概念世界中的基本单位，属性有属性域，每个实体可取属性域内的值。一个实体的所有属性值叫元组。(4)E-R模型的图示法：实体集表示法：在矩形内写上实体集的名字；属性表示法：在椭圆形内写上属性的名称；联系表示法：用菱形内写上联系的名称；实体集与属性的联接关系：用无向线段来表示；实体集与联系间的联接关系；E-R模型由实体、属性、联系这三个基本概念细成。只有实体、联系、属性三者结合起来才能表示一个现实世界。4、关系模型(1)在关系模型中，把数据看成一个二维表，每一个二维表称为一个关系。表中的每一列称为一个属性，相当于记录中的一个数据项，对属性的

18、命名称为属性名，表中的一行称为一个元组，相当于记录值。(2)在二维表中凡能唯一标识元组的最小属性称为键或码。从所有侯选健中选取一个作为用户使用的键称主键。表A中的某属性是某表B的键，则称该属性集为A的外键或外码。(3)关系中的数据约束：实体完整性约束：约束关系的主键中属性值不能为空值；参照完全性约束：是关系之间的基本约束；用户定义的完整性约束：它反映了具体应用中数据的语义要求。(4)关系模型的数据操作即是建立在关系上的数据操作，一般有查询、增加、删除和修改四种操作。Point2：软件定义阶段考点精讲1、软件定义阶段：包括制定计划与需求分析。可行性研究与计划制定：确定总目标，可行性研究，探讨解决

19、方案，制定开发计划。2、需求分析：对待开发软件提出的需求进行分析并给出详细的定义。主要工作是编写软件需求规格说明书及用户手册。(1)需求分析的任务是导出目标系统的逻辑模型，解决“做什么”的问题。(2)需求分析一般分成4个阶段：需求获取，需求分析，编写需求规格说明书，需求评审。(3)软件需求规格说明书（SRS），是需求分析阶段的最后成果，是软件开发中的重要文档之一。该说明把在软件计划中确定的软件范围加以展开，制定出完整的信息描述，详细的功能说明，恰当的检验标准以及其他与要求有关的数据。其特点有：正确性；无岐义性；完整性；可验证性；一致性；可理解性；可追踪性。(4)需求分析的方法：结构化分析方法：

20、包括面向数据流的结构化分析方法（SA），面向数据结构的Jackson方法（JSD）和面向数据结构的结构化数据系统开发方法（DSSD）。面向对象的分析的方法（OOA）。从需求分析建立的模型的特性来分：静态分析和动态分析。3、结构化方法的核心和基础是结构化程序设计理论。结构化分析方法的实质：面向数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。数据字典是结构化分析的核心。(1)结构化分析的常用工具有：数据流图；数据字典；判定树；判定表。(2)数据流图（DFD）：描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统功能建模。建立数据

21、流图的步骤：由外向里，自顶向下，逐层分解，完善求精。数据流图的主要图形元素：椭圆：代表加工（转换）。输入数据经加工变换产生输出。箭头：代表数据流。沿箭头方向传送数据的通道，一般在旁边标注数据流名。双横线：代表存储文件（数据）。表示处理过程中存入各种数据的文件。矩形：代表源，潭。表示系统和环境的接口，属系统之外的实体。(3)数据字典：是结构化分析的核心。是对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。概括地说，数据字典是对DFD中出现的被命名的图形元素的确切解释。(4)判定树：是从问题定义的文字描述中

22、分清哪些是判定的条件，哪些是判定的结论，根据描述材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们-31-构造判定树。(5)判定表：与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的取值，即完成该加工的一组动作是由于某一组条件取值的组合而引发的，使用判定表描述比较适宜。Point3：关系代数考点精讲1、关系模型的基本运算：并、差、交、广义笛卡尔积、投影、选择、连接、除。关系是有序组的集合，可将关系操作看成是集合的运算。2、并、差、交(1)并运算。RS。(2)差运算。R-S。(3)交运算。交运算是将两个关系中共有元组表示为RS。3、广义笛卡尔积、除(1)广义笛卡尔积。笛卡

23、儿积运算：两个关系的合并操作可用笛卡儿积表示。设有n元关系R及m元关系R，它们分别有p，q个元组，则R与S的笛卡儿积为RS，该关系是一个n+m元关系，元组个数是pq。(2)除运算。将一个关系中元组去除另一个关系中元组，表示为：R/S。4、投影运算：投影运算是一个一元运算，一个关系通过投影运算后仍为一个关系R。R是这样一个关系，它是R中投影运算所指出的那些域的列所组成的关系。5、选择运算：选择运算是一个一元运算，关系R通过选择运算后仍为一个关系。这个关系是由R中那些满足逻辑条件的元组所组成。6、连接运算：Point4：软件设计阶段考点精讲1、软件设计是软件工程的重要阶段，是一个把软件需求持换为软

24、件表示的过程。软件设计的基本目标是用比较抽象慨括的方式确定目标系统如何完成预定的任务，即软件设计是确定系统的物理模型。(1)需求分析主要解决“做什么”问题，软件设计解决“怎么做”的问题。从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。结构设计：定义软件系统各主要部件之间的关系。数据设计：将分析时创建的模型转化为数据结构的定义。接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。过程设计：把系统结构部件转换成软件的过程描述。(2)从工程管理角度来看，软件设计包括：概要设计和详细设计。2、软件设计中应该遵循的基本原理和与软件设计有关的概念(1)抽象：就是把事

25、物本质的共同特征提取出来而不考虑其他细节。(2)模块化：是指把一个待开发的软件分解成若干小的简单的部分。但划分模块不是越多越好。(3)信息隐蔽：是指在一个模块中包含的信息，对于不需求这些信息的其他模块来说是不能访问的。(4)模块独立性：每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。这是评价设计好坏的重要度量标准。3、衡量软件模块独立性使用耦合性和内聚性两个定性的度量标准：(1)内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。内聚是从功能角度来度量模块内的联系。(2)耦合性：耦合性是模块间互相连接的紧密程度的度量。耦合性的强弱取决于各个模块之间接口的复杂度、调

26、用方式以及哪些信息通过接口。在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚、低耦合。4、软件概要设计(1)概要设计的基本任务是：设计软件系统结构；数据结构及数据库设计；编写概要设-37-计文档；概要设计文档评审。(2)结构图（SC），是概要设计阶段的工具。其图形元素为：矩形表示一般模块。箭头表示模块间的调用关系。在结构图中还可以用带注释的箭头表示模块调用过程中来回传递的信息。用带实心圆的箭头表示传递的是控制信息。空心圆箭心表示传递的是数据。结构图的基本形式：基本形式、顺序形式、重复形式、选择形式。结构图有四种模块类型：传入模块、传出模块、变换模块和协调模块。结构图的形态特征：包

27、括深度、宽度、扇出、扇入。深度：表示控制的层数宽度：表示整体控制跨度扇入：调用一个给定模块的模块个数。扇出：一个模块直接调用的其他模块数。(3)面向数据流的设计方法：典型的数据流类型有两种：变换型和事务型。变换型系统结构图由输入、中心变换、输出三部分组成。事务型数据流的特点是：接受一项事务，根据事务处理的特点和性质，选择分派一个适当的处理单元，然后给出结果。5、软件详细设计(1)是为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。(2)常见的过程设计工具有：图形工具：程序流程图（PDF），N-S，PAD（问题分析图），HIPO表格工具：判定表语

28、言工具：PDL（伪码）Point5：数据库设计与管理考点精讲1、数据库设计是数据应用的核心。数据库设计的两种方法：(1)面向数据：以信息需求为主，兼顾处理需求；(2)面向过程：以处理需求为主，兼顾信息需求。2、数据库的生命周期：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段。3、数据库设计包括：需求分析、概念设计、逻辑设计、物理设计。(1)需求分析：常用结构分析方法和面向对象的方法。结构化分析（简称SA）方法用自顶向下、逐层分解的方式分析系统。用数据流图表达数据和处理过程的关系。对数据库设计来讲，数据字典是进行详细的数据收集和数据分析所获得

29、的主要结果。数据字典是各类数据描述的集合，包括5个部分：数据项、数据结构、数据流（可以是数据项，也可以是数据结构）、数据存储、处理过程。(2)数据库概念设计的目的是分析数据间内在语义关联，并建立数据的抽象模型。设计的方法有两种：集中式模式设计法（适用于小型或并不复杂的单位或部门）；视图集成设计法。常见的方法有：E-R模型与视图集成。视图设计一般有三种设计次序：自顶向下、由底向上、由内向外。视图集成的实质是将所有的局部视图统一与合并成一个完整的数据模式，常见的几种局部设计的冲突：命名冲突、概念冲突、域冲突、约束冲突。(3)数据库的逻辑设计主要工作是将E-R图转换成RDBMS中的关系模式。逻辑设计

30、的另一个重要内容是关系视图的设计，又称为外模式设计。关系视图设计：关系视图的设计又称外模式设计。关系视图的主要作用：提供数据逻辑独立性：使应用程序不爱逻辑模式变化的影响。能适应用户对数据的不同需求；有一定数据保密功能。(4)数据库的物理设计主要目标是对数据内部物理结构做调整并选择合理的存取路径，以提高数据库访问速度有效利用存储空间。一般RDBMS中留给用户参与物理设计的内容大致有索引设计、集成簇设计和分区设计。4、数据库管理的内容：(1)数据库的建立；(2)数据库的调整；(3)数据库的重组；(4)数据库安全性与完整性控制；(5)数据库的故障恢复；(6)数据库监控。Point6：软件测试考点精讲

31、1、软件测试定义：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别。2、软件测试的目的：软件测试是为了发现错误而执行程序的过程。3、软件测试的准则：所有测试都应追溯到需求；严格执行测试计划，排除测试的随意性；充分注意测试中的群集现象；程序员应避免检查自己的程序；穷举测试不可能。4、软件测试的方法和技术分类：从是否需要执行被测试软件的角度，分为静态测试和动态测试方法；按照功能划分，分为白盒测试和黑盒测试方法。5、静态测试包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行；动态测试是基本计算机的测试，主要包

32、括白盒测试方法和黑盒测试方法。6、白盒测试：在程序内部进行，主要用于完成软件内部操作的验证。主要方法有逻辑覆盖、基本路径测试。黑盒测试：主要诊断功能不对或遗漏、界面错误、数据结构或外部数据率访问错误、性能错误、初始化和终止条件错，用于软件确认。主要方法有等价类划分法、边界值分析法、错误推测法、因果图等。7、软件测试过程一般按四个步骤进行：单元测试、集成测试、验收测试(确认测试)和系统测试。(1)单元测试：是对软件设计的最小单位（模块）进行正确性检验的测试，目的是发现各模块内部可能存在的各种错误。依据是详细设计说明书和源程序。采用的技术有表静态分析和动态测试。对动态测试以白盒测试为主，辅助以黑盒

33、测试。-46-单元测试的内容包括：模块接口测试，局部数据结构测试，重要的执行路径的检查，出错处理测试，影响以上各点及其相关点的边界条件测试。单元测试需要辅助模块：驱动模块和桩模块。驱动模块相当于被测试模块的主程序，桩模块是主程序调用的其他模块。(2)集成测试：是把模块在按照设计要求组装起来的同时进行测试，主要目的是发现与接口有关的错误，依据是概要设计说明书。集成测试所涉及的内容包括：软件单元的接口测试，全局数据结构测试，边界条件和非法输入的测试。集成测试将模块组装成程序通常采用：非增量方式和增量方式组装。增量方式包括自顶向下，自底向上，自顶向下和自向上相结合。(3)确认测试的任务是验证软件的功

34、能和性能及其他特性是否满足了需求规格说明中确定的各种需求，主要依据的是软件需求规格说明书。确认测试主要运用黑盒测试法。(4)系统测试的目的是在真实的系统工作环境下检验软件是否能与系统正确连接，发现软件与系统需求不一致的地方。系统测试的具体实施一般包括：功能测试，性能测试，操作测试，配置测试，外部接口测试，安全测试等。Point7：程序的调试考点精讲1、程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。2、程序调试的基本步骤：(1)错误定位；(2)修改设计和代码，以排除错误；(3)进行回归测试，防止引进新的错误。3、程序调试可分为静态调试和动态调试。静态调试主要是指通过人的思维来分析源

35、程序代码和排错，是主要的调试手段，而动态调试是辅助静态调试。主要调试方法有：(1)强行排错法；(2)回溯法；(3)原因排除法。数据结构：栈、队列、二叉树等Point1：数据结构的定义考点精讲1、数据结构：是指相互有关联的数据元素的集合。(1)数据结构研究以下三个方面的问题：数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；对各种数据结构进行的运算。研究以上问题的主要目的是为了提高数据处理的效率（一是提高数据处理的速度，二是节省数据处理过程所占的空间。）(2)数据的逻辑结构反映数据元素之间的逻辑关系，即前、后件关系，

36、分为线性结构（线性表、栈和队列）和非线性结构（树和图）。包含：表示数据元素的信息；表示各数据元素之间的前后件关系。(3)数据的存储结构，是指数据逻辑结构在计算机存储空间中的存放形式，也称数据的物理结构。一般来说，一种数据逻辑结构根据需要可以表示成多种存储结构，常用的数据的存储结构有顺序、链接、索引等。2、数据的逻辑结构与数据的存储结构不一定相同。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。常见的存储结构有顺序、链接、索引等。采用不同的存储结构，数据处理的效率是不相同的。Point2：线性表、线性链表和循环链表考点精讲1、如果在一个数据结构中一个数据元素都没有，则称为空的数据结构

37、。根据数据结构中各数据元素之间的前后件关系的复杂程度，分为线性结构与非线性结构。2、如果一个非空的数据结构满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。线性表是一个典型的线性结构。常见的有：线性表，栈，队列，循环队列和线性链表等。3、不满足线性结构条件的数据结构，就是非线性结构。常见的有：数组、广义表、树、二叉树和图都是非线性结构。4、在计算机内，线性表的存储结构有两种：顺序存储（称为线性表）和链式存储（线性链表）。线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构。Point3：栈、队列和循环队列考点精讲1、栈（Stack

38、）又称堆栈。(1)栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。人们把此端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。(2)由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以又把栈称为后进先出表（LastInFirstOut，简称LIFO）；先进栈的元素必定后出栈，所以又把栈称为先进后出表（FirstInLastOut，简称FILO）。2、队列（Qu

39、eue）简称队。(1)队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入操作，而在表的另一端进行删除操作。我们把允许插入的一端称作队尾（rear），允许删除的一端称作队首（front）。(2)向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除队首元素称为离队或出队，该元素离队后，其后继元素就成为新的队首元素。(3)由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进队的次序离队，所以又把队列称为先进先出表（FirstInFirstOut，简称FIFO）。3、循环队列。就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供

40、队列循环使用，其实质还是顺序存储结构。Point4：线性链表、双向链表与循环链表考点精讲1、数据结构中，每个数据存储在一个存储单元中，这个存储单元称为结点。在链式存储方式中，要求每个结点由两部分组成：部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。2、线性链表：线性表的链式存储结构，称为线性链表。(1)对于大的线性表，特别是元素变化频繁的线性表不宜采用顺序存储结构，而要用链式存储结构。(2)数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。(3)结点由两部分组成：(1)用于存储数据元素

41、值，称为数据域；(2)用于存放指针，称为指针域，用于指向前一个或后一个结点。(4)在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。(5)链式存储方式既可用于表示线性结构，也可用于表示非线性结构。(6)线性链表，HEAD称为头指针，HEAD=NULL(或0)称为空表。线性链表的基本运算：查找、插入、删除。3、双向链表：两指针：左指针(Llink)指向前件结点，右指针(Rlink)指向后件结点。4、循环链表的两个特点：-60-(1)增加了一个表头结点。(2)最后一个结点的指针域不是空，而是指向表

42、头结点。Point5：二叉树考点精讲1、树树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。2、二叉树：度为2的树就是二叉树。(1)二叉树的特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。3、二叉树的性质(1)在二叉树中，第i层的结点总数不超过2i-1(i1)。(

43、2)深度为h的二叉树总计最多有2h-1个结点(h1)，最少有h个结点。(3)对于任意一棵二叉树，如果其叶子结点数为N0，而度数为2的结点总数为N2，则N0=N2+1，即叶子数总比度为2的节点数多1。(4)具有n个结点的完全二叉树的深度为int(log2n)+1。(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若k为结点编号，则如果k1，则其父结点的编号为k/2；如果2xkN，则无左孩子;如果2xk+1N，则无右孩子。3、完全二叉树和满二叉树(1)完全二叉树：只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；(2)满二叉树：除了叶

44、子结点外每一个结点都有左右子女且叶子结点都处在最低层的二叉树。4、遍历是对树的一种最基本的运算。所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。设L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍历有三种情况：DLR(称为先根次序遍历，简称前序遍历)，LDR(称为中根次序遍历，简称中序遍历)，LRD(称为后根次序遍历，简称后序遍历)。(1)前序遍历：访问根；按先序遍历左子树；按先序遍历右子树。(2)中序遍历：按中序遍历左予树；访问根；按中序遍历右子树。(3)后序遍历：按后序遍历左予树；按后序遍历右子树；访问根。