卓越考研

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

第一部分数据结构（共35分）一、选择题，在所给的四个选项中，选择一个最确切的（每小题1分，共10分）
1.设单循环链表中结点的结构为（data,next），且rear是指向非空的带头结点的单循环链表的尾结点的指针。若要删除链表的第一个结点，正确的操作是。A)s=rear;rear=rear->next;free(s);B)rear=rear->next;free(s);
C)rear=rear->next->next;free(s);
D)s=rear->next->next;rear->next->next=s->next;free(s)
2.设输入序列为{20，11，12，……}，构造一棵平衡二叉树，当在树中插入值12时发生不平衡，则应进行的平衡旋转是。A)LLB)LRC)RLD)RR
3.设有1000个无序的元素，希望用最快的方法选出前10个最小的数据，下面四种方法中最好的是。A)冒泡B)快速C)堆D)选择4.下面程序的时间复杂性为。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A)0(n2)B)0(n*m)C)0(m2)D)0(m+n)5.关于下面的程序段，不正确的说法是。pb=pc=-1;
for(intk=0;k<n;k++)if(A[k]>0)B[++pb]=A[k];elseC[++pc]=A[k];
A)其时间复杂性为0(n/2)
B)它将数组A中的正数放到数组B中，将负数放在数组C中C)如果数组A中没有负数，程序执行后pc=-1D)如果数组A中没有正数，程序执行后pc=-1
6.有三个数字1，2，3，将它们构成二叉树，中序遍历序列为1，2，3的不同二叉树有种。A)5B)6C)7D)8
7.判断有向图是否有回路，除了可以用拓扑排序外，还可以用。A)求关键路径的方法B)广度优先遍历算法C)求最短路径的方法D)深度优先遍历算法8.在线索二叉树中，下面说法不正确的是。A)在中序线索树中，若某结点有右孩子，则其后继结点是它的右子树的左支末端结点
B)线索二叉树是利用二叉树的n+1个空指针来存放结点前驱和后继信息的C)每个结点通过线索都可以直接找到它的前驱和后继D)在中序线索中，若某结点有左孩子，则其前驱结点是它的左子树的右支末端结点。9.一棵有64片叶结点的完全二叉树，该完全二叉树最多有结点。A)124B)125C)126D)127
10.若从二叉树的任一结点出发到根的路径上所经过的结点序列是按关键字有序的，则该二叉树是。
A)二叉排序树B)用二叉树形式存储的堆C)哈夫曼树D)AVL树
二、判断题（每小题1分，共10分）判断下面的叙述是否正确，在答题纸上用题号加“True”或题号加“False”表示。
1.数据的逻辑结构与数据元素本身的内容和形式无关。2.中缀表达式：（a+b）*d+e/(f+a*d)+c的后缀表达式为ab+d*efadd+/*+c+3.中序序列和后序序列相同的二叉树为：空树和缺右子树的单支树。
4.对于两棵具有相同关键字集合而开关不同的二叉排序树，中序遍历后得到的关键字排列顺序相同。
5.序列{30，40，50，15，25，35，38，10}是堆。
6.对于无向图的生成树，从同一顶点出发所得的生成树相同。
7.若以{4，5，6，7，8}作为叶子结点的权值来构造哈夫曼树，则带权路径长度是69.8.一个深度为k的，具有最少结点数的完全二叉树按层次（同层次从左向右）用自然数依次对结点编号，则编号最小的叶子的序号是2k-2+1;编号是i的结点所在的层次号是┌log2i│+1(logzi│表示向上取整┚(根所在的层次号规定为1层)。
9.在一棵7阶B树中，一个结点中最多有6棵子树，最少有3棵子树。10.算法可以没有输入，但是必须有输出。
三、填空题（每个空格1分，共10分）
1.在《数据结构》中，线性结构、树形结构和图形结构数据元素之间分别存在______、_______和______的联系。

2.从顶点A到F的最短路径长度是______。

四、算法（5分）树的存储结构如下：
#defineMAX_TREE_SIZE100TypedefstructCTNode{//孩子结点Intchild;Struct
CTNode*next;
}*childPtr;Typedefstruct{ElemtypedatachildPtr*firstchild;//孩子链表头指针}*CTBox;Typedefstruct{
CTBoxnodes[MAX_TREE_SIZE];Intn;//n为结点数}*CTree
写出求树的度的算法。
第二部分操作系统（共35分）
一、选择题，在所给的四个选项中，选择一个最确切的（每小题1分，共10分）

1.操作系统的主要作用是。A)管理设备B)提供操作命令C)管理文件D)为用户提供使用计算机的接口，管理计算机的资源

2.在操作系统术语中，C/S是。A)浏览器/服务器B)网络OSC)实时OSD)分布式OS

3.与UNIX操作使用基本相同的操作系统操作系统是。A)LINUXB)WindowsNTC)UNIXD)OS/2

4.在操作系统中，并发性是指。A)若干个事件在同一时刻内发生B)事件的发生时间随机C)若干个事件在同一时间间隔内发生D)事件驱动

5.特权指令是指。A)机器指令B)其执行可能有损系统的安全性C)控制指令D)系统管理员可用的指令

6.在物理上，进程由所组成。A)程序B)命令C)PCB、程序和数据D)PCB和程序

7.操作系统中的三级调度是指。A)处理机调度、资源调度和网络调度B)CPU调度、设备调度和存储器调度C)作业调度、进程调度和资源调度D)作业调度、进程调度和均衡负载调度
8.在操作系统中，设备独立性是指。A)用户程序与设备无关B)设备独立管理C)设备具有自治性D)只有OS才有权启动设备

9.当发生中断后，进入中断处理的程序属于。A)用户程序B)可能是用户程序，也可能是OS程序

C)OS程序D)单独的程序，既不是用户程序，也不是OS程序

10.在设备管理中，设备映射表（DMT）的作用是。A)管理物理设备B)管理逻辑设备C)实现输入输出D)建立逻辑设备与物理设备间的对应关系

二、填空题（答题时，标明题号。每个空格1分，共10分）

1、操作系统的特征包括并发性、共享性、______、______、_______。

2、操作系统提供二种接口，即为用户提供______，为程序用户提供______。
3、在UNIX操作系统中，为块设备提供了二种读方式，分别是______和______。
4、产生死锁的四个必要条件是互斥条件、______、______、______。

三、应用题（共15分）1、（7分）在UNIX系统中，空闲磁盘空间的管理采用了成组链表法，试述成组链表法的实现方法。说明其优缺点。
2、桌子有一个盘子，每一次只能放入一个水果。现有许多苹果和桔子。一家四口人各行其职，爸爸的动作是：负责取苹果，然后将苹果放入盘子中，并重复这二个动作。当取来一个苹果后，若盘子中允许放入水果，即盘子为空，则将苹果放入盘子中；否则等待，直等到盘子中能放入苹果为至。妈妈的动作是：负责取桔子，然后将桔子放入盘子中，并重复这二个动作。当取来一个桔子后，若盘子中允许放入水果，则将桔子放入盘子中；否则等待，直等到盘子中能放入桔子为至。一个女儿的动作是：负责从盘中取苹果，然后吃苹果，并重复这二个动作。若盘子中有苹果，则取走苹果；否则等待，直等到盘子中有苹果为止。一个儿子的动作是：负责从盘中取桔子，然后吃桔子，并重复这二个动作。若盘子中有桔
子，则取走桔子；否则等待，直等到盘子中有桔子为止。试用P、V操作写出他们四人之间的同步算法（8分）。提示：先分析四人之间的同步关系，然后写出同步算法。
第四部分计算机原理（共40分）
一、选择题，在所给的四个选项中，选择一个最确切的（每题2分，共10分）
2.下面叙述不正确的是。A)半导体随机存储器可随时存取信息，掉电后信息丢失B)在访问随机存储器时，访问时间与单元的物理位置无关C)动态存储器和静态存储器都是靠电容维持信息D)随机存储器和只读存储器可以统一编址
3.在单级中断系统中，CPU一旦响应中断，为了防止本次中断服务结束前同级的其他中断源产生另一次中断进行干扰，需要立即执行。A)关中断B)中断请求C)开中断D)中断保护

4.衡量非格式化硬盘的一个磁表面存储容量的两个指标是。A)磁道的长度和半径B)磁盘的厚度和载体C)驱动器的转速和磁头个数D)磁盘的位密度和道密度
5.DMA与CPU共享总线时，论述DMA工作方式不正确的是。A)CPU暂停方式B)周期挪用方式C)CPU中断方式D)交替访问方式

二、是非题，请用√表示正确，用×表示错误（每题2分，共8分）1.中断向量表是存放用户调用子程序的地址表。2.补码乘法中，右移位操作是算术移位。
3.可编程逻辑阵列是一种存储逻辑，也是主存的一部分。
4.DMA和中断系统一样，只有在CPU执行完当前指令后，才响应请求。