全国计算机等级考试二级公共基础知识点总结 1/5 第一章数据结构与算法 1. 算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。 2. 算法的三种基本控制结构：顺序，选择，循环。 3. 算法的复杂度主要包括：时间复杂度，空间复杂度。 4. 算法的时间复杂度：指执行算法所需要的计算工作量。 5. 计算工作量：在执行过程中所需要基本运算的执行次数。 6. 算法的时间复杂度与问题的规模有关，也可能与输入有关。分析方法：平均性态和最坏情况复杂性。 7. 算法的空间复杂度：指执行算法所需要的内存空间。 8. 数据结构：指反映数据元素之间关系的数据元素集合的表示。 9. 研究数据结构的目的：提高数据处理的速度，节省数据处理所占用的存储空间。 10. 数据的逻辑结构：指反映数据元素之间逻辑关系的数据结构。 11. 数据的存储结构：指数据的逻辑结构在计算机存储空间中的存放形式。 12. 常用的存储结构：顺序，链接，索引。一种逻辑结构可以有多种存储结构。 13. 数据结构的分类：根据数据结构中各数据元素之间前后件关系的复杂程度，分为线性结构和非线性结构。 14. 非空的线性结构应满足的条件： a. 有且只有一个根结点；b.每个结点最多有一个前件，也最多有一个后件。 反之，即为非线性结构。 15. 线性结构和非线性结构都可以是空的数据结构。 16. 线性表的顺序存储结构的特点： a. 所有元素所占的存储空间是连续的； b. 各元素是按逻辑顺序依次存放的。 17. 在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。 18. 线性表的顺序存储结构，适用于小线性表或者其中元素不常变动的线性表。 19. 两种特殊的线性表：栈，队列。 20. 栈：只限定在一端进行插入与删除的线性表。 21. 栈具有记忆作用，按照“先进后出”的原则组织数据。 22. 通常用指针 top 来指向栈顶元素，用指针 bottom 指向栈底元素。 23. top=0 表示栈空，top=m 表示栈满，其中 m 表示栈的最大容量。 24. 栈中元素的个数=（top 值-bottom 值）+1 25. 栈的三种基本运算：入栈，退栈，读栈顶元素。 26. 队列：允许在一端进行插入，而在另一端进行删除的线性表。 27. 队列按照“先进先出”的原则组织数据。 28. 队头：指允许删除的一端，用指针 front 指向队头元素的前一个位置。 29. 队尾：指允许插入的一端，用指针 rear 指向队尾元素。 30. front=rear 时，表示队空或队满。 31. 队列中的元素个数=（rear 值-front 值） 32. 队列的两种基本运算：入队，退队。队列的顺序存储结构，一般采用循环队列的形式。 33. 线性表的链式存储结构（也称为线性链表）的特点： a. 每个数据结点对应于一个存储单元，由两部分组成：数据域和指针域。 b. 存储数据结构的存储空间可以不连续。 c. 各数据结点的存放顺序与它们之间的逻辑关系可以不一致。其逻辑关系是由指针域来确定的。 34. 头指针：指向线性表中第一个结点的指针 HEAD，称为头指针。 35. 线性链表的基本运算：插入结点，删除结点等。线性链表在插入或删除过程中不发生数据元素移动的现象， 只需改变有关结点的指针即可，从而提高了效率。 36. 非线性结构：树，二叉树。 37. 有关树的基本概念： a. 结点的度：一个结点所拥有的后件个数。叶子结点的度为 0. b. 树的度：所有结点中的最大的度。 c.树的深度：树的最大层次。全国计算机等级考试二级公共基础知识点总结 2/5 38. 二叉树的特点： a. 非空二叉树只有一个根结点。 b. 每个结点最多有两棵子树，分别称为该结点的左子树和右子树。即，所有结点的度最大为 2. c. 任意一棵二叉树中，度为 0 的结点总比度为 2 的结点多一个。 39. 满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。 （满二叉树，只有度为 0 和 2 的结点，而且叶子结点只出现在最后一层。 ） 40. 满二叉树的第 K 层上有 个结点。 1 2 k 41. 深度为 m 的满二叉树有 个结点，其中有 个叶子结点。 1 2 m 1 2 m 42. 完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 43. 完全二叉树的叶子结点只可能出现在层次最大的两层上。 44. 有 n 个结点的完全二叉树，其叶子结点数为 n/2. 45. 有 n 个结点的完全二叉树的深度为 +1. n 2 log 46. 二叉树通常采用链式存储结构。 47. 二叉树的遍历：指不重复地访问二叉树中的所有结点。 48. 三种遍历方法：前序遍历（根左右） ，中序遍历（左根右） ，后序遍历（左右根） 。要求会遍历。 49. 查找技术：顺序查找，二分法查找（只适用于顺序存储的有序表） 50. 最坏情况下，二分查找需比较 次，顺序查找需比较 n 次。 n 2 log 51. 排序技术：交换类排序（冒泡排序法，快速排序法） 、插入类排序（简单插入排序法，希尔排序法） 、 选择类排序（简单选择排序法，堆排序法） 52. 最坏情况下，冒泡/ 简单插入/ 简单选择，需比较的次数都是 n(n-1)/2. 堆排序，需比较的次数是 O (n ). n 2 log 第二章程序设计基础 1. 结构化程序设计主要强调的是：程序的易读性。 2. 对建立良好的程序设计风格，程序应简单、清晰、可读性好。 3. 源程序文档化要求程序加注释，注释一般分为序言性注释和功能性注释。 结构化程序设计方法的主要原则：自顶向下，逐步求精，模块化，限制使用 goto 语句。 4. 面向对象的方法的基本概念： 5. 对象，是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特 征的属性和它可执行的一组操作组成。 6. 对象的特点：标识唯一性，分类性，多态性，封装性，模块独立性好。 7. 在面向对象的方法中，信息隐蔽是通过对象的封装性来实现的。 8. 类，是具有共同属性、共同方法的对象的集合。一个对象是其对应类的一个实例。 9. 消息，是一个实例与另一个实例之间传递的信息。 10. 通常一个消息有三部分组成：接受消息的对象的名称，消息标识符，零个或多个参数。 11. 在面向对象的方法中，一个对象请求另一对象为其服务的方式是通过发送消息。 12. 继承，是使用已有的类定义作为基础建立新类的定义技术。 13. 多态性，是对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致不同的行动。 14. 类的继承和对象的多态性。 第三章软件工程基础 1. 计算机软件，包括程序、数据及相关文档的完整集合。 2. 软件危机：泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。 3. 软件工程：是建立并使用完善的工程化原则以较经济的手段获得能在实际机器上有效运行的可靠软件 的一系列方法。 4. 软件在开发过程中需要应用工程化原则。全国计算机等级考试二级公共基础知识点总结 3/5 5. 软件工程包括 3 个要素：方法、工具、过程。 6. 软件生命周期分为：软件定义；软件开发；软件运行维护。 7. 软件生命周期的主要活动阶段：软件定义（可行性研究与计划指定，需求分析） ；软件开发（概要设 计，详细设计，软件实现，软件测试） ；运行和维护。 8. 软件工程研究的主要内容：软件开发技术和软件工程管理。 9. 软件工程的原则：抽象，信息隐蔽（采用封装技术） ，模块化，局部化，确定性，一致性，完备性和 可验证性。 10. 软件开发方法，包括分析方法、设计方法、程序设计方法。 11. 软件开发环境：是全面支持软件开发全过程的软件工具的集合。 12. 需求分析阶段的工作内容包括四个方面（需求获取，需求分析，编写需求规格说明书，需求评审） 。 13. 结构化分析方法：以数据流图（DFD）和数据字典（DD ）为主要工具。 14. 数据流图中的主要图形元素： 加工， 数据流， 存储文件， 源/潭。 15. 数据字典：其作用是对数据流图中出现的被命名的图形元素的确切解释。 16. 结构化分析的常用工具：DFD,DD,判定树，判定表。 17. 需求分析阶段的最后成果：软件需求规格说明书。 18. 软件需求规格说明书的作用： a. 便于用户、开发人员进行理解和交流。 b. 反映出用户问题的机构，可作为软件开发工作的基础和依据。 c. 作为确认测试和验收的依据。 19. 软件设计：从技术观点来看，包括结构设计，数据设计，接口设计，过程设计；从工程管理角度来看， 分两步完成（概要设计和详细设计） 。 20. 软件设计的基本原理：抽象，模块化，信息隐蔽，模块独立性（通过内聚性和耦合性来衡量） 。 21. 一般较优秀的软件设计，应尽量做到“高内聚低耦合” 。 22. 结构化设计方法：是将软件设计成由相对独立、单一功能的模块组成的结构。 23. 概要设计的主要任务：确定软件由哪些模块组成及模块之间的关系，即软件功能的分解。 24. 概要设计中，面向数据流的设计方法：可以把数据流图变换成软件结构图。 25. 典型的数据流类型有两种（变换型和事务型） 。 26. 详细设计的主要任务：为每个模块确定实现的算法和局部数据结构，并且用某种选定的表达工具表示 出它们的细节。 27. 详细设计中，过程设计的常见工具有：程序流程图，N-S 方框图，PAD 问题分析图，PDL 伪码。 程序流程图中的主要图形元素： 控制流， 加工步骤， 逻辑条件。 28. 软件测试，其主要过程涵盖了整个软件生命期的过程。 29. 软件测试的目的：发现错误。 30. 测试用例：是为测试设计的数据，包括输入值集和输出值集。 31. 一个好的测试用例，找到迄今为止尚未发现的错误。 32. 软件测试的方法：从是否需要执行被测软件的角度，分为动态测试和静态测试；从功能上，可分为白 盒测试和黑盒测试。 33. 白盒测试：也称为结构测试或逻辑驱动测试，是在程序内部进行，主要用于完成软件内部操作的验证。 34. 白盒测试的主要方法：逻辑覆盖，基本路径测试。 35. 黑盒测试：也称为功能测试或数据驱动测试，检查程序的功能是否符合它的功能说明。 36. 黑盒测试的主要方法：等价类划分法，边界值分析法，错误推测法，因果图。 37. 软件测试的实施分为四个步骤：单元测试，集成测试，验收测试（确认测试） ，系统测试。 38. 单元测试的目的：发现各模块内部可能存在的各种错误。 39. 单元测试的依据：详细设计说明书和源程序。 40. 单元测试的技术：静态分析和动态测试。对动态测试通常以白盒测试为主，辅之以黑盒测试。 41. 集成测试：是测试和组装软件的过程。 42. 集成测试的目的：发现与接口有关的错误。全国计算机等级考试二级公共基础知识点总结 4/5 43. 集成测试的依据：概要设计说明书。 44. 确认测试的目的：检查软件产品是否符合需求定义的过程。 45. 确认测试的主要方法：黑盒测试。 46. 系统测试的目的：在真实的系统工作环境下检验软件是否能与系统正确链接，发现软件与系统需求不 一致的地方。 47. 程序调试：主要在开发阶段。 48. 程序调试的任务：诊断和改正程序中的错误。 49. 程序调试的基本步骤：a.错误定位；b.修改设计，以排除错误；c.回归测试，以防止引进新的错误。 50. 软件调试方法：以静态调试为主，辅之以动态调试。 51. 静态调试：主要指通过人的思维来分析源程序代码和排错。 第四章数据库设计基础 1. 数据库系统（DBS） ，数据库(DB) ，数据库管理系统