2018年南京工业大学828数据结构与操作系统真题

南京工业大学2018年硕士研究生入学考试初试试题（A卷）科目代码：828科目名称：数据结构与操作系统满分：150分注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！第一部分：数据结构（共90分）单项选择题（下列每题给出的四个选项中，只有一项符合试题要求。每小题2分，共30分）1、通常所说的时间复杂度是指。A.语句的频度B.算法的时间消耗C.渐进时间复杂度D.最坏的时间复杂度2、等概率条件下,在由n个结点构成的顺序表上做插入结点操作,需平均移动的结点数为。A.nB.(n-1)/2C.n/2D.(n+1)/23、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是。A.O(1)B.O(n)C.O(n2)D.O(logan)4、从一个栈顶指针为top的链栈中删除一个结点时,用x保存被删除的结点,20应执行下列命令。A.x=top:top-topnextB.top=Top-next;=topdataB.C.x=Top-data;D,x=Top-data;Top-top-next5、循环队列SQ队满的条件是。A.SQ-rear=SQ-froat;B.(SQ-rear+1)%MAXLEN=SQ-froatC.SQ-rear+2=SQL-froatD.(SQ-rear+2)%MAXLEN=SQLfroat6、某队列允许在两端进行入队操作,但仅允许在一端进行出队操作(称为输出受限的双端队列),若五个元素a,b,c,d,e依次进队,则不可能得到的出队顺序是。A.bacdeB.dbaceC.dbcaeD.ecbad7、对特殊矩阵采用压缩存储的目的主要是为了。A.表达变得简单B.对矩阵元素的存取变得简单C.去掉矩阵中的多余元素D.减少不必要的存储空间8、一颗具有25个叶结点的完全二叉树最多有个结点。A.48B.49C.50D.519、在线索二叉树中,t所指结点没有左子树的充要条件是。A.t-left=NULLB.t-Itag=TRUEC.t-Itag=TRUE且t-left=NULLD.以上都不对10、设有一个二维数组A[m][n],假设A[O][0]存放位置在644,A[2][2]存放位置在676,每个元素占一个空间,则A[3][3]存放位置为。A.688B.678C.692D.69611、将一棵树转换为二又树后,这棵二叉村的形态是。A.唯一的,根结点没有左孩子B.唯一的,根结点没有右孩子C.有多种,根结点都没有左孩子D.有多种,根结点都没有右孩子12、在图1中,从顶点a出发,按深度优先遍历,不可能得到的顶点的序列为。A.a,b,e,c,d,fB.a,b,e,c,f,dC.a,c,d,f,b,eD.a,b,c,d,f,e13、下面关于工程计划的AOE网的叙述中，不正确的是。A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有关键活动都提前完成，那么整个工程将会提前完成D.某些关键工程若提前完成，那么整个工程将会提前完成14、分别以下列列序构造二叉排序数(二叉查找树,与用其他三个数列所构造的结果不同的是。A(30,10,40,5,50,20,35)B.(30,40,5,50,10,20,35)C.(30,40,10,50,5,35,20)D.(30,10,5,20,40,50,35)15、有一组关键字(3,12,258,33,15,22,64,20,55,26),采用除留余数法构造散列函数,H(key)=keymod11,则将发生次冲突。A.3B.4C.5D.6二、综合应用题（5小题，共60分）16、已知一个箭头结点的单项箭表,试完成函数voldcopyList(LISTh1,list&h2),实现将链表h1中的所有元素复制到链表h2中,具体要求如下:(1)定义链表的结点的抽象数据类型node,其所包涵的数据为:intdata,并定义链表结点的型LIST(node类型的指针);(2)在(1)的基础上完成函数copyList。17、试完成求二叉树的叶子结点的函数intleafNunt(BTREE,T),具体如下:(1)定义用左右键方法表示的二叉树的抽象数据类型node和型BTREE(node)类型的指针,(2)编写函数leafNunt(BREET),返回树T的叶子结点的个数。18、现在所有如下9个元素:7、16、49、82、5、31、6、2、44,画出将每个元素依次插入堆中构成最大堆的过程,具体要求如下,用第一个元素7构成一个二叉树,然后将第二个元素16插入该二叉树中,再将第三个元素49插入堆中直到最后一个元素插入为止。上述每一个插入过程都要求画图完成,并标注每一个结点插入的初始位置以及调整路线和调整后的位置。19.给定如图2所示的有向网络,利用Dijkstra法求从顶点v1到其他各定点的最短路径。V1V3V4V6V2V54510101530151520602015具体要求如下(1)填写下表,模拟Dijkstra算法的实现过程。其中S为当前已考虑的点的集合；w为每一步加入集合S的点的编号;D[i]为v1到vi的最高距离(如果v到vi之间还没有通路,则D[i]为INF);p[i]为v1到vi的最短路径中离vi最近的点。(2)根据上表中的D的值,求v1到其他各顶点之间的距离(3)根据上表中的P的值,求v1到其他各顶点之间的最短路径,并简要说明求解过程。20、给定AOE网如图3所示(起始点为V1,结束点为V10)；(1)分别计算每个事件Vi的最早发生时间VE(i)和最迟发生时间VL(i)。(2)根据(1)的结果,分别计算每个活动ai的最早发生时间E(i)和最迟发生时间L(i)(3)根据(2)的结果,求得关键活动。并画出表示关键活动的有向图。步骤SWD[2]D[3]D[4]D[5]D[6]P[2]P[3]P[4]P[5]P[6]初态1—4515INF15INF1111123456第二部分:操作系统(共60分)一、单项选择题1、操作系统是一组。A.文件管理程序B.中断处理程序C.资源管理程序D.设备管理程序2、现化操作系统的两个基本特征是和资源共享。A.多道程序设计B.中断处理程序C.程序的并发执行D.实现分时与实时处理3、进程控制块是描述进程状态和特性的数据结构,一个进程。A.可以有多个进程控制块B.可以和其他进程共用一个进程控制块C.可以没有进程控制块D.只能有唯一的进程控制块4、采用时间片轮转法进行进程调度是为了。A.多个终端都能得到系统的及时响应B.先来先服务C.优先级较高的进程得到及时响应D.需要CPU最短的进程先做5、资源的有序分配策略破坏条件,是一种死锁预防策略。A.互斥条件B.保持和请求条件C.不剥夺条件D.环路等待条件6、按照作业到达的先后次序调度作业,排队等特时间够长的作业被优先调度,这是指调度算法A.先来先服务B.最短作业优先C.定时轮转法D.优先数法7、在存储管理中,为实现地址映射,硬件应提供两个容存器,一个是基址寄存器,另一个是。A.控制寄存器B,程序状态寄存器C.限长寄存器D.通用寄存器8、很好地解决了内存“碎片”问题的存储管理方式是。A分页存储管理B.分段存储管理C.可变分区存储管理D.固定分区存储管理9、现在现代操作系统中采用缓冲技术的主要目的是。A.改善用户编程环境B.提高CPU的处理速度C.提高CPU和设备之间的并行程度D.实现设备与无关性10、索引式(随机)文件组织的一个主要优点是。A.不需要链接指针B.能实现物理的动态分配C.回收实现比较简单D.用户存取方便二、计算题11、桌上有一空盘,允许存放一只水果。爸爸可向盘中放苹果,也可向盘中放橘子,儿子专等吃盘中的橘子,女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用,请用P,V原语实现爸爸儿子、女儿三个并发进程的同步。12、假设有四个作业的单道系统。它们的提交、运行时间如下表所示(时间单位:小时,以十进制进行计算)。若采用越于优先权的非抢占式调度算法(优先数高者优先权低)试回答(1)作业应以怎样的顺序调度?给出分析过程。(2)计算平均带权周转时间。13、在分页存储管理系统中,存取一次内存的时间是8ns,查询一次快表的时间是1ns,缺页中断的时间是20ns。假设页面的查询与快表的查询同时进行,当查询页表时,如果该页在内存但快表中没有页表项,系统将自动把该页页表项送入快表，一个作业最多可能保留3个页面内存,现在开始执行一作业,系统连续对作业的2,4,5,2,7,6,4,8页面的数据进行一次存取,如分别采用FIFO算法和最优页面置算法,求每种算法存取这些数据需要的总时间。14、旋转型设备上信息的优先化分布能减少若干个I/O服务的总时间。设磁鼓上分为20个区,每区存放一个记录,磁鼓旋转一周需20毫秒,读出每个记录平均需用1毫秒,读出后经2毫秒处理,再继续处理下一个记录。在不知当前磁鼓位置的情况下,(1)顺序存放记录1、…、记录20时,试计算读出并处理20个记录的总时间;(2)给出优先分布20个记录的一种方案,使得所花的总处理时间减少,且计算出这个方案所花的总时间。作业号到达时间运行时间优先数A8.02.04B8.50.56C9.00.22D9.51.05