网( )：，在带权有向图中，以事件表示顶点，以边表示活动，以边上的权值表示活动持续的时间，则这种网称为用边表示活动的网，简称网。 网特点： 1）顶点所表示的事件是指该顶点的所有进入边所表示的活动已完成，所有发出边表示的活动可以开始的一种状态。 2）对一个工程来说，要有一个开始状态和一个结束状态，所以在网中有一个入度为0的开始顶点，称为源点；有一个出度为0的结束顶点，称为汇点。网中也不允许存在回路。
3）完成整个工程的时间是从开始顶点到结束顶点间的最长路径的长度（指该路径上的权值和）。
活动的松驰时间：用活动的持续时间和该活动两侧的两个事件的关键路径时间，二者取差。
关键路径：从源点到汇点的路径长度最长路径称为关键路径。关键路径上的所有活动均是关键活动。
最短路径？？？
20、查找的基本概念
1）查找是一种常用的基本运算。查找表是由同一类型数据元素构成的集合；
2）静态查找表，指在进行查找运算时不再修改的已经构造好的查找表。静态查找表只进行两种操作：查询某个特定的数据元素是否在查找表中；检索某个特定的数据元素的各种属性。
3）动态查找表，是可以进行另两种操作的查找表，即在查找表中插入一个数据元素；从查找表中删除一个数据元素。 4）关键字，是数据元素的某个数据项的值，用它来识别这个数据元素； 5）主关键字，指能唯一标识一个数据元素的关键字； 6）次关键字，指能标识多个数据元素的关键字；
7）查找，根据给定的某个值，在查找表中确定是否存在一个其关键字等于给定值的记录，并返回结果。
顺序查找，从表的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字和给定值相等则查找成功；若整个表均比较过仍未找到则查找失败。若要查找的记录不在表中则需进行1次查找。 平均查找长度为(1)/2。
折半查找（二分查找），可以用二叉树进行分析，以中间记录为根，左子表为左子树，右子表为右子树，依此类推。关键字的比较次数即为被查找结点在树中的层数。查找成功或失败时所比较的关键字数不超过树的层数。折半查找只适用于有序顺序表（以数组方式存储的有序表）。 2^k - 1, (1)
分块查找，又称为索引顺序查找，综合使用上面两种方法。
将长度为n的表均匀分为b块，每块含有s个记录，按顺序查找确定元素所在的块，则 = + , 即块内查找与索引查找之和。
(1)/2 + (1)/2 , 当s取n的平方根时，取得最小值“n的平方根加1\。
21、二叉排序树（又称二叉查找树）：二叉查找树或者是一棵空树，或者具有这样的特性， 1）若二叉查找树的左子树非空，则左子树上的结点值均小于根结点的值； 2）若它的右子树非空，则右子树上的结点值均大于根结点的值； 3）左、右子树的子身就是一棵二叉查找树。
二叉查找树的查找过程从根结点开始，过程类似于折半查找（二分查找）。二叉查找树的插入操作按它的特性法则进行插入，若是空树则作根结点，否则会成为一个新的叶子结点。在二叉查找树中删除一个结点时不能把该结点的子树也删掉，只能删除这个结点但仍要保持二叉查找树的特性，相当于是从一个有序序列中删除一个元素，不能破坏其它元素的有序性。一种方法是，如果删除结点＊P，则可以用＊P的直接前驱或直接后继代替＊P，同时删除它的直接前驱（或直接后继）。
二叉排序树顺序存储在一地址连续的空间内，则序列按中序递增存储。
22、平衡二叉树：它或者是一棵空树，或者具有这样的性质：它的左右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。
平衡因子： 某结点的平衡因子定义为该结点的左子树深度减去它的右子树深度。平衡二叉树上的所有结点的平衡因子只可能是－1、0和1。
为了得到树形均匀的二叉排序树，在构造二叉排序树的过程中可以使用几种办法让它保持为一棵平衡二叉树。每插入一个新结点时，就检查是否打破了平衡。若是，则找出最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡二叉树中结点间关系，达到新的平衡。
最小不平衡二叉树是指离插入结点最近且以平衡因子的绝对值大于1的结点作为根的子树。
平衡二叉树上的插入操作引起不平衡的解决方法：
1）单向右旋平衡处理 －－用于在根的左子树根结点的左子树上插入新结点情况 2）单向左旋平衡处理 －－用于在根的右子树根结点的右子树上插入新结点情况
3）双向旋转（先左旋后右旋）操作 －－用于在根的左子树根结点的右子树上插入新结点的情况 4）双向旋转（先右旋后左旋）操作 －－用于在根的右子树根结点的左子树上插入新结点的情况
11 / 56
B树，有几个比较鲜明的特点。如：一棵m阶的B树中每个结点至多有m棵子树；非终结点（根除外）至少有2棵树；根至少有两棵子树（当根不是叶子时）；所有叶子结点出现在同一层次上。
23、哈希表的定义：根据设定的哈希函数H（）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关健字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表。这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。哈希函数是从关键字集合到地址集合的映像。
对于哈希表主要考虑两个问题：一是如何构造哈希函数；一是如何解决冲突。
构造哈希函数要解决好两个问题：首先哈希函数是一个压缩映像函数；其次哈希函数应具有较好的散列性。前者为节省空间，后者为减少冲突。常用的哈希函数构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法。
处理冲突的方法：
1）开放地址法 = (H() + ) 1,2 (k<1)
H()为哈希函数；m为哈希表的表长；为增量序列。 1,2,31 称为线性探测再散列；
1^21^2,2^22^2^2 (k<2) 称为二次探测再散列； ＝伪随机序列，称为随机探测再散列。 最简单的产生探测序列的方法是线性探测，即当冲突时顺序对下一单元进行探测并存储。在用线性探测法解决冲突构造的哈希表中进行查找时有3种可能结果：一是在某一位置上找到关键字等于的记录，查找成功；一是按探测序列查找不到而又遇到了空单元，查找失败，此时可进行插入操作；一是查遍全表，未查到指定关键字且存储区已满，要进行溢出处理。
线性探测法的缺点是“溢出处理需别编程序”，“很容易产生聚集现象”。
2）链地址法 ，它在符号表的每一个记录增加一个链域，链域中存放下一个有相同哈希函数值的记录的的存储地址。 3）再哈希法 ， = () 1,2 均是不同的哈希函数，即在同义词发生地址冲突时计算另一个哈希函数地址，直到解决。
4）建立一个公共溢出区，一溢出全放这里去；
哈希表的装填因子， a = (表中添入的记录数/哈希表长度） －－a越小，发生冲突的可能越小
虽然哈希表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得哈希表的查找过程仍是一个给定值和关键字进行比较的过程。仍须以平均查找长度衡量哈希表的查找效率。 在查找过程中须与给定值进行比较的关键字的个数取决于3个因素：哈希函数、处理冲突方法、哈希表的装填因子。
24、排序：稳定的排序、不稳定的排序。 内部排序、外部排序。
简单排序法：包括直接插入排序、冒泡排序和简单选择排序。它们的算法复杂度为O（n＾2），在元素已经基本有序的情况下，使用直接排序方法可获得较高的效率O(n)。直接插入排序和冒泡排序是稳定的排序方法，简单选择排序是不稳定的排序方法。
直接插入排序适用于”在文件局部有序或文件长度较小的情况下的一种最佳内部排序方法“。直接插入排序的时间复杂度为O(n*n)，若记录序列为正序时其时间复杂度可提高到O(n)。正序？？
冒泡排序算法： ( [], n){ ;
(011<1){ = 0; (0<1)
([j]>[1]){ [j][j][1][1]; 1; } } }
简单选择排序算法： ( [], n){ ; (0<1){ ; (1<) ([j]<[k]); (){
12 / 56
[i][i][k][k]; } } }
希尔排序，又称为缩小增量排序。它是在直接插入排序的基础上加以改进得到的排序方法。基本思想就是：设定一个初始间隔 快速排序，基本思想是通过一趟排序将待排序的记录分割为独立的两部分，其中一部分的关键字均比另一部分小，然后再分别对这两部分记录继续进行排序。具体做法：在头尾设两个指针，分别指向第一个元素和最后一个元素。设枢轴记录为正向（返向）的第一个记录。当初始序列有序时，快速排序蜕变为冒泡排序，此时算法的时间复杂度为n*n。 例如，对50个整数进行快速排序时，因为初始序列有序，所以排序过程退化为冒泡排序，总过程中的比较次数为49+481 = 49*50/2 堆排序，基本思想是对一组待排序记录的关键字，首选把它们按堆的定义排成一个序列，从而输出堆顶的最小关键字。然后将剩余关键字再调整成堆，便得到次小关键字，反复进行，直至全部关键字排成有序序列。 归并排序，是将两个或多个有序表合并成一个新的有序表。是一种稳定的排序。 基数排序，是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。它不是基于关键字比较的排序方法，其平均时间复杂度为O(d*n)，适合于n值很大而关键字较少的序列。 基于关键字比较的内部排序方法的时间复杂度的下限为O()，简单排序、希尔排序、快速排序、堆排序和归并排序是要熟练掌握的排序方法。（重要） 排序方法好坏的两条因素：执行算法的时间；执行算法所需要的附加空间。 常用的外部排序方法是归并排序。 25、分治法，将一个规模为n的问题逐步分解为k个规模更小的子问题，这些子问题互相独立且与原问题性质相同，逐个解决分解出的子问题，由这些子问题的解构造出原问题的解，当2时称为二分法。如解决棋盘覆盖问题。 分治法适用的问题一般具有这些特征： 原问题可以分解成多个子问题，这些子问题与原问题相比只是规模的下降而其结构和求解方法与原问题相同； 若子问题的规模足够小，则直接求解，否则递归地求解子问题； 在得到各子问题的解后，能采用某种方法构造出原问题的解。 动态规划法，与分治法类似也是先将待求解的问题分解成若个个子问题，先求解子问题，然后从子问题的解得到原问题的解。不同的是适合于动态规划法求解的问题所分解得到的子问题之间往往不是独立的。动态规划法常用来求解具有最优性质的问题。即问题的最优解包含了其子问题的最优解。如求解多边形游戏问题。 设计动态规划法的步骤为： 1）找出最优解的性质，并刻画其结构特征； 2）递归地定义最优值； 3）以向前或向后处理方式计算出最优值； 4）根据计算最优值得到的信息，构造最优解。 贪心法，通过一系列的选择来得到一个问题的解，它所做的每一次选择都是当前情况下某种意义的最好选择，即贪心选择。如果待求解的问题具有最优子结构特征，也就是原问题的最优解包含子问题的最优解，并且可以通过局部的贪心选择来达到问题的全局最优解时，可通过贪心法进行求解。贪心标准的选择和问题的结构决定是否可以使用贪心法。如用于二分最小覆盖问题。 回溯法，又被称为通用解题法，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间中按深度优先策略，从根结点出发搜索解空间树。算法搜索到解空间树的任意结点时，首先判断该结点是否包含问题的解。如果不包含则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则进入这棵子树继续按深度优先搜索。如收费公路重建问题。 分支限界法，它类似于回溯法，也是在解空间中搜索问题解的算法，但分支限界法求解的目标是找出满足条件的一个解，如有多个解则要找出某种意义下的最优解。分支限界法以广度优先或以最小耗费优先的方式搜索解空间树。如最大完备子图问题。 26、算法的几个基本特征 有穷性，确定性，能行性，输入，输出。 程序 ＝ 数据结构 ＋ 算法 13 / 56 内容关键字： 线性表、栈、队、串、数组 树、二叉树、森林、线索二叉树、霍夫曼树 图、有向图、无向图、最小生成树、拓朴排序、关键路径 查找、静态查找（顺序、折半、分块）、动态查找（二叉排序树、平衡二叉树、哈希表） 排序、直接插入、简单选择、冒泡、希尔、快速、堆、归并、基数 3.操作系统知识 1、操作系统的定义：是管理计算机中各种软件、硬件资源的程序和相关文档的集合，是一种系统软件。 操作系统能有效的组织和管理系统中的各种软、硬件资源，合理地组织计算机工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口。 操作系统的两个重要作用： 通过资源管理，提高系统的使用效率； 改善人机界面，向用户提供友好的工作环境。 操作系统的4个特征：并发性、共享性、虚拟性、不确定性。 操作系统的5个管理功能：进程管理、文件管理、存储管理、设备管理、作业管理 操作系统的分类： 批处理系统，计算机自动、顺序地执行作业流产生的每一个作业，以节省人工操作时间和提高机器的使用效率。分为单道批处理系统和多道批处理系统。优点是同一批内的各作业次次执行，改善了的使用效率，提高了吞吐量。缺点是磁盘需要人工装卸，作业需要人工分类，监督程序易受用户程序破坏，缺少交互性。 分时系统， 具有如下特征：多路性、独立性、交互性、及时性。 实时系统，分为实时控制系统和实时信息处理系统。主要特点有：快速的响应时间、有限的交互能力、高可靠性 网络操作系统，使得计算机更有效地共享网络资源，为网络用户提供所需各种服务的软件和有关协议的集合。 分布式操作系统，是由多个分散的计算机经网络连接而成，各主机无主次之分。为分布式计算机配置的操作系统称为分布式操作系统。 微机操作系统 嵌入式操作系统 2、研究操作系统的观点 资源管理的观点：从这种观点看，操作系统的管理对象是计算机系统的资源，操作系统则是管理计算机系统的程序集合。这种观点是在共享的前提下以资源分配、使用和回收为出发点，考虑操作系统各部分程序的功能和算法。 虚拟机的观点：操作系统加裸机构成虚拟计算机。虚拟机的观点是从功能分解的角度出发，考虑操作系统的结构，将操作系统分成若干层次，每一层完成特定的功能。 3、顺序程序执行时的特征：顺序性、封闭性、可再现性； 并发程序执行时的特征：非封闭性、程序和机器执行程序的活动不在一一对应、并发程序间的相互制约性。 引入进程的原因：由于程序并发执行破坏了程序的封闭性和可再现性，使得程序和执行程序的活动不在一一对应，此时用静态的程序概念已经不能描述系统中程序动态执行的过程，所以引入了进程。 4、进程的定义：就是程序的一次执行，该程序可以和其它程序并发执行。 进程的组成：进程通常是由程序、数据及进程控制块（）组成的。 进程的程序部分是进程执行时不可修改部分，它描述了进程需要完成的功能； 14 / 56 进程的数据部分是进程的可修改部分； 进程控制块是进程的描述信息和控制信息，是进程存在的惟一标志。 进程和程序的区别是：进程具有状态而程序没有。 5、进程的状态及状态间的切换 三态模型：运行、就绪、阻塞。 五态模型：新建态、终止态、运行、就绪、阻塞。 新建态：对应于进程刚刚被创建时还没有被提交，并等待系统完成创建进程的所有必要信息的状态。整个过程分为两个阶段，一是为一个新建进程创建必要的管理信息，另一是让进程进入就绪状态。因为有了新建态，操作系统可以根据系统的性能和主存的容量限制而推迟新建态的提交。 终止态也分为两个阶段，一是等待操作系统进行善后处理，另一是释放主存。 具有挂起状态的进程状态：当系统资源不能满足所有进程的运行要求时，必须将某些进程挂起，放在磁盘对换区，暂时不参加调度，以平衡系统负载。有这样几个状态：活跃就绪、静止就绪、活跃阻塞、静止阻塞。 6、进程的控制，就是对系统中所有进程从创建到消亡的全过程实施有效的控制。操作系统的内核为系统实现进程控制和存储管理提供了有效的控制机制。 大多数操作系统内核均包含支撑功能和资源管理功能。 支撑功能：中断处理、时钟管理、原语操作。 原语是由若干条机器指令构成的，用于完成特定功能的一段程序。内核在执行某些基本操作时往往是通过原语操作实现的。原语在执行过程中不可分割。内核中包含的原语有进程控制、进程通信、资源管理等。 资源管理功能：进程管理、存储器管理、设备管理。 7、进程间通信 进程间的同步：一般来说，一个进程相对于另一个进程的运行速度是不确定的，即进程是在异步环境下运行。每个进程都以各自独立的不可预知的速度向前推进，但相互合作的进程需要在某些确定点上协调它们的工作，当一个进程到达了这些点后，除非另一进程已完成了某些操作，否则就不得不停下来等等这些操作结束。 进程间的互斥：在多道程序系统中，各进程可以共享各类资源，但有些资源一次只能供一个进程使用，称为临界资源( )。同步是进程间的直接制约问题，互斥是进程间的间接制约问题。 临界区( )是对临界资源实施操作的那段程序。互斥临界区管理的原则为：有空即进、无空则等、有限等待、让权等待。 8、整形信号量与操作 整形信号量是一个整形变量，根据控制对象的不同赋不同的值。信号量分为两类： 公用信号量：实现进程间的互斥，每个相关进程即可对它施行P操作也可以进行V操作，初值为1或资源的数目； 私用信号量：实现进程间的同步，只有一个进程可以对它施行P操作，其它进程只能做V操作，初值为0或某个正整数。 信号量S的物理意义：S＞＝0表示某资源的可用数，S＜0则其绝对值表示阻塞队列中等待该资源的进程数。 操作是实现进程同步与互斥的常用方法。操作是低级通信原语，其中P操作表示申请一个资源，V操作表示释放一个资源。 P操作定义：1，若S＞＝0，则执行P操作的进程继续执行；否则若S＜0，则该进程为阻塞状态，并将其插入阻塞队列。 V操作定义：1，若S＞0，则执行V操作的进程继续执行；否则，若S＜＝0，则从阻塞状态唤醒一个进程，并将其插入就绪队列，执行V操作的进程继续执行。 利用操作实现进程的互斥：令信号量的初值为1，当进入临界区时执行P操作，临界区时执行V操作。 P() 临界区 V() 怎样利用操作实现进程的同步：可用一个信号量与消息联系起来，当信号量的值为0时表示希望的消息未产生，当信号量的值为非0时表示希望的消息已经存在。假定用信号量S表示某条消息，进程可以通过调用P操作测试消息是否到达，调用V操作通知消息已准备好。最典型的是单缓冲区的生产者和消费者的同步问题。如果采用操作来实现进程和进程间的管道通信，并且保证这两个进程并发执行的正确性，则至少需要2个信号量，信号量的初值分别为0、1。 15 / 56
软考学习笔记-数据库工程师
