计算机等级考试二级公共基础知识部分重点归纳

doc文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。计算机等级考试二级公共基础知识部分重点归纳计算机等级考试二级公共基础知识部分重点归纳2010-08-0216:311.算法是一种设计好的计算序列，用来解决一类问题。12.算法复杂的包括：时间复杂度和空间复杂度。时间复杂度指计算工作量，空间复杂度指内存空间的要求。3.数据元素的集合，记为D，数据之间的前后关系，记为R，B=（D,R）,B表示数据结构。二元组表示D中各元素间的前后关系。4.数据的逻辑结构在计算机存储空间中的存放形式称为存储结构（物理结构）。5.常用的存储结构：顺序存储，链接存储。6.数据的存储结构中，不接要存放数据元素的信息，还要存放数据元素之间的前后件关系的信息。7.线性结构（条件：非空数据结构）：1有且只有一个根节点；2每一个节点最多有一个前件，有最多有一个后件。8.栈、队列、串等都是线性结构。9.数组、广义表、树和图等数据结构都是非线性结构。10.根据数据结构中各数据元素之间前后件关系的复杂度分：线性结构和非线性结构。11.栈，特殊的线性表，按“先进后出”或“先出后进”原则组织数据。如射击时射出子弹，顺序为后进弹匣先射出。12.栈的一端封闭，另一端开口，仅开口端允许插入和删除元素。允许插入与删除的一端称为栈顶，另一端称为栈底。无元素为空栈。13.栈的基本运算有3种：入栈、退栈、与读栈顶元素。14.队列只允许在一端（队头）进行删除，另一端（队尾）进行插入。无元素为空队列。15队列的修改是依照先进先出的原则进行。16.链式存储方式可用于两种数据结构中的任一种。17.链式中的结点由两部分组成：一部分用于存放数据元素值，称为数据域，另一部分用于存放指针，称为指针域。指针用于指向该结点的前一个或后一个结点（即前件或后件）。18.二叉树是非线性结构，具有两个特点：1非空二叉树只有一个根节点；2每一个结点最多有两个子树，分别称为左子树右子树。。19.二叉树中，每个结点的度最大为2，因此所有子树也均为二叉树。20.二叉树中，一个结点可以只有左子树或右子树，当结点没有左子树或右子树时，该结点即为叶子结点。21.二叉树具有的性质：1在二叉树的第k层上，最多有2的k-1次方（k=》1）个结点。2深度为m的二叉树最多有2的m-1次方个结点。3在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。4具有m个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分。1计算机等级考试二级公共基础知识部分重点归纳222.遍历子树一般先遍历左子树再遍历右子树，即先左后右。根据访问根节点的次序，二叉树的遍历分为3类，前序遍历、中序遍历、后序遍历。23.查找是指在一个给定的数据结构中查找某一个指定的元素。24.二分法查找也称拆半查找，只是用于顺序存储的有序表。25.对于长度为n的有序线性表，利用二分法查找流程：1将X与线性表中间项比较。2若相等则查找成功，结束查找。3若X小于中间项值，则在线性表前半部分以二分法继续查找。（X大于中间项值方法相同。）26.比较顺序查找与二分法查找，在最坏情况下，二分法查找只需log2n次，顺序查找则要n次。27.冒泡排序法和快速排序法都属于交换类排序法。其中冒泡法在最坏情况下需比较n(n-1)/2次，同此数排序还有快速排序、直接插入排序、简单插入排序、简单选择排序。28.结构化程序设计的基本结构有3类，顺序结构、选择结构、循环结构。29.结构化程序设计方法的主要原则为：自顶向下、逐步求精、模块化和限制使用goto语句。30.对象是面向对象中最基本的概念，通常把对象的操作也称为方法和服务。31.对象有5个特征：标识唯一性、分类性、多态性、封装性、模块独立性。32.类是具有共同属性，共同方法的对象的集合，类是对象的抽象，它包含了该对象类型中所有对象的性质，而一个对象则是其对应类的一个实例。33.一个消息由3部分组成：接收消息的对象的名称，消息标识符（消息名）和零个或多个参数。34.继承指的是可以直接获得已有的性质和特征，而不必重复定义它们。35.继承分为单继承与多重继承，单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。36.多态性指对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动。37.软件包括程序、数据、和相关文档的完整集合。38.软件根据应用目标的不同可分为应用软件、系统软件、支撑软件（或工具软件）。39.软件由两部分组成：1机器可执行的程序和数据；2机器不可执行的，与软件开发、运行、维护使用等有关的文档。40.软件工程包括3个要素，即方法、工具、和过程。41.软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。该周期一般包括可行性分析研究与需求分析、设计、实现、测试、交付使用以及维护等活动。42.软件的生命周期分为3个时期共8个阶段，各阶段可重复可迭代：1定义期，包括问题定义、可行性研究和需求分析；开发期，2包括概要设计、详细设计、实现和测试；维护期3，即运行维护阶段。43.从技术观点看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。从工程管理角度看，软件设计分两步完成，即概要设计和详细设计。44.软件设计应遵循的基本原理和软件设计的有关概念：1抽象；2模块化；3信息隐藏；4模块独立性。45.模块的独立程度是评价设计好坏的重要度量标准。2计算机等级考试二级公共基础知识部分重点归纳46.耦合性是模块之间互相连接的紧密程度的度量。47.耦合性取决于各个模块之间接口的复杂度、调试方式以及哪些信息通过接口。348.按耦合度可将耦合由高到低列为：内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合、非直流耦合。49.内聚性是度量一个模块功能程度的一个相对指标。50.内聚是从功能角度来衡量模块的联系，它描述的是模块内的功能联系。51.内聚度由弱到强排列为：偶然内聚、罗技内聚、时间内聚、过程内聚、通信内聚、顺序内聚、功能内聚。52.在程序结构中，内聚性越强，耦合性越弱。53.优秀的软件设计应尽量做到高内聚、低耦合，即减弱模块之间的耦合性和提高模块内的内聚性，有利于提高模块的独立性。54.结构化分析方法就是使用特定的工具建立一种新的，称为结构化规格说明的目标文档。55.结构化分析方法的实质是着眼于数据流、自顶向下、对系统的功能进行逐层分解以数据流图和数据字典为主要工具，建立系统的逻辑模型。56.结构化分析方法常用过工具有数据流图（DFD）、数据字典（DD）、结构化英语、判定表和判定树。57.软件需求规格说明书是需求分析阶段的最后成果。其特点是具有正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性和可追踪性。58.测试的目的是发现软件中的错误，其根本目的是尽可能多的发现并排出软件中隐藏的错误。59.软件测试的基本准则：1所有测试都应追溯到用户要求；2在测试之前制定测试计划，并严格执行；充分注意测试中的群集现象；避免由程序的编写者测试自己的程序；不可345能进行穷举测试；6妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便。60.软件测试按是否需要被执行可分为静态测试和动态测试。按功能划分，可分为白盒测试和黑盒测试。61.软件测试一般分为4个步骤：单元测试、集成测试、验收测试（确认测试）、和系统测试。62.程序的调试任务是诊断和改正程序中的错误，调试主要在开发阶段进行。63.程序调试活动由两部分组成，一是根据错误迹象确定程序中错误的确切性质、原因和位置；二是对程序进行修改，排除这个错误。64.程序调试的基本步骤：1错误定位；2修改设计和代码，以排除错误；3进行回归测试，防止引进新的错误。65.软件测试可分为静态调试和动态调试。静态调试主要指通过人的思维来分析原程序代码和排错。动态调试是辅助静态调试的。66.主要调试方法有：强行排错法、回溯法、原因排除法。67.数据库是数据的集合，它具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。68.数据是数据库中存储的基本对象，是描述事物的符号记录。69.数据库管理系统提供了3种语言：数据定义语言、数据操纵语言、数据控制语言。3计算机等级考试二级公共基础知识部分重点归纳70.数据库技术的根本目标是解决数据共享问题。471.数据库管理系统（DBMS）是数据库的机构，是一种系统软件，负责数据库中的数据组织、数据操作、数据维护、控制及保护和数据服务等。数据库管理系统是数据系统的核心。72.数据库系统的发展分3个阶段：文件系统阶段、层次数据库与网络数据库系统阶段和关系数据库系统阶段。73.数据库系统具有4大特点：1数据的集成性；2数据的高共享性与低冗余性；3数据独立性；4数据统一管理与控制。其中，数据独立性共分为物理独立性和逻辑独立性两种。74.数据库系统的3级模式：1外模式（子模式），一个概念模式可有若干个外模式；2内模式，物理模式，它给出了数据库屋里存储结构与物理存取方法；概念模式，3逻辑模式，一个数据库只有一个概念模式。75.数据库系统的两级映射（保证数据库系统中的数据的独立性）：1概念模式到内模式的映射；2外模式到概念模式的映射。76.数据模型所描述的内容有3个部分：数据结构、数据操作和数据约束。77.数据库管理系统所支持的数据模型分为3种：层次模型、网状模型、关系模型。78.E-R模型由实体、属性和联系三个基本概念组成。79.两个实体间的联系实际上是实体间的函数关系，即一对一的联系、一对多的联系或多对一的联系、多对多的联系。80.E-R模型用E-R图来表示，简称表，二维表一般满足下面7个性质：1.二维表中元组个数是有限的——元组个数有限性；2.二维表中元组均不相同——元组的唯一性；3.二维表中元组的次序可以任意交换——元组的次序无序性；4.二维表中元组的分量是不可分割的基本数据项——元组分量的原子性；5.二维表中属性名各不相同——属性名唯一性；6.二维表中属性与次序无关可任意交换——属性的次序无关性；7.二维表中属性的分量具有该属性相同的值域——分量值域的统一性。82.关系模型允许定义3类数据约束：实体完整性约束、参照完整性约束和用户定义的完整性约束。83.新增集合运算：1投影运算；2选择运算，从关系中找出满足给定条件的元组的操作成为选择；3笛卡儿积，对于两个关系的合并操作可以用笛卡儿积表示。设有n元关系R和m元关系S，他们分别有p和q个元组，则R和S的笛卡儿积记为：R×S。它是一个m+n元关系，元组个数是p×q。84.假设有n元关系R和n元关系S，它们的交仍然是一个n元关系，它是属于关系R切且由属于关系S的元组组成，并记为R∩S，它可由基本运算推导而得：R∩S=R-(R-S)。85.数据库设计有两种方法：1面向数据的方式是以信息需求为主，兼顾处理要求；2面向过程的方式已处理需求为主，兼顾信息要求。86.数据库设计目前一般采取生命周期法，即将系统开发分解成目标独立的若干阶段，即需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段和进一步修改阶段。在数据库设计中采用前4个阶段。41