第2章 计算机软件

🟢 基础 | 课程A·计算机应用基础 · 约占理论卷 60%（≈90 分）

2.1 软件基本概念 ★★★

• 软件定义：程序 + 数据 + 相关文档的集合（⚠ 只说"程序"不完整——判断题陷阱）
• 软件分类★★★：
  • 系统软件：管理硬件与软件资源、为应用软件提供运行环境——操作系统、语言处理程序（编译/解释/汇编）、数据库管理系统（DBMS）、系统工具/服务程序（⚠ DBMS 属系统软件高频考点）
  • 应用软件：面向具体应用——办公软件（Office/WPS）、图形图像（PS）、浏览器、即时通信等

2.2 操作系统 ★★★

• 定义：管理计算机硬件和软件资源、控制程序执行、方便用户使用的系统软件（最重要的系统软件；裸机+OS=虚拟机/扩充机器）
• 四大特征★★★：并发性、共享性、虚拟性、异步性（不确定性）
• 五大功能★★★：处理机管理（进程管理）、存储器管理、设备管理、文件管理、作业管理（用户接口）
• 类型 ★★：
  • 批处理系统（成批、无交互、吞吐量大）
  • 分时系统（时间片轮转、交互性强、多用户；Unix 典型）
  • 实时系统（响应及时可靠，实时控制/实时信息处理，如导弹制导、订票）
  • 网络操作系统、分布式操作系统、嵌入式操作系统（手机/家电中，如 Android、iOS、鸿蒙 HarmonyOS、VxWorks）
• 常用操作系统 ★★★：Windows（微软，单用户多任务）、macOS（苹果）、Linux（开源，内核 Linus Torvalds；发行版 CentOS/Ubuntu/红旗）、Android（Google，Linux 内核，开源）、iOS（苹果，闭源）、HarmonyOS 鸿蒙（华为）——开源/闭源、厂商对应关系是高频选择
• 进程：程序的一次执行过程，是资源分配和调度的独立单位；进程三态：就绪→运行→阻塞 ★；线程：CPU 调度的基本单位（进程内多条线程共享进程资源）★

2.3 程序设计语言 ★★★

• 分类★★★：
  • 机器语言：二进制指令，计算机唯一直接识别/执行（依赖机器，不可移植）
  • 汇编语言：助记符，需汇编程序翻译；面向机器的低级语言
  • 高级语言：面向问题/过程/对象，易读易移植——C、C++、Java、Python 等
• 语言处理程序★★★：
  • 汇编程序：汇编语言源程序→机器语言
  • 编译程序（编译器）：高级语言源程序→目标程序（一次翻译、整体执行、执行快；C/C++）
  • 解释程序（解释器）：逐句翻译逐句执行、不生成目标程序、可交互但慢（Python 传统模式）
  • ⚠ 编译 vs 解释对比：是否生成目标程序、执行速度、灵活性的三行对比是高频选择
• 语言组成（数据成分、运算成分、控制成分、传输成分）
• 程序的三种控制结构★★★：顺序、选择（分支）、循环
• 源程序执行方式：编译方式 / 解释方式（同上）
• 常用语言 ★★：C（面向过程，系统开发）、C++（面向对象）、Java（面向对象、跨平台"一次编译到处运行"→字节码+JVM）、Python（解释型、胶水语言、AI 领域主流）、C#、JavaScript（网页脚本）、PHP、Go、SQL（结构化查询语言，数据库）、HTML（⚠ 是标记语言不是程序设计语言——判断题陷阱）

2.4 算法和数据结构 ★★★（理论卷必考）

算法：

• 定义：对特定问题求解步骤的有限描述
• 算法五大特性★★★：有穷性、确定性（无二义）、可行性、有 0 个或多个输入、有 1 个或多个输出（⚠ 输出至少一个——判断题陷阱）
• 算法复杂度★★★：时间复杂度（执行时间增长率，大 O 记法）与空间复杂度（存储空间增长率）；常见量级排序：O(1) < O(log₂n) < O(n) < O(n·log₂n) < O(n²) < O(n³) < O(2ⁿ)；⚠ 与问题规模 n 相关；"算法的优劣与所用计算机无关"

数据结构：

• 定义：相互之间存在特定关系的数据元素的集合
• 逻辑结构★★：线性结构（线性表、栈、队列、串）与非线性结构（树、图）
• 存储结构★★：顺序存储、链式存储、索引存储、散列（哈希）存储
• 线性表★★★：n 个同类型元素的有序序列
  • 顺序存储（顺序表）：地址连续、可随机存取（按序号 O(1) 访问）；插入/删除需移动元素（平均移动 n/2 个，O(n)）
  • 链式存储（链表）：结点=数据域+指针域；顺序存取（须从头遍历）；插删只改指针 O(1)（已定位时）；不要求连续空间
  • 链表分类：线性单链表（单向）、双向链表（前后两个指针）、循环链表（尾指针指回头）；带头结点的意义：操作统一
• 栈（Stack）★★★：后进先出（LIFO）；只允许在栈顶插入（入栈 push）删除（出栈 pop）；应用：函数/递归调用、表达式求值、进制转换、括号匹配、页面后退
• 队列（Queue）★★★：先进先出（FIFO）；队尾入队（rear）、队头出队（front）；应用：打印队列、CPU 任务调度、消息缓冲
• 树★★★：
  • 术语：根结点、叶子结点（度为 0）、结点的度、树的深度（层次）、父/子/兄弟结点
  • 二叉树：每个结点最多 2 棵子树（左子树/右子树，次序不能颠倒）
  • 性质 📐：第 i 层最多 2^(i-1) 个结点；深度为 k 的二叉树最多 2ᵏ−1 个结点；n₀ = n₂ + 1（叶子数=度 2 结点数+1）
  • 满二叉树（每层全满）/ 完全二叉树（编号对应满二叉树，仅缺最下层右侧）
  • 遍历★★★：前序（根左右）、中序（左根右）、后序（左右根）——由中序+前/后序之一可唯一重建二叉树（高频综合题）
  • 二叉树存储结构：顺序存储（数组按下标存，适合完全二叉树）；链式存储（二叉链表：data+lchild+rchild，最常用）
  • 二叉排序树（BST）：左<根<右，中序遍历得升序序列
• 图★：顶点+边；有向图/无向图；度（入度/出度）；连通图；存储：邻接矩阵（n×n 矩阵，稠密图，空间 O(n²)）/ 邻接表（数组+链表，稀疏图，O(n+e)）；遍历：深度优先 DFS / 广度优先 BFS
• 查找★★：顺序查找（任意表，ASL 长）；折半查找（二分查找）：要求有序 + 顺序存储，mid=(low+high)/2，比较次数 ⌈log₂(n+1)⌉（⚠ 两个前提条件是高频判断）
• 排序★★★：

算法	平均复杂度	稳定性	要点
冒泡排序	O(n²)	稳定	相邻比较交换，每趟最大沉底
简单选择排序	O(n²)	不稳定	每趟选最小放前
直接插入排序	O(n²)	稳定	把元素插入前面有序区
快速排序	O(nlog₂n)	不稳定	基准分区，平均最快
堆排序	O(nlog₂n)	不稳定	建堆+调整
归并排序	O(nlog₂n)	稳定	两两合并

2.5 软件工程基础 ★★

• 软件工程：用工程化方法开发维护软件（应对"软件危机"）
• 软件生命周期★★：问题定义→可行性研究→需求分析→软件设计（总体/概要设计+详细设计）→编码→软件测试→运行维护（维护是持续时间最长、花费最高的阶段）
• 结构化设计方法：自顶向下、逐步求精、模块化
  • 总体设计（概要设计）：模块划分、模块调用关系（"做什么"结构）
  • 详细设计：模块内部算法与数据结构（"怎么做"）
  • 模块独立性好 = 高内聚、低耦合 ★★
• 面向对象方法（OOA 分析 / OOD 设计）★★：类（抽象模板）/对象（实例）；三大特性：封装、继承、多态；UML统一建模语言（详见技能三）
• 软件测试★★★：
  • 目的：发现错误（不能证明无错）
  • 白盒测试：看代码内部逻辑——逻辑覆盖（语句/判定/条件/路径覆盖）
  • 黑盒测试：只看功能输入输出——等价类划分、边界值分析
  • 步骤：单元测试→集成测试→确认测试（验证）→系统测试；α 测试（用户在开发环境）/β 测试（用户在实际环境）
• 程序调试：定位并改正错误；静态调试（不运行：走查、代码审查）/ 动态调试（运行：断点、单步、打印中间结果）

---