[考研类试卷]2012年考研计算机专业（基础综合）真题试卷及答案与解析.doc

1、2012 年考研计算机专业（基础综合）真题试卷及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 求整数 n(n0)阶乘的算法如下，其时间复杂度是intfact(intn)if(n是：、 、 、。请回答下列问题。54 访问时，对应的页框号是什么 ?55 访问时，对应的页框号是什么 ?说明理由。56 访问时，对应的页框号是什么 ?说明理由。57 该策略是否适合于时间局部性好的程序?说明理由。57 某文件系统空间的最大容量为 4TB(1T=240)，以磁盘块为基本分配单位，磁盘块大小为 lKB。文件控制块(FCB)包

2、含一个 512B 的索引表区。 请回答下列问题。58 假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节?可支持的单个文件最大长度是多少字节?59 假设索引表区采用如下结构：第 07 字节采用格式表示文件创建时预分配的连续存储空间，其中起始块号占 6B，块数占 2B；剩余 504 字节采用直接索引结构，一个索引项占 6B，则可支持的单个文件最大长度是多少字节?为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。59 主机 H 通过快速以太网连接 Internet，IP 地址为 19216808，服务器 S 的lP 地址为

3、 211687180。H 与 S 使用 TCP 通信时，在 H 捕获的其中 5 个 IP 分组如题 47 一 a 表所示。请回答下列问题。60 题 47 一 a 表中的 IP 分组中，哪几个是由 H 发送的? 哪几个完成了 TCP 连接建立过程?哪几个在通过快速以太网传输时进行了填充?61 根据题 47 一 a 表中的 IP 分组，分析 s 已经收到的应用层数据字节数是多少 ?62 若题 47 一 a 表中的某个 IP 分组在 S 发出时的前 40 字节如题 47 一 h 表所示，则该 IP 分组到达 H 时经过了多少个路由器?2012 年考研计算机专业（基础综合）真题试卷答案与解析一、单项选

4、择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 B【试题解析】 时间复杂度是由语句频度分析得来，递归算法中重复执行的语句主要是调用。所以递归算法的时间复杂度分析主要是分析递归函数的调用次数，并给出调用次数的函数 f(n)。从图中可以总结出该函数被调用了 n+1 次。2 【正确答案】 A【试题解析】 根据题目要求，栈中只存储操作符“+”，“-”，“*”，“”，“(” 和“)”，并不存储字母，这一点一定要看清楚。根据中缀表达式 a+ha*(c+d)ef)+g，可以利用栈将其转换为后缀表达式 ab+acd+ef 一*一 g

5、+，在转换过程中，栈中的操作符最多有 5 个。这种情况出现在第二个“+”号人栈后，栈中的操作符分别为：“一”，“*”，“(”，“(” ，“+”。3 【正确答案】 A【试题解析】 根据题中给出的二叉树的前序遍历 a、e、b、d、c 和后序遍历b、c、d、e、a 可以确定的是 a 为二叉树的根结点。那么根据前序遍历的访问次序为根结点、左子树、右子树，可以确定 e 为左子树或右子树的根结点，即根结点的孩子结点。假设 e 为左孩子结点，那么根据后序遍历的结果可知，b、e、d 一定在左子树上，不可能为 a 的孩子结点。若 e 为右子树的根结点，根据前序遍历结果可知，此二叉树没有左子树。4 【正确答案】

6、B【试题解析】 所有非叶结点的平衡因子均为 1，说明这棵平衡二叉树的非叶子结点左子树都比右子树多一层。因此，可以得到下一页的一个图，即次平衡二叉树上的结点总数为 20。5 【正确答案】 C【试题解析】 邻接表存储的有向图进行广度优先遍历的时间复杂度与图中的顶点个数以及边数都相关，因此答案选 C。6 【正确答案】 C【试题解析】 邻接矩阵存储有向图且主对角线以下的元素均为零，说明在此有向图中，l 为起点，n 为终点。任何一个顶点都不能到达比其号码小的顶点。在这种有向图中拓扑序列是存在的，但是可能唯一，也可能不唯一。例如，只有两个顶点的有向图，其拓扑序列就唯一。但是，三个顶点的有向图中拓扑序列就可

7、能不唯一了。7 【正确答案】 C【试题解析】 根据迪杰斯特拉(Dijkstra) 算法，可以得到以下过程：从 a 出发，与其直接相邻的是 b(2)、c(5) ，因此可以得到第一条最短路径的目标顶点是 b。从a，h出发，与其相邻的是 c(3)、d(5)、e(6) ，因此可以得到第二条最短路径的目标顶点是 c。从 a,b，c出发，与其相邻的是 d(5)、e(6)、f(4)，因此可以得到第三条最短路径的目标顶点是 f。从a，h，e，f 出发，与其相邻的是 d(5)、e(6)，因此可以得到第四、五条最短路径的目标顶点是 d、e。因此结点的顺序为 f、d、e，即C 选项。8 【正确答案】 A【试题解析】

8、 I最小生成树的代价唯一这种叙述是正确的。 如果利用kruskal 算法，那么权值最小的边一定会出现在所有的最小生成树中，但是利用prim 算法权值最小的边不一定会在最小生成树中。用 prim 算法从不同的顶点开始得到的最小生成树也不一定相同。最后，用 prim 算法和 kruskal 算法得到的最小生成树也有可能相同。9 【正确答案】 D【试题解析】 删除关键字 78，则需要对非叶子结点55，65进行分裂。将 65 与叶子结点60 ，62 合并成一个叶子结点 60，62，65，在 3 阶 B 树中，叶子结点中元素的个数不能多于 3 个，因此，叶子结点60，62，65需要进行分裂。将 62 转

9、到非叶子结点中，与 55 合并，即55，62 ；而 60 与 65 分别构成新的叶子结点。最右边的叶子结点的关键字为 65。10 【正确答案】 A【试题解析】 每一趟排序结束都至少能够确定一个元素最终位置的方法有：简单选择排序、快速排序、堆排序。11 【正确答案】 D【试题解析】 折半插入排序和直接插入排序二者之间的不同之处在于，查找插入位置时，折半插入排序进行元素的比较次数比较少。12 【正确答案】 D【试题解析】 基准程序 A 的运行时间为 100 秒， 90 秒为 CPU 时问，10 秒为IO 时间。由于 CPU 速度提高 50，则原来要执行 90 秒的任务，现在缩短为90(1+50)=

10、60 秒。由于 IO 速度不变，则运行基准程序 A 所耗费的时间为 10秒+60 秒=70 秒。13 【正确答案】 B【试题解析】 对于 unsignedshortx=65530；可先将其化成二进制：1111111111111010，对应的十六进制数为 FFFA，将其转换成 32 位 unsignedint 类型为 0000FFFAH。即 y 的机器数为： 0000FFFAH。14 【正确答案】 D【试题解析】 本题考查的是 IEEE754 单精度浮点数格式的表示范围，答案为D。15 【正确答案】 D【试题解析】 小端方式存放数据是指将最后一个字节存放在首地址处。显然，0xC008 存放的是

11、a 变量的最后一个字节，而 273 用十六进制表示为 00000111H。即将 a 分成 4 个字节存放，分别为：0x00，0x00，Ox01 ，0x11。而 0xC008 存放的是 a 变量的最后一个字节，即 0x11。在程序执行过程中，先给 reecorDa 分配内存，然后给 recorDh 分配内存，而 recorDa 占 4 个字节，recorDh占 1 个字节，那么存放 recorDc 的地址要偏移 5 个字节，但是在小端存放数据的方式中，则需要偏移 6 个字节，即 0xc008+0x0006=0xC00E。16 【正确答案】 A【试题解析】 闪存是电子可擦除只渎存储器(EEPROM

12、)的变种，闪存掉电后信息不丢失，是一种非易失性存储器。采用随机访问方式，可替代计算机外部存储器。闪存是一种半导体存储器，不能实现信息可读可写。删除或重写闪存中的内容是有条件的，而且有次数的限制。闪存与 EEPROM 不同的是，它能在字节水平上进行删除和重写而不是整个芯片擦写，这样闪存就比 EEPROM 的更新速度快。17 【正确答案】 C【试题解析】 根据 2 路组相连的映射方式和 LRu 替换策略可以得到，命中 cache的次数是 3 次。18 【正确答案】 C【试题解析】 操作控制字段采用字段直接编码法，要表示 33 个微命令，构成 5个互斥类，那么控制字段至少要 15 位。19 【正确答

13、案】 C【试题解析】 根据题中条件可知：总线频率为 100MHz，可以求得一个时钟周期的时间为 1100MHz=10ns。传送 128 位数据需要 12832=4 个时钟周期，而接受“主存写”命令需要一个时钟周期，因此一共需要 5 个时钟周期，即 50ns。20 【正确答案】 D【试题解析】 USB 的全称是 universalSerialBus，最多可连接 127 台外设，由于USB 支持热插拔、即插即用的优点，所以 USB 接口已经成为计算机的标准接口。USB 没备之所以会被大量应用，主要具有以下优点： 可以热插拔。携带方便。标准统一。 可以连接多个没备。21 【正确答案】 D【试题解析】

14、 IO 总线的数据线上传输的信息可以有：I0 接口中的命令字，IO 接口中的状态字，中断类型号。22 【正确答案】 B【试题解析】 中断隐指令完成的操作包括：保护断点，关中断，形成中断服务程序人口地址并送 PC。23 【正确答案】 C【试题解析】 进程切换是在核心态完成的，不能够在用户态下发生。24 【正确答案】 B【试题解析】 中断处理一定会保存程序状态字寄存器中的内容，而子程序调用不需要保存其内容。25 【正确答案】 B【试题解析】 虚拟存储器只能基于非连续分配技术。虚拟存储容量是虚拟的空间，与逻辑地址的位数相关，不会只受到内存或外存容量的限制。26 【正确答案】 A【试题解析】 IO 子

15、系统的四个层次分别是：用户级 IO 软件、设备无关软件、设备驱动程序、中断处理程序。27 【正确答案】 D【试题解析】 根据题中给出的条件，(R1、R2、R3)资源的总数为(18、6、22)。经计算系统将资源分配掉后，目前系统内所剩的资源数量为(2、3、3)。而进程 PO要完成所需的资源量为(2、3、7)；进程 Pl 要完成所需的资源量为(1、3、3)；进程P2要完成所需的资源量为(0、0、6) ；进程 P3 要完成所需的资源量为(2、2、1)；进程 P4 要完成所需的资源量为(1、1、0)。系统可以将资源分配给 P1、P3，设分配给 P3。当 P3 执行结束后，系统所剩的资源量为(4、3、7

16、)，可以分配给任意一个进程都能执行结束。即 P3、P4、P2、P1、P0 是安全序列。28 【正确答案】 A【试题解析】 用户进程通过 read 系统调用读取一个磁盘文件中的数据，若该文件的数据不在内存，则该进程进入睡眠等待状态。请求 read 系统调用会导致 CPU从用户态切换到核心态。29 【正确答案】 B30 【正确答案】 C【试题解析】 叙述错误的只有 C。31 【正确答案】 A【试题解析】 在系统中，进程是最小的资源分配的基本单位，不管系统是否支持线程。在支持线程的系统中，线程是调度的基本单位。同一进程中的各个线程拥有共同的共享地址空间。32 【正确答案】 B【试题解析】 重排 IO

17、 请求次序、预读和滞后写、优化文件物理的分布都能够改善磁盘设备的 IO 性能。在一个磁盘上设置多个分区，不能够改善磁盘的IO 性能。33 【正确答案】 B【试题解析】 IP 是直接为 ICMP 提供服务的协议。34 【正确答案】 C【试题解析】 物理层接口特性中用于描述完成每种功能的事件发生顺序的是过程特性。35 【正确答案】 A【试题解析】 以太网的 MAC 提供的是无连接的不可靠的服务。36 【正确答案】 B【试题解析】 在一个来回的 2270ms 时间内，发送方可以发送至少 9 个 128 字节的数据帧。帧序号 8 需要用 4 位二进制数表示。37 【正确答案】 C【试题解析】 IP 路

18、由器运行路由协议，更新设备路由表。当检测到网络发生拥塞时，合理丢弃 IP 分组。路由器根据收到的 IP 分组的目的 IP 地址，将其转发至合适的输出线路上。但是 IP 路由器只是尽最大努力交付数据报，不会进行差错校验，也不能确保传输的 lP 分组不丢失。38 【正确答案】 A【试题解析】 ARP 的功能：根据 IP 地址查询 MAC 地址。39 【正确答案】 D【试题解析】 分析题目可知，主机 IP 为 180807755，子网掩码为2552552520，网络 IP 为 18080760。如果主机向子网发送广播分组，则目的 IP 地址的主机号要全部置 1，即为 1808079255。40 【正

19、确答案】 D【试题解析】 发送电子邮件时，使用的是 SMTP 协议；接收电子邮件时使用的是 POP3 协议。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 6 个表的合并顺序如下页图所示。根据下页图中的哈夫曼树，6 个序列的合并过程为：第 1 次合并：表 A 与表 B 合并，生成含 45 个元素的表 AB；第 2 次合并：表 AB 与表 c 合并，生成含 85 个元素的表 ABC；第 3 次合并：表 D与表 E 合并，生成含 110 个元素的表 DE；第 4 次合并：表 ABc 与表 DE 合并，生成含 195 个元素的表 ABCDE； 第 5 次合并：表ABcDE 与表 F

20、 合并，生成含 395 个元素的最终表。由于合并两个长度分别为 m 和n 的有序表，最坏情况下需要比较 m+n1 次，故最坏情况下比较的总次数计算如下：第次合并：最多比较次数=10+35 一 1=44 第 2 次合并：最多比较次数=45+401=84 第 3 次合并：最多比较次数 =50+601=109 第 4 次合并：最多比较次数=85+110 一 1=194 第 5 次合并：最多比较次数 =195+200 一 1=394 比较的总次数最多为：44+84+109+194+394=825。42 【正确答案】 各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依

21、赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。43 【正确答案】 给出算法的基本设计思想：分别求出 str1 和 str2 所指的两个链表的长度 m 和 n；将两个链表以表尾对齐：令指针，p、q 分别指向 sfr1 和 str2的头结点，若 mn，则使 Jp 指向链表中的第 m 一 n+1 个结点；若 mn；mm-)术使 P 指向的链表与 q 指向的链表等长*P=P 一 next：for(q=str2；mnext：while(p-next!=NULL&p-next!=q-next)*查找共同后缀起始点*P=p-next； *两个指

22、针同步向后移动 *q=q 一 next：一next；*返回共同后缀的起始点 *returnPnextintlistlen(SNODE*head)*求链表长度*intlen=0；while(head-next!=NULL)len+：head=head-next；returnlen；45 【正确答案】 说明算法的时间复杂度：参考答案的时间复杂度为：O(m+n)或O(max(m，n)。其中 m、n 分别为两个链表的长度。46 【正确答案】 平均每秒 CPU 执行的指令数为：80M4=20M，故 MIPS 数为20；平均每秒 cache 缺失的次数为：20M15(199)=300000=300K ；当

23、 cache缺失时，CPU 访问主存，主存与 Cache 之问以块为单位传送数据，此时，主存带宽为：l6B300k s=48MBs。在不考虑 DMA 传输的情况下，主存带宽至少达到 48MB s 才能满足 CPU 的访存要求。47 【正确答案】 平均每秒钟“缺页” 异常次数为： 30000000005=1 5 次；因为存储器总线宽度为 32 位，所以，每传送 32 位数据，磁盘控制器发一次 DMA 请求，故平均每秒磁盘 DMA 请求的次数至少为：154KB4B=15K=1536。48 【正确答案】 CPU 和 DMA 控制器同时要求使用存储器总线时，DMA 请求优先级更高；因为，若 DMA 请

24、求得不到及时响应，I O 传输数据可能会丢失。49 【正确答案】 4 体交叉存储模式能提供的最大带宽为：44B50ns=320MBs。50 【正确答案】 x 的机器码为x =1111110111111111B，即指令执行前(R1)=FDFFH，右移 1 位后为 1111111011111111B，即指令执行后(R1)=FEFFH。51 【正确答案】 至少需要 4+(5 一 1)=8 个时钟周期数。52 【正确答案】 I，的 ID 段被阻塞的原因：因为 I3 与 I1 和 I2 都存在数据相关，需等到 I1 和 I2 将结果写回寄存器后，I 3 才能读寄存器内容，所以 I3 的 ID 段被阻塞。

25、I4 的 IF 段被阻塞的原因：因为 I4 的前一条指令 I3 在 ID 段被阻塞，所以 I4 的 lF 段被阻塞。53 【正确答案】 术 x 操作有左移和加法两种实现方法，故 x=2*x+a 对应的指令序列为： I 1LOADR1，x I 2LOADR2，a I3SHLR1或者 ADDR1，R1 I4ADDR1，R2 I 5sTORER2，x54 【正确答案】 页框号为 21。因为起始驻留集为空，而 0 页对应的页框为空闲链表中的第三个空闲页框(21)，其对应的页框号为 2l。55 【正确答案】 页框号为 32。理由：因 1110，故发生第三轮扫描，页号为 l 的页框在第二轮已处于空闲页框链

26、表中，此刻该页又被重新访问，因此应被重新放回到驻留集中。其页框号为 32。56 【正确答案】 页框号为 41。理由：因为第 2 页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框 4l，页框号为 41。57 【正确答案】 适合。理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。58 【正确答案】 文件系统存储空间共有块数 2422 10=232。为表示 232 个块号，索引表项占 328=4B 。5l2 字节可存放 27 个索引表项，故最大文件长度：27210=217B=128KB。59 【正确答案】 块号占 6 字节，块数占 2 字

27、节的情形下，最大文件长度：216210+(5046)2 10=64MB+84KB=65620KB。合理的起始块号和块数所占字节数分别为 4，4(或 1，7 或 2，6 或 3，5)。 理由：块数占 4B 或以上，就可表示 4TB大小的文件长度，达到文件系统的空间上限。60 【正确答案】 由于题 47 一 a 表中 1、3、4 号分组的源 IP 地址均为19216808(cOa80008H) ，所以 1、3、4 号分组是由 H 发送的；题 47 一 a 表中 1 号分组封装的 TCP 段的 FLAG 为 02H(即 syn=1，ack=O)，seq=846b41c5H ，2号分组封装的 TCP

28、段的 FLAG 为 12H(即 syn=1，ack=1)，seq=e0599femack=846b41c6H，3 号分组封装的 TCP 段的 FLAG 为 l0H(即 ack=1)，seq=846b41c6H，ack=e0599ffOH ，所以 1、2、3 号分组完成了 TCP 连接建立过程；由于快速以太网数据帧有效载荷的最小长度为 46 字节，表中 3、5 号分组的总长度为 40(28H)字节，小于 46 字节，其余分组总长度均大于 46 字节，所以 3、5 号分组在通过快速以太网传输时进行了填充。61 【正确答案】 由 3 号分组封装的 TCP 段可知，发送应用层数据初始序号为846h41c6H，由 5 号分组封装的 TCP 段可知，ack 为 846b41d6H，所以 s 已经收到的应用层数据的字节数为 846h41d6H 一 846b41c6H=10H=16B。62 【正确答案】 由于 s 发出的 IP 分组的标识=6811 日，所以该分组所对应的是题47 一 a 表中的 5 号分组。 S 发出的 IP 分组的 TTL=40H=64，5 号分组的TTL=31H=49，6449=15。所以，可以推断该 IP 分组到达 H 时经过了 15 个路由器。