掌握程序设计语言（Programming Languages）基础知识与基本成分，汇编语言、编译程序、解释程序的基本原理。

一、程序语言基础

• 低级语言：机器语言（二进制0/1组成的机器指令序列）、汇编语言（使用助记符表示机器指令，需要通过汇编器转换为机器语言）
• 高级语言：接近自然语言的语法，需要编译器或解释器转换为机器语言；如 C、Java、Python 等。

1.1 程序设计语言的分类

1. 按抽象级别

一、面向对象基础概念

• 类（Class）：具有相同属性和方法的对象的抽象模板。
• 对象（Object）：类的实例，包含具体属性和行为。
• 继承（Inheritance）：子类继承父类的属性和方法，实现代码复用（如Java中的extends）。
• 封装（Encapsulation）：隐藏内部细节，通过接口访问对象（如私有属性+公有方法）。
• 多态（Polymorphism）：同一方法在不同对象中有不同实现（通过重写和接口实现）。
• 抽象（Abstraction）：提取关键特征，忽略非本质细节（如抽象类、接口）。

二、面向对象设计原则（SOLID原则）

1. 单一职责原则（SRP）：一个类只负责一个功能领域的变化。
2. 开闭原则（OCP）：对扩展开放，对修改关闭（通过抽象和继承实现）。
3. 里氏替换原则（LSP）：子类必须能替换父类，且不影响程序正确性。
4. 接口隔离原则（ISP）：客户端不应依赖不需要的接口，拆分臃肿接口。
5. 依赖倒置原则（DIP）：高层模块不依赖低层模块，二者依赖抽象（如面向接口编程）。

三、设计模式

• 创建型模式：用于对象创建的过程
  • 单例模式、工厂方法模式、抽象工厂模式、建造者模式(生成器模式)、原型模式
• 结构型模式：用于把类或对象通过某种形式结合在一起，构成某种复杂或合理的结构
  • 适配器模式、装饰者模式、代理模式、外观模式、桥接模式、组合模式、享元模式(过滤器/标准模式)
• 行为型模式：用于解决类或对象之间的交互，更合理的优化类或对象之间的关系
  • 责任链模式、命令模式、迭代子模式(迭代器模式)、观察者模式、中介者模式、解析器模式、状态模式、空对象模式、策略模式、模板模式、访问者模式、备忘录模式、
• 常用设计模式及应用场景：

  模式类型	模式名称	核心思想	典型应用场景
  创建型	工厂方法	由子类决定实例化哪个类	动态创建对象
  	抽象工厂	创建相关对象家族	跨平台UI组件库
  	单例（Singleton）	确保一个类只有一个实例	数据库连接池、配置管理器
  结构型	适配器（Adapter）	转换接口使不兼容的类协同工作	旧系统接口适配新需求
  	装饰器（Decorator）	动态添加职责	Java I/O流、GUI组件增强
  行为型	观察者（Observer）	对象间一对多的依赖关系	事件处理系统（如消息通知）
  	策略（Strategy）	封装算法，使其可互换	排序算法、支付方式选择

四、UML建模技术

UML（Unified Modeling Language，统一建模语言）是面向对象系统分析与设计的标准化建模工具。

数据库系统组成:

• 数据库（DB）：结构化数据的集合。
• 数据库管理系统（DBMS）：管理数据库的软件（如MySQL、Oracle）。
• 数据库系统（DBS）：DB + DBMS + 应用程序 + 用户。

数据库管理系统利用日志文件来进行事务故障恢复和系统故障恢复。在事务处理过程中，把事务开始、事务结束以及对数据库的插入、删除和修改的每一次操作写入日志文件。 当系统正常运行时，按一定的时间间隔，把数据库缓冲区内容写入数据文件；一旦发生故障，DBMS的恢复子系统利用日志文件撤销事务对数据库的改变，回退到事务的初始状态。

一、数据库系统基础

1. 数据库模型
   • 关系模型：核心模型，用二维表（关系）表示数据，核心概念包括：
     • 关系（表）、属性（列）、元组（行）、候选码（唯一标识元组的属性集）、主码（选定的候选码）、外码（关联其他表主码的属性）。
   • 其他模型：层次模型（树形结构）、网状模型（图结构），了解其特点即可。
2. 数据库三级模式
   • 外模式（用户视图）、模式（逻辑结构）、内模式（物理存储），通过两级映像实现数据独立性（逻辑独立性与物理独立性）。

二、关系数据库与SQL

1. 关系代数
   • 基本运算：选择（σ）、投影（π）、并（∪）、差（−）、笛卡尔积（×）。
   • 扩展运算：连接（⋈）、自然连接、除运算（÷）、交（∩）等。
   • 考试重点：根据关系代数表达式写出等价SQL语句。
2. SQL语言
   • DDL（数据定义语言）：CREATE TABLE, ALTER TABLE, DROP TABLE。
   • DML（数据操纵语言）：SELECT（重点）、INSERT, UPDATE, DELETE。
   • DCL（数据控制语言）：GRANT, REVOKE。
   • 高级查询：分组（GROUP BY）、聚合函数（COUNT, SUM, AVG）、子查询、连接查询（内连接、左外连接、右外连接）。
   • 索引：CREATE INDEX，理解B树、哈希索引的适用场景。
3. 完整性约束
   • 实体完整性：主键（PRIMARY KEY）非空且唯一。
   • 参照完整性：外键（FOREIGN KEY）引用有效值。
   • 用户定义完整性：如CHECK约束。

三、数据库设计

1. E-R模型：全称实体-关系模型（Entity-Relationship Model），用于描述现实世界中的对象之间的关系。
   • E-R模型是一种图形化的表示方式，通常使用矩形表示实体，椭圆表示属性，菱形表示关系(联系)，箭头表示关系的方向，线条表示属性或关系的类型。
   • 
2. ER模型与关系模式转换
   • ER图要素：实体、属性、联系（1:1、1:N、M:N）。
   • 转换规则：实体→表，属性→字段，多对多联系→独立表。
   • 考试重点：根据ER图设计关系模式，解决冗余和异常问题。
3. 规范化理论
   • 函数依赖（Functional Dependency, FD）:
     • 在一个关系模式\( R(U) \)中，\( U \)是属性集，\( X \)和\( Y \)是\( U \)的子集。如果对与\( R \)的任意两个元组\( t{1},t{2} \)，当它们在\( X \)上的属性值相同时则在\( Y \)上必相同，则称\( X \)函数决定\( Y \)，记为 \( X \rightarrow Y \)。

       类型	定义	示例
       完全函数依赖	\( Y \) 完全依赖于 \( X \)，即 \( X \rightarrow Y \)，且 \( X \) 的任意真子集无法决定 \( Y \)。	\( (\text{学号}, \text{课程号}) \rightarrow \text{成绩} \)（成绩由学号和课程号共同决定）
       部分函数依赖	\( Y \) 部分依赖于 \( X \)，即存在 \( X \) 的真子集 \( X' \) 满足 \( X' \rightarrow Y \)。	若 \( \text{学号} \rightarrow \text{姓名} \)，则 \( (\text{学号}, \text{课程号}) \rightarrow \text{姓名} \) 是部分依赖
       传递函数依赖	若 \( X \rightarrow Y \)，\( Y \rightarrow Z \)，且 \( Y \nrightarrow X \)，则 \( X \rightarrow Z \) 是传递依赖。	学号 → 所属学院，所属学院 → 院长，则学号 → 院长 是传递依赖

   • 范式（Normal Form）：

     范式	要求	解决的问题
     1NF	原子性(属性不可再分)	消除重复字段
     2NF	消除非主属性对候选码的部分依赖	减少数据冗余（将部分依赖的属性单独建表）
     3NF	消除非主属性对候选码的传递依赖	避免更新异常（将传递依赖的属性拆分到新表）
     BCNF	消除主属性对候选码的部分/传递依赖（所有决定因素必为候选码）	更强的3NF

   • 判断与分解：给定关系模式，判断范式级别，并通过投影分解达到更高范式。
   • 闭包计算：求属性集 \( X \) 在函数依赖集 \( F \) 下的闭包 \( X^+ \)，即所有能被 \( X \) 决定的属性集合。
4. 考试高频题型与解法
   1. 判断候选码
      • 步骤：
        1. 找出所有可能的候选码（最小属性集能决定所有属性）。
        2. 利用闭包计算验证候选码是否满足 \( X^+ = U \)。
      • 示例：
        关系模式 \( R(A,B,C,D) \)，函数依赖集 \( F = \{ A \rightarrow B, B \rightarrow C, D \rightarrow B \} \)，求候选码。
        答案：候选码为 \( AD \)（因为 \( AD^+ = ABCD \)）。
   2. 判断范式级别
      • 步骤：
        1. 判断是否满足1NF（属性原子性）。
        2. 找候选码，判断是否存在部分依赖（不满足2NF）或传递依赖（不满足3NF）。
        3. 检查是否所有决定因素均为候选码（满足BCNF）。
      • 示例：
        关系模式 \( R(学号, 课程号, 成绩, 姓名) \)，函数依赖集 \( F = \{ (\text{学号}, 课程号) \rightarrow 成绩, 学号 \rightarrow 姓名 \} \)。
        答案：候选码为 \( (\text{学号}, 课程号) \)，存在非主属性“姓名”对候选码的部分依赖，故仅满足1NF。
   3. 模式分解
      • 目标：消除冗余和异常，满足更高范式。
      • 原则：
        • 保持函数依赖（分解后的子模式函数依赖集覆盖原依赖）。
        • 无损连接（分解后的表通过自然连接可恢复原表）。
      • 示例：将上述示例分解为2NF：
        • \( R1(\text{学号}, 课程号, 成绩) \)（满足2NF）。
        • \( R2(\text{学号}, 姓名) \)（满足2NF）。
   4. 典型例题
      • 题目：关系模式 \( R(A,B,C,D) \)，函数依赖集 \( F = \{ A \rightarrow B, B \rightarrow C, C \rightarrow D \} \)，判断其最高范式级别。
      • 解析：
        • 候选码为 \( A \)（\( A^+ = ABCD \)）。
        • 非主属性 \( B, C, D \) 均传递依赖于候选码 \( A \)，故仅满足2NF（未消除传递依赖）。
      • 答案：2NF。

四、事务与并发控制

1. 事务ACID特性
   • 原子性（Atomicity）：事务要么全执行，要么全不执行。
   • 一致性（Consistency）：事务前后数据库状态一致。
   • 隔离性（Isolation）：并发事务互不干扰。
   • 持久性（Durability）：事务提交后结果永久保存。
2. 并发问题
   • 丢失更新：两个事务同时修改同一数据，后提交的覆盖先提交的。
   • 脏读：读取到未提交的数据。
   • 不可重复读：同一事务内两次读取结果不同（数据被修改）。
   • 幻读：同一事务内两次查询结果集不同（数据被插入/删除）。
3. 封锁协议
   • 共享锁（S锁）：读锁，允许多事务同时读取。
   • 排他锁（X锁）：写锁，独占数据。
   • 两段锁协议（2PL）：事务分为加锁阶段和解锁阶段，避免死锁。
   • 隔离级别：读未提交、读已提交（解决脏读）、可重复读（解决不可重复读）、串行化（解决幻读）。
4. 故障与恢复
   • 日志技术：Undo（撤销未提交事务）、Redo（重做已提交事务）；
   • 检查点机制：减少恢复时间。

五、其他高频考点

1. 视图（View）
   • 作用：简化查询、数据安全（隐藏敏感字段）。
   • 更新限制：视图的更新需满足特定条件。
2. 存储过程与触发器
   • 存储过程：预编译的SQL代码块，提高执行效率。
   • 触发器：由事件（如INSERT、UPDATE）自动触发的特殊存储过程。
3. 分布式数据库与NoSQL
   • 分布式数据库：数据分片存储，支持水平扩展、CAP理论（一致性、可用性、分区容忍性）。
   • NoSQL类型：键值存储（Redis）、文档数据库（MongoDB）、列族数据库（HBase）、图数据库（Neo4j）。
   • 大数据技术
     • Hadoop：分布式存储（HDFS）与计算（MapReduce）。
     • Spark：内存计算，适合迭代分析。
4. 其他
   1. SQL优化：避免全表扫描（使用索引）、优化子查询。
   2. 事务隔离级别：读未提交、读已提交、可重复读、串行化。
   3. 索引设计：B+树索引、哈希索引的适用场景。
   4. 数据库安全：角色权限管理、SQL注入防范。

软件工程涵盖了软件开发的全生命周期、方法、模型、工具和原则。 软件生命周期：需求分析、设计、编码、测试、维护。

一、软件开发模型

软件开发模型：是指开发软件的过程中所采用的一种规范化方法或框架。常见的软件开发模型：

一、计算机组成（Computer Organization）

计算机系统是由硬件和软件两大部分组成的复杂系统，它们协同工作以完成各种任务。硬件是计算机的物理部分，软件是计算机的程序和数据（包括操作系统和应用软件）。

一、进制及其转换

1.1 常见进制

• 二进制（Binary）：由0和1组成，基数为2；位权：\(\ldots, 2^2, 2^1, 2^0 \)。
• 八进制（Octal）：由0-7组成，基数为8；位权：\(\ldots, 8^2, 8^1, 8^0 \)。
• 十进制（Decimal）：由0-9组成，基数为10；位权：\(\ldots, 10^2, 10^1, 10^0 \)。
• 十六进制（Hexadecimal）：由0-9和A-F组成，基数为16；位权：\(\ldots, 16^2, 16^1, 16^0 \)。

1.2 进制转换

• 二进制转十进制： 按位权展开，逐位相加。
  • 例如：1011(二进制) = $$ \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 \times 2^3 & 0 \times 2^2 & 1 \times 2^1 & 1 \times 2^0 \\ \end{bmatrix} $$ = 8 + 0 + 2 + 1 = 11(十进制)。
• 八进制转十进制： 按位权展开，逐位相加。
  • 例如：127(八进制) = $$ \begin{bmatrix} 1 & 2 & 7 \\ 1 \times 8^2 & 2 \times 8^1 & 7 \times 8^0 \\ \end{bmatrix} $$ = 64 + 16 + 7 = 87(十进制)。
• 十六进制转十进制： 按位权展开，逐位相加。
  • 例如：1A3(十六进制) = $$ \begin{bmatrix} 1 & A & 3 \\ 1 \times 16^2 & 10 \times 16^1 & 3 \times 16^0 \\ \end{bmatrix} $$ = 256 + 160 + 3 = 419(十进制)。
• 十进制转二进制、八进制、十六进制：除基数取余，余数逆序。

• 二进制转八进制、十六进制：从右向左将二进制数分组，对于八进制每3位一组转换，对于十六进制每4位一组转换。
  • 例如：10110001(二进制) = 010 110 001 = 261(八进制)。
  • 例如：10110001(二进制) = 1011 0001 = B1(十六进制)。

1.3 浮点数进制转换

• R进制：基数为R；位权：\(\ldots, R^2, R^1, R^0, R^{-1}, R^{-2}, \ldots \)。
• R进制转十进制： 按位权展开，逐位相加。
  • 例：127.1(八进制)= $$ \begin{bmatrix} 1 & 2 & 7 & 1 \\ 1 \times 8^2 & 2 \times 8^1 & 7 \times 8^0 & 1 \times 8^{-1} \\ 1 \times 64 & 2 \times 8 & 7 \times 1 & 1 \times \left(\frac{1}{8}\right)^{1} \\ \end{bmatrix} $$ = 64+16+7+0.125 =87.125(十进制)。
• 十进制转R进制：整数部分-除以基数取余,余数逆序；小数部分-乘以基数取整,整数正序。
  • 例：0.625(十进制)= $$ \left[ \begin{array}{l} 0.625 \times 2 = 1.25 & 取1，剩余0.25 \\ 0.25 \times 2 = 0.5 & 取0，剩余0.5 \\ 0.5 \times 2 = 1.0 & 取1，剩余0.0 \\ \end{array} \right] $$ = 0.101(二进制)。
• 二进制转八进制、十六进制：小数点开始,向左和向右分组，对于八进制每3位一组转换，对于十六进制每4位一组转换。
  • 例如：10110001.0111(二进制) = 010 110 001.011 100 = 261.34(八进制)。
  • 例如：10110001.0111(二进制) = 1011 0001.0111 = B1.7(十六进制)。

二、计算机内数据表示

2.1 基本单位

• 位（Bit）：最小数据单位，0或1。
• 字节（Byte）：8位组成1字节，可表示范围 00000000（0）到 11111111（255）。

2.2 数值数据的表示

计算机内部使用二进制表示数据，数值表示方式有：