第 11 章　公共基础知识

学习目标

这一章对应《二级公共基础知识考试大纲（2025年版）》。这里只整理考试里反复出现的概念。

数据结构研究数据如何组织，以及组织上能做哪些运算。线性结构的元素之间是一对一的关系，例如线性表、栈、队列。非线性结构包括树和图。

栈是后进先出，只能在栈顶插入和删除。队列是先进先出，一端进入、另一端离开。

在二叉树里，叶子结点没有子结点。完全二叉树从左到右逐层填满。满二叉树每一层都是满的。

算法要有输入、输出、有穷性、确定性和可行性。时间复杂度用来比较数据量变大时操作次数的增长速度。二分查找要求序列已经有序，时间复杂度是 O(log n)。顺序查找是 O(n)。冒泡排序、简单选择排序的时间复杂度是 O(n²)。

结构化程序由顺序、选择和循环三种基本结构组成。一个入口、一个出口，避免随意跳转。

面向对象把数据和操作封装在对象里。类是对象的模板。继承让新类沿用已有类的成员。多态允许同一消息在不同对象上有不同表现。

软件生命周期包括可行性研究、需求分析、设计、实现、测试、运行和维护。需求分析要回答系统做什么，设计回答怎么做。

白盒测试根据程序内部结构来设计用例。黑盒测试只看输入和输出是否符合功能，不看内部代码。

数据库用数据库管理系统统一管理。关系数据库用二维表表示数据。行是记录，列是字段。主键用来唯一标识一行，不能重复，也不能为空。

关系运算里，选择是按条件留下行，投影是留下指定列，连接是按共同字段把表接起来。

SQL 中，SELECT 查询，INSERT 插入，UPDATE 修改，DELETE 删除。WHERE 写条件。

E-R 图里，矩形表示实体，椭圆表示属性，菱形表示联系。联系可以是一对一、一对多或多对多。