2010-2018年南京某航空航天大学《922数据结构与操作系统》历年考研真题汇总

目录TOC\o"1-5"\h\z2010年南京航空航天大学922数据结构（专业学位）考研真题 42011年南京航空航天大学922数据结构（专业学位）考研真题 72012年南京航空航天大学922数据结构与操作系统（专业学位）考研真题 102013年南京航空航天大学922数据结构与操作系统（专业学位）考研真题 142014年南京航空航天大学922数据结构与操作系统（专业学位）考研真题 172015年南京航空航天大学922数据结构与操作系统（专业学位）考研真题 222016年南京航空航天大学922数据结构与操作系统（专业学位）考研真题 252017年南京航空航天大学922数据结构与操作系统（专业学位）考研真题 282018年南京航空航天大学922数据结构与操作系统（专业学位）考研真题 32南京航空航天大学二。一O年硕士研究生入学考试试题考试科目：数据结构（专业学位）说明：答案一律写在答题纸上，写在试卷上无效一、单项选择题（共30分，15题，每题2分）1.一个算法具有以下5个重要特性。（ ）A.有穷性、确定性、可行性、输入、输出B.可行性、可移植性、可扩充性、输入、输出C.确定性、有穷性、稳定性、输入、输出D.易读性、稳定性、安全性、输入、输出2.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）（l<=i<=n+l）.A.0（0）B.0（1） C.0（n） D.0（n2）.一个栈的输入序列为1,2,3…，n,若输出序列的第一个元素是n,输出第i（l<=i〈=n）个元素是（）.A.不确定B.n-iC.iD.n-i+1.循环队列存放其元素值，用front和rear分别表示队头和队尾，当前队列的长度是（）.A.rear-front+lB.rear-frontC.（rear-front+m）%mD.（rear-front）%m.数组A[L.5,1..6]的每个元素占4个字节，将其按行优先次序存储在起始地址为1000的内存单元中，则元素A[4,4]的地址是（）.A.1175 B.1180 C.1088 D.1084.已知一棵二叉树的先序遍历为ABCDEF,中序遍历为CBAEDF,则后序遍历为（ ）。A.CBEDFAB.FEDCBAC.CBEFDAD.不定.一棵具有n个结点的完全二叉树的树高度（深度）是（ ）A.Llog2nJB.log2n+lC.LlogziiJ+1D.log2n-l8.若一棵二叉树具有15个度为2的结点，10个度为1的结点，则度为0的结点个数是（）。A.16 B.25 C.40D.不确定一棵完全二叉树上有2001个结点，其中叶子结点的个数是（）。A.500B.501C.1000D.100110.一个n个顶点的连通无向图，其边的个数至少为（）。A.n+1 B.nA.n+1 B.n11.下面说法不正确的是（ ）»A.广义表的表头总是一个广义表C.广义表难以用顺序存储结构C.n-1 D.nlogn;B.广义表的表尾总是一个广义表D.广义表可以是一个多层次的结构TOC\o"1-5"\h\z12.适用于折半查找的表的存储方式及元素排列要求为（ ）。A.顺序方式存储，元素无序 B.顺序方式存储，元素有序C.链接方式存储，元素无序 D.链接方式存储，元素有序13.下列排序算法中，平均时间复杂度不为O（nlog'n）的是（ ）。A.快速排序 B.堆排序C.归并排序 D.希尔排序14.下列排序算法中，其中（ ）是稳定的。。A.快速排序 B.起泡排序 C.堆排序D.希尔排序15.Floyd算法是用来求解（ ）。D.任意两点间最短距离A.拓扑排序B.关键路径C.D.任意两点间最短距离二、解答题（共80分，8题，每题10分）16.应用栈操作求解算术表达式：（18-24/4）*（3+9）,画出栈的变化过程。.画出下图所示树的二种存储结构示意图。（1）带双亲的孩子链表表示法（2）孩子兄弟链表表示法.详细解释哈希表的工作原理，以及常见的哈希函数构造方法和解决冲突方法，举例说明。.已知在一份电文中只使用了6个字符A,B,C,D,E,F,其频率分别为5,29,7,8,12,画出哈夫曼树，并写出每个字符对应的哈夫曼编码。.已知数据序列为（36,74,8,50,18,6,40,30）,给出建立二叉排序树的过程示意图，再给出删除74,8后的二叉排序树。.求下图中的关键路径，写出算法求解过程中每一步的状态。.已知输入数据序列为(36,56,50,24,62,18,40,80,30,12),给出建立3阶B-树示意图.再给出删除30,50后的B-树。.已知数据序列为(86,8,234,50,116,64,68,453,24,142),给出基数排序过程的示意图.三、编程题(共40分，4题，每题10分)用C或C++或JAVA语言设计与实现算法.编写函数，将单链表中具有相同元素值的结点删除(只保留一个)，分析时间复杂度.写出算法思想。.已知一棵二叉链表表示的二叉树T,编写函数，实现二叉树的层次遍历.写出算法思想。.无向图G用邻接矩阵存储，编写程序，输出G的每一连通分量的顶点值。写出算法思想。.设有一整数序列由正数、负数组成，编写程序，通过一趟扫描处理，将所有的负数移到正数前面，只能用一个辅助单元。写出算法思想。南京航空航天大学2011年硕士研究生入学考试初试试题（ A卷）科目代码： 922 、廿科目名称. 数据结构（-业学位）丽必-"注意：①认女阅读答题纸上的注意事项；②所有答案必须写在僭题纸|上,写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！一、单项选择题（共30分，15题，每题2分）.如果最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。A.单链表B,双链表C.单循环链表D.顺序表.在一个双链表中，在*P结点之前插入*q结点的操作是（）□p->prior=q；q->next=p；p->prior->next=q；q->prior=p->prior；q->prior=p->prior；p->prior->next=q；q->next=p；p->prior=q->next；q->next=p；p->next=q；q->prior->next=q；q->next=p；p->prior->next=q；q->next=p；q->prior=p->prior；p->prior=q；.一个栈的进栈序列是abode,则栈的输出序列不可能的是（）。A.edcbaB.decbaC.dceabD.abode.表达式a*（b+c）-d的后缀表达式是（）。A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd.环形队列qu的队空条件是（）o（qu.rear+1）%MaxSize=（qu.front+1）%MaxSize；（qu.rear+1）%MaxSize=qu.front+1；（qu.rear+1）%MaxSize==qu.front；qu.rear==qu.front；.一棵高度为h的完全二叉树至少有（）结点。A.2h-1B,2^'-1C. D.2h.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。A.不发生改变B.发生改变C.不能确定D.以上都不对.根据使用频率为5个字符设计的哈夫曼编码不可能是（）oA.000,001,010,011,1B.0000,0001,001,01,1C.000,001,01,10,11D,00,100,101,110,1119.在一个无向图中，所有顶点的度之和等于边数的（）倍。A.1/2B.1C.2D.4

10.关键路径是事件结点网络中的（）oA.从源点到汇点的最长路径 B.从源点到汇点的最短路径C.最长的回路C.最长的回路D.最短的回路11.索引顺序表是将表分成若干子表（或称块），据此建立索引表，并要求关键字（）oA.块内A.块内有序，块间有序B.块内无序，块间有序C.块内有序，块间无序D.块内无序，块间无序12.稳定的排序方法是（）oA.直接插入排序B,直接选择排序 C.堆排序D.快速排序13.以下序列是堆的是（）oA.B.C.D.(75,65,30,15,25,45,20.10)(75,65,45,10,30,25,20,15)(75,45,65,30,15,25,20,10}{75,45,65,10,25,30,20,15}A.B.C.D.4.m阶B-树任一个结点最多有（ ）个关键字。A.mB,m-1C.m+1D,任意.归并排序算法的时间复杂度是()。A.0(Iog2n)B.0(n)C.0(n2)D.0(nIog2n)二、解答题（共80分，8题，每题10分）.应用栈操作求解算术表达式：（12+28）*2-（68-14）/9，画出栈的变化过程。.输入关键字序列{16,3,7,11,9,26,18,14,15.12},给出构造一棵平衡二叉树的步骤。.已知世界6大城市：北京⑻、纽约（N）、巴黎（P）、伦敦（L）、东京⑴、墨西哥城（M）。试在下表给出的交通网中确定最小生成树，并说明所使用的方法和时间复杂度。表：世界6大城市交通里程网络表（单位：100km）BNPLTMB109828121124N109585510832P825839792L815539589T211089795113M124329289113.对于下图所示的带权有向图，采用Dijkstra算法求解从顶点1到其他顶点的最短路径,要求给出求解过程。.关键字序列为{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12.14.18,19.15},创建一棵5阶B-树。对于该B-树，删除8,16,15,4等4个关键字的过程。.已知在一份电文中只使用了8个字符A,B,C,D,E,F,G,H,其频率分别为(36,10,18,8,2,16,4,12),画出哈夫曼树，并写出每个字符对应的哈夫曼编码。.已知哈希函数H(k)=2*kmod11,用开放定址法处理冲突：H,(k)=(H(k)+d.)mod11i=1,2,其中：d,=1,4“=(7d,+3)mod11(i>1)o试在。〜10的哈希地址空间中对关键字序列(6,8,10,17,20,23,53,41,54,57)构造哈希表。.已知序列［503,87.512,61.908,170,897,275,653,462},写出采用堆排序法对该序列作降序排序时的每一趟的结果。三、编程题(共40分，4题，每题10分)用C或C++或JAVA语言设计与实现算法.编写程序，实现在带头结点的单链表L中删除一个最小值结点的算法。写出算法思想。.假设二叉树T采用二叉链存储结构，编写程序，求二叉树T的宽度。(即具有结点数最多的那一层上的结点个数)。写出算法思想。.假设无向图G采用邻接表存储，编写程序，判断图G是否是连通图。若是连通图返回1,否则返回0。写出算法思想。.已知二叉树T采用二叉链存储结构存储，编写程序，对二叉树T进行非递归先序遍历。写出算法思想。

南京航空航天大学2012年硕士研究生入学考试初试试题（A卷）科目代码：科目名称：数据结构与操作系统（专业学位）满分:150分注意：①认真阅读答题纸上的注意事项；②所有答案必须写在国酬上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！

数据结构部分（75分）（5分）已知一棵完全二叉树共有691个结点.结点从1开始，自上而下自左而右层序编号，试求以下问题，并给出推导过程。（1）树的高度； （2）叶子结点的数目；（3）分支为1的结点数目：（4）最后一个非终端结点的编号；（5）还差多少个结点就可以构造成相同高度的满二叉树。（10分）画出广义表L=（f,（b,e）,（（c,d）,a））的两种存储结构图.（10分）如图1所示的AOE网，试求完成工程最少需要多少天（设边上的权值为天数），并说明哪些是关键活动。要求给出规范的计算过程。图1第3题图（10分）已知输入数据序列为{38,66,18,80,58,52,26,42,28,16},给出建立3阶B■树示意图，再给出删除28,52后的3树。（10分）已知序列{108,170,503,87,512,161,175,53,897,462},写出采用堆排序法对该序列作降序排序时的每一趟结果。（10分）设L为带头结点的单链表，元素值为整数。设计一个算法，调整结点的位置，将所有元素值为负数的结点移动到元素值为正数的结点之前，要求时间夏杂度T（n）=CKn）。要求先给出算法思想，再写出相应代码。（10分）设树采用孩子兄弟链表结构进行存储，设计一个算法，求树的宽度（即具有结点数最多的那一层上的结点个数）.要求先给出算法思想，再写出相应代码。（10分）设二叉排序树T的key值为整数，高度为k,对任意给定的整数x,查找元素值小于x且最接近x的结点并返回结点指针，如该结点不存在则返回指针为空，要求用非递归算法实现且时间更杂度T（n）=O（k）.要求先给出算法思想，再写出相应代码。

操作系统部分(75分)1、(8分)(1)处理机的调度有哪三个层次？(2)假设一操作系统以单道批处理方式运行，现有四道作业，进入系统的时间及运行时间如下表所示，试用响应比高者优先算法进行调度，请给出这组作业的运行顺序、平均周转时间和带权平均周转时间。作业号进入时间运行时间(小时)17:002.0027:500.5038:000.1048:500.202、27分)(1)实现进程同步机制必须遵循哪几条准则，含义是什么？(2)以下程序中，哪些代码应该设为临界区？(3)假设操作系统采用非抢占调度策略，sys_nc()是主动放弃CRJ的系统函数。对于以下程序代码，可能违反什么同步准则？inta;进程1(){sys_nc();a=a+l;)进程2(){a=a-l;sys_nc();)(4)采用信号量来进行进程同步可以很好地满足进程同步准则。现假设有一个共享数据库,允许进程对数据库进行查询和更新两种操作，规则是查询操作可以允许多个进程同时查询，但更新必须是排他性的，即每次只允许一个进程更新数据库，请用信号量和P、V操作来完成这一进程同步问题(要求：必须首先给出所设置信号量的意义及初值)3、(10分)(1)产生死锁的主要原因是什么？(2)有哪些处理死锁的基本方法？静态分配资源的方法属于哪种处理死锁的方法？而银行家算法属于哪种死锁处理方法？(3)设系统中有三种类型的资源(A,B,C)和五个进程(Pl,P2,P3,P4,P5),A的资源的数量为17,B的资源的数量为5,C的资源的数量为20,在T0时刻状态如下：

ABCABcP1559212P2536402P34011405P4425204P5424314最大资源需求量已分配资源需求量剩余资源数ABC233系统采用银行家算法实施死锁处理策略。（a）TO时刻是否为安全状态？若是请给出安全序列。（b）在TO时刻，若进程P2请求资源（0,3,4）,是否能实施资源分配？为什么？（c）在（2）基础上，若进程P4请求资源（2,0,1）,是否能实施资源分配？为什么？（d）在（3）基础上，若进程P1请求资源（0,2,0）,是否能实施资源分配？为什么？4、（10分）（1）分页和分段属于离散型的存储管理方式，相对于连续内存管理方法的主要优点是什么？（2）某操作系统采用段式存储管理，假设有如下段表：（注意：其中数字为十进制表示）段号段的长度（字节）主存起始地址06602191143300210090358012374961952试解决下列问题：（a）给定段号和段内地址，完成段式管理中的地址变换过程（并用图示）。（b）计算[0,430],[1,10],[2,500],[3,400]的内存地址，其中方号内的第一元素为段号，第二元素为段内地址。（c）存取内存中的一条指令或数据至少要访问几次内存？如何提高地址转换的效率？5、（8分）（1）操作系统中虚拟存储器的基本原理是什么？（2）页面置换算法是虚拟存储器的支撑软件方法，现假设某页式虚拟内存系统中，程序代码位于虚空间0页，A为256x256的数组，在虚空间以行为主序进行存储(A(l,l),A(l,2),A(l,3)……)，每页存放256个数组元素。现工作集大小为2个页框，假设代码已经在内存中，用以下两种代码对数组A进行初始化，都必须进行页面置换，问两个代码各自的缺页次数为多少？程序(a)fbrj:=lto256dofori:=1to256doA(ij)：=0;程序(b)fbri:=lto256dofbrj=1to256doA(ij)=0;6、(6分)1)磁盘访问时间由哪几部分组成？2)若当前磁头在153号磁道，进程请求访问的磁道为96,157,101,187,104,160,112,185,140。请用SCAN调度算法给出访问顺序。(磁头方向为由小到大)7、(8分)某操作系统的文件系统采用索引节点的结构进行文件管理，即文件所占用的盘块号放在该文件的索引结点的13个地址页中，前10个为直接寻址，后三个分别为一次间址，二次间址和三次间寻址。假设盘块大小为1KB,每个间址放256个盘块地址。问：(1)这种文件系统可存放的最大文件为多少字节？(2)一个4MB大小的文件，要占用多少磁盘空间(多少盘块)？8、(8分)(1)在某文件系统中，每个盘块为256字节，文件控制块占64个字节，其中文件名占8个字节。如果索引结点编号占2个字节，对一个存放在磁盘上的128个目录项的目录，试比较引入索引节点前后，为找到其中一个文件，平均启动磁盘的次数。(2)常用的提高文件系统性能的方法有哪些？南京航空航天大学2013年硕士研究生入学考试初试试题（ A卷）科目代码：922科目名称:_数据结构与操作系统（专业学位） 酒7r型力注意：①认真阅读答题纸上的注意事项；②所有答案必须写在懵题纸।上,写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！数据结构部分（75分）（1）（2分）推导二叉树的性质3：度为2的结点数与度为。的结点数的关系。（2）（3分）推导二叉树的性质4：求解N个结点完全二叉树的高度。（10分）画出下图（1）所示树的三种存储结构示意图。（10分）试用Dijkstra算法，求下图（2）中从V1到其余各顶点的最短路径,写出算法过程中每一步的状态。过程中每一步的状态。（10分）已知数据序列为（76,58.234,5,16,164,28,423,24,102）,给出基数排序过程的示意图。（10分）设稀疏矩阵用三元组顺序表存储，用下面例子说明快速转置算法的执行过程。A5x6=（（1.3,8）,（1,5,68）,（3,1,12）,（3,4,52）.（3,5,3）,（4,1,45）,（5,1,26））（10分）已知有两个带头结点的单链表A和B,元素值递增有序，编写函数，调整删减A链表，使A链表结点的元素值为A、B的交集，并成为一个递减有序的单链表。要求先给出算法思想，再写出相应代码。（10分）编写函数，用非递归方法，求二叉链表表示的二叉树T的高度。要求先给出算法思想，再写出相应代码。（10分）编写函数,判断一个有向图是否存在回路。要求先给出算法思想，再写出相应代码。

操作系统部分（75分）一.简答（每题5分，共25分）1）为什么要引入线程，线程和进程有何区别？2）为什么多道批处理操作系统可以提高资源利用率？什么是通道，通道经常采用如图所示的交叉连接，为什么？什么是通道，通道经常采用如图所示的交叉连接，为什么？4）简述操作系统引入缓冲的原因？5）何谓文件的物理结构，可分为哪几类，比较其优缺点？计算题共50分（10分）假设有个南北向的胡同很窄，仅能容同方向的人顺序走过，相对方向的两个人则无法通过。现在胡同南北入口都有过路人。现把每个过路人当成一个进程，用PV操作实现管理。（10分）设在批处理系统中有四道作业，它们进入系统的时间及运行时间如表所示。作业号进入时间运行时间（小时）18：002.0028:500.5039：000.1049:500.20设系统每次只选择一个作业装入主机，分别给出在下列算法中这组作业的运行顺序、平均周转时间和平均带权周转时间。（1）FCFS算法;（2）SJF算法。（8分）设系统有五个进程（P0,PI,P2,P3,P4）和四类资源（A,B,C,D］各种资源的数量分别为2,1,0,0,在T0时刻资源分配情况如下表：

进程最大资源需求A当前已分配到的资源ABCDBCDP000120012P127502000P266560034P343562354P406520332(1)当前系统是否是安全的？为什么？(2)假定此时P2发出请求向量为Request(0,1,0,0),系统可否分配给它？为什么？4.(8分)进程某时刻的页表如下图所示：页号标志主存块号0141182031240510其中的数字为十进制，页号、块号都以0开始，页的大小为2K字节，标志为1是在内存，标志为。表示不在内存。请回答下列问题：(1)简述分页式虚拟存储系统中，一个逻辑地址到物理地址的转换过程(并画出地址转换机构图)。⑵逻辑地址0x1830和0x206B对应的物理地址是什么？(7分)说明LRU相比FIFO算法有何优点。当分配给进程的物理页个数分别为3和4,页面访问序列为4,3,2,1,43,5,4,3,2,1,5,采用LRU算法分别给出页面走向。(7分)设磁盘的I/O请求队列中的柱面号为:65,68,49,28,100,170,160,48,194.磁头初始位置为110,磁臂方向由小到大，请给出分别采用最短寻道时间优先的磁盘调度算法和电梯磁盘调度算法的柱面移动次数，并给出操作系统采用何种磁盘调度算法更好，为什么？南京航空航天大学2014年硕士研究生入学考试初试试题（ A卷）科目代码：922 分 分科目名称」数据结构与操作系统（专业学位）满7r坨万注意：①认真阅读答题纸上的注意事项；②所有答案必须写在僭题纲上,写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！数据结构部分（75分）（5分）给出广义表G=（（e,a）,（（b,（）,d）,c）,f）的以表头表尾形式的链式存储结构不意图。（10分）解释哈希表工作原理。将关键字序列（75,54.48.90,18,22.84.63）存储在长度为10的哈希表中，使用哈希函数H（key）=Key/10,并采用二次探测再散列法解决冲突，画出哈希表示意图。（10分）试用Floyd算法，求解下图中各顶点之间的最短路径，写出算法过程中每一步的状态。（10分）已知数据序列为（555,88,499,58,808,170,797,275,653,460）,给出堆排序过程的示意图。（10分）设有6个字符，其权值为（12,40,16,8,14,10）,给出进行Huffman编码的数据结构和执行过程示意图。（10分）设一个带头结点的单链表L数据元素为（a1,a2,a3,a4 an）,编写函数,调整该链表，使得数据元素次序为（al.a3 an a4,a2）,要求T（n）=0（n）,先给出算法思想.再写出相应代码。（10分）设有一家谱树T,用二叉链表结构存储（孩子兄弟表示法），树中的结点信息为成员名字。编写函数，输出家谱中共有多少代以及最后一代人数和成员名字。要求先给出算法思想，再写出相应代码。（10分）编写函数，给有向无环图G的每一个顶点赋以一个整数编号，要求：若顶点v到顶点W之间有一条弧，则顶点V的编号小于顶点W的编号。先给出算法思想，再写出相应代码。操作系统部分（75分）选择题（共10小题，每小题1分，共10分）.下列关于操作系统的四种陈述中，正确的是（）0A.批处理操作系统必须在响应时间内处理完一个任务B.实时操作系统必须在规定时间内处理完来自外部的事件C.分时操作系统必须在周转时间内处理完来自外部的事件D.分时操作系统必须在调度时间内处理完来自外部的事件.设有两个进程A、B,各按以下顺序使用P,V操作进行同步。A进程：B进程：al—*P(sl)a2—*P(s2)a3—♦V(s2)a4TV(sl)a5—»bl~*P(s2)b2—*P(sl)b3-V(sl)b4—♦V(s2)b5—♦试问在下列执行顺序中，哪种情况会发生死锁？（）A.a1,a2,a3,a4- B.bl,b2,b3,b4,b5C.a1ta2,b1,b2,a3,b3- D.a1.b1.a2.b2,a3,b3-.在内存管理中，内存利用率高且保护和共享容易的是（ ）内存管理方式。A.分区管理 B.分页管理C.分段管理 D.段页式管理.操作系统中，很多事件会引起调度程序的运行，但下列事件中不一定引起操作系统调度程序运行是（）0A.当前运行着的进程出错。B.当前运行着的进程请求输入/输出。C.有新的进程进入就绪状态。D.当前运行的进程时间片用完。5.操作系统中调度算法是核心算法之一，下列关于调度算法的论述中正确的是（）0A.先来先服务调度算法对即对长作业有利也对段作业有利。B.时间片轮调度算法转只对长作业有利。C.实时调度算法也要考虑作业的长短问题。D.高相应比者优先调度算法既有利于短作业又兼顾长作业的作业还实现了先来先服务。.操作系统中产生死锁的根本原因是（）oA.资源分配不当和CPU太慢 B.系统资源数量不足C.作业调度不当和进程推进顺序不当 D.用户数太多和CPU太慢.内存管理中把作业地址空间中使用的逻辑地址转变为内存中的物理地址称为（）。A.链接B.装入C.重定位D.虚拟化.I/O设备管理是操作系统的重要功能，那么下列对设备属性的描述正确的是（）oA.字符设备的基本特征是可寻址到字节，即能指定输入的源地址或输出的目标地址。B.共享设备必须是可寻址的和可随机访问的设备。C.共享设备是指同一时间内运行多个进程同时访问的设备。D.在分配共享设备和独占设备时都可能引起进程死锁。.程序设计时需要调用操作系统提供的系统调用，被调用的系统调用命令经过编译后，形成若干参数和（）。A.访管指令或软中断B.后动I/O指令C.屏蔽中断指令 D.通道指令.以时间换空间或者以空间换时间是操作系统的基本技术，以下以空间换时间的机制是（）oA.SPOOLINGB.虚拟存储技术 C.通道技术D.覆盖技术二、简要分析题（共4小题，每小题5分，共20分）.从操作系统设计角度谈谈进程控制块的作用。.解释静态链接和动态链接是现代操作系统中两种重要的链接方式，试比较同一程序经过静态链接和动态链接后的可执行文件大小，如果有不同分析原因。.试比较磁盘高速缓存和虚拟盘，提高文件系统性能的通常有哪些方法？.举例说明线性检索法检索过程（例如查找/usr/ast/mbox）三.综合应用题（共7小题，共45分）（6分）设在批处理系统中有四道作业，它们进入系统的时间及运行时间如表所示。作业号进入时间运行时间（小时）19：002.0029：500.50310:000.10410：500.20设系统每次只选择一个作业装入主机。问：采用SJF调度算法，给出这组作业的运行顺序、平均周转时间和平均带权周转时间；（6分）某操作系统采用分页式虚拟存储管理方法，现有一个进程需要访问的地址序列（字节）分别是：115,228,120,88,446,102,321,432,260,167,假设该进程的第0页已经装入内存，并分配给该进程300字节内，页的大小为100字节，试回答以下问题：（1）按LRU调度算法将产生多少次页面置换，依次淘汰的页号是什么？页面置换率为多少？LRU页面置换算法的基本思想是什么？（6分）设磁盘的1/0请求队列中的柱面号分别为：155,158,139,118,190,260,250,138,284,磁头初始位置为200,磁臂方向由小到大。（1）请给出采用SSTF的磁盘调度算法的磁头的柱面移动次数。（2）SSTF的磁盘调度算法有何缺点。（6分）简述消息缓冲队列通信机制，并用信号量和wait,signal操作实现消息缓冲队列通信机制中的发送和接受原语。5.（6分）设系统中有三种类型的资源（A,B,C）和五个进程（P1,P2,P3,P4,P5）,A的资源的数量为17.B的资源的数量为5,C的资源的数量为20,在T0时刻状态如下：最大资源需求量已分配资源需求量ABCABCP1559212P2536402P34011405P4425204P5424314剩余资源数ABC233系统采用银行家算法实施死锁避免策略。T0时刻是否为安全状态？若是请给出安全序列。（2）在T0时刻，若进程P2请求资源（0,3,4）,是否能实施资源分配？为什么？（3）在（2）基础上，若进程P4请求资源（2,0,1）,是否能实施资源分配？为什么？（6分）一个进程某时刻的页表如下图所示页号标心内存块号0121021831140510本题中的数字均为十进制，页号、块号都以0开始，页的大小为2K字节，标志为1表示页面在内存，标志为0表示不在内存；请回答下列问题：⑴简述分页式虚拟存储系统中，一个逻辑地址到物理地址的转换过程（并画出地址转换机构图）⑵逻辑地址5188和3199对应的物理地址是什么？（9分）进程同步机制都应遵循的准则是什么？以下程序中，P1和P2并发执行是否满足进程同步机制应遵循的准则,为什么？varstatusl,status2：boolean；/*进程P1*/RepeatWhilestatus2dono-op；Statusl=true临界区代码；Statusl=false剩余区代码；UntiIflase；/*进程P2*/RepeatWhilestatusldono-op；Status2=true临界区代码；Status2=false剩余区代码；UntiIflase；南京航空航天大学2015年硕士研究生入学考试初试试题（满分：150满分：150分科目名称： 数据结构与操作系统（专业学位）注意：①认真阅读答题纸上的注意事项；②所有答案必须写在画列上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！数据结构部分（75分）（5分）已知一棵完全二叉树共有999个结点，试求以下问题，并给出求解过程。（1）树的高度（2）叶子结点数（10分）应用栈操作求解算术表达式：（28+10*2）/（11-5）,画出栈的变化过程。（10分）已知带权图如下所示，用Prim算法从顶点2开始产生最小生成树，说明算法思想，并给出求解所需的数据结构和每一步执行过程的相关数据变化。（10分）已知输入数据序列为（68,40,25,21,33,12,58,51,16,36）,给出建立3阶B-树示意图，再给出删除51,16后的B-树。（10分））解释希尔排序的算法思想。对以下的数据序列，给出希尔排序过程的示意图。（46.8,36,50,6,24,18,78,12,10）（10分）设一个带头结点的单链表L,数据元素为整数，编写函数，通过调整该链表的结点指针，对该链表进行简单选择排序（元素值从小到大）。先给出算法思想，再写相应代码。（10分）设二叉树T,用二叉链表结构存储。编写函数，输出最长一枝（根到叶子）上的所有结点值。要求先给出算法思想，再写出相应代码。（10分）基于图的广度优先搜索策略，编写函数，判别以邻接表存储的有向图G中，是否存在由顶点Vi到顶点Vj的路径（iwj）。要求先给出算法思想，再写出相应代码。操作系统部分（75分）（30分）文件系统是操作系统的主要功能之一，请设计一个文件系统，需给出以下信息：（1）给出描述文件的数据结构（即文件控制块）和目录结构；（5分）（2）以索引节点为文件系统的物理文件组织结构，图示索引节点结构，说明其优点；（5分）（3）以线性检索法作为此文件系统的文件检索方法，以实例方式给出检索一个文件的过程（例如查找/usr/ast/mbox）;（10分）（4）为该文件系统设计几个必要的系统调用，选其中一个为例，详细说明实现该系统调用的方法和过程（注意要使用以上设计中的数据结构）。（10分）（10分）某机场只有一条飞机跑道，为了提高效率和安全性，现规定：当飞机跑道有飞机起飞时，不允许飞机降落.但此时可以让多架飞机逐个利用跑道起飞；反之，当有飞机降落进入跑道时则不允许起飞飞机进入跑道，但允许飞机依次降落在跑道上，然后驶出跑道。请解决以下问题：（1）请利用信号量和P、V操作正确实现飞机在跑道上起降。（要求：说明所设的信号量的意义及初值）；（2）若把飞机看作进程，为了合理实现对飞机进程的管理，给出描述飞机进程的数据结构。3. （9分）某段式存储管理系统中采用如下段表：（用十进制）段号段的长度（字节）主存起始地址0500150118080026001000316801850试回答：⑴给定段号和段内地址，图示说明完成段式管理中的地址变换过程。（3分）⑵计算[0,150],[1,98],[2,601],[3,50]的内存地址，其中方号内的第一元素为段号，第二元素为段内地址。（3分）⑶存取主存中的一条指令或数据至少要访问几次内存？如何提高速度？（3分）

（8分）LRU算法的思想和依据是什么？请利用LRU算法解决下列问题：在一个请求分页系统中，假如系统分配给一个作业的物理块数为3,此作业的页面走向为3,4,3,3,8,3,6,8,4,3,8,3。试用LRU算法计算页面置换次数。（5分）扫描算法（SCAN）是一种磁盘调度算法，它的优化目标是什么？设磁盘的I/O请求队列中的柱面号依次为：35,58,40.28,80,160,143,38,204,磁头初始位置为95,若采用SCAN（先由小到大开始扫描）磁盘调度算法，磁头移动多少个磁道。9.6Kh/s送内存送内存-1位缓冲（5分）按照下图说明9.6Kh/s送内存送内存-1位缓冲⑻(b)(c)（8分）假设系统有五类独占资源：ri,r2,r3,r4,r5,各类资源分别有：2,2,2,1,1个单位的资源，有五个进程：P1,P2,P3,P4,P5,其中P1已占有2个单位的ri,且申请一个单位的r2和一个单位的r4；P2已占有一个单位的r2,且申请一个单位的ri;P3已占有一个单位的r2且申请一个单位的r2和一个单位的r3;P4已占有一个单位的r4和一个单位的r5,且申请一个单位的r3；P5已占有一个单位的r3且申请一个单位的r5o（1）试画出该时刻的资源分配图。（2）什么是死锁定理，如何判断（1）给出的资源分配图中有无死锁，给出判断过程和结果。南京航空航天大学2016年硕士研究生招生考试初试试题（ A卷）科目代码：922科目名称：数据结构与操作系统（专业学位） 满分：—分注意：①认真阅读答题纸上的注意事项；②所有答案必须写在牌题纸|上,写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！数据结构部分（75分）L（5分）解释m阶B-树的5个特性。（10分）说明基数排序的算法思想和数据结构，对数据序列（130,6,458,92,12,836,250,59,525,272）,给出基数排序过程示意图。（10分）求下图中的关键路径，给出算法思想和求解过程每一步的状态.（10分）输入关键字序列（55,12,24,47,30,68,19）,建立平衡二叉树.说明算法思想，给出插入和调整的具体过程示意图.（10分）设稀琉矩阵用三元组顺序表存储，说明快速转置算法思想，并用下面例子解释执行过程。A5m6=（（1,3,21）,（2,1,16）,（2,3,9）,（3,3,16）,（4,2,58）,（4,5,8）,（5,1,66））（10分）设L为带头结点的单链表，元素值为整型.编写函数，删除L中的重复结点（具有相同元素值的结点只保留一个）.先给出算法思想，再写出程序代码.（10分）已知一棵二叉链表表示的二叉树T,编写函数，判断T是否是完全二叉树.先给出算法思想，再写出程序代码。（10分）已知顺序表（a“a”…a.）是小顶堆，编写函数，将（a,此•••时,aQ调整为小顶堆，要求T（n）=0（logm）.先给出算法思想，再写出相应代码.操作系统部分(75分)简答(25分.每题5分)(1)缺页中断与其他普通中断的主要区别是什么？(2)开发程序时用动态链接库有什么优点？(3)在单缓冲情况下，为什么系统对一块数据的处理时间为max(C,T)+M?(4)什么是通道，什么是通道的瓶颈问题，如何处理此问题，请画出示意图？(5)推动I/O发展的动力是什么，有哪几个发展阶段？(10分)回答下列问题：(1)试说明页面置换算法在虚拟存储管理中的重要性.(2分)FIFO算法适用于什么场合，又有何缺点.(2分)(3)设页面走向为1,2,3,4,1,2,5,1,2,3,4,5,当物理页框数分别是3和4时，试问：采用FIFO、LRU置换算法产生的缺页中断分别是多少？(这里假设内存开始时都是空的并且只要是第一次用到的页面都产生缺页中断)(6分)(10分)A、B两个程序，程序A按顺序使用CPU10秒，使用设备甲5秒，使用CPU5秒，使用设备乙10秒，最后使用CPU10秒，程序B按顺序使用设备甲10秒，使用CPU10秒，使用设备乙10秒，使用CPU5秒，使用设备乙10秒.试问：(1)在顺序环境下执行程序A和程序B,CPU的利用率是多少？(3分)(2)在多道程序环境下，CPU的利用率是多少？请画出A、B程序的执行过程.(4分)(3)多道批处理中，是否系统中并发的进程越多，资源利用率越好，为什么？(3分)4.(10分)考虑5个进程Pl、P2、P3、P4、P5,如下表，规定进程的优先级越小，优先级越高，试计算在采用下述几种调度算法时各个进程周转时间和带权周转时间.假设忽略进程的调度时间.(1)先来先服务调度算法(FCFS);(2)时间片轮转调度算法(时间片为1ms)(RR);(3)最短作业优先调度算法(SJF);(4)剥夺式优先级调度算法(HPF).进程提交时刻需要的CPU时间(ms)优先级P1033P2265P3441

P4652P5824逻辑地址8 4 12段号内号段页逻辑地址8 4 12段号内号段页页内偏移01（1）说明在段页式系统中动态地址变换过程.（4分）（2）计算虚地址200804（十进制）的物理地址（用十进制表示）（3分）.（3）计算物理地址32784（十进制）的虚地址（用十进制表示）（3分）.6.（10分）某工厂有两个生产车间和一个装配车间，生产车间生产A、B两种零件，装备车间把这两种零件装配成产品.生产车间甲把生产的A零件放到货架F1上，生产车间乙把生产的B零件放到货架F2上，假设两个货架的容量都是10个零件.装配车间每次从货架上取出一个A和一个B然后进行装配，请用P、V操作来进行正确的三个车间管理.南京航空航天大学2017年硕士研究生入学考试初试试题（A卷）科目代码：922 满分. 分科目名称：数据结构与操作系统（专业学位） 晒万.但万注意：①认真阅读答题纸上的注意事项；②所有答案必须写在瓯缎上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！数据结构部分（75分）（5分）已知带权图如下所示，用Kruskal算法产生最小生成树，并说明算法思想.（10分）为一个家谱管理程序设计一种数据结构，以一个四代人，11个家庭成员为例，（A有3个孩子Al、A2、A3;A1有2个孩子All、A12;A2无子,A3有3个孩子A31、A32,A33;All有1个孩子Alli;A32有1个孩子A321;其余尚无子），画出家谱示意图，给出所设计的存储结构示意图，并给出在该存储结构上输出第k代所有人员的算法思想.（10分）设有8个字符（a,b,c,d,e,f,g,h）,其权值为（48,15,20,12,6,61,8,10）,给出进行Huffman编码所用的数据结构和求解过程数据结构中数据的最后结果。（10分）已知输入数据序列为（58,68,42,10,88,32,70,52,55,46）,给出建立3阶B-树示意图，再给出删除55,70后的B-树。（10分）试用Dijkstra算法，求下图中从VI到其余各顶点的最短路径，给出实现算法所用的数据结构和求解过程中每一步的状态.（10分）设A、B为递减有序（元素值为整型）的单链表，编写函数，利用原结点将它们合并成一个递增有序的单链表，相同元素值只保留一个结点.先给出算法思想，再写出相应代码.（10分）设二叉树T,用二叉链表结构存储.编写函数，对于每个元素值为x的结点，删去以它为根的子树，并释放相应的空间.要求先给出算法思想，再写出相应代码.（10分）设有n个学生成绩（0-100整数）的顺序结构线性表L,编写函数，将该线性表中调整为成绩及格（大于等于60）在不及格之前，要求T（n）=O（n）,S（n）=O（l）。先给出算法思想，再写出相应代码.操作系统部分（75分）.单选题（10分，每题1分）.在下列系统中，（）是实时系统.A.计算机激光照排系统B.军用反导弹系统C.办公自动化系统 D.计算机辅助设计系统.引入多道程序的目的在于（）.A.充分利用CPU,减少CPU等待时间 B.提高实时响应速度C.有利于代码共享，减少主、辅存信息交换量 D.解放cpu对外设的管理.已经获得除（）以外的所有运行所需资源的进程处于就绪状态A.存储器B.打印机C.CPUD.磁盘空间.采用时间片轮转法调度是为了（）.A.多个终端都能得到系统的及时响应 B.先来先服务C.优先级较高的进程得到及时调度 D.需CPU最短的进程先做.在一段时间内只允许一个进程访问的资源，称为（）.A.共享资源 B.临界区C.临界资源D.共享区.并发性是指若干事件在（）发生.A.同一时刻B.同一时间间隔内C.不同时刻D.不同时间间隔内.管道通信是以（）进行写入和读出.A.消息为单位B.自然字符流C.文件D.报文.操作系统中有一组特殊的程序.它们不能被系统中断，在操作系统中称为（）A.初始化程序B.原语C.子程序D.控制模块.在分段管理中().A.以段为单位分配，每段是一个连续存储区B.段与段之间必定不连续C.段与段之间必定连续 D.每段是等长的.通道是一种().A.I/O端口B.数据通道C.I/O专用处理机 D.软件工具.简答题(20分，每题4分).系统型线程和用户型线程有何区别？.多级反馈队列调度算法是如何工作的？.分段式系统和分页式系统有何区别？.引入缓冲的目的是什么，有哪些常见的缓冲模式？.SPOOLING技术如何实现，在操作系统中起何作用？3.(9分)设有三道作业，它们的提交时间及执行时间由下表给出：作业号提交时间执行时间18.52.029.21.639.40.5(1)周转时间和带权周转时间的区别是什么，为何引入带权周转时间？(2分)(2)试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间.(7分)(9分)某系统有A、B、C、D四类资源可供五个进程Pl、P2、P3、P4、P5共享.系统共有这四类资源为：A类3个、B类14个、C类12个、D类12个.进程对资源的需求和分配情况如下:进程已占有资源最大需求数ABCDABCDP100120012P210001750P313542356P406320652P500140656（1）现在系统是否处于安全状态？（4分）（2）如果进程P2提出需要A类资源。个、B类资源4个、C类资源2个和D类资源。个,系统能否去满足它的请求？（5分）（9分）某分页系统，每个页面长为1KB,某时刻该用户进程的页表如下：页号物理块号是否在快表中08是17是24否310否45否53是62是（1）请写出分页系统的地址转换过程（3分）（2）计算两个逻辑地址：0AC5H、1AC5H对应的物理地址（16进制表示）.（3分）（3）已知主存的一次存取为2us,对于快表的查询时间可以忽略，则访问上述两个逻辑地址分别耗费多少时间？（3分）（9分）在某请求分页管理系统中，作业执行时一次访问如下页面：1,4,3,1,2,5,4,2,1,4,5,若分配给该作业的主存块数为3.（1）页面置换算法在虚拟存储管理中的重要性.（2分））FIFO,LRU算法各适用于什么场合（3分）（3）计算FIFO,LRU,页面置换算法，试求出缺页中断次数.（4分）7.（9分）一家四口人，儿子喜欢吃苹果，由父亲负责购买，女儿喜欢吃橘子，由母亲负责购买.父亲和母亲购买水果后放到家中的抽屉里，儿子和女儿从抽屉里取出水果。假设抽屉只能容纳20个水果，同时只能一人开关，用纪录型信号量同步父母子女四个进程。南京航空航天大学2018年硕士研究生入学考试初试试题（A卷）科目代码：922 满分.150分科目名称： 数据结构与操作系统（专业学位） 酒力.必方_注意：①认真阅读答题纸上的注意事项；②所有答案必须写在圈题园上,写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！数据结构部分（5分）设n*n的矩阵A[l..n,l..n]为三角特殊矩阵，其逆对角线以上为0,逆对角线以及逆对角线以下的所有元素按行序压缩存储在一维数组B[l..n*（n+l）/2]中，根据i、j在满足何种条件下，计算元素A”的存储位置，给出推导过程.（1）带双亲的孩子链表表示法（2）孩子兄弟表示法（1）带双亲的孩子链表表示法（2）孩子兄弟表示法并说明这二种存储结构的优缺点.（10分）给定n个村庄之间的交通图，边上的值