计算机软件技术基础总复习课件.ppt

总复习各部分内容比例各部分内容比例数据结构数据结构50%左右左右操作系统操作系统30%左右左右数据库系统数据库系统15%左右左右软件工程软件工程5%左右左右考试时间：考试时间：12周四周四6-7考试地点：考试地点：231：M206/M306251：D209/B209集中答疑时间：集中答疑时间：12周二周二6-7，周三下午，周三下午答疑地点：实验楼答疑地点：实验楼304数据结构数据结构1数据的逻辑结构数据的逻辑结构2、数据的存储结构、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。、数据的运算：检索、排序、插入、删除、修改等。A线性结构线性结构B非线性结构非线性结构A顺序存储顺序存储B链式存储链式存储线性表线性表栈栈队队树形结构树形结构图形结构图形结构数数据据结结构构的的三三个个方方面面数据结构可描述为数据结构可描述为Group=（D，R）(亦称物理结构亦称物理结构)数组数组逻辑结构逻辑结构存储结构（定义，特点）存储结构（定义，特点）顺序存储结构顺序存储结构链式存储结构链式存储结构相关运算及应用相关运算及应用插入、删除等插入、删除等线性表线性表定义，特点定义，特点存储结构存储结构相关运算及应用相关运算及应用栈和队列栈和队列多多维维数数组组的的两两种种顺顺序序存存储储方方式式：行行优优先先顺顺序序和和列列优优先先顺顺序序。这这两两种种存存储储方方式式下下的地址计算方法的地址计算方法。稀疏矩阵的三元组表示稀疏矩阵的三元组表示数组数组树的概念树的概念，包括与树有关的各个名词的意义，包括与树有关的各个名词的意义二叉树的定义二叉树的定义二叉树的性质二叉树的性质两种特殊情形的二叉树两种特殊情形的二叉树(完全二叉树和满二叉树的定义完全二叉树和满二叉树的定义)二叉树的遍历二叉树的遍历:能够熟练排出二叉树的三种遍历次序。能够熟练排出二叉树的三种遍历次序。三种遍历算法的实现，运用这些算法解决简单的问题。三种遍历算法的实现，运用这些算法解决简单的问题。二叉排序树二叉排序树二叉排序树的插入和生成，给定一个序列，画出二叉排序树的二叉排序树的插入和生成，给定一个序列，画出二叉排序树的生成过程。生成过程。二叉排序树中结点的删除。二叉排序树中结点的删除。哈夫曼树哈夫曼树:用图示法画出哈夫曼树用图示法画出哈夫曼树根据哈夫曼树给出根据哈夫曼树给出最优前缀码最优前缀码。树形结构树形结构图形结构图形结构图的概念包括与图有关的各个名词的意义图的概念包括与图有关的各个名词的意义图的邻接矩阵表示法和邻接表表示法图的邻接矩阵表示法和邻接表表示法根据表示法画出图或者根据图写出邻接矩阵表根据表示法画出图或者根据图写出邻接矩阵表示或画出邻接表。示或画出邻接表。图的遍历图的遍历深度优先遍历深度优先遍历广度优先遍历广度优先遍历单源最短路径单源最短路径拓扑排序拓扑排序查找查找查找的基本概念，平均查找长度的定义及计算查找的基本概念，平均查找长度的定义及计算线性表的查找有三种方法线性表的查找有三种方法顺序查找、二分查找、分块查找顺序查找、二分查找、分块查找二叉排序树查找二叉排序树查找哈希查找，什么是哈希表哈希查找，什么是哈希表?哈希函数、哈希值、哈哈希函数、哈希值、哈希的含义。冲突希的含义。冲突(碰撞碰撞)、同义词的含义。、同义词的含义。处理哈希表中冲突的方法：处理哈希表中冲突的方法：开放定址法开放定址法拉链法拉链法画出哈希表，并计算哈希表中查找的平均查找长度画出哈希表，并计算哈希表中查找的平均查找长度排序方法排序方法插入排序插入排序选择排序选择排序交换排序交换排序归并排序归并排序线性插入排序线性插入排序对半插入排序对半插入排序简单选择排序简单选择排序堆堆排序排序冒泡排序冒泡排序快速排序快速排序排序排序操作系统概念操作系统概念q操作系统基本概念操作系统基本概念定义、目的、特征定义、目的、特征q操作系统的分类操作系统的分类批处理系统、分时系统、实时系统。批处理系统、分时系统、实时系统。q操作系统的功能操作系统的功能处理机管理、存储管理、设备管理、文件处理机管理、存储管理、设备管理、文件管理、作业管理管理、作业管理处理机管理处理机管理作业的概念作业的概念作业的定义、组成、作业的定义、组成、JCB、状态状态进程的概念进程的概念进程的定义、进程的定义、PCB、进程与程序进程与程序进程状态及进程控制进程状态及进程控制进程状态及转换、进程队列、进程控制进程状态及转换、进程队列、进程控制处理机调度处理机调度高级高级调度、低级调度、调度算法调度、低级调度、调度算法进程的同步与互斥进程的同步与互斥概念、解决同步互斥的软件工具（概念、解决同步互斥的软件工具（P-V操作）、生操作）、生产者产者消费者问题消费者问题死锁死锁产生死锁的原因、必要条件、解决死锁方法产生死锁的原因、必要条件、解决死锁方法解决死锁方法解决死锁方法预防：预防：在系统运行之前就采取措施，严格防止死锁的产生。方法为：破在系统运行之前就采取措施，严格防止死锁的产生。方法为：破坏死锁产生的坏死锁产生的四个必要条件四个必要条件之一。之一。一次性分配资源。一次性分配资源。申请不到资源，则释放全部资源。申请不到资源，则释放全部资源。资源编号，从低到高申请。资源编号，从低到高申请。避免：避免：允许死锁产生的四个必要条件存在，当系统有可能产生死锁时，允许死锁产生的四个必要条件存在，当系统有可能产生死锁时，小心地避免。小心地避免。银行家算法。银行家算法。检测和恢复：检测和恢复：允许死锁的产生，每隔一段时间进行检测，若存在死锁，允许死锁的产生，每隔一段时间进行检测，若存在死锁，则即决之。则即决之。化简资源分配图。化简资源分配图。撤销进程。撤销进程。按某种次序强行从系统中撤销一个或多个卷入死锁的进按某种次序强行从系统中撤销一个或多个卷入死锁的进程，收回它们的资源，直到有足够的资源可供其他进程执行完毕。程，收回它们的资源，直到有足够的资源可供其他进程执行完毕。挂起进程。挂起进程。使用挂起使用挂起/激活机构挂起一些进程，暂时剥夺它们占有的激活机构挂起一些进程，暂时剥夺它们占有的资源，以解除死锁，待以后条件满足后再激活被挂起的进程。资源，以解除死锁，待以后条件满足后再激活被挂起的进程。存储管理存储管理q存储管理任务存储管理任务主存空间分配、地址映射、内存保护、内存主存空间分配、地址映射、内存保护、内存“扩充扩充”q实存储管理实存储管理1.固定分区、动态分区（空闲分区分配算法、固定分区、动态分区（空闲分区分配算法、动态重定位）动态重定位）q虚拟存储管理虚拟存储管理请求分页（概念、特点、地址转换、页面置请求分页（概念、特点、地址转换、页面置换算法）换算法）请求分段请求分段设备管理设备管理q有关概念有关概念设备管理的功能、任务设备管理的功能、任务qI/O请求的检测与控制请求的检测与控制n循环测试循环测试、中断、中断、DMADMA、通道通道q缓冲技术缓冲技术概念、目的概念、目的q设备管理程序设备管理程序逻辑设备与物理设备逻辑设备与物理设备q虚拟设备技术虚拟设备技术虚拟设备、虚拟设备、SPOOLingSPOOLing技术技术文件管理文件管理q基本概念与术语基本概念与术语文件、文件系统文件、文件系统文件分类文件分类q文件的结构文件的结构n逻辑结构（记录式文件、流式文件）逻辑结构（记录式文件、流式文件）、物理结构、物理结构（连续分配、链接分配、索引分配）（连续分配、链接分配、索引分配）q文件目录文件目录nFCB、文件目录文件目录、目录项、目录文件、目录结构、目录项、目录文件、目录结构（单级、目录、目录）、路径（单级、目录、目录）、路径q文件存储空间的管理文件存储空间的管理数据库系统概述数据库系统概述数据库基本概念数据库基本概念DB、DBMS、DBS、DBA数据模型数据模型数据模型（数据模型（E-R图）图）、结构模型（层次、网状、关系）、结构模型（层次、网状、关系）、E-R图转换为关系模型图转换为关系模型数据库系统结构（三级模式结构）数据库系统结构（三级模式结构）外模式、模式、内模式、外模式外模式、模式、内模式、外模式/模式映象、模式模式映象、模式/内内模式映象模式映象、逻辑独立性、物理独立性、逻辑独立性、物理独立性关系数据库的基本概念关系数据库的基本概念关系、元组、属性、候选码、主码关系、元组、属性、候选码、主码关系模式、关系模型、关系特点关系模式、关系模型、关系特点关系数据操作语言关系数据操作语言关系代数关系代数传统的集合运算（并、交、差、广义笛卡尔传统的集合运算（并、交、差、广义笛卡尔积）积）专门的关系运算（选择、投影、连接（条件专门的关系运算（选择、投影、连接（条件连接、自然连接）连接、自然连接）结构化查询语言结构化查询语言SQL SQL：DDL、DML、DCLSELECT语句的使用语句的使用软件工程软件工程软件工程基本概念软件工程基本概念软件、软件危机软件、软件危机软件生命周期软件生命周期软件开发过程软件开发过程过程模型过程模型软件开发方法软件开发方法结构化、面向对象结构化、面向对象软件开发工具软件开发工具结构化软件开发方法结构化软件开发方法可行性研究可行性研究市场、经济市场、经济、技术、技术、法律、可行性研究报告、法律、可行性研究报告需求分析需求分析任务、步骤、数据流图、数据字典、需求规格说明书任务、步骤、数据流图、数据字典、需求规格说明书概要设计概要设计体系结构设计、模块设计、用户界面设计、数据库设计、概要设计说明书体系结构设计、模块设计、用户界面设计、数据库设计、概要设计说明书模块独立性、耦合、内聚模块独立性、耦合、内聚-详细设计（图形工具）详细设计（图形工具）-编码编码-测试测试目的、任务、白盒测试、黑盒测试、目的、任务、白盒测试、黑盒测试、测试用例测试用例、测试计划、测试报告、测试计划、测试报告软件维护软件维护改正性维护、适应性维护、改正性维护、适应性维护、扩充与完善性维护、预防性维护扩充与完善性维护、预防性维护线性链表的基本操作线性链表的基本操作指针赋值指针移动后插前插pss=pp=p-nextppsps-next=p-nextp-next=sspqheadq=headWhile(q-next!=p)q=q-nextq-next=ss-next=p栈的定义栈的定义限定只能在表的一端进行插入限定只能在表的一端进行插入和删除的特殊的线性表和删除的特殊的线性表栈顶栈顶（top)top)：允许插入和删除允许插入和删除的一端；的一端；栈底栈底（bottom):bottom):不允许插入和不允许插入和删除的一端。删除的一端。空栈空栈:表中无元素时。表中无元素时。栈的修改是按后进先出的原则栈的修改是按后进先出的原则进行的，我们又称栈为进行的，我们又称栈为LIFOLIFO表表(Last In First Out).Last In First Out).ana3a2a1栈底进栈进栈出栈出栈栈顶栈顶栈栈底底练习练习设一数列的顺序为1,2,3,4,5 通过栈操作,不可能得到的序列是()A.23451B.54123C.23145D.15432122334455 1练习练习设一数列的顺序为1,2,3,4,5 通过栈操作,不可能得到的序列是()A.23451B.54123C.23145D.154321234455答案答案B队的定义队的定义一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear):允许插入的一端队头(Front):允许删除的一端队列的操作原则是先进先出的，所以队列又称作FIFO表(First In First Out)a1 a2 a3 a4 a5anfront队头队头 rear队尾队尾出队出队入队入队数组的顺序存储结构数组的顺序存储结构计算机的内存结构是一维的，因此将数计算机的内存结构是一维的，因此将数组元素排成线性序列，然后将这个线性组元素排成线性序列，然后将这个线性序列存放在存储器中序列存放在存储器中行优先顺序行优先顺序：把数组按一行一行的顺序：把数组按一行一行的顺序依次排列。依次排列。列优先顺序列优先顺序：就是把数组按一列列的顺：就是把数组按一列列的顺序依次排列。序依次排列。地址的计算方法地址的计算方法二维按行优先顺序存放二维按行优先顺序存放a11a12a13a14a15a21a22a23a24a25a31a32a33a34a35a41a42a43a44a45存放在计算机内：mj-1aiji-1na11a12a13a14a15a21a22a43a44a45Loc（aij）=Loc(a11)+(i-1)*n+(j-1)(1=i=m,1=j=n)第一个元素是从a11开始，注意从a00开始的情况Loc（aij）=Loc(a00)+i*n+jaij前的元素个数 地址的计算方法地址的计算方法二维按列优先顺序存放二维按列优先顺序存放a11a12a13a14a15a21a22a23a24a25a31a32a33a34a35a41a42a43a44a45存放在计算机内：mj-1aiji-1na11a21a31a41a12a22a32a25a35a45Loc（aij）=Loc(a11)+(j-1)*m+(i-1)(1=i=m,1=j=n)第一个元素是从a11开始，注意从a00开始的情况Loc（aij）=Loc(a00)+(j*m+i)*d稀疏矩阵的压缩存储方式稀疏矩阵的压缩存储方式三元组表三元组表示示把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表(三元组表)来表示这个稀疏矩阵。但是这种压缩存储方式将失去随机存储功能。一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。稀疏矩阵的压缩存储方式稀疏矩阵的压缩存储方式三元组表三元组表示示把非零元素的值和它所在的行号列号做把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组为一个结点存放在一起，用这些结点组成的一个线性表成的一个线性表(三元组表三元组表)来表示这个来表示这个稀疏矩阵。稀疏矩阵。但是这种压缩存储方式将失去随机存储但是这种压缩存储方式将失去随机存储功能。功能。711列列行行值值ACGT2DHIT3JMBELKT1F介绍几个术语：介绍几个术语：结点结点（Node）：）：树中的元素树中的元素。结点的度结点的度（Degree）：）：结点拥有的子树数。结点拥有的子树数。叶子叶子（Leaf）：）：度为零的结点，也称端结点。度为零的结点，也称端结点。结点的层次结点的层次：从根结点开始算起，根为第一层。：从根结点开始算起，根为第一层。深度深度（Depth)：树中结点的最大层次数。树中结点的最大层次数。孩子孩子（Child）：）：除根结点外除根结点外,每个结点都是其前趋结点的孩子每个结点都是其前趋结点的孩子双亲双亲（Parent）：）：孩子结点的上层结点，称为这些结点的双亲孩子结点的上层结点，称为这些结点的双亲兄弟兄弟（Sibling）：）：同一双亲的孩子。同一双亲的孩子。森林森林（Forest）：）：M棵互不相交的树的集合。棵互不相交的树的集合。有有序序树树:每每个个结结点点的的各各子子树树从从左左到到右右的的次次序序不不能能互互换换的的树树称称为为有有序序树树二叉二叉树树4231678910 11125 非完全二叉树非完全二叉树完全二叉树完全二叉树4231678910 11125 完全二叉树完全二叉树特点：除最后一层外，每一层都取最大结点数，特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。最后一层结点都集中在该层最左边的若干位置。二、几种特殊形式的二叉树二、几种特殊形式的二叉树二叉树的性质二叉树的性质1.二叉树上第二叉树上第i层上的结点数目最多为层上的结点数目最多为2i-1(i1)2.深度深度为为h的二叉树至多有的二叉树至多有2h-1个结点个结点(h1)3.在任意一棵二叉树中，若叶子结点的个数为在任意一棵二叉树中，若叶子结点的个数为n0,度为度为2的结点数为的结点数为n2，则则n0=n2+1。4.具有具有n个结点的完全二叉树高度为个结点的完全二叉树高度为|_log2n_|+15.设完全二叉树中阶段数设完全二叉树中阶段数n，按层编号，对树中第按层编号，对树中第i个结点有：个结点有：1.若若i=1，i的双亲节点编号为的双亲节点编号为|_i/2_|2.i的左子位于第的左子位于第2*i号节点号节点3.i的右子位于第的右子位于第2*i+1号节点号节点二叉树的遍历二叉树的遍历先序ABCDEFG中序CBDAEGF后序CDBGFEAABGCEDF若二叉若二叉树树中各中各结结点的点的值值均不相同，均不相同，则则由二叉由二叉树树的前序序列和中序序列，或由其后序序列和中的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉序序列均能唯一地确定一棵二叉树树，但由前序，但由前序序列和后序序列却不一定能唯一地确定一棵二序列和后序序列却不一定能唯一地确定一棵二叉叉树树。例例:已知一棵二叉已知一棵二叉树树的前序序列和的前序序列和中序序列分中序序列分别为别为前前序遍历序遍历:ABCDEFG ABCDEFG 中序遍历中序遍历:CBDAFEGCBDAFEG ，请请画出此二叉画出此二叉树树。二叉排序树二叉排序树二叉排序树或是空树二叉排序树或是空树,或具或具有下列性质有下列性质其左子树上所有结点的其左子树上所有结点的数据值均数据值均小于小于根结点的根结点的数据值数据值;其右子树上所有结点的其右子树上所有结点的数据值均数据值均大于或等于大于或等于根根结点的数据值结点的数据值;左子树和右子树又各是左子树和右子树又各是一棵一棵二叉排序树二叉排序树10103 321212 218184 4131315159 99 98 8中序遍历中序遍历:2,3,4,8,9,9,10,13,15,18,212,3,4,8,9,9,10,13,15,18,21得到由小到大的有序序列得到由小到大的有序序列哈夫曼树哈夫曼树树的带权路树的带权路径长度最小径长度最小的二叉树就的二叉树就称为最优二称为最优二叉树（即哈叉树（即哈夫曼树）。夫曼树）。d db ba ac c7 75 52 24 4WPL=7*1+5*2+2*3+4*3=35WPL=7*1+5*2+2*3+4*3=35哈夫曼首先提出了构造最优二叉树的算法，哈夫曼算法哈夫曼首先提出了构造最优二叉树的算法，哈夫曼算法 练习练习:给定一组权值给定一组权值w=w=22，3 3，8 8，4 4，4545，7 7，99构造关于构造关于w w的哈夫曼树的哈夫曼树458784532916724339练习练习:给定一组权值给定一组权值w=w=22，3 3，8 8，4 4，4545，7 7，99构造关于构造关于w w的哈夫曼树的哈夫曼树5328 4 45 7 9453298 45 7 915874532945 9158745329451893315874532918933784515874532945189图的概念图的概念图是一种复杂的非线性结构,由两个集合V和E组成，V是顶点的有穷非空集，E是V中顶点偶对(边)的有穷集图的逻辑结构特征：就是其结点(顶点)的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。无向图:图中顶点关系为无序对。(边)有向图:图中顶点关系为有序对。(弧)网：图中每一条边附有一个对应的数（权）有向网：弧上带权的有向图子图:简单地说，子图就是原图的一部分度:无向图中顶点的度就是关联于该顶点的边的数目入度:顶点v的入度即是以该顶点为终点的边的数目出度:顶点v的出度即是以该顶点为始点的边的数目图的存储结构图的存储结构邻接矩阵表示法邻接矩阵表示法1 12 23 35 54 401110101001100110000001001 12 23 34 40110000000011000有向图无向图，矩阵对称图的存储结构图的存储结构邻接表邻接表1 12 23 35 54 41 12 23 34 41234 213 3215 41 53 123 234 41 邻接矩阵与邻接表邻接矩阵与邻接表从存储空间角度看，邻接表更适合于表示稀疏图而邻接矩阵适合于表示稠密图。从求解相应问题来看，求顶点的度，采用邻接矩阵比邻接表表示更方便。23 4 12341 000000011000V1V2V3V4V1V2V3V40110图的遍历从某一个顶点出发，沿着某条路经对途中其余顶点进行访问，且每个顶点仅被访问一次深度优先遍历（DFS depth-first search）广度优先遍历（BFS breadth-first search）深度优先遍历算法深度优先遍历算法(dfs)1 12 23 34 47 78 85 56 601100000100110001000011001000001010000010010000100100001000111101234567812345678Dfs(1)Dfs(2)Dfs(4)Dfs(8)Dfs(5)Dfs(6)Dfs(3)Dfs(7)10000000Visited1:8112345678111111深度优先遍历算法深度优先遍历算法邻接表邻接表存储存储1245 213 3167 48 58 2268 853467 Dfs(7)Dfs(3)Dfs(1)Dfs(2)Dfs(4)Dfs(8)Dfs(5)Dfs(6)78 300000010Visited1:8123456781111111广度优先遍历算法广度优先遍历算法(邻接表邻接表存储存储)1245 213 3167 48 58 2268 853467 Visited1:80 0 0 0 0 0 0 001234567 12345678 2队列队列rfr1121r3131f414r51r5f61r671r7f81r8fff f78 3图的应用图的应用单源最短路径单源最短路径求单源最短路径的求单源最短路径的(dijkstra)思想思想设置并逐步扩充一个集合设置并逐步扩充一个集合S，存放已求出其最短存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合路径的顶点，则尚未确定最短路径的顶点集合是是V-S，其中其中V为网中所有顶点集合。按最短路为网中所有顶点集合。按最短路径长度递增的顺序逐个将径长度递增的顺序逐个将V-S中的顶点加中的顶点加S中，中，直到直到S中包含全部顶点，而中包含全部顶点，而V-S为空。为空。图的应用图的应用拓扑排序AOV网网作业活动网作业活动网将将G G中所有顶点排成一个线性序列，使得对图中所有顶点排成一个线性序列，使得对图中任一对顶点中任一对顶点u u和和v v，若若 E(G)(u,vE(G)(该有向边该有向边在该图的边集中可以找到在该图的边集中可以找到)，则，则u u在线性序列中在线性序列中出现在出现在v v之前。这种线性序列称为之前。这种线性序列称为拓扑序列拓扑序列。拓扑排序拓扑排序是对于是对于有向无环图有向无环图才可以排序成功的才可以排序成功的，若图中存在有向环，则该拓扑序列不存在。若图中存在有向环，则该拓扑序列不存在。拓扑排序方法拓扑排序方法每次输出一个无前趋的结点并删去此结点每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。及其出边，最后得到的序列即拓扑序列。1 12 23 34 45 56 6三种查找方法的比较三种查找方法的比较哈希表（散列表）概念哈希表（散列表）概念BaiChangZhao1234.26KeyT:记录记录H通过对给定值做某种运算，直接求得某关键字在记录文件中的位置哈希哈希(hash)hash)函数：函数：根据关键字直接计算出元素所在位置的函根据关键字直接计算出元素所在位置的函数数 H(key)H(key)哈希表：存放记录元素的一维数组哈希表：存放记录元素的一维数组哈希地址：一维数组的下标哈希地址：一维数组的下标处理冲突的方法处理冲突的方法开放定址法：开放定址法：将所有结点均存放在哈希将所有结点均存放在哈希表表T0.m-1中中线性探查法线性探查法平方探查法平方探查法随机探查法随机探查法拉链法：拉链法：将互为同义词的结点链成一个将互为同义词的结点链成一个单链表，而将此链表的头指针放在哈希单链表，而将此链表的头指针放在哈希表中。表中。线性探查法线性探查法关键字序列关键字序列:19、14、23、1、68、20、84、28、55、11、10、79设哈希函数为：设哈希函数为：H(k)=kmod13(除留余数法除留余数法)01234567891011126、1、10、1、3、7、6、2、3、11、10、119142316820842855111079184842828 551079处理冲突的方法处理冲突的方法拉链法拉链法将所有关键字为同义词的结点链接在同一个单链表中。0123456789101112关键字序列关键字序列:19,14,23,1,68,20,84,28,55,11,10,796,1,10,1,3,7,6,2,3,11,10,1H(k)=kmod13(除留余数法除留余数法)14128796855198423101120ASL=7*1+4*2+1*3=1.5处理冲突的方法处理冲突的方法排序排序1.1.插入排序：插入排序：基本思想：每次将一个待排序的记录，按其关键基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。位置，直到全部记录插入完成为止。线性插入排序线性插入排序从数组的第从数组的第2号元素开始，顺序从数组中取出元素，并将号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上该元素插入到其左端已排好序的数组的适当位置上对半插入排序对半插入排序在有序区中进行对分查找，以确定插入的位置在有序区中进行对分查找，以确定插入的位置排序排序2.2.交换排序交换排序基本思想：两两比较反即换。基本思想：两两比较反即换。冒泡排序冒泡排序第第一一趟趟：第第1个个与与第第2个个比比较较，大大则则交交换换；第第2个个与与第第3个个比比较较，大则交换，大则交换，关键字最大的记录交换到最后一个位置上；关键字最大的记录交换到最后一个位置上；第第二二趟趟：对对前前n-1个个记记录录进进行行同同样样的的操操作作，关关键键字字次次大大的的记记录录交交换换到第到第n-1个个位置上；位置上；依次类推，则完成排序。依次类推，则完成排序。快速排序快速排序通过一趟排序将待排序列通过一趟排序将待排序列分成两部分分成两部分，使其中，使其中一部分记录一部分记录的的关键字均比关键字均比另一部分小另一部分小，再分别对这两部分排序，以达到整，再分别对这两部分排序，以达到整个序列有序。个序列有序。排序排序3.3.选择排序选择排序基本思想：基本思想：每趟选一排在（前）后每趟选一排在（前）后。简单选择排序：简单选择排序：每一趟从待排序的记录中选出关键字最小的记录，顺序存放已排好每一趟从待排序的记录中选出关键字最小的记录，顺序存放已排好的子文件的最后的子文件的最后(最前最前)，直到全部记录排序完毕。，直到全部记录排序完毕。堆排序：堆的定义、堆排序：堆的定义、堆的构造、堆排序基本思想堆的构造、堆排序基本思想由给定的无序序列构造堆由给定的无序序列构造堆将堆顶元素与堆中最后一个元素交换，将堆顶元素与堆中最后一个元素交换，将最后一个元素从堆中删除将最后一个元素从堆中删除将余下的元素构成完全二叉树重新调整成堆将余下的元素构成完全二叉树重新调整成堆反复进行，直到堆空。反复进行，直到堆空。堆排序过程堆排序过程4270174655051394135517464205709405461713425570940542171346557094051317424655709405131742465570940513174246557094第一趟结果第一趟结果:第二趟结果第二趟结果:第三趟结果第三趟结果:第四趟结果第四趟结果:第五趟结果第五趟结果:第六趟结果第六趟结果:第七趟结果第七趟结果:4655134294051770快速排序例快速排序例初始值初始值465513429451770第一趟第一趟175134246945570第二趟第二趟513174246705594第三趟第三趟513174246557094第四趟第四趟513174246557094例如对序列16，31，9，15，87，76，13，24，43进行二路归并排序过程为：初始序列初始序列161631319 9151587877676131324244343第一趟第一趟归归并并161631319 9151576768787131324244343第二趟第二趟归归并并9 915151616313113132424767687874343第三趟第三趟归归并并9 913131515161624243131767687874343结结果果9 913131515161624243131434376768787归并排序归并排序一趟归并过程中的三种情况一趟归并过程中的三种情况n1lengthiii+2*length=nn1lengthiii+length0时，表示该类临界资源的可用个数。时，表示该类临界资源的可用个数。S0时，表示该类临界资源的可用个数。S0时，表示该类临界资源的可用个数。时，表示该类临界资源的可用个数。S0时，表示该类临界资源的可用个数。时，表示该类临界资源的可用个数。S0时，表示等待使用该类临界资源的进程个数。时，表示等待使用该类临界资源的进程个数。第六节第六节死锁问题死锁问题一、死锁的概念一、死锁的概念二、死锁产生的原因二、死锁产生的原因三、死锁产生的必要条件三、死锁产生的必要条件四、四、死锁的排除方法死锁的排除方法 死锁产生的原因死锁产生的原因系统资源不足系统资源不足进程推进的顺序不当进程推进的顺序不当产生死锁的必要条件产生死锁的必要条件1.所涉及的资源是非共享的所涉及的资源是非共享的（互斥条件）（互斥条件）2.进程在等待新资源时进程在等待新资源时,继续占用已分配的资源继续占用已分配的资源（请求和保持条件）（请求和保持条件）3.一个进程占有的资源不能被别的进程强行攻占一个进程占有的资源不能被别的进程强行攻占（不剥夺条件）（不剥夺条件）4.前一个进程获得的资源正是后一个进程所请求的前一个进程获得的资源正是后一个进程所请求的,从而形成一个从而形成一个进程的循环链进程的循环链（环路等待条件）（环路等待条件）R1R2P1P2进程进程1 1 进程进程2 2申请申请R1 R1 申请申请R2R2申请申请R2 R2 申请申请R1R1释放释放R1 R1 释放释放R2R2解决死锁方法解决死锁方法预防：预防：在系统运行之前就采取措施，严格防止死锁的产生。方法为：破在系统运行之前就采取措施，严格防止死锁的产生。方法为：破坏死锁产生的四个必要条件之一。坏死锁产生的四个必要条件之一。静态分配资源。静态分配资源。申请不到资源，则释放全部资源。申请不到资源，则释放全部资源。资源编号，从低到高申请。资源编号，从低到高申请。避免：避免：允许死锁产生的四个必要条件存在，当系统有可能产生死锁时，允许死锁产生的四个必要条件存在，当系统有可能产生死锁时，小心地避免。小心地避免。银行家算法。银行家算法。检测和恢复：检测和恢复：允许死锁的产生，每隔一段时间进行检测，若存在死锁，允许死锁的产生，每隔一段时间进行检测，若存在死锁，则即决之。则即决之。化简资源分配图。化简资源分配图。撤销进程。撤销进程。按某种次序强行从系统中撤销一个或多个卷入死锁的进按某种次序强行从系统中撤销一个或多个卷入死锁的进程，收回它们的资源，直到有足够的资源可供其他进程执行完毕。程，收回它们的资源，直到有足够的资源可供其他进程执行完毕。挂起进程。挂起进程。使用挂起使用挂起/激活机构挂起一些进程，暂时剥夺它们占有的激活机构挂起一些进程，暂时剥夺它们占有的资源，以解除死锁，待以后条件满足后再激活被挂起的进程。资源，以解除死锁，待以后条件满足后再激活被挂起的进程。第九章第九章存储管理存储管理n基本内容基本内容q存储器层次结构存储器层次结构q存储管理任务存储管理任务q实存储管理实存储管理q虚拟存储管理虚拟存储管理n要求要求q掌握存储管理任务掌握存储管理任务q掌握存储管理、掌握存储管理、实存储管理、虚拟存储管理实存储管理、虚拟存储管理q了解存储器层次结构了解存储器层次结构第二节第二节存储管理任务存储管理任务1.主存空间分配主存空间分配:动态地为不断进进出出的作动态地为不断进进出出的作业分配内存空间。业分配内存空间。2.地址映射地址映射:保证作业运行中能够正确的定位。保证作业运行中能够正确的定位。3.内存保护内存保护:保证作业的进程之间既能互相通保证作业的进程之间既能互相通信而又不互相干扰。信而又不互相干扰。4.内存内存“扩充扩充”:使空间需求量大于用户区容使空间需求量大于用户区容量的作业也能够正常运行。量的作业也能够正常运行。2.地址映射地址映射程序的起始地址都是从程序的起始地址都是从“0”开始的，程序中的其它地址开始的，程序中的其它地址都是相对于起始地址计算的，该地址被称为都是相对于起始地址计算的，该地址被称为逻辑地址（或逻辑地址（或相对地址）相对地址）。由这些地址所形成的地址范围称为（作业）由这些地址所形成的地址范围称为（作业）地址空间地址空间。主存单元的编号称为主存单元的编号称为物理地址（或绝对地址）物理地址（或绝对地址）由主存中的一系列单元所限定的地址范围称为由主存中的一系列单元所限定的地址范围称为存储空间存储空间。相对地址到绝对地址的转换，同时程序中与地址有关的指相对地址到绝对地址的转换，同时程序中与地址有关的指令的修改，这一过程叫做令的修改，这一过程叫做地址重定位地址重定位。静态重定位静态重定位在程序装入时进行在程序装入时进行,由装配程序进行地址转换由装配程序进行地址转换动态重定位动态重定位是在程序的执行过程中是在程序的执行过程中,当当CPU访问指令或数据前，访问指令或数据前，由地址变换机构进行地址变换。由地址变换机构进行地址变换。第三节第三节实存储管理实存储管理1.单一连续分区单一连续分区(单道环境单道环境)2.固定分区固定分区3.动态分区动态分区为调入内存的程序提供一个不小于作业地址为调入内存的程序提供一个不小于作业地址空间的存储空间，当存储空间不够时，采用空间的存储空间，当存储空间不够时，采用覆盖或交换技术扩充内存覆盖或交换技术扩充内存第四节第四节虚拟存储管理虚拟存储管理1.虚拟存储器的原理2.请求分页存储管理请求分页存储管理3.请求分段存储管理请求分段存储管理虚拟存储管理虚拟存储管理工作原理：工作原理：首先把作业信息保留在磁盘上，当作首先把作业信息保留在磁盘上，当作业请求装入时，只将其中一部分先装入主存，作业请求装入时，只将其中一部分先装入主存，作业执行中若要访问的信息不在主存中，则再设法业执行中若要访问的信息不在主存中，则再设法将这些信息装入主存。将这些信息装入主存。用软件方法扩充内存。用软件方法扩充内存。用软件方法扩充内存。用软件方法扩充内存。逻辑上扩充了内存空间。逻辑上扩充了内存空间。逻辑上扩充了内存空间。逻辑上扩充了内存空间。虚拟地址空间的大小受指令中地址长度的限制虚拟地址空间的大小受指令中地址长度的限制虚拟地址空间的大小受指令中地址长度的限制虚拟地址空间的大小受指令中地址长度的限制和外存储容量的限制；和外存储容量的限制；和外存储容量的限制；和外存储容量的限制；需解决什么时候把哪部分程序装入内存、放在需解决什么时候把哪部分程序装入内存、放在需解决什么时候把哪部分程序装入内存、放在需解决什么时候把哪部分程序装入内存、放在内存什么地方、淘汰策略问题。内存什么地方、淘汰策略问题。内存什么地方、淘汰策略问题。内存什么地方、淘汰策略问题。内存分页内存分页分页存储管理分页存储管理页页:将作业的地址空间划分成一系列大小相等的块，将作业的地址空间划分成一系列大小相等的块，称为称为页页，所有页按顺序编号为，所有页按顺序编号为0、1、2、。页内地址页内地址:每个页内的内容也都从每个页内的内容也都从0开始顺序编号，开始顺序编号，这个编号