2013考研408真题答案(1).pdf

2013年计算机学科专业基础综合试题参考答案一、单项选择题1.8D2.3.D4.B5.A6.C7.C8.D9.c10.A11.c12.C13:A14.A15.C16.A17.D18.C19.B20.B21.B22.D23.A24.A25.C26.A27.C28.B29.D30.B31.B32.B33.B34.A35.D36.B37.A38.B39.B40.A1.解析：两个升序链表合并，两两比较表中元素，每比较一次确定一个元素的链接位置（取较小元素，头插法)。当一个链表比较结束后，将另一个链表的剩余元素插入即可。最坏的情况是两个链表中的元素依次进行比较，直到两个链表都到表尾，即每个元素都经过比较，时间复杂度为O(m+n)-O(max(m,n)。2.解析显然，3之后的4,5，n都是P3可取的数（一直进栈直到该数入栈后马上出栈）。接下来分析1和2：P1只能是3之前入栈的数（可能是1或2），当P1=1时，P3可取2：当P1=2时，P3可取1，故P3可能取除3之外的所有数，个数为n-1。3.解析：利用7个关键字构建平衡二叉树T,平衡因子为0的分支结点个数为3，构建的平衡二叉树如下图所示。构造及调整的过程如下：(RRRR4RR425RR】3674.解析：将哈夫曼树的思想推广到三叉树的情形。为了构成严格的三叉树，需添加权为0的虚叶结点，对于严格的三叉树(n01)%(3-1)u=10，需要添加m-u-1=3-1-1个叶结点，说明7个叶结点刚好可以构成一个严格的三叉树。按照哈夫曼树的原则，权为0的叶结点应离树根最远，构造最小带权生成树的过程如下：086027141455最小的带权路径长度为(2+3)3+(4+5)2+(6+7)1=46。5.解析：根据后序线索二叉树的定义，X结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后序遍历的方式可知X结点的后序后继是其父结点，即其右线索指向的是父结点。为了更加形象，在解题的过程中可以画出如下草图。6.解析：在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点，那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树会发生变化，不完全相同。7.解析：邻接矩阵A为非对称矩阵，说明图是有向图，度为入度加出度之和。各顶点的度是矩阵中此结点对应的行（对应出度）和列（对应入度）的非零元素之和。8.解析：送分题。只要掌握DFS和BFS的遍历过程，便能轻易解决。逐个代入，手工模拟，选项D是深度优先遍历，而不是广度优先遍历。b9.解析：找出AOE网的全部关键路径为(b、d、c、g)、(b、d、e、h)和(b、f、h)。根据定义，只有关键路径上的活动时间同时减少时，才能缩短工期，即正确选项中的两条路径必须涵盖在所有关键路径之中。利用关键路径算法可求出图中的关键路径共有三条：(b、d、c、g)、(b、d、e、h)和(b、f、h)。由此可知，选项A和B中并不能包含(b、f、h)这条路径，选项C中，并不能08703FFH所对应的页表项，页框号为0153H,页框号与页内地址拼接即为物理地址0153180H。17.解析：根据变址寻址的方法，变址寄存器的内容(1000H)与形式地址的内容(2000H)相加，得到操作数的实际地址(3000H),根据实际地址访问内存，获取操作数4000H。变址寄存器形式地址1000H2000H地址内容1000H2000H3000H3000H3000H4000日18.解析：采用4级流水执行100条指令，在执行过程中共用4+(100-1)=103个时钟周期。CPU的主频是1.03GHz,也就是说每秒钟有1.03G个时钟周期。流水线的吞吐率为1.03G100/103=1.0109条指令秒。时钟99100时钟399100时钟2999100时钟129910010019.解析：USB是一种连接外部设备的I/O总线标准，属于设备总线，是设备和设备控制器之间的接口。而PCI、AGP、PCI-E作为计算机系统的局部总线标准，通常用来连接主存、网卡、视频卡等。20.解析：RAD0方案是无冗余和无校验的磁盘阵列，而RAD15方案均是加入了冗余（镜像）或校验的磁盘阵列。条带化技术就是一种自动地将V0的负载均衡到多个物理磁盘上的技术，条带化技术就是将一块连续的数据分成很多小部分并把它们分别存储到不同磁盘上去。这就能使多个进程同时访问数据的多个不同部分而不会造成磁盘冲突，而且在需要对这种数据进行顺序访问的时候可以获得最大程度上的IVO并行能力，从而获得非常好的性能。故能够提高RAD可靠性的措施主要是对磁盘进行镜像处理和奇偶校验，其余选项不符合条件。21.解析：磁盘转速是10000转/分，转一圈的时间为6ms,因此平均查询扇区的时间为3ms,平均寻道时间为6ms,读取4KB扇区信息的时间为4KB/(20MB/s)=0.2ms,磁盘控制器延迟为0.2ms,总时间为3+6+0.2+0.2-9.4ms。22.解析：中断处理方式：在I/O设备输入每个数据的过程中，由于无需CPU干预，因而可使CPU与/O设备并行工作。仅当输完一个数据时，才需CPU花费极短的时间去做些中断处理。因此中断申请使用的是CPU处理时间，发生的时间是在一条指令执行结束之后，数据是在软件的控制下完成传送的。而DMA方式与之不同。DMA方式：数据传输的基本单位是数据块，即在CPU与IVO设备之间，每次传送至少一个数据块；DMA方式每次申请的是总线的使用权，所传送的数据是从设备直接送入内存的，或者相反：仅在传送一个或多个数据块的开始和结束时，才需CPU干预，089间隔为低电平后一个间隔为高电平表示码元1；码元0正好相反。也可以采用相反的规定。故对应比特串可以是00110110，或11001001。35.解析：不进行分组时，发送一个报文的时延是8Mb/10Mbps=-800ms,采用报文交换时，主机甲发送报文需要一次时延，而报文到达路由器进行存储转发又需要一次时延，总时延为800ms*2=1600ms。进行分组后，发送一个报文的时延是10kb/10Mbps=1ms,一共有8Mb/10kb=800个分组，主机甲发送800个分组需要1ms*800-800ms的时延，而路由器接受到第一个分组后直接开始转发，即除了第一个分组，其余分组经过路由器转发不会产生额外的时延，总时延就为800ms+1ms=801msa36.解析：选项A、C和D都是信道划分协议，信道划分协议是静态划分信道的方法，肯定不会发生冲突。CSMA全称是载波侦听多路访问协议，其原理是站点在发送数据前先侦听信道，发现信道空闲后再发送，但在发送过程中有可能会发生冲突。37.解析：HDLC协议对比特串进行组帧时，HDLC数据帧以位模式01111110标识每一个帧的开始和结束，因此在帧数据中凡是出现了5个连续的位“1”的时候，就会在输出的位流中填充一个“0”。因此组帧后的比特串为011111000011111010（下划线部分为新增的0）。38.解析：直通交换在输入端口检测到一个数据帧时，检查帧首部，获取帧的目的地址，启动内部的动态查找表转换成相应的输出端口，在输入与输出交叉处接通，把数据帧直通到相应的端口，实现交换功能。直通交换方式只检查帧的目的地址，共6B,所以最短的传输延迟是68bit/100Mbps=0.48us.39.解析：确认序号ack是期望收到对方下一个报文段的数据的第一个字节的序号，序号sq是指本报文段所发送的数据的第一个字节的序号。甲收到1个来自乙的TCP段，该段的序号sq=1913、确认序号ack=2046、有效载荷为100字节，表明到序号1913+100-1=2012为止的所有数据甲均已收到，而乙期望收到下一个报文段的序号从2046开始.故甲发给乙的TCP段的序号sCq1=ack=2046和确认序号ack1=seq+100=2013。40.解析：根据下图可知，SMTP协议用于用户代理向邮件服务器发送邮件，或在邮件服务器之间发送邮件。SMTP协议只支持传输7比特的ASCI码内容。发作人发送方接收方收体人用户代理发送邮件服务器郎件服务器读取用户代理邮件邮件SMTPSMTPSMTPPOP3POP3POP3客户TCP服务器服务器T客户连接连接SMTP发送邮件SMTPSMTP客户TCP连接服务器二、综合应用题41.解答：,(1)给出算法的基本设计思想：算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计091