2013考研408真题.pdf

8.若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是A.h,c,a,b,d,e,g,fB.e,a,f,g,b,h,c,dC.d,b,c,a,h,e,f,gD.a,b,c,d,h,e,f,g9.下列AOE网表示一项包含8个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是a=31b=8h=935=10A.c和eB.d和cC.f和dD.f和h10.在一棵高度为2的5阶B树中，所含关键字的个数最少是A.5.B.7C.8D.1411.对给定的关键字序列110,119,007,911,114,120,122进行基数排序，则第2趟分配收集后得到的关键字序列是。A.007,110,119,114,911,120,122B.007,110,119,114,911,122,120C.007,110,911,114,119,120,122D.110,120,911,122,114,007,11912.某计算机主频为1.2GHz,其指令分为4类，它们在基准程序中所占比例及CPI如下表所示。指令类型所占比例CPIA50%2B20%3c.10%4D20%5该机的MIPS数是A.100B.200C.400D.60013.某数采用EEE754单精度浮点数格式表示为C6400000H,则该数的值是A.-1.5213B.-1.522C.0.521D.-0.52214.某字长为8位的计算机中，已知整型变量x、y的机器数分别为x=11110100,y#=10110000。若整型变量z=2*x+y/2,则z的机器数为A.11000000B.00100100C.10101010D.溢出15.用海明码对长度为8位的数据进行检/纠错时，若能纠正一位错，则校验位数至少079为A.2B.3C.4D.516.某计算机主存地址空间大小为256MB,按字节编址。虚拟地址空间大小为4GB,采用页式存储管理，页面大小为4KB,TLB(快表)采用全相联映射，有4个页表项，内容如下表所示。有效位标记页框号0FF180H0002H3FFF1H0035H0002FF3H0351H103FFFH0153H则对虚拟地址O3FFF180H进行虚实地址变换的结果是A.0153180HB.0035180HC.TLB缺失D.缺页17.假设变址寄存器R的内容为1000H,指令中的形式地址为2000H:地址1000H中的内容为2000H,地址2000H中的内容为3000H,地址3000H中的内容为4000H,则变址寻址方式下访问到的操作数是A.1000HB.2000HC.3000HD.4000H18.某CPU主频为1.03GHz,采用4级指令流水线，每个流水段的执行需要1个时钟周期。假定CPU执行了100条指令，在其执行过程中，没有发生任何流水线阻塞，此时流水线的吞吐率为。A.0.2510条指令秒B.0.9710条指令/秒C.1.010条指令秒D.1.0310条指令/秒19.下列选项中，用于设备和设备控制器(I/O接口)之间互连的接口标准是A.PCIB.USBC.AGPD.PCI-Express20.下列选项中，用于提高RAD可靠性的措施有I.磁盘镜像.条带化.奇偶校验V.增加Cache机制A.仅I、B.仅I、C.仅I、I和VD.仅、和V21.某磁盘的转速为10000转/分，平均寻道时间是6ms,磁盘传输速率是20MB/s,磁盘控制器延迟为0.2ms,读取一个4KB的扇区所需的平均时间约为A.9msB.9.4msC.12msD.12.4ms22.下列关于中断I/O方式和DMA方式比较的叙述中，错误的是A.中断I/O方式请求的是CPU处理时间，DMA方式请求的是总线使用权B.中断响应发生在一条指令执行结束后，DMA响应发生在一个总线事务完成后C.中断I/O方式下数据传送通过软件完成，DMA方式下数据传送由硬件完成D.中断IVO方式适用于所有外部设备，DMA方式仅适用于快速外部设备23.用户在删除某文件的过程中，操作系统不可能执行的操作是A.删除此文件所在的目录B.删除与此文件关联的目录项C.删除与此文件对应的文件控制块D.释放与此文件关联的内存缓冲区24.为支持CD-ROM中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是A.连续结构B.链式结构C.直接索引结构D.多级索引结构25.用户程序发出磁盘/O请求后，系统的处理流程是：用户程序系统调用处理程序设080备驱动程序中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是A.用户程序B.系统调用处理程序C.设备驱动程序D.中断处理程序26.若某文件系统索引结点(inode)中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是A.索引结点的总数B.间接地址索引的级数C.地址项的个数D.文件块大小27.设系统缓冲区和用户工作区均采用单缓冲，从外设读入1个数据块到系统缓冲区的时间为100，从系统缓冲区读入1个数据块到用户工作区的时间为5，对用户工作区中的1个数据块进行分析的时间为90（如下图所示）。进程从外设读入并分析2个数据块的最短时间是90用户工作区5系统缓冲区100外设A.200B.295C.300D.39028.下列选项中，会导致用户进程从用户态切换到内核态的操作是I.整数除以零.sinO函数调用l.read系统调用A.仅I、B.仅I、C.仅、D.I、和29.计算机开机后，操作系统最终被加载到A.BIOSB.ROMC.EPROMD.RAM30.若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是I.处理越界错.置换页.分配内存A.仅I、B.仅、C.仅I、D.I、和31.某系统正在执行三个进程P1、P2和P3,各进程的计算(CPU)时间和I/O时间比例如下表所示。进程计算时间/O时间PI90%10%P250%50%P315%85%为提高系统资源利用率，合理的进程优先级设置应为A.P1P2P3B.P3P2P1C.P2P1=P3D.P1P2=P332.下列关于银行家算法的叙述中，正确的是A.银行家算法可以预防死锁B.当系统处于安全状态时，系统中一定无死锁进程C.当系统处于不安全状态时，系统中一定会出现死锁进程D.银行家算法破坏了死锁必要条件中的“请求和保持”条件33.在OSI参考模型中，下列功能需由应用层的相邻层实现的是081A.对话管理B.数据格式转换C.路由选择D.可靠数据传输34.若下图为10BasT网卡接收到的信号波形，则该网卡收到的比特串是IA.00110110B.10101101C.01010010D.1100010135.主机甲通过1个路由器（存储转发方式）与主机乙互联，两段链路的数据传输速率均为10Mbps,主机甲分别采用报文交换和分组大小为10kb的分组交换向主机乙发送1个大小为8M(1M=10kb)的报文。若忽略链路传播延迟、分组头开销和分组拆装时间，则两种交换方式完成该报文传输所需的总时间分别为A.800ms、1600msB.801ms、1600msC.1600ms、800msD.1600ms、801ms36.下列介质访问控制方法中，可能发生冲突的是A.CDMAB.CSMAC.TDMAD.FDMA37.HDLC协议对0111110001111110组帧后对应的比特串为A.011111000011111010B.011111000111110101111110C.01111100011111010D.01111100011111100111110138.对于10 OMbps的以太网交换机，当输出端口无排队，以直通交换(cut-through switching)方式转发一个以太网帧（不包括前导码）时，引入的转发延迟至少是】A.0sB.0.48sC.5.12sD.121.44s39.主机甲与主机乙之间已建立一个TCP连接，双方持续有数据传输，且数据无差错与丢失。若甲收到1个来自乙的TCP段，该段的序号为1913、确认序号为2046、有效载荷为100字节，则甲立即发送给乙的TCP段的序号和确认序号分别是A.2046、2012B.2046、2013C.2047、2012D.2047、201340.下列关于SMTP协议的叙述中，正确的是I.只支持传输7比特ASCI码内容.支持在邮件服务器之间发送邮件.支持从用户代理向邮件服务器发送邮件V.支持从邮件服务器向用户代理发送邮件A.仅I、和B.仅I、和VC.仅I、和VD.仅、和V二、综合应用题：第4147小题，共70分。41.(13分)已知一个整数序列A=(a,a,an1),其中0an(0in/2(0pn,1km),则称x为A的主元素。例如A=(0,5,5,3,5,7,5,5),则5为主元素；又如A=(0,5,5,3,5,1,5,7),则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元082素；否则输出-1。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C、C+或Java语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。42.(10分)设包含4个数据元素的集合S=“do”,“for”,“repeat”,“while”,各元素的查找概率依次为：pl=0.35,p2-0.15,p3-0.15,p4-0.35。将S保存在一个长度为4的顺序表中，采用折半查找法，查找成功时的平均查找长度为2.2。请回答：(1)若采用顺序存储结构保存S,且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？(2)若采用链式存储结构保存S,且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？43.(9分)某32位计算机，CPU主频为800MHz,Cache命中时的CPI为4，Cache块大小为32字节；主存采用8体交叉存储方式，每个体的存储字长为32位、存储周期为40s:存储器总线宽度为32位，总线时钟频率为200MHz,支持突发传送总线事务。每次读突发传送总线事务的过程包括：送首地址和命令、存储器准备数据、传送数据。每次突发传送32字节，传送地址或32位数据均需要一个总线时钟周期。请回答下列问题，要求给出理由或计算过程。(1)CPU和总线的时钟周期各为多少？总线的带宽（即最大数据传输率）为多少？(2)Cache缺失时，需要用几个读突发传送总线事务来完成一个主存块的读取？(3)存储器总线完成一次读突发传送总线事务所需的时间是多少？(4)若程序BP执行过程中，共执行了100条指令，平均每条指令需进行1.2次访存，Cache缺失率为5%，不考虑替换等开销，则BP的CPU执行时间是多少？44.(14分)某计算机采用16位定长指令字格式，其CPU中有一个标志寄存器，其中包含进位/借位标志C、零标志ZF和符号标志NP。假定为该机设计了条件转移指令，其格式如下：151110987.000000 C Z N OFFSET其中，00000为操作码OP;C、Z和N分别为CF、ZF和NF的对应检测位，某检测位为1时表示需检测对应标志位，需检测的标志位中只要有一个为1就转移，否则不转移，例如，若C=1,Z-O,N=1,则需检测CF和NP的值，当CF=1或NF=1时发生转移；OFFSET是相对偏移量，用补码表示。转移执行时，转移目标地址为PC)+2+2OFFSET;顺序执行时，下条指令地址为(PC+2。请回答下列问题。(1)该计算机存储器按字节编址还是按字编址？该条件转移指令向后（反向）最多可跳转多少条指令？(2)某条件转移指令的地址为200CH,指令内容如下图所示，若该指令执行时CF=0,ZF-0,NF=1,则该指令执行后PC的值是多少？若该指令执行时CP=1,ZFO,NF-O,则该指令执行后PC的值又是多少？请给出计算过程。15711109800000001111100011(3)实现“无符号数比较小于等于时转移”功能的指令中，C、Z和N应各是什么？(4)以下是该指令对应的数据通路示意图，要求给出图中部件的名称或功能说明。083