南京理工大学计算机科学与工程学院计算机专业基础B数据结构操作系统专业硕士历年考研真题汇编

南京理工大学计算机科学与工程学院计算机专业基础B数据结构操作系统专业硕士历年考研真题汇编第一部分数据结构(共75分)选择题(每题2分，共20分)0A)L->ncx[->nex(=B)L>next==L存储单元。6.将下图所示的二叉树按中序线索化后，结点E的左指针指向结点7.一棵完全二叉树上有722个结点，则该二叉树中叶子结点的个数是8.对下图所示的无向图，从顶点1开始进行深度优先遍历，可得到顶点访问序列为。A)I,2,4,5,6,3,7,8B)1,2,4,3,5,6,7.8元素时，所需的比较次数为。A)4B)3C)2D)5108简单排序方法中，当序列中的记录已“基本有序”时，是最佳的排序A)起泡排序B)简单选释排序C)快速排序D)直接插入排序二、填空题(每空1分；共5分) 三、简答题(共6题，共42分)插入和删除操作，则该线性表宜采用何种存储方式?(5分)该二叉树共有多少个结点?(4分)5.根据下图所示的AOE网，顶点Vi,Vz,V₃,Vs(1)求出所有事件的最早发生时间与最迟发生时间。(4分)(2)求出所有活动的最早发生时间与最迟发生时间。(4分)(3)列出所有关键活动。(2分)(4)将本题的AOE网视为无向图(即将图中的有向边看成无向边),用克鲁斯卡尔算法构造一棵最小生成树并画出。(4分)状态。(4分)四、算法设计题(共8分)第二部分操作系统(75分)一、单项选择题(每题1分，共20分)柱面号为100,185,39,124,16,126,67,69。当55柱面号操作完成后，若825计算机专业基础(B)第4页共7页12.设备的打开、关闭、读、写等操作是由A)用户程序B)编译程序C)设备分配程序D)设备驱动程序13.能使作业平均周转时间最小的作业调度算法是A)先来先服务算法B)计算时间最短的作业优先算法C)优先级调度算法D)均衡调度算法14.管理磁盘存储空间的方法是A)索引表、位示图、空闲块表B)位示图、空闲块表、空闲块链C)空闲块表、空闲块链、索引表D)空闲块链、索引表、位示图15.关于处理机调度，以下说法错误的是A)衡量调度策名的主要指标有：周转时间、吞吐率、响应时间和设备利用率B)处理机调度可以分为4级：作业调度、交换调度、进程调度和线程调度D)进程调度的算法有：轮转法、先来先服务法、优先级法16,分段管理提供维的地址结构。17.如果允许不同用户的文件可以具有相同的文件名，通常采用来保A)重名翻译机构]B)建立索引表C)建立指针D)多级目录结构18.SPOOLing技术利用于则它的最大页号和最大页内地址是A)256和65536B)255和65535C)256和65535D)255和6553620.实现“分配主存空间和重定位”"属于操作系统中的A)处理器管理B)存储管理C)文件管理D)设备管理I.创建线程比创建进程开销小。2.FCB长期存放于操作系统核心空间。3.同一程序可以由多个进程运行。4.缓冲技术因为增加了数据拷贝次数，所以不能改善I/O性能。5.磁盘驱动程序磁盘请求生成后插入请求队列时进行为减少寻道时间的排队优6.磁盘中断优先级应该比打印机中断优先级低。7.在处理系统调用请求时应该屏蔽外部中断。8.进程申请资源时有可能进入等待状态。9.用户级线程实现不能支持同一进程的多线程在多处理机并行运行。10.死锁避免比死锁检测实用。三.填空题(每空1分，共10分)1,一个程序在一个数据集上的一次运行称为一个。2.地址转换是在作业执行前集中完成，执行中无需再进行地址转换的定位方式称为"3.设与某资源关联的信号量初值为4,当前值为-2。若M表示该资源的可用个数，第5页共7页8,分页系统中，作业内部碎片的平均大小为9-10,页是信息的单位，进行分页是出于系统管理的需要；段是信息的 单位，分段是出于用户的需要。四.填空题(1-4题每空1分，5题每空2分，共20分)1.假设一个磁盘组有100个柱面，编号为0—99,每个柱面有32个磁道，编号为0-31,每个盘面有16个扇区，编号为0-15。现采用位示图的方法管理磁盘3.假设某操作系统采用时间片轮转调度策略，时间片大小为100ms,就绪进程队列的平均长度为5,如果在系统中运行一个需要在CPU上执行.0.8s时间的问的程面号顺序为99,18,44,18,67,75,如果使用SCAN算法，服务的顺五.简答题(每题5分，共15分)2011年南京理工大学计算机科学与工程学院825计算机专业基础B[专业硕士]考研真题2011年硕士学位研究生入学考试试题科目代码：825科目名称：计算机专业基础(B)满分：150分第一部分数据结构(共75分)一、填空(每题2分，共20分)1.算法分析的目的是2.用邻接表表示图时，顶点数为n,边数为e,在邻接表上执行图的深度优先遍历操作时，时间复杂性。指向链表中任意结点。若在指针p所指结点之后插入结点s,则应执行的操作;若在指针p所指结点之前插入结点s,则应执行的操作5.设待排序的序列为{48,35,60,13,75,80,26,49}下面是排序过程：(4)这一趟排序的序列为(6)6.二叉树的存储结构定义为TypedefstructBiTreeNode*Lchild;*Rchild;//指针t是二叉树的根指针elsereturnunknownLchildunknowtypedefstructLNode{二、简答题(共23分)3.(12分)对于下图的AOE网(1)填写下面的2个表(各2分)事件最早发生时间最迟发生时间活动最早发生时间最迟发生时问(2)列出关键活动(2分);(3)忽略图中的权值，将图看成AOE网，写出图的3个拓扑序列(3分):825共6页第2页4.(5分)简述分块查找的数据组织方式及查找过程。三、(每题5分，共20分)设有一个输入数据的序列是{46,25,78,2.逐个输入各个数据生成的3阶B-树，画出过程；1.(4分)图用邻接表存储，若已知顶点Yi和Vj.写出判断Vi与Yj__intadjvex;//边(弧)的另一顶点的在数组中的位置ArcNode*finrstarc://指向关联该顶点的边(弧)链表2.(8分)设有线性表L={al,a2,…,an),顺序存储，试写一个算法将该线性表typedefstruct{typedefstructLNode{第二部分操作系统(75分)、选择题(每题1.5分，共30分)。A)就绪状态B)阻塞状态C)运行状态D)撤消状态85共6页第4页A)重名翻译机构B)建立索引表C)建立指针D)多级目录结构A)分区式B)分页式C)分段式D)段页式A)地址动态重定位B)时钟管理C)进程调度D)中断系统A)磁盘B)磁带C)打印机D)键盘、显示终端二、填空题(每空1分，共5分)三、问答题(共15分，每题1分)1、已知某分页系统，主存容量为64K,页面大小为1K,对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。则十进制的逻辑地查找时间，实行电梯算法(初始由外向里移动)需要查找时间(假定磁指令。块号页号访问时间修改位01232103块号页号访问时间修改位012321030011001FIFO算法(8)块将被换出，使用CLOCK算法(9)块将被换出加载时间a)每个信号量的初值应该是多少?b)填写下面的P、V操作读者进入阅览室的动作描述填写登记表；进入阅览室读书；}四、简单题(25分，每题5分)2010年南京理工大学计算机科学与工程学院825计算机专业基础B[专业硕士]考研真题2010年硕士学位研究生入学考试试题第一部分数据结构(75分)一、选择题(每题2分，共20分)1.算法的空间复杂度是指()。A)B)C)D)结点的()。7.一个有n个顶点的无向图最多有()条边。9.顺序查找法适合于存储结构为()的线性表。二、填空题(每空1分，共10分)7.以数据集{4,5,6,7,10,12,18}为结点权值所构造的哈夫曼树的带权路9.一组记录的排序值为{25,48,16,35,79,82,23,40,36,72},请给出三、简答题(共6题，共35分)1.(4分)简述二叉树的定义。2.(5分)简述拓扑排序的概念和拓扑排序的过程。3.(7分)一个二叉树如下图所示：4.(6分)已知无向图G如下图所示：(1)请画出该无向图G的邻接矩阵表示。(3分)(2)请画出该无向图G的邻接表表示。(3分)(3)列出所有关键活动。(2分)6.(5分)设有一组关键字{6,01,36,14,29,20,84,27,68,11,10,70},四、算法设计题(共2题，共10分)编写在该单链表中删除一个最小值结点的算法voidDelMinNode(LinkListtypedefstruct{基于上述类型模块，写出循环队列出队算法intDeQueue(SqQueue&Q,第二部分操作系统(75分)一、选择题(每一选项1分，共15分)A)尺寸从小到大B)尺寸从大到小C)地址从小到大D)地址从大到小A)一个进程多次申请，释放该资源B)若干并A)主存与外设B)CPU与外设C)外设与外设D)CPU与辅存A)允许有两个B)可以有多个C)最多有1个D)至少有1个量15、设有12个同类资源可供四个进程共享，目前剩余资源数为2。现资源分配2332333进程P46742341P.1P当进程P,P₂,P,P,满足的要求。二、填空题(本大题共10小空，每空1分，共10分)(1)采用先进先出(FIFO)淘汰算法，缺页次数是(3)(2)采用最进最少使用(LRU)淘汰算法，缺页次数是(4)(3)若用优化(0PT)算法，则次数是(5)4、假定一磁盘有200个磁道，编号是0至199,在完成了磁道143处的请求后，当用FCFS(先来先服务),最短寻道时间优先(SSTF)和扫描(SCAN,按磁道号递增移动)来按排磁头移动时，其移动的总量分别是(6),三、概念填空，从供选择的答案选出最确切的答案填入下面叙述中的内(1*16分)1、A以操作系统为支