南京理工大学计算机科学与工程学院824计算机专业基础A历年考研真题汇编

南京理工大学计算机科学与工程学院

824计算机专业基础A历年考研真题汇编THROUGHTRRIN最新资料，WORD格式，可编辑修改!TOC\o"1-5"\h\z\o"CurrentDocument"2012年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题 32011年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题 132010年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题 222009年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题 312008年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题 392007年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题 502006年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题 602005年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题 702004年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题 782003年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题 862012年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题南京理工大学2012年硕士学位斫究生入学考试试题科目代码：824 科目名称：计算机专业基础（A）满分：150分注意:①认真阅读答题纸上的注意事项；②所有答案必须写在溶画|上,写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！第一部分离散数学（50分）.已知K是4上的自反和对称的二元关系，试证明：（8分）（1）对于任意的nwW,肥具有对称性；（2），（的为4上的等价关系..已知48,CO为四个集合，/为/到3的满射，g为C到。的满射，且{cC=3cD=O.h为AkjC至!IBuD的映射，且对于Vxe/l^C.A（x）=fW^XeA,试证明方为6C到爪。的满射.（6分）U（x）当xwC.彳为一个集合，试证明i川（6分）.G=（匕E）是一个简单无向平面图，若|E[<30,则G中至少有一个顶点的度数小于等于4.（6分）.G=(匕玲是一个连通且无图的图。若G中仅有两个1度顶点，期G可以画成一条直线.(6分).设/和g都是群(40到群(8J)的同态映射，证明(CQ是(46的一个子群，其中C={x|xe4M/Xx)=g(x)}(6分).把下列语句翻译为谓词演算公式(每小题3分，共6分)(1〉任何个集合X,总存在一个集合3,使得8的基数比人的基数耍大：(2)布.些大学生喜欢所有的网络游戏..已知知识的表示如下；Ux(P(x)t(4(x)v8(x))) .<2)Vx(N(x)fQ(x))rUx(P(x)T0(x))824计算机专业品端(A)第I页共6页结论：3xU\x)B(x)),贰用归结原理证明之“〈6分)第二部分 数据结构(共50分)一环空(每个空瓶1分，共15分)LAOE网中的关键路径是LO,.与线性表的麟接存贮方式相比较，线性表的顺序存世方式的优点於⑵缺一是.131。..二叉树的先序和中序遍历序列分别是ABCDEFG,CDBAFEG,则后序遮历序列是一(4) °.有向图G=(V,A4其中Vyabcde}.A={<a,b>,<a、c>,<d,c),vdQ,<b,e>,v%e>,<c,b>},清给出的一个拓扑序列：⑸°.在一个带头结点的循环征队列中，结点的结构为(da弭next),有指针p指向队列最后一个元素.若第一个元素出队列，则应执行的操作为：s=p->next->next;(6) .；fiec(s)(free⑸也可以用deletes)«.一棵二叉树中叶子结点数刖和度为2的结点数匹之间满足以下关系：no=n2+l；一棵满k叉树上的叶子结点数n°和非四结点数n(之同满足一⑺关系。1.一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向岩)用自然数依此对结点编号，则编号最小的哇子的序号是_W_:编号是i的•点斫花的层次号是一(9)(根所在的层次号规定为1层人.有关键字序列为：(20,11.12,9,23,42,44,36)/对应的大顶堆为：10)一;一趟冒泡排序后的序列为：(II)；将序列中的关键字看作权值，构造哈夫曼树，其带全路径长度为：(⑵。.若某二叉树有20个叶子结点，有304结点仅有一个孩子，则该二叉树的结，数是C3），.在无序线索二叉楼中，若P炉指结点的右孩子域为孩子指价，则P的后继结点是（14） ..在B-树中剁除关键字K,若Ki为并终端结点中的关维字,则以 C5）代替心二、（15分）笥答题：设关键字的输入序列为{55,31,11,37,46,39}（5分）从空树开始构造平衡二叉树，画出每加入一个新结点时二叉树的形态，若发生不平锄，指明需做的平衡旋转类型及平衡旋转的绍果，《4分）所出1.中二叉树的二叉链表存储结构，并给出对该二叉树进行中序遍店的雉出序列.（2分）构造一棵二叉排序梃.（4分）画出在2,中的二叉排序树服除31后的二叉排序树，接着再班824计算机y业耳咄（A）第2支共6支除55后的二叉排序树.三、（】0分）对给定的有6个顶点的无向图的邻接矩阵如F：.（3分）画出邻接表存储结构：.（2分）画出该无向图；.（3分）画出该图的最小生成树；.（2分）给出从V1出发的深度优先遍历序列和广度优先遍历序列:8 1260087 8684002686656oo600003qo4600ao7ooao537co四、（10分）用类C（类-C++）写出如下算法：1.（4分）已知源二叉树s,将其复制成另一棵二叉树t.voidCopyTree（BiTNodes,BiTNodet）二叉树用二叉链表存储，存储结构定义为：typedefstructBiTNode{Elemtypedata;structBiTNode,[child,*rchild;}BiTNode,*BiTree;（6分）线性表用单握表存储，使用尽可能少的存储空［可将其元素全部颠踮倒。 statusTum（Linklist链表有头结点单链衣的存储结构定义为：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkLis!;第三部分操作系统（50分）单项选择题（每题1分，共20分）.当沙兜机区分了管态（系统态）和月态（用户态）指令之后，从管态到目态的转换是由操作系统程序执行后完成的，而目态到管态的转换则是由 完成的.A.硬件 B.管态程序C.用户程序 D.中断处理程序.作业在执行中发生了缺页中断’经操作系统处理后，应让其执行指令.A.被中断的前一条 B.被中断的后一条C..作业的第一条 D.作业的最后一条.在用户程序中将一个字符送到显不器上显示，使用的是操作系统提供的接口.A.系统调用 B.库函数C,原语 D.例理824计算机专业拈裙（A） 第3页共6克.在文件系统中引入“当前目录”的主要目的是A.方便用户 B.提高系统性能C.增强系统安全性D.支持共享访问.为了便于上层软件的编制，设备通常需要提供是A.控制寄存器、状态寄存器和控制命令I/O地址寄存器、工作方式状态寄存器和控制命令C.中断寄存耦、控制寄存器和控制命令D.控制寄存器、编程空间和控制逻辑寄存春.在批处理操作系统控制下实现多道程序并行工作,从系统的角度，主要希望进入“输入井”的作业能够 ,A.响应时间短 B.平均周转时间短oC.题务费用低 D.长作业优先得到服务.并发进程中与共享变是有关的程序段被称为临界区,因此这姐并发进程A.相茎间是有交互的 B.拥有一个共同的临界区C.不能修改共享变量的值 D.执行络果不受执行速度的影响8,采用伸态分配资源策略可以防止死校,这是因为 A.破坏了互斥使用货源的条件 B.系统不会出现循环等待资源的现政C.提高了资源利用率 D.能随时检泅资源的使用情况.用户“实现按名存取”属于操作系统中的A.处理那管理 B.存储管理C.文件管理 D.设务管理.进程的并发性是指A.一组进程可同时执行B.每个进程的执行结果不受其它进程的影响C.每个进程的执行都是可再现的D.通过一个进程创建出多个进程.在下列选项中，不属于造成某进程状态从等特态到就绪态变化的原因是_A.有更高优先级的进程要运行B.读进程占用的外围设备工作结束C.该进程等待的货源得到满足D.谈进程等待干位的故障被排除.某文件共有4个记录采用箧接存储结构，每个记录及链接指针占用一个磁盘块，主存储器中的磁盘缱冲区的大小与磁盘块的大小相哥・为了在L和L，之间插入-个记录Lj•（已蛭在内存中），需要进行的磁盘掾作有一A.4次读盘和2次写盘 B.4次读盘和1次写盘C.3次读盘和2次写盘 D.3次读盘和I次写盘13.采用银行家算法可避免死桢的发生，这是因为该算法A,可抢夺已分配的资源B.能及时为各进程分配资源C.任何时刻都能保证每个进用得到所需的资源D.任何时刻都能保证至少有个进程可利到所需的全部资源.假定一个分时系统允许20个终端用户同时工作•若分配给每个终端用户的时间片为50毫秒,而对终端用户的每个请求需处理200曝秒给出应答，那么终潮的最长响应时间为秒A.1B.2C.3D.4.页式存储管理中，作业运行时，该作业的页表是放在 X24H■机专业呆哇（A>箍4天共6页踮A.磁盘B.主存系统区C.主存用户区 D.用户程序.为实现磁盘空间的分配与回收，UNIX采用的是A.位示图法B.单块链接法C.成组链接法D.索引链接法.假设每条磁道被分为8个扇区，每个扇区存放一个记录，处理程序顺序处理这8个记录L，L2，…，U.每次请求从磁盘上读一个记录，然后对读出的记录花1ms的时间进行处理，以后再读下一个记录进行处理.磁盘旋转一周花费16ms（即每读一个扇区需2ms）.若将这8个记录在•条磁道上进行优化分布，则全部处理完这8个记录至少需要msA.31B.32C.33D.34.虚拟页式存储管理中页表有若干项，当内存中某一页面被淘汰时，可根据其中哪一项决定是否将该页写回外存.A.是否在内存标志B.外存地址C.修改标志D.访问标志.有一磁盘，共有10个柱面，每个柱面20个磁道，每个盘面分成16个扇区.采用位示图对其存储空间进行管理.如果字长是16个二进制位，那么位示图共需字.A.200B.128C.256 D.100.校友会的文件系统磁盘库中，“毕业生档案”文件的记录包含的数据项是毕业年份、身份证号和在校时档案材料.由于各人的档案信息量不同，记录的长度因人而异，但记录总是先按照毕业年份，然后按身份证序号在磁盘中顺序存放.使用这个文件的方式是按毕业年份和身份证号快速查出此人的档案材料.适合这个文件的逻辑结构是A.顺序结构 B.准接结构 C.索引结构 D.索引顺序结构解答题（1-5题每空1分，6题每空2分，共20分）.在具有N个进程的系统中，允许M个进程（NZM21）同时进入它们的共享区,其信号量s的值的变化范围是（1）,处于等待状态的进程数场多是3个..假设某操作系统采用时间片轮转调度策略，时间片大小为100ms,就绪进程&列的平均长度为5,如果在系统中运行一个需要在CPU上执行0.8s时间的程

序，则该程序的平均周转时间是一□1_.平均等待时序是（4）.（不考虑10情况）.在页式虚存管理系统中，设页面大小为2\页表内容如卜，现访问虚地址:（233）8,则将虚地址（233）1t变换成物理地址是（5）.页表：（表中的数均为八进制）衣号有效位页帧号轴存块号001004011517721206304.假定在某动臂磁盘匕刚处理了访问75号柱前的请求，目前正在74号柱面上读信息，且有如下清求序列在等待访问磁盘; 请求序列12345678欲访问柱面号22481931889278156101写出电梯调度算法处理时的序列次序。写出最短寻找时间优先算法时处理的时窗的移动方向改变了 （7）次..假定在一个请求页式存储管理系统中，某作业J所涉及的页面依次为页面访824计算机专业条何（A）第5页共6女问序歹U：2,3,2』,5,2,45325,2'分配内存块：3块.采用页面调度算法LRU产生缺页中断的次数是优)，采用FIFO产生缺页中断的次数是(9),采用Clock算法产生歌页中断的次数是一001，.战地指挥官通过无线电不断地向他的两个士兵下达作战指令，但是他必须在得到所有士兵对前一条指令的“确认”之后才能下达新的指令。使用P、V集作完成指挥官和士兵之间的协同管理。structsemaphoreSl=(11) .S2-1;cobeginprocess指挥官：beginwhile(true){(⑵：(13):向上兵1发送指令；O向士兵2发送指令：}end；process士兵】begin -while<tme){接收指挥官的指令；(14);}end；process士兵2beginwhile(true){接收指挥官的指令：(15J;踮end；coend三.简答题(每题5分，共10分).什么是进程和线程？应用程序可以采用多进程实现，也可以采用多线程实现,试分析这两种实现方法对应用程序的运行有什么影响？.什么是设备无关性？*，4i+flr机专业战砧(A)笫6页共6页2011年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题南京理工大学2011年硕士学位研究生入学考试试题科目代码：824科目名称：计算机专业基础(A) 满分：150分注意：①认真阅读答题纸上的注意事项；②所有答案必须写在函国上，写在本试题纸或草稿纸上均无效：③本试题纸须随答题纸一起装入试题袋中交回！数据结构(共50分)一、填空(每个空格1.5分，共15分).线性表的两种存储方式是和(2)。.用邻接表表示图时，顶点数为n,边数为e,在邻接表上执行图的深度优先遍历操作时，时间复杂性(3).对二叉排序树树进行(4) 遍历，可以得到树中数据元素的有序序列..由带权为3、9、6,2、5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为..棵一叉树中，度为2的结点有15个，度为1的有30个，则叶子数有(6)个。.设待排序的序列为(48,35,60,13,75,80,26,49}下面是排序过程：TOC\o"1-5"\h\z(48) 35 60 13 75 80 26 49(35 48) 60 13 75 80 26 49(35 48 60) 13 75 80 26 49(4)这一精排序的序列为 (7〉 .7.单链表的存储结构定义为：typedefstructLNode{EletnTypedata;structLNode*next;}LNode,*LinkList;下面是单链表的插入算法，请在空格处填入正确的语句.StatusInsertnode(Link!ist&L,inti,EletnTypee){//L为无头结点的链表,在第i个元素结点前面插入元素e：s=(LinkList)malloc(sizeof(LNode));//分配新结点824计算机专业基A第I贞共7人s-〉data=e;if((8) ))s->next=L;L=SsreturnOK：)p-L；j=O：while((9))(p=p->next;++j;)〃寻找第i4个元素结点if((10))returnERROR：//i小于1或者大于表长s->next=p->next;p>next=s; 〃插入新结点returnOK;I//LinstTnsert_L二、简答题(15分).分别画出右图所示二叉树的存储表示：(3分)(1)顺序表示；(2)二叉性表表示法；(3)静态链表表示..对于下图的AQE网(12分)(1)填写下面的2个表(各2分);(2)事件vlv2v3v4v5v6v7最早发生时间最迟发生时间活动ala2a3a4a5a7aBa9alO及早发生时间最迟发生时间(2)列出关键活动(2分)；(3)忽略图中的权值，将图看成AOE网，写出图的3个拓扑序列(3分)；(4)将图看成无向图(将图中的有向边看成无向边)，商出最小生成树(3分)；三、(每题5分，共10分)设有一个输入数据的序列是{46,25,78,62,12,37,70.29).L逐个输入各个数据生成的3阶B-树，画出过程；2.设Hash表表长m=13,选取Hash函数为H(key)=keyMOD11,处理冲突的方法为“线性探测再散列",请对输入序列构造Hash表.四、算法(10分)二叉树的存储结构如下：typedefstructBitNode(Telemlypedata:structBitnode*lchild,*rchild;}BitNode.*Bitree;用类C写出二叉树中序遍历的非递归算法.注；算法中可能用到的枝的操作Ini(Stack(s)s初始一个化栈sPush(s,p)：将所指向的结点进s栈Pop(s,p)：s栈顶元素出栈gettop(s,p)：取s栈顶元素stackempty(s)：判栈s是否为空

操作系统（共50分）一、选择题（每题1分，共20分）1、为了实现多道程序设计，il算机需要有.A）更大的内存B）更快的外部设备C）更快的CPUD）更先进的终端2.、进程的—和并发性是两个很重要的属性.A）动态性B）鄢态性C）易用性D）顺序性3、P、V黑作是.A）两条低级进程通信原语C）两条系统调用命令B）两条高级进程通信原语D）两条特权指令4、在下列操作系统的各个功能组成部分中，—不需要硬件的支持。A）进程调度 B）时钟管理C）地址映射 D）中断系统5,关于处理机调度，以下说法错误的是—.A）衡量调度策略的主要指标有：周转时间、吞吐率、响应时间和设备利用率B）处理机调度可以分为4级：作业调度、交换调度、进程调度和线程调度。作业调度时，先来先服务法不利于长作业，最短作业优先法不利于短作业D）进程调度的算法有：轮转法、先来先服务法、优先级法6、分段管理提供—维的地址结构.A）1 B）2C）3 D）47、若一个系统内存有64MB,处理器是32位地址，则它的虚拟地址空间为 字节.A）2GB B）4GBC）100KBD）64MB8、操作系统中的工作集模型与一有关。A）合并存储区中的空白块A）合并存储区中的空白块C）•个进程访问的页面集合9、成组健法是用于_.A）文件的逻辑组织C）文件存储器空闲空间的组织B）将CPU分配给进程D）为进程分配1/0资源B）文件的物理组织D）文件的目录组织10、虚拟页式存储管理中页表有若干项，当内存中某一页而被淘汰时，可根据其中哪决定是否将该页写回外存—.A）是否在内存标志 B）外存地址C）修改标志 D）访问标志11、有一磁盘，共有10个柱面,每个柱面20个磁道，体•个盘面分成16个扇区.采用位824计算机专业基础A第4次共7页图对其存储空间进行管理。如果字长是16个二进制位，那么位示图共需_字.A)200A)200B)128C)256D)10012,设备的打开、关闭'读、写等操作是由—完成的。A）用户程序B）编译程序C）设备分配程序 D）设备驱动程序13-14,静态重定位是在作业的_中进行的，动态重定位是在作业的—中进行的。A）编译过程 B）装入过程 C）修改过程D）执行过程15、如果允许不同用户的文件可以具有相同的文件名，通常采用—来保证按名存取的安全.A）重名翻译机构B）建立索引表C）建立指针D）多级目录结构 是直接存取的存储设备。D）键盘、显示终端B）优先级变为最大D）变为就绪状态D）键盘、显示终端B）优先级变为最大D）变为就绪状态一个进程被唤醒，意味着该进程_.A）重新占有CPUC）移至等待队列之首18、通道是一种.A）I/O端口B）数据通道 C）I/O专用处理机 D）软件工具19、SPOOLing技术利用于 .A）外设概念B）虚拟设备概念C）磁带概念D）存储概念20.从用户的观点看，操作系统是一A）用户与计算机之间的接口B）控制和管理计算机资源的软件C）合理地组织计算机工作流程的软件D）由若干层次的程序按•定的结构组成的有机体二、填空题（银空1分，共5分）I、操作系统提供给编程人员的唯•接口是⑴ 。2、将主存空闲区按地址顺序从小到登记在空闲区表中，每次分配时总是顺序杳找空闲区表.直到找到一个能满足其大小要求的空闲区为止，此种算法称为 （2）算法.3、在页式虚拟存储系统中，选择页面调度算法时技尽量注意减少或避免工”现象的发4」.4、页是信息的（4）单位,进行分页是出于系统管理的需要；段是信息的工单位，分段是出F用户的需要三、填空题（共15分，每题1分）824计算机专业基瞅A第5网共7页I、请你写出请求页式管理中缺页中断处理时的2种不同的洵汰算法的名称：3、⑵.2.系统为一个有6页的进程分配4个物理块，其页表如下所示(时间单位：滴答)，页的大小为1K,请计算逻辑地址为0X17C8的物理地址.按CLOCK算法为⑶:按FIFO算法为(4)；页号块号装入时间上次引用时间R(读)M(修改)07126279001423026010221202721139160280113、若F个等待访问磁盘者依次要访问的磁道为20,44,40,4,80,12,76,移动臂当前位于40号柱面，则先来先服务算法的平均天道氏度为一@；最短手道时间优先算法的平均寻道长度为(6):4,在采用分页存贮管理系统中，地址结构长度为18位，其中11至17位表示页号，。至10位表示页内位移量。主存容最最大可为K,每块有⑻K。5、有一个恐龙博物馆和个公园.有m个旅客和n辆车,每辆车只能容纳一个旅客。旅客在博物馆逛了一会儿，然后排队乘坐旅行车。当一辆车可用时，它载入一个旅客，然后绕公园行驶任意氏的时间。如果n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用信号量同步m个旅客和n辆车的进程.(1)完善如下程序，在下列(9)-(12)四处填入有关语句(2)说明每个信号量的物理意义。muicx^l;pci()muicx^l;pci(){repeatp(visitors):(⑵start;run;stop;v(visitors);v(muiex);untilfalse;⑼；p(mutex);gelon;travell;getoff;-00)—;(ID;untilfalse;)visitors的含义（13） ;cars的含义（14）n;mutex的含义（15）四、简答题（每题5分，共10分）1、可以通过哪些途径来提高内存的利用率？2、为什么位示图法适用于分页式存储管理和对磁盘存储空间的管理？如果在存储管理中采用可变分区存储管理方案，也能采用位示图法来管理空闲区吗？为什么？离散数学（共50分）（4分）已知集合/={{<»}.⑴},B={{a}},试求（1）2'；（2）8x2"（6分）把下列语句翻译为谓词演算公式（1）鱼我所欲，能掌亦我所欲：（2）并非所有人均喜欢电脑游戏：（6分）已知E是集合/上的自反和对称关系,试证明，（幻为/上的等价关系。（6分）7=（匕马是一棵树。试证明（1）7为二部图；（2）若{匕，匕}是二部图丁的顶点:分类，H|K|=n,|E\=m,试证明mV2.4（6分）设G=（匕E）是一个简单无向图，卜|=",〃23.若对于任何两个不相邻的顶点w,veV,d（u）+d（v）>n,试证明G是连通图。（4分）证明：在一个有限群中，阶大于2的元素个数一定是偶数。（6分）已知0，=。-{0}.0是有理数集，Vm.neQ'.n^m=-mn,证明（。=4）为群.6（6分）已知知识的符号表示（1）女（尸（x）aVy（D（y）->Z（x,y）））W（P（x）fVy（0（y）->-£（x,y）））结论：Vx（D（x）->r°（X））试用HORN子句逻辑程序证明之.（6分）已知G=（匕E）是一个简单平面图，K|£|<30.成证明至少有一个顶点的度数小于或等于4.第21页2010年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题南京理工大学2010年硕士学位入学考试试题试题编号：2010006020考试科目：计算机专业基础(满分150分)(AJ考生注意：.所有答案(包括填空题)按试题序号写在答题纸上，写在试卷上不给分.本试卷共有三部分组成，其中第一部分为“数据结构”，第二部分为"操作系统，第三部分为“离散数学”.每部分各50分.第一部分数据结构(共50分)一、填空(每个空格1.5分，共15分).I.已知一个带头结点的单链表L,其存储结构为：typedefstructLNode{ElemTypedata;structLNode*next;)LNode,*LinkList;下面的算法是在L中删除其最大值结点(表中有唯一的最大值)的算法，请在空格处填入正确的语句。voidDeleteMaxNode(LinkList&L){pre-L,p-pre->next,maxp=p,maxpre=pre;while((1)){if((2)){maxp=p;maxpre=pre;Jpre=p；(3);}//while:free(maxp);}//DeleteMaxNode.设哈希表长为14,哈希函数是H(key)=key%ll,表中已有数据的关健字为16,28,40,52共四个，现要将关键字为61的结点加到表中，用二次探测再散列法解决冲突，则放入的位中是(5):用线性探测再散列法解决冲突,则放入的位置是 ⑹ ..在一棵二叉树中，度为I的结点有40个，总的结点数为99,则二叉树中叶子结点数共有(7)..有序表为{2,5,9,12,16,20,26,28,32,36,40,43,45),在该表中用二分法查找值为37的数据，比较(8)次,可以确定查找失败.共7页第1版.对序列［50,37,66,98,75,12,26,49}进行树型选择排序，选出12的二叉树为⑼ ，接着再选出26的二叉树为（10） .二、简答题（23分）.已知有向图G有6个顶点（顶点号从1计），弧集E如下：（其中弧后面冒号后数表示弧上的权）E={<1,2>:12,<1,4>:15,<1,5>:8,<2,3>:13,<4,3>:25,<4,6>:5,<5,4>:5,<5,6>:20,<6,3>:2}请回答下面的问题：（3分）画出该有向图.（2）（3分）画出该图邻接表存储结构。（3分）按Dijkstra算法，给出从顶点1到其余顶点的最短路径及路径长度。（3分）将图看成无向图（将图中方向去掉），画出该无向图的最小生成树。2.已知关键字的集合{46,55,13,42,94,5,17,70）（1）（3分）请按给出的序列构造一棵二叉排序树（不要构造过程），并给出该二叉树排序树的深度；（3分）请对（1）中的二叉树进行先、中、后序遍历，分别给出遍历结果；（3分）请给出该关健字集合的大顶堆；（2分）如果对该关键字集合进行起泡排序，请给出第一趟排序后关键字的序列.三、算法（共12分）二叉树的存储结构如下：typedefstructBitnode{TelemTypedata;structBitnode*Ichild,*rchild;}Bitnode,*Bitree;请编写按层次顺序（同一层自左至右）遍历二叉树的算法（6分）voidLayerOrder（Bitree,T）。所用队列操作如下：InitQueue（Q）〃队列初始化EnQueue（Q,T）//T入队列，将T插入到队尾QueueEmpty（Q）//队列判空操作DeQueue（Q,p）〃出队列，将队头元素赋值给p如果队列用循环队列实现，其存储结构为：#defineMAXQSIZE100typedefstruct{

QelemType*base;intfront;intrear;JSqQueue;请实现函数EnQueue(Q,T)(3分)和DeQueue(Q,p)(3、)第二部分操作系统（共50分）一、 单项选择题（每小题1分，共20分）.关于多道程序设计的论述中不正确的是（ ）A）.能提高资源使用效率B）能增加单位时间的算题量0对每个计算问题的计算时间可能要延长D）对每个计算问题的计算时间不会延长.当一个进程独占处理器顺序执行时，具有两个特性（ ）A）封闭性和可再现性 B）实时性和可靠性0交互性和可再现性 D）封闭性和实时性.某系统中，每个进程在I/O阻塞之前的运行时间为T,一次进程切换的系统开销时间为S,若采用时间片长度为Q的时间片轮转法，并且SVQVT,则CPU的利用率是（）D)Q/CT+S)A）T/（T+S） B）Q/（Q+S） C）50%D)Q/CT+S).把并发进程中与共享变量有关的程序段称为（ ）A）共享数据区 B）临界区D）共享程序C）D）共享程序.有关并发进程的阐述中，不事确的说法是（ ）A）进程的执行速度不能由‘进'程'自己来控制B）进程的执行速度与进程能占用处理器的时间有关O进程的执行速度与是否出现中断事件有关D）任何两个并发进程之间均存在着相互制约关系.有n个进程竞争某共享资源，系统允许每次最多m个进程同时使用该资源,若用PV操作管理时信号量的变化范围为（ ）B）[n>（m+n）]B）[n>（m+n）]D）[（m-n）,n]B）只能在管态下D）从目态变为管态时C）[（m-n）,m].特权指令（ ）执行.A）只能在目态下0可在管态也可在目态下.造成某进程状态从运行态到等待态的变化原因不可能是（ ）A）该进程运行中请求启动了外围设备B）该进程在运行中申请资源得不到满足共7金第3贝0分配给该进程的处理器时间用完D）该进程在运行中出现了程序错误故障.在五个哲学家就餐问题中，为保证其不发生死锁，可限定同时要求就餐的人数最多不举可：（ ）A）2个 B）3个 C）4个 D）5个.已知作业的周转时间=作业完成时间一作业的到达时间.现有三个同时到达的作业JI,J2和J3,它们的执行时间分别是Tl,T2和T3,且TKT2VT3.系统按单道方式运行且采用短作业优先算法，则平均周转时间是（）。A）T1+T2+T3 B）（T1+T2+T3）/3C）Tl+2*T2/3+T3/3 D）Tl/3+2*T2/3+T3.作业8：00到达系统，估计运行时间为1小时，若10：00开始执行该作业，其响应比是（）A）2 B）1 03 D）0.5TOC\o"1-5"\h\z.让多个用户作业轮流进入内存执行的技术称为（ ）A）覆盖技术B）对换技术C）移动技术 D）虚存技术.可以采用静态重定位方式转换地址的管理内存方案是（ ）A）页式管理 B）页式虚拟管理0可变分区管理 D）固定分区管理.在以下存贮管理方案中，不适用于多道程序设计系统的是（ ）A）单用户连续分配 B）固定式分区分配O可变式分区分配 D）页式存贮管理.现有如下请求队列：8,18,27,129,110,186,78,147,41,10,64,12：用最短寻道时间优先算法处理所有请求，移动的总柱面数（ ）..假设磁头当前位置在100.A）263 B）264 C）265 D）266.在页式虚存管理中，（ ）有一个页表.A）整个主存空间 B）整个虚存空间0每个作业 D）每个用户文件.在页式存储管理中，假定访问主存的时间为200亳微秒，访问高速缓冲存储器的时间为40亳微秒,高速缓冲存储器为16个单元，查快表的命中率为90%,则按逻辑地址转换成绝对地址进行存取的平均时间为（ ）A） 256亳微秒 B） 400毫微秒C） 260亳微秒 D） 240毫微秒.信箱通信是一种（ ）通信方式.A）高级通信 B）低级通信0信号量 0）直接通信.在操作系统提供的文件系统中，用户把信息组织成文件并对其操作时，关于文件存储位置和如何组织输入/输出等工作，正确的说法是（ ）

A)B)A)B)C)D)用户不需要考虑文件存储的物理位置，也不需要组织输入输出工作用户需要考虑文件存储的物理位置，但不需要组织输入输出工作用户不需要考虑文件存储的物理位置，但需要组织输入输出工作B）盘的躯动调度D）页式虚拟存贮管理中的页面调度.位示图方法可用于（A）B）盘的躯动调度D）页式虚拟存贮管理中的页面调度二、填空题（每空1分，共5分）1.2.1.2.为了便于对文件进行控制和管理，在文件系统内部，需要为每个文件建立一个处在采用线程技术的操作系统中，线程是他和执行单位，而进程是④单位.要确定一个盘块所在的位置必须给出三个参数：15）_,柱面号和扇区号。三、解答题（共15分）1.（4分）有一个多道批处理系统，作业调度采用“短作业优先“调度算法，进程调度采用“优先数抢占式“调度算法，且优先数越小而优先级越高。现系统拥有一台打印机，采用静态方法分配，忽略系统的调度开销，现有如下作业序列到达系统：回答：（1）写出作业完成的先后次序。（2）求出作业的平均周转时间和平均带权周转时间.作业编号到达系统时间要求执行时间需打印机数进程优先级J114：0040分钟1台4J214：2030分钟0台2J314：3050分钟1台3J414：5020分钟0台5J515：0010分钟1台12.（2分）在一个分页存储管理系统中，逻辑地址长度为16位，页面大小为4096个字节.且第0、1,2页依次存在物理块10、12、14号中，则逻辑地址为2F6AH所对应的物理块号是,其物理地址是.3.（2分）假定在某动臂磁盘上，刚处理了访问75号柱面的请求，目前正在74号柱面上读信息,且有如下请求序列在等待访问磁盘：请求序列12345678欲访问柱面号22481931889278156101试回答：（1）写出电梯调度算法处理时的序列次序：（2）写出最短寻找时间优先算法时处理的序列次序；4.（2分）在一请求分页系统中，一作业共有7个页面，其中页面0,1,2,3分别装入到物理页块中.若作业的页面走向为0123213252362142,采用FIFO页面置换算法，产生缺页中断次,采用LRU页面置换算法，产生缺页中断次。5.(5分)现有n个进程，它们的标号依次为1、2、…、n.现允许它们同时读文件FL但必须满足条件：同时该文件的进程的标号之和小于采用PV操作协调多进程读文件的程序如下，完成填空。semaphproewaits,mutex;intnumbersum=0;wait=0;TOC\o"1-5"\h\zmutex= (]) ;cobeginprocessreaderi(intnumber){//i=l,2,…P(mutcx); ,while(numbersum+number>=ni)f⑵：P(waits);}numbersum=nunibersum^number; .⑶：ReadFl⑷：numbersum=numbersum-numbcr;©_；V(mutex);四、简答题(每题5分，共10分).对资源采用静态分配策略为什么能防止死锁？.文件目录一般包括哪些信息？设置文件目录的功能是什么？第三部分离散数学(共50分).试把下列语句翻译为谓词演算公式(每小题3分，共6分)(1)我为人人，人人为我；(2)鱼我所欲，熊掌亦我所欲..已知知识的符号表示(5分)⑴3x(P(x)aV>(产(y)fZ(xj)))Vx(P(x)f4"(y)->rL(x,y)))结论：Vx(尸(x)-Y(x))试用Hom子句逻辑程序证明之。4,8,C是三个任意的集合，若4£(8uC),则(H-B)c(4-C)=<D.(5分)已知为四个集合，|川且Hc3=CcO=(D,试证明MuB|=|CuD|.(5分)G=(匕£)是一个简单连通平面图，试证明G中一定存在一个顶点，其度数小于等于5.(4分)H是集合力上的二元关系，对于任意的a,b,ce/，如果(a,6)eR,(b,c)wA,则(CM)e/?,称R为循环关系。试证明K是自反的和循环的关系当且仅当/?是等价关系.(5分)1-已知9个人匕,匕，…“，其中匕与2个人握过手，》＞2，与，！，匕各与3个人握过手，v6与4个人握过手，叫,匕各与5个人握过手，vg与6个人握过手.试用图论的语言证明这9个人中一定可以找出3个人互相握过手.(5分)7=(匕E)为一棵树.若匕，匕是？作为二部图的顶点分类，国国匕I，则匕中至少有一片树叶。(5分)(4*)，(8,*)是两个群.令C=4x8,且对于任意的(db),(c,W)wC,有(a,b)*(c,d)=(a*c,b*d)。证明(C,*)也是一个群。(5分)设(4*)是群(民*)的子群，定义C={x|xe8,x*〃xT=/}。试证明(C,*)是(民*)的子群.(5分)第30页2009年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题南京理工大学2009年硕士学位入学考试试题试题编号:

考试科目:试题编号:

考试科目:计算机专业基础(满分150分)考生注意:.所有答案(包括填空题)按试题序号写在答题纸上，写在试卷上不给分.本试卷共有三部分组成，其中第一部分为“数据结构”，第二部分为“操作系统”,第三部分为“离散数学”。每部分各50分.第一部分数据结构(共50分)一、填空(每个空格L5分，共15分).与顺序表相比链表不具有的特点是 (1)。.待排序的序列为(55,31,11,37,46,73,63,2,7},快速排序进行一趟划分后的序列⑵.设单循环链表中结点的结构为(data,next),且rear是指向非空的带头结点的单循环链表尾结点的指针。若要删除链表的第一个结点(删除结点后，链表仍然不空)，则应执行 ⑶ 。.无向图6=(V,E),其中：V={a,b,c,d,e,丹，E={(a,b),(a,e),(a,c),(b,c),(c,f),(f,d),(c,d)}, 图的存储结构为邻接矩阵。从a出发对该图进行深度优先遍历，得到的顶点序列是⑷ ；从a出发对该图进行广度优先遍历，得到的顶点序列是⑸ 。.二叉树的先序和中序遍历序列分别是ABCDEFGH,CBEDFAGH,则后序遍历序列是(6) ..折半插入排序算法如下所示，请在空格处填入正确的语句。voidBsort(Sqlist&L){fbr(i=2;i<=L.length;-H-i){L.r[0]=L.r[i];low=l;high=ST.length;while(⑺){m=(low+high)/2;TOC\o"1-5"\h\zif(LT(L.r[0].key,L.r[m].key)) ⑻：else(9) :}//whilefor(j=i-ly>=high+1;-j) (10) ;L.r[high+l]=L,r[O];

}//for}//Bsort二、简答（每小题5分，共15分）.已知关键字的集合{56,8,15,80,10,22},试构造3阶打树。.编写递归算法，计算二叉树中叶子结点的个数；.画出下图的最小生成树三、（每小题4分，共12分）输入关键字序列{10,6,7,4,8,9,12}.构造一棵二叉排序树T；.在T的中序线索树中，结点7的前驱和后继结点分别是什么结点；datanext四、算法（共8分）设有两个集合计算(A-B)U(B-A)四、算法（共8分）设有两个集合计算(A-B)U(B-A),A和B,分别用有头节点的单链表（结点结构）la和1b表示。用类C语言设计算法：结果放在la中。第二部分操作系统（共50分）一、单项选择题（每小题1分，共20分）.使用户所编制的程序与实际使用的物理设备无关，这是由设备管理的功能实现的。A）设备独立性 B）设备分配C）缓冲管理D）虚拟设备.在页式虚存管理中，有一个页表。A）整个主存空间B）整个虚存空间 C）每个作业 D）每个用户文件.对一般用户是透明的，但是对程序员是不透明的。A）虚拟存储器 B）页表C）人工覆盖 D）静态重定位.重定位的地址转换工作是指。A）绝对地址转换成物理地址B）物理地址转换成绝对地址0绝对地址转换成逻辑地址D）逻辑地址转换成绝对地址.对若干进程共享某一变量的相关临界区的管理描述错误的是。A）一次最多让规定数目的进程在临界区执行B）任何一个进入临界区执行的进程必须在有限的时间内退出临界区0不能强迫一个进程无限地等待进入它的临界区D）有进程退出临界区时一定要选择一个进程进入临界区.对死锁的解除有关描述正确的是.A）可采用重新启动操作系统来解除死锁B）可采用强迫进程结束来解除死锁0可采用静态分配资源来解除死锁D）可采用银行家算法来解除死锁.进程并发执行时，每个进程的执行速度是。A）由进程的程序结构决定的 B）由进程自己控制的0在进程被创建时确定的 D）与进程调度的策珞有关.当多道程序系统中发生死锁时，。A）计算机系统不能处理任何事情B）某个进程不能执行0一组进程相互等待，并进入阻塞状态D）不能进行输入和输出.三个进程A、B,C对某类资源的需求量分别是7个、8个和3个，且目前别得到了3个、3个和2个。为保证系统的安全，该系统目前剩余的资3少是oA）1个B）2个C）5个 D）10个.为避免用户程序中直接使用特权指令，用户进程运行在oA）系统态B）核心态C）目态 D）管态.一个进程独占处理器顺序执行时具有封闭性和可再现性，其含义是A）进程执行的结果只取决于进程本身B）进程执行的速度对执行结果有影响O进程多次执行时其执行结果可能不同D）进程执行时不会发生中断事件.在批处理系统中，作业控制说明书是用编写而成。A）C语言B）命令语言 0作业控制语言 D）会话语.当进程处于阻塞状态时，进程。A）没有占用处理机 B）将进入结束状态0将进入执行状态 D）等待处理机.在下列各项步骤中，不是创建进程所必须的步骤。A）建立一个PCB B）进程调度程序为进程分配CPU0为进程分配内存等资源 D）将PCB插入进程就绪队列.静态分配资源（所有进程在开始运行之前，都必须一次性地申请其在整，行过程所需的全部资源）死锁防止策略。A）破坏了“循环等待”和“占有并等待”两个条件B）破坏了“互斥”和“占有并等待“两个条件C）破坏了“互斥”条件D）破坏了“不可抢夺”条件.平均周转时间最小的作业调度算法是oA）先来先服务算法 B）短作业优先算法0响应比最高者优先算法 D）优先数调度算法.段逻辑地址形式是：段号13位，段内地址23位，内存1M,辅存100G,那么虚拟存储器最大实际容量可能是oA）8G-1M B）8G C）64G+1M D）64G.假设有编号为1、2、3、4四个空闲区，大小分别为16K、24K、15K、30K,现要申请15K的主存空间，采用最坏适应算法，则申请到的空闲区编号为=A）1 B）2 C）3 D）4.设备的打开、关闭、读、写等操作是由完成的。A）用户程序B）编译程序C）设备分配程序 D）设备驱动程序.寻道时间是指。A）由磁头把扇区中的信息读到主存储器所需时间B）磁头在移动臂带动下移动到指定磁道所需的时间0指定扇区旋转到磁头下所需的时间D）把主存储器中信息写到扇区中所需的时间二、填空题（每空1分，共5分）.系统中有4个进程都要使用某类资源，而系统能提供的该类资源数为9个。那么，当每个进程需申请的资源超过口_个时，该系统就可能发生死锁。.在UNIX中，文件系统的文件存储结构采用的是（2）。.我们把并发进程中与共享变量有关的程序段称为“⑶I.在采用线程技术的操作系统中，线程是（4）和执行单位,而进程是（5）单位。三、解答题（共15分）1.（本小题2分）设正在处理器上执行的一个进程的页表如下，表中的页号，物理块号是十进制数，起始页号（块号）均为0,所有的地址均是存储器字节地址，页面大小为1024字节，则逻辑地址2148对应的物理地址为,逻辑地址4000对应的物理地址为。页号物理块号02132136.（本小题2分）在一个请求页式存储管理系统中，某作业所涉及的页面依次为0,1,4,2,0,2,6,5,1,2,3,2,1,2,6,2,1,3,6,2,并已知分给该作业的主存物理块是3,则按照FIFO置换算法将产生 次缺页中断。按照最佳页面置换算法将产生 次缺页中断。（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）.（本小题2分）假设一个磁盘驱动器有500个柱面，编号从0到499。磁盘驱动器正在为第255柱面的一个请求提供服务，且磁头目前向0号柱面移动，按FIFO顺序排列的磁盘请求的柱面号依次为233,474,392,175,55,176,252,65,487,0和22。当用FCFS（先来先服务）,SSTF（最短寻道时间优先）来安排磁头移动时，移动的总量分别是，。.（本小题3分）设一个文件由100个物理块组成，若要将一块信息加在文件的50块之后，对顺序、链接和索引（一级）三种存储结构各需启动I/O操作,,次。（其中该添加块，目录项（及索引块，如果采用索引分配的话）都已经在内存中）.（本小题6分）在一个箱子里混装有数量相等的黑色围棋子和白色围棋子，现要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程组成，功能如下：（1）进程A专门拣黑子，进程B专门拣白子；（2）每个进程每次只拣一个子，当一个进程在拣子时不允许另一个进程去拣子；（3）当一个进程拣了一个棋子（黑子或白子）以后，必让另一个进程拣一个棋子（黑子或白子），并要求A进程首先开始。要求（1）（4分）完善如下程序，在下列A,B,C,D四处填入有关语句（2）（2分）说明信号量的物理意义。sl,s2:semaphore;siA; s2:=B;processA processBbegin beginLl:P（sl）; L2:P（s2）;拣黑子； 拣白子；C ； D；gotoLI; gotoL2;end; end;四、简答题（每小题5分，共10分）L什么叫文件目录？文件目录应含哪些基本内容？2.为实现分页式虚拟存储，页表中至少包含哪些内容？第三部分离散数学（共50分）（每小题3分，共6分）把下列语句翻译为谓词演算公式（1）所有的学生均喜欢老师；（2）任何一个集合X,总存在一个集合y,y的势比x的势要大。（6分）已知公理：小（PTT（0T「P）B：PT（QfP）0：（PT（0f （（PT0）f（p-R））D：（Pv0）-＞（0vP）E：Pf（0vF）以及分离规则和代入规则试证明；（尸f「rP）V（&人为定理。（4分）证明小于30条边的简单平面图至少有一个顶点的度数小于或等于4。（6分）已知（4。）是一个群，（8,*）是一个代数系统，/是4到8的一个满射,且对于Va,6w/I,有f（aob）=f（a）*f（b）。证明（8,*）是一个群。（5分）证明具有7个顶点15条边的连通平面图，它的每一个面都是有3条边围成。（6分）设48,C是三个集合，试证明（4- C）=/当且仅当ZcBcC=①。（5分）简单图G=（匕E）且|P|=v"E|=e,若有e2+2,则G是哈密尔顿图。（6分）（G,*）是一个群，aeG,/是G到G的一个映射：VxeG,/（x）=a*x*a7。试证明/是G到G的双射。（6分）G=（匕约是一个简单无向图。设G中任何两点间仅有唯一的一条简单通路，试证明：（1）G是一棵树；（2）G是一个二部图。第38页2008年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题南京理工大学2008年硕士学位研究生入学考试试题试题编号：2008006018考试科目：计算机专业基础（满分150分）考生注童:（1）所有答案（包括填空图按试题序号写在答题纸上,写在试卷上不给分.（2）本试卷共有三部分组成,其中第一部分为“计算机组成原理”，第二部分为“数据结构”,该两部分共100分，所有考生必做.第三部分有“离散数学”和“操作系境”各50分,考生可选做其中之一.若两者均做，将按“离散数学”阅卷.请在解答第三部分试题时,注明所选考试科目名称.一、 计算机组成原理部分（共50分）（-）简答题（本题12分）1,中断是计算机的处理一些意外事件和特殊请求的重要机制，一旦有中断请求，CPU则响应，并进入中断周期。请问中断周期（又称中断隐指令）的主要任务是什么？ （本小题4分）2,某双面磁盘，每面有220道，已知磁盘转速r=3000转/分，数据传输率为17500B/S,请问磁盘的总容,是多少？ （本小JH4分）3、在CPU与DMA控制器共享总线的结构中，DMA都采用哪些传送方式实现外设和主存之间的数据传送？ （本小题4分）（二）单项选择题：（本题共9分，在每小愿的四个备选答案中，选出一个正确的答案.）1,设某浮点格式为16位,最高1位为数符、最低8位是尾数值，尾数采用补码形式，阶码用移码表示（1位阶符、6位阶值）.若十进制数为-143,则其规格化的浮点数是。（H表示十六进制）①C871H ②8871H ③E572H ④8143H2、主存储器和CPU之间增加cache的目的是.①扩大主存储器的容量②扩大CPU中通用寄存器的数量解决CPU和主存之间的速度匹配问题既扩大主存储容量又扩大CPU通用寄存器数量3、当采用 对设备进行编址情况下，需要专门的I/O指令组.①统一编址法②单独编址法③两者都是④两者都不是4、指令系统中采用不同寻址方式的目的主要是.①缩短指令长度，扩大寻址空间，提高编程灵活性②实现存储程序和程序控制③可以直接访问外存④提供扩展操作码的可能并降低指令译码难度5,奔腾CPU内的浮点处理单元采用的浮点格式符合标准.①ASCII②GB2312 ③IBM360④IEEE7546,为了更好地实现计算机的多级子程序嵌套调用，需要支持.①累加器②堆栈③光盘 ④磁盘7、运算型指令的寻址与转移性指令的寻址不同点在于.①前者是短指令，后者是长指令②前者是长指令，后者是短指令③后者取操作数，前者决定程序转移地址④前者取操作数，后者决定程序转移地址8、在单级中断系统中，CPU一旦响应中断，则立即关闭标志，以防止本次中断服务结束前同级的其他中断源产生另一次中断进行干扰.①中断允许 ②中断请求 ③独立请求 ④中断屏蔽9、流水处理器中本条指令的结果是后继指令的操作数源，则存在.①资源相关 ②控制相关③数据相关 ④中断相关（三）图1.1为一个可以实现扑码加法、减法和补码一位乘法的筒单逆辑框图.（C寄存器具有右移功能，门电路可自选，但需标明功能：本题1。分）图1.11、请指出A、B、C寄存器分别在加、减、乘运算中的用途.（本问4分）2、若加、减、乘的控制信号分别为ADD、SUB、MUL,请写出Pl、P2的逻辑表达式，并设计其形成电路. （本问6分）（四）设某机指令长为16位，每个地址码长为4位，试用扩展操作码方法设计指令格式.其中三地址指令有10条，二地址指令为90条，单地址指令84条，还有若干零地址指令.现给定带有使能端（低电位有效）的446译码⑶（译码器输出低电位有效），其它爱辑门电路自选，但需说明所选电扇功能，

1、零地址指令最多有多少条？ （本问5分）2,若指令已在指令寄存器IR中，怎样设计指令译码ID部件？（本问4分）（五）假设某计算机的运算器框图如图1.2所示，其中ALU为16位的并行加法器（高电平工作），低位进位位Co取值为。或1,Sa、Sb为16位暂存器，接收数据分别受Pa、Pb控制，且Reset信号用于给Sb复位（清零），Ldalu、LdE信号分别控制SB的原值输出和反值输出，4个16位的通用寄存器CRo-Rj）由D触发器组成，并由原端（Q端）输出.（本题10分）16位数据总线R♦W♦4个16位二款：｝读选择通用寄存器 WAoT.写选择 WA1J图1.2通用寄存器（R/Rj）的读写控制如表1.1所示:表1.1寄存器读写控制表读控制写控制RRA0RA)选择WWA0WAi选择100读即100写&101读Ri101写R]110读R2110写Rz111读1111写R30XXX0XXX（注；X表示不工作）1、请简述控制器的微程序设计基本思想。 （本问3分）2,请用水平型微程序方法设计微指令控制字段的格式 （本问4分）（替不考虑后继地址）.3,请给出实现减法（Ri）-（R2）》R3运算的控制信号序列. （本问3分）二、 数据结构部分（共50分）（-）填空（本题15分，每个空格1.5分）1,对序列{50,37,66,98,75,12,26,49}进行树型选择排序，画出选出12,和26的两棵二叉树 （1） 。2,已知一棵完全二叉树共有892个结点，则该二叉树的高度是经,叶子数是（3）,度为1的结点数是（4）,最后一个非叶结点的序号是⑸.（注：二叉树结点按自然数顺序从1开始从上到下，同一层从左至！J右编号）3、下面的算法是求有向图中所有顶点入度的算法，请在空格处填入适当的语句。voidFindindegree（ALGraphG,intindegree[vexnum]）{for（i=0;i<vexnum;i++）indegree[i]=0;…for（i=0;i<vexnum;i++）-for（p=G.vertices[i]. 7c）~wr（（7） ;indegree[k+l]++;}//forp}//fori}//Findindegree4、设哈希表长为14,哈希函数是H（key）=key%13,表中已有数据的关键字为16,30,44,58共四个，现要将关键字为82的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（8）；用线性探测再散列法解决冲突，则放入的位置是 （9）.5,在B—树中删除关键字Ki,若Ki为非终端结点中的关键字，则以（1。）代替记（二）简答（本题15分）1,用类C的类型说明定义树的二叉链表（孩子-兄弟）存储结构。（本小题2分）2,给出图2.1树的先序遍历和后序遍历序列。（本小题2分）3、将图2.1的树转换成二叉树，并画出该二叉树的二叉链表存储表示.（本小题4分）

AOE网可以表示某个工程，在网中顶点表示事件，有向弧表示活动.给出求AOE网中某个事件j的最早发生时间Ve（j）和最迟发生时间VI。）的式子：如果活动ai由弧勺k>表示，持续时间记为dutq,k>,则：活动的最早（本小题4分）（本小题3分）开始时间e（i）（本小题4分）（本小题3分）（=）设关键字序列为{4,6,7,8,9,10,12},试解答：（本题12分）1,请对该关键字序列构造一棵平衡二叉树，画出树的生成过程和所进行的平衡操作.（本问2分）平衡操作.2、计算该平衡二叉树所有叶结点的带权路径长度之和，并给出树的深度.（本问4分）3、画出删除该平衡二叉树关键字为8的结点后的平衡二叉树。（本问2分）（本问2分）（本问2（本问2分）（本问2分）5,将序列建成大顶堆。（四）现给出数据类型描述如下所示.请用类C语言设计一个算法，将“中，所有结点的原有次序保持在各个结点的next域中，利用pre域把所有结点按照其值从小到大的顺序连接起来。（本题8分）类型定义为：#defineM1000//链表最大长度typedefstruct{Elemlypedata;int pre;int next;}component,SLinkList[M];假设si为SLinkList类型的双向链表，sl[0].next指向表的第一个结点。三、操作系统部分（共50分.若选择此部分，请在答题纸上标明）（-）单项选择题（每小题1分，本题共2Q分）I、从下述对操作系统的叙述中选出正确的叙述是A）操作系统的程序都是在核心态下运行.B）分时系统中常用的原则是使时间片越小越好.C）批处理系统的主要缺点是缺少交互性.D）Windows是一个多用户多任务的操作系统。2、在采用线程技术的操作系统中，不正确的说法是A）线程是资源分配的独立单位.B）线程是调度执行的单位。C）同一进程中各线程共享该进程分配到的主存空间。D）线程运行的系统开错更小.3、若当前进程因时间片用完而让出处理机时，该进程的状态变为A）就绪B）等待 C）运行D）完成4,在一个单处理系统中，若有4个用户进程，则处于就绪状态的用户进程最多有个，最少有个.A）4、1 B）3、IC）3、0 D）4、05、进程依靠从阻塞状态过渡到就绪状态.A）程序员的命令 B）系统服务C）等待下一个时间片到来 D）“合作”进程的唤醒6、临界区是指并发进程涉及共享变量的A）程序段B）缓冲区C）数据区D）信息区7、从下列有关进程管理的叙述中，选出正确的描述A）进程之间同步，主要源于进程之间的资源竞争，是指对多个相关进程在执行次序上的协调.B）临界资源是指每次仅允许一个进程访问的资源.C）信号量是一个整型变量，在其上只能进行P操作和V操作.D）V操作是对信号量执行加1操作，意味着释放一个单位资源，加1后如果信号量的值小于等于零，则从等待队列中唤醒一个进程，现进程变为等待状态，否则现进程继续进行.8、在操作系统中，对信号量S的P操作中，使进程进入相应阻塞队列等待的条件是 A）S>0 B）S=0 C）S<0 D）SW09,某系统有4个并发进程，都需要同类资源2个，当系统中这类资源最少数是个时系统不会发生死锁。A）4 B）5 C）6 D）710、某进程被唤醒后，立即被执行，该系统采用的调度方式是A）抢先调度 B）非抢先调度C）不能确定是否采用抢先调度 D）用户抢先调度1k为了使系统中各部分资源得到均衡使用，就必须选择对资源需求不同的作业进行合理搭配,这项工作是由完成的。A）作业调度B）中级调度C）进程调度 D）内存调度12、在下面的调度算法中，算法不是合理的作业调度。A）时间片轮转 B）先来先服务C）短进程优先 D）优先权13、假设系统中有三类互斥资源R】、氏和R3,可用资源数分别为9、8和5.在To时刻系统中有口、Pz、P,、P,和P,五个进程，这些进程对资源的最大需求量和已分配资源数如下表所示.如果进程按序列执行，那么系统状态是安全的.源进程最大需求，已分配资源数RiR?R3RiRjRjP.652121P?221211Pj801200P，121120巴344113A）P|-―►p4—kPs-B）p2-*P1-*?4-*Pj—*PjC）P2-*P4->Pj-»Pi―>Pj D）P4-—>Pj―»Pi-^Pj14、当采用资源有序分配方法预防死锁时，它破坏了产生死锁必要条件中的一A）互斥条件B）请求和保持条件C）不剥夺条件D）环路等待条件15、以下存储管理不可用于多道程序系统中.A）固定分区B）单一连续区C）动态分区 D）段式存储管理16、在可变分区管理算法中，把空闲区按其长度递减次序排序的做法最适合于一A）首次适应算法 B）最佳适应算法C）最坏适应算法 D）循环首次适应算法17,在分页存储管理中，地址转换工作是由完成的.A）硬件B）地址转换程序 C）用户程序 D）装入程序18、在一个请求页式存储管理系统中，某作业所涉及的页面依次为3,2,1,4,4,5,3,4,3.2,1,5,并已知分给该作业的主存物理块是3,则按照LRU调度算法将产生 次缺页中断.（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断.）A）7 B）8 C）9 D）1019、采用SPOOLing技术的目的是A）提高独占设备的利用率 B）提高主机效率C）减轻用户编程负担 D）提高程序的运行速度20、要考虑磁头当前移动方向的移符调度算法是A）最短寻找时间优先调度算法 B）先来先服务调度算法C）优先级调度算法 D）电梯调度算法（二）填空（每个空格1分，本题共5分）1,虚拟存储管理系统的基础是程序的（1）理论,根据这个理论，Denning提出了（2）理论.2、文件存储设备管理中,UNIX采用的空闱块管理方法是qi・3、为了使得操作系统具有特权，通常将计算机指令分为二类，即一般指令和（4）指令.4、通常情况下，连续文件结构在顺序存取时速度量快，皿结构在随机存取时速度最快.

（=）解答题（本题共15分）1、某计算机有32位虚地址空间，且页大小为1024字节.每个页表项长4个字节。因为每个页表都必须包含在一页中，所以使用多级页表，则需要几级页表？每一级都有多少页表项？ （本小题4分）2、在单道批处理系统中，有四个作业进入系统，进入时间及所需时间如下表所示：现忽略作业调度所花时间，当第一个作业进入系统后就可开始调度。（本小题4分）作业进入时间所需计重时间18t002小时28：3030分钟39：006分钟49：3012分钟（1）若用“先来先服务”调度算法，则作业3完成时间是多少？作业的平均周转时间是多少？ （本子题2分）（2）采用“非抢先的短作业优先”调度算法时，作业3完成时间又是多少？作业的平均周转时间是多少？（本子题2分）3,在某餐馆里有一个收银员，且同时最多允许有30个顾客就餐，我们可以将顾客和收银员看成是两类不同的进程，其工作流程如图3.1所示.为了利用PV操作正确地协调这两类进程之间的工作，设置了三个信号*S，、S?和Sn,且初值分别为0、0和30. （本小题7分）图3.]（D完善流程图，在A,B,C,D处填入有关语句. （本子题4分）（2）说明信号量Si、&和Sn的作用及它们初值的物理意义・（本子题3分）（四）叙述题（每小题5分，本题共10分）1、什么叫进程？为什么要引入进程？2、请问分页式和分段式内存管理有什么区别？它们都如何实现共享和保护？三、离散数学部分(每题5分，共50分.若选择此部分，请在答题纸上标明)1、某公司生产的8种不同的颜色的梦织成的双色布,已知在品种中,每种第色至少分别与其它7种颜色中的4种颤色搭配.试用图论的语言证明可以挑出4种双色布,它们恰有8种不同的旗色.2、试证明他单连通图G的任何一条边均可以是某一生成树的枝.3、证明一棵树若有3片树叶，2个2度顶点，则至少有一个顶点的度数大于等于3.4、设(G,♦)是一个群，定义R为G上的二元关系，R=((x,y)|存在0WG使得y=e*x*6-l},试证明R为G上的等价关系.(G,♦)是一个群，H.K均是G的正规子群，请证明HcK也是G的正规子群.6、在一个边长为4的正方形内任意加入65个顶点，至少有两个顶点的距离小于红.试用鸽巢原理证明之.7,A是无限集，B为可数无限集，试证明：|AkjB|=IA]8、试证明：(A-B)u(A-C)=0当且仅当AsBrC9、设R1和R2是集合A上的两个关系，而且R1CR2,试证明：t(Rl)£t(R2).10、A,B,C是三个任意的非空集合，f是A到B的函数，g是B到C的函数,若g是单射，且Pg是A到C的满射.请证明f是满射.第49页2007年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题南京理工大学2007年硕士学位研究生入学考试试题试题缰号：2007006019考试科目：计算机专业基础(满分150分)考生注意:(1)所有答案(包括填空题)按试画序号写在答息纸上,写在试卷上不给分.⑵本试卷共有三部分组成,其中第一部分为《数据结构，第二部分为《计算机组成原理，该两部分共100分,所有考生必做.第三部分有《离效数学》和《镰作系统)各50分,考生可选做其中之一.若两者均做，将按《高《数学》阅卷.请在解答第三部分试分时,注明所选考试科目名口.一、 数据结构部分(共50分)(一)填空(每个空格1.5分，共15分)1、无向图G=(V,E),其中：V={&b,cde,f),E={(a.b),(a.c),(a.c).(b.e).(c.D,(f,d),(e,d)}对该图进行深度优先遍历,得到的顶点序列正确的是(1)2.该算法为简单选择排序算法.voidsort(Linklist&H){while(q){while(p){if(⑴ )r=p;p»p->next;Jq->data•--»r->data; 14) ;}//while(q)J//sort3、满7叉树上的叶子结点数g和非叶结点数曲之间的关系是：(514、3阶B树如下，画出删除24后的B房 ⑹痣I页.共8页5、设单循环锌表中结点的结构为（data,next）,且rear是指向非空的带头结点的单循环链表的尾结点的指针.若要删除徒表的第一个结点，则应执行的操作为 ⑺6、输入殍列为!8,6,4,10,12,9.7L构造一棵哈夫曼树，该哈夫曼树的带权路径长度WPL为 ⑻7、写出表达式a*（b+c）Y的后缀表达式」8,有序表为（5,8,10,15,32,41,45,62,75,77,82,95,100},用二分查找值为82的数据时，需要比较（10）次.（二）筒答（16分，每小题4分）1、拓扑排序算法.2、Prim算法.3,说出二叉树的五种形式.4.二叉树中序遍历的递归算法.《三》（9分）输入关犍字序列{8,