计算机二级公共基础知识 精简笔记|考前速记

第 1 章 数据结构与算法

1.1 算法

算法：解决问题的清晰指令

四大特征：可行性、确定性、有穷性、足够情报

两要素：数据运算 + 控制结构

复杂度：

时间复杂度：计算工作量

空间复杂度：所需内存

两者无必然关系

1.2 数据结构

逻辑结构：数据间逻辑关系

存储结构：顺序、链式、索引、散列

线性结构：一个根、每个节点最多一个前驱一个后继

非线性结构：不满足线性就是非线性（树、图）

1.3 线性表

顺序存储：空间连续、按逻辑顺序存放

插入 / 删除：最坏情况要移动全部元素

1.4 栈与队列

栈：先进后出（后进先出），只在栈顶操作

队列：先进先出，队尾入、队头出

循环队列：头尾指针循环走；front=rear 可能空也可能满

1.5 线性链表

节点 =数据域 + 指针域

存储空间可连续可不连续

单链表、双向链表、循环链表都属于线性结构

1.6 树与二叉树（必考）

二叉树：最多两个子树，可为空

必背性质：

第 k 层最多 2^(k-1) 个节点

深度 m 最多 2^m -1 个节点

叶子节点数 = 度 2 节点数 +1

完全二叉树深度：⌊log₂n⌋ +1

满二叉树 → 一定是完全二叉树

三种遍历（必考）：

前序：根 → 左 → 右

中序：左 → 根 → 右

后序：左 → 右 → 根

1.7 查找

顺序查找：最坏 n 次

二分查找：必须有序 + 顺序存储，最坏 log₂n 次

1.8 排序（必背复杂度）

冒泡、简单插入、简单选择：最坏 n(n-1)/2

快速排序：最坏 n(n-1)/2，平均最快

堆排序：最坏 O(nlog₂n)

第 2 章 程序设计基础

结构化程序设计

原则：自顶向下、逐步求精、模块化、少用 goto

三种结构：顺序、选择、循环

一个入口、一个出口

面向对象

对象：具体实体

类：对象的集合

消息：对象间通信

继承：复用已有类

多态：同一消息不同响应

第 3 章 软件工程基础

软件与软件危机

软件 = 程序 + 数据 + 文档

软件生命周期：定义→开发→维护

开发阶段：设计→实现→测试

结构化分析

工具：DFD 数据流图、数据字典、判定树 / 表

数据字典是核心

软件设计

原则：高内聚、低耦合

概要设计 + 详细设计

软件测试

目的：发现错误

白盒：测内部逻辑（语句、路径、逻辑覆盖）

黑盒：测功能（等价类、边界值、错误推测）

步骤：单元测试→集成测试→确认测试→系统测试

程序调试

任务：诊断并改错

方法：强行排错、回溯、原因排除

第 4 章 数据库设计基础

数据库系统

DBMS 是核心，属于系统软件

特点：共享高、冗余低、独立性高

三级模式：外模式→概念模式→内模式

数据模型

E-R 模型：实体、属性、联系（1:1 / 1:N / M:N）

关系模型：用二维表表示

键：唯一标识元组的最小属性集

关系代数

基本运算：选择、投影、笛卡尔积

常用：并、交、差、自然连接

数据库设计

流程：需求分析→概念设计→逻辑设计→物理设计

二级高频必背口诀

栈：先进后出；队列：先进先出

叶子 = 度 2 +1

前中后遍历：根位置不同

高内聚低耦合

白盒测逻辑，黑盒测功能

自然连接：按共有属性等值连接

最后，预祝大家二级考试顺利，愿所有努力都不被辜负，选择题全会、操作题全对，稳稳上岸，一次通关！