2014年计算机学科专业基础综合试题参考答案
一、单项选择题
（一）单选题答案
1．C2．B3．  A 4．D5．C6．D7．D8．D
9．D10．B11．C12．D13．C14．A 15．A 16．D
17．A 18．C19．C20．C21．D22．B23．A 24．B宜春就业网招聘
25．D26．A 27．A 28．C29．B30．A 31．C32．D
33．C 34．B 35．D 36．C 37．B 38．A 39．B 40．D （二）单选题答案解析
深圳公务员岗位1．内层循环条件j<=n与外层循环的变量无关，每次循环j自增1，每次内层循环都执行n次。外层循环条件为k<=n，增量定义为k*=2，可知循环次数为2k<=n，即k<=log2n。所以内层循环的时间复杂度是O(n)，外层循环的时间复杂度是O(log2n)。对于嵌套循环，根据乘法规则可知，该段程序的时间复杂度T(n)=T1(n)*T2(n)=O(n)*O(log2n)=O(nlog2n)。
2．将中缀表达式转换为后缀表达式的算法思想如下：
江苏省公务员报名入口网址从左向右开始扫描中缀表达式；
遇到数字时，加入后缀表达式；
遇到运算符时：
a.若为'('，入栈；
b.若为')'，则依次把栈中的的运算符加入后缀表达式中，直到出现'('，从栈中删除'(' ；
c.若为除括号外的其他运算符，当其优先级高于除'('以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。
在此，再给出中缀表达式转换为前缀或后缀表达式的一种手工做法，以上面给出的中缀表达式为例：
第一步：按照运算符的优先级对所有的运算单位加括号。
式子变成了：((a/b)+(((c*d)-(e*f))/g))
第二步：转换为前缀或后缀表达式。
前缀：把运算符号移动到对应的括号前面，则变成了：+(/(ab)/(-(*(cd)*(ef))g))
把括号去掉：+/ab/-*cd*efg前缀式子出现。
后缀：把运算符号移动到对应的括号后面，则变成了：((ab)/(((cd)*(ef)*)-g)/)+
把括号去掉：ab/cd*ef*-g/+ 后缀式子出现。
当题目要求直接求前缀或后缀表达式时，这种方法会比上一种快捷得多。
3．end1指向队头元素，那么可知出队的操作是先从A[end1]读数，然后end1再加1。end2指向队尾元素的后一个位置，那么可知入队操作是先存数到A[end2]，然后end2 再加1。若把A[0]储存第一个元素，当队列初始时，入队操作是先把数据放到A[0]，然后end2自增，即可知end2初值为0；而end1指向的是队头元素，队头元素的在数组A中的下标为0，所以得知end1初值也为0，可知队空条件为end1==end2；然后考虑队列满时，因为队列最多能容纳M-1个元素，假设队列存储在下标为0到下标为M-2的M-1个区域，队头为A[0]，队尾为A[M-2]，此时队列满，考虑在这种情况下end1和end2的状态，end1指向队头元素，可知end1=0，end2指向队尾元素的后一个位置，可知end2=M-2+1=M-1，所以可知队满的条件为end1==(end2+1)mod M，选A。
注意：考虑这类具体问题时，用一些特殊情况判断往往比直接思考问题能更快的得到答案，并可以画出简单的草图以方便解题。
4．线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点，所以先写出二叉树的中序遍历序列：edbxac，中序遍历中在x左边和右边的字符，就是它在中序线索化的左、右线索，即b、a，选D。
5．将森林转化为二叉树即相当于用孩子兄弟表示法表示森林。在变化过程中，原森林某结点的第一个孩子结点作为它的左子树，它的兄弟作为它的右子树。那么森林中的叶结点由于没有孩子结点，那么转化为二叉树时，该结点就没有左结点，所以F中叶结点的个数
身份证号一键查询往年中考成绩
就等于T中左孩子指针为空的结点个数，选C。
此题还可以通过一些特例来排除A、B、D选项。
6．前缀编码的定义是在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。D中编码110是编码1100的前缀，违反了前缀编码的规则，所以D不是前缀编码。
7．按照拓扑排序的算法，每次都选择入度为0的结点从图中删去，此图中一开始只有结点3的入度为0；删掉3结点后，只有结点1的入度为0；删掉结点1后，只有结点4的入度为0；删掉4结点后，结点2
和结点6的入度都为0，此时选择删去不同的结点，会得出不同的拓扑序列，分别处理完毕后可知可能的拓扑序列为314265和314625，选D。
8．产生堆积现象，即产生了冲突，它对存储效率、散列函数和装填因子均不会有影响，而平均查长度会因为堆积现象而增大，选D。
9．关键字数量不变，要求结点数量最多，那么即每个结点中含关键字的数量最少。根据4阶B树的定义，根结点最少含1个关键字，非根结点中最少含⎡4/2⎤-1=1个关键字，所以每个结点中，关键字数量最少都为1个，即每个结点都有2个分支，类似与排序二叉树，而15个结点正好可以构造一个4层的4阶B树，使得叶子结点全在第四层，符合B树定义，因此选D。
10．首先，第二个元素为1，是整个序列中的最小元素，所以可知该希尔排序为从小到大排序。然后考虑增量问题，若增量为2，第1+2个元素4明显比第1个元素9要大，A排除；若增量为3，第i、i+3、i+6个元素都为有序序列(i=1,2,3)，符合希尔排序的定义；若增量为4，第1个元素9比第1+4个元素7要大，C排除；若增量为5，第1个元素9比第1+5个元素8要大，D排除，选B。
11．快排的阶段性排序结果的特点是，第i趟完成时，会有i个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。题目问第二趟排序的结果，即要不存在2个这样的数的选项。A选项中2、3、6、7、9均符合，所以A排除；B选项中，2、9均符合，所以B排除；D选项中
5、9均符合，所以D选项排除；最后看C选项，只有9一个数符合，所以C不可能是快速排序第二趟的结果。
12．不妨设原来指令条数为x，那么原CPI就为20/x，经过编译优化后，指令条数减少到原来的70%，即指令条数为0.7x，而CPI增加到原来的1.2倍，即24/x，那么现在P在M 上的执行时间就为指令条数*CPI=0.7x*24/x=24*0.7=16.8秒，选D。
13．8位定点补码表示的数据范围为-128~127，若运算结果超出这个范围则会溢出，A 选项x+y=103-25=78，符合范围，A排除；B选项-x+y=-103-25=-128，符合范围，B排除；D选项-x-y=-103+25=-78，符合范围，D排除；C选项x-y=103+25=128，超过了127，选C。
该题也可按照二进制写出两个数进行运算观察运算的进位信息得到结果，不过这种方法更为麻烦和耗时，在实际考试中并不推荐。
14．(f1)和(f2)对应的二进制分别是(110011001001……)2和(101100001100……)2，根据IEEE754浮点数标准，可知(f1)的数符为1，阶码为10011001，尾数为1.001，而(f2)的数符为1，阶码为01100001，尾数为1.1，则可知两数均为负数，符号相同，B、D排除，(f1)的绝对值为1.001×226，(f2)的绝对值为1.1×2-30，则(f1)的绝对值比(f2)的绝对值大，而符号为负，真值大小相反，即(f1)的真值比(f2)的真值小，即x<y，选A。
此题还有更为简便的算法，(f1)与(f2)的前4位为1100与1011，可以看出两数均为负数，而阶码用移码表示，两数的阶码头三位分别为100和011，可知(f1)的阶码大于(f2)的阶码，又因为是IEEE754规格化的数，尾数部分均为1.xxx，则阶码大的数，真值的绝对值必然大，可知(f1)真值的绝对值大于(f2)真值的绝对值，因为都为负数，则(f1)<(f2)，即x<y。尤溪县教育网
15．4M×8位的芯片数据线应为8根，地址线应为log24M=22根，而DRAM采用地址复用技术，地址线是原来的1/2，且地址信号分行、列两次传送。地址线数为22/2=11根，
所以地址引脚与数据引脚的总数为11+8=19根，选A。
此题需要注意的是DRAM是采用传两次地址的策略的，所以地址线为正常的一半，这是很多考生容易忽略的地方。
16．把指令Cache与数据Cache分离后，取指和取数分别到不同的Cache中寻，那么指令流水线中取指部分和取数部分就可以很好的避免冲突，即减少了指令流水线的冲突。
17．采用32位定长指令字，其中操作码为8位，两个地址码一共占用32-8=24位，而Store指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址，机器中共有16个通用寄存器，则寻址一个寄存器需要log216=4位，源操作数中的寄存器直接寻址用掉4位，而目的操作数采用基址寻址也要指定
一个寄存器，同样用掉4位，则留给偏移址的位数为24-4-4=16位，而偏移址用补码表示，16位补码的表示范围为-32768~+32767，选A。
18．计算机共有32条指令，各个指令对应的微程序平均为4条，则指令对应的微指令为32*4=128条，而公共微指令还有2条，整个系统中微指令的条数一共为128+2=130条，所以需要⎡log2130⎤=8位才能寻址到130条微指令，答案选C。
19．数据线有32根也就是一次可以传送32bit/8=4B的数据，66MHz意味着有66M个时钟周期，而每个时钟周期传送两次数据，可知总线每秒传送的最大数据量为66M×2×4B=528MB，所以总线的最大数据传输率为528MB/s，选C。
20．猝发(突发)传输是在一个总线周期中，可以传输多个存储地址连续的数据，即一次传输一个地址和一批地址连续的数据，并行传输是在传输中有多个数据位同时在设备之间进行的传输，串行传输是指数据的二进制代码在一条物理信道上以位为单位按时间顺序逐位传输的方式，同步传输是指传输过程由统一的时钟控制，选C。
21．采用统一编址时，CPU访存和访问I/O端口用的是一样的指令，所以访存指令可以访问I/O端口，D选项错误，其他三个选项均为正确陈述，选D。
22．每400ns发出一次中断请求，而响应和处理时间为100ns，其中容许的延迟为干扰信息，因为在50ns内，无论怎么延迟，每400ns还是要花费100ns处理中断的，所以该设备的I/O时间占整个CPU时间的百分比为100ns/400ns=25%，选B。
23．采用静态优先级调度时，当系统总是出现优先级高的任务时，优先级低的任务会总是得不到处理机而产生饥饿现象；而短作业优先调度不管是抢占式或是非抢占的，当系统总是出现新来的短任务时，长任务会总是得不到处理机，产生饥饿现象，因此B、C、D都错误，选A。
24．三个并发进程分别需要3、4、5台设备，当系统只有(3-1)+(4-1)+(5-1)=9台设备时，第一个进程分配2台，第二个进程分配3台，第三个进程分配4台。这种情况下，三个进程均无法继续执行下去，发生死锁。当系统中再增加1台设备，也就是总共10台设备时，这最后1台设备分配给任意一个进程都可以顺利执行完成，因此保证系统不发生死锁的最小设备数为10。
25．trap指令、跳转指令和压栈指令均可以在用户态执行，其中trap指令负责由用户态转换成为内核态。而关中断指令为特权指令，必须在核心态才能执行，选D。
26．进程申请读磁盘操作的时候，因为要等待I/O操作完成，会把自身阻塞，此时进程就变为了阻塞状态，当I/O操作完成后，进程得到了想要的资源，就会从阻塞态转换到就绪态（这是操作系统的行为）。而降低进程优先级、分配用户内存空间和增加进程的时间片大小都不一定会发生，选A。
考研计算机真题
27．簇的总数为10GB/4KB=2.5M，用一位标识一簇是否被分配，则整个磁盘共需要2.5M 位，即需要2.5M/8=320KB，则共需要320KB/4KB=80个簇，选A。
28．虚实地址转换是指逻辑地址和物理地址的转换。增大快表容量能把更多的表项装入快表中，会加快虚实地址转换的平均速率；让页表常驻内存可以省去一些不在内存中的页表
从磁盘上调入的过程，也能加快虚实地址变换；增大交换区对虚实地址变换速度无影响，因此I、II正确，选C。
29．一个文件被用户进程首次打开即被执行了Open操作，会把文件的FCB调入内存，而不会把文件内容读到内存中，只有进程希望获取文件内容的时候才会读入文件内容；C、D明显错误，选B。
30．只有FIFO算法会导致Belady异常，选A。
31．管道实际上是一种固定大小的缓冲区，管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，并且只存在于内存中。它类似于通信中半双工信道的进程通信机制，一个管道可以实现双向的数据传输，而同一个时刻只能最多有一个方向的传输，不能两个方向同时进行。管道的容量大小通常为内存上的一页，它的大小并不是受磁盘容量大小的限制。当管道满时，进程在写管道会被阻塞，而当管道空时，进程读管道会被阻塞，因此选C。
32．多级页表不仅不会加快地址的变换速度，还因为增加更多的查表过程，会使地址变换速度减慢；也不会减少缺页中断的次数，反而如果访问过程中多级的页表都不在内存中，会大大增加缺页的次数，也并不会减少页表项所占的字节数(详细解析参考下段)，而多级页表能够减少页表所占的连续内存空间，即当页表太大时，将页表再分级，可以把每张页表控制在一页之内，减少页表所占的连续内存空间，因此选D。
补充：页式管理中每个页表项的大小的下限如何决定？
页表项的作用是到该页在内存的位置，以32位逻辑地址空间，字节为编址单位，一页4KB为例，地址空间内一共含有232B/4KB=1M页，则需要log21M=20位才能保证表示范围能容纳所有页面，又因为以字节作为编址单位，即页表项的大小≥⌈20/8⌉=3B。所以在这个条件下，为了保证页表项能够指向所有页面，那么页表项的大小应该大于3B，当然，也可以选择更大的页表项大小以至于让一个页面能够正好容下整数个页表项以方便存储（例如取成4B，那么一页正好可以装下1K个页表项），或者增加一些其他信息。
33．直接为会话层提供服务的即会话层的下一层，是传输层，选C。
34．主机00-e1-d5-00-23-a1向00-e1-d5-00-23-c1发送数据帧时，交换机转发表中没有00-e1-d5-00-23-c1这项，所以向除1接口外的所有接口广播这帧，即2、3端口会转发这帧，同时因为转发表中并没
有00-e1-d5-00-23-a1这项，所以转发表会把(目的地址00-e1-d5-00-23-a1，端口1)这项加入转发表。而当00-e1-d5-00-23-c1向00-e1-d5-00-23-a1发送确认帧时，由于转发表已经有00-e1-d5-00-23-a1这项，所以交换机只向1端口转发，选B。
35．由香农定理可知，信噪比和频率带宽都可以限制信道的极限传输速率，所以信噪比和频率带宽对信道的数据传输速率是有影响的，A、B错误；信道的传输速率实际上就是信号的发送速率，而调制速度也会直接限制数据的传输速率，C错误；信号的传播速度是信号在信道上传播的速度，与信道的发送速率无关，选D。
36．考虑制约甲的数据传输速率的因素，首先，信道带宽能直接制约数据的传输速率，传输速率一定是小于等于信道带宽的；其次，主机甲乙之间采用后退N帧协议，那么因为甲乙主机之间采用后退N帧协议传输数据，要考虑发送一个数据到接收到它的确认之前，最多能发送多少数据，甲的最大传输速率受这两个条件的约束，所以甲的最大传输速率是这两个值中小的那一个。甲的发送窗口的尺寸为1000，即收到第一个数据的确认之前，最多能发送1000个数据帧，也就是发送1000*1000B=1MB的内容，而从发送第一个帧到接收到它的确认的时间是一个往返时延，也就是50+50=100ms=0.1s，即在100ms中，最多能传输1MB的数据，因此此时的最大传输速率为1MB/0.1s=10MB/s=80Mbps。信道带宽为100Mbps，所以答案为min{80Mbps,100Mbps}=80Mbps，选C。
37．把收到的序列分成每4个数字一组，即为(2,0,2,0)、(0,-2,0,-2)、(0,2,0,2)，因为题目