东南大学《935计算机专业基础》历年考研真题汇编.pdf

目录第一部分东南大学935计算机专业基础历年考研真题1993年东南大学935计算机专业基础考研真题（数据结构部分）1994年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）1995年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）1996年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）1997年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）1998年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）1999年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）2000年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）2001年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）2002年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）2003年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）2004年东南大学935计算机专业基础考研真题2005年东南大学935计算机专业基础考研真题2006年东南大学935计算机专业基础考研真题（回忆版）2007年东南大学935计算机专业基础考研真题（回忆版）2008年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）2013年东南大学935计算机专业基础考研真题及部分参考答案2014年东南大学935计算机专业基础考研真题及参考答案2015年东南大学935计算机专业基础考研真题及详解2016年东南大学935计算机专业基础考研真题（回忆版）2017年东南大学935计算机专业基础考研真题（回忆版）第二部分全国计算机联考408考研真题及答案详解2009年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解2011年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解2013年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解2014年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解2015年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解2016年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及参考答案2017年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及参考答案2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及参考答案第一部分东南大学935计算机专业基础历年考研真题1993年东南大学935计算机专业基础考研真题（数据结构部分）1994年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）1995年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）1996年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）1997年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）1998年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）1999年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）2000年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）2001年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）2002年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）2003年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）2004年东南大学935计算机专业基础考研真题2005年东南大学935计算机专业基础考研真题2006年东南大学935计算机专业基础考研真题（回忆版）2007年东南大学935计算机专业基础考研真题（回忆版）2008年东南大学935计算机专业基础考研真题（数据结构、操作系统部分）2013年东南大学935计算机专业基础考研真题及部分参考答案一、选择题（120题，共40分）1在利用栈将中缀表达式A（BC/D）E转化成后缀表达式的过程中，当扫描到符号“）”时，栈中的内容是（）A（/B（C（/D（/D【答案】2现有一颗含有25个结点的4叉树T，若T中所有分支（即度不为0的）结点的度均为4，则T的叶子节点数是（）A15B17C19D21C【答案】3下列序列中，不可能是任意二叉搜索树后序遍历序列的个数是（）5，3，4，10，12，8 5，4，3，10，12，18 3，4，5，12，10，8 10，12，5，4，3，8A0B1C2D3C【答案】4带权无向图G如下图所示，若分别用Prim算法（从顶点0开始）和Kruskal算法求G的最小生成树，则最后选中的边的权值分别是（）A5，3B3，5C5，4D5，5B【答案】5已知序列25，13，10，12，9，5，6，8是大根堆，在插下新元素20的过程中，共进行比较操作的次数是（）A0B1C2D3D【答案】6若数据元素序列9，10，11，8，5，12，2，4，7是采用下列排序方法之一得到的第二遍排序后的结果，则该排序算法只可能是（）A冒泡排序B选择排序C插入排序D二路归并排序C【答案】7若依次将关键码20，30，50，52，60，68，70插入到初始为空的3阶B树中，则最后得到B树的根结点中所包含的关键码是（）A50B52D60D50，52B【答案】8下列关于机器字长的叙述中，错误的是（）A通用寄存器位数等于机器字长B系统总线宽度等于机器字长C主存单元长度不大于机器字长DALU位数等于机器字长B【答案】9为了使计算机的数据传送和数据处理的功能可以并行实现，下列方法中有效的是（）A多种总线互联B以存储器为中心C多重存储器共存D以运算器为中心B【答案】10 某计算机存储器按字节编址，主存容量配置为64KB，下列设计方案中，所用芯片的MOS管门电路等基本元件性能相当，则性能最优的方案是（）A4片16KB8位SRAM芯片B4片16KB8位DRAM芯片C4片32KB4位SRAM芯片D8片64KB1位DRAM芯片A【答案】11 下列寻址方式中，只能用于指令寻址的是（）A立即寻址B寄存器寻址C相对寻址D基址寻址C【答案】12 下列有关微指令的叙述中，错误的是（）A垂直型微指令全部是功能性指令B垂直型微指令指令长度比较短C水平型微指令可完成多个微操作D水平型微指令显示表示顺序控制信息A【答案】13 下列有关总线定时的叙述中，错误的是（）A异步全互锁定时方式的通信速度最慢B异步不互锁定时方式的通信可靠性最差C异步定时方式的握手信息可不通过联络信号产生D同步定时方式的时钟信号可由设备自行提供D【答案】14 下列有关I/O接口的描述中，错误的是（）A每个I/O接口中至少包含一个I/O端口B一个I/O接口可以连接多个I/O设备C程序控制方式的I/O接口中可以没有状态口D不同I/O接口的I/O端口之间允许独立编址C【答案】15 一个请求分页系统，测得如下利用率：CPU为5%，分页磁盘为97.5%，外设为4%，则下列措施中，可改善CPU利用率的是（）A更换速度更快的CPUB更换更大容量的分页磁盘C挂起内存中的某个用户进程D增加内存中的用户进程C【答案】16 以下关于页式内存管理系统页面大小的叙述中，正确的是A页越大，页表也越大B页越大，则I/O开销越大C页越大，则内部碎片越大D页越大，则产生缺页中断的可能性越大C【答案】17 某系统中有11台打印机，N个进程共享打印机资源，每个进程要求3台，为使系统不产生死锁，N的取值最多是（）A4B5C6D7B【答案】18 以下关于进程说法正确的是（）I进程从运行状态转换到就绪状态，系统一定会发生CPU调度当I/O完成时，一个进程的状态有可能从等待状态转换为运行状态进程从等待状态转换为就绪状态，系统一定会发生CPU调度进程进入终止状态，系统一定会发生CPU调度AI和B和C和DB【答案】19 页式内存管理系统中，物理内存地址为16位，逻辑地址为24位，页面大小为512B，采用两级页表结构，外层页表有256页，则以下正确的是I一个进程中最多有128个页一个进程中最多有32K个页逻辑地址中表示外层页表、页号和页内偏移量的位数分别为8、7、9逻辑地址中表示外层页表、页号和页内偏移量的位数分别为7、8、9AI和B和C和DC【答案】20 系统中四个进程（P1P4）和三类资源（3个R1，2个R2，2个R3），进程资源分配和请求状况如下表所示：则正确的是A由银行家算法知，找不到安全序列，存在死锁B由银行家算法知，系统处于安全状态，无死锁C由死锁检测算法知，系统中存在死锁D由死锁检测算法知，系统中不存在死锁B【答案】二、综合应用题（2132，共110分）21（8分）归并排序一般从用2路归并，即在两两归并过程中，从两个有序子序列中逐次挑选关键字最小的元素。如果采用K路（K2）归并，能提高排序效率吗？说明理由22（8分）连通无向图G（V，E）采用邻接表存储，其中|V|n，|E|e。现需要在G中找到这样一个顶点V，删除V及相关联的边对剩下的图的连通性无影响。试说明解决上述问题的算法思路（不需要写出具体程序），并估计时间复杂度23（8分）二叉树T采用二叉链表存储，T中结点结构为（Lchild，data，Rchild），其中Lchild和Rchild分别是指向左右孩子的指针，data为正整数，编写算法，按后序遍历次序输出T中每个结点data值及所处层次（假定根节点在第一层）24（12分）设S是n个互不相同的整数组成的序列，试编写一个尽可能高效的算法，判定S是否可能在某棵二叉搜索树查找过程中产生的关键字比较序列，若S可能是，则算法输出为1，否则为0。请说明算法的设计思想，并给出时间复杂度和空间复杂度。25（8分）某16位计算机的ALU仅实现定点加法/减法运算，如下图所示，其中CF为进位/借位标记。ZF为零标记，SF和OF为符号标记和溢出标记。OP0时实现加法运算，OP1时，减法运算。请回答下列问题：1）若ALU操作时，入端A和B的数据分别由寄存器R1和R2提供，出端Z的数据存放到寄存器R3中，且R1和R2内容分别为23及34，则ALU进行加法及减法后，R3的内容分别是多少？（用十六进制表示）2）简述用同一加法器实现加法和减法运算的方法，画出图中的加法/减法处理电路3）根据图中所给信号，写出溢出判断电路OF及CF的信号逻辑26（11分）某16位计算机存储器按字节编址，主存容量为16MB，Cache容量为32KB，采用4路组相联映射方式。Cache和主存间的块大小为32B，请回答下列问题：1）为了实现映射，主存地址应划分为哪几个字段？各字段长度分别为多少位？2）CPU访问主存单元053070H时，可能命中的Cache组号是多少？所命中的Cache行标记字段的值是多少？3）若int型一维数组A存放在主存单元000050H开始的连续的4KB空间中，CPU依次读出数组A中的所有元素，此时Cache的命中率是多少？4）相对于全写法写策略，简述回写法写策略的优点27（11分）某8位计算机存储器地址空间为8位，按字节编址。指令系统包含如下2种指令格式：其中，格式2为双字长指令格式，操作类型由FUNC指定（OP000），IMME/Address存放在第2字中：目标操作数仅支持寄存器寻址方式，即Rd为通用寄存器编号；源操作数支持4种寻址方式，分别为寄存器寻址（MS10）、寄存器间接寻址（MS11）、立即寻址（MS20）、直接寻址（MS21），且约定加法指令采用格式1时，OP001，采用格式2时，FUNC01.设计算机CPU部分如下，R0R3为通用寄存器（编号03）。ALU可实现加法（ALUOP0时）及减法（ALUOP1时）操作，其余控制信号为1时表示有效，为0时表示无效。微操作（uOP）控制信号的定时采用联合控制方式（访存操作的等待信号为WMFC），指令结束信号用End表示。请回答：1）该计算机指令系统最多有多少条指令？2）分别写出R1中数据与R2内容所指主存单元中数据相加指令字，以及R2中数据与43H号主存单元中数据相加指令字，目标操作数均为寄存器寻址方式（十六进制表示）3）下表给出了CPU取指和译码每个节拍（时钟周期）的功能及有效信号若所取指令为加法指令，源操作数为立即寻址方式，目标操作数在R3中，请按上表格式用表格列出指令执行阶段每个节拍的功能及有效控制信号。4）若将该CPU改造成流水线处理器，流水线由取指（IF）、译码（ID）、取数（OF）、执行（EX）和写结果（WB）组成，简述处理结构相关时须解决的基本问题。28（6分）某计算机主频为200MHz，CPI为5，存储器总线宽度为32位。准备连接一个数据传输率为20KB/s的字符设备，及1个数据传输率为1MB/s的块设备；字符设备采用中断方式I/O，块设备采用DMA方式I/O，DMA传送方式为周期窃取方式，每次DMA传送数据块大小为4000B。请回答：1）若CPU平均每条指令访存1.2次，Cache命中率为0.98，则CPU平均每秒访问主存次数是多少？2）当两个设备均以最大能力工作时，每秒将有多少次DMA请求及中断请求？3）若采用I/O总线连接上述设备，且每个总线周期需要4个总线时钟周期，则I/O总线的总线时钟频率最少是多少？29（9分）在一个双CPU机器上执行四个进程（P1P4），进程到达时刻分别是0，5，10，20，优先级分别是1，2，3，4（值最大者优先级高），执行时间分别为15，10，25和10个时间单位，系统中有一个就绪队列（ready queue）。可采用下列可抢占调度算法：优先级（Priority）调度，时间片为10个时间单位的轮转（Round Robin）调度，以及最短作业优先（Shortest Job First）调度。请回答下列问题：1）分别画出采用上述各种调度算法的甘特图。2）若上下文切换开销为0，分别计算采用上述各种调度算法的平均等待时间和平均周转时间。30（8分）一个磁盘有1024个磁道，当前磁头位置在51号磁道，且正向第0号磁道运动。有一个文件分别存储在4个磁盘块中，按顺序其所处的磁道号分别为20，500，10，900，该文件的目录项存储在第50号磁道的某块中。请回答下列问题：1）假定磁盘调度采用LOOK策略，文件结构采用链接分配方式，给出读取整个文件的磁盘访问序列，计算所需的总寻道距离。2）假定磁盘调度策略采用C-SCAN策略，文件结构采用FAT分配方式，FAT表位于0磁道，若执行append操作（在文件末添加内容），添加的数据存储于600号磁道上的某块中。给出append操作的磁盘访问序列，计算相应的寻道距离。31（12分）车间有甲乙丙三个工人，甲生产零件A，乙生产零件B，甲和乙每生产出一个零件都放入到同一个周转箱中，丙每次从该箱中取出一件A和一件B组装成成品。周转箱每次只能有一个人放入或者取出零件，能放入的零件总数为n，规定A和B均不能连续放入，且放入一件A后才能放入B，使用信号量实现甲乙丙之间的同步。32（9分）在一个请求分页存储管理系统中，页表存放于内存中，所有的页框（Frame）初始都为空，一次页面失效（Page Fault）的处理时间为8ms；内存访问时间为500ns，其他时间忽略不计。假设分配给某作业的页框数为3，该作业的页引用序列为：1，3，5，6，1，3，5，6。请回答下列问题：1）分别采用先进先出（FIFO）、最近最少使用（LRU）和最优（OPT）页面置换算法时，各会产生多少次页面失效？完成上述页引用序列各需要多少时间？2）针对以上具有循环页引用序列特征的内存访问模式，是否存在不需未来知识的最优页面置换算法？如存在，请描述该算法；如不存在，请解释理由。2014年东南大学935计算机专业基础考研真题及参考答案一、选择题（共80分）1下面关于进程的描述中，不正确的是（）A进程是动态的概念B进程就是一个独立的程序C进程可以并发执行D进程可由程序、数据和进程控制块描述B【答案】2在多对一的线程模型中，一个多线程中的某个线程执行一个需阻塞的系统调用时，下列选项中正确的是（）A整个进程都将被阻塞B该进程的其他线程仍可继续执行C该阻塞线程将被撤销D该阻塞线程将阻塞直到进程退出A【答案】3采用多道程序设计技术能提高整个计算机系统的效率，其基本条件是（）A硬盘容量大B处理器执行指令速度快C外围设备多D系统具有处理器与外设并行工作的能力D【答案】4下列指令中，不是特权指令的是（）AI/O指令B读取当前时钟C设置基址寄存器D关闭中断B【答案】5在存储管理中，外部碎片指的是（）A存储分配完成所剩的空闲区B没有被使用的存储区C不能被使用的存储区D未被使用，又暂时不能使用的存储区D【答案】6进程所请求的一次打印输出结束后，进程状态会发生的变化是（）A从运行态变成就绪态B从运行态变成等待态C从等待态变成就绪态D从就绪态变成运行态C【答案】7关于Round Robin调度算法，以下说法正确的是（）I同样的情况下，时间片越大，平均周转时间越小FCFS算法是Round Robin算法的一种特殊情况只有实现了定时的机制，才能实现Round Robin算法Round Robin属于非抢占调度算法A仅I和B仅和C仅和D仅I和B【答案】8物理内存和虚拟存储空间相比，其大小关系是（）A前者比后者大B前者比后者小C两者一样大D不一定D【答案】9临界区指的是（）A一段内存共享区域B一个共享变量C访问临界资源的一段程序D一种同步机制C【答案】10 为使虚拟存储系统有效发挥其预期作用，所运行的程序应具有的特性是（）A程序应比较大B程序应该具有良好的局部性C程序应含有多个I/O操作D程序应含有较多的动态分配内存工作B【答案】11 下列说法正确的是（）I当发现系统中存在抖动（Thrashing）时，应更换一块更大的磁盘用于页面置换内存分页管理方式不会产生外部碎片磁盘访问时间主要是由旋转时延和传输时延组成FCFS算法可用于实现磁盘调度A仅I和B仅和C仅和D仅I和C【答案】12 一个请求分页存储管理系统中，假设分配给某作业的页框（Frame）数为3，该作业的页引用序列为0，2，1，3，0，2，4，0，2，1，3，4，所有的页框初始时都为空，分别采用最近最少次数使用（LRU）和最优（OPT）页面置换算法时，产生页面失效（Page Fault）的次数分别是（）A10和7B9和8C9和7D7和4A【答案】13 单处理器系统中有n（n2）个进程，若进程调度程序当前没有执行，则以下情形不可能发生的是（）A有一个运行进程，没有就绪进程，剩下的n1个进程处于等待状态B有一个运行进程和一个就绪进程，剩下的n2个进程处于等待状态C没有运行进程，有一个就绪进程，剩下的n1个进程处于等待状态D有一个运行进程和n1个就绪进程，没有进程处于等待状态C【答案】14 关于短作业优先（SJF）调度算法，下列说法正确的是（）ISJF算法能得到最优的平均等待时间SJF算法能得到最优的平均响应时间SJF算法可能产生”饥饿”（Starvation）现象SJF算法是一种实际系统中常用的CPU调度算法A仅I和B仅和C仅I和D仅和A【答案】15 下列选项中，不是文件系统应具备的功能的是（）A对文件按名存取B实现对文件的各种操作C提高磁盘的I/O速度D访问数据时实现从逻辑结构到物理结构的转换C【答案】16 下列文件的物理结构中，可能带来外部碎片问题的是（）A连续结构B链接结构C索引结构DHash结构A【答案】17 下列选项中，不属于算法的主要特征的是（）A有穷性B可行性C确定性D可读性D【答案】18 若一个栈S的入栈序列为0，1，2，3，4，5，6，7，8，9，对于下列序列，S的可能出栈序列是（）I5，6，8，7，2，1，4，3，0，90，2，1，6，5，8，7，4，3，92，0，1，4，3，7，8，6，5，96，5，7，8，4，3，1，2，9，0A仅IB仅C仅I和D仅和B【答案】19 对任意一个给定的二叉树进行前序、中序和后序遍历可得到三个遍历序列。下列有关这三个遍历序列的叙述中，正确的是（）I叶子结点在三个遍历序列中先后次序是一样的兄弟结点在三个遍历序列中先后次序是一样的父子结点在三个遍历序列中先后次序是一样的祖先和子孙结点在三个遍历序列中先后次序是一样的A仅I和B仅和C仅I和D仅和A【答案】20 下列选项中，不可能是任何二叉搜索树的前序遍历序列的是（）A4，2，3，5，6，7B4，3，2，7，6，5C6，5，4，2，3，7D6，5，3，4，2，7D【答案】21 用n（n大于等于2）个权值均不相同的字符构成哈夫曼树，下列关于该树的叙述中错误的是（）A树中一定没有度为1的结点B该树一定是一棵完全二叉树C树中两个权值最小的结点一定是兄弟结点D树中任一非叶子结点的权值一定不小于其任一子节点的权值B【答案】22 无向图G如下图所示，下列选项中，不可能是G的广度优先遍历序列的是（）A0，1，2，3，4，5B0，2，1，3，4，5C0，1，2，3，5，4D0，3，2，1，5，4C【答案】23 下列关于图的叙述中，正确的是（）A强连通有向图的任何顶点到其他所有顶点都有弧B图与树的区别在于图的边树大于等于顶点数C有向图的遍历不可采用广度优先遍历方法D带权无向图G中，若所有边的权值均不相同，则G的最小生成树是唯一的D【答案】24 若排序过程中出现这种情况，在最后一遍开始之前，所有元素都不能保证在其最终的位置上，则采用的排序算法是（）A冒泡排序B堆排序C快速排序D直接插入排序D【答案】25 若对15个元素进行快速排序，则元素的比较次数至少是（）A26B34C52D78B【答案】26 对序列14，9，7，10，20，1，5进行排序，若第一趟后的数据排列为5，9，1，10，20，7，14，则采用的排序算法是（）A选择排序B归并排序C希尔排序D冒泡排序C【答案】27 对一个长度为16的有序表，若采用折半查找法查找一个表中不存在的元素，则比较次数最多的是（）A7B6C5D4C【答案】28 在一棵初始为空的AVL树T中依次插入关键码1，2，3，4，5，6，7的结点后，T的根结点的关键码是（）A3B4C5D6B【答案】29 冯诺依曼模型计算机中存放指令地址的寄存器是（）APCBIRCMARDMDRA【答案】30 某计算机中各种指令的CPI平均为8，CPU采用5级流水方式执行指令，流水线每拍为2个时钟周期。执行程序A时，共执行2000条指令，此时流水线的加速比约为（）A4.0B5.0C8.0D10.0A【答案】31 下列奇偶校验码中，若有一个存在错误，则它是（）A10001001B01001101C11010110D10000101B【答案】32 某16位计算机中，存储器按字节编址，整数用补码表示。数据在存储器中采用小端次序存放，若X，Y，Z为整数，且X41，Y75，ZXY，Z存放在地址为A和A1存储单元中，则存储单元A的内容是（）A00HB74HC8CHDFFHC【答案】33 某CPU中，若进位/借位标志为CF，零标志为ZF，符号标志为SF（0表示正），溢出标志为OF，uA和uB为无符号整数，则判定uA小于等于uB的条件是（）ASF1BSFZF1CCF1DCFZF1D【答案】34 目前，内存条通常由DDR2 SDRAM或DDR3 SDRAM芯片组成，该芯片为多体存储器，能够在总线时钟上升沿、下降沿都传送数据。相对基本的SDRAM芯片，该类芯片提高性能采用的主要方法是（）A增加数据引脚数量B减小存储元和I/O电路延迟C交叉编址，并行或交叉存取D顺序编址，并行或交叉存取C【答案】35 下列虚拟存储器的叙述中，错误的是（）A虚拟存储器有自己的存储阵列B虚拟存储器需按程序逻辑地址访问C虚拟存储的慢表放在主存中D虚拟存储的快表结构类似于CacheA【答案】36 下列选项中，与CPU主时钟周期相同的是（）ACPU周期B机器周期C节拍周期D节拍脉冲C【答案】37 某同步总线的总线宽度为16位，每次数据传输需2个总线时钟周期，若希望总线带宽达到1064MB/s，则总线时钟的频率至少是（）A133MHzB266MHzC532MHzD1064MHzD【答案】38 下列总线仲裁方法中，仲裁过程不需要主设备参与的是（）A链式查询B独立请求C分布式仲裁D计数器定时查询B【答案】39 某磁盘有1800个磁道，每个磁道有120个扇区，每个扇区可以记录2KB的信息，若磁盘机的转速为5400转/分钟，则该磁盘的最大数据传输率为（）A2.73MB/sB19.33MB/sC20.60MB/sD22.12MB/sD【答案】40 Intel 8086 CPU采用向量方式处理中断和异常，支持多个可屏蔽中断向量，可以屏蔽中断请求及响应引脚为INTR及，则CPU采用的可屏蔽中断源识别方法是（）A软件查询B串行判优C并行判优D无法确定B【答案】二、综合应用题（4147题，共70分）41（9分）页式内存管理系统中，逻辑地址为24位，页面大小为512B，采用两极页表结构，页表中的每一项占2B。该系统中访问一次内存的时间为250ns，不考虑其他环节所用的时间。请回答下列问题：1）逻辑地址中，用于表示外层页表（outer page table）、页号和页内偏移量的位数分别是多少？2）简要描述该页式内存管理系统的逻辑地址到物理地址的转换过程。3）访问一个逻辑地址需要多长时间。【答案】（1）（2）查外层页表获得内层页表的开始地址，再根据内层页表偏移量获得对应的地址值与负内偏移量组合成为物理地址。（3）3250ns750ns。42（9分）一个系统中共存在A、B、C、D四类资源，有P0到P3四个进程，系统在某一时刻的资源分配情况如下表所示：请回答下列问题：1）死锁产生的四个条件分别是什么？2）需求（Need）矩阵的内容是怎样的？3）系统是否处于安全状态？为什么？【答案】（1）互斥、循环等待、占有并等待（请求和保持）、非抢占（不剥夺）。（2）NeedMaxAllocation（3）不是安全状态，因为找不到安全序列，也就是找不到某种进程推进顺序，使得每个进程都可顺序地完成。43（10分）假设缓冲区buf最多可存放n个数据，进程P1往buf中写数据，当buf中数据多于m个时允许进程P2从中取数据，m小于n，均为正数，试用信号量实现P1和P2之间的同步。【答案】44（10分）设散列表HT的存储空间是一个从0开始的一位数组，装填（载）因子为0.6，散列函数为H（key）key MOD 7。现将关键字序列（8，19，12，17，13，20）散列存储到HT中，处理冲突采用线性探测法。回答下列问题：1）请画出所构造的散列表。2）分别计算等概率的情况下，查找成功和查找不成功的平均查找长度。【答案】装填因子0.6，关键字个数6个，则散列表长度为6/0.610，地址为09。又38%71，19%75，12%75，17%73，13%76，20%76，则散列表为：ASLsucc（112123）/610/65/3。ASLunsucc（1212154）/716/7。45（11分）令A是具有n个元素的一维数组，x是A中的一个元素，若A中有一半以上的元素与x相同，则称x是A的主元素。例如：若数组A为a，c，a，b，a，d，a，则存在主元素a；若数组A为a，d，b，c，b，d，a，则A中不存在主元素。试设计算法，判断A中是否存在主元素，若存在则给出其主元素。请简要说明算法的设计思想，用C或C语言给出算法，并请说明算法的时间、空间复杂度。【答案】算法设计：读取第一个元素，设为主元素，并得主元素计数值由count0加1得到count1；读取下一个元素，若是主元素，count，若不是count；当count0时，将下一个读取元素置为主元素，重新计数；获得主元素后，再次扫描数组并计数，若计数次数大于一半以上，是主元素，否则不是。46（10分）某计算机主存按字节编址、地址空间为32位；Cache数据区容量为1MB，采用4路组相联映射方式、LRU替换算法、写回法写策略，块大小为32B。请回答下列问题：1）Cache共有多少个组？Cache行（块）包含目录表项及块数据区两部分，Cache行的大小至少为多少位？2）若CPU访存地址为00463050H，命中时Cache的组号是多少？命中时Cache行的标记字段的值是多少？（用二进制表示）3）某C语言程序段为若编译时sizeof（int）4，i分配在寄存器中，A分配在基址为00000060H的连续主存空间中。执行该程序段时，访问数组A共多少次？若仅考虑数组A的访存情况，Cache的命中率是多少？写出计算过程。【答案】（1）Cache地址为：组号13位、组内块号2位、块内地址5位。则Cache有2的13次方个组8192个组。主存地址为：区号14位、区内块号13位、块内地址5位。Cache行由目录表项和数据区两部分，目录表项位数为：142（LRU位）1（标记位）1（写回法脏位）18位。数据区为32*8位256位。则Cache行大小至少有18256274位。（2）0000 0000 0100 0110 0011 0000 0101 0000，则10 0011 0000 010为命中组号，Cache行标记字段的值为0000 0000 0100 01。（3）AiAi1等价于AiAiAi1，则一次循环需要访问主存三次。for（i0;i512;i2）可得循环次数为512/2256次，则该程序段共访存256*3768次。由sizeof（int）4，可得存储一个int型数据需要4B。由一个Cache块大小为32B，可得一个Cache块可以存放32/48个int型数据。int A512定义了512个int型数据，则存储A512共需要512/864个Cache块。则命中率为164/768704/76891.7%。47（11分）某8位计算机的存储器按字节编址，地址空间为8位。下图所示的是该机指令系统的指令格式，以及CPU内部与数据通路相关的结构。指令格式中，格式1指令功能为：Rd（Rd）OP1（Rs）或Rd（Rd）OP1（Rs），Rs、Rd表示寄存器，（Ry）表示寄存器Ry的内容，x表示存储单元x的内容，OP1000、001、010分别表示加法、算术左移、算术右移操作，移位位数放在Rs中。格式2指令为双字长指令，OP21000、1001、1010分别表示赋值、取数、存数操作，Rs/Rd表示源或目的寄存器，Imme/Address表示立即数或存储单元结构。CPU结构中，数据通路为单总线结构，R0R3为通用寄存器（编号为03），寄存器间的数据传送操作和ALU运算操作均需一个时钟周期，访存操作采用同步控制方式、需2个时钟周期，请回答下列问题：（1）若（IR）A8H，写出该指令的操作、源操作数寻址方式（2）某C语言语句为“yy*8”，若变量y的存储单元地址为23H，写出实现该语句功能的指令串。（通用寄存器可任意使用）（3）CPU取指并译码后，若IR中指令为：R3（R3）（R2），则该指令执行阶段至少需要几个时钟周期？（可以用文字或微操作步序列描述）【答案】（1）A8H1010 1000，1010对应为OP2的存数操作，Rs/Rd10，则源操作数的寻址方式为寄存器寻址。（2）yy*8，思路：先将y所在单元存入R0，将R0左移3位，再将R0放入y所在单元。1001 0000：取数操作；0010 0011：地址23H，这两步相当于R023H；1000 0100：赋值操作；0000 0011：3，这两步相当于R103H；0010 0001：R0算术左移（R1）位，相当于R0（R1）；1010 0000：存数操作；0010 0011：地址23H，这两步相当于23H（R0）；（3）总共需要5个时钟周期2015年东南大学935计算机专业基础考研真题及详解2016年东南大学935计算机专业基础考研真题（回忆版）2016年的题型跟14年的一样。选择题类似2014年的，共40道选择题。其中操作系统16道，数据结构和组成原理均12道。数据结构和操作系统都是很基础的，计组稍微难一点，不过仔细复习注意联系还是都可以轻松地选出正确答案的。操作系统1页表的题。（但是跟往年的差距很大）一个计算机的逻辑地址空间有64个页，每个页的大小是2048B。物理地址空间占用32个页框（frame）。一个程序P占用6个页框，并且0到5号逻辑页分别分配到3，4，1，7，10，11号页框（具体数字不太确定，只确定最后两个）。（1）P的逻辑地址有多少位（2）该计算机的物理地址有多少位（3）P运行时，逻辑地址为06045H和0C234H的物理地址分别是什么（这两个数字的具体是多少也不记得了，但是每个数字的前两位我确定是对的，而且都是5位16进制数）（4）若访问CPU的时间是200us，访问页表的时间是40us，命中率为90%，则有效访问时间是多少。（具体数字记不清了）2文件系统的题。（比较类似15年王道书上的237的第7题）一个文件系统有10个索引块，每个磁盘块大小为2048B。（1）若这10个索引块都是直接索引，则最大的文件是多大（2）若有7个直接索引，2个一级间接索引，1个二级间接索引，最大的文件系统有多大（3）若不用索引用FAT，FAT的大小已给。（具体想不起来数据了QAQ，反正这个题比较简单）3生产者消费者的题有三个进程，一个进程往缓冲区里放数，缓冲区里面最多只能放n个数。另外两个进程，一个从缓冲区里取负数，另一个从缓冲区里取非负数。实现这三个进程的同步过程。数据结构1想一个从10万个数里面选出最小的10个数的实现方法，不需要用算法实现，分析你的算法为什么高效。2一个数组，写一个算法找出这个数组中最大的逆序差。（逆序差就是ij的情况下，AjAi的差。比如4 15 5 6 9 1 16 11中最大的逆序差就是16115）计算机组成原理1Cache的题32位的计算机按字节编址。CPU的控制引脚有/M，和代表读和写，主存的片选端是。主存的主存块大小32B，Cache采8路组相联，LRU替换算法，写回法策略（1）Cache的地址共有多少位？（2）若主存访问的地址是12345678H，Cache命中，则Cache行标记中的内容是什么？（3）的逻辑关系式是什么？（4）总线应该使用什么传输模式？2指令系统的题16位的计算机，按字节编址。数据在计算机中以有符号整数补码的形式存放。DE是一个数据扩展器，扩展之后数据真值保持不变。有两种指令格式OP1和OP2，其格式如下表（其中OP1由OP1_1和OP1_2组成，Rs、Rs代表两个寄存器）可以进行的操作有RdOP1_1 Rs OP1_2或RdRs OP2 RdIMME或RsRd OP2RsDISP（具体的图是怎样不太记得了，左上角的部分都是我画的，比较重要的部分就是DE连入了ALU）（1）需要访问存储器的指令有多少条，该指令系统最多支持多少种指令？（2）完全记不得了QAQ，甚至想不起来是3道题还是4道QAQ（3）若DE的输入端有8个引脚I0到I7，输出端引脚为O0到Ox，则x是多少，O0到Ox的逻辑关系式是什么？（4）R2（R1）75H的微操作步序列2017年东南大学935计算机专业基础考研真题（回忆版）一、选择题（共80分）1在多对一的线程模型中，一个多线程中的某个线程执行一个需阻塞的系统调用时，下列选项中正确的是（）A整个进程都将被阻塞B该进程的其他线程仍可继续执行C该阻塞线程将被撤销D该阻塞线程将阻塞直到进程退出2进程可能发生调度的时机为（）正在执行的进程时间片用完正在执行的进程提出I/O请求进入等待系统创建新进程等待从硬盘中读数据的进程获得了数据AB、C、D、3某分段系统，地址为32位，段号为8位，最大段长为多少位（）A28B216C224D2324关于临界区，正确的是（）A访问临界资源的那段代码B访问共享资源的那段代码C用于系统同步的那段代码D用于系统互斥的那段代码5访问主存的时间为100ns，访问快表的时间为10ns，TLB命中率为0.9