卓越考研

南京理工大学2007年硕士学位研究生入学考试试题算机专业基地,卓越考研特整理南京理工大学考研真题，为广大考生提供有效的信息支持。

一、数据结构部分（共50分）
（一）填空（每个空格1.5分，共15分）

1、无向图G=（V,E），其中：V={a,b,c,d,e,f}，E={（a,b）,(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}
对该图进行深度优先遍历，得到的顶点序列正确的是（1）

2、该算法为简单选择排序算法。voidsort(Linklist&H){q=H;
while(q){r=q;(2);while(p){if((3))r=p;p=p->next;}q->data←→r->data;(4);}while(q)}//sort
3、满7叉树上的叶子结点数n0和非叶结点数n1之间的关系是：（5）

5、设单循环链表中结点的结构为（data,next），且rear是指向非空的带头结点的单循环链表的尾结点的指针。若要删除链表的第一个结点，则应执行的操作为（7）
6、输入序列为{8，6，4，10，12，9，7}，构造一棵哈夫曼树，该哈夫曼树的带权路径长度WPL为（8）
7、写出表达式a*(b+c)-d的后缀表达式（9）
8、有序表为{5，8，10，15，32，41，45，62，75，77，82，95，100}，用二分查找值为82的数据时，需要比较（10）次。（二）简答（16分，每小题4分）1、拓扑排序算法。2、Prim算法。
3、说出二叉树的五种形式。
4、二叉树中序遍历的递归算法。（三）（9分）输入关键字序列{8，6，4，10，12，9，7}1、（5分）构造一棵二叉平衡（AVL）树，画出树的生成过程和所进行的平衡操作。2、（4分）将上述关键字序列作为初始序列，写出冒泡排序一趟后的序列。（四）算法题（本题10分）：
用类C写一算法，把一个用数组表示的线性表转换成双向循环链表。所用数据类型定义如下：typedef
struct{EelemType*elem;intlength;intlistsize;}sqList;
typedefstruct
DulNode{ElemTypedata;StructDulNode*prior;StructDulNode*next;}DulNode,*DuLinkList;
二、计算机组成原理部分（共50分）（一）单项选择题：（本题共10分，在每小题的四个备选答案中，选出一个正确的答案。）
1、设寄存器位数为8位，机器数采用补码形式（含一位符号位）。对应于十进制数-27，寄存器内为。（H表示十六进制）①27H②9BH③E5H④5AH
2、为了便于实现多级中断，保存现场信息最有效的方式是采用。①通用寄存器②堆栈③Cache④磁盘3、在CPU中，跟踪后继指令地址的寄存器是。①指令寄存器②程序计数器③地址寄存器④状态条件寄存器
5、三种集中式总线控制中，方式对电路故障最敏感。①链式查询②独立请求③中断请求④计数器定时查询6、为了确定下一条微指令的地址而采用的断定方式的基本思想是。①用程序计数器PC来产生后继微指令地址
②用微程序计数器μPC来产生后继微指令地址
③通过微指令中由设计者指定的判别字段控制产生后继微指令地址④通过指令中指定的字段来控制产生后继微指令地址7、当采用对设备进行编址情况下，不需要专门的I/O指令组。①统一编址②单独编址③两者都是④两者都不是8、一般而言，CPU响应DMA请求的条件是。①当前指令周期结束②当前机器周期结束③相关外设处于空闲④累加器的内容为零
（三）设有一个具有20位地址和32位字长的存储器，试问：（3分×3共9分）1、该存储器能存储多少个字节的信息？
2、如果存储器由512K×8位的SRAM芯片组成，需多少片？3、若存储器按字编址，则需多少位地址作芯片选择？
（五）简答题（本题11分）
1、在寄存器—寄存器型，寄存器—存储器型和存储器—存储器型三类指令中，哪类指令的执行时间最长？哪类指令的执行时间最短？为什么？（本小题4分）2、在“右移-加减”迭代的补码两位乘法运算过程中，给定二进制数据的数值部分的位数为n时，需要多少步骤完成乘法运算？（本小题4分）
3、请简述DMA控制方式的数据传送过程？（本小题3分）三、操作系统部分（共50分。若选择此部分，请在答题纸上标明）（一）单项选择题（每小题1分，共20分）1、在下列性质中，不是分时系统特征的是。A)交互性B)独立性C)多路性D)成批性2、引入多道程序设计的主要目的在于。A)有利于代码共享，减少主、辅存信息交换量B)提高实时响应速度
C)充分利用CPU，减少CPU等待时间D)充分利用存储器
3、在下面的进程状态转换过程中，可能发生的转换有。（1）运行→就绪（2）运行→阻塞（3）阻塞→运行（4）运行→终止A）（2）（3）（4）B）（1）（2）（3）C）（1）（2）（4）D）（2）（4）
4、分时系统中，一个运行进程用完了分给它的时间片后，还未完成计算任务，它的状态将变为。A）就绪B）阻塞C）运行D）挂起
5、在非剥夺调度方式下，运行进程执行V原语后，其状态。A）不变B）要变C）可能要变D）可能不变6、对于大量缓冲区的管理，采用多个生产者-多个消费者方式解决同步或互斥时，通常需要用个信号量。A）2B）3C）4D）5
7、一个正在访问临界资源的进程由于申请等待I/O操作而被中断时。A）可以允许其他进程进入与该进程相关的临界区B）不允许其他进程进入任何临界区C）可以允许其他就绪进程抢占处理器，继续运行D）不允许任何进程抢占处理器8、如果信号量的当前值为-2，则系统中在该信号量上等待的进程数目是。A）2B）3C）4D）5
9、下面的情况中，进程调度可能发生的时机有。
（1）正在执行的进程运行完毕（2）正在执行的进程提出I/O请求后进入等待状态（3）就绪队列中某个进程的优先级高于当前正在运行进程的优先级（4）有某个进程从阻塞状态转换成就绪状态A）（1）（2）（3）B）（1）（2）（3）（4）C）（1）（2）（4）D）（1）（3）（4）
10、主要在分时系统中使用的一种调度算法是。A）先来先服务B）短作业优先C）时间片轮转法D）优先数法11、在死锁预防方法中，系统要求所有进程在运行前一次性的申请在整个运行过程中所需要的全部资源，得到满足后才得以运行，并在运行期间不允许提出资源请求。这种方法破坏产生死锁必要条件中的。A）互斥条件B）请求和保持条件C）不剥夺条件D）环路等待条件12、在多道程序系统中，由于可共享的资源不足，可能会出现死锁。有时，不恰当的也可能引起死锁。A）进程调度算法B）资源分配方法C）进程推进顺序D）进程优先权
13、在页式管理中，每个页表中的表项实际上是用于实现。A）内存单元B）静态重定位C）动态重定位D）加载14、有关资源分配图中存在环路和死锁关系正确的说法是。A）图中无环路则系统可能存在死锁B）图中有环路则系统肯定存在死锁C）图中有环路则系统可能存在死锁，也可能不存在死锁D）以上说法都不对
16、下面关于虚拟存储器的论述中，正确的是。
A）要求作业运行前，必须全部装入内存，且在运行中必须常驻内存B）要求作业运行前，不必须全部装入内存，且在运行中不必常驻内存C）要求作业运行前，不必须全部装入内存，但在运行中必须常驻内存D）要求作业运行前，不必须全部装入内存，但在运行中不必常驻内存
17、在现代操作系统中，为了提高操作系统的可适应性和可扩展性，都实现了
，使得用户所编写的程序与实际使用的物理设备无关。
A）虚拟设备B）缓冲管理C）设备独立性D）设备分配18、如果文件系统中有两个文件重名，不应采用。A）单级目录结构B）两级目录结构C）树型目录结构D）多级目录结构19、特权指令。A）是可能影响系统安全的一类指令
B）既允许操作系统程序使用，又允许用户程序使用C）是管态和目态运行的基本单位D）是一种存储保护方法20、并发性是指若干事件在发生。A）同一时刻B）同一时间间隔内C）不同时刻D）不同时间间隔内（二）填空（每空1分，共8分）
1、虚拟设备是通过（1）技术把独享设备变成能为若干用户共享的设备。2、UNIX系统采用的空闲盘块管理方法是（2）。
3、用户进程从目态（常态、用户态）转换为管态（特态、系统态）的唯一途径是（3），当该用户进程需要使用打印机进行输出时，进程的状态由（4）变为（5），在打印结束后，会产生一个打印中断，此时进程的状态会变为（6）。4、在磁盘调度策略中有可能使I/O请求长期等待的调度算法是（7）。5、在操作系统中，用户界面指的是命令接口、程序接口和（8）。（三）解答题（共14分）1、（3分）在一个请求页式存储管理系统中，某作业所涉及的页面依次为3，2，1，4，4，5，3，4，3，2，1，5，并已知分给该作业的主存物理块是3，则按照FIFO调度算法将产生次缺页中断。按照LRU调度算法将产生次缺页中断。按照OPT调度算法将产生次缺页中断。（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）2、（3分）设某移动头磁盘共有200道，编号为0-199，磁头当前处在130道上，且正向0磁道方向移动，对于如下盘请求序列：70，120，80，160，60，150.当用FCFS（先来先服务），SSTF（最短寻道时间优先）和SCAN（扫描或电梯调度）来安排磁头移动时，移动的总量分别是，，。
（四）叙述题（每小题4分，共8分）
1、现代操作系统挂起状态是何含义？引入的目的是什么？
2、请叙述银行家算法的主要思想。它是否能用来解决实际中的死锁问题，请解释说明。