目录

Chapter1  绪论

1.1 软件开发六步骤（了解）

1.2 操作系统主要功能（了解）

/p>

Chapter2 数据结构与算法

2.1 线性表的逻辑存储结构

2.2 线性表的顺序存储结构

2.3 线性表的链式存储

2.4 两种储存方式的优缺点

2.5 时间复杂度渐近分析（大题）

2.6 分治算法求解排序问题

2.7 树

2.8 二叉树的概念

2.9 二叉树的存储

2.10 二叉树的遍历

2.11 树和二叉树的互换：

2.12 先序和中序遍历恢复二叉树

2.13 图

2.14 图的遍历

2.15 贪心算法

2.16 Dijkstra算法求最短路径

Chapter 3 操作系统

3.1 进程的定义

3.2 进程五状态转换模型

3.3 挂起状态

3.4 进程的构成（了解）

3.5 线程

3.6 进程与线程的区别

3.7竞争临界资源引起的问题

3.8 互斥的条件

3.9 信号量方法

3.10 生产者消费者问题

3.11 进程间的通信

3.12 链接方式

3.13 装入方式（了解）

Chapter 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 语法树

4.13 编译步骤

4.14 词法分析

4.15 语法分析两大类型

4.16 自下而上分析可能遇到的问题

4.17 确定与不确定

4.18 递归下降分析法

4.19 预测分析法

4.20 算符优先分析法

4.21 FIRSTVT集

4.22 LASTVT集

4.23 优先关系表构造方法

Chapter 5  数据库

5.1 数据库基本概念：

5.2 模式的体系结构

5.3 关系模型基本概念

5.4 关系运算

5.5 连接运算

5.6  完整性约束

5.7  函数依赖

5.8 主码与候选码

5.9 模式分解

5.10 范式

5.11 重要例题

5.12 三种数据模型

5.13 E-R模型

5.14 数据库设计阶段

Chapter1  绪论

1.1 软件开发六步骤（了解）

1. 问题的理解
2. 算法设计
3. 数据结构设计
4. 算法分析
5. 程序设计
6. 程序实现

1.2 操作系统主要功能（了解）

Chapter2 数据结构与算法

2.1 线性表的逻辑存储结构

在线性结构中，数据元素之间存在着一对一的关系，其特点是数据元素之间按某种规定存在一个顺序关系。（逻辑结构）

线性表: n个同类型数据元素的有限序列,记为：L= (a1，a2,…，ai,…，an)

L为表名；i为数据元素ai 在线性表中的位序；n为线性表的表长;  n=0 时称为空表；ai的数据类型相同

2.2 线性表的顺序存储结构

基本概念：

用一组地址连续的存储单元依次存放线性表中的数据元素，线性表的起始地址s称作线性表的基地址，数据元素ai的存储位置为：LOC(ai) = LOC(a1) + (i-1)×d 

顺序表的c语言定义：

插入操作：

1.  检查插入位置是否合法，如果合法则继续，否则退出；
2. 判表是否已占满；因为是事先静态地分配空间，可能存在所分配存储空间全部被占用的情况，此时也不能实现插入。
3.  若前面检查通过则数据元素依次向后移动一个位置；为避免覆盖原数据，应从最后一个向前依次移动。
4.  新数据元素放到恰当位置；
5.  表长加1。

        时间复杂度O(n)

删除操作：

1. 检查删除位置是否合法；
2.  若检查通过，数据元素依次向前移动一个位置；
3.  表长减1

2.3 线性表的链式存储

用一组地址任意的存储单元存放线性表中的数据元素。

数据域 (数据元素) + 指针域 (指示后继元素存储位置) =  结点，以“结点的序列”表示线性表 /span>/span> 称作链表

以线性表中第一个数据元素a1的存储地址作为线性表的地址，称作线性表的头指针。有时为了操作方便，在第一个结点之前虚加一个“头结点”，并用链表的头指针指向头结点，称为带头结点的单链表

带或不带头结点的区别：

不带：链表指针存放链表第一个数据元素结点的地址，空链表时该指针域为NULL

带：一个专门的结点，称为头结点，该头结点永远存在，该头结点指针域存放第一个数据元素结点的地址，空链表时L.next= NULL

单链表的定义：

变量定义和使用

• ListNode    n1, n2;  /* 定义2个结点变量*/
• ListNodePtr  p = &n1; /* 定义一个指向结点的指针变量p, 并存放n1的地址(指针) */
• n1.next=&n2;  /* 结点n1的指针域存放结点n2的地址 */
• List  L; //定义一个单链表L

插入操作：

步骤：找到ai-1的位置，构造一个数据域为elem的新结点，将其挂在单链链表上

s->data=elem;

s->next=pre->next;

 pre->next=s;

删除操作:

步骤：首先求得第i-1来源：我不会写BUG