卓越考研

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

一、数据结构部分（共35分）（一）、选择（每项1分，共15分）
1、快速排序算法在最好情况下的时间复杂度。A)O(n)B)O(n2)C)O(log2n)D)O(logn)2、有n个顶点，e条边的图G采用邻接表存储，则拓扑排序算法的时间复杂度为。A)O(n)B)O(n+e)C)O(n*e)D)O(n2)
3、设双向循环链表中结点的结构有数据域data，指针域pre和next，链表不带头结点。若在指针p所指结点之后插入结点s，则应执行下列操作。A)p->next=s;s->pre=p;p->next->pre=s;s->next=p->next;B)p->next=s;p->next->pre=s;s->pre=p;s->next=p->next;C)s->pre=p;s->next=p->next;p->next=s;p->next->pre=s;D)s->pre=p;s->next=p->next;p->next->pre=s;p->next=s;
4、输入序列为{20，35，……}，构造平衡二叉树，当在树中插入值30时发生不平衡，则应进行的平衡旋转是。A)LLB)RLC)LRD)RR
5、二叉树的先序和中序遍历序列分别是ABCDEFGH,CBEDFAGH,则后序遍历序列是
。
A)HGFEDACBB)GHEDFCBAC)CEFDBHGAD)HGAFDEBC6、前序遍历和后序遍历相同的二叉树为前序遍历和中序遍历相同的二叉树为中序遍历和后序遍历相同的二叉树为A)一般二叉树
B)空树或根结点无左孩子的二叉树C)空树或只有根结点的二叉树
D)空树或根结点无右孩子的二叉树E)空树或缺左子树的单支二叉树F)空树或缺右子树的单支二叉树
7、设Hash表的表长为14，Hash函数是H（key）=key%11，现表中已有15，38，
61和84四个数，其余位置空。处理冲突采用线性探测再散列，现插入49，则它的位置是。A)8B)3C)5D)9
8、对于无向图的生成树，下列说法不正确的是。A)生成树是遍历的产物B)从同一顶点出发所得的生成树相同C)生成树是图的极小连通子图D)不同遍历方法所得到的生成树不同
9、有向图G=(V,A),其中V={a,b,c,d,e},A={<a,b>,<a,c>,<d,c>,<d,e>,<b,e>,<c,e>},对该图进行拓扑排序，下面序列中哪一个不是拓扑序列。A)a,d,c,b,eB)d,a,b,c,eC)a,b,d,c,eD)a,b,c,d,e10、下列排序算法中，排序在一趟结束后不一定能选出一个元素放在其最终位置上。A)希尔B)冒泡C)选择D)直接插入11、对线性表进行二分查找时，要求线性表必须。A)以顺序方式存储B)以链接方式存储C)以顺序方式存储，且数据有序D)以链接方式存储，且数据有序

12、稀疏矩阵一般的压缩存储方法有。A)三元组和二维数组B)散列和十字链表C)三元组和散列D)三元组和十字链表

13、链表不具有的特点是。A)可以随机访问任一元素B)插入和删除不需要移动元素C)不必事先估计存储空间的大小D)所需空间与线性表的长度成正比

二、操作系统部分（共35分）（一）、单项选择题（每题1分，共15分）1、进程与程序之间有密切联系，但又是不同的概念。二者的一个本质区别是。A)程序是静态概念，进程是动态概念B)程序是动态概念，进程是静态概念C)程序保存在文件中，进程存放在内在中D)程序顺序执行，进程并发执行2、下列进程状态的转换中，哪一个是不正确的。A)就绪->运行B)运行->就绪C)就绪->阻塞D)阻塞->就绪3、以下存储管理技术中，支持虚拟存储器的技术是。A)请求分页技术B)可重定位分区法C)动态分区法D)对换技术4、系统出现死锁的原因是。A)进程进入临界区B)有多个封锁的进程同时存在C)若干进程因竞争资源无休止地循环等待，且都不释放已占有的资源D)资源数大大少于进程数，或进程同时申请的资源数大大超过资源总数5、进程所请求的一次打印输出结束后，将使进程状态从态变为态。A)运行就绪B)运行阻塞C)就绪运行D)阻塞就绪6、UNIX系统中，空闲文件存储区的管理采用的是。A)位图法B)空闲块表法C)成组链接法D)单块链接法7、一种既有利于短小作业又兼顾到长作业的作业调度算法是。A)先来先服务B)轮转C)最高响应比优先D)均衡调度
8、在单处理器的多进程系统中，进程什么时候占用处理器和占用多长时间，取决于。
A)进程相应的程序段的长度B)进程总共需要运行时间多少C)进程自身和进程调度策略D)进程完成什么功能
9、若系统中有五个并发进程涉及某个相同的变量A，则变量A的相关临界区是由
个临界区构成。
A)1B)3C)5D)6
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)目录文件、数据文件15、在页式管理中，每个页表中的每个表项实际上都是用于实现。A)内在单元B)静态重定位C)动态重定位D)加载程序（二）、填空题（每空1分，共12分）
1、如果淘汰算法不合理，那么有可能刚被调出的一页马上又要求被调入。内存和外存这种频繁地来回调入调出页面的现象称为（1）。
2、某分页系统的逻辑地址为16位，其中高6位为页号，低10位为页内地址。则这样的地址结构：（1）一页有（2）字节（2）逻辑地址可有（3）页（3）一个作业最大的使用空间是（4）字节3、在一个采用页式虚拟存储管理的系统中，某进程依次要访问的字地址序列（逻辑地址）是：115，228，120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题：A、按FIFO调度算法将产生（5）次缺页中断，依次淘汰的页号为（6）B、按LRU调度算法将产生（7）次缺页中断，依次淘汰的页号为（8）
4、若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。A、先来先服务算法（9）B、最短寻道时间优先（10）
5、进程的（11）和（12）反映了进程间直接制约和间接制约的关系。（三）（8分）有三个人A、B、C，其中A负责采购原材料并放入仓库1（该库只能放一件原材料），B从库1取出原材料并加工成产品后放入库2（该库也只能放一件产品），C从库2取出商品后销售。试说明：
（1）为了实现并必发，需要几个信号灯，功能和初值是什么？（3分）（2）利用P、V（wait、signal）操作写出并发流程。（3分）四、计算机原理部分（共40分）（一）、单项选择题：（8分，在每小题的四个备选答案中，选出一个正确的答案）1、下面叙述不正确的是。
A)半导体随机存储器可随时存取信息，掉电后信息丢失B)在访问随机存储器时，访问时间与单元的物理位置无关C)动态存储器和静态存储器都是靠电容维持信息D)随机存储器和只读存储器可以统一编址
2、单级中断系统中，CPU一旦响应中断，为了防止本次中断服务结束前同级的其它中断源产生另一次中断进行干扰，需要立即执行。A)关中断B)中断请求C)开中断D)中断保护3、量非格式化硬盘的一个磁表面存储容量的两个指标是。A)磁道的长度和半径B)磁盘的厚度和载体C)驱动器的转速和磁头个数D)磁盘的位密度和道密度4、DMA与CPU共享总线时，论述DMA工作方式不正确的是方式。A)CPU中断B)周期挪用C)CPU暂停D)交替访问5、令周期是指。
A)CPU从主存取出一条指令的时间B)CPU的工作主频C)CPU从取出指令开始到指令执行完毕所需的时间D)RAM的存取周期6、在循环冗余校验中，生成多项式为G(x)=x3+x+1,则信息码1101的CRC码为
。
A)11010000B)1101011C)1101101D)1101001
7、在变址寻址中，设变址寄存器中的内容为2100H，指令中的地址部分的值为B9H，采用补码表示，则操作数的有效地址为。A)21B9HB)2147HC)20B9HD)2047H
（二）、是非题（10分，请用√表示正确，用×表示错误）1、浮点运算部件通常既有算术运算功能也有逻辑运算功能。
2、设[X]补=0.x1x2x3x4x5x6x7，若要求X>1/2成立，则需要满足的条件是：x1必须为1，x2∽x7至少有一个为1。
3、指令中地址码部分所指定的寄存器中内容是操作数的有效地址的寻址方式称为寄存器寻址。
4、高并行加法器速度的关键是提高传递进位的速度。在设计并行加法器时，只有采用超高速电子器件才能提高传递进位的速度。5、码乘法中，右移位操作是算术移位。
（五）、已知某8位计算机的地址总线为18位，且主存采用4k×4位的SRAM芯片构成该机所允许的最大主存空间。若主存采用模块板结构组织，请问：（本题7分）
1、若每块存储条容量为32k×8位，则共需多少个这样的存储条？（2分）2、每块存储条内共需多少4k×4位SRAM芯片？（2分）
3、每块存储条的芯片如何组织？CPU又怎样选择这些存储条？（3分）说明：SRAM除地址、数据线外，有CS（低电平有效）、WE（高电平读、低电平写）等控制线。其它逻辑芯片自由选择，但必须说明所选芯片的功能。