南京理工大学-825-2012-真题

南京理工大学2012年研士学位研究生入学考试试题手斗目1码：825 科目名称：计算机专业基础CB)满分：150分注意认真阅读础纸上的注意事项：所有答案必须写在医噩噩上，写在本试题纸或草稿纸上均无效：本试题纸须随答题纸一起装入试题袋中交回！第一部分数据结构共75分一、选择题（每题2分，共20分）I.以下关于数据结构的说法，正确的是一一一一。2.3.4.5.6.7.8.A）数据结构仅由逻辑结构和基本运算两方面组成B）数据的逻辑结构相同，对应的存储结构也相同C)数据的逻辑结构与数据元素本身的形式、内容无关D）数据结构的逻辑结构是数据元素的各数据项之间的逻辑关系，而不是数据元素之间的逻辑关系。随着问题规模n的增长，以下时间复杂度量级中，量级最高的是一一oA)O(log2n)B)O(n3)C)O(n)D)O(n2)判断带头结点的循环单链表L中，只有一个数据结点的条件是一一一，A)L-next-next=LB)-L-next=L C)L=NULLD)L-next=NULL在一个长度为n的Jlli)j序存储的线性表中，若要在第i C 1三i.Sn+l）个位置插入一个元素，则需要从后向前依次后移一一一一个元素。A n-iB)iC)n-i-1对于n阶对称矩阵，如果采用以列序为主序的存储方式，存储单元。D)n-i+l则需要一一一一个A)n(n-1)/2B)2nC)n(n+I V2D)n2 将下图所示的工叉树按中序线索化后，结点E的左指针指向结点A)A B)C C)B D)H一棵完全二叉树上有722个结点，则该二叉树中叶子结点的个数是一一一一。A)362 B)361 C)363 D)360对下图所示的无向图，从顶点l开始进行深度优先遍历，可得到顶点访问序列为一一一一。9.A)I.2,4,5,6,3,7,8B)l,2,4,3,5,6,7,8C)I,2,4,3,5,7,8,6D)!,2,3,4,5,7,8,6己知有序表为4,5,6,8,13,15,17,22,23,25,28,36，用折半查找法查找值为36的元素时，所需的比较次数为一二一一。A)48)3C)20)510.简单排序方法中，当序列中的记录己“基本有序”时，一一一是最佳的排序方法A）起泡排序C）快速排序二、填空题（每全l分；;I.I;5分）B）简单选择排序D）直接插入排序1线性结构中数据元素之间的关系是一对一的关系，在树形结构中数据元素之间是一马上一一的关系。2.如右图所示的双向链表中，欲在与所指结点之后插入一个结点吨，请在下面的空格处填入正确的语句。P、s-pnor=p；一总干s-next=p-next；一?一豆L一；p-next=s;s一li口3.二叉树的后序遍历序列是DGEBFCA，中序遍历序列是DBGEACF，则先序遍历序列是(3)4.根据权值集合15,3,14,2瓜9构造相应的哈夫曼树，则该树的带权路径长度是(4)5，己知关键字序列为52，邸，51,60,96,16,87,24,52,61，用筛选法建雄，必须从值为一_fil一一的关键字开始。三、简答题（共6题，共42分）1.简洁顺序表和链表存储方式的优缺点。并说明，若频繁地对一个线性表进行插入和删除操作，则该线性表：应采用何种存储方式？(5分）2.若二叉树中叶子结点数为n口，且所有非叶子结点都有丘、右子树，则请回答该二叉树共有多少个结点？(4分3.简述二叉排序树和堆的主要区别。4分4.己知下图所示的二叉树是由某森林转换而来，i青画出其原来的森林（5分825计算机今业恭础（8)第1 g.7 贝第2页共7).各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研5.根据下图所示的AOE网，顶点V1,V2，町，町，Vs，吨，V1表示事件，酌，旬，句，ai岛，句，衔，饨，a9表示活动，i青回答以下问题：14分）a.=(I）求出所有事件的最早发生时间与最迟发生时间。（4分(2）求出所有活动的最早发生时间与最迟发生时间。（4分）(3）列出所有关键活动。（2分）弧(4）将本题的AOE网视为无向图（即将图中的有向边看成无向边，用克鲁斯卡尔算法构造一棵最小生成树并画出。（4分）6.设记录的关键字（key）集合是：(10分K=37,25,14,36,49,68,57,22 CI）从空树起，依次插入关键字生成一棵3阶B树，画出每一次插入后B树的状态。（4分(2）写出对该序列进行第一趟快速排序后的序列。（2分）(3）设Hash表表长m=12，选取Hash函数的方法为“除留余数法”，其函数形式为H(key)=key MOD 11，处理冲突的方法为“线性探测再散列”，请依次取K中各值，构造出满足所给条件的Hash衰，画出该晗希表的存储结构图。（4分）四、算法设计题（共8分）二叉树采用二叉链表作为存储结构，链表中结点的结构为：struct BTreeNode ElemType data;struct BTreeNode*le丘struct BTreeNode*right;i青编写个算法，计算二叉树中叶子结点的个数，算法对应的函数定义为intcount(BTreeNode*BT)825计算机专业基础（B)第3页共7页第二部分操作系统(75分一、单项、选择题（每题1分，共.20分）I.采用核序分配资源策略可以防止死锁，这是因为它能破坏产生死锁的四个必要条件之一。它所破坏的条件是一一一一一A）资源互斥使用B）占有且等待资源。不可抢夺资源D循环等待资源2.若干进程是可同时执行的，它们轮流占用处理器交替运行，这种进程特性称为丁了石磊性B）并发性C）异步性D）同步性3.操作系统采用多道程序设计技术，能有效提高效率的计算机器件是一一一一一A）缓存医B）通道C)CPUD）运算器4.操作系统的设备管理中采用缓冲池技术，缓冲池中共有4个缓冲区，每个缓冲区的大小跟一个磁盘块相等。如果在工作的过程中p发生缓冲区不够分配的情况，则优先收回在缓冲池中停留时间最长的那个缓冲区，缓冲池最初是空的。文件X的第i块记为X；（块号从0开始编号）如果用户程序对文件A和B进行如下操作：读Ao，读A2，读As，写Ao，读Bo，读酌，写As.那么，当操作系统接到用户程序发出“写As”请求时，读写磁盘的次数一共是一一一一一一次A)5B)6C)7D85.可变分区存储管理的主存分配算法中，查找次数最少的是一一一一分配算法A）随机适应B）最先适应。最优适应D）最坏适应6.进程有若干属性，它们是一一一一A）进程有多种状态，多个进程可以对应子相同的程序，多个进程可以并发运行B）进程只有一种状态，多个进程可以对应子相同的程序，多个进程可并发运行C）进程有多种状态，多个进程不可以对应子相同的程序，多个进程可并发运行D）进程有多种状态，多个进程可以对应于相同的程序，多个进程不可并发运行7.若系统在分配资源时不加以特别的限制，则可采用死锁检测的方法来解决死锁问题。所以该系统一一一一一一A）提高了资源利用率B）不会发生死锁C）有时要抢夺某进程的资源进行再分配D）能加快进程的执行速度8.设磁盘的读写磁头正从50号柱面移到55号柱面上操作，现有依次请求访问的柱面号为100,185，”，124,16,126,67,69.当55柱面号操作完成后，若采用电梯调度算法，为完成这些请求，磁头需要移动过的柱面数是一一一一A)279 B)289 C299D)309 9若某系统有菜类资源5个供若干进程共事，不会引起死锁的情况是一一一一一A有6个进程，每个进程需1个资源B有5个进程，每个进程需2个资源。有4个进程，每个进程需3个资源D）有3个进程，每个进程需4个贺，源10.下面关于临界区的叙述中，正确的是一一一一一A，向界区可以允许规定数目的多个进程同时执行B)临界区只包含一个程序段C,1备界区是必须互斥地执行的程序段D，备界区的执行不能被中断11.作业在执行中发生了缺页中断，经操作系统处理后，应让其执行一一f旨令。A）被中断的前一条B）被中断的后条C)作业的第一条D作业的最后一条825计算机专业基础（Bl第4民共7页各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研12.设备的打开、关闭、读、写等操作是由一一一一一一完成的。A）用户程序B）编译程序C）设备分配程序D）设备驱动程序13.能使作业平均周转时间最小的作业调度算法是A）先来先服务算法B）计算时间最短的作业优先算法。优先级调度算法D）均衡调度算法14.管理磁盘存储空间的方法是A）索引表、位示图、空闲块表B位示图、空闲块表、空闲块链C）空闲块表、空闲块链、索引表D）空闲块链、索寻表、位示图15.关于处理机调度，以下说法错误的是A）衡量调度策略的主要指标有2周转时间、吞吐率、响应时间和设备利用率B）处理机调度可以分为4级：作业调度、交换调度、进程调度和线程调度C）作业调度时，先来先服务法不利于长作业，最短作业优先法不利子短作业D）进程调度的算法有：轮转法、先来先服务法、优先级法16.分段管理提供维的地址结构。AIB)2 C)3D)417.如果允许不同用户的文件可以具有榈同的文件名，通常采用来保证按名存取的安全。A重名翻译机构8）建立索引表18.SPOOLing技术利用于一一一一A，外设概念B虚拟设备概念19.若页式存储管理中的地址格式为I 23 16 I ts则它的最大页号和最大页内地址是C）建立指针D）多级目录结构C.磁带概念D.存储概念。A)256和65536B)255和65535C)256和65535 D)255和6553620.实现“分配主存空间和重定位”属于操作系统中的A处理器管理B）存储管理。文件管理D）设各管理二判断题（每题l分，共10分）.创建线程比创建进程开销小。2.FCB长期存放于操作系统核心空间。3.同一程序可以由多个进程运行。4.缓冲技术因为增加了数据拷贝次数，所以不能改善I/0性能5.磁盘驱动程序磁盘请求生成后插入请求队列时进行为减少寻道时间的排队优化。6.磁盘中断优先级应该比打印机中断优先级低。7.在处理系统调用请求时应该屏蔽外部中断。8.进程申请资源时有可能进入等待状态e9.用户级线程实现不能支持同进程的多线程在多处理机并行运行。10.死锁避免tt死锁检测实用。三填空题每空l分，共10分）.一个程序在一个数据集上的一次运行称为一个2.地址转换是在作业执行前集中完成，执行中无需再进行地址转换的定位方式称为3.设与某资源关联的信号量初值为4，当前值为2。若M表示该资源的可用个数，N表示等待该资源的进程数，贝UM、N的值分别是一一4.通道的出现把从耗时的输入输出操作中解放出来5.有一个链接结构的文件，其中被链接的每个物理块存放一个逻辑记录和一个链接指针。目前，该文件中共存放了1、2、3、4、51i个逻辑记录。假设对应于该文件的目录项已经在内存中，那么完成删除记录4需访问磁盘一一次。6.若请求访问磁盘柱面2、4、7、9的要求己经依次到达，目前磁头位于柱面5,并正朝着柱面号大的方向移动。在这种情况下，比较现有的三种移臂调度算法（先来先服务、最短寻找时间优先和电梯调度）一一一一一算法需移动的柱面数最多。7.如果把一本词典的内容作为一个文件存放，每个单词和对它的解释组成一个记录。为了便于该词典的使用者迅速查到所需的单词，这个文件的存储结构采用文件结构比较合适8.分页系统中，作业内部碎片的平均大小为一一一一一。9-10.页是信息的单位，进行分页是出于系统管理的需要：段是信息的单位，分段是出于用户的需要。四a填空题Cl-4题每空1分，5题每空2分，共20分）l.假设一个磁盘组有100个柱面，编号为99，每个柱面有32个磁道，编号为0-31，每个盘面有16个扇区，编号为0-15。现采用位示图的方法管理磁盘空间。该盘组共被划分散个_ill_物理块。者采用字长为32位的字来组成位示圈，共需_ill_个字。2.在一个采用页式虚似存储管理的系统中，某进程依次要访问的字地址序列是：115,228,128，邸，446,102,321,432,260,l67，若作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，回答下列问题：按FIFO调度算法将产生L一迭缺页中断，依次沟汰页号是且一。按LRU调度算法，将产生_fil_一次缺页中断，依次淘汰页号是一业上一。3.假设某操作系统采用时间片轮转调度策略，时间片大小为lOOms，就绪进程队列的平均长度为5，如果在系统中运行一个需要在CPU上执行.0.8s时间的程序，则该程序的平均周转时间是7l一。4.一个磁盘系统中，最大的柱面号为100，最小柱面号为0。假设当前磁头位置的柱面号为54，正在从小号柱面向大号柱面方向移动。现在请求队列中要求访问的柱丽号顺序为99,18,44,18,67,75，如果使用SCAN算法，服务的顺序为ll_一。s.假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上进行登记，而且每次只允许一人进行登记操作。完成用信号量实现该过程的代码。struct semaphore s=100,mutex=1;cobegin reader(i)(i=l,2,.均2(9)(IQ)写登记表：Cl!)阅读；(12)825日算机专业蒜E出(B)第5页共7页第6 i,J共7页各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研！；IEI 写登记表：4且上；(14)离开：coend 五 简答题（每题5分，其15分）I.什么是线程？多线程技术具有哪些优越性。2.哪些事件的发生会引起进程调度？优先级调度和时间片轮转调度各有什么特点？为了使某个用户进程更快地运行，作为系统管理员可以采用哪些措施？3.简述操作系统的文件保护机制。文件旬柄可以通过创建子进程传递给子进程使用，但不能传递给其他进程使用，为什么？l第7页共7页825计算机专业基础(B)各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研