VF全国计算机等级考试二级公共基础知识点总结_资格考试-计算机等级考试.pdf

《VF全国计算机等级考试二级公共基础知识点总结_资格考试-计算机等级考试.pdf》由会员分享，可在线阅读，更多相关《VF全国计算机等级考试二级公共基础知识点总结_资格考试-计算机等级考试.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第一章数据结构与算法 1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。2.算法的三种基本控制结构：顺序，选择，循环。3.算法的复杂度主要包括：时间复杂度，空间复杂度。4.算法的时间复杂度：指执行算法所需要的计算工作量。5.计算工作量：在执行过程中所需要基本运算的执行次数。6.算法的时间复杂度与问题的规模有关，也可能与输入有关。分析方法：平均性态和最坏情况复杂性。7.算法的空间复杂度：指执行算法所需要的内存空间。8.数据结构：指反映数据元素之间关系的数据元素集合的表示。9.研究数据结构的目的：提高数据处理的速度，节省数据处理所占用的存储空间。10.数据的逻辑结构：指反映数据元素之间

2、逻辑关系的数据结构。11.数据的存储结构：指数据的逻辑结构在计算机存储空间中的存放形式。12.常用的存储结构：顺序，链接，索引。一种逻辑结构可以有多种存储结构。13.数据结构的分类：根据数据结构中各数据元素之间前后件关系的复杂程度，分为线性结构和非线性结构。14.非空的线性结构应满足的条件：a.有且只有一个根结点；b.每个结点最多有一个前件，也最多有一个后件。反之，即为非线性结构。15.线性结构和非线性结构都可以是空的数据结构。16.线性表的顺序存储结构的特点：a.所有元素所占的存储空间是连续的；b.各元素是按逻辑顺序依次存放的。17.在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存

3、储空间。18.线性表的顺序存储结构，适用于小线性表或者其中元素不常变动的线性表。19.两种特殊的线性表：栈，队列。20.栈：只限定在一端进行插入与删除的线性表。21.栈具有记忆作用，按照“先进后出”的原则组织数据。22.通常用指针 top 来指向栈顶元素，用指针 bottom 指向栈底元素。23.top=0 表示栈空，top=m 表示栈满，其中 m 表示栈的最大容量。24.栈中元素的个数=（top 值-bottom 值）+1 25.栈的三种基本运算：入栈，退栈，读栈顶元素。26.队列：允许在一端进行插入，而在另一端进行删除的线性表。27.队列按照“先进先出”的原则组织数据。28.队头：指允许删

4、除的一端，用指针 front 指向队头元素的前一个位置。29.队尾：指允许插入的一端，用指针 rear 指向队尾元素。30.front=rear 时，表示队空或队满。31.队列中的元素个数=（rear 值-front 值）32.队列的两种基本运算：入队，退队。队列的顺序存储结构，一般采用循环队列的形式。33.线性表的链式存储结构（也称为线性链表）的特点：a.每个数据结点对应于一个存储单元，由两部分组成：数据域和指针域。b.存储数据结构的存储空间可以不连续。c.各数据结点的存放顺序与它们之间的逻辑关系可以不一致。其逻辑关系是由指针域来确定的。34.头指针：指向线性表中第一个结点的指针 HEAD，

5、称为头指针。35.线性链表的基本运算：插入结点，删除结点等。线性链表在插入或删除过程中不发生数据元素移动的现象，只需改变有关结点的指针即可，从而提高了效率。36.非线性结构：树，二叉树。37.有关树的基本概念：a.结点的度：一个结点所拥有的后件个数。叶子结点的度为 0.b.树的度：所有结点中的最大的度。c.树的深度：树的最大层次。38.二叉树的特点：a.非空二叉树只有一个根结点。b.每个结点最多有两棵子树，分别称为该结点的左子树和右子树。即，所有结点的度最大为 2.c.任意一棵二叉树中，度为 0 的结点总比度为 2 的结点多一个。39.满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。

6、（满二叉树，只有度为 0 和 2 的结点，而且叶子结点只出现在最后一层。）40.满二叉树的第 K 层上有12 k个结点。41.深度为 m 的满二叉树有1 2 m个结点，其中有12 m个叶子结点。42.完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。43.完全二叉树的叶子结点只可能出现在层次最大的两层上。44.有 n 个结点的完全二叉树，其叶子结点数为 n/2.45.有 n 个结点的完全二叉树的深度为 n2log+1.46.二叉树通常采用链式存储结构。47.二叉树的遍历：指不重复地访问二叉树中的所有结点。48.三种遍历方法：前序遍历（根左右），中序遍历（

7、左根右），后序遍历（左右根）。要求会遍历。49.查找技术：顺序查找，二分法查找（只适用于顺序存储的有序表）50.最坏情况下，二分查找需比较n2log次，顺序查找需比较 n 次。51.排序技术：交换类排序（冒泡排序法，快速排序法）、插入类排序（简单插入排序法，希尔排序法）、选择类排序（简单选择排序法，堆排序法）52.最坏情况下，冒泡/简单插入/简单选择，需比较的次数都是 n(n-1)/2.堆排序，需比较的次数是 O(nn2log).第二章程序设计基础 1.结构化程序设计主要强调的是：程序的易读性。2.对建立良好的程序设计风格，程序应简单、清晰、可读性好。3.源程序文档化要求程序加注释，注释一般分

8、为序言性注释和功能性注释。结构化程序设计方法的主要原则：自顶向下，逐步求精，模块化，限制使用 goto 语句。4.面向对象的方法的基本概念：5.对象，是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。6.对象的特点：标识唯一性，分类性，多态性，封装性，模块独立性好。7.在面向对象的方法中，信息隐蔽是通过对象的封装性来实现的。8.类，是具有共同属性、共同方法的对象的集合。一个对象是其对应类的一个实例。9.消息，是一个实例与另一个实例之间传递的信息。10.通常一个消息有三部分组成：接受消息的对象的名称，消息标识符，零个或多个参数。1

9、1.在面向对象的方法中，一个对象请求另一对象为其服务的方式是通过发送消息。12.继承，是使用已有的类定义作为基础建立新类的定义技术。13.多态性，是对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致不同的行动。14.类的继承和对象的多态性。第三章软件工程基础 1.计算机软件，包括程序、数据及相关文档的完整集合。2.软件危机：泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。3.软件工程：是建立并使用完善的工程化原则以较经济的手段获得能在实际机器上有效运行的可靠软件的一系列方法。4.软件在开发过程中需要应用工程化原则。5.软件工程包括 3 个要素：方法、工具、过程。环算法

10、的复杂度主要包括时间复杂度空间复杂度算法的时间复杂度指执行算法所需要的计算工作量计算工作量在执行过程中所需要基本运算的执行次数算法的时间复杂度与问题的规模有关也可能与输入有关分析方法平均性态和最坏 表示研究数据结构的目的提高数据处理的速度节省数据处理所占用的存储空间数据的逻辑结构指反映数据元素之间逻辑关系的数据结构数据的存储结构指数据的逻辑结构在计算机存储空间中的存放形式常用的存储结构顺序链接索引 结构和非线性结构非空的线性结构应满足的条件有且只有一个根结点每个结点最多有一个前件也最多有一个后件反之即非线性结构线性结构和非线性结构都可以是空的数据结构线性表的顺序存储结构的特点所有元素所占的存储

11、空间 6.软件生命周期分为：软件定义；软件开发；软件运行维护。7.软件生命周期的主要活动阶段：软件定义（可行性研究与计划指定，需求分析）；软件开发（概要设计，详细设计，软件实现，软件测试）；运行和维护。8.软件工程研究的主要内容：软件开发技术和软件工程管理。9.软件工程的原则：抽象，信息隐蔽（采用封装技术），模块化，局部化，确定性，一致性，完备性和可验证性。10.软件开发方法，包括分析方法、设计方法、程序设计方法。11.软件开发环境：是全面支持软件开发全过程的软件工具的集合。12.需求分析阶段的工作内容包括四个方面（需求获取，需求分析，编写需求规格说明书，需求评审）。13.结构化分析方法：以数

12、据流图（DFD）和数据字典（DD）为主要工具。14.数据流图中的主要图形元素：加工，数据流，存储文件，源/潭。15.数据字典：其作用是对数据流图中出现的被命名的图形元素的确切解释。16.结构化分析的常用工具：DFD,DD,判定树，判定表。17.需求分析阶段的最后成果：软件需求规格说明书。18.软件需求规格说明书的作用：a.便于用户、开发人员进行理解和交流。b.反映出用户问题的机构，可作为软件开发工作的基础和依据。c.作为确认测试和验收的依据。19.软件设计：从技术观点来看，包括结构设计，数据设计，接口设计，过程设计；从工程管理角度来看，分两步完成（概要设计和详细设计）。20.软件设计的基本原理

13、：抽象，模块化，信息隐蔽，模块独立性（通过内聚性和耦合性来衡量）。21.一般较优秀的软件设计，应尽量做到“高内聚低耦合”。22.结构化设计方法：是将软件设计成由相对独立、单一功能的模块组成的结构。23.概要设计的主要任务：确定软件由哪些模块组成及模块之间的关系，即软件功能的分解。24.概要设计中，面向数据流的设计方法：可以把数据流图变换成软件结构图。25.典型的数据流类型有两种（变换型和事务型）。26.详细设计的主要任务：为每个模块确定实现的算法和局部数据结构，并且用某种选定的表达工具表示出它们的细节。27.详细设计中，过程设计的常见工具有：程序流程图，N-S 方框图，PAD 问题分析图，PD

14、L 伪码。程序流程图中的主要图形元素：控制流，加工步骤，逻辑条件。28.软件测试，其主要过程涵盖了整个软件生命期的过程。29.软件测试的目的：发现错误。30.测试用例：是为测试设计的数据，包括输入值集和输出值集。31.一个好的测试用例，找到迄今为止尚未发现的错误。32.软件测试的方法：从是否需要执行被测软件的角度，分为动态测试和静态测试；从功能上，可分为白盒测试和黑盒测试。33.白盒测试：也称为结构测试或逻辑驱动测试，是在程序内部进行，主要用于完成软件内部操作的验证。34.白盒测试的主要方法：逻辑覆盖，基本路径测试。35.黑盒测试：也称为功能测试或数据驱动测试，检查程序的功能是否符合它的功能说

15、明。36.黑盒测试的主要方法：等价类划分法，边界值分析法，错误推测法，因果图。37.软件测试的实施分为四个步骤：单元测试，集成测试，验收测试（确认测试），系统测试。38.单元测试的目的：发现各模块内部可能存在的各种错误。39.单元测试的依据：详细设计说明书和源程序。40.单元测试的技术：静态分析和动态测试。对动态测试通常以白盒测试为主，辅之以黑盒测试。41.集成测试：是测试和组装软件的过程。42.集成测试的目的：发现与接口有关的错误。43.集成测试的依据：概要设计说明书。44.确认测试的目的：检查软件产品是否符合需求定义的过程。45.确认测试的主要方法：黑盒测试。环算法的复杂度主要包括时间复杂

16、度空间复杂度算法的时间复杂度指执行算法所需要的计算工作量计算工作量在执行过程中所需要基本运算的执行次数算法的时间复杂度与问题的规模有关也可能与输入有关分析方法平均性态和最坏 表示研究数据结构的目的提高数据处理的速度节省数据处理所占用的存储空间数据的逻辑结构指反映数据元素之间逻辑关系的数据结构数据的存储结构指数据的逻辑结构在计算机存储空间中的存放形式常用的存储结构顺序链接索引 结构和非线性结构非空的线性结构应满足的条件有且只有一个根结点每个结点最多有一个前件也最多有一个后件反之即非线性结构线性结构和非线性结构都可以是空的数据结构线性表的顺序存储结构的特点所有元素所占的存储空间 46.系统测试的目

17、的：在真实的系统工作环境下检验软件是否能与系统正确链接，发现软件与系统需求不一致的地方。47.程序调试：主要在开发阶段。48.程序调试的任务：诊断和改正程序中的错误。49.程序调试的基本步骤：a.错误定位；b.修改设计，以排除错误；c.回归测试，以防止引进新的错误。50.软件调试方法：以静态调试为主，辅之以动态调试。51.静态调试：主要指通过人的思维来分析源程序代码和排错。第四章数据库设计基础 1.数据库系统（DBS），数据库(DB)，数据库管理系统（DBMS），数据库管理员（DBA），数据库应用系统（DBAS）2.数据库管理系统（DBMS）是数据库系统（DBS）的核心。3.数据管理发展至今经

18、历了三个阶段：人工管理阶段，文件系统阶段，数据库系统阶段。4.数据库系统的基本特点：数据的集成性，数据的高共享性与低冗余性，数据独立性，数据统一管理与控制。5.数据库系统的内部结构体系：三级模式及二级映射。6.三级模式：外部级模式，概念级模式，内部级模式。7.二级映射：外部级到概念级的映射，概念级到内部级的映射。8.概念模式：数据库系统中全局数据逻辑结构的描述，是全体用户公共数据视图。它处于中层，反映了设计者的数据全局逻辑要求。9.外模式：是每个用户的数据视图，也就是每个用户所见到的数据模式。它处于最外层，反映了每个用户对数据的要求，也称为用户模式或子模式。10.内模式：它处于最底层，反映了数

19、据在计算机物理结构中的实际存储形式，也称为物理模式。11.数据模型：按不同的应用层次分成三种（概念模型，逻辑模型，物理模型）。12.E-R模型：是一种常用的概念模型。该模型将现实世界的要求转化为实体、属性、联系等几个概念。13.联系：一对一的联系（例如，学校和校长），一对多的联系（例如，学生和宿舍房间），多对多（例如，学生和可选课程，学生和老师）的联系。14.E-R模型的图示法：实体集，属性，联系。15.数据库模型：层次模型（树形结构），网状模型（网状结构），关系模型（二维表结构）。16.关系模型：采用二维表来表示，17.二维表一般满足的 7 个性质：元组个数有限性，元组的惟一性，元组的次序无

20、关性，元组分量的原子性，属性名的惟一性，属性名的次序无关性，分量值域的同一性。18.关系的“键”或“码”：具有标识元组、建立元组间联系等重要作用。19.在二维表中，凡能惟一标识元组的最小属性集称为该表的键或码。20.二维表中可能有若干个键，它们称为该表的候选键。选取其中一个作为用户使用的键，称为主键。21.关系模式支持子模式。关系子模式也是二维表结构，称为视图。22.关系操纵：包括四种查询、增加、删除、修改。23.关系中的数据约束：实体完整性约束，参照完整性约束，用户定义的完整性约束。24.关系代数中，关系模型的基本运算：插入（R S）、删除（R-S）、修改(R-S)S)、查询。25.查询的三

21、个操作：投影，选择，笛卡尔积（R S）.26.关系代数中的扩充运算：交运算，除运算，连接与自然连接运算。27.最常用的关系运算：选择，投影，自然连接，并运算，差运算。（要求会运算）环算法的复杂度主要包括时间复杂度空间复杂度算法的时间复杂度指执行算法所需要的计算工作量计算工作量在执行过程中所需要基本运算的执行次数算法的时间复杂度与问题的规模有关也可能与输入有关分析方法平均性态和最坏 表示研究数据结构的目的提高数据处理的速度节省数据处理所占用的存储空间数据的逻辑结构指反映数据元素之间逻辑关系的数据结构数据的存储结构指数据的逻辑结构在计算机存储空间中的存放形式常用的存储结构顺序链接索引 结构和非线性

22、结构非空的线性结构应满足的条件有且只有一个根结点每个结点最多有一个前件也最多有一个后件反之即非线性结构线性结构和非线性结构都可以是空的数据结构线性表的顺序存储结构的特点所有元素所占的存储空间 28.数据库设计是数据库应用的核心。29.数据库设计的四个阶段：需求分析，概念设计，逻辑设计，物理设计。30.需求分析阶段：经常采用的方法有结构化分析方法（自顶向下、逐层分解）和面向对象的方法。主要结果是建立数据字典，任务是确定新系统的功能。31.概念设计阶段：建立一个数据的抽象模型。经常采用的方法有两种：集中式模式设计法、视图集成设计法。视图设计的三种设计次序：自顶向下，由底向上，由内向外。视图集成过程

23、中，要解决的常见冲突有：命名冲突、概念冲突、域冲突、约束冲突。视图经过合并生成初步的 E-R图。32.逻辑设计阶段：主要工作是将 E-R图转换成指定 RDBMS 中的关系模式。如表格 1 所示。33.物理设计阶段：主要内容有索引设计、集簇设计、分区设计。34.数据库管理 关系 实体集 关系 联系 属性 属性 元组 实体 关系模型 E-R 模型 表格 1 环算法的复杂度主要包括时间复杂度空间复杂度算法的时间复杂度指执行算法所需要的计算工作量计算工作量在执行过程中所需要基本运算的执行次数算法的时间复杂度与问题的规模有关也可能与输入有关分析方法平均性态和最坏 表示研究数据结构的目的提高数据处理的速度节省数据处理所占用的存储空间数据的逻辑结构指反映数据元素之间逻辑关系的数据结构数据的存储结构指数据的逻辑结构在计算机存储空间中的存放形式常用的存储结构顺序链接索引 结构和非线性结构非空的线性结构应满足的条件有且只有一个根结点每个结点最多有一个前件也最多有一个后件反之即非线性结构线性结构和非线性结构都可以是空的数据结构线性表的顺序存储结构的特点所有元素所占的存储空间