1、2009年计算机学科专业基础综合试题参考答案一、单项选择题1.Bc2.3.D4.B5.C6.B1.A8.D9.10.B11.C12.D13.D14.15.D16.17.A18.A19.D20.B21.D22A23.D24.D25.26.A27.C28.B29.A30.A31.B32.A33.B34.B35.C36.A37.D38.D39.C40.A1.解析：缓冲区的概念出现在操作系统的设备管理中，其特点是先进先出。缓冲区的作用是解决主机与打印机之间速度不匹配的问题，而不应改变打印数据的顺序。若用栈，先进入缓冲区的数据则要排队到最后才能打印，显然不符题意，故选B。2.解析：由于队列的特点是先进先
2、出，即栈S的出栈顺序就是队Q的出队顺序。故本题只需注意栈的特点是先进后出。出入栈的详细过程见下表。序号说明栈内栈外序号说明栈内栈外1a入栈a8c入栈aebde2b入栈%9f入栈aefbde3b出栈ab10f出栈aebdcfc入栈acbe出栈abdefed入栈acdb12a出栈bdcfea6d出栈acbd13g入栈bdcfea7c出栈bde14g出栈bdcfeag栈内的最大深度为3，故栈S的容量至少是3。【另解】元素的出栈顺序是b,d,c,，e,a,g,可推出进栈出栈顺序为Push(S,a),Push(S,b),Pop(S,b),Push(S,c),Push(S,d),Pop(S,d),Pop(
3、S,c),Push(S,e),Push(S,f),Pop(S,f),Pop(S,e),Pop(S,a),Push(S,g),Pop(S,g)。假设初始所需容量为0，每做一次Push进行一次“+1”操作，每做一次Pop进行一次“-1”操作，记录容量的最大值为3，所以选C。3.解析：分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即遍历的方式是NL。本题考查的遍历方法并不是二叉树的3种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。4.解析：根据平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过1。而其余3个选项均可以找到不符合该条件的结点。在做题的过程
4、中，如果答案不太明显，可以把每个非叶结点的平衡因子都写出来再进行判断。1625.解析：完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第6层有叶结点则完全二叉树的高度可能为6或7，显然树高为7时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了82=16个叶结点，故完全二叉树的结点个数最多为(2？-1)-16=111个结点。6.解析：森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。情形I:若结点v是结点u的第二个孩子结点，在转换时，结点v
5、就变成结点u第一个孩子的右孩子，符合要求。情形：结点u和v是兄弟结点的关系，但二者之中还有一个兄弟结点k,则转换后，结点V就变为结点k的右孩子，而结点k则是结点山的右孩子，符合要求。OO图1图情形：若结点的父结点与v的父结点是兄弟关系，则转换后，结点u和v分别在两者最左父结点的两棵子树中，不可能出现在同一条路径中。233图【逆向法】由题意可知u是的父结点的父结点，如下图所示有4种情况：(1)(4)根据树与二叉树的转换规则，将这4种情况转换成树种结点的关系。(1)在原来的树中u是的父结点的父结点：(2)在树中u是v的父结点；(3)在树中u是v的父结点的兄弟；(4)在树中u与v是兄弟关系。由此可知
6、I和正确。7.解析：每条边都连接了两个结点，在计算顶点的度之和时每条边都被计算了两次（出度和入度），故所有顶点的度之和为边数的两倍，I正确。n个顶点、n-1条边可以构成无向连通图，比如树，错误。顶点数为N(N21)的无向完全图中不存在度为1的顶点，错误。8.解析：选项A、B和C都是B-树的特点，而选项D则是B+树的特点。注意区别B-树和B+树各自163第四步：判溢出。阶码符号位为01，说明发生溢出。本题容易误选选项B、C,这是因为选项B、C本身并没有计算错误，只是它们不是最终结果，选项B少了第3第4步，选项C少了第4步。【偷懒法】本题也可以直接用数学知识对原数进行计算，然后将计算的结果转换成浮
7、点数的格式。X+Y=29/3227+5/825=29/3227+5/3227-(29/32+5/32)27=34/3227=17/3228,阶码用补码表示，数值位3位，最大只能表示7，即X+Y的结果的阶码8超出了该浮点数的表示范围，故溢出。“你在做题时有想到这种方法么？”14.解析：由于Cache共有16块，采用2路组相联，因此共分为8组，组号为0、1、2、7。主存的某一字块按模8映射到Cache某组的任一字块中，即主存的第0,8，l6字块可以映射到Cache第0组的任一字块中。每个主存块大小为32字节，故129号单元位于第4块主存块（注意是从0开始)，因此将映射到Cache第4组的任一字块中
8、。15.解析：首先确定ROM的个数，ROM区为4KB,选用2KX8位的ROM芯片，需要4Kx8=2片，2K8采用字扩展方式：RAM区为60KB,选用4KX4位的RAM芯片，需要6OK8=30片，采用字4K4和位同时扩展方式。16.解析：相对寻址EA=(PC)十A,首先要求的是取指令后PC的值。转移指令由两个字节组成，每取一个字节PC值自动加1，因此取指令后PC值为2000H+2H=2002H,故EA=(PC)十A=2002H+06H=2008H。【易错点】本题易误选A或B。选项A没有考虑PC值的自动更新，选项B虽然考虑了PC值要自动更新，但没有注意到该转移指令是一条两字节指令，P值仅仅“+1”
9、而不是“+2”。17.解析：相对于CISC,RISC的特点是指令条数少；指令长度固定，指令格式和寻址种类少；只有取数/存数指令访问存储器，其余指令的操作均在寄存器之间进行：CPU中通用寄存器多；大部分指令在一个或者小于一个机器周期内完成；以硬布线逻辑为主，不用或者少用微程序控制。选项B、C、D都是RISC的特点，选项A是错误的，因为RISC的速度快，所以普遍采用硬布线控制器，而非微程序控制器。18.解析：流水线的时钟周期应以最长的执行时间为准，否则用时长的流水段的功能将不能正确完成。19.解析：微程序控制器采用了“存储程序”的原理，每条机器指令对应一个微程序，因此修改和扩充容易，灵活性好，但每
10、条指令的执行都要访问控制存储器，所以速度慢。硬布线控制器采用专门的逻辑电路实现，其速度主要取决于逻辑电路的延迟，因此速度快，但修改和扩展困难，灵活性差。20.解析：总线带宽是指单位时间内总线上传输数据的位数，通常用每秒钟传送信息的字节数来衡量，单位Bs。由题意可知，在1个总线周期(=2个时钟周期)内传输了4字节信息，时钟周期=1/10MHz0.1s,故总线带宽为4B/(20.1s)=4B/(0.2106s)=20MB/s。21.解析：165建立符号链接时，引用计数值直接复制：建立硬链接时，引用计数值加1。删除文件时，删除操作对于符号链接是不可见的，这并不影响文件系统，当以后再通过符号链接访问时
11、，发现文件不存在，直接删除符号链接；但对于硬链接则不可以直接删除，引用计数值减1，若值不为0，则不能删除此文件，因为还有其他硬链接指向此文件。当建立F2时，F1和F2的引用计数值都为1。当再建立F3时，F1和F3的引用计数值就都变成了2。当后来删除F1时，F3的引用计数值为2-1=1，F2的引用计数值一直不变。32.解析：设备管理具有设备独立性的特点，操作系统以系统调用方式来请求某类设备时，使用的是逻辑设备名。而在程序实际执行时，将逻辑设备名转换为对应的物理设备名。33.解析：传输层提供应用进程间的逻辑通信（通过端口号），即端到端的通信。而数据链路层负责相邻结点之间的通信，这个结点包括了交换机
12、和路由器等数据通信设备，这些设备不能称为端系统。网络层负责主机到主机的逻辑通信。因此选B。34.解析：采用4个相位，每个相位有4种幅度的QAM调制方法，每个信号可以有16种变化，传输4bit的数据。根据奈奎斯特定理，信息的最大传输速率为23k4-24kbps。35.解析：在后退N帧协议中，当接收方检测到某个帧出错后，则简单地丢弃该帧及其后所有的后续帧，发送方超时后需重传该数据帧及其后续的所有帧。这里应注意，连续ARQ协议中，接收方一般采用累积确认的方式，即接收方对按序到达的最后一个分组发送确认，因此本题中收到3的确认帧就表示编号为0、1、2、3的帧已接收，而此时发送方未收到1号帧的确认只能代表
13、确认帧在返回的过程中丢失了，而不代表1号帧未到达接收方。因此需要重传的帧为编号是4、5、6、7的帧。36.解析：交换机实质上是一个多端口网桥，工作在数据链路层，数据链路层使用物理地址进行转发而转发到目的地通常是使用目的地址。因此PDU地址是目的物理地址。37.解析：若最短帧长减少，而数据传输速率不变，则需要使冲突域的最大距离变短来实现碰撞窗口的减少。碰撞窗口是指网络中收发结点间的往返时延，因此假设需要减少的最小距离为S,则可以得到如下公式（注意单位的转换）：减少的往返时延=减少的发送时延，即2s/(210)=800/(110)。即，由于帧长减少而缩短的发送时延，应等于由于距离减少而缩短的传播时
14、延的2倍。可得s=80,即最远的两个站点之间的距离最少需要减少80m。【注意】CSMA/CD的碰撞窗口=2倍传播时延，报文发送时间碰撞窗口。38.解析：返回的确认序列号是接收端期待收到对方下一个报文段数据部分的第一个字节的序号，因此乙在正确接收到两个段后，返回给甲的确认序列号是200+300+500=1000。39解析：在发生超时后，慢开始门限ssthresh变为16KB/2=8KB,拥塞窗口变为1KB。在接下来的3个RTT内，执行慢开始算法，拥塞窗口大小依次为2KB、4KB、8KB,由于慢开始门限ssthresh为8KB,因此之后转而执行拥塞避免算法，即拥塞窗口开始“加法增大”。因此第4个RTT结束167:
