文章目录

• 第一章 绪论
• • 软件开发过程
  • 数据结构在计算问题中的用途
  • 算法设计
  • 操作系统
  • 操作系统主要功能
  • 编译原理相关
  • 数据库相关
• 第二章 数据结构
• • 2.1 线性表
  • 2.2 复杂度分析
  • 2.3 分治递归
  • 2.4 树
  • • 树的各种基本概念
    • 二叉树的存储结构
    • 二叉树、满二叉树、完全二叉树
    • 二叉树的遍历
  • 2.5 图
  • • 图的定义及相关术语
    • 图的存储结构
    • 图的遍历
    • 贪心算法与单源最短路径
• 第三章 操作系统
• • 3.1 进程相关
  • • 进程的定义
    • 进程的五状态转换模型
    • 进程的构成与PCB
    • 运行Fork()创建进程
  • 3.2 线程相关
  • • 线程的定义
    • 进程和线程的区别
    • 三类线程（用户级、内核级、混合）
  • 3.3 互斥与同步
  • • 竞争临界资源引起的问题和互斥的条件
    • 掌握信 量方法
    • • 信 量进行互斥和同步
      • 解决生产者消费者问题
    • 进程间通信方式
  • 3.4 程序的装入和链接
  • • 高级语言的源代码转化为进程的三个步骤
    • 静态链接，装入时链接，运行时链接的区别，以及各自的优缺点
    • 绝对装入方式和可重定位装入方式的优缺点
• 第四章 编译原理
• • 4.1 数据类型及其抽象层次
  • 4.2 六种数据类型聚合方式
  • 4.3 语句级控制结构
  • 4.4 定义语言：生成（文法）或识别（语法图）
  • 4.5 文法的分类
  • 4.6 推导与规约，文法与语言，二义性问题
  • 4.7 短语、直接短语、句柄的含义和求法
  • 4.8 编译步骤
  • 4.9 语法分析的两大类别：自下而上和自上而下
  • 4.10 递归下降分析法
  • 4.11 预测分析法
  • 4.12 LR分析法是句柄规约
  • 4.13 语义翻译的概念、作用
  • 4.14 类型检查
  • 4.15 语义翻译
  • 4.16 中间代码的写法：三地址码、四元式
• 第五章 数据库
• • 5.1 数据库基本概念
  • 5.2 模式的体系结构，三种模式
  • 5.3 关系模式的基本概念
  • 5.4 主码与候选码
  • 5.5 关系运算，运算符表达式
  • 5.6 完整性约束，规则、类别等
  • 5.7 SQL语法
  • 5.8 数据库设计理论
  • • 函数依赖，模式分解
    • 范式的概念、如何区分不同的范式
  • 5.9 数据库应用设计方法
  • • 数据库的三种数据模型
    • ER模型的概念、结构及使用其构造数据库的方法
    • 数据库设计的各个阶段及主要工作

第一章 绪论

复习课地址

软件开发过程

1. 问题的理解：清楚问题的输入、要求和输出
2. 算法设计：包括软件架构设计、模块分解、选择具体算法策略、用适当的方式描述和逐步细化算法步骤
3. 数据结构设计：一方面要选择或设计能有效表示和存储应用问题中所涉及的数据对象的数据结构，同时还要选择或设计能支持算法策略实现的数据结构
4. 算法分析：发现有改进完善之处，返回第二步，重新选择或设计算法与数据结构
5. 程序设计：设计具体的数据存储方案、数据结构实现细节、基于某种操作系统设计程序实现细节，在计算机上调试和运行程序
6. 1. 处理机管理
      按照一定的算法把处理机分配给进程（线程)，并对其进行有效的管理和控制
   3. 设备管理
      完成用户进程提出的I/O请求；为用户进程分配其所需的I/O设备；提高CPU和I/O设备的利用率；提高I/O速度；方便用户使用I/O设备

7. 用户接口
   提供友好的用户接口以方便用户使用
   系统调用是用户程序取得操作系统服务的唯一途径
   

8. 不依赖操作系统的编译方式
   

数据库相关

数据库管理系统（DBMS) 是位于用户与操作系统之间的数据管理软件。
数据库在建立、运用和维护时由数据库管理系统统一管理、统一控制。它使用户方便的定义数据和操作数据，并能够保证数据的安全性、完整性、以及多用户对数据的并发使用及发生故障后的数据库恢复。

第二章 数据结构

2.1 线性表

• 线性表的逻辑存储结构

• 线性表的顺序和链式存储结构
  顺序：用一组地址连续的存储单元依次存放线性表中的数据元素
  链式：用一组地址任意的存储单元存放线性表中的数据元素

• 两种方式插入删除操作
  顺序：均为O(n)
  链式：O(1)

• 两种存储结构的优缺点
  顺序适合查找，链式适合插入删除

2.2 复杂度分析

2.3 分治递归

• 分治递归算法思想
  第一步：要求解一个大问题可划分为k个子问题，对这k个子问题进行求解，如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题的规模足够小，很容易求出其解为止
  第二步：将求出的小规模问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解

• 分支法的适用条件

  该问题的规模缩小到一定的程度就可以容易地解决；
  该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
  利用该问题分解出的子问题可以合并为该问题的解；
  该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
  Tips: 如果各个子问题不独立，需要重复的解决公共的子问题，用动态规划更好

• 分治思想求解排序问题
  思想：
  

2.4 树

树的各种基本概念

• 树(Tree)是n(n≥0）个结点的有限集，有且只有一个根结点，其余结点可划分为不同的根的子树
• 树的结点包含一个数据元素及若干指向其子树的分支
• 结点拥有的子树数称为结点的度(Degree)
• 度数为0的结点称为叶子(Leaf)或终端结点
• 度数不为0的结点称为非终端结点或分支结点
• 树的度是树内各结点的度的最大值
• 结点的子树的跟称为该结点的孩子，该结点称为孩子的双亲，同一个双亲的孩子互称兄弟
• 结点的祖先是从根到该结点所经分支上的所有结点，反之，以某结点为根的子树的任意结点都称为该结点的子孙
• 结点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层
• 其双亲在同一层的结点互称为堂兄弟
• 树中结点的最大层次称为树的深度
• 如果树中结点的各子树看成从左到右是有次序的，则称该树为有序树，否则称为无序树
• 森林(Forest)是m(m≥0)棵互不相交的树的集合

二叉树的存储结构

• 顺序存储结构
  用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素；对于一般二叉树
• 链式存储结构
  二叉树的链表中的结点至少包含3个域：数据域和左、右指针域，称之为二叉链表，如若还包含指向双亲结点的指针域则称之为三叉链表
  容易证得，在含有 n n n个结点的二叉链表中有 n + 1 n+1 n+1个空链域，则应将其每个结点于完全二叉树上的结点相对照，存储在一维数组的相应分量中

二叉树、满二叉树、完全二叉树

• 二叉树(Binary Tree)是另一种树型结构，它的特点是每个结点至多只有两棵子树（度小于等于2），并且二叉树的子树有左右之分
• 满二叉树一棵深度为 k k k且有 2 2 2 ^{k k k} 1 -1 /span>1个结点的二叉树
• 完全二叉树深度为 k k k的，有n个结点的二叉树，当且仅当其中每一个结点都与深度为 k k k的满二叉树中编 1至n的结点一一对应

二叉树的遍历

先序中序后序遍历
关键: 递归实现（先序指的是根结点的顺序在先）