1、2009 年考研计算机专业（基础综合）真题试卷及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是_。（A）栈（B）队列（C）树（D）图2 设栈 S 和队列 Q 的初始状态均为空，元素 a，b ，c ，d，e，f，g 依次进入栈 s。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是b，d，c，f，e ，a，g，则栈 S 的容量至少是_。
2、（A）1（B） 2（C） 3（D）43 给定二叉树如图 A-1 所示。设 N 代表二叉树的根，L 代表根结点的左了树，R 代表根结点的右子树。若遍历后的结点序列是 3，1，7，5，6，2，4，则其遍历方式是_。（A）LRN（B） NRL（C） RLN（D）RNL4 下列二叉排序树中，满足平衡二叉树定义的是_。（A）（B）（C）（D）5 已知一棵完全二叉树的第 6 层(设根为第 1 层)有 8 个叶结点，则该完全二叉树的结点个数最多是_。（A）39（B） 52（C） 111（D）1196 将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的：父结点的父结点，则在原来的森林中，u 和
3、v 可能具有的关系是_。I父子关系兄弟关系u 的父结点与 v 的父结点是兄弟关系（A）只有（B） I 和（C） I 和（D）I、和7 下列关于无向连通图特性的叙述中，正确的是_。I所有顶点的度之和为偶数边数大于顶点个数减 1至少有一个顶点的度为 1（A）只有 I（B）只有 （C） I 和（D）I 和8 下列叙述中，不符合 m 阶 B 树定义要求的是_。（A）根结点最多有 m 棵子树（B）所有叶结点都在同一层上（C）各结点内关键字均升序或降序排列（D）叶结点之间通过指针链接9 已知关键字序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字 3，调整后得到的小根堆是_。
4、（A）3，5，12，8，28，20，15，22，19（B） 3，5，12，19，20，15，22，8，28（C） 3，8，12，5，20，15，22，28，19（D）3，12，5，8，28，20，15，22，1910 若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是_。（A）冒泡排序（B）插入排序（C）选择排序（D）二路归并排序11 冯.诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是_。（A）指令操作码的译码结果（B）指令和数据的寻址方式（C）指令周期的不同阶段（D）指令和数据所在的存
5、储单元12 一个 C 语言程序在一台 32 位机器卜运行。程序中定义了三个变量 x、y 和 z，其中 x 和 z 为 int 型，y 为 short 型。当 x=127，y=一 9 时，执行赋值语句 z=x+y 后，x、y 和 z 的值分别是 _。（A）x=0000007FH，v=FFF9H，z=00000076H（B） x=0000007FH，v=FFF9H ，z=FFFF0076H（C） x=0000007FH，v=FFF7H ，z=FFFF0076H（D）x=0000007FH，v=FFF7H，z=00000076H13 浮点数加、减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等
6、步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为 5 位和 7 位(均含 2 位符号位)。若有两个数 x=272932，Y=2 558，则用浮点加法计算 x+Y 的最终结果是_。（A）1111100010（B） 1.1101e+009（C） 1e+010（D）发生溢出14 某计算机的 Cache 共有 16 块，采用 2 路组相联映射方式(即每组 2 块)。每个主存块大小为 32B，按字节编址。主存 129 号单元所在主存块应装入到的 Cache 组号是_。（A）0（B） 1（C） 4（D）615 某计算机主存容量为 64KB，其中 ROM 区为 4KB，其余为 RAM 区，按字节编址。
7、现要用 2K8 位的 ROM 芯片和 4K4 位的 RAM 芯片来设计该存储器，则需要上述规格的 ROM 芯片数和 RAM 芯片数分别是_。（A）1、15（B） 2、15（C） 1、30（D）2、3016 某机器字长为 16 位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一个字节 PC 自动加 1。若某转移指令所在主存地址为 2000H，相对位移量字段的内容为 06H，则该转移指令成功转移后的目标地址是 _。（A）2006H（B） 2007H（C） 2008H（D）2009H17 下列关于 RISC 的叙述中，错误的
8、是 _。（A）RISC 普遍采用微程序控制器（B） RISC 大多数指令在一个时钟周期内完成（C） RISC 的内部通用寄存器数量相对 CISC 多（D）RISC 的指令数、寻址方式和指令格式种类相对 CISC 少18 某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间(忽略各功能段之间的缓存时间)分别为 90ns、80ns、70ns、和 60ns，则该计算机的 CPU 时钟周期至少是_。（A）90ns（B） 80ns（C） 0ns（D）60ns19 相对于微程序控制器，硬布线控制器的特点是_。（A）指令执行速度慢，指令功能的修改和扩展容易（B）指令执行速度慢，指令功能的修改和扩展难
9、（C）指令执行速度快，指令功能的修改和扩展容易（D）指令执行速度快，指令功能的修改和扩展难20 假设某系统总线在一个总线周期中并行传输 4B 信息，一个总线周期占用 2 个时钟周期，总线时钟频率为 10MHz，则总线带宽是_。（A）10MBs（B） 20MBs（C） 40MBs（D）80MBs21 假设某计算机的存储系统由 Cache 和主存组成，某程序执行过程中访存 1000 次，其中访问 Cache 缺失( 未命中)50 次，则 Cache 的命中率是_。（A）5%（B） 9.50%（C） 50%（D）95%22 1F 列选项中，能引起外部中断的事件是_。（A）键盘输入（B）除数为 0（C
10、）浮点运算下溢（D）访存缺页23 单处理机系统中，可并行的是_。I 进程与进程处理机与设备处理机与通道设备与设备（A）I、和（B） I、和（C） I、和（D）、和24 下列进程调度算法中，综合考虑进程等待时间和执行时间的是_。（A）时间片轮转调度算法（B）短进程优先调度算法（C）先来先服务调度算法（D）高响应比优先调度算法25 某计算机系统中有 8 台打印机，由 K 个进程竞争使用，每个进程最多需要 3 台打印机。该系统可能会发生死锁的 K 的最小值是_ 。（A）2（B） 3（C） 4（D）526 分区分配内存管理方式的主要保护措施是_。（A）界地址保护（B）程序代码保护（C）数据保护（D）栈
11、保护27 一个分段存储管理系统中，地址长度为 32 位，其中段号占 8 位，则最大段长是_。（A）2 8B（B） 216B（C） 224B（D）2 32B28 下列文件物理结构中，适合随机访问且易于文件扩展的是_。（A）连续结构（B）索引结构（C）链式结构且磁盘块定长（D）链式结构且磁盘块变长29 假设磁头当前位于第 105 道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为 35，45，12，68，110，180，170，195，采用 SCAN 调度(电梯调度)算法得到的磁道访问序列是_。（A）110，170，180，195，68，45，35，12（B） 110，68，45，35，
12、12，170，180，195（C） 110，170，180，195，12，35，45，68（D）12，35，45，68，110，170，180，19530 文件系统中，文件访问控制信息存储的合理位置是_。（A）文件控制块（B）文件分配表（C）用户口令表（D）系统注册表31 设文件 F1 的当前引用计数值为 1，先建立 F1 的符号链接(软链接)文件 F2，再建立 F1 的硬链接文件 F3，然后删除 F1。此时，F2 和 F3 的引用计数值分别是_。（A）0、1（B） 1、1（C） 1、2（D）2、132 程序员利用系统调用打开 IO 设备时，通常使用的设备标识是_。（A）逻辑设备名（B）物理设
13、备名（C）主设备号（D）从设备号33 在 OSI 参考模型中，自下而上第一个提供端到端服务的层次是_。（A）数据链路层（B）传输层（C）会话层（D）应用层34 在无噪声情况下，若某通信链路的带宽为 3kHz，采用 4 个相位，每个相位具有4 种振幅的 QAM 调制技术，则该通信链路的最大数据传输速率是_。（A）12kbits（B） 24kbits（C） 48kbits（D）96kbits35 数据链路层采用后退 N 帧(GBN)协议，发送方已经发送了编号为 07 的帧。当计时器超时时，若发送方只收到 0、2、3 号帧的确认，则发送方需要重发的帧数是_。（A）2（B） 3（C） 4（D）536
14、以太网交换机进行转发决策时使用的 PDU 地址是 _。（A）目的物理地址（B）目的 lP 地址（C）源物理地址（D）源 IP 地址37 在一个采用 CSMACD 协议的网络中，传输介质是一根完整的电缆，传输速率为 1Gbits，电缆中的信号传播速度为 200000kms 。若最小数据帧长度减少800bit，则最远的两个站点之间的距离至少需要_。（A）增加 160m（B）增加 80m（C）减少 160m（D）减少 80m38 主机甲与主机乙之间已建立一个 TCP 连接，主机甲向主机乙发送了两个连续的TCP 段，分别包含 300B 和 500B 的有效载荷，第一个段的序列号为 200，主机乙正确接
15、收到两个段后，发送给主机甲的确认序列号是_。（A）500（B） 700（C） 800（D）100039 一个 TCP 连接总是以 1KB 的最大段长发送 TCP 段，发送方有足够多的数据要发送。当拥塞窗口为 16KB 时发生了超时，如果接下来的 4 个 RTT(往返时间)时间内的 TCP 段的传输都是成功的，那么当第 4 个 RTT 时间内发送的所有 TCP 段都得到肯定应答时，拥塞窗口大小是_。（A）7KB（B） 8KB（C） 9KB（D）16KB40 FTP 客户和服务器间传递 FTP 命令时，使用的连接是 _。（A）建立在 TCP 之上的控制连接（B）建立在 TCP 之上的数据连接（C）
16、建立在 UDP 之上的控制连接（D）建立在 UDP 之上的数据连接二、综合应用题41-47 小题，共 70 分。41 带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题足找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：设最短路径初始时仅包含初始顶点，令当前顶点u 为初始顶点；选择离 u 最近且尚未在最短路径中的一个顶点 v，加入到最短路径中，修改当前顶点 u=v： 重复步骤，直到 u 是目标顶点时为止。请问上述方法能否求得最短路径? 若该方法可行，请证明之；否则，请举例说明。41 已知一个带有表头结点的单链表，结点结构为：
17、假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点(k 为正整数)。若查找成功，算法输出该结点的data 域的值，并返回 1；否则，只返回 0。要求：42 描述算法的基本设计思想。43 描述算法的详细实现步骤。44 根据设计思想和实现步骤，采用程序设计语言描述算法(使用 c、c+ 或 Java 语言实现)，关键之处请给出简要注释。44 某计算机的 CPU 主频为 500MHz，CPI 为 5(即执行每条指令平均需 5 个时钟周期)。假定某外设的数据传输率为 05MBs，采用中断方式与主机进行数据传送，以 32 位为传输单位
18、，对应的中断服务程序包含 18 条指令，中断服务的其他开销相当于 2 条指令的执行时间。请回答下列问题，要求给出计算过程。45 在中断方式下，CPU 用于该外设 IO 的时间占整个 CPU 时间的百分比是多少?46 当该外设的数据传输率达到 5MBs 时，改用 DMA 方式传送数据。假定每次DMA 传送块大小为 5000B，且 DMA 预处理和后处理的总开销为 500 个时钟周期，则 CPU 用于该外设 IO 的时间占整个 CPU 时间的百分比是多少?(假设 DMA 与CPU 之间没有访存冲突)47 某计算机字长为 16 位，采用 16 位定长指令字结构，部分数据通路结构如图 A-2 所示，图
19、中所有控制信号为 1 时表示有效、为 O 时表示无效。例如，控制信号MDRinE 为 1 表示允许数据从 DB 打入 MDR，MDRin 为 l 表示允许数据从内总线打入 MDR。假设 MAR 的输出一直处于使能状态。加法指令“ADD(R1)，R0”的功能为(R0)+(R1)一(R1)，即将 R0 中的数据与 R1 的内容所指主存单元的数据相加，并将结果送入 R1 的内容所指主存单元中保存。表 A-1 给出了上述指令取指和译码阶段每个节拍(时钟周期) 的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。48 三个进程 P1、P2 、P3 互斥使用一个包含
20、N(NO)个单元的缓冲区。Pl 每次用produce()生成一个正整数并用 put()送入缓冲区某一空单元中： P2 每次用 getodd()从该缓冲区中取出一个奇数并用 countodd()统计奇数个数； P3 每次用 geteven()从该缓冲区中取出一个偶数并用 counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。48 请求分页管理系统中，假设某进程的页表内容见表 A 一 2。页面大小为4KB，一次内存的访问时间为 100ns，一次快表(TLB)的访问时间为 10ns，处理一次缺页的平均时间为 10Sns(已含更新
21、 TLB 和页表的时间)，进程的驻留集大小固定为 2，采用最近最少使用置换算法(LRu)和局部淘汰策略。假设 TLB 初始为空；地址转换时先访问 TLB，若 TLB 未命中，再访问页表(忽略访问页表之后的TLB 更新时间)：有效位为 0 表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：49 依次访问上述三个虚地址，各需多少时间?给出计算过程。50 基于上述访问序列，虚地址 1565H 的物理地址是多少 ?请说明理由。50 某网络拓扑如图 A-3 所示，路由器 R1 通过接口 E1、E2 分别连接局域
22、网 1、局域网 2，通过接口 LO 连接路由器 R2，并通过路由器 R2 连接域名服务器与互联网。R1 的 L0 接口的 IP 地址是 20211821，R2 的 L0 接口的 IP 地址是20211822，L1 接口的 IP 地址是 130111201，E0 接口的 IP 地址是20211831，域名服务器的 IP 地址是 202118 32。R1 和 R2 的路由表结构为：51 将 IP 地址空间 2021181024 划分为 2 个子网，分别分配给局域网 1、局域网 2，每个局域网需分配的 IP 地址数不少于 120 个。请给出子网划分结果，说明理由或给出必要的计算过程。52 请给出 R
23、1 的路由表。使其明确包括到局域网 1 的路由、局域网 2 的路由、域名服务器的主机路由和互联网的路由。53 请采用路由聚合技术，给 LHR2 到局域网 1 和局域网 2 的路由。2009 年考研计算机专业（基础综合）真题试卷答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 B【试题解析】 考查栈和队列的特点及应用。C 和 D 直接排除，缓冲区的特点需要先进先出，若用栈，先进入缓冲区的数据则要排队到最后才能打印，不符题意，故选 B。2 【正确答案】 C【试题解析】 考查栈的最大递归深度。时刻注意栈的
24、特点是先进后出。出入栈的详细过程见表 A-3。栈内的最大深度为 3，故栈 S 的容量至少是 3。3 【正确答案】 D【试题解析】 考查二叉树的特殊遍历。分析遍历后的结点序列，可以看出根结点是在中间被访问的，而右子树结点在左子树之前，得遍历的方法是 RNL。本题考查的遍历方法并不是二叉树的三种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。4 【正确答案】 B【试题解析】 考查平衡二叉树的定义。根据平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过 1。而其余三个答案均可以找到不符合的结点。5 【正确答案】 C【试题解析】 考查完全二叉树的特点。完全二叉树比满二叉树只是在最下面一
25、层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第 6 层有叶结点则完全二叉树的高度可能为 6 或 7，显然树高为 7 时结点更多。若第 6 层上有 8 个叶结点，则前六层为满二叉树，而第 7 层缺失了 82=16 个叶结点，故完全二叉树的结点个数最多为 27 一 1-16=111 个结点。6 【正确答案】 B【试题解析】 考查森林和二叉树的转换。森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。情形 I：若结点 v 是结点 u 的第二个孩子结点，在转换时，结点v 就变成结点 u 第一个孩子
26、的右孩子，符合要求。情形：结点 u 和 v 是兄弟结点的关系，但二者之中还有一个兄弟结点 k，则转换后，结点 v 就变为结点 k 的右孩子，而结点 k 则是结点 u 的右孩了，符合要求。情形 ：结点 v 的父结点要么是原先的父结点或兄弟结点。若结点 u 的父结点与 v 的父结点是兄弟关系，则转换之后，不可能出现结点 u 是结点 v 的父结点的父结点。7 【正确答案】 A【试题解析】 考查无向连通图的特性。每条边都连接了两个结点，则在计算顶点的度之和时，这条边都被计算了两次，故所有顶点的度之和为边数的两倍，显然必为偶数。而和则不一定正确，如对顶点数 N1 无向完全图不存在一个顶点的度为 1，并且
27、边数与顶点数的差要大于 1。8 【正确答案】 D【试题解析】 考查 m 阶 B 树的定义。A、B 和 C 都是 B 树的特点，而选项 D 则是 B+树的特点。注意区别 B 树和 B+树各自的特点。9 【正确答案】 A【试题解析】 考查小根堆的调整操作。小根堆在逻辑上可以用完全二叉树来表示，根据关键序列得到的小顶堆的二叉树形式如图 A-4a 所示。插入关键字 3 时，先将其放在小顶堆的末端，再将该关键字向上进行调整，得到的结果如图 A-4b 所示。所以，调整后的小顶堆序列为 3，5，12，8，28，20，15，22，19。10 【正确答案】 B【试题解析】 考查各排序算法的特点。解答本题之前要对
28、不同排序算法的特点极为清楚。对于冒泡排序和选择排序而言，每趟过后都能确定一个元素的最终位置，而由题目中所说，前两个元素和后两个元素均不是最小或最大的两个元素并按序排列。答案 D 中的二路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。插入排序在每趟排序结束后能保证前面的若干元素是有序的，而此时第二趟排序后，序列的前三个元素是有序的，符合其特点。11 【正确答案】 C【试题解析】 考查指令的执行过程。通常完成一条指令可分为取指阶段和执行阶段。在取指阶段通过访问存储器可将指令取出；在执行阶段通过访问存储器可以将操作数取出。这样，虽然指令和数据都是以二进制代
29、码形式存放在存储器中，但CPU 可以判断在取指阶段访问存储器取出的二进制代码是指令：在执行阶段访存取出的二进制代码是数据。12 【正确答案】 D【试题解析】 考查符号位的扩展。结合题干及选项可知，int 为 32 位，short 为16 位；又 C 语言的数据在内存中为补码形式，故 x、y 的机器数写为0000007FH、FFF7H 。执行 Z=X+y 时，由于 x 是 int 型，y 为 short 型，故需将 y的类型强制转换为 int，在机器中通过符号位扩展实现，由于 y 的符号位为 l，故在y 的前面添加 16 个 1，即可将 y 强制转换为 int 型，其十六进制形式为FFFFFFF
30、7H。然后执行加法，即 0000007FH+FFFFFFF7H=00000076H，其中最高位的进位 1 自然丢弃。故选 D。13 【正确答案】 D【试题解析】 考查浮点加法运算。根据题意，x 可记为 00，111：00，11101(分号前为阶码，分号后为尾数)，Y 可记为 00，101；00，10100。首先对阶，X、Y阶码相减，即 00，11100，101=00，111+11，0111=00，010，可知 x 的阶码比Y 的价码火 2，根据小阶向大阶看齐的原则，将 Y 的阶码加 2，尾数右移 2 位，可得 Y 为 00，111：00，00101。尾数相加，即 00， 11101+00，00
31、101=01，00010，尾数相加结果符号位为 01，故需进行右规。规格化，将尾数右移 1 位，阶码加 1，得 x+Y 为 01，000；00，1000，阶码符号位为 01，说明发生溢出。14 【正确答案】 C【试题解析】 考查 Cache 与主存的映射方式。由于 Cache 共有 16 块，采用 2 路组相联，因此共有 8 组，0，1，2，7。主存的某一字块按模 8 映射到 Cache某组的任一字块中，即主存的第 0，8，16字块可以映射到 Cache 第 0 组 2 个字块的任一字块中，而 129 号单元是位于第 4 块主存块中，因此将映射到 Cache 第4 组 2 个字块的任一一字块中
32、。15 【正确答案】 D【试题解析】 考查存储器的扩展。首先确定 ROM 的个数，ROM 区为 4KB，选用 2K8 位的 ROM 芯片， ，采用字扩展方式；60KB 的 RAM 区，选用 4K4 位的 RAM 芯片， ，采用字和位同时扩展方式。16 【正确答案】 C【试题解析】 考查相对寻址。相对寻址 EA=(PC)+A，首先要求的是取指令后 PC的值。转移指令由两个字节组成，每取一个字节 PC 自动加 1，因此取指令后 Pc值为 2002H，故 EA：(Pc)+A=2002H+06H=2008H。17 【正确答案】 A【试题解析】 考查 RISC：的特性。相对于 cISC 计算机，RISC
33、 计算机的特点是指令条数少；指令长度固定，指令格式和寻址种类少；只有取数存数指令访问存储器，其余指令的操作均在寄存器之间进行：CPU 中通用寄存器多；大部分指令在一个或者小于一个机器周期内完成：以硬布线逻辑为主，不用或者少用微程序控制。18 【正确答案】 A【试题解析】 考查流水线中时钟周期的特性。时钟周期应以最长的执行时间为准。否则用时长的流水段的功能将不能正确完成。19 【正确答案】 D【试题解析】 考查硬布线控制器的特点。硬布线控制器的速度取决于电路延迟，所以速度快：微程序控制器采用了存储程序原理，每条指令都要访控存，所以速度慢。硬布线控制器采用专门的逻辑电路实现，修改和扩展困难。20
34、【正确答案】 B【试题解析】 考查总线的基本概念。总线带宽是指单位时间内总线上可传输数据的位数，通常用每秒钟传送信息的字节数来衡量，单位可用字节秒(Bs) 表示。根据题意可知，在 2(110MHz)秒内传输了 4B。所以4B10MHz2=20M 。B s。21 【正确答案】 D【试题解析】 考查 Cache 的命中率。命中率=Cache 命中的次数所有访问次数，有了这个公式这道题就很容易看出，要注意的一点是看清题，题中说明的是缺失50 次，而不是命中 50 次，仔细审题是做对题的第一步。22 【正确答案】 A【试题解析】 考查中断的分类。选项中能引起外部中断的只能是输入设备键盘。23 【正确答
35、案】 D【试题解析】 考查并行性的限定。单处理器系统中只有一条指令流水线，一个多功能的操作部件，每个时钟周期只能完成一条指令，故进程与进程显然不可以并行。24 【正确答案】 D【试题解析】 考查几种基本的调度算法概念。高响应比优先调度算法，同时考虑每个进程的等待时间和需要的执行时间，从中选出响应比最高的进程投入执行。响应比 R 定义如下：响应比 R=(等待时间+执行时间)执行时间。25 【正确答案】 C【试题解析】 考查死锁的条件。这种题用到组合数学中鸽巢原理的思想，考虑最极端情况，因为每个进程最多需要 3 台打印机，如果每个进程已经占有了 2 台打印机，那么只要还有多的打印机，那么总能满足达
36、到 3 台的条件，所以，将 8 台打印机分给 K 个进程，每个进程有 2 台打印机，这个情况就是极端情况， K 为 4。26 【正确答案】 A【试题解析】 考查分区分配存储管理方式的保护措施。分区分配存储管理方式的保护措施是设置界地址寄存器。每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界，即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。27 【正确答案】 C【试题解析】 考查分段存储管理系统。段地址为 32 位二进制数，其中 8 位表示段号，则段内位移占用 32 位一 8 位=24
37、 位二进制数，故最大段长为 224B。28 【正确答案】 B【试题解析】 考查文件物理结构的特性。随机访问是索引结构的特性。29 【正确答案】 A【试题解析】 考查磁盘的调度算法。类似于电梯调度的思想。首先，磁头选择与当前磁头所在磁道距离最近的请求作为首次服务的对象(110)，当磁头沿途相应访问请求序列直到达到一端末(110，170，180，195)，再反向移动响应另一端的访问请求(68 ，45，35，12) 。30 【正确答案】 A【试题解析】 考查文件控制块的内容。在文件控制块中，通常含有以下三类信息，即基本信息、存取控制信息及使用信息。31 【正确答案】 B【试题解析】 考查软硬链接建立
38、的属性。建立符号链接(软链接)时，引用计数值直接复制：建立硬链接时，引用计数值加 1。删除文件时，删除操作对于符号链接是不可见的，这并不影响文件系统，当以后再通过符号链接访问时，发现文件不存在，直接删除符号链接；但是对于硬链接则不可以直接删除，引用计数值减 1，若值不为 0，则不能删除此文件，因为还有其他硬链接指向此文件。32 【正确答案】 A【试题解析】 考查系统调用的设备标识。用户程序对 IO 设备的请求采用逻辑设备名，而在程序实际执行时使用物理设备名。33 【正确答案】 B【试题解析】 考查 OSI 模型中传输层的功能。传输层提供应用进程间的逻辑通信，即端到端的通信。而网络层提供点到点的
39、逻辑通信。因此选 B。34 【正确答案】 B【试题解析】 考查奈氏准则和香农定理。采用 4 个相位，每个相位有 4 种幅度的QAM 调制方法，每个信号可以有 16 种变化，传输 4bit 的数据。根据奈奎斯特定理，信息的最大传输速率为 23kHz4bit=24kbits。35 【正确答案】 C【试题解析】 考查后退 N 帧协议的工作原理。在后退 N 帧协议中，发送方可以连续发送若干个数据帧，如果收到接收方的确认帧则可以继续发送。若某个帧出错，接收方只是简单的丢弃该帧及其后所有的后续帧，发送方超时后需重传该数据帧及其后续的所有数据帧。这里要注意，连续 ARQ 协议中，接收方一般采用累积确认的方式
40、，即接收方对按序到达的最后一个分组发送确认，因此题目中收到 3 的确认帧就代表编号为 0、1、2、3 的帧已接收，而此时发送方未收到 1 号帧的确认只能代表确认帧在返回的过程中丢失了，而不代表 1 号帧未到达接收方。因此需要重传的帧为编号是 4、5、6、7 的帧。36 【正确答案】 A【试题解析】 考查交换机的工作原理。交换机实质上是一个多端口网桥，工作在数据链路层，数据链路层使用物理地址进行转发，而转发通常都是根据目的地址来决定出端口。37 【正确答案】 D【试题解析】 考查 CSMACD 协议的工作原理。若最短帧长减少，而数据传输速率不变，则需要使冲突域的最大距离变短来实现争用期的减少。争
41、用期是指网络中收发节点间的往返时延，因此假设需要减少的最小距离为 s，单位为 m，则可以得到下式(注意单位的转换)：2s(210 8)=800(110 9)，因此可得 s=80，即最远的两个站点之间的距离最少需要减少 80m。38 【正确答案】 D【试题解析】 考查 TCP 的数据编号与确认。TCP 是面向字节流的，其选择确认(SelectiveACK)机制是接收端对字节序号进行确认，其返回的序号是接收端下一次期望接收的序号，因此主机乙接收两个段后返回给主机甲的确认序列号是 1000。39 【正确答案】 C【试题解析】 考查 TCP 的拥塞控制方法。无论在慢开始阶段还是在拥塞避免阶段，只要发送
42、方判断网络出现拥塞(其根据就是没有按时收到确认)，就要把慢开始门限 ssthresh 设置为出现拥塞时的发送方窗口值的一半 (但不能小于 2)。然后把拥塞窗口 cwnd 重新设置为 1，执行慢开始算法。这样做的目的就是要迅速减少主机发送到网络中的分组数，使得发生拥塞的路由器有足够时间把队列中积压的分组处理完毕。因此，在发送拥塞后，慢开始门限 ssthresh 变为 16KB2=8KB，发送窗口变为 lKB。在接下来的 3 个 RTT 内，拥塞窗口执行慢开始算法，呈指数形式增加到 8KB，此时由于慢开始门限 ssthresh 为 8KB，因此转而执行拥塞避免算法，即拥塞窗口开始“加法增大”。因此
43、第 4 个 RTT 结束后，拥塞窗口的大小为 9KB。40 【正确答案】 A【试题解析】 考查 FTP 协议的特点。FTP 协议是基于传输层 TCP 协议的。FTP的控制连接使用端口 21，用来传输控制信息(如连接请求，传送请求等)；数据连接使用端口 20，用来传输数据。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 该方法不一定能(或不能)求得最短路径。例如，对于图 A-5 所示的带权图，如果按照题中的原则，从 A 到 C 的最短路径是 A-B-C，事实上其最短路径是 A-D-C。42 【正确答案】 算法的基本设计思想：问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍
44、历，找到倒数第 k 个结点的位置。算法的基本设计思想：定义两个指针变量 p 和 q。初始时均指向头结点的下一个结点(链表的第一个结点)。p 指针沿链表移动，当 p 指针移动到第 k 个结点时，q 指针开始与 p 指针同步移动；当 p 指针移动到最后一个结点时，q 指针所指示结点为倒数第 k 个结点。以上过程对链表仅进行一遍扫描。43 【正确答案】 算法的详细实现步骤：count=0，p 和 q 指向链表表头结点的下一个结点：若 p 为空，转 ；若 count 等于 k，则 q 指向下一个结点：否则，count=count+1；p 指向下一个结点，转；若 count 等于 k，则查找成功，输出该
45、结点的 data 域的值，返回 1；否则，说明 k 值超过了线性表的长度，查找失败，返回 0；算法结束。44 【正确答案】 算法实现：typedef int ElemType ; 链表数据的类型定义typedef struct LNode 链表结点的结构定义ElemType data， 结点数据struct Lnode*link; 结点链接指针 *LinkList；int Searchk(LinkList list，int k)查找链表 list 倒数第 k 个结点，并输出该结点 data 域的值LinkList p=lis 七一link，q=list 一link， 指针 p、q 指示第一个结
46、点int COunt=O；while(p!=NULL) 遍历链表直到最后一个结点if(COUntlink;p=p 一link； 之后让 p、q 同步移动) whileif(COUntdata);return 1； Searchk【试题解析】 算法程序题，如果能够写出数据结构类型定义、正确的算法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。若所给出的算法采用一遍扫描方式就能得到正确结果，可给满分 15分；若采用两遍或多遍扫描才能得到正确结果的，最高给 10 分：若采用递归算法得到正确结果的，最高给 10 分：若实现算法的空间复杂度过高(使用了大小与 k
47、 有关的辅助数组)，但结果正确，最高给 10 分。45 【正确答案】 按题意，外设每秒传送 05MB，中断时每次传送 4B。中断方式下，CPU 每次用于数据传送的时钟周期为 518+52=100.为达到外设 05MBs的数据传输率，外设每秒申请的中断次数为 05MB4B=125000。1s 内用于中断的开销为 100x125000=12500000=125M 个时钟周期。 CPU 用于外设 IO 的时间占整个 CPU 时间的百分比为 125M 500M=2 5。46 【正确答案】 当外设数据传输率提高到 5MBs 时，改用 DMA 方式传送，每次 DMA 传送 5000B，ls 内需产生的 D
48、MA 次数为 5MB5000B=1000。CPU 用于DMA 处理的总开销为 1000500=500000=05M 个时钟周期。CPU 用于外设 IO的时间占整个 CPU 时间的百分比为 05M 500M=01。47 【正确答案】 一条指令的执行过程通常由取指、译码和执行 3 个步骤完成，本题中取指用 3 个节拍、译码用 1 个节拍，执行加法运算并把结果写入主存如何完成呢?包括划分执行步骤、确定完成的功能、要提供的控制信号，这是本题要测试的内容。为回答这个问题，首先要看清图 A-2 中给出的部件组成情况和信息传送的路径。要完成的功能是(R0)+(R1)(R1)，从图 A-2 中看到：1)R0、Rl 都有送自己内容到内总线的路径，控制信号分别是 R00ut 和 Rlout。2)ALu 加运算，2 个数据由工作寄存器 A 和内总线提供，控制信号是 Add；A 只接收内总线的内容，控制信号是 Ain；结果需存 AC，控制信号是 ACin：AC 的内容可送内总线，控制信号是 ACout。3)PC 可接收内总线的内容，还可增 1，控制信号是 PCin 和 PC+1，PC的内容可送内总线，控制信号是 PCout。4)指令寄存器 IR 可接收内总线的内容，控制信号是 IRin。5)读写存储器时，地址由 MAR 经 AB 提供，MAR 只接收总线上的信息，控制信号是 MARin。6)
