2013年联考《408计算机学科专业基础综合》真题答案.pdf

计算机学科专业基础综合试题参考答案及解析(2013年)一、单项选择题1.D解析：m、n是两个升序链表，长度分别为m和n。在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是m和n中的最小值。2.C解析：除了3本身以外，其他的值均可以取到，因此可能取值的个数为n-1。3.D解析：利用7个关键字构建平衡二叉树T,平衡因子为0的分支结点个数为3，构建的平衡二叉树如下图所示。王道伦坛好月”：4.B解析：利用三叉树的6个叶子结点的权构建最小带权生成树，最小的带权路径长度为(2+3)3+(4+5)2+(6+7)1=46。5.A解析：根据后续线索二叉树的定义，X结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后续遍历的方式可知X结点的后继是其父结点，即其右线索指向的是父结点。6.C解析：在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点，那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树可能发生变化，不完全相同。7.C解析：各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。8.D解析：D选项是深度优先遍历不是广度优先遍历的顺序。9.C10解析：根据AOE网的定义可知，关键路径上的活动时间同时减少，可以缩短工期。10.A解析：一棵高度为2的5阶B树，根结点只有到达5个关键字的时候才能产生分裂，成为高度为2的B树。11.C解析：基数排序的第1趟排序是按照个位数字来排序的，第2趟排序是按照十位数字的大小进行排序的，答案是C选项。12.C解析：基准程序的CPI=20.5+30.2+40.1+50.2=3。计算机的主频为1.2GHz,为1200MHz,该机器的MIPS为1200/3=400。13.A解析：IEEE754单精度浮点数格式为C6400000H,二进制格式为11000110010000000000000000000000,转换为标准的格式为阶码尾数1000110010000000000000000000000因此，浮点数的值为-1.5214.A解析：将x左移一位，y右移一位，两个数的补码相加的机器数为11000000，答案选择A。15.C解析：设校验位的位数为k,数据位的位数为n,应满足下述关系：2n+k+1。n=8,当k=4时，2(=16)8+4+1(=13)，符合要求，校验位至少是4位。16.A解析：虚拟地址为03FFF180H,其中页号为03FFFH,页内地址为180H,根据题目中给出的页表项可知页标记为O3FFH所对应的页框号为O153H,页框号与页内地址之和即为物理地址0153180H。17.D解析：根据变址寻址的主要方法，变址寄存器的内容与形式地址的内容相加之后，得到操作数的实际地址，根据实际地址访问内存，获取操作数4000H。变址寄存器形式地址1000H2000H地址内容1000H2000H2000H3000H3000H4000H18.C解析：采用4级流水执行100条指令，在执行过程中共用4+(100-1)=103个时钟周期。CPU的主频是1.03GHz,也就是说每秒钟有1.03G个时钟周期。流水线的吞吐率为11解析：用户进程访问内存时缺页会发生缺页中断。发生缺页中断，系统会执行的操作可能是置换页面或分配内存。系统内没有越界的错误，不会进行越界出错处理。31.B解析：为了合理地设置进程优先级，应该将进程的CPU利用时间和I/0时间做综合考虑，答案选B。32.B解析：银行家算法是避免死锁的方法。利用银行家算法，系统处于安全状态时没有死锁进程，答案选B。33.B解析：0SI参考模型中，应用层的相邻层是表示层。表示层是OSI七层协议的第六层。表示层的目的是表示出用户看得懂的数据格式，实现与数据表示有关的功能。主要完成数据字符集的转换、数据格式化和文本压缩、数据加密、解密等工作。因此答案选B。34.A解析：根据信号编码的基本规则可知，网卡收到的比特串为00110110，答案选A。35.D解析：不进行分组时，发送一个报文的时延是8Mb/10Mb/s=800ms,在接收端接收此报文的时延也是800ms,共计1600ms。进行分组后，发送一个报文的时延是10kb/10Mb/s=1ms,接收一个报文的时延也是1ms,但是在发送第二个报文时，第一个报文已经开始接收。共计有800个分组，总时间为801ms。36.B解析：介质访问控制协议中能够发生冲突的是CSMA协议，答案为B。37.A解析：HDLC协议对比特串进行组帧时，HDLC数据帧以位模式01111110标识每一个帧的开始和结束，因此在帧数据中凡是出现了5个连续的位“1”的时候，就会在输出的位流中填充一个“0”。所以答案为A。38.B解析：直通交换方式是指以太网交换机可以在各端口间交换数据。它在输人端口检测到一个数据包时，检查该包的包头，获取包的目的地址，启动内部的动态查找表转换成相应的输出端口，在输人与输出交叉处接通，把数据包直通到相应的端口，实现交换功能。通常情况下，直通交换方式只检查数据包的包头即前14个字节，由于不需要考虑前导码，只需要检测目的地址的6B,所以最短的传输延迟是0.483。39.B解析：若甲收到1个来自乙的TCP段，该段的序号seg=1913、确认序号ack=2046、有效载荷为100字节，则甲立即发送给乙的TCP段的序号seql=ack=2046和确认序号ack1=seq+100=2013,答案为B。40.A解析：根据下图可知，SMTP协议支持在邮件服务器之间发送邮件，也支持从用户代理向邮件服务器发送信息。SMTP协议只支持传输7比特的ASC码内容。13发件人发送方接收方收件人用户代理发送邮件服务器邮件服务器读取用户代理邮件邮件SMTPSMTPSMTPPOP3POP3POP3客户TCP服务器服务器TCP客户连接连接SMTP发送邮件SMTP客户TCP连接最务二、综合应用题41.【答案要点】(1)给出算法的基本设计思想：(4分)算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是主元素。算法可分为以下两步：选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num,则计数加1，否则计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。判断c中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，若大于n/2,则为主元素；否则，序列中不存在主元素。(2)算法实现：(7分)int Majority(int A,int n)int i,c,count=1;/c用来保存候选主元素，count用来计数c=A0;/设置A0为候选主元素for i=1;i0)/处理不是候选主元素的情况count-;else/更换候选主元素，重新计数c=Ai;count=1;if count0for(i=count=0;in/2)return c;/确认候选主元素else return-1;/不存在主元素【(1)、(2)的评分说明】若考生设计的算法满足题目的功能要求且正确，则(1)、(2)根据所实现算法的效率给分，细则见下表：时间空间(1)(2)复杂度说明复杂度得分得分0(n)0(1)70(n)0(n)6如采用计数排序思想，见表后Majority1程序0(nlogzn)其他6如采用其他排序的思想0(n2)其他其他方法int Majorityl(intA,intn)/采用计数排序思想，时间：0(n),空间：0(n)int k,*p,max;p=(int*malloc(sizeof(int)*n)申请辅助计数数组for k=0;kn;k+)pk0计数数组清0max=0;for(k=0;kpmax)max=Ak;/记录出现次数最多的元素if（pmaxn/2）return max;else return-1;若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照的标准给分。若算法的基本设计思想描述或算法实现中部分正确，可参照中各种情况的相应给分标准酌情给分。参考答案中只给出了使用C语言的版本，使用C+或Java语言的答案视同使用C语言。(3)说明算法复杂性：(2分)参考答案中实现的程序的时间复杂度为0(n),空间复杂度为0(1)。【评分说明】若考生所估计的时间复杂度与空间复杂度与考生所实现的算法一致，可各给1分。42.【答案要点】(1)采用顺序存储结构，数据元素按其查找概率降序排列。(2分)15