2017考研408真题答案.pdf

2017年计算机学科专业基础综合试题参考答案一、单项选择题1.B2.c3.A4.B5.B6.D7.B8.A9.B10.B11.D12.C13.C14.A15.D16.A17.C18.B19.A20.D21.D22.B23.D24.C25.B26.D27.B28.D29.B30.D31.B32.B33.A34.D35.B36.A37.D38.C39.A40.C1.解析：Sum+=+i;相当于+i;sum=sum+i;。进行到第k趟循环，sum=(1+k)k/2。显然需要进行O(n12)趟循环，因此这也是该函数的时间复杂度。2.解析：I的反例：计算斐波拉契数列迭代实现只需要一个循环即可实现。的反例：入栈序列为1、2,进行如下操作PUSH、PUSH、POP、POP,出栈次序为2、1；进行如下操作PUSH、POP、PUSH、POP,出栈次序为1、2。V,栈是一种受限的线性表，只允许在一端进行操作。正确。3.解析：三元组表的结点存储了行row、列col、值value三种信息，是主要用来存储稀疏矩阵的一种数据结构。十字链表将行单链表和列单链表结合起来存储稀疏矩阵。邻接矩阵空间复杂度达O(,不适于存储稀疏矩阵。二叉链表又名左孩子右兄弟表示法，可用于表示树或森林。因此A正确。4.解析：先序序列是先父结点，接着左子树，然后右子树。中序序列是先左子树，接着父结点，然后右子树，递归进行。如果所有非叶结点只有右子树，先序序列和中序序列都是先父结点，然后右子树，递归进行，因此B正确。5.解析：后序序列是先左子树，接着右子树，最后父结点，递归进行。根结点左子树的叶结点首先被访问，它是e。接下来是它的父结点a,然后是a的父节点c。接着访问根结点的右子树。它的叶结点b首先被访问，然后是b的父结点d,再者是d的父结点g。最后是根结点f。因此d与a同层，B正确。6.解析：哈夫曼编码是前缀编码，各个编码的前缀各不相同，因此直接拿编码序列与哈夫曼编码009。此需要3轮，选C。14.解析：时间局部性是一旦一条指令执行了，则在不久的将来它可能再被执行。空间局部性是一旦一个存储单元被访问，那么它附近的存储单元也很快被访问。显然，这里的循环指令本身具有时间局部性，它对数组a的访问具有空间局部性，选A。15.解析：在变址操作时，将计算机指令中的地址与变址寄存器中的地址相加，得到有效地址，指令提供数组首地址，由变址寄存器来定位数据中的各元素。所以它最适合按下标顺序访问一维数组元素，选D。相对寻址以P为基地址，以指令中的地址为偏移量确定有效地址。寄存器寻址则是在指令中指出需要使用的寄存器。直接寻址是在指令的地址字段直接指出操作数的有效地址。16.解析：三地址指令有29条，所以它的操作码至少为5位。以5位进行计算，它剩余32-29=3种操作码给二地址。而二地址另外多了6位给操作码，因此它数量最大达3*64=192。所以指令字长最少为23位，因为计算机按字节编址，需要是8的倍数，所以指令字长至少应该是24位，选A。17.解析：超标量是指在CPU中有一条以上的流水线，并且每个时钟周期内可以完成一条以上的指令，其实质是以空间换时间。I错误，它不影响流水线功能段的处理时间；、正确。选C。18.解析：主存储器就是我们通常说的主存，在CPU外，存储指令和数据，由RAM和ROM实现。控制存储器用来存放实现指令系统的所有微指令，是一种只读型存储器，机器运行时只读不写，在CPU的控制器内。CS按照微指令的地址访问，所以B错误。19.解析：五阶段流水线可分为取指IF、译码/取数ID、执行EXC、存储器读MEM、写回Write Back。数字系统中，各个子系统通过数据总线连接形成的数据传送路径称为数据通路，包括程序计数器、算术逻辑运算部件、通用寄存器组、取指部件等等，不包括控制部件，选A。20.解析：多总线结构用速率高的总线连接高速设备，用速率低的总线连接低速设备。一般来说，CPU是计算机的核心，是计算机中速度最快的设备之一，所以A正确。突发传送方式把多个数据单元作为一个独立传输处理，从而最大化设备的吞吐量。现实中一般用支持突发传送方式的总线提高存储器的读写效率，B正确。各总线通过桥接器相连，后者起流量交换作用。PCI-Express总线都采用串行数据包传输数据，所以选D。21.解析：I/O端口又称I/O接口，是CPU与设备之间的交接面。由于主机和I/O设备的工作方式和工作速度有很大差异，I/O端口就应运而生。在执行一条指令时，CPU使用地址总线选择所请求的IVO端口，使用数据总线在CPU寄存器和端口之间传输数据。所以选D。22.解析：多重中断系统在保护被中断进程现场时关中断，执行中断处理程序时开中断，B错误。CPU一般在一条指令执行结束的阶段采样中断请求信号，查看是否存在中断请求，然后决定是否响应中断，A、D正确。中断请求一般来自CPU以外的事件，异常一般发生在CPU内部，C正确。23.解析：011先来先服务调度算法是作业来得越早，优先级越高，因此会选择J1。短作业优先调度算法是作业运行时间越短，优先级越高，因此会选择J3。所以D正确。24.解析：执行系统调用的过程是这样的：正在运行的进程先传递系统调用参数，然后由陷入(trap)指令负责将用户态转化为内核态，并将返回地址压入堆栈以备后用，接下来CPU执行相应的内核态服务程序，最后返回用户态。所以C正确。25.解析：回收起始地址为60K、大小为140KB的分区时，它与表中第一个分区和第四个分区合并，成为起始地址为20K、大小为380KB的分区，剩余3个空闲分区。在回收内存后，算法会对空闲分区链按分区大小由小到大进行排序，表中的第二个分区排第一。所以选择B。26.解析：绝大多数操作系统为改善磁盘访问时间，以簇为单位进行空间分配，因此选D。27.解析：进程切换带来系统开销，切换次数越多，开销越大，A正确。当前进程的时间片用完后，它的状态由执行态变为就绪态，B错误。时钟中断是系统中特定的周期性时钟节拍。操作系统通过它来确定时间间隔，实现时间的延时和任务的超时，C正确。现代操作系统为了保证性能最优，通常根据响应时间、系统开销、进程数量、进程运行时间、进程切换开销等等因素确定时间片大小，D正确。28.解析：多道程序系统通过组织作业（编码或数据）使CPU总有一个作业可执行，从而提高了CPU的利用率、系统吞吐量和I/O设备利用率，I、V是优点。但系统要付出额外的开销来组织作业和切换作业，错误。所以选D。29.解析：一个新的磁盘是一个空白版，必须分成扇区以便磁盘控制器能读和写，这个过程称为低级格式化（或物理格式化）。低级格式化为磁盘的每个扇区采用特别的数据结构，包括校验码，错误。为了使用磁盘存储文件，操作系统还需要将自己的数据结构记录在磁盘上。这分为两步。第一步是将磁盘分为由一个或多个柱面组成的分区，每个分区可以作为一个独立的磁盘，I错误。在分区之后，第二步是逻辑格式化（创建文件系统）。在这一步，操作系统将初始的文件系统数据结构存储道磁盘上。这些数据结构包括空闲和已分配的空间和一个初始为空的目录，、V正确。所以选B。30.解析：可以把用户访问权限抽象为一个矩阵，行代表用户，列代表访问权限。这个矩阵有4行5列，1代表true,0代表false,所以需要20位，选D。31.解析：硬链接指通过索引结点进行连接。一个文件在物理存储器上有一个索引节点号。存在多个文件名指向同一个索引节点，正确。两个进程各自维护自己的文件描述符，正确，I错误。所以选择B。32.解析：在开始DMA传输时，主机向内存写入DMA命令块，向DMA控制器写入该命令块的地址，启动I/O设备。然后，CPU继续其他工作，DMA控制器则继续下去直接操作内存总线，将地址放到总线上开始传输。当整个传输完成后，DMA控制器中断CPU。因此执行顺序是2、3、1、4，012表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层（对应根结点）及操作数（对应叶结点）不需要添加括号。(2分)(2)算法实现(10分)将二叉树的中序遍历递归算法稍加改造即可得本题答案。除根结点和叶结点外，遍历到其他结点时在遍历其左子树之前加上左括号，在遍历完右子树后加上右括号。void BtreeToE(BTree*root)BtreeToExp(root,1);/根的高度为1void BtreeToExp(BTree*root,int deep)Aif(root=NULL)return;/空结点返回else if(root-left=NULL&root-right=NULL)/若为叶结点printf(%s,root-data);/输出操作数，不加括号elseif(deep1)printf();/若有子表达式则加1层括号BtreeToExp(root-left,deep+1);printf(号s,root-data);/输出操作符BtreeToExp(root-right,deep+1);if(deepl)printf();/若有子表达式则加1层括号【评分说明】若考生设计的算法满足题目的功能要求，则(1)、(2)根据所实现算法的策略及输出结果给分，细则见下表。分数备注15采用中序遍历算法且正确，括号嵌套正确，层数适当。14采用中序遍历算法且正确，括号嵌套正确，但括号嵌套层数过多。例如，表达式最外层加上括号，或操作数加括号如(a)。11采用中序遍历算法，但括号嵌套层数不完全正确。例如，左右括号数量不匹配。9采用中序遍历算法，但没有考虑括号。7其他若考生采用其他方法得到正确结果，可参照的评分标准给分。如果程序中使用了求结点深度等辅助函数，但没有给出相应的实现过程，只要考生进行了必要的说明，可不扣分。若在算法的基本设计思想描述中因文字表达没有清晰反映出算法思路，但在算法实现中能够表达出算法思想且正确的，可参照的标准给分。若算法的基本设计思想描述或算法实现中部分正确，可参照中各种情况的相应给分标准酌情给分。参考答案中只给出了使用C语言的版本，使用C+语言的答案参照以上评分标准。42.解答：(1)Pim算法属于贪心策略。算法从一个任意的顶点开始，一直长大到覆盖图中所有顶点为014