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