2011考研408真题.pdf

2011年全国硕士研究生人学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：140小题，每小题2分，共80分。下列每小题给出的四个选项中，只有一项符合题目要求。（请在答题卡上将所选项的字母涂黑。）1,设是描述问题规模的非负整数，下面程序片段的时间复杂度是81X=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依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素开头的序列个数是。A.3B.4C.5D.63.已知循环队列存储在一维数组A0.n-1中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在AO处，则初始时frot和rear的值分别是A.0,0B.0,n-1C.n-1,0D.n-1,n-14.若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是A.257.B.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.18967.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是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,回路是简单路径.存储稀疏图，用邻接矩阵比邻接表更省空间.若有向图中存在拓扑序列，则该图不存在回路A,仅B.仅I、C.仅D.仅I、9.为提高散列(Hash)表的查找效率，可以采取的正确措施是I.增大装填（载）因子，设计冲突（碰撞）少的散列函数.处理冲突（碰撞）时避免产生聚集（堆积）现象A,仅IB.仅C.仅I、D.仅、10.为实现快速排序算法，待排序序列宜采用的存储方式是A.顺序存储B.散列存储C.链式存储D.索引存储11.已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是A.1B.2C.4D.512.下列选项中，描述浮点数操作速度指标的是A.MIPSB.CPIC.IPCD.MFLOPS13.f1oat型数据通常用EEE754单精度浮点数格式表示。若编译器将float型变量x分配到一个32位浮点寄存器FR1中，且x=-8.25,则FR1的内容是A.C1040000HB.C2420000HC.C1840000HD.C1C20000H14.下列各类存储器中，不采用随机存取方式的是A.EPROMB.CDROMC.DRAMD.SRAM15.某计算机存储器按字节编址，主存地址空间大小为64MB,现用4MB8位的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是A.22位B.23位C.25位D.26位16.偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是A.间接寻址B.基址寻址C.相对寻址D.变址寻址17.某机器有一个标志寄存器，其中有进位/借位标志C、零标志ZF、符号标志SF和溢出标志OF,条件转移指令bgt(无符号整数比较大于时转移)的转移条件是A.CF+OF=1 B.SF+ZF=1 C.CF+ZF=1D.CF+SF=118.下列给出的指令系统特点中，有利于实现指令流水线的是I,指令格式规整且长度一致.指令和数据按边界对齐存放.只有Load/Store指令才能对操作数进行存储访问A.仅I、B.仅、C.仅I、D.I、l9.假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是A.每个指令周期中CPU都至少访问内存一次B.每个指令周期一定大于或等于一个CPU时钟周期C.空操作指令的指令周期中任何寄存器的内容都不会被改变D.当前程序在每条指令执行结束时都可能被外部中断打断20.在系统总线的数据线上，不可能传输的是A.指令B.操作数C.握手（应答）信号D.中断类型号21.某计算机有五级中断L4Lo,中断屏蔽字为M4M,M2M1Mo,M=1(0i4)表示对L级中断进行屏蔽。若中断响应优先级从高到低的顺序是L4L。L2L1L3,则L,的中断处理程117序中设置的中断屏蔽字是A.11110B.01101C.00011D.0101022.某计算机处理器主频为50MHz,采用定时查询方式控制设备A的I/O,查询程序运行一次所用的时钟周期数至少为500。在设备A工作期间，为保证数据不丢失，每秒需对其查询至少200次，则CPU用于设备A的IVO的时间占整个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请求后，系统的正确处理流程是0A.用户程序系统调用处理程序中断处理程序设备驱动程序B.用户程序系统调用处理程序设备驱动程序中断处理程序C.用户程序设备驱动程序系统调用处理程序中断处理程序D.用户程序设备驱动程序中断处理程序系统调用处理程序27.某时刻进程的资源使用情况如下表所示。已分配资源尚需分配可用资源进程R1R2R3R1R2R3R1R2R3P1200001P21201w202P301P400200此时的安全序列是A.P1,P2,P3,P4B.P1,P3,P2,P4C.P1,P4,P3,P2D.不存在的28.在缺页处理过程中，操作系统执行的操作可能是I,修改页表.磁盘I/O.分配页框A,仅I、B.仅C.仅D.I、和29.当系统发生抖动(thrashing)时，可以采取的有效措施是I.撤销部分进程.增加磁盘交换区的容量.提高用户进程的优先级A,仅IB.仅C.仅D.仅I、30.在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段118A.0B.1C.2D.439.主机甲向主机乙发送一个(SYN=1,sq-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段，分别包含300B、400B和500B的有效载荷，第3个段的序号为900。若主机乙仅正确接收到第1和第3个段，则主机乙发送给主机甲的确认序号是一。A.300B.500C.1200D.1400二、综合应用题：第4147小题，共70分。请将答案写在答题纸指定位置上。41.(8分)已知有6个顶点（顶点编号为05）的有向带权图G,其邻接矩阵A为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。46o54333要求：(1)写出图G的邻接矩阵A。(2)画出有向带权图G。(3)求图G的关键路径，并计算该关键路径的长度。42.(15分)一个长度为L(L1)的升序序列S,处在第L21个位置的数称为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程序段：unsigned int x=134;unsigned int y=246;int m=x;int ney;unsigned int z1=x-y;unsigned int z2-x+y;int kl=m-n;int k2=m+n;若编译器编译时将8个8位寄存器R1一R8分别分配给变量x、y、m、n、z1、z2、k1和k2。请回答下列问题。（提示：带符号整数用补码表示。）(1)执行上述程序段后，寄存器R1、R5和R6的内容分别是什么（用十六进制表示）？(2)执行上述程序段后，变量m和k1的值分别是多少（用十进制表示）？120