2025年计算机等级考试二级公共基础知识核心要点精讲

第一章

1、算法是指解题方案的精确而完整的描述

2、算法的基本特性可行性、确定性、又穷性、拥有足够的情报

3、算法设计基本措施列举法、归纳法、递推、递归、减半递推技术、回溯法

4、算法的复杂度重要包括时间复杂度和空间复杂度

5、用算法在执行过程中所需基本运算的执行次数来度量算法的工作量

6、数据构造作为计算机的一门学科，重要研究和讨论一下三个方面的问题

（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑构造

（2）在对数据进行处理时，各数据元素在计算机中的储存关系，即数据的存储构造

（3）对数据构造进行的运算

7、数据的逻辑构造是指带有构造的数据元素的集合

8、数据构造应包括

（1）表达数据元素的信息

（2）表达各数据元素之间的前后件关系

9、所谓数据的逻辑构造，是指反应数据元素之间逻辑关系的数据构造

10、数据的逻辑构造在计算机存储空间中的寄存形式称为数据的存储构造

11、根据数据构造中各数据元素之间前后件关系的复杂程度一般将数据构造分为两大类型:线性构造与非线性构造

12、假如一种非空的数据构造满足下列两个条件

（1）有且只有一种根结点

（2）每一种结点最多有一种前件，也最多有一种后件则称该数据构造为线性构造，又称线性表

13、线性表是最简朴、最常用的一种数据构造

14、非线性表有如下构造特性

（1）有且只有一种根结点al,它无前件

（2）有且只有一种终止点An,它无后件

（3）除根结点与终止端外，其他所有结点有且只有一种前件，也有且只有一种后件，线性表中结点的个数n称为为线性表长度，当n=0时，称为空表15线性表的次序存储构造具有两个基本特点

（1）线性表中所有元素所占的存储空间是持续的

（2）线性表中各数据元素在存储空间中是按逻辑次序依次寄存的

16、次序表的插入、删除运算

17、栈是限定在一端进行插入与删除的线性表

18、栈是按照“先进后出”或“后进先出”的原则组织数据的，栈也被称为“先进后出”表或“后进先出”表19＞栈中的个数=bottom-top+l（用值大的减值小的再加一）Top=0表达栈空top=m表达栈满支持子程序调用的数据构造是栈栈的基本运算有三种入栈、退栈、与读栈顶元素

20、队列是指容许在一端进行插入、而在另一端进行删除的线性表

21、队列称为“先进先出”或“后进后出”的线性表

22、对列空与对列满的条件队列空的条件为s=0,队列满的条件为s=l且ftont=rear

23、入队运算、是指在循环队列的队尾加入一种新元素退队运算、是指在循环队列的排头位置退出一种元素并赋给指定的变量

24、线性表的链式存储式构造称为线性链表

25、

（1）在线性链表中查找指定元素

（2）线性链表的插入、是指在链式存储构造下的线性表中插入一种新元素

（3）线性链表的删除、是指在链式存储构造下的线性表中删除包括指定元素的结点

26、树是一种简朴的非线性构造

27、树这种数据构造的基本特性

（1）在树构造中每一种结点只有一种前件，称为父结点没有前件的结点只有一种，称为树的根结点，简称为树的根

（2）在树构造中，每一种结点可以有多种后件，它们都称为该结点的子结点没有后件的结点称为叶子结点

（3）在树构造中，一种结点所拥有的后件个数称为该结点的度叶子结点的度为在树中，所有结点中的最大的度称为树的度

28、树的最大层次称为树的深度

29、在树中，以某结点的一种子结点为根构成的树称为该结点的一颗子树，叶子结点没有子树

30、二叉树，是一种很有用的非线性构造

31、二叉树的特点

（1）非空二叉树只有一种根结点

（2）每一种结点最多有两颗子树，每一种结点的度最大为

232、二叉树的基本性质

（1）在二叉树的第k层上，最多有2的k-l次方（k=l）个结点

（2）深度为m的二叉树最多有2的m次方-1个结点（深度为m的二叉树是指二叉树共有m层）

（3）在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一种

（4）具有n个结点的二叉树,其深度至少为【log2N】+l,其中【log2N】表达取其整数部分

33、满二叉树与完全二叉树

（1）满二叉树除最终一层外，每一层上的所有结点均有两个子结点

（2）完全二叉树除最终一层外，每一层上的结点树均到达最大值，在最终一层上只缺乏右边的若干结点

34、完全二叉树的性质

（1）具有m个结点的完全二叉树的深度为【log2N1+1

（2）设完全二叉树共有n个结点

35、计算机中二叉树一般采用链式存储构造

36、二叉树的遍历是指不反复地访问二叉树中的所有结点

（1）前序遍历

（2）中序遍历

（3）后序遍历

37、二分法查找只合用于次序存储的有序表二分法查找只需要比较log2N次而次序查找需要比较n次

38、互换类排序法冒泡排序法、迅速排序法

39、插入类排序法简朴插入排序法、希尔排序法

40、选择类排序法简朴选择排序法、堆排序法第二章

1、注释一般分为序言性注释、功能性注释

2、构造化程序设计措施的重要原则可以概括为自项而下、逐渐求精、模块化、限制使用语句

3、面向对象措施的长处

（1）与人类习惯的思维措施一

（2）稳定性好⑶可重用性好

（4）易于开发大型软件产品

（5）可维护性好

4、对象的基本特点标志唯一性、分类性、多态性、封装性、模块独立性好

5、将属性、操作相似的对象归为类类是对象的抽象

6、消息对象与对象之间的传递形式称为消息

7、继承是指可以直接获得已经有的性质和特性，而不必反复定义他们第三章

1、计算机软件是计算机系统中与硬件互相依存的另一部分，是包括程序、数据及有关文档的完整集合

2、软件的特点

（1）软件是一种逻辑实体，而不是物理实体，具有抽象性

（2）软件的生产与硬件不一样他没有明显的制作过程

（3）软件在运行、有效期间不存在磨损、老化问题

（4）软件的开发、运行对计算机系统具有依赖性受计算机系统的限制导致了软件移植问题

（5）软件复杂性高，成本昂贵

（6）软件开发波及诸多的社会原因

2、软件工程概念的出现源自软件危机

3、软件危机重要表目前

（1）软件需求的增长得不到满足

（2）软件开发成本和进度无法控制

（3）软件质量难以保证

（4）软件不可维护或维护程度非常低

（5）软件的成本不停提高

（6）软件开发生产率的提高赶不上硬件的发展和应用需求的增长

4、软件工程3要素，措施、工具、过程

5、软件生命周期，软件定义、软件开发、软件运行

6、软件生命周期的重要活动阶段，

（1）可行性研究与计划制定

（2）需求分析

（3）软件设计

（4）软件实现

（5）软件测试

（6）运行和维护

7、软件工程的原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、和可验证性

8、软件开发环境是全面支持软件开发全过程的软件工具集合

9、需求分析阶段的工作

（1）需求获取

（2）需求分析

（3）编写需求规格阐明书

（4）需求评审

10、需求分析措施

（1）构造化分析措施

（2）面向对象的分析措施

11、数据流图重要图形元素（椭圆）加工转换（箭头）数据流（两条横线）存储文献（长方形）源，潭

12、数据字典、是构造化分析措施的关键，数据字典是对所有与系统有关的数据元素的一种有组织的列表以及精确的严格的定义，使得顾客和系统分析员对于输入、输出、存储成分和中间计算成果有共同的理解

13、软件需求规格阐明书的作用是

（1）便于顾客、开发人员进行理解和交流

（2）反应出顾客问题的构造，可以作为软件开发工作的基础和根据

（3）作为确认测试和验收的根据

14、软件设计的重要性和地位概括为如下几点

（1）软件开发阶段（设计、编码、测试）占据软件项目开发总成本绝大部分，是在软件开发中形成质量的关键环节

（2）软件设计是开发阶段最重要的环节，是将需求精确的转化为完整的软件产品或系统的唯一途径

（3）软件设计作出的决策，最终影响软件实现的成败

（4）设计是软件工程和软件维护的基础

15、衡量软件的模块独立性使用耦合性和内聚性两个定性的度量原则

16、软件概要设计的基本任务是

（1）设计软件系统构造

（2）数据构造及数据库设计

（3）编写概要设计文档

（4）概要设计文档评审经典的数据流类型有两种变换型和事务型

17、常见的过程设计工具有

（1）图形工具程序流程图18

（2）表格工具鉴定表

（3）语言工具PDL（伪码）

19、软件测试的目的、发现错误

20、软件测试措施若从与否需要执行被测软件的角度，可分为静态测试和动态测试若按照功能划分为白盒测试和黑盒测试

21、静态测试不实际运行软件，重要通过人工进行，动态测试是基于计算机的测试

22、白盒测试的重要措施有逻辑覆盖、基本途径测试

23、黑盒测试措施重要有等价类划分法、边界分析法、错误推测法、因果图，重要用于软件确认测试

24、软件测试过程单元测试、集成测试、验收测试（确认测试）、系统测试

25、系统测试的详细实行一般包括功能测试、性能测试、操作测试、配置测试、外部接口测试、安全性测试

26、程序调试的任务是诊断和改正程序中的错误第四章

1、数据实际上就是描述事物的符号记录

2、数据库是数据的集合

3、数据库管理系统DBMS、数据定义语言DDL、数据操纵语言DML、数据控制语言DCL

4、数据库管理员的重要工作数据库设计、数据库维护、改善系统性能

5、数据管剪发展至今经历了三个阶段人工管理阶段、文献系统阶段、数据库系统阶段

6、数据库系统具有如下特点数据的集成性、数据的高共享性、数据独立性、数据统一管理与控制（数据的完整性检查、数据的安全性保护、并发控制）

7、数据库系统的三级模式概念模式、外模式、内模式

8、数据库系统的两级映射概念模式到内模式的映射、外模式到概念模式的映射

9、数据模型描述内容有三个部分数据构造、数据操作、数据约束

10、E-R模型可以用一种非常直观的图的形式表达，称为E-R图

11、层次模型是最早发展起来的数据库模型网状模型是一种不加任何条件限制的无向图

12、二维表一般满足七个性质元组个数有限性、元组的唯一性、元组的次序无关性、元组分量的原子性、属性名惟一性、属性的次序无关性、分量值域的同一性

13、关系模型的数据操纵即是建立在关系上的数据操纵，一般有查询、增长、删除及修改四种操纵

14、关系模型容许定义三类数据约束实体完整性约束、参照完整性约束、顾客定义的完整性约束

15、关系模型的基本运算插入、删除、修改、查询

16、常用的扩充运算有交、除、连接及自然连接

17、数据库设计是数据库应用的关键

18、数据库概念设计的措施集中式模式设计法、视图集成设计法、

19、数据库的逻辑设计重要工作是将E-R图转换成指定RDBMS中的关系模式。