计算机二级公共基础

二级公共基础考点总结第一章 数据结构与算法（八大考点）考点一:算法L盲法是指解题方案的准确而完整的描述。它有4个基本特征，分别是可行性、确定性、有穷性和拥有足够的情报。2.算法的复杂度主要包括时间复杂度和空间复杂度算金的时间复杂度是指执行算法所需要的计算所需要的计算工作量（或算法执行过程中所需要的基本运算次数）算法的空间复杂度是指执行这个算法所需要的内存空间.考点二:数据结构的基本概念.数据结构是研究数据元素及其之间的相互关系和数据运算的一门学科.数据结构概念一般包括3个方面的内容:数据之间的逻辑关系（逻辑结构）、数据在计算机中的存储方式（存储结构）以及在这些数据上定义的运算的集合（数据的运算）.数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构；数据的存储结构是指数据的逻辑结构在计

算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。.在链式存储结构中，存储数据结构的存储空间可以是连续的，也可以是不连续的，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。.一般来说，一种数据结构根据需要可以表示成多种存储结构。常用的存储结构有顺序、链接、索引等，而采用不同的存储结构，其数据处理的效率是不同的；一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的。.线性结构是指各数据元素之间的逻辑关系可以用一个线性序列简单地表示出来。否则称之为非线性结构。考点三:线性表及其顺序存储结构1.当线性表采用顺序存储结构实现存储时，其主要特点是数据元素按线性表的逻辑次序，依次存放在一组地址连续的存储单元中。在存储单元中各元素的物理位置和逻辑结构中各结点

间的相邻关系是一致的。考点四:栈和队列栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种〃后进先出〃的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种〃先进先出〃的线性表。栈和队列的共同特点是只允许在端点处插入和删除元素常常一个程序中要用到多个栈，为了不发生上溢错误，就必须给每个栈分配一个足够大的存储空间。但实际中，很难准确地估计,若每个栈都分配过大的存储空间，势必造成系统空间紧张；若让多个栈共用一个足够大的连续存储空间，则可利用栈的动态特性使他们的存储空间互补。所以，由两个栈共享一个存储空间的好处是节省存储空间，降低上溢发生的机率（设有两个串P和q,求q在P中首次出现位置的运算称作模式匹配）（n个顶点的连通图中边的条数至少为n-1）考点五:线性链表1.星表采用的是链式存储结构（链式存储中每个结点由两部分组成:数据域和指针域）,它克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放;它的数据元素的逻辑次序靠结点的指针来指示,不需要移动数据元素。但是链式存储结构也有不足之处:①每个结点中的指针域需额外占用存储空间;②链式存储结构是一种非随机存储结构。用链表表示线性表的突出优点是便于插入和删除操作.考点六:树与二叉树.树是一个或多个结点组成的有限集合，其中一个特定的结点称为根，其余结点分为若干个不相交的集合。每个集合同时又是一棵树。树有且只有1个根结点。.二叉树的遍历是指不重复地访问二叉树中的所有结点二叉树的遍历可以分为三种：前序遍历(DLR)是指先访问根结点，然后遍历左子树，最后遍历右子树.(先根后左再右)中序遍历(LDR)是指先遍历左子树,然后访问根结点，最后遍历右子树.(先左后根再右)后序遍历(LRD)是指先遍历左子树,然后遍历右子树，最后访问根结点.(先左后右再根)如：已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是cedba解题思路：由后序或前序遍历可判断根结点,再由中序遍历可判断左右子树.考点七:查找技术一.顺序查找顺序查找的方法是：用待查关键码值与线性表中各结点的关键码值逐个比较，直到找出相等的关键码值，则查找成功；或者找遍所有结点都不相等，则查找失败。顺序查找的优点：对线性表的结点的逻辑次序无要求（不必按关键码值排序），对线性表的存储结构无要求（顺序存储、链接存储皆可。）二二分法查找二分法查展是一种效率较高的线性表查找方法。要进行二分法查找，则线性表结点必须进按关键码值排好序的，且线性表以顺序方式存储。二分法查找的方法：首先用要查找的关键码值与线性表中间位置结点的关键码值相比较，这个中间结点把线性表分成了两个子表，比较相等则查找完成，不等则根据比较结果确定下一步的查找应在哪一个子表中进行，如此进行下去，直到找到满足条件的结点，或者确定表中没有这样的结点。对于二分法查找的缺点是线性表排序需花费时间，顺序方式存储的插入、删除不便。长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。考点八:排序技术一.交换类排序法交换类排序的基本思想:两两比较待排序记录的关键码，并交换不满足顺序要求的那些偶对,直到全部满足为止.冒泡排序法(或称下沉排序)将待排序的记录顺次两两比较,若为逆序则进行交换.将序列照此方法从头到尾处理一遍称作一趟起泡，一趟起泡的效果是将关键码值最大的记录交换到了最后的位置,即该记录的排序最终位置.若某一趟起泡过程中没有发生任何交换，则排序过程结束.对n个记录的文件进行排序最多需要n-1趟起泡.对n个记录的文件进行冒泡排序，在最坏情况下，需要的比较次数为：N(N-1)/2快速排序法快速排序又称分区交换排序，是对冒泡排序的一种改进.其基本方法是:在待排序序列中任取一个记录,以它为基准用交换的方法将所有的记录分成两部分,关键码值比它小的在一个部分，关键码值比它大的在另一个部分.再分别对两个部分实施上述过程，一直重复到排序完成.在最坏的情况下与起泡排序相当，然而快速排序的平均执行时间为O(nlog2n),显然优于起泡排序和直接插入排序、直接选择排序方法。需要指出的是，快速排序需要O(logzn)的附加存储开销，这是因为快速排序算法的实现过程中需用到大小为O(log2n)的栈空间。快速排序是以一个记录为基准，用交换的方法把文件分成两部分的思想。.插入类排序法插入排序的基本思想是：每步将一个待排序记录按其关键码值的大小插入到前面已排序的文件中的适当位置上,直到全部记录插入完为止。1)简单插入排序它是指将无序序列中的各元素依次插入到已经有序的线性表中。这种排序的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要N(N-l)/2次比较.将已排好序的序列中找插入位置时用顺序法查找，找到插入位置后将该位置原来的记录及其后面所有的记录顺序后移一个位置，空出该位置来插入记录。

2)希尔(Shell)排序法(缩小增量法)希尔排序的基本思想是把记录按下标的一定增量分组，对每组记录使用插入排序，随增量的逐渐减小，所分成的组包含的记录越来越多，到增量的值减小到1时，整个数据合成一组，构成一组有序记录，故其属于插入排序方法。在最坏情况下，希尔排序所需要的比较次数为O(NL5).希尔排序的效率与所选取的增量序列有关..选择类排序法选择排序的基本思想是：每次从待排序的记录中选出关键码值最小(或最大)的记录，顺序放在已排序的记录序列的最后,直到全部排完。1)简单选择排序简单选择排序法在最坏情况下需要比较N(N-l)/2次对文件进行n-1趟扫描，第I趟扫描从剩下的n-i+1个记录中选出关键码值最小的记录，与第I个记录交换。直接选择排序的每一趟扫描找出当前最小关键码，但没有为以后的选择留下任何信息。

堆排序是对直接选择排序的改进，在第一次选择出最小关键码的同时为以后的选择准备了条件。2）堆排序堆排序是完全二叉树结构的一个重要应用。堆排序的基本思想是:对一组待排序的关键码，首先把它们按堆的定义排成一个序列（称为建堆），这就找到了最小的关键码，然后将最小的关键码取出，用剩下的关键码再建堆，便得到次最小的的关键码，如此反复进行，直到将全部关键码排好序为止。堆排序的方法对于规模较小的线性表并不适合,但对于较大规模的线性表来说是很有效的.在最坏怀况下，堆排序需要比较的次数为nlog2n次,堆排序的执行时间为O（nlog2n），且仅需要一个用于交换的附加存储结点。因此堆排序是一种适合于较大文件的排序方法。相关知识点：从平均时间性能而言，快速排序最佳，其所需时间最少，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。当序列中的记录基本有序或元素个数较少时，冒泡排序和简单选择排序为最佳排序方法.所以,在待排序的元素序列基本有序的前提下，效率最高的排序方法是冒泡排序和简单选择排序第二章 程序设计基础（三大考点）考点一:程序设计方法与风格程序的主要风格：“清晰第一，效率第二”要形成良好的程序设计风格，主要应注意下述1II一,要素：.源程序文档化文档是有关计算机程序功能、设计、编制、使用的文字或图形资料。编制一个好的程序首先要确保它的正确性和可靠性还应强调良好的编程风格。在书写时应考虑为程序作注释。.数据说明的方法.语句的结构程序编写要做到清晰第一、效率第二。.输入和输出考点二:结构化程序设计结构化程序设计的原则：概括为：自顶向下、逐步求精、模块化、限制使用GOTO语句。结构化程序的基本结构：顺序结构、选择结构、重复结构（或称为循环结构）严格控制GOTO语句的使用。其意思是指：A.用一个非结构化的程序设计语言去实现一个结构化的构造。B.若不使用GOTO语句会使功能模糊C.在某种可以改造而不是损害程序可读性的情况下。相关知1。程序设计语言是用于书写计算机程序的语言，其基本成分有以下4种，数据成分：用来描述程序中的数据。运算成分：描述程序中所需的运算。控制成分：用来构造程序的逻辑控制结构。传输成分：定义数据传输成分，如输入输出语言。2.当程序之间发生调用关系时，调用命令所在的代码段被称为主程序，被调用的代码段被称为子程序。子程序是对功能的抽象，可分为过程和函数两类，两者的区别是函数是通过函数名来返回值的，而过程只能通过形式参数或对全局变量进行修改以返回值。考点三:面向对象的程序设计一.面向对象的优点：A.与人类习惯的思维方法一致B.稳定性好C.可重用性好（软件重用是指在不同的软件开发过程中重复使用相同或相似软件元素的过程O重用是提高软件生产率的最主要的方法。）D.易于开发大型软件产品E.可维护性好4.面向对象方法的基本概念1）对象面向对象方法学中的对象是由描述该对象属性的数据以及可以对这些数据施加的所有操作封装在一起构成的统一体。面向对象方法基本目的和主要优点:通过重用性提高软件的生产率。对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象O对象是属性和方法的封装体。属性即对象包含的信息，操作描述了对象执行的功能，操作也称为方法或服务。面向对象方法和技术以对象为核心，对象之间通过传递消息互相联系。面向对象方法的基本概念包括：对象、属性、方法、类、继承、多态性没有过程调用。对象有五个基本特点：A.标识惟一性B.分类性C.多态性D.封装性E.模块独立性好2）类和实例将属性、操作相似的对象归为类。类是具有共同属性、共同方法的对象的集合。所以，类是对象的抽象，它 描述了属于该对象类型的所有对象的性质。而一个对象则是其对应类的一个实例。3）消息面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制协助进行，这样的机制称为“消息”。消息是一个实例与另一个实例之间传递的信息，它请求对象进行某一处理或回答某一要求的信息，它统一了数据流和控制流。消息的使用类似于函数调用4）继承继承是使用已有的类定义作为基础建立新类的定义技术。已有的类可当作基类来引用，则新类相应地可当作派生类来引用。一个类直接继承其父类的描述或特性，子类自动地共享基类中定义的数据和方法。继承是指能够直接获得已有的性质和特征，而不必重复定义他们。继承分单继承和多重继承o单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。

在面向对象方法中，类之间共享属性和操作的机制称为继承。继承性是面向对象程序设计语言不同于其他语言的主要标志。5）多态性对象根据所接受的消息而做出的动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。（利用多态性，用户能够发送一般形式的消息，而将所有的实现细节都留给接受消息的对象）多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。是否建立了丰富的类库是衡量一个面向对象程序设计语言成熟与否的一个重要标志。第三章软件工程基础（五大考点）第三章软件工程基础（五大考点）考点一:软件工程基本概念—软件定▽与软件蚌占,计算机软件是计算机朱统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。其中，程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令（语句）序列。数据是使程序能正常操纵信息的数据结构。文档是与程序开发、维护和使用有关的图文资料。计算机软件是指与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。软件的特点：它是一种逻辑实体，没有明显的制作过程，软件在运行、使用期间不存在磨损、老化问题，软件的开发具有依赖性，其复杂性高，成本高，软件开发涉及诸多的社会因素。软件按功能来分为：应用软件、系统软件、支撑软件（或工具软件）。二.软件危机与软件工程.软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。软件危机归结为成本、质量、生产率等问题。软件工程就是试图用工程、科学和数学的原理与方法研制、维护计算机软件的有关技术及管理方法。软件工程包括3个要素，即方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。软件工程过程通常包含4种基本活动：P-软件规格说明。D-软件开发。软件确认A-软件演进.软件生命周期分为软件定义、软件开发及软件运行维护3个阶段。软件定义包括可行性研究与计划制定、需求分析两个阶段；软件开发包括软件设计（概要设计和详细设计）、软件编码和软件测试三大阶段；软件运行维护阶段包括使用、维护、退役。软件维护活动包括以下几类：改正性维护、适应性维护、完善性维护、预防性维护。维护是软件生命周期的最后一个阶段，也是持续时间最长，花费代价最大的一个阶段，软件工程学的一个目的就是提高软件的可维护性，降低维护的代价。只有软件定义有用户的参与。软件产品从考虑其概念开始，到该软件产品不能使用为止的整个时期都属于软件生命周期。一般包括可行性研究与需求分析、设计、实现、测试、交付使用以及维护等活动。三.软件工程的目标和原则1.基于软件工程的目标软件工程的理论和技术性研究的内容主要包括：软件开发技术（软件开发方法学、开发过程、开发工具和软件工程环境，其主体内容是软件开发方法学）,另一个内容是软件工程管理（软件管理学、软件工程经济学、软件心理学等）把用户的要求转变成软件产品的过程称为软件开发过程。1.软件工程的原则：其基本原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。四.软件开发工具与软件开发环境软件开发工具为软件工程学提供了自动的或半自动的软件支撑环境。软件开发工具的发展是从单项工具的开发逐步向集成工具发展的。软件开发环境或称软件工程环境是全面支持软件开发全过程的软件工具集合。计算机辅助软件工程（CASE）是当前软件开发环境中富有特色的研究工作和发展方向。考点二:结构化分析方法一.需求分析与需求分析方法.需求分析阶段工作概括为四个方面：需求获取、需求分析、编写需求规格说明书、需求评审。需求分析是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期待。准确地解决了“软件系统必须做什么”。需求规格说明书是需求分析的最终结果。.常见的需求分析方法有结构化分析方法和面向对象的分析方法两类。其中结构化分析方法又包括面向数据流的结构化分析方法(SA一Structuredanalysis),面向数据结构的Jackson方法(JSD-Jacksonsystemdevelopmentmethod)和面向数据结构的结构化数据系统开发方法(DSSD-Datastructuredsystemdevelopmentmethod)o从需求分析建立的模型的特性来分，需求分析方法又分为静态分析方法和动态分析方法。二.结构化分析方法结构化分析方法是结构化程序设计理论在软件需求分析阶段的运用。.结构化分析方法的实质是着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。.结构化分析的常用工具：1)数据流图(DFD-DataFlowDiagram)数据流图是描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统的功能建模。o 数据流图中的主要图形元素：加工（转换）。输入数据经加工变换产生输出。f 数据流。沿箭头方向传送数据的通道,二般在旁边标注数据流名。= 存储文件（数据源）。表示处理过程中存放各种数据的文件。匚源，潭。表示系统和环境的接口，属系统之外的实体。建立数据流图的步骤：由外向里，自顶向下，逐层分解。2）数据字典（DD-DataDictionary）数据字典是结构化分析方法的核心。数据字典是对所有与系统相关的数据元素的一个有组织的列表，以及精确的，严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。结构化分析方法使用的描述工具数据字典定义了数据流图中的每个图形元素。3）判定树4）判定表（它与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的取值，即完成该加工的一组动作是由于某一组条件取值的组合而引发的，使用判定表描述比较适宜）判定表采用表格表达工具。三.软件需求规格说明书软件需求规格说明书（SRS,SoftwareRequirementSpecification）是需求分析阶段的最后成果，是软件开发中的重要文档之一。内容对软件主要功能、用户界面、运行环境、算法详细过程、软件的性能说明。它有以下几个方面的作用：①便于用户、开发人员进行理解和交流;②反映出用户问题的结构，可以作为软件开发工作的基础和依据；③作为确认测试和验收的依据。考点三:结构化设计方法一.软件设计的基本概念.软件设计的基础软件件设计是确定系统的物理模型。从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。其中，结构设计是定义软件系统各主要部件之间的关系；数据设计是将分析时创建的模型转化为数据结构的定义；接口设计是描述逻辑内部、软件和协作系统之间以及软件与人之间如何通信；过程设计则是把系统结构部件转换成软件的过程性描述。从工程管理角度来看，软件设计分两步完成：概要设计和详细设计。概要设计(又称结构设计)将软件需求转化为软件体系结构、确定系统级接口、全局数据结构或数据库模式;详细设计确立每个模块的实现算法和局部数据结构,用适当方法表示算法和数据结构的细节。软件设计的一般过程是：软件设计是一个迭代的过程；先进行高层次的结构设计；后进行低层次的过程设计；穿插进行数据设计和接口设计。.软件设计的基本原理：抽象模块化

3）信息隐蔽（信息隐蔽指在一个模块化内包含的信息（过程或数据），对于不需要这些信息的其他模块来说是不能访问的。）4）模块独立性（耦合性和内聚性是模块独立性的两个定性标准,耦合和内聚是相互关联的。内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。耦合性是模块间互相连接的紧密程度的度量。）内容耦合（耦合性最强）、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合、非直接耦合（独立性最强）软件设计中，有利于提高模块独立性的一个准则是高内聚低耦合。二.概要设计软件的概要设计又称为总体结构设计，其主要任务是建立软件系统的总体结构。结果得到一个优化的软件结构图。常见的软件结构设计工具是结构图（SC）,也称为程序结构图。经常使用的结构图有四种模块类型：传入模块、传出模块、变换模块和协调模块。

有关术语：深度：表示控制的层数。宽度：整体控制跨度（最大模块数的层）的表示。扇入：调用一个给定模块的模块个数。扇出：一个模块直接调用的其他模块数。原子模块：树中位于叶子结点的模块。面向数据流的设计方法中，典型的数据流类型有两种：变换型和事务型。二详细设计r详质设计阶段的任务是为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节O详细设算阶段的根本目标是确定应该怎样具体的实现所要求的系统，但详细设计阶段的任务还不是具体的编写程序，而是要设计出程序的“蓝图”，以后程序员将根据这个蓝图写出实际的程序代码。因此，详细设计阶段的结果基本上就决定了最终的程序代码的质里,o2.常见的过程设计工具有：A图形工具：程序流程图(PFD),N-S,PAD,HIPOB表格工具：判定表C语言工具：PDL(伪码)1)程序流程图(PFD)：它是一种传统的、应用广泛的软件过程设计表示工具，通常也称为流程框图。程序流程图表达直观、清晰、易于学习掌握，且独立于任何一种程序设计语言。注：一控制流口加工步骤O逻辑条件N-S图：提出了用方框图来代替传统的程序流程图。PAD图：它是问题分析图(ProblemAnalysisDiagram)的英文缩写。它是继程序流程图和方框图之后，提出的又一种主要用于描述软件详细设计的图形表示工具。(树型结构)PAD图的特征：A结构清晰，结构化程度高;B易于阅读C最左端的纵线是程序主干线，对应程序的第一层结构；每增加一层PAD图向右扩展一条纵线，故程序的纵线数等于程序层次数。D程序执行：从PAD图最左主干线上端结点开始，自上而下，自向而右依次执行，程序终止于最左主干线。PDL过程设计语言(PDL)也称为结构化的英语和伪码，它是一种混合语言，采用英语的词汇和结构化程序设计语言的语法，类似编码语言。考点四:软件测试一.软件测试的目的测试的目的是发现软件中的错误。经验表明，程序中存在错误的概率与该程序中已发现的错误数成正比。这一现象说明，为了提高测试效率，测试人员应该集中对付那些错误群集的程序。一个成功的测试是发现了至今尚未发现的

错误的测试.三.软件测试技术从是否需要执行被测软件的角度，可以分为静态测试和动态测试方法。按功能划分为白盒测试和黑盒测试方法。.静态测试与动态测试静态测试不实际运行软件,主要通过人工进行。动态测试是基于计算机的测试，是为了发现错误执行程序的过程.白盒测试与黑盒测试.白盒测试方法也称结构测试或逻辑驱动测试。它是根据软件的内部工作过程，检查内部成分。主要方法有逻辑覆盖（语句覆盖、路径覆盖、判定覆盖、条件覆盖、判断■条件覆盖（查错能力最强））、基本路径测试（最强的覆盖准则）。白盒测试属于动态测试。（白盒测试的基本原则是：保证所测模块中每一独立路径至少执行一次；保证所测模块每一循环都在边界条件和一般条件下个执行一次；验证所有内部结构的数据有效性。“白盒”法是穷举路径测试。）

.黑盒测试方法也称功能测试或数据驱动测试。它是对软件已经实现的功能是否满足需求进行测试和验证。它不考虑程序内部的逻辑结构和内部特性，只依据程序的需求和功能规格说明,检查程序的功能是否符合它的功能说明。主要方法有：等价类划分法、边界值分析法、错误推测法、因果图等，主要用于软件确认测试。白盒法是根据程序的内部逻辑来设计测试用例的。黑盒法是根据程序的功能来设计测试用例的。注：白盒、黑盒法都不可能使测试达到彻底。四.软件测试的实施软件测试过程一般按4个步骤进行，即单元测试、集成测试、验收测试（确认测试）和系统测试1）单元测试单元测试的技术可以采用静态分析和动态测试。对动态测试多采用白盒动态测试为主，辅之以黑盒测试。单元测试的依据是详细设计说明书和源程序。

单元测试的目的是发现各模块内部可能存在的各种错误。2）集成测试（概要设计阶段进行）集成测试是测试和组装软件的过程。集成测试的目的是发现与接口有关的错误。集成测试的依据是概要设计说明书。人们提出了自顶向下和自底向上相结合、从两头向中间副近的混合式组装方法，被形象称之为“三明治”方法。3）确认测试（需求分析阶段进行）确认测试的任务是验证软件的功能和性能及其它特性是否满足了需求规格说明中确定的各种需求，以及软件配置是否完全、正确。确认测试首先运用黑盒方法,对软件进行有效性测试。对软件是否能达到用户所期望的要求的测试称为有效性测试.以需求规格说明文档作为测试基础。以4）系统测试系统测试是在真实的系统工作环境下检验软件是否能与系统正确连接，发现软件与系统需求

不一致的地方。系统测试的目的是尽可能多的发现软件系统中的错误和缺陷。考点五:程序的调试程序调试的任务是诊断和改正程序中的错误。一.程序序调试的基本步骤：1）错误定位2）修改设计和代码，以排除错误3）进行回归测试，防止引进新的错误。二.软件调试方法：调试的关键在于推断程序内部的错误位置及原因。主要的调试方法有强行排错法（设置断点和监视表达式）、回溯法（适合小规模程序）和原因排除法（通过演绎和归纳，以及二分法来实现）。第四章 数据库设计基础（四大考点）考点一:数据库系统的基本概念一.数据、数据库、数据库管理系统•数据数据实际上就是描述事物的符号记录。计算机中的数据一般分为两部分，即临时性数据和持久性数据。数据库系统中处理的就是持久性数据。软件中的数据是有一定结构的，数据有型（类型）和值之分。.数据库数据库（简称DB）是数据的集合，它具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序所共享。数据库存放数据是按数据所提供的数据模式存放的，数据库中的数据具有“集成”、“共享”的特点，即数据库集中了各种应用的数据，进行统一的构造和存储，而使它们可被不同应用程序所使用。.数据库管理系统数据库管理系统（简称DBMS）是数据库的机构，它是一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。数据库管理系统是数据库系统的核心。其主要六个功能有：1）数据模式定义2）数据存取的物理构建3）数据操纵4）数据的完整性、安全性定义与检查5）数据库的并发控制与故障恢复6）数据的服务数据库管理系统一般提供相应的数据语言，它们是：数据定义语言（简称DDL）：该语言负责数据的模式定义与数据的物理存取构建。数据操纵语言（简称DML）：该语言负责数据的操纵，包括查询及增、删、改等操作。数据控制语言（简称DCL）：该语言负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能。上述数据语言按其使用方法具有两种结构形式：交互式命令语言（又称为自含型或自主型语言）2）宿主型语言。.数据库管理员数据库管理员（简称DBA）.其主要工作有：1）数据库设计2）数据库维护3）改善系统性能，提高系统效率..数据库系统数据库系统（简称DBS）.由五个部分构成:1）数据库（数据）2）数据库管理系统（软件）3）数据库管理员（人员） 4）硬件平台（硬件）5）系统平台（软件）6.数据库应用系统（简称DBAS）.数据库系统的发展数据库系统经历了三个阶段:人工管理阶段、文件系统阶段和数据库系统阶段.数据库系统的基本特点数据库系统基本特点有：1）数据的集成性（全局与局部的结构模式构成了数据库系统数据集成性的主要特征）2）数据的高共享性与低冗余性（数据的一致性是指在系统中同一数据的不同出现应保持相同的值）3）数据独立性（数据独立性是数据与程序间的互不依赖性。数据的独立性一般分为物理独立性和逻辑独立性两级。物理独立性是指数据的物理结构的改变，不会影响数据库的逻辑结构。逻辑独立性是指数据库总体逻辑结构的改变，不需要相应修改应用程序。）4）数据统一管理与控制（主要包含三个方面：数据的完整性检查、数据的安全性保护、并发控制）四.数据库系统的内部结构体系数据库系统的内部结构体系:数据库系统在其内部具有三级模式及二级映射，三级模式分别为概念级模式、内部级模式与外部级模式，二级映射则是分别是概念级到内部级的映射以及外部级到概念级的映射。概念模式是数据库系统中全局数据逻辑结构的描述，是全体用户公共数据视图。（可用DBMS中的DDL语言定义o）外部模式，也称子模式或用户模式，它是用户的数据视图，也是用户所见到的数据模式。（用外模式DDL描述。）内部模式，又称物理模式，它给出了数据库物理存储结构与物理存取方法。（用内模式DDL描述。）考点二:数据模型一.数据模型的基本概念数据是现实世界符号的抽象，而数据模型是数据特征的抽象.其描述的内容有三个部分，它们是数据结构、数据操作与数据约束。数据模型按不同的应用层次分成三种类型：1）概念数据模型简称概念模型。（它是一种面向客观世界、面向用户的模型；它与具体的数据库管理系统无关,与具体的计算机平台无关。较为有名的概念模型有E-R模型）以模式（或概念模式）为框架的数据库称为概念数据库。关系数据库的概念模型是关系模式的集合。2）逻辑数据模型又称为数据模型。（它是一种面向数据库系统的模型，常见的有：层次模型、网状模型、关系模型、面向对象模型等）以子模式为框架的数据库称为用户数据库。3）物理数据模型又称为物理模型。（它是一种面向计算机物理表示的模型，此模型给出了数据模型在计算机上物理结构的表示。）以物理模式为框架的数据库称为物理数据库。二.E-R模型广泛使用的概念模型是E-R模型（或实体联系模型），它于1976年由PeterChen首先提出。E-R模型的基本概念1）实体（它是概念世界中的基本单位，它们是客观存在的且又能相互区别的事物。凡是有共性的实体可组成一个集合称为实体集。）2）属性（它是现实世界中事物的特性。一个属性的取值范围称为该属性的值域或值集）3）联系（它是指现实世界中事物间的关联）两个实体集间的联系实际上是实体集间的函数关系，这种函数关系可以有下面几种：一对一的联系（简记为1：1）一对多或多对一联系（简记为1：M或M：1）多对多联系（简记M：N）oE-R模型由上面三个基本概念组成。由实体、联系、属性三者结合起来才能表示现实世界。E-R模型（设计关系模式）是概念设计与逻辑设计起桥梁作用。1）实体集表示法（用矩形表示实体集，在矩形内写上该实体集的名字）2）属性集表示法（用椭圆形表示属性，在椭圆内写上该属性的名称）4）联系表示法（有菱形（内写上联系名）表示联系）.层次模型层次模型是最早发展起来的数据库模型。它的基本结构是树形结构。它们自顶向下、层次分明。但树结构是受到限制的，每棵树有且仅有一个无双亲结点，即根；树中除根外所有结点有且仅有一个双亲。.网状模型它的出现略晚于层次模型。在结构上较层次模型好，不像层次模型那样满足严格的条件。网状模型将通用的网络拓朴结构分成一些基本结构，一般规定根结点与任一叶子结点间的联系均是一对多的联系。.关系模型1）关系的数据结构关系模型采用二维表来表示，简称表。二

维表由表框架及表的元组组成。表框架由N个命名的属性组成，N称为属性元数。每个属性有一个取值范围称为值域。在表框架中按行可以存放数据，每行数据称为元组。一个表框架可以存放M个元组，M称为表的基数。二维表一般满足7个性质：元组个数有限性、元组的唯一性、元组的次序无关性、元组分量的原子性、属性名惟一性、属性的次序无关性、分量值域的同一性。以二维表为基本结构所建立的模型称为关系模型。键具有标识元组、建立元组间联系等重要作用。在二维表中凡能惟一标识元组的最小属性集称为该表的键或码。二维表中可能有若干个键，它们称为该表的候选码或候选键。从二维表的所有候选键中选取一个作为用户使用的键称为主键或主码，一般主键也简称为键或码。表A中的某些属性集是某B的键，则称该属性集为A的外键或外码。表中一定要有键。

空值表示未知的值或不可能出现的值，一般用NULL表示。关系框架称为关系的模式，关系模式支持子模式，关系子模式是关系数据库模式中用户所见到的那部分数据模式描述。它也是二维表结构，关系子模式对应用户数据库称为视图2）关系操纵数据查询、数据删除、数据插入、数据修改。3）关系中的数据约束关系模型允许定义三类数据约束，它们是实体完整性、参照完整性、用户自定义的完整性约束。其中前种由关系数据库系统自动支持。相关知识点：1）数据库管理系统是位于用户与操作系统之间的一层系统管理软件，是一种系统软件，是用户与数据库之间的一个标准接口。其总是基于某种数据模型，可以分为层次模型、网状模型和关系模型。2）在关系模型的数据语言中，一般除了运用常规的集合运算（并、交、差、笛卡尔积等），还定义了一些专门的关系运算,如投影、选择、连接等。前者是将关系（即二维表）看成是元组的集合，这些运算主要是从二维表的行的方向来进行的。后者是从二维表的列的方向来进行运算的。3）关系数据模型诞生之后迅速发展，深受用户喜爱，但关系数据模型也有缺点，其最主要的缺点是由于存取路径对用户透明，查询效率往往不如非关系数据模型，因此为了提高性能，必须对用户的查询请求进行优化。考点三:关系代数一.关系模型的基本运算1）插入设有关系R需插入若干元组，要插入的元组组成关系R，,则插入可用集合并运算表示为:RUR，删除设有关系R需删除一些元组，要删除的元组组成关系R，则删除可用集合差运算表示为:R-R，3）修改设需修改的元组构成关系R，则先做删除得:R-R，设修改后的元组构成关系R”,此时将其插入即得到结果（RR）UR”4）查询投影运算（表示为兀12,・・♦Aim（R））选择运算（表示为。f（R）逻辑条件F是一个逻辑表达式.基本逻辑条件:V、＞、W、2、手复合逻辑条件有：八（并且）、V（或者）、〜（否））c）笛卡尔积运算（对于两个关系R（n元关系P个元组）与S（m元关系q个元组）的合并操作可以用笛卡尔积T表示，记为T=RXS 该关系是一个n+m元系,元组个数是pXq）二.关系代数中的扩充运算：1）交运算（记为：RAS）2）除运算（如果将笛卡尔积看作乘，那么除运算就是它的逆运算。表示为：T+R=S或自然连接可记为：R|X|S通过公共域的相等值进行连接.）考点四:数据库设计与管理一.数据库设计概述数据库设计的基本任务:根据用户对象的信息需求、处理需求和数据库的支持环境（包括硬件、操作系统与DBMS）设计出数据模式。数据库设计中有两种方法，一是面向数据；二是面向过程。面向数据的设计方法已成为主流方流。数据库设计目前一般采用生命周期法,它们是:需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段等。数据库设计中采用前四个阶段，并且重点以数据结构与模型的设计为主线。

二.数据库设计的需求分析需求分析是整个设计活动的基础，也是最困难、最花时间的一步。分析和表达用户的需求，经常采用的方法有结构化分析方法和面向对象的方法。结构化分析（简称SA方法）方法用自顶向下、逐层分解的方法分析系统。用数据流图（简记为DFD）表达了数据和处理过程的关系。数据字典对系统中数据的详尽描述,是各类数据属性的清单。（数据字典是各类数据描述的集合，它通常包括5个部分，即数据项，是数据的最小单位；数据结构；数据流；数据存储；处理过程）三.数据库概念设计数据库概念设计的目的是分析数据间内在的语义关联,在此基础上建立一个数据的抽象模型。数据库概念设计的方法有两种：集中式模式设计法（统一的模式设计方法）和视图集成设计法（一种分散到集中的方法）。视图设计一般有3种设计次序，它们分别是自顶向下、自底向上和由内向外，它们又为视图设计提供了具体的操作方法，设计者可根据实

际情况灵活掌握,可以单独使用也可混合使用O视图集成的常见冲突：命名冲突、概念冲突、域冲突、约束冲突三.数据库的逻辑设计.从E-R图向关系模式转换数据库逻辑设计的主要工作是将E-R图转换成指定RDBMS中的关系模式。首先，从E-R图到关系模式的转换是比较直接的，实体与联系都可以表示成关系，E-R图中属性也可以转换成关系的属性。实体集也可以转换成关系。.逻辑模式规范化及调整、实现.关系视图设计关系视图的作用大致有三点:提供数据逻辑独立性、能适应用户对数据的不同需求、有一定数据保密功能。四.数据库的物理设计数据库物理设计的主要目标是对数据库内部物理结构作调整并选择合理的存取路径，以提高数据库访问速度及有效利用存储空间。留给用户参与物理设计的内容有：索引设计、集簇设计和分区设计。五.数据库管理数据库管理包括六个内容：数据库的建立、数据库的调整、数据库的重组、数据库安全性控制与完整性控制、数据库的故障恢复、数据库监控。数据库恢复是将数据库中的数据从错误状态中恢复到某种逻辑一致的状态。如果数据库中包含成功事务提交的结果，则称数据库处于一致性状态。数据库保护分为：安全性控制、完整性控制、并发性控制、数据的恢复。第一套⑴下面叙述正确的是o（C）A.算法的执行效率与数据的存储结构无关B.算法的空间复杂度是指算法程序中指令（或语句）的条数（指的是算法所占用的空间）C.算法的有穷性是指算法必须能在执行有限个步骤之后终止D.以上三种描述都不对(2)以下数据结构中不属于线性数据结构的是。(C)A.队列B.线性表C.二叉树D.栈(3)在一棵二叉树上第5层的结点数最多是o(B)2n-18163215(4)下面描述中，符合结构化程序设计风格的是o(A)A.使用顺序、选择和重复(循环)三种基本控制结构表示程序的控制逻辑B.模块只有一个入口，可以有多个出口(可以有0个入口)C.注重提高程序的执行效率D.不使用goto语句(只是限制使用)(5)下面概念中，不属于面向对象方法的是 。(D)A.对象B.继承C.类D.过程调用(6)在结构化方法中，用数据流程图(DFD)作为描述工具的软件开发阶段是o(B)A.可行性分析B.需求分析C.详细设计D.程序编码(7)在软件开发中，下面任务不属于设计阶段的是o(D)A.数据结构设计B.给出系统模块结构C.定义模块算法D.定义需求并建立系统模型(8)数据库系统的核心是o(B)A.数据模型B.数据库管理系统C.软件工具D.数据库(9)下列叙述中正确的是o(C)A.数据库是一个独立的系统，不需要操作系统的支持B.数据库设计是指设计数据库管理系统C.数据库技术的根本目标是要解决数据共享的问题D.数据库系统中，数据的物理结构必须与逻辑结构一致(10)下列模式中，能够给出数据库物理存储结构与物理存取方法的是o(A)A.内模式B.外模式C.概念模式D.逻哮式套(1)算法的时间复杂度是指o(C)A.执行算法程序所需要的时间B.算法程序的长度C.算法执行过程中所需要的基本运算次数D.算法程序中的指令条数(2)下列叙述中正确的是o(A)A.线性表是线性结构B.栈与队列是非线性结构C.线性链表是非线性结构D.二叉树是线性结构⑶设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为o(B)349350255351(4)结构化程序设计主要强调的是 。(B)A.程序的规模B.程序的易读性C.程序的执行效率D.程序的可移植性⑸在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是o(D)A.概要设计B.详细设计C.可行性分析D.需求分析(6)数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是。(A)A.控制流B.加工C.数据存储D.源和潭⑺软件需求分析阶段的工作，可以分为四个方面：需求获取、需求分析、编写需求规格说明书以及o(B)A.阶段性报告B.需求评审C.总结D.都不正确(8)下述关于数据库系统的叙述中正确的是o(A)A.数据库系统减少了数据冗余B.数据库系统避免了一切冗余C.数据库系统中数据的一致性是指数据类型的一致D.数据库系统比文件系统能管理更多的数据(9)关系表中的每一横行称为一个 。(A)A.元组B.字段C.属性

D.码(10)数据库设计包括两个方面的设计内容，它们是O(A)A.概念设计和逻辑设计B.模式设计和内模式设计C.内模式设计和物理设计D.结构特性设计和行为和性域计第三套⑴算法而空间复杂度是指。(D)A.度是指。(D)B.算法程序中的指令条数C.算法程序所占的存储空间D.算法执行过程中所需要的存储空间(2)下列关于栈的叙述中正确的是 。(D)A.在栈中只能插入数据B.在栈中只能删除数据C.栈是先进先出的线性表D.栈是后进先出的线性表(3)在深度为5的满二叉树中，叶子结点的个数为o(C)32B.311615(4)对建立良好的程序设计风格，下面描述正确的是O(A)A.程序应简单、清晰、可读性好B.符号名的命名要符合语法C.充分考虑程序的执行效率D.程序的注释可有可无(5)下面对对象概念描述错误的是 。(A)A.任何对象都必须有继承性B.对象是属性和方法的封装体C.对象间的通讯靠消息传递D.操作是对象的动态性属性(6)下面不属于软件工程的3个要素的是o(D)A.工具B.过程C.方法D.环境(7)程序流程图(PFD)中的箭头代表的是o(B)A.数据流B.控制流C.调用关系D.组成关系(8)在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独

立性最高的阶段是 o(A)A.数据库系统B.文件系统C.人工管理D.数据项管理(9)用树形结构来表示实体之间联系的模型称为o(B)A.关系模型B.层次模型C.网状模型D.数据模型(10)关系数据库管理系统能实现的专门关系运算包括 。(B)A.排序、索引、统计B.选择、投影、连接C.关联、更新、排序D.显示、打印、制表第四套⑴算法一般都可以用哪几种控制结构组合而成o(D)制表第四套A.循环、分支、递归B.顺序、循环、嵌套C,循环、递归、选择D.顺序、选择、循环(2)数据的存储结构是指o(B)A.数据所占的存储空间量B.数据的逻辑结构在计算机中的表示C.数据在计算机中的顺序存储方式D.存储在外存中的数据⑶在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送o(D)D.消息A.调用语句B.命令C.口令(4)检查软件产品是否符合需求定义的过程称为O(A)A.确认测试B.集成测试C.验证测试D.验收测试⑸下列工具中属于需求分析常用工具的是o(D)A.PADPFDN-SDFD(6)下面不属于软件设计原则的是 。(C)A.抽象B.模块化C.自底向上D.信息隐蔽(7)索引属于o(B)A.模式B.内模式C.外模式D.概念模式(8)在关系数据库中，用来表示实体之间联系的是o(D)A.树结构B.网结构C.线性表D.二维表(9)将E-R图转换到关系模式时，实体与联系都可以表示成 。(B)A.属性B.关系C.键D.域第五套(1)在下列选项中，哪个不是一个算法一般应该具有的基本特征 。(C)A.确定性B.可行性C.无穷性D.拥有足够的情报(2)希尔排序法属于哪一种类型的排序法o(B)A.交换类排序法B.插入类排序法C.选择类排序法D.建堆排序法(3)下列关于队列的叙述中正确的是 。(C)A.在队列中只能插入数据B.在队列中只能删除数据C.队列是先进先出的线性表D.队列是先进后出的线性表(4)对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为 。(B)A.N+1B.N(N+l)/2N/2(5)信息隐蔽的概念与下述哪一种概念直接相关o(B)A.软件结构定义B.模块独立性C.模块类型划分D.模拟耦合度(6)面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是o(C)A.模拟现实世界中不同事物之间的联系B.强调模拟现实世界中的算法而不强调概念C使用现实世界的概念抽象地思考问题从而自然地解决问题D.鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考(7)在结构化方法中，软件功能分解属于下列软件开发中的阶段是o(C)A.详细设计B.需求分析C总体设计D.编程调试(8)软件调试的目的是o(B)A.发现错误B.改正错误C.改善软件的性能D.挖掘软件的潜能(9)按条件f对关系R进行选择，其关系代数表达式为 。(C)R|X|RR|X|R6f(R)d.nm(10)数据库概念设计的过程中，视图设计一般有三种设计次序，以下各项中不对的是o(D)A.自顶向下B.由底向上C.由内向外D.若雌到局部第K套(1)在计算机中，算法是指o(C)A.查询方法B.加工方法C.解题方案的准确而完整的描述D.排序方法(2)栈和队列的共同点是o(C)A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点(3)已知二叉树后序遍历序列是dabecy中序遍历序列是debac,它的前序遍历序列是o(A)cedbaacbeddecabdeabc(4)在下列几种排序方法中，要求内存量最大的是o(D)A.插入排序B.选择排序C.快速排序D.归并排序(5)在设计程序时，应采纳的原则之一是o(A)A.程序结构应有助于读者理解.不限制goto语句的使用C.减少或取消注解行D.程序越短越好(6)下列不属于软件调试技术的是 。(B)A.强行排错法B.集成测试法C.回溯法D.原因排除法(7)下列叙述中，不属于软件需求规格说明书的作用的是 。(D)A.便于用户、开发人员进行理解和交流B.反映出用户问题的结构，可以作为软件开发工作的基础和依据C.作为确认测试和验收的依据D.便于开发人员进行需求分析(8)在数据流图(DFD)中，带有名字的箭头表示o(C)A.控制程序的执行顺序B.模块之间的调用关系C.数据的流向D.程序的组成成分9)SQL语言又称为o(C)A.结构化定义语B.结构化控制语_C.结构化查询语:D.结构化操纵语言(10)视图设计一般有3种设计次序，下列不属于视图设计的是o(B)A.自顶向下B.由外向内C.由内向外D.基唇迪上

第七套

(1)数据结构中，与所

使用的计算机无关的

是数据的o(C)A.存储结构B.物理结构C.逻辑结构D.物理和存储结构(2)栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是o(D)ABCEDDBCEACDABEDCBEA(3)线性表的顺序存储结构和线性表的链式存储结构分别是 。(B)A.顺序存取的存储结构、顺序存取的存储结构B.随机存取的存储结构、顺序存取的存储结构C.随机存取的存储结构、随机存取的存储结构D.任意存取的存储结构、任意存取的存储结构(4)在单链表中，增加头结点的目的是 。(A)A.方便运算的实现B.使单链表至少有一个结点C.标识表结点中首结点的位置D.说明单链表是线性表的链式存储实现(5)软件设计包括软件的结构、数据接口和过程设计，其中软件的过程设计是指。(B)A.模块间的关系B.系统结构部件转换成软件的过程描述C.软件层次结构D.软件开发过程(6)为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来代替传统的程序流程图，通常也把这种图称为回PAD图N-S图C.结构图D.数据流图(7)数据处理的最小单位是o(C)A.数据B.数据元素C.数据项D.数据结构(8)下列有关数据库的描述，正确的是 。(C)A.数据库是一个DBF文件B.数据库是一个关系C.数据库是一个结构化的数据集合D.数据库是一组文件(9)单个用户使用的数据视图的描述称为 。(A)A.外模式B.概念模式C.内模式D.存储模式(10)需求分析阶段的任务是确定o(D)A.软件开发方法B.软件开发工具C.软件开发费用D.螯膻统功能⑴算法分析的目的是o(D)A.找出数据结构的合理性B.找出算法中输入和输出之间的关系C.分析算法的易懂性和可靠性D.分析算法的效率以求改进n个顶点的强连通图的边数至少有 。(C)n-1n