江苏科技大学计算机科学与工程学院845计算机综合历年考研真题汇编

江苏科技大学计算机科学与工程学院845计算机综合历年考研真题汇编目录名改为计算机综合。为帮助考生全面复习，特提供2009~2012年408计算机学第一部分江苏科技大学计算机科学与工程学院845计算机基础综合历年考研真计算机科学与工程学院845计算机基础综合考研真题计算机科学与工程学院845计算机基础综合考研真题第二部分全国硕士研究生入学统一考试408计算机学科专业基础综合历年真题408计算机学科专业基础综合真题1．求整数n(n≥0)阶乘的算法如下，其时间复杂度是()。A．O(log2n)2．已知操作符包括‘+’、‘-’、‘*’、‘／’、‘(’和‘)’。将中序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是()。二叉树的结点总数为()。法时间复杂度是()。D．O(n×e)图拓扑序列的结论是()。7．有向带权图如题7图所示，若采用迪杰斯特拉(Dijkstra)算法求从源点b短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是()。8．下列关于最小生成树的叙述中，正确的是()。小生成树中Ⅲ．使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同Ⅳ．使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总同最右叶结点所含的关键字是()。序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是()。能的不同之处是()。UA所耗费的时间是()。y为()。14．float类型(即IEEE754单精度浮点数格式)能表示的最大正整数是 ()。程序段如下： ()。16．下列关于闪存(FlashMemory)的叙述中，错误的是()。的次数是()。和6个微命令，则操作控制字段至少有()。每传输一个地址或数据占用一个时钟周期。若该总线支持突发(猝发)传输方式，则一次“主存写”总线事务传输l28位数据所需要的时间至少是()。)。21．下列选项中，在I／O总线的数据线上传输的信息包括()。括()。．保存通用寄存器的内容Ⅲ．形成中断服务程序入口地PC23．下列选项中，不可能在用户态发生的事件是()。子程序调用不需要保存其内容的是()。25．下列关于虚拟存储的叙述中，正确的是()。层次的接口。其合理的层次组织排列顺序是()。一个安全序列是()。RRR3PO323P14O3P24O5P32O4P43145544453O22654关于此过程的叙述中，正确的是()。完成两个作业需要的时间最少是()。的叙述中，错误的是()。31．下列关于进程和线程的叙述中，正确的是()。A32．下列选项中，不能改善磁盘设备I／O性能的是()。TCPIPICMP()。 ()。35．以太网的MAC协议提供的是()。6．两台主机之间的数据链路层采用后退N帧协议(GBN)传输数据，数据接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为()。37．下列关于IP路由器功能的描述中，正确的是()。38．ARP协议的功能是()。则目的地址可以是()。中①、②、③阶段分别使用的应用层协议可以是()。题40图电子邮件发送接收示意图最小。请回 (1)给出完整的合并过程，并求出最坏情况下比较的总次数。 (2)根据你的合并过程，描述n(n≥2)个不等长升序表的合并策略，并说42．(13分)假定采用带头结点的单链表保存单词，当两个单词有相同的后像如题42图所示。题42图存储映像示意图共同后缀的起始位置(如图中字符i所在结点的位置p)。要求： (1)给出算法的基本设计思想。 A (3)说明你所设计算法的时间复杂度。 (1)该计算机的MIPS数是多少?平均每秒Cache缺失的次数是多少?在不 (2)假定在Cache缺失的情况下访问主存时，存在％的缺页率，则CPU平 CPUDMA高?为 (4)为了提高性能，主存采用4体交叉存储模式，工作时每l/4个存储周期算机中，带符号整数用补码表示，数据Cache和指存器，mem表示存储单元地址，(X)表示寄存器X或存储单元X的内容。表指令系统中部分指令格式指令的汇编格式指令的汇编格式指令功能令计算机采用5段流水方式执行指令，各流水段分别是取指(IF)、译码／读寄存器(ID)、执行／计算有效地址(EX)、访问存储器(M)和结果写回寄，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回 后，Rl的内容是多少?(用十六进制表示) )若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有 (4)若高级语言程序中某赋值语句为x＝2*x+a，x和a均为unsignedint模仿题44图画出这条语句对应的指令序列及其在流水线中45．(7分)某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集(扫描时间忽略不计)，本轮没有被访 (1)访问<0，4>时，对应的页框号是什么? (4)该策略是否适合于时间局部性好的程序?说明理由。46．(8分)某文件系统空间的最大容量为4TB(1T＝240)，以磁盘块为基 索引表项中块号最少占多少字节?可支持的单个文件最大长度是多少字节? (2)假设索引表区采用如下结构：第0~7字节采用<起始块号，块数>格式块数分别所占字节1IP分组的前40字节内容(十六进制)019b40008006lde8coa80008d34447500bd91388846b41c5000000005db000000000400031066e833d3444750cOa8000880bd9e0599fef846b41c66701216d023019c40008006ldefbcecOa8d3444750ff501043802019d400080061ddecOa80008d344475040bd91388846b4lc6e0599ff0c65500007ad3444750cOa80008880bd9e0599ff0846b41d6501016d0 CP哪几个在通过快速以太网传输时进行了填充? aIPS7-b表所4004006eCadd3444750ca760106来自S发出的分1388a108e0599ff0846b41d6501016dO组 (8-15)度生存时(TTL)总长度(16-31)源端源端口(0-15)目的端口(16-31)序号(seq)确认号(ack)数据偏移保留RCSSYI窗口紧急指针选项(长度可变)填充8计算机学科专业基础综合真题及详解1．求整数n(n≥0)阶乘的算法如下，其时间复杂度是()。A．O(log2n)【解析】设fact(n)的运行时间函数是T(n)。O其中O(1)为乘法运算的时间。因此，当n≤1时，T(n)-0(1)；当n>1时，T(n)＝T(n-1)+O(1)。则，T(n)＝O(1)+T(n-1)＝2×O(1)+T(n-2)＝(n-1)×O(1)+T(1)＝n×O(1)即fact(n)的时间复杂度为O(n)。2．已知操作符包括‘+’、‘-’、‘*’、‘／’、‘(’和‘)’。将中序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是()。的运算符直接进栈，否则需要退栈栈顶运算符(先出栈的运算符先计算，同优先级的运算符在栈中的先计算)。表达式a+b-a*((c+d)／e-f)+g产生后缀表达式的过程如下表所列：a+b-a* ( (+d)／e-f容++*(-*((-*((-*((+-*((+-*(-*(／-*(／-*(--*(-“*”的优先级大于栈顶元素“-”，则“*”进栈“(”对它之前后的运算符起隔离作用“(”对它之前后的运算符起隔离作用与其配对与其配对的左括号及其前所有运算出栈相abacdef*f-*-f-*-gfg+g-++栈中的操作符的最大个数是二叉树的结点总数为()。法时间复杂度是()。D．O(n×e)时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为O(n2)，其中n为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为0(e)，其中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。即可得出正确答案。图拓扑序列的结论是()。素均为零，说明该图为有向无环图，所以其拓扑序列存在，但不一7．有向带权图如题7图所示，若采用迪杰斯特拉(Dijkstra)算法求从源点b短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是()。执行Dijkstra算法过程中各步的状态表，故后续目标顶点依次为f,d,e。ccd5 集合S 点k1b2 efdd fd)f) d e} 8．下列关于最小生成树的叙述中，正确的是()。小生成树中Ⅲ．使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同Ⅳ．使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总同条权值最小的边可能构成回路，所以说法Ⅱ错误。当某个顶点有权值相同的边，使用普里姆(Prim)算法从不同顶点开始得到的最小生成树并不一定相同，所以说法Ⅲ错误。当最小生成树不唯一时，使用普里姆算法和克鲁斯卡尔(Kruskal)以说法Ⅳ错误。由此可得出正最右叶结点所含的关键字是()。个数等于[m/2]-1，而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于[m/2]-1，则需将其兄弟结点中最小(或最大)的关键字上移至双亲结点中，而将双亲结点中小于(或大于)且紧靠该上移关键字的关键字下移至被删序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是()。确定最大(或最小)关键字所在的位置。快速排序每一趟排序结束时将确定基准能的不同之处是()。较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。折半插入排序的时间复杂度仍为O(n2),所以两者之间的不同只可能是元素之间的比UA所耗费的时间是()。y为()。0FFFAH。14．float类型(即IEEE754单精度浮点数格式)能表示的最大正整数是 ()。＝2127×(2-2-23)＝2128-2104。程序段如下： ()。16．下列关于闪存(FlashMemory)的叙述中，错误的是()。的次数是()。和6个微命令，则操作控制字段至少有()。【解析】33个微命令分成5个互斥类(即5个字段)，根据每个类中微命令每传输一个地址或数据占用一个时钟周期。若该总线支持突发(猝发)传输方式，则一次“主存写”总线事务传输l28位数据所需要的时间至少是()。)。传【解析】USB总线即通用串行总线，它的特点有：(1)即插即用；(2)热插拔；(3)有很强的链接能力能将所有外设链接起来，且不损失带宽；(4)有很好的可扩展性；(5)高速传输，速度可达480Mbps。所有A，B，C都符合21．下列选项中，在I／O总线的数据线上传输的信息包括()。括()。保存通用寄存器的内容Ⅲ．形成中断服务程序入口地PC断服务程序(形成中断服务程序入口地址并送PC)。而保存通用寄存器内容的操23．下列选项中，不可能在用户态发生的事件是()。共享和保护，设定了用户态和内核态(可以通过设置软、硬件标志位来实现)，在用户态运行用户的程序，在内核运行系统的程序。所以，从选项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控缺页的发生也是不可控的，可以发生在用户代码之间；时调会在用户态发生(所谓发生指其起始的源头时刻)，必定是在内核态(进程调度)发子程序调用不需要保存其内容的是()。序的地址，计数器(指针)和数据寄存器以外，还需要保存程序状态字。子程序断处理程序必定会保存程序状态字寄存25．下列关于虚拟存储的叙述中，正确的是()。中，当所需要的代码部分不在内存时，通过一种技术(例如缺页中断技术)，将所需要的页面调入内存，从而继续运行。相应，虚层次的接口。其合理的层次组织排列顺序是()。一个安全序列是()。已分配资源资源最大需求323554O35364O54O2O4425314424进程R1R2R3P32O4P4314P24O5P1403PO323334442l033247372lO121O637关于此过程的叙述中，正确的是()。【解析】对于Ⅰ，当所读文件的数据不再内存时，产生中断(缺页中断、缺段中断)，原进程进入睡眠等待状态(阻塞状态)，直到所需数据从外村调入内完成两个作业需要的时间最少是()。的叙述中，错误的是()。如，通常访问临界资源可能是慢速的外设(如打印机)，如果在进程访问打印机时，31．下列关于进程和线程的叙述中，正确的是()。A程的基本单位”这句话说反了，明显错误。“系统级线程和用户级线程的切要内核的支持”也不正确，因为用户级线程的切换由用户编写的32．下列选项中，不能改善磁盘设备I／O性能的是()。PPP议是广域网数据链路层协议，直接为网络层， ()。接插装置；电气特性：规定传输二进制位时，就是规程，也就是过程特性，答案是C。35．以太网的MAC协议提供的是()。进行编号，也不要求对方发回确认。因此，以太网提供的服务是不可靠的服务，6．两台主机之间的数据链路层采用后退N帧协议(GBN)传输数据，数据接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为()。帧，要尽可能多发送帧，应以短的数据帧时间总共可以发送668/64＝(帧)，为了保证发送帧序号和确认帧序号在此期间Ⅱ说法仅Ⅰ、Ⅱ、Ⅳ，因此答案是C。38．ARP协议的功能是()。则目的地址可以是()。中①、②、③阶段分别使用的应用层协议可以是()。收信人的用户邮箱中，等待收信人在他方便时进行读取。收信人在打算收信时，回(如果邮箱中有来信的话)。 (1)给出完整的合并过程，并求出最坏情况下比较的总次数。 (2)根据你的合并过程，描述n(n≥2)个不等长升序表的合并策略，并说解： 哈夫曼树故最坏情况下比较的总次数计算如下：；4+84+109+194+394＝825。 (2)各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则42．(13分)假定采用带头结点的单链表保存单词，当两个单词有相同的后像如题42图所示。题42图存储映像示意图共同后缀的起始位置(如图中字符i所在结点的位置p)。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出 (3)说明你所设计算法的时间复杂度。解： (1)算法的基本设计思想：将两个链表以表尾对齐：令指针p、q分别指向strl和str2的头结点，若qp (2)用C语言算法描述如下： (3)参考答案的时间复杂度为：0(m+n)或O(max(m，n))。其中 (1)该计算机的MIPS数是多少?平均每秒Cache缺失的次数是多少?在不 (2)假定在Cache缺失的情况下访问主存时，存在％的缺页率，则CPU平 CPUDMA高?为 (4)为了提高性能，主存采用4体交叉存储模式，工作时每l/4个存储周期 均每秒Cache缺失的次数为：20M××(1-99％)＝300000；e (2)平均每秒钟“缺页”异常次数为：300000×％＝次； (4)4体交叉存储模式能提供的最大带宽为：4×4B/50ns＝320MB/s。44．(12分)某16位计算机中，带符号整数用补码表示，数据Cache和指存器，mem表示存储单元地址，(X)表示寄存器X或存储单元X的内容。表指令系统中部分指令格式指令的汇编格式指令的汇编格式指令功能指令该计算机采用5段流水方式执行指令，各流水段分别是取指(IF)、译码／读寄存器(ID)、执行／计算有效地址(EX)、访问存储器(M)和结果写回寄存器(WB)，流水线采用“按序发射，按序完成”方式，没有采用转发技术处理 后，Rl的内容是多少?(用十六进制表示) )若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有 (4)若高级语言程序中某赋值语句为x＝2*x+a，x和a均为unsignedint模仿题44图画出这条语句对应的指令序列及其在流水线中解： 1wei后为1111111011111111B，即指令执行后(R1)＝FEFFH。 (2)至少需要5+(4-1)＝8个时钟周期数。 (3)I3的ID段被阻塞的原因：因为I3与I1和I2都存在数据相关，需等到 (4)x＝2*x+a对应的指令序列为：45．(7分)某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集(扫描时间忽略不计)，本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中 (1)访问<0，4>时，对应的页框号是什么? (4)该策略是否适合于时间局部性好的程序?说明理由。 (4)适合。理由：如果程序的时间局部性越好，从空闲页框链表中重新取回46．(8分)某文件系统空间的最大容量为4TB(1T＝240)，以磁盘块为基 索引表项中块号最少占多少字节?可支持的单个文件最大长度是多少字节? (2)假设索引表区采用如下结构：第0~7字节采用<起始块号，块数>格式块数分别所占字节解： 32个块号，索引表 1IP分组的前40字节内容(十六进制)019b40008006lde8coa80008d34447500bd91388846b41c5000000005db000000000400031066e833d3444750cOa8000880bd9e0599fef846b41c66701216d02019c40008006ldefcOa80008d3444750bd388846b41c6e0599ff0501043802019d400080061ddecOa80008d344475040bd91388846b4lc6e0599ff0c65500007ad3444750cOa80008880bd9e0599ff0846b41d6501016d0 CP哪几个在通过快速以太网传输时进行了填充? aIPS7-b表所44006eCadd3444750ca760106来自S发出的分1388a108e0599ff0846b41d6501016dO组 (8-15)度生存时(TTL)总长度(16-31)源端源端口(0-15)目的端口(16-31)序号(seq)确认号(ack)数据偏移保留RCSSYI窗口紧急指针选项(长度可变)填充KH度均大于46字节，所以 (2)由3号分组封装的TCP段可知，发送应用层数据初始序号为846bHB 408计算机学科专业基础综合真题while(x<n/2)A．O(log2n)d开头的序列个数是()。素存储在A[0]处，则初始时front和rear的值分别是()。)。无右孩子的结点个数是()。 ()。8．下列关于图的叙述中，正确的是()。9．为提高散列(Hash)表的查找效率，可以采用的正确措施是()。Ⅰ．增大装填(载)因子Ⅱ．设计冲突(碰撞)少的散列函数Ⅲ．处理冲突(碰撞)时避免产生聚集(堆积)现象10．为实现快速排序算法，待排序序列宜采用的存储方式是()。将其再调整为大根堆，调整过程中元素之间进行的比较次数是()。12．下列选项中，描述浮点数操作速度指标的是()。14．下列各类存储器中，不采用随机存取方式的是()。是()。下列寻址方式中，不属于偏移寻址方式的是()。号标志SF和溢出标志OF，条件转移指令bgt(无符号整数比较大于时转移)的转移条件是()。18．下列给出的指令系统特点中，有利于实现指令流水线的是()。下列有关指令执行的叙述中，错误的是()。．20．在系统总线的数据线上，不可能传输的是()。C．握手(应答)信号 (0≤i≤4)表示对Li级中断进行屏蔽。若中断响应优先级从高到低的顺序是个CPU时间的百分比至少是()。24．下列选项中，在用户态执行的是()。26．用户程序发出磁盘I／O请求后，系统的正确处理流程是()。进程R1R2R3P12OOP212OP3O11R2R31O33O12lOO1120此时的安全序列是()。28．在缺页处理过程中，操作系统执行的操作可能是()。29．当系统发生抖动(thrashing)时，可以采取的有效措施是()。逻辑地址的阶段是()。缓件的时间分别是()。两个操作完成后，2的值()。33．TCP／IP参考模型的网络层提供的是()。的波特率是()。35．数据链路层采用选择重传协议(SR)传输数据，发送方已发送了0H3帧数是()。MAC)。将IP分组正确地路由到图中所有子网，则在R1中需要增加一条路由(目的网络，子网掩码，下一跳)是()。38．在子网中，能接收目的地址为的IP分组的最大主机数是()。确的TCP段可能是()。甲的确认序号是()。41．(8分)已知有6个顶点(顶点编号为0--5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。46∞∞∞5∞∞∞43∞∞33要求： (1)写出图G的邻接矩阵A。 (2)画出有向带权图G。 (3)求图G的关键路径，并计算该关键路径的长度。42．(15分)一个长度为L(L≥1)的升序序列S，处在第「L／2」个位置的中位数。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出 (3)说明你所设计算法的时间复杂度和空间复杂度。43．(11分)假定在一个8位字长的计算机中运行下列C程序段：z2、k1和k2。请回答下列问题。(提示：带符号整数用补码表示) (1)执行上述程序段后，寄存器R1、R5和R6的内容分别是什么?(用十六进制表示) (2)执行上述程序段后，变量m和kl的值分别是多少?(用十进制表示) (3)上述程序段涉及带符号整数加／减、无符号整数加／减运算，这四种运 (4)计算机内部如何判断带符号整数加／减运算的结果是否发生溢出?上述44．(12分)某计算机存储器按字节编址，虚拟(逻辑)地址空间大小为16MB，主存(物理)地址空间大小为1MB，页面大小为4KB；Cache采用直接六进制形式。 (1)虚拟地址共有几位，哪几位表示虚页号?物理地址共有几位，哪几位表示页框号(物理页号)? (2)使用物理地址访问Cache时，物理地址应划分哪几个字段?要求说明每 (3)虚拟地址001C60H所在的页面是否在主存中?若在主存中，则该虚拟 (4)假定为该机配置一个4路组相联的TLB，该TLB共可存放8个页表项，若其当前内容(十六进制)如题44-c图所示，则此时虚拟地址024BACH所在的45．(8分)某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达请添加必要的信号量和P、V(或wait()、signal())操作，实现上述过46．(7分)某文件系统为一级目录结构，文件的数据一次性写入磁盘，已 (1)在连续、链式、索引三种文件的数据块组织方式中，哪种更合适?要求FCB哪些相关描述字段? 47．(9分)某主机的MAC地址为00-15-C5-Cl-5E-28，IP地址为(私有址)。题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太题47-b图以太网数据帧(前80字节) (2)该主机在构造题47-b图的数据帧时，使用什么协议确定目的MAC地 (3)假设HTTP/协议以持续的非流水线方式工作，以此请求一响应时间为个RTT? (4)该帧所封装的IP分组经过路由器R转发时，需修改IP分组头中的哪些8计算机学科专业基础综合真题及详解while(x<n/2)A．O(log2n)<log2(n/2)＝O(log2n)。d列个数是()。作： decba 素存储在A[0]处，则初始时front和rear的值分别是()。和rear的值都为0。由于进队操作要执行(rear+1)%n，则初始时front的值叶子结点数为384，而叶子结点的个数为768-384＝384。([x]表示不大于x的最大整数，比如[]＝3)。)。8棵二叉树的中序序列分别为： 无右孩子的结点个数是()。【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点(因为成二叉树后一定没有右孩子)，另外，树根结点转换成二叉树后也没有右孩子。题目中树的总结 ()。8．下列关于图的叙述中，正确的是()。省空间若有向图中存在拓扑序列，则该图不存在回路复出现的路径称为简单路径；回路显然不是简单路径，所以选项Ⅰ错误。稀疏图用邻接表表示比邻接矩阵节省存储空间，稠密图适合用邻接矩阵的存储表示，所以选项Ⅱ错误。利用拓扑排序算法可以判断图中是否存在回路，即在拓扑排序输出结束后所余下的顶点都有前驱，则说明了只得到了部分顶点的拓扑有序序列，9．为提高散列(Hash)表的查找效率，可以采用的正确措施是()。Ⅰ．增大装填(载)因子Ⅱ．设计冲突(碰撞)少的散列函数Ⅲ．处理冲突(碰撞)时避免产生聚集(堆积)现象【解析】散列表的查找效率(比较次数)取决于：散列函数、处理冲突的方10．为实现快速排序算法，待排序序列宜采用的存储方式是()。将其再调整为大根堆，调整过程中元素之间进行的比较次数是()。 (1)为原堆， (2)为插入18后， (3)比较10与18，交换后， (4)比较25与18，不交换，即为调整后的新的大根堆。12．下列选项中，描述浮点数操作速度指标的是()。MIPS(MillionInstructionsperSecond)表示每秒执行多少百万条指令。同指令的功能不同，造成指令执行时间不同，也即指令执行所用的时钟数不同，IPC(InstructionsperCycle)每个时钟周期执行的指令数。(按14．下列各类存储器中，不采用随机存取方式的是()。是()。RAM有32MB，但不排除还有ROM下列寻址方式中，不属于偏移寻址方式的是()。取的有效地址，然后再按此有效地址从主存中读出操作数。其余三种寻址号标志SF和溢出标志OF，条件转移指令bgt(无符号整数比较大于时转移)的转移条件是()。18．下列给出的指令系统特点中，有利于实现指令流水线的是()。下列有关指令执行的叙述中，错误的是()。．每个指令周期中至少要访问内存一次，即从内存中取指令。其次，指令有的简单20．在系统总线的数据线上，不可能传输的是()。C．握手(应答)信号【解析】握手(应答)信号属于通信联络控制信号应该在通信总线上传输，。 (0≤i≤4)表示对Li级中断进行屏蔽。若中断响应优先级从高到低的顺序是。个CPU时间的百分比至少是()。U轮转的算法。其次，因为问题提到短任务，则先来先服务的算法也可以排除了，一个?我们可务，均可以得到调度，而且，较短任务会得到优先的调度。故满足短24．下列选项中，在用户态执行的是()。。于当设备时，首先在用户程序中发起一次系统调用，操作系统的内核接到该后调用处理程序进行处理，根据调用格式和形参，再转到相应的设备驱处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断设备，即设置好控制寄存器参数和中断向量等参数后阻塞自己；当设备所需数据到达后设备硬件发出中断，设备驱动程序唤醒，将数据按上述逆向回传到用户程序中，或继续驱动设备执行下一条指令。因此，正确进程R1R2R3P12OOP212OP3O11OO113213l2OOR2R310此时的安全序列是()。已分配资源尚需资源可用资源R1R2R3R1R2R3R1R2R320OO0lO211O0210O1111233021O22222222128．在缺页处理过程中，操作系统执行的操作可能是()。分装入的，还有部分是处于外存上的，因此，页所做的工作就是首先要在内存中找到空闲页框并分配给需要访问的页(若没有空闲磁盘，或覆盖掉，然后将此页分配给需要访问的页)，分配妥当以后，缺页中断处理程序调用设备驱动程序做磁盘I/O，将位于外存(一般是磁盘)上的页面调入内存，调入后转身去修改页表，将页表中代表该页是否在内存的标志位(一般称为存在位或有效位、在位位)修改为“真”，将物理页框号填入相应位置，若必要29．当系统发生抖动(thrashing)时，可以采取的有效措施是()。存容量。增加内存容量可以是直接添加物理内存(大型计算机都可以在不关机的增加内存。而增加交换逻辑地址的阶段是()。。件的时间分别是()。对单一缓冲区，从磁盘写入和读出到用户区的操作必须串行执行，也就是要保证分析与从磁盘写入缓冲区的操作可以并行。从本题看，由于分析所用的时间小于从磁盘写入缓冲区的时间，因此，CPU会空闲。单缓冲区的总时间＝(磁盘写入缓冲区时间+缓冲区读出时间)×10+CPU处理最后一块数据的时间＝(100+50)以并行，所以，当第一个缓冲区写满以后，磁盘前一个已经满了的缓冲区被读出到用户区，并立时间＝(磁盘写入缓冲区时间)×10+读出最后一块数据时间+CPU分析最后一块数据时间＝(100)×10+50+50＝1100μs。PV施，则最后结果就哪个进程后执行存数store的操作了，哪个进程后操作，结果就是那个进程的x的波特率是()。 N为一个码元所取的离散值个数。从而可以得到波特率与数据传输速率的关系，CBlogNbpsCN，因此波特率35．数据链路层采用选择重传协议(SR)传输数据，发送方已发送了0H3帧数是()。将IP分组正确地路由到图中所有子网，则在R1中需要增加一条路由(目的网络，子网掩码，下一跳)是()。R与子网把大网络分成若干小网络相反，案是D。38．在子网中，能接收目的地址为的IP分组的最大主机数是()。确的TCP段可能是()。段的序号为900。若主机乙仅正确接收到第1和第3个段，则主机乙发送给主机甲的确认序号是()。数据包中第一个字节的序号应该41．(8分)已知有6个顶点(顶点编号为0--5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。46∞∞∞5∞∞∞43∞∞33要求： (1)写出图G的邻接矩阵A。 (2)画出有向带权图G。 (3)求图G的关键路径，并计算该关键路径的长度。解：(1)由题可以画出待定上三角矩阵的结构图如下(图中?为待定元素)：填入各行即得邻接矩阵： (2)根据第一步所得矩阵A容易做出有向带权图G，如下： (3)下图中粗线箭头所标识的4个活动组成图G的关键路径。42．(15分)一个长度为L(L≥1)的升序序列S，处在第「L／2」个位置的中位数。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出 (3)说明你所设计算法的时间复杂度和空间复杂度。设计思想：分别求两个升序序列A和B的中位数，设ab能出现(a，b)范围内，舍弃a所在序列A的较 (2)用C语言算法描述如下： 和O(1)。43．(11分)假定在一个8位字长的计算机中运行下列C程序段：z2、k1和k2。请回答下列问题。(提示：带符号整数用补码表示) (1)执行上述程序段后，寄存器R1、R5和R6的内容分别是什么?(用十六进制表示) (2)执行上述程序段后，变量m和kl的值分别是多少?(用十进制表示) (3)上述程序段涉及带符号整数加／减、无符号整数加／减运算，这四种运 (4)计算机内部如何判断带符号整数加／减运算的结果是否发生溢出?上述＝B＝90H、(R6)＝x+y＝01111100B＝7CH。 数(用补码表示)时,其值为-1111010B＝-112；同理k1＝(m-n)＝(x-y)＝90H＝10010000B，解释为带符号整数(用补码表示)时,其值为-1111010B＝ 个加法器及辅助电路实现，n位加法器实现的是而a-b＝a+[-b]补(mod2n)实现；对于带符号整数用补码表示，补码加减运算 (4)判断溢出的方法有3种：一位符号位、进位位和双符号位。上述程序段44．(12分)某计算机存储器按字节编址，虚拟(逻辑)地址空间大小为16MB，主存(物理)地址空间大小为1MB，页面大小为4KB；Cache采用直接 (1)虚拟地址共有几位，哪几位表示虚页号?物理地址共有几位，哪几位表示页框号(物理页号)? (2)使用物理地址访问Cache时，物理地址应划分哪几个字段?要求说明每 (3)虚拟地址001C60H所在的页面是否在主存中?若在主存中，则该虚拟 (4)假定为该机配置一个4路组相联的TLB，该TLB共可存放8个页表项，若其当前内容(十六进制)如题44-c图所示，则此时虚拟地址024BACH所在的其中虚页号占12位；物理地址20位，其中页框号(实页号)占8位。 3)虚拟地址001C60H＝000000000001110001100000B，该虚拟地地址应该映射到Cache的第3行中，其有效位为1，标记值105H≠04CH(物理地址高12位)，故访问该地址时Cache不命中。 (4)虚拟地址024BACH＝00000001100B，虚页号为024H，TLB中存放45．(8分)某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达请添加必要的信号量和P、V(或wait()、signal())操作，实现上述过解：(1)互斥资源：取机号，故设一个互斥信号量mutex。 (2)同步问题：顾客需要获得空座位等待叫号，当营业员空闲时，将选取一顾客初始时为0，最大不超过10(10把座椅)，各进程的具体实现如下所示：46．(7分)某文件系统为一级目录结构，文件的数据一次性写入磁盘，已 (1)在连续、链式、索引三种文件的数据块组织方式中，哪种更合适?要求FCB哪些相关描述字段? B47．(9分)某主机的MAC地址为00-15-C5-Cl-5E-28，IP地址为(私有)。题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太题47-b图以太网数据帧(前80字节) (2)该主机在构造题47-b图的数据帧时，使用什么协议确定目的MAC地 (3)假设HTTP/协议以持续的非流水线方式工作，以此请求一响应时间为个RTT? (4)该帧所封装的IP分组经过路由器R转发时，需修改IP分组头中的哪些)以太网的数据部分是IP数据报，只要找出相应字段所在的字节即 bWeb (4)私有地址要和Internet上的主机通信时，须由NAT路由器进行网络地408计算机学科专业基础综合真题不允许连续三次进行退栈操作，则不可能得到的出栈序列是()。树中，关键字37所在结点的左、右子结点中保存的关键字分别是 ()。6．对n(n≥2)个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是()。7．若无向图G＝(V，E)中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是()。8．对下图进行拓扑排序，可以得到不同的拓扑序列的个数是()。找法查找一个L中不存在的元素，则关键字的比较次数最多是()。确的是()。如下：则采用的排序方法可能是()。12．下列选项中，能缩短程序执行时间的措施是()。 ()。示，float和double分别用IEEE754单精度和双精度浮点数格式表示)，已知i ()。 (Ⅰ)i＝＝(int)(float)i (Ⅱ)f＝＝(float)(int)f (Ⅲ)f＝＝(float)(double)f (IV)(d+f)-d＝＝f所在芯片的最小地址是()。RAMROM)。17．下列命中组合情况中，一次访存过程中不可能发生的是()。18．下列寄存器中，汇编语言程序员可见的是()。A．存储器地址寄存器(MAR)B．程序计数器(PC)C．存储器数据寄存器(MDR)D．指令寄存器(IR)19．下列选项中，不会引起指令流水线阻塞的是()。A．数据旁路(转发)20．下列选项中的英文缩写均为总线标准的是()。21．单级中断系统中，中断服务程序内的执行顺序是()。现场；Ⅶ中断返回幕，则需要的显存总带宽至少约为()。23．下列选项中，操作系统提供的给应用程序的接口是()。24．下列选项中，导致创建新进程的操作是()。26．下列选项中，降低进程优先级的合理时机是()。代码实现如下：则并发执行进程P0和Pl时产生的情况是()。采用最佳适配(BestFit)算法，分配和释放的顺序为：分配15MB、分配30MB、的个数至少是()。件最大长度是()。31．设置当前工作目录的主要目的是()。 ()。33．下列选项中，不属于网络体系结构中所描述的内容是()。延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少是()。是()。机发送的ICMP报文件类型是()。P最大子网个数、每个子网内的最大可分配地址个数分别是()。38．下列网络设备中，能够抑制广播风暴的是()。窗口大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是()。用户主机、本地域名服务器发送的域名请求消息数分别为()。，8，30，11，18，9，14)散列存储到散＝(key×3)MOD7，处理冲突采用线性探测再散列法，要求装填(载)因子为。 (1)请画出所构造的散列表。 (2)分别计算等概率情况下查找成功和查找不成功的平均查找长度。42．(13分)设将n(n>1)个整数存放到一维数组R中。试设计一个在时RPPn)x1，…,xp-1)。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出 法的时间复杂度和空间复杂度。操作数一(操作数一(Rn)操作数一((Rn))操作数一((Rn))， (Rn)+1一Rn转移目标地址一(PC)(Rn) (Rn) (Rn)+注：(X)表示存储器地址X或寄存器X的内容。请回答下列问题： (1)该指令系统最多可有多少条指令?该计算机最多有多少个通用寄存器?存储器地址寄存器(MAR)和存储器数据寄存器(MDR)至少各需要多少位? (2)转移指令的目标地址范围是多少? (3)若操作码0010B表示加法操作(助记符为add)，寄存器R4和R5的的内容为5678H，地址5678H中的内容为1234H，则汇编语句“add(R4)， (R5)+”(逗号前为源操作数，逗号后为目的操作数)对应的机器码是什么(十六进制表示)?该指令执行后，哪些寄存器和存储单元的内容会改变?改变后的内容是什么?44．(12分)某计算机的主存地址空间大小为256MB，按字节编址，指令中，数组a按行优先方式存放，首地址320(十进制数)。请回答下列问题，要 (1)若不考虑用于Cache一致性维护和替换算法的控制位，则数据Cache (2)数组数据a[0][31]和a[1][1]各自所在的主存块对应的Cache行号分别是多少(Cache行号从0开始)? (3)程序A和B的数据访问命中率各是多少?哪个程序的执行时间更短?45．(7分)假设计算机系统采用CSCAN(循环扫描)磁盘调度策略。使用 (1)请说明在上述条件下如何进行磁盘空闲状态的管理。 (3)如果将磁盘替换为随机访问的Flash半导体存储器(如U盘、SSD等)，46．(8分)设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页(Page)数据存储空间，页的大小为1KB，操作系me前的该进程访问情况如下表所示(访问位即使用位)。号入时刻访问位O71141221391下列问题： (1)该逻辑地址对应的页号是多少? (2)若采用先进先出(FIFO)置换算法，该逻辑地址对应的物理地址是多少? (3)若采用时钟(CLOCK)置换算法，该逻辑地址对应的物理地址是多少?要求给出计算过程。(设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，如图所示)47．(9分)某局域网采用CSMA／CD协议实现介质访问控制，数据传输率 (1)若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间?最长需经过多长时间?(假设主机甲和主机乙发送数据过程中，其他主机不发送数据) (2)若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧 (1518字节)向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲机甲的有效数据传输速率是多少?(不考虑以太网帧的前导码)8计算机学科专业基础综合真题及详解不允许连续三次进行退栈操作，则不可能得到的出栈序列是()。数队列为输出受限的双端队列。本题解题方法分别判断每个选项如何项所给序列的进队操作序列分别为：，树中，关键字37所在结点的左、右子结点中保存的关键字分别是 ()。衡。这属于RL(先右后左)型平衡旋转，需做两次(先右旋后左旋转)旋转操作。6．对n(n≥2)个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是()。通的，则需要的边数最少是()。2G8．对下图进行拓扑排序，可以得到不同的拓扑序列的个数是()。 (1)在有向图中选一个没有前驱的顶点并且输出它； (2)从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已找法查找一个L中不存在的元素，则关键字的比较次数最多是()。【解析】折半查找法在查找不成功时和给定值进行比较的关键字个数最多为 (logn)+1，在本题中，n＝l6，故比较次数最多为5。确的是()。数。如下：则采用的排序方法可能是()。序往后依次比较，使大值“沉底”。希尔排序的基本思想是：先对序列进行调整”，待序列中的记录“基本有序”时再进行直接插入排序。宏观调整是：通过某种规则将大的待排序序列分割为若干小的待排序序列，再依次多次，每次分割的序列数逐渐增多，基数排序是分配排序的一种，这类排序不是通过关键字比较，而是通过“分配”．下列选项中，能缩短程序执行时间的措施是()。【解析】一般说来，CPU时钟频率(主频)越高，CPU的速度就越快；优化r4＝F8H。若将运算结果存放在一个8位寄存器中，则下列运算会发生溢出的是 )。t示，float和double分别用IEEE754单精度和双精度浮点数格式表示)，已知i ()。 (Ⅰ)i＝＝(int)(float)i (Ⅱ)f＝＝(float)(int)f (Ⅲ)f＝＝(float)(double)f (IV)(d+f)-d＝＝f并没有改变其值。所在芯片的最小地址是()。HRAMROM)。解析】RAM中的内容断电后即丢失(易失性)，ROM中的内容断电后不会丢失(非易失性)，同时RAM和ROM都采用随机存取方式(即CPU对任何一个存储单元的存取时间相同)，区别在于RAM可读可写，ROM只读不写。而17．下列命中组合情况中，一次访存过程中不可能发生的是()。【解析】TLB(快表)和慢表(页表，Page)构成二级存储系统，若TLB命18．下列寄存器中，汇编语言程序员可见的是()。A．存储器地址寄存器(MAR)B．程序计数器(PC)C．存储器数据寄存器(MDR)D．指令寄存器(IR)存储器地址寄存器(MAR)、存储器数据寄存器(MBR)和状态标志寄存器 (PSWR)，这些寄存器中有些是CPU的内部工作寄存器，对汇编语言程序员来说是透明的，在汇编语言程序设计中不会出现。但汇编语言程序员可以通过制定待执行指令的地址来设置PC的值,所以程序计数器(PC)对于汇编语言程序员可19．下列选项中，不会引起指令流水线阻塞的是()。A．数据旁路(转发)20．下列选项中的英文缩写均为总线标准的是()。21．单级中断系统中，中断服务程序内的执行顺序是()。现场；Ⅶ中断返回硬件(中断隐指令)完成的，所以在单级中断系统中，中断服务程序内应完成的幕，则需要的显存总带宽至少约为()。834Mbps。23．下列选项中，操作系统提供的给应用程序的接口是()。形式，例如常规的命令行、图形化人机交互接口 (GUI)、自然命令用户接口(NUI)等，而系统调用中除了常规的一些传统的系统调用(例如read())以外，还有经过扩展的复杂调用(例如多种API)，以及包含在Lib库中的各种封装好的过程调用(最终都是通过系统调用陷入到操作系统中去的)等。24．下列选项中，导致创建新进程的操作是()。也可以由父进程创建，例如lock()时，操作系统首先到PCB表区搜索空闲的表过程有一段时间(主要涉及资源分配需要协调)，许多操作系统为此设立了一个系统填写进程ID号、处理机参数、进程参数(状态、特权、优先级)、分配内存(若是26．下列选项中，降低进程优先级的合理时机是()。先级，处于就绪队列等待调度的进程一般不会改变其优先级。进行这样的操作主要是为了改善交互式系统的响应时间，并均衡各个作业的公平性。采用时间片轮转技术主要为改善交互式用户的感受，使其觉得是独享计算机(时间片轮转可以有效地防止计算繁忙型的进程独占计算机)，时间片用完后降低其优先级是为了改善新进程的响应时间(新进程优先级较高，老进程降低优先级可以保证新进程具有优先权)，对于刚进入就绪队列的新进程，往往在创建时已经根据其特点和来了较长时间的等待，一般会根据阻塞队列的不同适当地提高优先级，以改善用则并发执行进程P0和Pl时产生的情况是()。【解析】这是皮特森算法(Peterson’SAlgorithm)的实现，保证进入临界n一个15MB和一个10MB的空闲空间，分配8MB时按最佳适配(BestFit)算法9MB的碎片(空闲空间)，因此最大空闲区为9MB。的个数至少是()。件最大长度是()。31．设置当前工作目录的主要目的是()。不需要由根目录一层一层地解析，在文件路径比较长时，可以节省许多解析的时 ()。线中断的物理设备(注意与陷阱，即软中断有区别)，那么对不同外部设备进行服务是由硬件根据中断的类型(不同外设不同)计算所得，或计算机系统在开机配置，先将键盘扫描码读入键盘缓冲区，再向处理机发出键盘中断，适当的时候(一条指令的末尾或一条原语结束)处理机会响应中断，调用指定服务程序盘缓冲区中的键盘扫描码输入到登录进程中去。如此，最先响应键盘的必然是中断处理程序。本题中，像命令解释器(例如cmd窗口)、系统调用服务和用33．下列选项中，不属于网络体系结构中所描述的内容是()。lMB有链路的数据传输速度相同，因此文件传输经过最短是()。D机发送的ICMP报文件类型是()。最大子网个数、每个子网内的最大可分配地址个数分别是()。38．下列网络设备中，能够抑制广播风暴的是()。互联网的各个机接收到一个将该帧从所有大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是()。中较小的一个，于是此时发送方的发送窗口为min{4000，2000)＝2000字节，乙发用户主机、本地域名服务器发送的域名请求消息数分别为()。NS本向＝(key×3)MOD7，处理冲突采用线性探测再散列法，要求装填(载)因子为。 (1)请画出所构造的散列表。 (2)分别计算等概率情况下查找成功和查找不成功的平均查找长度。：789H(key)O36556O采用线性探测法再散列法处理冲突，所构造的散列表为：012345678关键字789 (2)查找成功时，在等概率情况下，查找表中每个元素的概率是相等的，故查找成功的平均查找长度为(1+1+1+1+3+3+2)/7＝12/7。keyHkey)的值只能是0~6之间，H(key)为0需要比较3次，H(key)为1需要比较2次，H(key)为2需要比较l次，H(key)为3需要比较2次，H(key)为4需要比较l次，H(key)为5需要比较5次，H(key)为6需要比较4次，共7种情况，如下表所示：202244l202244l数所以，在等概率下，查找失败的平均查找长度为：(3+2+1+2+1+5+4)/742．(13分)设将n(n>1)个整数存放到一维数组R中。试设计一个在时RPPn)x1，…,xp-1)。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出 法的时间复杂度和空间复杂度。 (2)用C语言算法描述如下： 法中3个Reverse函数的的时间复杂度分别为O(p/2)、O((p-2)/2)为0(n/2)，故算法的时间复杂度为O(n),算法的空间复杂度为0(1)。采用单字长指令格式，指令各字段定义如下：转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：操作数一(Rn