国家计算机二级公共基础常考内容.doc

第一章 数据结构与算法1、 算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。2、 算法的复杂度：时间复杂度和空间复杂度。3、 数据结构：线性结构和非线性结构。4、 常见的线性结构：线性表、栈、队列和线性链表等；非线性结构：树、二叉树和图等。5、栈的概念：栈是限定一端进行插入与删除运算的线性表。“先进后出”原则。具有记忆作用。队列是指允许在一端进行插入、而在另一端进行删除的线性表。它又称为先进先出或后进后出的线性表，体现了先来先服务的原则。5、 栈的运算有：入栈、退栈与读栈顶元素。6、 线性链表的存储结构主要分为顺序存储结构和链式存储结构。7、 度的概念：在树的结构中，一个结点所拥有的后件的个数。所有结点中最大的度称为的度。叶子结点的度为0。8、 用树形结构来表示实体之间联系的模型称为 层次模型9、 二叉树的基本性质二叉树具有以下几个性质：性质1：在二叉树的第k层上，最多有 个结点；性质2：深度为m的二叉树最多有 个结点；性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。性质4：具有n个结点的二叉树，其深度至少为log2n+1，其中log2n表示取log2n的整数部分。10、 二叉树遍历：后序遍历的顺序是“左子树右子树根结点”；中序遍历顺序是“左子树根结点右子树”；前序遍历顺序是“根结点左子树右子树”。11、 各种排序法比较类别排序方法最坏情况下的比较次数交换类冒泡排序n(n-1)/2快速排序n(n-1)/2插入类简单插入排序n(n-1)/2希尔排序O(n1.5)选择类简单选择排序n(n-1)/2堆排序O(nlog2n)第二章 程序设计基础1、结构化程序设计方法的主要原则为：自顶向下、逐步求精、模块化和限制使用goto语句。2、模块设计要求高内聚、低耦合。3、（1）面向对象方法是一种运用对象、类、封装、继承、多态和消息等概念来构造、测试、重构软件的方法。对象是属性和方法的封装体。 （2）类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。 （3） 消息是一个实例与另一个实例之间传递的信息。在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送消息。4、结构化程序的基本结构：顺序结构、选择结构和重复结构。第三章 软件工程基础1、软件的相关概念计算机软件是包括程序、数据及相关文档的完整集合。2、软件生命周期 软件生命周期的主要活动阶段为： （1）可行性研究和计划制定。确定待开发软件系统的开发目标和总的要求，给出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成开发任务的实施计划。 （2）需求分析。对待开发软件提出的需求进行分析并给出详细定义，即准确地确定软件系统的功能。编写软件规格说明书及初步的用户手册，提交评审。 （3）软件设计。系统设计人员和程序设计人员应该在反复理解软件需求的基础上，给出软件的结构、模块的划分、功能的分配以及处理流程。 （4）软件实现。把软件设计转换成计算机可以接受的程序代码。即完成源程序的编码，编写用户手册、操作手册等面向用户的文档，编写单元测试计划。 （5）软件测试。在设计测试用例的基础上，检验软件的各个组成部分。编写测试分析报告。 （6）运行和维护。将已交付的软件投入运行，并在运行使用中不断地维护，根据新提出的需求进行必要而且可能的扩充和删改3、软件工程包括3要素;方法、工具和过程。4、软件的调试方法主要有：强行排错法、_回溯法和原因排除法。5、软件开发阶段包括需求分析、总体设计、详细设计、编码和测试五个阶段。其中需求分析阶段常用的工具是数据流图和数据字典。6、在软件设计过程中，必须遵循软件工程的基本原则：这些原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可靠性。7、软件维护活动包括以下几类：改正性维护、适应性维护、完善性维护和预防性维护。8、软件需求规格说明书（SRS，Software Requirement Specification）是需求分析阶段的最是软件开发中的重要文档之一。它有以下几个方面的作用： 便于用户、开发人员进行理解和交流； 反映出用户问题的结构，可以作为软件开发工作的基础和依据； 作为确认测试和验收的依据。9、与结构化需求分析方法相对应的是结构化设计方法。10、从工程管理角度来看，软件设计分两步完成：概要设计和详细设计。（1）概要设计将软件需求转化为软件体系结构、确定系统级接口、全局数据结构或数据库模式；（2）详细设计确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。11、详细设计*：详细设计的任务是确定实现算法和局部数据结构，不同于编码或编程。详细过程设计的常用工具有：（1）图形工具：程序流程图，N-S，PAD，HIPO。（2）表格工具：判定表。（3）语言工具：PDL（伪码）程序流程图中主要元素：1）方框：表示一个处理步骤2）菱形框：表示一个逻辑条件3）箭头：表示控制流向12、概要设计常用的软件结构设计工具是结构图，也称程序结构图。程序结构图的基本图符：模块用一个矩形表示，箭头表示模块间的调用关系。在结构图中还可以用带注释的箭头表示模块调用过程中来回传递的信息。还可用带实心圆的箭头表示传递的是控制信息，空心圆箭心表示传递的是数据 13、软件测试*：软件测试的目的：尽可能地多发现程序中的错误，不能也不可能证明程序没有错误。软件测试方法：静态测试和动态测试。动态测试：主要包括白盒测试方法和黑盒测试方法。&白盒测试白盒测试的基本原则：保证所测模块中每一独立路径至少执行一次；保证所测模块所有判断的每一分支至少执行一次；保证所测模块每一循环都在边界条件和一般条件下至少各执行一次；验证所有内部数据结构的有效性。语句覆盖：选择足够的测试用例，使得程序中每一个语句至少都能被执行一次。路径覆盖：执行足够的测试用例，使程序中所有的可能的路径都至少经历一次。判定覆盖：使设计的测试用例保证程序中每个判断的每个取值分支（T或F）至少经历一次。条件覆盖：设计的测试用例保证程序中每个判断的每个条件的可能取值至少执行一次。判断-条件覆盖：设计足够的测试用例，使判断中每个条件的所有可能取值至少执行一次，同时每个判断的所有可能取值分支至少执行一次。*：覆盖的强度依次是：语句覆盖路径覆盖判定覆盖条件覆盖判断-条件覆盖。&黑盒测试黑盒测试不关心程序内部的逻辑，只是根据程序的功能说明来设计测试用例，主要方法有等价类划分法、边界值分析法、错误推测法等，主要用软件的确认测试。14、软件测试过程分4个步骤，即单元测试、集成测试、验收测试和系统测试。（1）单元测试是对软件设计的最小单位-模块（程序单元）进行正确性检验测试。单元测试的技术可以采用静态分析和动态测试。（2）集成测试是测试和组装软件的过程，主要目的是发现与接口有关的错误，主要依据是概要设计说明书。集成测试所设计的内容包括：软件单元的接口测试、全局数据结构测试、边界条件和非法输入的测试等。集成测试时将模块组装成程序，通常采用两种方式：非增量方式组装和增量方式组装。（3）确认测试的任务是验证软件的功能和性能，以及其他特性是否满足了需求规格说明中确定的各种需求，包括软件配置是否完全、正确。确认测试的实施首先运用黑盒测试方法，对软件进行有效性测试，即验证被测软件是否满足需求规格说明确认的标准。（4）系统测试是通过测试确认软件，作为整个基于计算机系统的一个元素，与计算机硬件、外设、支撑软件、数据和人员等其他系统元素组合在一起，在实际运行（使用）环境下对计算机系统进行一系列的集成测试和确认测试。系统测试的具体实施一般包括：功能测试、性能测试、操作测试、配置测试、外部接口测试、安全性测试等。15、程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行，调试程序应该由编制源程序的程序员来完成。*程序调试的基本步骤：（1）错误定位。从错误的外部表现形式入手，研究有关部分的程序，确定程序中出错位置，找出错误的内在原因。（2）修改设计和代码，以排除错误。（3）进行回归测试，防止引进新的错误*修改错误原则：(1）在出现错误的地方，很可能有别的错误；(2）修改错误的一个常见失误是只修改了这个错误的征兆或这个错误的表现，而没有修改错误本身；(3）注意修正一个错误的同时有可能会引入新的错误；(4）修改错误的过程将迫使人们暂时回到程序设计阶段；(5）修改源代码程序，不要改变目标代码。16、从技术观点看，软件设计包括：结构设计、数据设计、接口设计、过程设计。第四章 数据库设计基础1、数据、数据库、数据管理系统（1）数据：实际上就是描述事物的符号记录。（2）数据库（DB）：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序所共享。（3）数据库管理系统（DBMS）：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。2、数据库系统的基本概念数据库管理系统提供以下的数据语言：数据定义语言：负责数据的模式定义与数据的物理存取构建；数据操纵语言：负责数据的操纵，如查询与增、删、改等；数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。3、数据库系统（DBS）：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。*数据库应用系统：由数据库系统、应用软件及应用界面三者组成。*：数据库技术的根本目标是解决数据的共享问题。34、数据库系统的基本特点（1）数据的高集成性。（2）数据的高共享性与低冗余性。（3）数据独立性：数据独立性是数据与程序间的互不依赖性，即数据库中数据独立于应用程序而不依赖于应用程序。数据独立性一般分为物理独立性与逻辑独立性两级。5、数据库系统的基本概念数据统一管理与控制。&数据统一管理与控制主要包含以下三个方面：1）数据的完整性检查：检查数据库中数据的正确性以保证数据的正确。2）数据的安全性保护：检查数据库访问者以防止非法访问。3）并发控制：控制多个应用的并发访问所产生的相互干扰以保证其正确性。&数据库系统的内部结构体系（1）数据库系统的三级模式： 1）概念模式：数据库系统中全局数据逻辑结构的描述，是全体用户（应用）公共数据视图。2）外模式：也称子模式或用户模式，它是用户的数据视图，也就是用户所见到的数据模式，它由概念模式推导而出。3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。6、数据模型（1）E-R模型的基本概念：1）实体：现实世界中的事物。2）属性：事物的特性。3）联系：现实世界中事物间的关系。实体集的关系有一对一、一对多、多对 多 的联系。4）码：唯一标识实体的属性集称为码。5）域：属性的取值范围称为该属性的域。*：E-R模型的基本成分是实体和联系。（2）E-R模型的图示法：1）实体集：用矩形表示。2）属性：用椭圆形表示。3）联系：用菱形表示。4）实体集与属性间的联接关系：用无向线段表示。5）实体集与联系间的联接关系：用无向线段表示。（3）数据库管理系统常见的数据模型有层次模型、网状模型和关系模型三种。1）层次模型的基本结构是树形结构。2）网状模型是层次模型的一个特例，从图论上看，网状模型是一个不加任何条件限制的无向图。36、（1）关系模型采用二维表来表示，一个二维表就是一个关系，二维表中的每一个分量都是不可再分的（2）同一个关系模型的任两个元组值不能完全相同。（3）在关系中，水平方向的行称为元组，垂直方向的列称为属性，每一列有一个属性名。（4）一个关系表的行称为元组。主码：或称为关键字，表中的一个属性或几个属性的组合、其值能唯一地标识表中一个元组的。主码属性不能取空值。（5）关系模型采用二维表来表示，二维表一般满足下面7个性质：1）二维表中元组个数是有限的-元组个数有限性；2）二维表中元组均不相同-元组的唯一性；3）二维表中元组的次序可以任意交换-元组的次序无关性；4）二维表中元组的分量是不可分割的基本数据项-元组分量的原子性；5）二维表中属性名各不相同-属性名唯一性；6）二维表中属性与次序无关，可任意交换-属性的次序无关性；7）二维表属性的分量具有与该属性相同的值域-分量值域的统一性（6）在二维表中惟一标识元组的最小属性值称为该表的键或码。二维表中可能有若干个健，它们称为表的侯选码或侯选健。从二维表的所有侯选键选取一个作为用户使用的键称为主键或主码。表A中的某属性集是某表B的键，则称该属性值为A的外键或外码。（7）关系操纵：数据查询、数据删除、数据插入、数据修改。（8）关系模型允许定义三类数据约束，它们是实体完整性约束、参照完整性约束以及用户定义的完整性约束。37、关系代数（1）交运算：关系R与S经交运算后所得到的关系是由那些既在R内又在S内的有序组所组成，记为RS。（2）除运算：如果将笛卡尔积运算看作乘运算的话，除运算就是它的逆运算。当关系T=RS时，则可将除运算写成：TR=S或T/R=SS称为T除以R的商。除法运算不是基本运算，它可以由基本运算推导而出。（3）连接与自然连接运算连接运算又可称为运算，这是一种二元运算，通过它可以将两个关系合并成一个大关系。设有关系R、S以及比较式ij，其中i为R中的域，j为S中的域，含义同前。则可以将R、S在域i，j上的连接记为：R | Sij在连接中如果为=，就称此连接为等值连接，否则称为不等值连接；如为时称为大于连接。自然连接（natural join）是一种特殊的等值连接，它满足下面的条件：两关系间有公共域；通过公共域的等值进行连接。设有关系R、S，R