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.编辑B.编译C.链接D.装载31.某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100S,将缓冲区的数据传送到用户区的时间是50s,CPU对一块数据进行分析的时间为50us。在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是A.1500us、1000sB.1550s、1100sC.1550us、1550sD.2000s、2000s32.有两个并发执行的进程P1和P2,共享初值为1的变量x。P1对x加1，P2对x减1。加1和减1操作的指令序列分别如下所示。/加1操作/减1操作心眼期坐1oad0R1,xd/取到寄存器R1中load R2,xinc R1dec R2store x,R1/将R1的内容存入xstore x,R2中用物合二两个操作完成后，x的值。A.可能为-1或3B.只能为1C.可能为0、1或2D.可能为-1、0、1或233.TCP/P参考模型的网络层提供的是A.无连接不可靠的数据报服务B,无连接可靠的数据报服务C.有连接不可靠的虚电路服务D.有连接可靠的虚电路服务34.若某通信链路的数据传输速率为2400bit/s,采用4相位调制，则该链路的波特率是A.600波特B.1200波特C.4800波特D.9600波特35.数据链路层采用选择重传协议(S)传输数据，发送方已发送了03号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是A.1B.2C.3D.436.下列选项中，对正确接收到的数据帧进行确认的MAC协议是A.CSMAB.CDMAC.CSMA/CDD.CSMA/CA37.某网络拓扑如下图所示，路由器R1只有到达子网192.168.1.0/24的路由。为使R1可以将P分组正确地路由到图中所有的子网，则在R1中需要增加的一条路由（目的网络，子网掩码，下一跳)是RI192.168.1.1192.1681.024R2192.168.1.2192.168.2.025192.168.2.1192.1682.130192.168.212825A.192.168.2.0255.255.255.128192.168.1.1B.192.168.2.0255.255.255.0192.168.1.1C.192.168.2.0255.255.255.128192.168.1.2D.192.168.2.0255.255.255.0192.168.1.238.在子网192.168.4.0/30中，能接收目的地址为192.168.4.3的P分组的最大主机数是119A.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(3)上述程序段涉及带符号整数加/减、无符号整数加/减运算，这四种运算能否利用同一个加法器辅助电路实现？简述理由。(4)计算机内部如何判断带符号整数加减运算的结果是否发生溢出？上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？44.(12分)某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为16MB,主存（物理)地址空间大小为1MB,页面大小为4KB;Cache采用直接映射方式，共8行；主存与Cache之间交换的块大小为32B。系统运行到某一时刻时，页表的部分内容和Cache的部分内容分别如题44(a)图、题44b)图所示，图中页框号及标记字段的内容为十六进制形式。虚页号有效位页框号行号有效位标记006002004052101D310231050一40642B5114D66713227A题44(a)图页表的部分内容题44b)图Cache的部分内容请回答下列问题。(1)虚拟地址共有几位，哪几位表示虚页号？物理地址共有几位，哪几位表示页框号（物理页号）？(2)使用物理地址访问Cache时，物理地址应划分成哪几个字段？要求说明每个字段的位数及在物理地址中的位置。(3)虚拟地址001C60H所在的页面是否在主存中？若在主存中，则该虚拟地址对应的物理地址是什么？访问该地址时是否Cache命中？要求说明理由。(4)假定为该机配置一个4路组相联的TLB共可存放8个页表项，若其当前内容（十六进制）如题44(c)图所示，则此时虚拟地址024BACH所在的页面是否存在主存中？要求说明理由数有效标页框有效今页框有效标页框有效桥页框位记位记号位记号位记0010011500121F10132D0087E0题44(c)图TLB的部分内容45.(8分)某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：cobeginprocess顾客1黄中d中候小09相从取号机获取一个号码：等待叫号：121