南京航空航天大学计算机考研试题

1、南京航空航天大学计算机考研试卷操作系统部分2000年操作系统考研试卷一、名词术语解释 每小题 4分，共 20分）1、系统调用与操作系统内核2、进程与线程3、页表与快表4、设备独立性5、文件控制块与索引节点二、填空 每小题 2分，共 10分）1如果在设备处理时设置 I/O进程，则不需要I/O进程工作时，I/O进程处于 状态。2、系统中有 3个进程，每个进程需 2台打印机，如果系统配有 4台打印机，则系统 _出现死锁的情况 本题要判断出现死锁的可能性）。3、 设磁盘的I/O请求队列中的磁道号为：98, 183, 37, 122, 14, 124, 65, 67,磁头初始 位置为50,若采用FCFS

2、先来先服务）和SSTF最短寻道时间优先）的磁盘调度算法，磁 头分别移动 、 磁道。4、 可以被多个进程在任何时刻共享的代码必须是 。5、 为了实现CPU与外部设备的并行工作，系统引入了 硬件机制。三、回答下列问题 每小题 8分,共 48分）1、在操作系统中,何为虚拟存储器、虚拟设备、虚拟处理机？2、 进程具有哪几种基本状态：对于每一种可能有的状态转换。给出一种状态转换的原因。需图示说明）3、 何为磁盘高速缓存：说明它为什么会提高磁盘的I/O速度。4、说明装入时动态链接 Load-time Dynamic Linking ）与运行时动态链接 Run-time Dynamic Linking ）这

3、两种程序链接方法之间差别。5、 试从物理概念上来说明记录型信号量和wait 与 signal 操作？6、 简述 Intel80386 实方式寻址和保护方式寻址时,内存地址的形成过程,最大寻址空间各为多少？四、10分）在测量控制系统中的数据采集任务,把所采集的数据送一单缓冲区：计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两者共享单缓冲的同步操 作算法。五、12分）某数据处理任务，要在 PC机上对40M字节的数据文件 集中放在硬盘上）进行 排序，文件中每记录的长度为 50个字节了。某学生编艘桓鼋鍪褂 ？40K常规内存的排序程序 ,速度很慢。问 ：1、该排序程序运行时,时间主要花

4、费在什么操作上？2、若将 40M 扩展内存 ExtendedMemory ）设置为虚拟盘,运行速度会有多大提高？为什么？请给出使用虚拟盘后的排序算法,仅需用简练的语言或粗框图描述该算法。2001 年操作系统考研试卷测试科目 ：操作系统说明 ：答案一律写在答题纸上一、名词术语解释 每小题 3分共 24分）1 、临界资源和临界区2、进程控制块 PCB3、多道程序设计4、计算机操作系统5、用户态与核心态6、SPOOLing 系统7、逻辑文件和物理文件8、进程映像二、填空 每小题2分，共 10分）1在具有两级页表的分页存储管理系统中，CPU每次要存取一个数据时，须访问 _次内存。2、产生死锁的必要条件

5、是 :3、 在一个请求分页存储管理系统中，某程序的页面走向为:7， 0， 1， 2， 0， 3， 0， 4， 2，3， 0， 3， 2， 1， 2， 0， 1， 7， 0， 1。假设分得的页框数是 3，并且开始时页框中是空的， 则分别采用最佳转换算法和LRU页面转换算法，在访问过程中发生缺页中断的次数分别是-和 。4、 一台计算机有10台磁带机被m个进程竞争，每个进程最多需要三台磁带机，那么m为_ 时，系统没有死锁的危险。5、磁盘请求以 10,22,20,2， 40,6， 38柱面的次序到达磁盘驱动器。寻道时每个柱面移动需要6ms,则采用先到先服务算法的寻道时间为 ;采用电梯算法 起始移动方向

6、向外）的寻道时间为 。假设磁头开始位置在柱面 20）三、回答下列问题 每小题 7分,共 42分）1、何谓系统的安全状态,试说明银行家算法避免死锁的原理？2、 在实现文件系统时把文件目录的目录项分解成两部分:索引结点和符号名目录项,有什 么好处？ 需图示说明）3、在存储管理中分页与分段的主要区别是什么？分页与分段两种方法中,哪个更易于实现 共享,为什么？4、 在设备管理中引入单缓冲，如果从磁盘把一块数据输入到缓冲区中花费的时间为B ;把 缓冲区中的数据送到用户区，所花费的时间为 M ; CPU对数据进行处理的时间为 C，则系统 对每一块数据的处理时间是多少？要求写出由 B，C，M组成的表达式，并

7、说明其中的道理5、提高磁盘I/O速度的方法有哪些？并分别加以简单的说明。6、程序顺序执行和并发执行分别有哪些牲？程序并发执行的条件是什么？对于下列语句, 哪些能并发执行,哪些不能,说明理由。S1:a=5-x; S2:b=a*x ; S3:c=4*x ; S4:d=b+c ; S5:e=d+3 ;四、14分）一个主修动物行为学、辅修计算机科学的学生参加了一个课题,调查花果山的猴子是否能被教会理解死锁。他找到一处峡谷,横跨峡谷拉了一根绳索假设为南北方向）,这样猴子就可以攀着绳索越过峡谷人。只要它们朝着相同的方向,同一时刻可以有 多只猴子通过。但是如果在相反的方向上同时有猴子通过则会发生死锁这些猴子

8、将被卡在绳索中间,假设这些猴子无法在绳索上从另一只猴子身上翻过去）。如果一只猴子相越 过峡谷,它必须看当前是否有别的猴子在逆向通过。请使用信号量写一个避免死锁的程序 来解决该问题。五、10分）在分页式存储管理中,什么叫快表,说明其工作原理和过程,画出具有快表 的地址变换机构。2002年操作系统考研试卷一、填空 每小题5分，共 20分）注意:答题时先给出填空内容，再作必要的说明）1、设系统中仅有一个资源类，其中共有3个资源实例，使用此类资源的进程共有3个，每个进程至少请求一个资源，它们所需资源最大量的总和为X ，则发生死锁的必要条件是 :2、在一个请求分页系统中，采用先进先出页面置换算时，假如一

9、个作业的页面走向为1， 2,3, 4, 1, 2, 5, 1, 2, 3, 4, 5,当分配给该作业的物理块数M分别为3和4时，访问过程中发生的缺页次数为 和。假定开始时，物理块中为空）3、 设系统中有三种类型的资源 A、B、C）和五个进程P0, P1, P2, P3, P4）,某时刻 的状态如下 :根据银行家算法可知，该时刻存在着一个安全序列 :_。4、 根据 Bernstein 条件 程序能并发执行，且具有可再现性的条件），则如下4条语句中 :S1: a:=x+yS2:b:=z+1S3:c:=a-bS4:w:=c+1S1和S2两条语句 并发执行，S3和S4两条语句 并发执行。本小题填空时考

10、虑 :是否可以并发执行）二、回答下列问题 每小题 6分,共 30分）1 、什么要引入设备独立性？如何实现设备独立性？2、举例说明在分页系统中,如何实现内存共享？要求图示说明。3、从用户角度看,引入线程后有何好处？4、 生产者一消费者问题的同步算法中，为什么颠倒生产者进程中的两个P操作的次序，将 导致进程死锁？5、Intel80386在保模式下工作时，为什么对内存有保护作用？三10分）进程P1和P2通过两个缓冲区给进程 P11、P12、P21、P22传递信息，进程 P11、P12取进程P1 的信息，进程P21、P22取进程P2的信息。假定这两个缓冲区一样大小，所要传递的信息也 与缓冲区一样大，同

11、一时刻只能由一个进程往缓冲区中送信息或取信息。试用PV操作来实现这6个进程之间的同步与互斥关系，只要求写出进程P1与P11的同步算法。四、10分）在DOS、WINDOWS操作系统中使用的FAT文件系统中，一个文件使用的磁盘空间以簇为 单位进行分配，并且将一个文件使用的全部簇组成一个链表放在FAT表 文件分配表）中；在UNIX中，一个文件使用的磁盘块号放在I结点 索引结点）中。试分析比较这两种典型的文件物理结构,在分析时要考虑到文件大小不同时对性能的影响。五、15分）用户程序在需要OS提供某种服务时，是通过系统调用来完成的。请以一个具体例子如读写磁盘、在显示屏幕上显示字符等）说明系统调用的处理过

12、程。你可以按照一个你熟悉的操作系统 如UNIX、WINDOWS、LINUX ）来说明，也可以介绍你自己根据某个硬件环境 设计的系统调用的处理过程。六、15分）页表设计。某系统采用了两级页表机制,可使页表所占用内存尽量少,分页地址变换机构如下图 :页目录表共 1024项，每个页表 1024项。地址转换时，先由分段部件生成线性地址，再由上 面所述的分页部件，根据线性地址中的页目录索引在页目录表中找相应的项，该项中为所 需页表在内存的块号，找到该页表后，然后按第2112位的页表索引找到所需页的内存块号，把它与 12位偏移相加得到 32位的物理地址。设系统有如表6.1中所示的10个段，已知:1 8段从

13、内存的200000H处开始由低地址到高地址连续存放，映射到3G+ 4M开始的线性地址空间；9段<缓冲区）放在400000H开始的内存， 映射的线性地址同物理地址；显存从 B8000H开始，映射到3G开始的线性地址空间。本题 用的页目录表和页表如表 6.2中所示，所有页表连续存放。表6.11、请按下面的格式设计页目录表和页表表6.22、线性地址为:C0401010H、C0404010H、C0414010H，则物理地址是多少，所在段的段名是什么？数据结构与程序设计考研试卷2000年数据结构与程序设计考研试卷测试科目 :数据结构与程序设计说明 :下列每道题 10分，编程题可用任何一种编程语言编

14、写1、叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。179，208，93，306，55，859，984，9，271，332、 什么是哈夫曼树？试证明有 n个叶子的哈夫曼树共有2n-1个结点。3、推导并求解n阶Hanoi塔问题至少执行move操作次数。4、 设有三对角矩阵<Aij ） n呦，将其三对角线上元素逐行存于数组B : 1.m中，使Bk=A ij求:<1 ）用i,j表示k的下标变换公式<2）用k表示i,j的下标变换公式5、 输入下列整数序列，画出建立的二叉排序树，最后分别图示将其中50，86删除后的二叉 排序树86，50，78，59，90，64，55，23，

15、100，40，80，456、设整数序列a1, a2,，an,给出求解最大值的递归程序。7、编程求解无向图G的所有连通分量。8、设有带头结点的单链表 L,编程对表中任一值只保留一个结点，删除其余值相同的结点。9、 设T是一棵n元树，Tb是T的孩子兄弟表示 < 二叉链表）的二叉树，试编程由Tb计算T的 高度。 <要求用非递归方法实现）10、 设以整数序列a1, a2, a3, a4作为栈S的输入，利用push, pop操作，写出所有可能的 输出,并编程实现算法。南京航空航天大学 2002年数据结构与程序设计试卷一、将下列稀疏矩阵的非零元素表示成三元组的形式和十字链表的形式。二、设一棵二

16、叉树的层次遍历序列为ABDEGHJK ,中序遍历序列为 GDJHKBEA 。<1）画出这棵二叉树示意图<2）说明建立这棵二叉树的原理三、回答下列B树<有些教材中称为B-树）问题：<1） 一棵4阶4层 <根为第一层，叶子为第二层）的B树，至少有多少关键字，至多有多少关键字<2)在含有n个关键字的m阶B树中进行查找时，最多访问多少个结点。四、哈希表中使用哈希函数 H<key ) =3*key%11, 并采用开放定址法处理冲突，随机探测再散列的下一地址公式为:d1=H (key >di=( di-1 +7 * key > % 11 <1=2,3)试在0到10的散列地址空间中对关键字序列<22， 41， 53， 46， 30， 13， 01， 67)画出 Hash表示意图，并求在等概率情况下查找成功的平均查找长度。五、求出一棵滿k叉树的叶子结点数n和所有非叶子结点数 m之间的关系，给出求解过程。六、已知两个链表 A和B，其元素值递增排列。编程，将 A和B合并成一个递减有序 < 相同值 只保留一个)的链表C,并要求