您的当前位置:首页正文

计算机考研模拟试题操作系统1

来源:个人技术集锦


一、名词术语解释(每小题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(先来先服务)和SSTF(最短寻道时间优先)的磁盘调度算法,磁头分别移动__________、__________磁道。

4、可以被多个进程在任何时刻共享的代码必须是__________。

5、为了实现CPU与外部设备的并行工作,系统引入了__________硬件机制。 三、回答下列问题(每小题8分,共48分)

1、在操作系统中,何为虚拟存储器、虚拟设备、虚拟处理机? 2、进程具有哪几种基本状态:对于每一种可能有的状态转换。给出一种状态转换的原因。(需图示说明)

3、何为磁盘高速缓存:说明它为什么会提高磁盘的I/O速度。 4、说明装入时动态链接(Load-time Dynamic Linking )与运行时动态链接(Run-time Dynamic Linking )这两种程序链接方法之间差别。

5、试从物理概念上来说明记录型信号量和wait 与 signal 操作?

6、简述Intel 80386 实方式寻址和保护方式寻址时,内存地址的形成过程,最大寻址空间各为多少? 四、(10分)在测量控制系统中的数据采集任务,把所采集的数据送一单缓冲区:计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两者共享单缓冲的同步操作算法。 五、(12分)某数据处理任务,要在PC机上对40M字节的数据文件(集中放在硬盘上)进行排序,文件中每记录的长度为50个字节了。某学生编艘桓鼋鍪褂?40K常规内存的排序程序,速度很慢。问:

1、该排序程序运行时,时间主要花费在什么操作上?

2、若将40M扩展内存(Extended Memory)设置为虚拟盘,运行速度会有多大提高?为什么?请给出使用虚拟盘后的排序算法,仅需用简练的语言或粗框图描述该算法。

2001年操作系统考研试题 考试科目:操作系统

说明:答案一律写在答题纸上

一、名词术语解释(每小题3分共24分) 1、临界资源和临界区 2、进程控制块PCB

3、多道程序设计 4、计算机操作系统 5、用户态与核心态 6、SPOOLing 系统

7、逻辑文件和物理文件 8、进程映像

二、填空(每小题2分,共10分) 1、在具有两级页表的分页存储管理系统中,CPU每次要存取一个数据时,须访问__________次内存。 2、产生死锁的必要条件是:____________________________________________________________

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,则采用先到先服务算法的寻道时间为__________;采用电梯算法(起始移动方向向外)的寻道时间为__________。(假设磁头开始位置在柱面20) 三、回答下列问题(每小题7分,共42分)

1、何谓系统的安全状态,试说明银行家算法避免死锁的原理?

2、在实现文件系统时把文件目录的目录项分解成两部分:索引结点和符号名目录项,有什么好处?(需图示说明)

3、在存储管理中分页与分段的主要区别是什么?分页与分段两种方法中,哪个更易于实现共享,为什么?

4、在设备管理中引入单缓冲,如果从磁盘把一块数据输入到缓冲区中花费的时间为B;把缓冲区中的数据送到用户区,所花费的时间为M;CPU对数据进行处理的时间为C,则系统对每一块数据的处理时间是多少?要求写出由B,C,M组成的表达式,并说明其中的道理。

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分)一个主修动物行为学、辅修计算机科学的学生参加了一个课题,调查花果山的猴子是否能被教会理解死锁。他找到一处峡谷,横跨峡谷拉了一根绳索(假设为南北方向),这样猴子就可以攀着绳索越过峡谷人。只要它们朝着相同的方向,同一时刻可以有多只猴子通过。但是如果在相反的方向上同时有猴子通过则会发生死锁(这些猴子将被卡在绳索中间,假设这些猴子无法在绳索上从另一只猴子身上翻过去)。如果一只猴子相越过峡谷,它必须

看当前是否有别的猴子在逆向通过。请使用信号量写一个避免死锁的程序来解决该问题。 五、(10分)在分页式存储管理中,什么叫快表,说明其工作原理和过程,画出具有快表的地址变换机构。

操作系统考研试题

一、填空(每小题5分,共20分)

(注意:答题时先给出填空内容,再作必要的说明)

1、设系统中仅有一个资源类,其中共有3个资源实例,使用此类资源的进程共有3个,每个进程至少请求一个资源,它们所需资源最大量的总和为X,则发生死锁的必要条件是:_________。

2、在一个请求分页系统中,采用先进先出页面置换算时,假如一个作业的页面走向为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+y

S2:b:=z+1

S3:c:=a-b

S4:w:=c+1

S1和S2两条语句_________并发执行,S3和S4两条语句_________并发执行。(本小题填空时考虑:是否可以并发执行)

二、回答下列问题(每小题6分,共30分)

1、什么要引入设备独立性?如何实现设备独立性?

2、举例说明在分页系统中,如何实现内存共享?要求图示说明。

3、从用户角度看,引入线程后有何好处?

4、生产者-消费者问题的同步算法中,为什么颠倒生产者进程中的两个P操作的次序,将导致进程死锁?

5、Intel 80386在保模式下工作时,为什么对内存有保护作用?

三(10分)

进程P1和P2通过两个缓冲区给进程P11、P12、P21、P22传递信息,进程P11、P12取进程P1的信息,进程P21、P22取进程P2的信息。假定这两个缓冲区一样大小,所要传递的信息也与缓冲区一样大,同一时刻只能由一个进程往缓冲区中送信息或取信息。试用PV操作来实现这6个进程之间的同步与互斥关系,只要求写出进程P1与P11的同步算法。 四、(10分)

在DOS、WINDOWS操作系统中使用的FAT文件系统中,一个文件使用的磁盘空间以簇为单位进行分配,并且将一个文件使用的全部簇组成一个链表放在FAT表(文件分配表)中;在UNIX中,一个文件使用的磁盘块号放在I结点(索引结点)中。试分析比较这两种典型的文件物理结构,在分析时要考虑到文件大小不同时对性能的影响。 五、(15分)

用户程序在需要OS提供某种服务时,是通过系统调用来完成的。请以一个具体例子(如读写磁盘、在显示屏幕上显示字符等)说明系统调用的处理过程。你可以按照一个你熟悉的操作系统(如UNIX、WINDOWS、LINUX)来说明,也可以介绍你自己根据某个硬件环境设计的系统调用的处理过程。 六、(15分)

页表设计。某系统采用了两级页表机制,可使页表所占用内存尽量少,分页地址变换机构如下图:

页目录表共1024项,每个页表1024项。地址转换时,先由分段部件生成线性地址,再由上面所述的分页部件,根据线性地址中的页目录索引在页目录表中找相应的项,该项中为所需页表在内存的块号,找到该页表后,然后按第21-12位的页表索引找到所需页的内存块号,把它与12位偏移相加得到32位的物理地址。

设系统有如表6.1中所示的10个段,已知:1-8段从内存的200000H处开始由低地址到高地址连续存放,映射到3G+4M开始的线性地址空间;9段(缓冲区)放在400000H开始的内存,映射的线性地址同物理地址;显存从B8000H开始,映射到3G开始的线性地址空间。本题用的页目录表和页表如表6.2中所示,所有页表连续存放。

表6.1

1、请按下面的格式设计页目录表和页表

表6.2

2、线性地址为:C0401010H、C0404010H、C0414010H,则物理地址是多少,所在段的段名是什么?

数据结构与程序设计考研试题

2000年数据结构与程序设计考研试题

考试科目:数据结构与程序设计

说明:下列每道题10分,编程题可用任何一种编程语言编写

1、 叙述基数排序算法,并对下列整数序列图示其基数排序的全过程。 179,208,93,306,55,859,984,9,271,33

2、 什么是哈夫曼树?试证明有n个叶子的哈夫曼树共有2n-1个结点。 3、 推导并求解n阶Hanoi塔问题至少执行move操作次数。 4、设有三对角矩阵(Aij)n×n,将其三对角线上元素逐行存于数组B[1..m]中,使B[k]=Aij 求:(1)用 i,j 表示k的下标变换公式 (2)用k表示i,j 的下标变换公式

5、输入下列整数序列,画出建立的二叉排序树,最后分别图示将其中50,86删除后的二叉排序树

86,50,78,59,90,64,55,23,100,40,80,45

6、设整数序列a1,a2,… ,an,给出求解最大值的递归程序。 7、编程求解无向图G的所有连通分量。

8、设有带头结点的单链表L,编程对表中任一值只保留一个结点,删除其余值相同的结点。 9、设T是一棵n元树,Tb是T的孩子兄弟表示(二叉链表)的二叉树,试编程由Tb计算T的高度。(要求用非递归方法实现)

10、设以整数序列a1,a2,a3,a4作为栈S的输入,利用push,pop操作,写出所有可能的输出,并编程实现算法。

南京航空航天大学2002年数据结构与程序设计试题

一、将下列稀疏矩阵的非零元素表示成三元组的形式和十字链表的形式。

二、设一棵二叉树的层次遍历序列为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 (I=2,3…..)

试在0到10的散列地址空间中对关键字序列(22,41,53,46,30,13,01,67)画出Hash表示意图,并求在等概率情况下查找成功的平均查找长度。

五、求出一棵滿k叉树的叶子结点数n和所有非叶子结点数m之间的关系,给出求解过程。 六、已知两个链表A和B,其元素值递增排列。编程,将A和B合并成一个递减有序(相同值只保留一个)的链表C,并要求利用原表结点。

七、已知一棵二叉树用二叉链表存储,root 指向根结点,p指向树中任一结点。编程,输出从root 到p 之间路径上的结点。

八、已知一棵树用孩子-兄弟链表存储。编程,计算该树的叶子数。

九、设有n 个整数组成的序列,每个整数为-1,0,1之一。编写一个时间复杂度为O(n)的算法,使该序列按负数、零、正数的次序排好。

十、已知n个顶点的带权图用邻接矩阵表示,编写函数,实现用Kruskal算法构造最小生成树,要求对函数中所使用的变量和内容做详细的注释说明。

因篇幅问题不能全部显示,请点此查看更多更全内容