2011考研408真题答案.pdf

2011年计算机学科专业基础综合试题参考答案一、单项选择题1.2.B3.B4.5.6.D1A8.DQ9.10.A11B12.D13.A14.B15.D16.17.c18.D19c20.21.D22.23.B24.A25.D26.B27.D28.D29.A30.C31.B32.c33.A34.B35.B36.D37.D38.C39.C40.1.解析：在程序中，执行频率最高的语句为“x=2*x”。设该语句共执行了Tn)次，则2T1n2,故T(n)=log2(n/2)-1=log2n-2,得Tn-0(1og2n)。2.解析：d为第1个出栈元素，则d之前的元素必定是进栈后在栈中停留，因而出栈顺序必为dcba,e的顺序不定，在任一“”上都有可能，一共有4种可能。【另解】d首先出栈，则abc停留在栈中，此时栈的状态如下图所示。此时可以有如下4种操作：e进栈后出栈，则出栈序列为decba;c出栈，e进栈后出栈，出栈序列为dceba;cb出栈，e进栈后出栈，出栈序列为dcbea:cba出栈，e进栈后出栈，出栈序列为dcbae。3.解析：根据题意，第一个元素进入队列后存储在AO处，此时front和rear值都为0。入队时由于要执行(rear+1)%n操作，所以如果入队后指针指向0，则rear初值为n-l,而由于第一个元素在AO中，插入操作只改变rear指针，所以front为0不变。注意：循环队列是指顺序存储的队列，而不是指逻辑上的循环，如循环单链表表示的队列不能称为循环队列。front和rear的初值并不是固定的。【排除法】如果front和rear的初值相等，则无法判断队列空和队列满，排除A、D。第1个进入队列的元素存储在AO处，进队操作不会改变ot的值，由题意可知队列非空时front指向队头元素，故front初值为O,只能选B。4.解析：根据完全二叉树的性质，最后一个分支结点的序号为27682=384，故叶子结点的个数为768-384-384。【另解1】由二叉树的性质nn+n+n2和nn2+1可知，n=2n0-1+n1,及2n0-1+n1=768,显然n1=1,2n0=768,则n0=384。124径；回路显然不是简单路径，故I错误；稀疏图是边比较少的情况，此时用邻接矩阵的空间复杂度为O,必将浪费大量的空间，而邻接表的空间复杂度为O+e),应该选用邻接表，故错误。存在回路的有向图不存在拓扑序列，若拓扑排序输出结束后所余下的顶点都有前驱，则说明只得到了部分顶点的拓扑有序序列，图中存在回路，故正确。9.解析：Hsh表的查找效率取决于散列函数、处理冲突的方法和装填因子。显然，冲突的产生概率与装填因子（表中记录数与表长之比）的大小成正比，即装填得越满越容易发生冲突，I错误。显然正确。采用合适的处理冲突的方式避免产生聚集现象，也将提高查找效率，例如用拉链法解决冲突时就不存在聚集现象，用线性探测法解决冲突时易引起聚集现象，正确。10.解析：对绝大部分内部排序而言，只适用于顺序存储结构。快速排序在排序的过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。11.解析：插入18后，首先18与10比较，交换位置，再18与25比较，不交换位置。共比较了2次，调整的过程如下图所示。25插入结点1825筛选结点10251筛选结点252513101310131813189189(9012.解析：MPS是每秒执行多少百万条指令，适用于衡量标量机的性能。CPI是平均每条指令的时钟周期数。IPC是CPI的倒数，即每个时钟周期执行的指令数。MFLOPS是每秒执行多少百万条浮点数运算，用来描述浮点数运算速度，适用于衡量向量机的性能。13.解析：本题题意即考查IEEE754单精度浮点数的表示。先将x转换成二进制为-1000.01=-1.0000123,其次计算阶码E,根据EEE754单精度浮点数格式，有E-127=3,故E=130,转换成二进制为10000010。最后，根据EEE754标准，最高位的“1”是被隐藏的。IEEE754单精度浮点数格式：数符(1位)+阶码(8位)+尾数(23位)。故，FR1内容为1；10000010：000010000000000000000000.即，11000001000001000000000000000000-C104000H。本题易误选D,未考虑EEE754标准隐含最高位1的情况，偏置值是128。14.解析：随机存取方式是指CPU可以对存储器的任一存储单元中的内容随机存取，而且存取时间与存储单元的物理位置无关。选项A、C、D均采用随机存取方式，CDROM即光盘，采用串行存取方式。注意：CDROM是只读型光盘存储器，而不属于只读存储器(ROM)。15.解析：主存按字节编址，地址空间大小为64MB,MAR的寻址范围为64M-226,故为26位。实际的主存容量32MB不能代表MAR的位数，考虑到存储器扩展的需要，MAR应保证访问到整个主126存地址空间，反过来，MAR的位数决定了主存地址空间的大小。16.解析：间接寻址不需要寄存器，EA=(A)。基址寻址EA=A+基址寄存器BR内容；相对寻址EA=A+程序计数器PC内容：变址寻址EA=A+变址寄存器X内容。后三者都是将某个寄存器内容与一个形式地址相加而形成有效地址，故选A。17.解析：假设两个无符号整数A和B,bgt指令会将A和B进行比较，也就是将A和B相减。如果AB,则A-B肯定无进位/借位，也不为0（为0时表示两数相同），故而CF和ZF均为0，选C。其余选项中用到了符号标志SF和溢出标志OF,显然应当排除。18.解析：指令定长、对齐、仅Load/Store指令访存，以上3个都是RISC的特征，指令格式规整且长度一致能大大简化指令译码的复杂度，有利于实现流水线。指令和数据按边界对齐存放能保证在一个存取周期内取到需要的数据和指令，不用多余的延迟等待，也有利于实现流水线。只有Load/Store指令才能对操作数进行存储访问使取指令、取操作数操作简化且时间长度固定，能够有效地简化流水线的复杂度。19.解析：由于不采用指令预取技术，每个指令周期都需要取指令，而不采用Cache技术，则每次取指令都至少要访问内存一次（当指令字长与存储字长相等且按边界对齐时），A正确。时钟周期是CPU的最小时间单位，每个指令周期一定大于或等于一个CPU时钟周期，B正确。即使是空操作指令，在取指操作后，PC也会自动加1，C错误。由于机器处于“开中断”状态，在每条指令执行结束时都可能被外部中断打断。20.解析：在取指令时，指令便是在数据线上传输的。操作数显然在数据线上传输。中断类型号用以指出中断向量的地址，CPU响应中断请求后，将中断应答信号(NTR)发回到数据总线上，CPU从数据总线上读取中断类型号后，查找中断向量表，找到相应的中断处理程序入口。而握手（应答)信号属于通信联络控制信号，应在通信总线上传输。21.解析：高优先级置0表示可被中断，比该中断优先级低（或相等）的置1表示不可被中断，L,只能屏蔽L3和其自身，故M3和M1置1，中断屏蔽字MMM2MMo=01010。22.解析：每秒至少查询200次，每次查询至少500个时钟周期，总的时钟周期数为200 x500=100000,因此CPU用于设备A的IVO的时间占CPU时间比为10000050M-0.20%。23.解析：高响应比优先算法是一种综合考虑任务长度和等待时间的调度算法，响应比（等待时间+执行时间)/执行时间。高响应比优先算法在等待时间相同的情况下，作业执行时间越短则响应比越高，满足短任务优先。随着长任务的等待时间增加，响应比也会变大，执行机会也就增大，所以不会发生饥饿现象。先来先服务和时间片轮转不符合短任务优先，非抢占式短任务优先会产生饥饿现象24.解析：缺页处理和时钟中断都属于中断，在核心态执行；进程调度是操作系统内核进程，无需用户干预，在核心态执行；命令解释程序属于命令接口，是四个选项中唯一能面对用户的，它在用户127态执行。25.解析：进程是资源分配的基本单位，线程是处理机调度的基本单位。因此，进程的代码段、进程打开的文件、进程的全局变量等都是进程的资源，唯有进程中某线程的栈指针是属于线程的，属于进程的资源可以共享，属于线程的栈是独享的，对其他线程透明。26.解析：输入输出软件一般从上到下分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。与设备无关的软件层也就是系统调用的处理程序。当用户使用设备时，首先在用户程序中发起一次系统调用，操作系统的内核接到该调用请求后请求调用处理程序进行处理，再转到相应的设备驱动程序，当设备准备好或所需数据到达后设备硬件发出中断，将数据按上述调用顺序逆向回传到用户程序中。27.解析：本题应采用排除法，逐个代入分析。当剩余资源分配给P1,待P1执行完后，可用资源数为(2,2,1),此时仅能满足P4的需求，排除AB:接着分配给P4,待P4执行完后，可用资源数为(2,2,2)，此时已无法满足任何进程的需求，排除C。此外，本题还可以使用银行家算法求解（对于选择题来说，显得过于复杂）。28.解析：缺页中断产生后，需要在内存中找到空闲页框并分配给需要访问的页（可能涉及到页面置换)，之后缺页中断处理程序调用设备驱动程序做磁盘/O,将位于外存上的页面调入内存，调入后需要修改页表，将页表中代表该页是否在内存的标志位（或有效位）置为1，并将物理页框号填入相应位置，若必要还需修改其他相关表项等。29.解析：在具有对换功能的操作系统中，通常把外存分为文件区和对换区。前者用于存放文件，后者用于存放从内存换出的进程。抖动现象是指刚刚被换出的页很快又要被访问，为此又要换出其他页，而该页又很快被访问，如此频繁地置换页面，以致大部分时间都花在页面置换上，引起系统性能下降。撤销部分进程可以减少所要用到的页面数，防止抖动。对换区大小和进程优先级都与抖动无关。30.解析：编译后的模块需要经过链接才能装载，而链接后形成的地址才是整个程序的完整逻辑地址空间。以C语言为例：C语言经过预处理(cpp)编译(ccl)汇编(as)链接(ld)产生可执行文件。其中链接的前一步，产生了可重定位的二进制的目标文件。C语言采用源文件独立编译的方法，如程序main.c,filel.c,file2.c,filel.h,file2.h,在链接的前一步生成了main.o,filel.o,fle2.o,这些目标模块采用的逻辑地址都从0开始，但只是相对于该模块的逻辑地址。链接器将这三个文件，b和其他的库文件链接成一个可执行文件。链接阶段主要完成了重定位，形成整个程序的完整逻辑地址空间。例如，ilel.0的逻辑地址为01023，main.0的逻辑地址为01023，假设链接时将f6lel.0链接在main.o之后，则重定位之后ilel.o对应的逻辑地址就应为10242047。这一题有不少同学会对C选项有疑问，认为产生逻辑地址的阶段是链接，下面引入一个线性地址的概念来解释为什么链接是不对的。为了区分各种不同的地址，下面也把逻辑地址和物理地址一并介绍。逻辑地址(Logical Address)是指在程序各个模块中的偏移地址。它是相对于当前模块首址128的地址。线性地址(Linear Address)是指在分页式存储管理中单个程序所有模块集合在一起构成的地址，即可以理解为操作系统联考复习指导一书中的全局的逻辑地址。物理地址(Physical Address)是指出现在CPU外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果地址。它实际上就是物理内存真正的地址。线性地址的概念在很多操作系统书中并不涉及，在这里引入只是为了把这题解释清楚。选择C选项的同学应该是把题目所说的逻辑地址当成了线性地址。实际上，很多书中也不会把这线性地址和逻辑地址区分得那么清楚，而统一的称为逻辑地址，这就导致了这题的错误选择。总之，在这题中，逻辑地址指的就是段内的偏移量而不是链接后生成的整个程序全局的逻辑地址空间，所以逻辑地址是编译时产生的。编者在查相关资料的过程中看到了关于这个问题的很多不一样的说法，这也是操作系统这门课的一个“特色”，所以这里综合了各个说法，并给出了一个觉得相对合理的解释，读者不必过多纠结，实际考试碰上这种问题的概率还是很低的。31.解析：在单缓冲区中，当上一个磁盘块从缓冲区读入用户区完成时，下一磁盘块才能开始读入，也就是当最后一块磁盘块读入用户区完毕时所用时间为15010=1500s,加上处理最后一个磁盘块的时间50s,得1550s。双缓冲区中，不存在等待磁盘块从缓冲区读入用户区的问题，10个磁盘块可以连续从外存读入主存缓冲区，加上将最后一个磁盘块从缓冲区送到用户区的传输时间50s以及处理时间50s,也就是10010+50+50=1100us。32.解析：将P1中3条语句依次编号为1、2、3：P2中3条语句依次编号为4、5、6。则依次执行1、2、3、4、5、6得结果1，依次执行1、2、4、.5、6、3得结果2，执行4、5、1、2、3、6得结果0。结果-1不可能得出。33.解析：TCP/P的网络层向上只提供简单灵活的、无连接的、尽最大努力交付的数据报服务。考查P首部，如果是面向连接的，则应有用于建立连接的字段，但是没有：如果提供可靠的服务，则至少应有序号和校验和两个字段，但是P分组头中也没有(P首部中只是首部校验和)。通常有连接、可靠的应用是由运输层的TCP实现的。34.解析：波特率B与数据传输率C的关系：C-B1og2N,N为一个码元所取的离散值个数。采用4种相位，也即可以表示4种变化，故一个码元可携带1og24-2bit信息，则该链路的波特率=比特率/2=1200波特。35.解析：在选择重传协议中，接收方逐个地确认正确接收的分组，不管接收到的分组是否有序，只要正确接收就发送选择ACK分组进行确认。因此选择重传协议中的ACK分组不再具有累积确认的作用，要特别注意其与GBN协议的区别。本题中只收到1号帧的确认，0、2号帧超时，由于对于1号帧的确认不具累积确认的作用，因此发送方认为接收方没有收到0、2号帧，于是重传这两帧。因为3号帧计时器并无超时，所以暂时不用重传3号帧。36.解析：CSMA/CA是无线局域网标准802.11中的协议，它在CSMA的基础上增加了冲突避免的功能。ACK帧是CSMA/CA避免冲突的机制之一，也就是说，只有当发送方收到接收方发回的ACK帧后才确认发出的数据帧己正确到达目的地。【排除法】首先CDMA即码分多址，是物理层的内容；CSMA/CD即带冲突检测的载波监听129