数据结构的基本概念(17页).doc

-数据结构的基本概念-第 16 页数据结构的基本概念 大纲对本节的要求就是：本节的标题数据结构的基本概念。说到概念，绝对不是死记硬背的方式解决，而应该注意理解！（因为没有填空题或者是论述题，不需要记住。）本节所涉及到所需要掌握的概念有：1数据结构的概念数据结构：是讨论计算机系统中数据的组织形式及其相互关系。数据的基本单位：数据元素。数据的逻辑结构：分为线性结构和非线性结构。存储结构：数据在计算机中的存储方法。（在理解存储方法的时候要注意：不是把数据放在存储器里就完了，重要的是在以后怎样找到他们）数据的存储结构分为：顺序存储、链接存储、索引存储和散列存储。顺序存储方法：逻辑上相邻的数据元素存储在实际相邻的存储单元中。链接存储方法：元素间的逻辑关系由指针字段确定，元素间的关系只是逻辑上的相邻，并不一定要求在物理上也相邻，数据元素的存储单元数据项指针项。索引存储方法：在存储元素信息时，建立一张附加索引表与之对应的方法。稠密索引：索引项对应元素稀疏索引：索引项对应一组元素散列存储方法：根据关键字直接算出元素的地址数据的处理：常用数据处理与运算的几种基本操作：遍历、插入、更新、删除、查找、排序。遍历和排序操作后，没有改变或增减数据元素；排序将改变其位置2举例 例 在已知的一个线性结构中有20个元素，将第8个元素的数据进行一次替代，则该操作属于算法中的（ ）。A） 遍历 B） 插入 C） 排序 D） 更新【解析】 所谓遍历是指在数据结构的各个元素中移动或查看所有数据元素，而插入是指往数据结构中添加新的元素；更新则指个性或替代数据结构中指定元素的一个或多个数据项，显然，本题中，没有涉及到增加新的元素，而仅仅是对原已有的元素进行了数据项的替换。故答案应选D。例（判断）采用“索引存储方法”的数据可以进行随机读写（）【解析】所谓“随机读写”，是相对于“顺序读写”而言，就是可以读写任意指定位置的数据，可以根据索引表找到元素的地址，而不需要从头开始。所以应该是正确的。线性结构考生在本节复习时，要着重从以下几个方向进行：1概念：线性结构的逻辑特征：有且仅有一个开始数据元素和个终点数据元素，并且所有数据元素都最多只有一个直接前趋和一个直接后继。线性表、数组、字符串、队列等都有属于线性结构。如人们排队，一个人前后最多只一个人，不能有两个。有且只有一个无直接前继的开始元素和一个无直接后继的终点元素。 线性结构的类型主要有：线性表（又包括顺序表，线性链表）、堆栈、队列、数组、串等。 线性表的两种存储方式：顺序存储方式（由此形成顺序表） 链式存储方式（由此形成链表） 顺序表：数据元素按其逻辑次序依次存放在一组地址连续的存储单元里。 缺点：插入、删除等操作比较麻烦，长度动态的变化不方便。 线性链表：采用链式存储方式进行存储的线性表，即用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，从而可以大提高存储器的使用效率。 链：在存储一个数据元素中，除了存储的数据本身外，还包含数据的直接后继（或直接前趋）的位置，或指针，这一部分称为链。 线性链表主要有：单链表，双链表，循环链表。 单向链表：。在单链表中，数据元素由数值域和数据元素的指针域两部分组成，即：每一个数据元素=数据域直接后继元素的地址。其中终点结点无直接后继，终结点的指针域值为空NIL。 双向链表：每一元素的指针域既包含直接后继，也包含直接前趋。即：每一个数据元素=直接前驱元素的地址数据域直接后继元素的地址。 循环链表：是一种首尾连接的链表。注意理解：计算机是根据“地址”来读写数据的：对于顺序表是不是不需要地址？当然不是。对于顺序表我们只关心第一个地址，因为后面一个一个的都挨着连续存放。在此应理解顺序表，链表的插入、删除算法。 栈：只能在表的一端进行插入和删除运算的线性表。插入和删除的一端称为栈顶；另一端称为栈底。栈中没有元素为空栈。栈的指针始终指向栈顶。 栈的基本操作原则：后进先出Last In First Out （LIFO）。 栈的主要应用：子程序的嵌套调用，递归调用，中断系统的断点保护，编译系统的后缀表达式计算等。 队列：只能在表的一端进行删除（队头）另一端进行插入（队尾）的线性表。 操作原则：先进先出First In First Out（FIFO） 队列有两个指针,队头指针：总是指队头元素前一位置；队尾指针：总是指向队尾元素所在的存储位置。 二维数组行优先的某一元素地址：Loc(aij)=Loc(a11)+(i-1)*n+(j-1) )*S 二维数组列优先的某一元素地址：Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*S 其中M，N为二维数组最大行号和列号，i,j为某一元素的行、列下标，S为数组中每一元素所占字节数。 串由若干字符组成。 串的基本单位：为一个字节。2举例： 例： 判断题和选择题 （1）顺序表和线性链表的物理存贮形式都是顺序存贮。（ ）【解析】 本题是错误的，首先要有在第一节中的存贮结构的概念，数据结构中，将存贮结构（物理）分为四种：顺序存贮、链接存贮、索引存贮、散列存贮。虽然顺序表和线性链表逻辑上都属于线性结构，但在物理存贮形式上有一定的区别，即顺序表的按顺序存贮形式，线性链表按链接存贮形式。 （2）单向链表的每个数据元素由两部分组成，一部分为存贮元素的数据域，另一部分为存贮直接后继（前趋）元素的数据域。【解析】:本题说法是错误的，单向链表的每个数据元素的确由两部分组成 ，一部分为该元的数据域（即本身的值），另一部分为其直接后继（或前趋）的存贮位置（地址），又称指针域。 （3）假设在一个计算机系统中，存放一个整型数据需要4个字节。现一个顺序表，数据元素都是整型数据，它第一个元素的地址是0Xfed1，那么第10个元素的地址是（） A） 0Xfeda B） 0Xfef1 C）0Xff17 D） 0Xfef5【解析】直接根据公式Loc(ai)=Loc(ai)+(i-1)*k可以算出来。这个公式不需要死记：第一的地址是0Xfed1，每个元素占4个字节，那么第二个元素的开始地址是0Xfed5，依次递推，那么第10个元素的地址是：fed1+4*9=fed1+24=fef5。注意是十六进制，至于进制的转换那是大一上期的内容，这里不再赘述。注意：链表在逻辑上可能是线性结构，也可能是非线性结构，但在物理上一定是链接存贮结构。 （4）栈和对列可以采用两类存贮结构存贮：一是顺序结构方式 ，二是链接存贮方式存贮（ ） 【解析】:本题说法正确。栈和对列是两种特殊的线性表，它们的逻辑结构和线性表是一致的，但其运算规则受了限制。既然都有是线性表（受限制的），当然符合线性表的物理存贮结构了。注意：在对线性表进行归类时，应将栈和队列归入其中，只不过要记住这两个类型的对象受限制（特征）在什么地方就行了。（5）队列中，允许删除的一端称为：（ ） A 栈底 B 队尾 C 线顶 D 队头 【解析】:本题应选择答案D。队列允许在一端插入，称为队尾，允许在另一端删除称为队头，满足元素“先进先出”原则； (6) 判断题：数据元素在链式存储中，逻辑上相邻的两个元素不可能在物理位置上也相邻【解析】：说法错误。链式存储中不一定相邻，可能是相邻的（7）判断题：子程序调用和递归调用是堆栈结构的典型应用。（ ）【解析】：正确，程序调用正是要求“先调用后返回”，堆栈结构用于保存环境变量等非线性结构非线性结构的逻辑特征是：一个结点元素可能有多个直接前趋和多个直接后趋。 大纲对本节要求不高，具体要求：树、二叉树和图的概念。 同学们在本节复习时，着重于树、二叉树和图这三个概念的联系、区别。 树的两个基本特征：有一个特定结点元素，称为根结点（ROOT），同层结点不相交。 重要术语： 叶子（终端结点）：没有后继的结点 分支结点（非终端结点）：非叶子结点 结点的度：一个结点子树的数目 树的度：树中某结点的度的最大值 子结点：某结点子树的根 父结点：相对于某结点子树的根 兄弟：具有同一父结点的子结点 结点的层次：根结点的层次为1，其它结点的最大层数等于它的父结点的层数加1。 树的深度：一棵树中，结点的最大层次值 有序树和无序树：在树中各子树 T1,T2,···,Tm有相对次序。为有序树，否则为无序树。 森林：n棵树不相交的集合(n0)。任何一棵树删去结点，树就变成森林。 二叉树的基本概念：n个结点的有限集合(n0),这个集合可以是空(即n=0),此时称为空二叉树;或者由一个根结点和两棵相交的被称为根的左子树和右子树组成。 二叉树有五种基本形态和二个特殊情形。 二叉树的三种遍历方式：先序遍历、中序遍历、后序遍历。二叉树与树的不同点：树至少应有一个结点，二叉树可以是空；二叉树结点的子树要区别左子树和右子树，即使某结点只有一棵子树，也要明确是左子树还是右子树。图：由边和点组成的（顶点是有穷、非空的）集合图与树的区别：图中，结点之间的联系是任意的，每个结点都可以与其他的结点相联系。例已知有如下结构：该结构中的结点有可能有多个前趋（后趋），每个结点只与上层的父节点有联系，则该结构属于（ ）A) 栈 B) 线性表 C） 图 D） 树【解析】:按照题里面的描述，显然是一种非线性结构，而又由于结点的联系不是任意的，故可知必为树结构，选D。几个常用算法 大纲所要求掌握的算法分成两类： 查找算法（顺序，二分，分块） 算法 排序算法（插入，选择，冒泡，快速，归并）算法也是大纲要求的一个重点！同学们在这部分进行复习时，着重要理解清楚不同算法的原理及其操作过程！1基本概念 算法：计算机中对数据处理和运算的方法。即将一个实际问题划分为计算机能够解决的一步步细小的步骤，这一方法就称为计算方法。一、 查找算法： 查找算法的基本组成的两个对象：一是查找表，二是给定查找关键字值。查找算法的原理：根据给定的关键值，在一组查找表中确定一个其关键值等于给定值的数据元素。若存在这样的数据元素，则称查找成功，否则称查找失败。顺序查找：就是从查找表的第一个元素开始，逐个把数据元素的关键字值和给定值比较。若有相等，则查找成功，否则，到了最后一个元素也不与给定值相等，则查找失败。顺序查找，又既适用于顺序存贮的查找表进行查找，也适用于对链式存贮结构的查找表进行查找。 顺序查找平均查找速度：为线性表长度的一半。顺序查找优缺点：简单容易实现，但查找效率低。 二分查找（对分法）基本思想：设线性表（alow,alow+1,·····,amid,······,ahigh)中所有元素排列有序，S1：求出中间位置：mid=(low+high)/2 S2：将amid与Key比较 1）若amid=Key，则查找成功， 2）Amid<Key，查找值在mid+1high之间，将mid+1=>low,返回S1步再进行二分查找。 3）Amid>Key，查找值在lowmid-1之间，将mid-1=>high，返回S1步再进行二分查找。 以上过程反复进行，直到找到或未找到mid=low(或high)为 止。二分查找平均查找速度：ASLLog2（n+1）-1。二分查找优缺点：查找次数少，速度快；但必须首先对线性表排序。分块查找：分块查找速度介于顺序和二分法查找之间。要注意：在使用分块查找前，查找表必须先做到块间有序，块内可以无序。 分块查找分两步进行：1）先用待查的关键字对索引关键字表（非查找表）进行二分查找或顺序查找确定待查数据元素可能在哪一块。2）在已确定的那一块（即查找表中的某一块）进行顺序查找。2练习题（判断题） 1）顺序队列不会产生假溢出（ ） 2）二分法查找，查找表中元素越多时，则查找速度优势越能体现出来（ ） 3）顺序查找时，查找表必须要有序。（ ） 4）二分法查找时，查找表必须先为升序状况。（ ） 5）分块查找直接对查找表进行查找。（ ） 6）当分块查找第一步中已经确定了在查找表中哪一块后，则在查找表的这一块中，既可采用二分法又可采用顺序查找方法。（ ） 7）若查找表降序，采用二分法查找，如果中间值比查找关键字值更小，则下一次二分法，应对中间值前面部分进行。（ ） 8）数组中某一元素分别按行优先和按列优先存储时，在内存中的物理位置都一样。（ ）答案：1）× 2） 3 、× 4、× 5、× 6、× 7、 8、×二、 排序算法 2 排序的基本概念：将一组数据元素按其排序码进行递增或递减排列的运算操作。 稳定和非稳定算法：如果待排序的序列中，存在多个排序码相同的数据元素,若经过排序后这些数据元素的相对次序保持不变，则称这种排序算法是稳定的，否则是不稳定的。 内部排序和外部排序：如果整个排序都是在计算机内存中进行的称为内部排序；如果排序还使用到了外存，称为外部排序。注意：二者的区别是：是否使用了外存，而不是排序在什么地方进行的。 注意：对于具体的五种排序算法，一定要清楚每一种的排序原理及其排序过程！我们讲的五种算法都是内部排序方法。 插入排序基本思想：把n个数据元素序列分成 R1,···,Ri-1已排好序的有序部分和Ri,Ri+1,···,Rn未排序的无序两部分。排序部分的第I个元素Ri依次与R1,···,Ri-1 比较，并插入到有序部分的合适位置上，使得R1,···,Ri变为新的有序部分。继续上述过程，直到当Rn与R1,···,Rn-1比较后插入到相应位置，则此序列为一有序序列。 插入排序是稳定排序。 选择排序：第一趟排序是在无序的R1，R2，···，Rn按排序选出最小的元素，将它与R1交换；第二趟排序是在无序的R2， R3 ···，Rn中选出最小的元素，将它与R2交换； 第I趟排序时R1，R2，···，Ri-1已排好序，在当前无序的Ri，Ri+1，···，Rn中再选出最小的元素，将它与Ri元素交 换，使R1，R2，···，Ri成为有序，继续在未排好序的元素中进行上述过程，直到交换到最一个元素，使n个元素排列有序。选择顺序是不稳定排序冒泡法排序：从R1开始，两两比较Ri和Ri+1(i=1,2,···,n-1)的大小，若Ri>Ri+1则交换Ri和Ri+1的位置，第一趟完毕后Rn是排序码中最大的元素，再从R1开始两两比较Ri和Ri+1(i=1,2,···,n-2)的大小，若Ri>Ri+1则交换Ri和Ri+1的位置，第二趟完毕后Rn-1是序列中次大元素，以此类推，进行n-1趟冒泡法排序后，n个元素为一有序数列。冒泡排序是稳定排序。快速排序：从待排序的n个数据元素中任意选取一个元素Ri(通常选取无序序列中的第一个元素)作标准, 调整序中各个元素的位置, 使排在Ri前面的元素的排序码都小于i-key, 排在Ri后的元素都大于Ri-key。通常把这样的一个过程称作一次快速排序。（排序中的难点算法）不稳定排序归并排序：将有n个元素的原始序列看作n个有序子序列, 每个子序列的长度为1 , 然后从第一个子序列开始,把相邻的子序列两两合并, 得到n/2个长度为2 或1的子序列, 这一过程称为一次归并排序, 对第一次归并排序后的n/2个子序列采用上述方法, 继续顺序成对归并, 如此重复当最后得到长度为n的一个子序列时, 该子序列便是原始序列归并排序后的有序序列。该算法稳定。若是对两两有序序列进行归并又称为2-路归并。假设有原始数列：65 97 74 13 27 49 38，各种排序算法经过一趟排序后的 结果如下：（假设都进行从小到大的排序） 大家可以自己先练习一下插入排序：65 97 74 13 27 49 38选择排序：13 97 74 65 27 49 38冒泡排序：65 74 13 27 49 38 97快速排序：38 49 27 74 972练习 一、判断题 1）采用快速排序，排完第一趟序后，固定了位置的那个排队序码左边的元素要比排序码右边的元素更大。（ ） 2）冒泡排序和归并排序都是稳定排序。（ ） 3）选择法排序的原理，是每一次都在无序序列中找出最大值，与无序序列第一个元素进行交换。 4）外部排序是指排序在外存上进行 二、选择题 1）已知有一组元素排序码（49，38，60，90，70，15，30，49），若以第三个元素60作为划分标准，第一趟排序后，排序码的顺序是 A） 49，38，49，90，70，15，30，60 B） 49，38，90，60，70，15，30，49 C） 49，38，49，60，70，15，30，90 D） 49，38，49，30，15，60，70，90 一、判断题 答案：1）× 2） 3）× 4）× 二、选择题 答案：1）D43操作系统操作系统是大纲要求的一个重点、难点。对于本章的复习，要着重从基本概念的理解入手。操作系统部分内容很多，有些概念在理解时比较困难，可以根据我们使用计算机的经验或者根据我们使用的操作系统如WINDOWS和DOS来对应学习。操作系统概述 复习重点： 掌握操作系统的功能和类型。 1理解操作系统在计算机系统中的地位； 操作系统是紧挨着硬件的第一层软件，操作系统是硬件和所有其他软件的接口，也是整个计算机系统的控制和管理中心； 2重点掌握操作系统的功能， 一是从资源管理角度：操作系统是协调、管理计算机的软硬件资源，提高利用率； 二是从用户的角度：操作系统为用户提供使用计算机的环境和服务； 操作系统的具体5大功能： 处理机管理、存储器管理、设备管理、文件管理、作业管理；3掌握操作系统的4个特征。 并发性、共享性、虚拟性、不确定性；4操作系统的分类 批处理操作系统：资源利用率高，作业吞吐量大、操作流程自动化；分时操作系统：响应时间：用户发出命令到系统响应所需时间，是衡量分时操作系统性能的主要指标；实时操作系统：特点:及时响应； 网络操作系统：提供网络通信，提供多种网络服务； 分布式操作系统：强调分布式计算和处理。例211 （判断题） 分时操作系统和实时操作系统都具有及时性和交互性，前者对及时性要求更强，而后者对交互性要求更强。【解析】该说法是错误的。实时操作系统更关心及时性，而分时操作系统是使多个用户以会话方式（交互性）控制自己的程序运行。（判断题）进程中的并发性是指一个处理器在同一时刻可以同时执行多个进程。【解析】：错误。并发，同一时刻只能运行一个进程，只是宏观上是同时的。并行性才是同一时刻可以运行多个进程处理机管理处理机管理是本章的重点！要求的重点是：进程、进程的通讯、进程控制、进程调度及死锁等基本概念的掌握。具体需要复习：1、 掌握进程的概念、进程的基本特征以及进程与程序的区别。程序是算法的描述，是静态的概念；进程是指一次执行过程，是动态过程。进程 有生命周期。进程：可并发执行的程序在给定数据集合上的一次执行过程；是系统进行资源分配和调度的一个独立的基本单位和实体；是执行一个映象程序的总环境。处理器分配和运行的基本单位：进程进程的基本特征：动态性、并发行、独立性、异步性。进程控制块PCB是进程存在的唯一标志。2、 理解进程的三种状态的概念，以及相互之间的转换关系（教材P84页图2.4）。 注意：只有执行和就绪状态（在分时操作中）可以互相转换。执行等待就绪执行.。3、 了解进程调度产生的原因,进程互斥与同步。互斥：因共享资源而产生的制约关系成为进程的互斥。临界资源：以互斥关系使用的共享资源称为临界资源。同步：进程之间通过执行时序上的某种限制而达到相互合作，因相互合作而产生的制约关系称为进程的同步。4、 了解进程通讯的三种方式(消息缓冲、管道、信箱通信)。5、 掌握死锁的概念，以及死锁产生的4个必要条件、解除死锁的方法。死锁：若干进程彼此互相等待对方拥有且又不放的资源，结果是谁也无法得到继续运行所需的全部资源而永远等待下去。产生死锁的原因：1、资源的争夺 2、进程推进顺序不当产生死锁的四个必要条件： 互斥条件、不剥夺条件、部分分配条件、环路条件。解除死锁的方法： 撤销进程法、资源剥夺法。例221（判断题）临界资源是以互斥关系使用的共享资源。 【解析】该说法是正确的。进程的互斥是由多个进程竞争同一共享资源而产生的相互制约的关系。这种因共享资源而产生的制约关系称为进程的互斥。以互斥关系使用的共享资源称为临界资源。例222（判断题）进程可以看成是并发执行的程序在给定数据集合上的一次执行过程，其状态是不可以被改变的。 【解析】该说法是错误的。进程可以看成是并发执行的程序在给定数据集合上的一次执行过程。进程有三种状态，其中，进程就绪与进程执行状态在一定条件可以相互转换，进程执行可以转换到等待状态。进程等待状态可以转换到就绪状态。例223（判断题）进程一经创建并具备运行条件后,即处于等待状态。 【解析】该说法是错误的。进程一经创建并具备运行条件后,即处于就绪状态。例224（判断题）一个进程独占资源而不释放资源称为死锁（ ）。 【解析】该说法是错误的。所谓死锁是指：若干进程彼此互相等待对方进程所拥有且不释放的资源，造成若干进程永远等待的现象。理解了这个死锁的概念，不难判断出该说法的正确予否。例224（选择题）进程的三个基本状态是就绪、执行、等待。由（ ）到执行是由进程调度所引起的。（A）等待 （B）就绪 （C）执行 （D）阻塞【解析】答案选择B。参照例的解析。 对进程和程序的异同描述正确的是（）A)进程和程序都是动态的概念B)程序可以存储在硬盘上，而进程不行C)一个程序可以被多个进程执行，而一个进程不能对应多个程序D)进程和程序都是一组有序的指令的集合答案：B（进程由操作系统调用“创建原语”创建，在内存中） 关于进程的论述错误的是A)进程有3种状态，就绪、执行、等待B)进程的3种状态在程序的控制下转换，一般不自动转换C)操作系统对进程的控制是通过原语来实现的D)PCB是进程存在的唯一标志答案：B（程序中不控制进程，进程由系统控制，在用户看来是自动转换的） 以下关于死锁的论述正确的是A)死锁产生的根本原因是用户程序运行时产生死循环B)在单道、单任务操作系统中不会出现死锁C)预防死锁的方法之一是把所有的资源作为并发共享资源D)只要其他三个条件满足，“环路条件”不一定是死锁产生的必要条件答案：B（多个进程争夺资源才会有死锁，单任务系统只有一个程序在运行，当然不会有死锁现象，也不能把所有资源作为共享资源，因为有些资源的性质决定了它不能被共享）作业管理掌握作业管理的基本概念。1、 作业与进程的区别、联系作业是用户请求系统服务的最大单位作业是用户请求计算机系统执行的一次独立的上机任务。一个作业可以由多个进程完成2、 用户和操作系统的接口：命令接口、系统调用3、 作业控制方式联机作业控制（分时系统）、脱机作业控制（批处理系统）存储管理复习重点：存储管理的功能、任务和方法。1、 地址空间和存储空间经过编译或汇编后形成的目标代码的首地址为零，其他指令中的地址是相对首地址而定，这种相对地址称为逻辑地址或虚拟地址。在内存中存储单元的地址称为物理地址。2、 地址映射（重定位）把逻辑地址变换成物理地址的过程。3、 内存空间的扩充（覆盖与交换技术，重点是虚拟存储技术）扩充：为了解决内存的实际容量小于多道程序所需的内存容量的矛盾，利用大容量的外存空间来逻辑扩充内存，暂时不执行的程序和数据先放在外存中，等到执行时再调入到内存。实现手段：覆盖技术：一个作业的若干程序段，或几个作业的某些部分共享一内存区域交换技术：在内外存之间交换数据虚拟存储管理：采用“部分装入”,“部分交换”的策略。4、 四种存储管理方式（分区、分页、分段、段页式存储管理）具体实现方式以及相互之间的优缺点比较。分页存储管理：（减少内存碎片） 页：逻辑地址空间分为的大小相同的块 块：物理空间划分的和页面大小相等的块 页表：页面和存储块号的对应表 快表：专用的高速缓存，存放页表中访问频繁的表项分段存储管理：（用户的需要） 将作业的地址空间按逻辑意义分段，以段作为内外存交换的单位段页式存储管理：先分段，再将段分为页例 (选择题)存储器管理中，采用覆盖与交换技术的目的是（ ）（A）提高 CPU效率 （B）扩充主存容量（C）节省主存空间 （D）实现主存的共享 【解析】答案选择B。为了解决大作业与小内存的矛盾，常采用“覆盖”与“交换”两种存储管理技术，目的就是要对内存进行逻辑扩充。 关于内存管理论述错误的是A)分区存储管理的一个缺点是容易产生内存碎片，内存利用率不高B)可以采用“拼接”技术来解决内存碎片问题C)覆盖技术指一个作业的若干程序段或几个作业的某些部分共享某一内存区域D)交换技术的引入是为了提高内存和CPU之间交换数据的速度答案：D（交换技术的目的是为了扩充内存的容量） 以下对于虚拟存储管理论述错误的是A)分页存储管理中的“页”是指内存的物理空间B)所谓的“快表”是指地址变换机构中的高速的缓冲存储器C)分段存储管理指：按照程序的逻辑结构把用户的作业分为若干段D)段页式存储管理结合了分页和分段的优点，而且克服了二者的缺点答案：A（页是用户进程分成的小块，内存的小块称为“块”或“页框”）设备管理大纲对本节的要求是：设备管理的功能、任务和方法。具体需要复习：1、 掌握设备的分类：工作特性分：I/O 设备，存储设备资源分配的角度分：独占、共享、虚拟设备2、 了解设备管理的任务和功能： 任务：1 提供方便的外设接口2 充分发挥设备的效率3、 掌握数据传输的三种控制方式，以及相互之间的区别 中断方式：单个字符的传递 DMA方式：整批数据的传送 通道方式：通道一种专门控制IO工作的简单处理机4、 掌握两种技术（缓冲技术和SPOOLing技术）缓冲技术：为了解决外设和CPU速度的匹配问题而引入的缓冲池：多个大小相等的缓冲区连接起来虚拟设备管理：用大容量的快速设备模拟慢速的独占设备SPOOLing技术：一种虚拟设备管理技术假脱机技术，例251（选择题）从资源的管理角度出发，设备可分为独享设备、共享设备和（ ）（A） 分享设备 （B）分时设备 （C）公共设备 （D）虚拟设备【解析】答案选择D。按工作特性，可以将外部设备分为I/O设备和存储设备，从资源分配角度有可以将外部设备分为：独占设备、共享设备、虚拟设备。文件管理复习重点：大纲对本节的要求是：文件管理的功能、任务和方法。具体要求复习：1、 了解文件的分类；2、 了解文件的逻辑、物理结构和组织；逻辑结构：流式文件、记录式文件；物理结构：连续文件、链接文件、索引文件； 连续文件、链接文件适合于顺序存取； 索引文件具有链接文件的优点（插入、删除、修改等操作方便），也可以方便的实现随机存取，缺点是要占用更多的外存空间。3、 了解文件的访问方式；顺序存取方式：严格按照文件基本单位的逻辑排列顺序依次逐个存取；随机存取方式：允许用户根据记录键存取文件的任意记录，或者根据存取命令把读写指针移到指定位置。4、 掌握文件管理的三种方法（位图、链接、索引法）。5、 掌握文件控制块和文件目录。 文件包括两部分：文件说明和文件体文件说明也称为文件控制块（FCB），用于描述文件的文件名、位置等信息的数据结构。文件的目录结构一般有：一级目录结构、二级目录结构、多级目录结构（树形目 录结构）。6、 掌握文件的使用（重点掌握文件的共享、保护、保密）文件的共享常用：连接法（两种连接法）；文件的保护常用：存取控制表、口令、密码（注意其区别）。例 (选择题)对于文件目录，错误的说法是（ ）（A） 文件目录的结构是树型结构（B） 文件目录结构分一级、二级和多级等形式（C） 文件目录是一个文件，称为目录文件(D) 文件目录不是一个文件【解析】答案选择D。文件控制块的集合为文件目录，文件目录也被组织成文件，常成为目录文件。文件目录结构形式有一级目录结构、二级目录结构和多级目录结构。 例262（判断题）为保证计算机的数据安全，常采用口令和密码两种方式。其中口令仅用于进入计算机系统时使用，而密码仅用于创建文件时使用。 【解析】说法错误。口令即可以在进入系统时使用，也可以在存取文件时使用；密码在创建文件时对文件进行编码加密，读文件时通过密码对文件进行译码。文件的逻辑地址到物理地址的转换是由文件的物理结构所决定，操作系统没有采用的结构型是（ A ） A）散列文件 B）连续文件 C）链接文件 D）索引文件4.4 软件工程一 、软件工程的一些基本概念1、 软件工具和软件工程软件工程的核心思想：采用工程化的原理与方法对软件进行计划、开发和修复软件的系统方法软件工具：为提高软件的生产率，促进软件生产的自动化，减轻软件生产者劳动强度而提供的工具2、 程序与软件的概念软件：是程序以及开发、使用和维护程序所需的各种文档。软件包括四个部分：应用程序、系统程序、面向用户的文档、面向开发者的文档。程序只是软件的一小部分注意：程序与软件的区别软件注重的是开发技术，程序注重的是设计方法二、软件的生存期开发模型1、 软件生存期：是从用户提出开发要求开始，到废止不用为止的全过程。软件生存周期的划分：瀑布模型： 计划 需求分析（常用结构化分析方法） 瀑布模型（重点） 开发 设计 总体设计 运行 详细设计(采用结构程序设计方法)编辑测试 计划时期（分析阶段）：分析用户需求、软件系统追求的目标、开发系统的可行性开发时期：主要任务是设计和实现 运行时期：主要任务是软件维护快速原型模型（注意与瀑布模型的区别） 首先建立一个能反映用户主要需求的原型，然后根据用户意见对原型进行改进，反复多次，最后建立符合用户要求的新系统。特点是：1、速度快 2、用户和分析员之间的交流具体化三、需求分析软件的需求分析前要进行： 问题定义和可行性研究 技术可行性、经济可行性、操作可行性需求分析的任务：用户和软件人员双方进一步理解用户的需求，并将双方的共同理解表达为“需求说明书”需求分析阶段是软件生存周期中唯一面向用户“问题”的阶段，是要弄清楚软件要“做什么”的阶段。需求分析常用的方法：结构化分析方法（SA）结构化分析方法：用“数据流图”表达需求，以“数据词典”的形式记录数据的逻辑定义结构化分析方法的基本手段：分解和抽象结构化分析方法采用自顶向下逐层分解的方式来分析问题结构化分析方法的最终目标：建立目标系统的逻辑模型数据流图：描述系统中数据流程的图形工具数据字典：对数据流图中包含的所有元素的定义的集合四、软件设计“怎么做”的阶段，是软件生存周期的中心注意区别：程序设计程序设计是软件设计的实现软件设计的任务：完成系统的结构设计，得到软件设计说明书软件设计的准则：软件结构的准则，模块化的准则，模块独立性的准则(最主要的准则)设计方法和步骤：分为两步：总体设计、详细设计总体设计：将软件需求转化为数据结构和软件的系统结构。软件结构图是描述软件结构的常用工具（程序结构的描述用程序流程图）。总体设计需要交付的是设计文档详细设计：设计每个模块的内部的实现算法，程序员根据详细设计结果写出实际的程序代码，详细设计的结果决定了最终的程序代码质量总体设计的方法：模块化方法，功能分解方法，面向数据流的设计方法，面向数据结构的设计方法，面向对象的设计方法。详细设计方法：结构化程序设计方法程序的三种基本结构：顺序、分支、循环结构化程序设计方法的要求：1、 单入口、单出口2、 只使用顺序、分支、循环三种基本结构3、 采用自顶向下逐步求精的设计方法详细设计的表示工具： 程序流程图 图示（图形）工具 方框图详细设计的表示工具 PAD（问题分析图） 语言工具：伪码（PDL）五、面向对象的程序设计的一些基本概念基本出发点：按照人类认识世界的方法和思维方式来分析和解决问题基本思想：把要构造的系统表示为“对象的集合”以对象为最基本的元素，以对象作为分析问题、解决问题的核心对象：