82011全国二级公共基础知识

个人收集整理-ZQ82011全国二级公共基础知识第一章 数据结构与算法算法是一组严谨的定义运算顺序的规则，是指令的有限序列。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。基本运算：算术运算、逻辑运算、关系运算、数据传输。控制结构：算法中各操作之间的执行顺序。算法设计的基本方法：列举法、归纳法、递推、递归、减半递推、回溯法。算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求。算法的时间复杂度，是指执行算法所需要的计算工作量。取决于问题的规模与待处理的数据的初态。平均性态：是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。数据结构：指相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。提高数据处理效率：提高数据处理的速度节省存储空间数据的逻辑结构：集合、线性结构、树形结构、图形结构。两个要素：数据元素的集合，数据元素之间的前后关系。b5E2R。b5E2R。数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式。（物理结构）常用的存储结构有顺序、链接、索引等。p1Ean。p1Ean。空的数据结构：在一个数据结构中一个数据元素都没有。根据前后关系的复杂程度（从逻辑上），可将数据结构分为两大类型：线性结构（线性表）、非线性结构。线性结构与非线性结构都可以是空的数据结构。线性表是个属于同一数据类型的数据元素构成的有限序列。若干数据项组成的数据元素称为记录，多个记录构成的线性表称为文件。为数据元素再线性表中的位序。DXDiT。DXDiT。线性表的顺序表：用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构是一种随机存取的存储结构（一维空间）。RTCrp。RTCrp。栈：实际也是线性表。是只能在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端为栈底。没有元素时为空栈。栈顶元素总是后被插入的元素，也是最先被删除的元素。称为“先进后出”“后进先出”表。5PCzV。5PCzV。栈的顺序存储及其运算：、入栈运算：在栈顶位置插入一个新元素。先将栈顶指针加，然后将新元素插入到栈顶指针指向的位置。、退栈运算：取出栈顶元素并赋给一个指定的变量。首先将栈顶元素赋给一个指定的变量，然后将栈顶指针减。、读栈顶元素：将栈顶元素赋给一个指定的变量。不删除栈顶元素，栈顶指针不会改变。jLBHr。jLBHr。队列：是只允许在一端删除，在另一端插入的顺序表，允许删除的一端叫做队头，允许插入的一端叫做队尾。“先进先出”“后进后出”表。往尾部插入一个元素称为入队运算。从排头删除一个元素称为退队运算。xHAQX。xHAQX。循环队列及其运算：队列的顺序存储结构一般采用循环队列的形式。将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。、入队运算：在循环队列的队尾加入一个新元素。、退队运算：在队头位置推出一个元素并赋给指定的变量。LDAYt。LDAYt。线性链表：只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。链表中结点的逻辑次序和物理次序不一定相同。树：由个结点组成的有限集合。若不为空树，则：、由一个特定的称为根的结点，只有直接后件，没有直接前件。、出根以外的其他结点可以划分为个互不相交的有限集合，每个集合又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前件，但可以有或多个直接后件。一个结点所拥有的后件个数称为结点的度。树的最大层次称为树的深度。Zzz6Z。Zzz6Z。二叉树：是由个结点的有限集合构成，集合为空集或由一个根结点及两棵相互不相交的左右子树组成，左右子树都是二叉树。二叉树不是树的特殊情况，是两个概念。特点：非空二叉树只有一个根结点；在而二叉树中不存在度大于二的结点，是有序树（树为无序树），子树的顺序不能颠倒。叶子结点总是比度为的结点多一个。dvzfv。dvzfv。完全二叉树结点的排列顺序为：从上到下，从左到右。若左边空一个位置不能将结点放入右边。完全二叉树除最后一排都是满的。rqyn1。rqyn1。在计算机中，二叉树通常采用链式存储结构。遍历二叉树：.前序遍历：根结点左子树右子树（在遍历左右子树时，仍然先访问根结点）、中序遍历：左子树根结点右子树（左大树都遍历了再右大树）、后序遍历：左子树右子树根结点Emxvx。Emxvx。排序方法时间复杂度空间复杂度复杂性平均情况最坏情况最好情况直接插入排序简单冒泡排序简单希尔排序较复杂快速排序较复杂简单选择排序简单堆排序较复杂第二章 程序设计基础程序设计经历的阶段：结构化程序设计阶段、面向对象的程序设计阶段。程序注释：、序言性注释：开头部分，给出程序的整体说明。、功能性注释：嵌在源程序体中，描述语句或程序的主要功能，不包括模块的功能。SixE2。SixE2。注意：编写程序要做到清晰第一，效率第二；即在正确的基础上再要求提高效率。模块化，使模块功能尽可能单一化（.函数实现）；模块的独立性，利用信息隐蔽，确保每一个模块的独立性（.局部变量）。对所有输入要检验输入数据的合法性；输入成批数据时，应有输入结束标志；6ewMy。6ewMy。结构化程序设计四条原则：自顶向下、逐步求精、模块化、限制使用语句。三种基本控制结构：顺序、选择和循环结构化程序设计的优缺点 优点：易读、易理解、易维护、结构良好；缺点：面向过程、可重用性差面向对象的方法：系统中的对象以及对象之间的关系能够如实地反映问题域中固有事物及其关系。一个对象应包括数据和需要进行的操作。对象就是一个包含数据以及与这些数据有关的操作的集合。kavU4。kavU4。面向对象优点：稳定性好、易修改、易理解、易于测试和调试。最大区别是：数据与操作结合。 对象：由一组表示其静态特征的属性和它可执行的一组操作（对象的动态特征）组成。 对象特征：对象标识唯一；分类性；多态性；封装性；模块独立性好。消息：对象之间相互请求或相互协作的途径，是要求某个对象执行某个功能操作的规格说明，它统一了数据流与控制流。种类：共有消息、私有消息。消息的使用类似函数的调用，消息中指定了某一实例，一个操作名和一个参数表。y6v3A。y6v3A。 继承：是指能够直接获得已有的性质和特征。而不必重复定义他们。分为单继承和多重继承。继承性是类所具有的性质，对象没有继承性。M2ub6。M2ub6。多态性：是指同样的消息被不同的对象接受时可导致完全不同的行动。消息是指对类的成员函数的调用。不同的行为是指不同的实现，即调用不同的函数。第三章 软件工程基础软件定义：与计算机系统的操作有关的计算机程序、规程、规律，以及可能有的文件、文档及数据。包括程序、数据及相关文档的完整集合。0YujC。0YujC。特点：不是物理实体，有抽象性；常受计算机系统的限制；复杂性高，成本昂贵。分类（按功能）：系统软件、工具软件、应用软件。 软件危机主要表现在成本、质量、生产率等问题。 软件工程包括三要素：方法、工具和过程。软件生命周期：将软件从提出、实现、使用维护到停止使用退役的过程称为软件周期。（定义、开发、维护三大阶段）eUts8。eUts8。软件工程研究的内容主要包括：软件开发技术、软件工程管理。 软件工程原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。需求分析阶段：需求获取、需求分析、编写规格说明书、需求评审。 结构化分析方法：使用数据流图、数据字典、结构化英语、判定表和判定树等工具，来建立一种新的称为结构化规格说明书的目标文档。实质：着眼于软件内部数据流，自顶向下，逐层分解。sQsAE。sQsAE。 数据流图和数据词典共同组成系统的逻辑模型。结构化分析方法的开发过程：计划期、开发期、运行期。从技术观点看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。从工程管理角度看，软件设计分为两步：概要设计和详细设计。 模块划分的原则是模块独立性。 衡量软件模块独立性使用耦合性和内聚性两个定性的度量标准。耦合：是模块间互相连接的紧密程度的度量。内聚：是一个模块内部各个元素彼此结合的紧密程度的度量。 划分模块尽量做到高内聚、低耦合，保持模块相对独立性。软件测试方法：静态测试、动态测试测试用例的设计方法：白盒测试方法、黑盒测试方法。白：有逻辑覆盖、基本路径测试。黑：也称功能测试或数据驱动测试。GMsIa。GMsIa。单元测试：是针对软件设计的最小单位模块，进行正确性检验的测试工作。目的在于发现各模块内部可能存在的各种错误。TIrRG。TIrRG。集成测试：是在单元测试的基础上，把所有模块按照设计要求组装成为系统，同时进行测试。目的：发现与接口有关的错误。测试方式：非增量方式和增量方式组装。7EqZc。7EqZc。验收测试：用黑盒测试法。系统测试：目的在真实的工作环境下检验软件是否与系统正确连接。 程序调