2011年真题答案与解析计算机

1/27万学海文钻石卡试题：2011年考研真题及答案解析之计算机万学海文2011年全国硕士研究生入学考试计算机科学与技术入学考试试题一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。请在答题卡上将所选项的字母涂黑。1．设n是描述问题规模的非负整数，下面程序片段的时间复杂度是x=2;while(xn/2)x=2*x;A．O(log2n)B．O(n)C．O(nlog2n)D．O(n2)2．元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是A．3B．4C．5D．63．已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是A．0,0B．0,n-1C．n-1,0D．n-1,n-14．若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是A．257B．258C．384D．3855．若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不．会是A．1,2,3,4B．2,3,4,1C．3,2,4,1D．4,3,2,16．已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是A．115B．116C．1895D．18962/277．对于下列关键字序列，不．可能构成某二叉排序树中一条查找路径的序列是A．95,22,91,24,94,71B．92,20,91,34,88,35C．21,89,77,29,36,38D．12,25,71,68,33,348．下列关于图的叙述中，正确的是I．回路是简单路径II．存储稀疏图，用邻接矩阵比邻接表更省空间III．若有向图中存在拓扑序列，则该图不存在回路A．仅IIB．仅I、IIC．仅IIID．仅I、III9．为提高散列（Hash）表的查找效率，可以采取的正确措施是I．增大装填（载）因子II．设计冲突（碰撞）少的散列函数III．处理冲突（碰撞）时避免产生聚集（堆积）现象A．仅IB．仅IIC．仅I、IID．仅II、III10．为实现快速排序算法，待排序序列宜采用的存储方式是A．顺序存储B．散列存储C．链式存储D．索引存储11．已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是A．1B．2C．4D．512．下列选项中，描述浮点数操作速度指标的是A．MIPSB．CPIC．IPCD．MFLOPS13．float型数据通常用IEEE754单精度浮点数格式表示。若编译器将float型变量x分配在一个32位浮点寄存器FR1中，且x=-8.25，则FR1的内容是A．C1040000HB．C2420000HC．C1840000HD．C1C20000H14．下列各类存储器中，不．采用随机存取方式的是3/27A．EPROMB．CDROMC．DRAMD．SRAM15．某计算机存储器按字节编址，主存地址空间大小为64MB，现用4M×8位的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是A．22位B．23位C．25位D．26位16．偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不．属于偏移寻址方式的是A．间接寻址B．基址寻址C．相对寻址D．变址寻址17．某机器有一个标志寄存器，其中有进位/借位标志CF、零标志ZF、符号标志SF和溢出标志OF，条件转移指令bgt（无符号整数比较大于时转移）的转移条件是A．CF+OF＝1B．SF+ZF＝1C．CF+ZF＝1D．CF+SF＝118．下列给出的指令系统特点中，有利于实现指令流水线的是I．指令格式规整且长度一致II．指令和数据按边界对齐存放III．只有Load/Store指令才能对操作数进行存储访问A．仅I、IIB．仅II、IIIC．仅I、IIID．I、II、III19．假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误．．的是A．每个指令周期中CPU都至少访问内存一次B．每个指令周期一定大于或等于一个CPU时钟周期C．空操作指令的指令周期中任何寄存器的内容都不会被改变D．当前程序在每条指令执行结束时都可能被外部中断打断20．在系统总线的数据线上，不．可能传输的是A．指令B．操作数C．握手（应答）信号D．中断类型号21．某计算机有五级中断L4~L0，中断屏蔽字为M4M3M2M1M0，Mi=1（0≤i≤4）表示对Li级中断进行屏蔽。若中断响应优先级从高到低的顺序是L0→L14/27→L2→L3→L4，且要求中断处理优先级从高到低的顺序为L4→L0→L2→L1→L3，则L1的中断处理程序中设置的中断屏蔽字是A．11110B．01101C．00011D．0101022．某计算机处理器主频为50MHz，采用定时查询方式控制设备A的I/O，查询程序运行一次所用的时钟周期数至少为500。在设备A工作期间，为保证数据不丢失，每秒需对其查询至少200次，则CPU用于设备A的I/O的时间占整个CPU时间的百分比至少是A．0.02%B．0.05%C．0.20%D．0.50%23．下列选项中，满足短任务优先且不．会发生饥饿现象的调度算法是A．先来先服务B．高响应比优先C．时间片轮转D．非抢占式短任务优先24．下列选项中，在用户态执行的是A．命令解释程序B．缺页处理程序C．进程调度程序D．时钟中断处理程序25．在支持多线程的系统中，进程P创建的若干个线程不．能共享的是A．进程P的代码段B．进程P中打开的文件C．进程P的全局变量D．进程P中某线程的栈指针26．用户程序发出磁盘I/O请求后，系统的正确处理流程是A．用户程序→系统调用处理程序→中断处理程序→设备驱动程序B．用户程序→系统调用处理程序→设备驱动程序→中断处理程序C．用户程序→设备驱动程序→系统调用处理程序→中断处理程序D．用户程序→设备驱动程序→中断处理程序→系统调用处理程序27．某时刻进程的资源使用情况如下表所示。进程已分配资源尚需资源可用资源R1R2R3R1R2R3R1R2R35/27P1200001021P2120132P3011131P4001200此时的安全序列是A．P1,P2,P3,P4B．P1,P3,P2,P4C．P1,P4,P3,P2D．不存在28．在缺页处理过程中，操作系统执行的操作可能是I．修改页表II．磁盘I/OIII．分配页框A．仅I、IIB．仅IIC．仅IIID．I、II和III29．当系统发生抖动（thrashing）时，可以采取的有效措施是I．撤销部分进程II．增加磁盘交换区的容量III．提高用户进程的优先级A．仅IB．仅IIC．仅IIID．仅I、II30．在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是A．编辑B．编译C．链接D．装载31．某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100μs，将缓冲区的数据传送到用户区的时间是50μs，CPU对一块数据进行分析的时间为50μs。在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是A．1500μs、1000μsB．1550μs、1100μsC．1550μs、1550μsD．2000μs、2000μs6/2732．有两个并发执行的进程P1和P2，共享初值为1的变量x。P1对x加1，P2对x减1。加1和减1操作的指令序列分别如下所示。//加1操作loadR1,x//取x到寄存器R1中incR1storex,R1//将R1的内容存入x//减1操作loadR2,xdecR2storex,R2两个操作完成后，x的值A．可能为-1或3B．只能为1C．可能为0、1或2D．可能为-1、0、1或233．TCP/IP参考模型的网络层提供的是A．无连接不可靠的数据报服务B．无连接可靠的数据报服务C．有连接不可靠的虚电路服务D．有连接可靠的虚电路服务34．若某通信链路的数据传输速率为2400bps，采用4相位调制，则该链路的波特率是A．600波特B．1200波特C．4800波特D．9600波特35．数据链路层采用选择重传协议（SR）传输数据，发送方已发送了0~3号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是A．1B．2C．3D．436．下列选项中，对正确接收到的数据帧进行确认的MAC协议是A．CSMAB．CDMAC．CSMA/CDD．CSMA/CA37．某网络拓扑如下图所示，路由器R1只有到达子网192.168.1.0/24的路由。为使R1可以将IP分组正确地路由到图中所有子网，则在R1中需要增加的一条路由（目的网络，子网掩码，下一跳）是7/27192.168.1.0/24192.168.1.0/24192.168.1.1192.168.1.2192.168.2.0/25192.168.2.0/25192.168.2.130192.168.2.128/25192.168.2.128/25192.168.2.1R1R2A．192.168.2.0，255.255.255.128，192.168.1.1B．192.168.2.0，255.255.255.0，192.168.1.1C．192.168.2.0，255.255.255.128，192.168.1.2D．192.168.2.0，255.255.255.0，192.168.1.238．在子网192.168.4.0/30中，能接收目的地址为192.168.4.3的IP分组的最大主机数是A．0B．1C．2D．439．主机甲向主机乙发送一个(SYN=1,seq=11220)的TCP段，期望与主机乙建立TCP连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的TCP段可能是A．(SYN=0,ACK=0,seq=11221,ack=11221)B．(SYN=1,ACK=1,seq=11220,ack=11220)C．(SYN=1,ACK=1,seq=11221,ack=11221)D．(SYN=0,ACK=0,seq=11220,ack=11220)40．主机甲与主机乙之间已建立一个TCP连接，主机甲向主机乙发送了3个连续的TCP段，分别包含300字节、400字节和500字节的有效载荷，第3个段的序号为900。若主机乙仅正确接收到第1和第3个段，则主机乙发送给主机甲的确认序号是8/27A．300B．500C．1200D．1400二、综合应用题：41～47小题，共70分。请将答案写在答题纸指定位置上。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个位置的数称为S的中位数。例如，若序列S1=(11,13,15,17,19)，则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2,4,6,8,20)，则S1和S2的中位数是11。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。43．（11分）假定在一个8位字长的计算机中运行如下类C程序段：unsignedintx=134;unsignedint