2015考研408真题答案.pdf

2015年计算机学科专业基础综合试题参考答案一、单项选择题1.A2.B3.D4.D5.D6.C7.A8.C9.C10.C11.A12.A13.B14.D15.C16.B17.B18.D19.C20.B21.B22.D23.B24.C25.D26.B27.A28.A29.B30.C31.C32.C33.D34.A35.B36.B37.A38.C39.A40.C1.解析：递归调用函数时，在系统栈里保存的函数信息需满足先进后出的特点，依次调用了mainO、S(1)、S(O),故栈底到栈顶的信息依次是mainO、S(1)、S(0)。2.解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列a,b,c,d为入栈次序，则出栈序列的个数为？”，对于n个不同元素进栈，出栈序列的个数为1C=14。n+13.解析：在哈夫曼树中，左右孩子权值之和为父结点权值。仅以分析选项A为例：若两个10分别属于两棵不同的子树，根的权值不等于其孩子的权值和，不符；若两个10属同棵子树，其权值不等于其两个孩子（叶结点）的权值和，不符。B、C选项的排除方法一样。4.解析：只有两个结点的平衡二叉树的根结点的度为1，A错误。中序遍历后可以得到一个降序序列，树中最大元素一定无左子树（可能有右子树），因此不一定是叶结点，B错误。最后插入的结点可能会导致平衡调整，而不一定是叶结点，C错误。5.解析：画出该有向图图形如下：采用图的深度优先遍历，共5种可能：,Vo,V3,V2,V1,V0,V3,V1,V2,选D。6.解析：从V4开始，Kruskal算法选中的第一条边一定是权值最小的(V,V4),B错误。由于V1和V4已经可达，第二条边含有V1和V4的权值为8的一定符合Prim算法，排除A、D。7.解析：。048。画出查找路径图，因为折半查找的判定树是一棵二叉排序树，看其是否满足二叉排序树的要求。500500180180200450500200450200200500180180450450很显然，选项A的查找路径不满足。8.解析：由题中“失配s)时，j5”,可知题中的主串和模式串的位序都是从0开始的（要注意灵活应变)。按照next数组生成算法，对于t有：编号05babcnext-10012依据KMP算法“当失配时，i不变，j回退到nex的位置并重新比较”，当失配s的们时，ij=5,由上表不难得出next=next5=2(位序从0开始)。从而最后结果应为：i=5(i保持不变)，j=2。9.解析：基数排序的元素移动次数与关键字的初始排列次序无关，而其他三种排序都是与关键字的初始排列明显相关的。10.解析：删除8后，将12移动到堆顶，第一次是15和10比较，第二次是10和12比较并交换，第三次还需比较12和16，故比较次数为3次。12101151015122116121341621341611.解析：希尔排序的思想是：先将待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成)，分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小)时，再对全体元素进行一次直接插入排序。12.解析：硬件能直接执行的只能是机器语言（二进制编码），汇编语言是为增强机器语言的可读性和记忆性的语言，经过汇编后才能被执行。13.解析：补码整数表示时，负数的符号位为1，数值位按位取反，末位加1，因此剩下的2个“1”在最低位时，表示的是最小整数，为10000011，转换成真值为-125。049。14.解析：对阶是较小的阶码对齐至较大的阶码，I正确。右规和尾数舍入过程，阶码加1而可能上溢，正确，同理I也正确。尾数溢出时可能仅产生误差，结果不一定溢出，V正确。15.解析：直接映射的地址结构为：主存字块标记Cache字块标记字块内地址按字节编址，块大小为432bit=16B=2B,则“字块内地址”占4位；“能存放4K字数据的Cache”即Cache的存储容量为4K字（注意单位），则Cache共有lK=21o个Cache行，则Cache字块标记占10位；则主存字块标记占32-10-4-18位。Cache的总容量包括：存储容量和标记阵列容量（有效位、标记位、一致性维护位和替换算法控制位)。标记阵列中的有效位和标记位是一定有的，而一致性维护位（脏位）和替换算法控制位的取舍标准是看题眼，题目中，明确说明了采用写回法，则一定包含一致性维护位，而关于替换算法的词眼题目中未提及，所以不予考虑。从而每个Cache行标记项包含18+1+1=20位，则标记阵列容量为：2l0*20位=20K位，存储容量为：4K*32位=128K位，则总容量为：128K+20K=148K位。16.解析：上述指令的执行过程可划分为取数、运算和写回过程，取数时读取xadd可能不需要访问主存而直接访问Cache,而写直通方式需要把数据同时写入Cache和主存，因此至少访问1次。17.解析：DRAM使用电容存储，所以必须隔一段时间刷新一次，如果存储单元没有被刷新，存储的信息就会丢失。SDRAM表示同步动态随机存储器。18.解析：每个访存地址对应的存储模块序号(0、1、2、3)如下所示：访存地址800580068007800880018002800380048000模块序号201300其中，模块序号=访存地址%存储器交叉模块数。判断可能发生访存冲突的规则是：给定的访存地址在相邻的四次访问中出现在同一个存储模块内。据此，根据上表可知8004和8000对应的模块号都为0，即表明这两次的访问出现在同一模块内且在相邻的访问请求中，满足发生冲突的条件。19.解析：在同步通信方式中，系统采用一个统一的时钟信号，而不是由各设备提供，否则没法实现统一的时钟。20.解析：存取时间=寻道时间+延迟时间+传输时间。存取一个扇区的平均延迟时间为旋转半周的时间，即为(60/7200)/2=4.17ms,传输时间为(60/7200)/1000=0.01ms,因此访问一个扇区的平均存取时间为4.17+0.01+8=12.18ms,保留一位小数则为12.2ms。21.解析：在程序中断I/O方式中，CPU和打印机直接交换，打印字符直接传输到打印机的/O端口，不会涉及到主存地址。而CPU和打印机通过I/O端口中状态口和控制口来实现交互。22.解析：050内中断是指来自CPU和内存内部产生的中断，包括程序运算引起的各种错误，如地址非法、校验错、页面失效、非法指令、用户程序执行特权指令自行中断(T)和除数为零等，以上都在指令的执行过程中产生的，故A正确。这种检测异常的工作肯定是由CPU(包括控制器和运算器)实现的，故B正确。内中断不能被屏蔽，一旦出现应立即处理，C正确。对于D,考虑到特殊情况，如除数为零和自行中断(T)都会自动跳过中断指令，所以不会返回到发生异常的指令继续执行，故错误。23.解析：外部中断处理过程，PC值由中断隐指令自动保存，而通用寄存器内容由操作系统保存。24.解析：考虑到部分指令可能出现异常（导致中断），从而转到核心态。指令A有除零异常的可能，指令B为中断指令，指令D有缺页异常的可能，指令C不会发生异常。25.解析：P(wit)操作表示进程请求某一资源，A、B和C都因为请求某一资源会进入阻塞态，而D只是被剥夺了处理机资源，进入就绪态，一旦得到处理机即可运行。26.解析：死锁的处理采用三种策略：死锁预防、死锁避免、死锁检测和解除。死锁预防，采用破坏产生死锁的四个必要条件中的一个或几个，以防止发生死锁。其中之一的“破坏循环等待条件”，一般采用顺序资源分配法，首先给系统的资源编号，规定每个进程必须按编号递增的顺序请求资源，也就是限制了用户申请资源的顺序，故I的前半句属于死锁预防的范畴。银行家算法是最著名的死锁避免算法，其中的最大需求矩阵MAX定义了每一个进程对类资源的最大需求量，系统在执行安全性算法中都会检查此次资源试分配后，系统是否处于安全状态，若不安全则将本次的试探分配作废。在死锁的检测和解除中，在系统为进程分配资源时不采取任何措施，但提供死锁的检测和解除的手段。故、正确。27.解析：可以采用书中常规的解法思路，也可以采用便捷法。对页号序列从后往前计数，直到数到4(页框数)个不同的数字为止，这个停止的数字就是要淘汰的页号（最近最久未使用的页），题中为页号2。28.解析：磁盘和内存的速度差异，决定了可以将内存经常访问的文件调入磁盘缓冲区，从高速缓存中复制的访问比磁盘/O的机械操作要快很多很多。29.解析：10个直接索引指针指向的数据块大小为10*1KB=10KB:每个索引指针占4B,则每个磁盘块可存放1KB/4B=256个索引指针，一级索引指针指向的数据块大小为：256*1KB=256KB二级索引指针指向的数据块大小为：256*256*1KB=216KB=64MB按字节编址，偏移量为1234时，因1234B10KB,则由直接索引指针可得到其所在的磁盘块地址。文件的索引结点已在内存中，则地址可直接得到，故仅需1次访盘即可。偏移量为307400时，因10KB+256KB307400B64MB,可知该偏移量的内容在二级索引051Connection:连接方式，Close表明为非持续连接方式，keep-alive表示持续连接方式。Cookie值是由服务器产生的，HTTP请求报文中有Cookie报头表示曾经访问过www.test.edu.cm服务器。二、综合应用题41.解答：1)算法的基本设计思想算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值，从而只需对链表进行一趟扫描。因为datan,故辅助数组q的大小为n+1l,各元素的初值均为0。依次扫描链表中的各结点，同时检查qldatal的值，如果为0，则保留该结点，并令qata=l;否则，将该结点从链表中删除。2)使用C语言描述的单链表结点的数据类型定义typedef struct nodeintdata;struct node*link;NODE;Typedef NODE*PNODE;3)算法实现void func(PNODE h,int n)PNODE p=h,;int*q,m;g=(int*)ma11oc(sizeof(int)*(n+1);/申请n+1个位置的辅助空间for(int i=0;ilink!=NULL)m=p-link-data0?p-link-data:-p-link-data;if(*(q+m)=0)/判断该结点的data是否已出现过*(g+m)=1:/首次出现p=p-link;/保留else/重复出现r=p-link;/删除p=link=r-linkfree(r);free(q);【评分说明】若考生设计的算法满足题目的功能要求且正确，则酌情给分。4)参考答案所给算法的时间复杂度为Om),空间复杂度为O()。【评分说明】若考生所估计的时间复杂度和空间复杂度与考生实现的算法一致，可给分。053。