南京航空航天大学2000年操作系统考研试题
 
作者：Alex    考研来源：原创    点击数：    更新时间：2005-4-23 
 
  
考试科目：操作系统

一、名词术语解释（每小题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个字节了。某学生编了一个仅使用640K常规内存的排序程序，速度很慢。问：
1、该排序程序运行时，时间主要花费在什么操作上？
2、若将40M扩展内存（Extended Memory）设置为虚拟盘，运行速度会有多大提高？为什么？请给出使用虚拟盘后的排序算法，仅需用简练的语言或粗框图描述该算法。
 

南京航空航天大学2002年操作系统考研试题
 
作者：Alex    考研来源：原创    点击数：    更新时间：2005-4-23 
 
  
一、填空（每小题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，则物理地址是多少，所在段的段名是什么？

南京航空航天大学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算法构造最小生成树，要求对函数中所使用的变量和内容做详细的注释说明。
 

南京航空航天大学2001年数据结构与程序设计考研试题
 
作者：Alex    考研来源：原创    点击数：    更新时间：2005-4-23 
 
  
考试科目：数据结构与程序设计

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

一、根据下图所示广义表的存储结构，写出此图表示的广义表。

二、试找出分别满足下列条件的所有二叉树
（1）先序序列和中序序列相同
（2）中序序列和后序序列相同
（3）先序序列和后序序列相同
三、根据下图所示的一棵3阶B树（有些教材中称为B-树）
（）分别给出插入关键字2，12，16，17和18之后的结果。
（）分别给出在原图上删除8和9之后的结果。
 

四、对下图所示的有向图
 

（1）画出它的邻接表示意图
（2）根据邻接表写出其拓扑排序序列
五、用栈实现将中缀表达式8-（3+5）*（5-6/2）转换成后缀表达式，画出栈的变化过程。
六、已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。
七、已知一棵二叉树用二叉链表存储，编写递归函数，判断其是否是平衡二叉树。
八、编写程序将一整数序列中所有负数移到所有正数之前，要求时间复杂度为O（n）
九、已知n个顶点的有向图用邻接矩阵表示，编写函数，计算每对顶点之间的最短路径。
十、编程，判断一棵用二叉链表表示的二叉树是否是完全二叉树。 

南京航空航天大学2001年操作系统考研试题
 
作者：Alex    考研来源：原创    点击数：    更新时间：2005-4-23 
 
  
考试科目：操作系统
说明：答案一律写在答题纸上
一、名词术语解释（每小题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分）在分页式存储管理中，什么叫快表，说明其工作原理和过程，画出具有快表的地址变换机构。

南京航空航天大学2000年数据结构与程序设计考研试题
 
作者：Alex    考研来源：原创    点击数：    更新时间：2005-4-23 
 
  
考试科目：数据结构与程序设计
说明：下列每道题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操作，写出所有可能的输出，并编程实现算法。
 

南京航空航天大学2000年操作系统考研试题
 
作者：Alex    考研来源：原创    点击数：    更新时间：2005-4-23 
 
  
考试科目：操作系统

一、名词术语解释（每小题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个字节了。某学生编了一个仅使用640K常规内存的排序程序，速度很慢。问：
1、该排序程序运行时，时间主要花费在什么操作上？
2、若将40M扩展内存（Extended Memory）设置为虚拟盘，运行速度会有多大提高？为什么？请给出使用虚拟盘后的排序算法，仅需用简练的语言或粗框图描述该算法。