数据结构,操作系统重要概念整理

数据结构：

一、重点知识点

1. 了解算法的时间复杂度的概念，会求一个算法的时间复杂度；

2. 了解线性表的概念，掌握线性表的顺序表示与链式表示；

3. 掌握链表的增、删、查、改等基本操作；

4. 理解栈和队列的基本概念；

5. 掌握循环队列的判空等基本操作；

6. 掌握栈在括号匹配和递归中的应用；

7. 了解数组的概念；

8. 理解矩阵的压缩存储；

9. 了解树和二叉树的基本概念；

10. 掌握二叉树的遍历、线索二叉树等相关算法；

11. 掌握二叉排序树、平衡二叉树以及Huffman 树；

12. 了解图的基本概念；

13. 理解图的的邻接矩阵法存储与邻接表法存储的类型定义；

14. 掌握图的遍历算法；

15. 掌握图的最小生成树算法、最短路径以及拓扑排序应用及算法；

16. 了解查找的基本概念；

17. 理解顺序查找方法与折半查找方法；

18. 理解B 树的概念与基本操作；

19. 掌握散列表的概念、构造以及处理冲突的方法；

20. 了解排序的基本概念；

21. 掌握几种排序算法；

22. 理解几种排序算法性能优劣的比较；

二、重要概念

一、概述

1. 数据：信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

2. 数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

3. 数据项：构成数据元素的不可分割的最小单位。

4. 数据对象：性质相同的数据元素的集合，是数据的一个子集。

5. 数据类型：一个值的集合和定义在此集合上一组操作的总称。、

6. 时间复杂度：算法中所有语句在算法中重复执行的次数。

二、线性表

1. 线性表：具有相同数据类型的n 个数据元素的有限序列。

2. 顺序表：用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

3. 单链表：通过一组任意的存储单元来存储线性表中的数据元素。

三、栈和队列

1. 栈：只允许在一端进行插入或删除操作的线性表。

2. 顺序栈：利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针指示当前栈顶的位置。

3. 共享栈：利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

4. 队列：只允许在表的一端进行插入，而在表的另一端进行删除，这种操作受限的线性表。

5. 循环队列：将顺序队列假想为一个环状的空间，即把存储队列元素的表从逻辑上看成一个环。

6. 数组:是由n(n>1)个相同类型的数据元素构成的有限序列。

7. 压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配存储空

间。

8. 特殊矩阵：具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。

9. 稀疏矩阵：矩阵元素个数s 相对于矩阵中非零元素个数t 来说非常多，即s>>t的矩阵。

四、树和二叉树

(4) 树：N 个结点的有限集合.

(5) 度：树中一个结点的子节点个数。

(6) 叶子结点：度为0的结点。

(7) 祖先结点：根A 到结点k 的唯一路径上的任意结点，称为k 的祖先结点。

(8) 二叉树：是n 个结点的有限集合：(1)或者为空二叉树，即n=0;(2)或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左右子树又分别为一棵二叉树。

(9) 满二叉树:一棵高度为h, 并且含有2h-1个结点的二叉树。

(10) 完全二叉树：设一个高度为h, 有n 个结点的二叉树，当且仅当其每一个结点都与高度为h 的满二叉树中编号为1-n 的结点一一对应时。

(11) 二叉排序树：一棵二叉树或者为空二叉树，或者是具有如下性质的二叉树：左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字。左右子树又各是一棵二叉排序树。

(12) 平衡二叉树：树上任一节点的左子树和右子树的深度之差不超过1。

(13) 哈夫曼树：又称最优二叉树，在含有N 个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树。

(14) 前缀编码：没有一个编码是另一个编码的前缀。

(15) 树的带权路径长度：从根节点到任意结点的路径长度与该结点上权值的乘积。

(16) 树的路径长度：从根节点到每一个结点路径长度之和。

五、图

1. 完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。(有向/无向)

2. 连通分量：无向图中的极大联通子图。

3. 强连通图：在有向图中，若从顶点v 到顶点w 和从顶点w 到顶点v 之间都有路径，则称这两个顶点是强连通的。若图中任何顶点都是强连通的，这称此图为强连通图。（强连通分量类推之）

4. 邻接矩阵：所谓邻接矩阵，就是用一个一维数组存储图中顶点信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组成为邻接矩阵。

5. 邻接表：适应于稀疏矩阵，可以画图描述。

6. 生成树：包含图中全部顶点的一个极小连通子图。

7. 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。

8. 简单回路：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。

9. 有向树：有一个顶点的入度为0，其余顶点的入度均为1的有向图。

10. 最小生成树：对于一个带权连通无向图G=(V,E),生成树不同，每棵树的权也可能不同。设R 为G 的所有生成树的集合，若T 为R 中边的权值之和最小的那棵生成树，则T 称为G 的最小生成树。

11. Prim 算法描述

12. Kruskal 算法描述

13. 最短路径：在带权图中，把从一个顶点V 到图中其余人一个顶点Vi 的一条路径（可能不止一条）上所有能路过边的权值之和定义为带权路径长度，把带权路径长度最短的那条成为最短路径长度。

14. Dijkstra 算法求单源最短路径算法描述

15. Floyd 算法求个顶点间最短路径算法描述

16. 有向无环图：一个有向图中不存在环。

17. 拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序。(1)每个顶点出现且只出现一次。(2)若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到A 的路径。

18. 关键路径：从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。

六、查找

1. 查找：在数据集合中寻找满足某种条件的数据元素的过程。

2. 查找表：由同一类型的数据元素组成，用于查找的数据集合。

3. 平均查找长度：在查找过程中，进行关键字的比较次数的平均值。

4. 折半查找：适用于有序的顺序表，首先将给定值key 与表中中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置，若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中。缩小范围，继续查找。

5. B 树：即多路平衡查找树，B 树中所有结点的孩子结点数的最大值称为B 树的阶。

6. 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数。

7. 散列表：根据关键字而直接进行访问的数据结构，建立了关键字和存储地址之间的一种直接映射关系。

8. 装填因子：定义一个散列表的装满程度。

七、排序

1. 算法的稳定性：如果待排序表中有两个元素R1，R2, 其对应的关键字为key1=key2，且在排序前R1在R2前面，如果使用某一排序算法排序后，R1仍然在R2的前面，则称这个排序算法是稳定的。

2. 希尔排序：先将待排序表分割成若干个形如L[i,i+d,i+2d，,,i+kd]的子表，分别进行直接插入排序，当整个表中元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

3. 快速排序：基于分治的思想，假设划分算法已知，先对表进行划分，而后对两个表调用同样的排序操作。

4. 选择排序：每一趟在后面n-i+1个待排序元素中选取关键字最小的元素，作为有序子序列的第i 个元素，知道第n-1趟做完，待排序列只剩1个，就不用再选了。

5. 堆排序：在排序过程中，将L[1...N]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大的元素。

6. 归并排序：将两个或两个以上的有序表组合成一个新的有序表。

基数排序：采用多关键字排序思想，借助“分配”和“收集”两种操作对单逻

操作系统

一、重点知识点

1. 了解几种不同的操作系统的基本概念(批处理、分时、实时) ；

2. 了解中断、异常以及系统调用等基本概念；

3. 了解操作系统的目标与功能；

4. 了解进程与线程的概念；

5. 理解进程与线程的比较；

6. 掌握进程调度的几种算法；

7. 理解进程的状态与转换；

8. 掌握死锁的概念、处理死锁的策略、死锁的预防、死锁的避免与死锁的检测和解除；

9. 理解覆盖与交换的区别与联系；

10. 理解页式存储管理方式、段式存储管理方式以及段页式存储管理方式；

11. 理解请求分页管理方式；

12. 理解虚拟存储器的基本概念；

13. 掌握几种常见的页面置换算法；

14. 理解抖动、工作集的概念；

15. 理解文件、目录、目录结构等的概念；

16. 理解文件的逻辑结构、目录结构；

17. 理解文件系统的层次结构；

18. 掌握磁盘调度算法；

19. 理解磁盘的结构与管理；

20. 了解I/0控制方式；

21. 理解高速缓存与缓冲区的概念；

22. 理解I/O调度的概念；

23. 掌握SPOOLing 技术的概念以及相关原理；

二、名词解析

一、操作系统及其相关概念

1. 操作系统（OS ）：控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供给用户和其它软件方便的接口和环境的程序集合。

2. 分时操作系统：多个用户通过终端同时共享一台主机，这些终端连接在主机上，用户可以同时与主机进行交互操作而互不干扰。

3. 并发：两个或多个事件在同一时间间隔内发生。

4. 虚拟：把一个物理上的实体变为若干个逻辑上的对应物。

5. 中断：也称为外中断，来自CPU 执行指令以外的事件的发生，如设备发出的I/O中断，表示设备输入/输出处理已经完成，希望处理机能够向设备发下一个输入/输出请求，同时让完成输入/输出后的程序继续运行。

6. 异常：也称为内中断，指源自CPU 执行指令内部的事件，如程序的非法操作码，地址越界，算术溢出，虚存系统的却也以及专门的陷入指令等引起的事件。

7. 系统调用：用户在程序中调用操作系统所提供的一些子功能，系统调用可以被看做是特殊的公共子程序。

8. 特权指令：指有特殊权限的指令，这类指令只能用于操作系统或其它系统软件，不直接提供给用户使用，只能运行在核心态下。

9. 访管指令：一条可以在用户态下执行的指令。

10. 访管中断：在用户程序中，因要求操作系统提供服务而有意识的使用访管指令，从而产生一个中断时间，将操作系统转换为核心态的中断。

二、进程管理

六、进程：进程实体的运行过程，是系统进行资源分配和调度的独立单位。

七、进程控制块：进程存在的唯一标志，将程序变成可并发执行的进程。

八、调度：实现进程的并发执行。

九、线程：线程是程序中一个单一的顺序控制流程。进程内一个相对独立的、可调度的执行单元，是系统独立调度和分派CPU 的基本单位，运行中的程序的调度单位。（这是百度上的概念，王道上没有终结，言之合理即可）

十、作业调度：即高级调度，按一定原则从外存上处于后备状态的作业中挑选一

个（或多个）作业，给他们分配内存、输入/输出设备等必要的资源，并建立相应的进程，以使他们获得竞争处理机的权利。

十一、中级调度：即内存调度，为了提高内存利用率和系统吞吐量。

十二、进程调度：即低级调度，按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。

十三、临界资源：一次仅允许一个进程使用的资源。

十四、原语：完成某种功能且不被分割不被中断执行的操作序列，通常可以由硬件来实现完成不被分割执行特性的功能。

十五、管程：由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块。

十六、死锁：多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将无法向前推进。

十七、饥饿：进程在信号量内无穷等待的情况。

十八、银行家算法（尝试描述）

三、内存管理

1. 静态链接：在运行之前，先将各目标模块及他们所需的库函数链接成一个完整的可执行状态，以后不再拆分。

2. 装入时动态链接：将用户程序编译后说得到的一组目标模块，在装入内存时，采用边装入边链接方式。

3. 运行时动态链接：对某些目标模块的链接，实在程序执行中需要该目标模块时，才对他进行链接。

4. 逻辑地址空间：面向用户和程序员的地址空间。

5. 物理地址空间：内存中物理单元的集合，是地址转换的最终地址，进程在运行时执行指令和访问数据组以后都用通过物理地址来存取主存。

6. 首次适应算法：空闲分区按容量递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。

7. 最佳适应算法：空闲分区按容量递增形成分区链，找到第一个能满足要求的空闲分区。

8. 最坏适应算法：空闲分区以容量递减的次序链接，找到第一个能满足要求的空

闲分区。

9. 循环首次适应算法：由首次适应算法演变而来，分配内存时从上次查找结束的位置开始继续查找。

10. 块表：用来存放当前访问的若干页表项，以加快地址转换的过程的一种具有并行查找能力的高速缓冲存储器。

11. 虚拟设备：通过某种虚拟技术，将一台物理设备变换成若干台逻辑设备，从而实现多个用户对该物理设备的同时分享。

12. SPOOLING 技术：被称作假脱机操作，在主机的直接控制下利用多道程序技术模拟脱机输入时和输出时的外围控制机的功能。

13. 最佳置换算法：选择以后永不使用的页面将其淘汰。

14. 最近最久未使用算法：选择最近最长时间未被访问过的页面予以淘汰。

15. Belady 异常：采用FIFO 算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的现象。

16. CLOCK 算法：为每个页设置一位访问位，再将内存中的所有页面通过链接指针链成一个循环队列，当某页被访问时，其访问位由硬件置1，然后顺序检查循环队列中的各个页，如果其访问位为0，就选择该页换出并将替换指针指向下一个页面，若访问位为1，则将其置为0，并继续向下查找。

17. 改进型CLOCK 算法：从上一次位置开始扫描，首先寻找未被访问和修改的页面。

14. 驻留集：某段时间间隔内，进程要访问的页面的集合。

15. 抖动：页面置换算法选择不当，造成的频繁的页面调度行为。

四、文件管理

1. 文件：具有文件名的一组相关信息的集合。

2. 文件系统：操作系统中与文件管理有关的那部分软件，以及被它们管理的文件和文件属性的集合。

3. 数据项：文件系统中最低级的数据组织形式，分为基本数据项和组合数据项。

4. 记录：一组相关的数据项的集合，用于描述一个对象在某方面的属性。

5. 文件目录：为实现“按名存取”，必须建立文件名与辅存空间中物理地址的对应关系，体现这种对应关系的数据结构称为文件目录。

6. 目录项：文件控制块与文件一一对应，而其中的每一个文件控制块被称为目录项。

7. 目录结构：文件目录的组织方式，它将直接关系到文件的存取速度以及文件的共享性和安全性。

8. 寻道时间：活动头磁盘在读写信息前，将磁头移动到制定磁道所需要的时间。

9. 延迟时间：磁头定位到某一磁道的扇区所需要的时间。

10. SCAN 算法：即电梯调度算法，在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。

11. C-SCAN 算法：在扫描算法的基础上规定磁头单向移动来提供服务，回返时直接快速移动至始端而不服务任何请求。