搜索
解析第一版，不排除答案、解析（特别是综合题），存在一些错误和问题。一、单项选择题1.C按上三角存储，m7,2对应的是m2,7，在它之前有：第1列：1第2列：2……第6列：6第7列：1前面一共1+2+3+4+5+6+1个元素，共22个元素，数组下标从0开始，故下标为m2,7的数组下标为22。2.D第一个pop栈中状态为a,b，pop出栈元素为b，第二个pop栈中状态为a,c，pop出栈元素为c，第三个pop栈中状态为a,d,e，pop出栈元素为e，把序列连起来就是b,c,e。3.A由于题目明确说明只存储结点数据信息，所以采用顺序存储时要用数组的下标保存结点的父子关系，所以对于这棵二叉树存储的结果就是存储了一棵五层的满二叉树，五层的满二叉树结点个数为1 + 2 + 4 + 8 + 16 = 31，所以至少需要31个存储单元。 4.C1.森林的先根遍历对应它自己转化后二叉树的先序遍历，森林的后根遍历对应它自己转化后二叉树的中序遍历，所以先根和后根可以唯一确定森林转化后的二叉树，如下：后序遍历为：b,f,e,d,c,aacbdef2020年全国硕士研究生入考试计算机学科专业基础综合（408）答案解析5.B在4，5，1，2，3中由于1先插入，所以1会成为4的左孩子，2会成为1的右孩子……。6.B首先有直觉这个方式输出的肯定是一个逆序，所以用一个简单的例子测试一下a-b-c，按照题目的遍历方式得到的序列为c,b,a，排除A,C,D，选B下面严谨的论证一下，题目已经限定有向无环图图，假设从a结点出发开始深度遍历，那么这一次递归到最大深度，必然终止于某结点(记为h结点)，h结点必然没有出度。此时h输出，程序栈退栈，回到h的前一个结点(记为f)，如果f还有其他出度，那么此时要访问其他出度，直到每一个出度的分支都访问结束才能访问f，这样来看，一个结点要被访问的前提必须是他的所有出度分支都要被访问，换句话说也就是等一个结点没有出度时才可以访问，这就是逆拓扑排序(每次删除的都是出度为零的结点)。7.A先将所有边按权值排序，然后依次取权值最小的边但不能在图中形成环，此时取得权值序列为5，6，此时7不能取因为形成了环，接下来去9，10，11，按权值对应的边。8.BA改为权值之和最大的路径，B的最长就是指权值之和最大，C增加关键活动一定会增加工期，D减小一关键活动不一定会缩短工期9.回忆不全III错误，因为堆只要求根大于左右子树，并不要求左右子树有序。10.B11.A直接插入排序在有序数组上的比较次数为n-1，简单选择排序的比较次数为1+2+...+n-1=n(n-1)/2。II，辅助空间都是O(1),没差别，III，因为本身已经有序，移动次数均为0。12.B王道书P13原话“机器字长通常与CPU的寄存器位数、加法器有关”。13.A展开1100100000000000…（省略16个0）H，将其转换为对应的float或int。如果是float，尾数是隐藏了的最高位1，数符为1表示负数，阶码10010000=27+24=128+16，减去偏置值127=17，为-217；如果是int，带符号补码，为负数，数值部分取反加1，011100000000000…（省略16个0）H，算出值为-7*227。14.D根据按边界对齐和小端方式的定义（王道书第2章和第4章的常见问题分别给出了大小端存放和按边界对其的定义及举例），给出变量a的存放方式如下：x1（LSB）x2（MSB）nullnull00H00H34H12H首地址为2020FE00H，按字节编址，则34H所在单元地址为2020FE00H+6=2020FE06H。15.DCache由SRAM组成。TLB通常用相联存储器组成，也可以由SRAM。DRAM需要不断的刷新，性能较低，肯定不能选。16.A48条指令需要6位操作码字段，4种寻址方式需要2位寻址特征位，故寻址范围为0～255。注意，主存地址不能为负数。17.BII肯定错误，IV是通过增加功能部件实现的并行。在理想情况下，I单周期CPU，令指令周期=时钟周期；III基本流水线CPU，让每个时钟周期流出一条指令（执行完一条指令）。18.A自陷是属于内中断。19.C每个时钟周期传递2次，根据公式，2.4G*2*2*2B/s=19.2GB/s，选C。误区，公式里最后已经乘了2次了（全双工），大家在求时不要再乘了。20.题干不完整II外部中断，描述的是时钟中断；III外部中断，外部事件。21.B容易误选A，这点王道书上有描述P278。B．CPU响应中断需要满足3个条件，王道书P278。22.C注意是周期挪用方式，如果是停止CPU访存，那就是应该选A。本题也有观点认为选A。23.B既可以是读的方式，也可以是写的方式，A错误。系统打开文件表整个系统只有一张，同一个文件打开多次只需要改变引用计数，不需要对应多项,B正确。用户进程的打开文件表关于同一个文件不一定相同，C错误。进程关闭文件时，文件的引用计数减少1，引用计数变为0时才删除，D错误。24.A链接分配不能支持随机访问，B错误。连续分配不支持可变文件长度，C错误。动态分区分配是内存管理方式非磁盘空间管理方式，D错误。25.D中断的保存硬件和软件分别都要保存部分寄存器内容，硬件保存程序计数器PC，操作系统保存程序状态字PSW，不仅仅由操作系统单独完成，I错误。26.D多级反馈队列调度需要综合考虑优先级数量、优先级之间的转换规则等，I,II,III,IV均正确。27.B此道题作出需求矩阵NEED=MAX-ALLOCATED即可。同时，由allocated矩阵得知当前available为（1，0）。由需求矩阵可知，初始只能满足p2需求。P2释放资源后available变为（4，1）。此时仅能满足p1需求，p1释放后可以满足p3。故得到顺序p2-p1-p3。B正确。28.DI影响缺页中断发生的频率；II,IV影响缺页中断的处理时间；II影响访问慢表和访问目标物理地址的时间，故I,II，III,IV均正确。29.B父进程可以和子进程共享一部分共享资源，但是不和子进程共享虚拟地址空间，在创建子进程时，会为子进程分配空闲的进程描述符、唯一标识的pid等，B错误。30.D设备可以看作特殊文件,A正确。B为知识点，正确。访问设备的驱动程序与具体设备无关，D错误。31.B最多创建文件个数=最多索引节点个数。由题，索引节点占4个字节，对应32位，最多可以表示2^32个文件，B正确。32.CI,II,III分别符合互斥、空闲让进、有限等待的原则，不能立即进入临界区的进程可以选择等待部分时间，IV错误。故C正确。（个人认为IV也对，四个原则：II是空闲让进，I是忙则等待，III是有限等待，IV是让权等待。不排除是回忆版真题有误）33.C王道书P14，网络协议主要由语义、语法和时序（一般教材定义为同步）三部分组成，即协议三要素。语义：规定通信双方彼此“讲什么”，规定所要完成的功能，如规定通信双方要发出什么控制信息，执行的动作和返回的应答。语法：规定通信双方彼此“如何讲”，即规定传输数据的格式，如数据和控制信息的格式。时序：或称同步，规定了信息交流的次序。由图可知发送方与接收方依次交换信息，体现了协议三要素中的时序要素。34.B虚电路服务需要有建立连接过程，每个分组使用短的虚电路号，属于同一条虚电路的分组按照同一路由进行转发，分组到达终点的顺序与发顺顺序相同，可以保证有序传输，不需要为每条虚电路预分配带宽。35.C网络层设备路由器可以隔离广播域和冲突域，链路层设备普通交换机只能隔离冲突域，物理层设备集线器、中继器既不能隔离冲突域也不能隔离广播域。题中共有2个广播域，4个冲突域。36.D发送数据帧和确认帧的时间分别为800ms，800ms。发送周期为T=800+200+800+200=2000ms。采用停止-等待协议，信道利用率为800/2000=40%。37.A为了尽量避免碰撞，802.11规定，所有的站在完成发送后，必须再等待一段很短的时间(继续监听)才能发送下一帧。这段时间通称为帧间间隔IFS(InterFrameSpace)。帧间间隔的长短取决于该站要发送的帧的类型。IEEE802.11推荐使用3种帧间隔（IFS），以便提供基于优先级的访问控制。DIFS(分布式协调IFS)：最长的IFS，优先级最低，用于异步帧竞争访问的时延。PIFS（点协调IFS）：中等长度的IFS，优先级居中，在PCF操作中使用。SIFS（短IFS）：最短的IFS，优先级最高，用于需要立即响应的操作。网络中的控制帧以及对所接收数据的确认帧都采用SIFS作为发送之前的等待时延。当结点要发送数据帧时，载波监听到信道空闲时，需等待DIFS后发送RTS预约信道，，IFS1对应的帧间隔DIFS，时间最长，图中IFS2，IFS3，IFS4对应SIFS。38.C在不出现拥塞的前提下，拥塞窗口从8KB增长到20KB所需的最长时间（由于慢开始门限可以根据需求设置所以这里面为了求最长时间可以假定在慢开始门限小于等于8KB，这样由8KB-20KB的过程中都是加法增大），考虑拥塞窗口达到8KB时，以后的每个轮次拥塞窗口逐次加1，需12X2=24ms后达到20KB大小。也有同学反馈：题目是从8k-32k，那么答案就选D。39.C主机甲与主机乙建立TCP连接时发送的SYN段中的序号为1000，，则在数据数据传输阶段所用序号起始为1001，在断开连接时，甲发送给乙的FIN段中的序号为5001，在无任何重传的情况下，甲向乙已经发送的应用层数据的字节数为5001-1001=4000。40.D忽略各种时延情况下，最短时间，即本地域名服务器存在域名与IP地址映射关系，仅需主机向本地域名服务器递归查询一次10ms，传送数据10ms，最短时间共需20ms；最长时间即本地域名服务器不存在域名与IP地址映射关系，需向本地域名服务器递归查询一次后，迭代查询各级域名服务器3次，需40ms,传送数据10ms，最长时间共需50ms。二、综合应用题41解析：由D=|a-b|+|b-c|+|c-a|得D最小为0，此时a=b=c，这就是最小情况，增大a,b,c任意一个都会使D变大，所以我们要找的就是S1,S2,S3中值最接近的一组数（三个数），同时改变a,b,c求最小的D是一个复杂组合优化问题，为了简化问题，我们每次只改变a,b,c中的一个值观察D的变化情况。换个角度看，分析D=|a-b|+|b-c|+|c-a|，不失一般性的假设a=b=c，观察下面数轴|a-b|=L1,|b-c|=L2,|c-a|=L3,D=|a-b|+|b-c|+|c-a|=L1+L2+L3=2L3,事实上决定D大小的关键在于a和c的距离，问题就变为了每次固定c找一个a使的|c-a|=L3最小，然后更新c寻找下一个a。（1）算法设计思想：不失一般性的假设a=b=c。分情况讨论：I.𝑎4=𝑏6=𝑐8且!（𝑎4=𝑏6=𝑐8）(a,b,c不全相同):此时𝐷:4;=𝐷=|𝑎4-𝑏6|+|𝑏6-𝑐8|+|𝑐8-𝑎4|，是一个不为0的数，要使这个数变小，可能会有两种选择增大a或者增大b（显然增大c只会让D增加），即𝑎4变为𝑎4=或𝑏6变为𝑏6=。先看𝑏6=，①如果𝑎4𝑏6==𝑐8，看数轴，b其实就是在a和c之间改变，并不影响L3=|𝑐8-𝑎4|，那么此时D是不改变的；②如果𝑎4𝑐8𝑏6=，看数轴，此时的L3=|𝑎4-𝑏6=|，L3变大了，那么此时D变大。再看𝑎4=，①如果𝑎4=𝑐8，看数轴，由于a增大L3=max{|𝑏6-𝑐8|,|𝑐8-𝑎4=|}|𝑐8-𝑎4|,L3变小了，此时D减小；②如果𝑏6=𝑐8𝑎4=，那么此时D变小变大不确定。综上，只有增加a才可能使D变小，所以a变为𝑎4=，重新计算D=𝐷?，如果𝐷?𝐷:4;，则𝐷:4;=𝐷?，循环上面步骤，直到任一数组遍历结束或出现II状态，最后返回𝐷:4;。I