2009年计算机408统考考研真题及答案解析.pdf

返回 相似
第1页 / 共17页
第2页 / 共17页
第3页 / 共17页
第4页 / 共17页
第5页 / 共17页
点击查看更多>>
资源描述:
2009 年全 国硕 士研 究 生入 学 统一 考试 计 算机 科学 与 技术 学科联考 计 算机 学科 专 业基 础综 合 试题 一 、单 项选 择题 第 140 小题 , 每小 题 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 .1 B .2 C .3 D .4 3. 给定二叉 树 如 右 图所示 。设 N 代表二 叉树的 根,L 代 表根结 点的左 子树,R 代 表根结 点的右子 树。若 遍历后 的结点 序列 是 3 ,1 ,7 ,5 ,6 ,2 ,4 ,则 其遍历 方式是 。 A .LRN B .NRL C .RLN D .RNL 4. 下列二叉 排序树 中,满 足平衡 二叉 树 定义的 是______ 。 5. 已知一棵 完全二 叉树的 第 6 层 (设 根为 第 1 层 ) 有 8 个叶结 点, 则 该 完全 二叉树 的结 点个数 最多是______ 。 A . 39 B .52 C .111 D .119 6. 将森林转 换为对 应的二 叉树, 若在二 叉树中 ,结 点 u 是结 点 v 的 父结点 的父结 点, 则在原 来的森 林中,u 和 v 可能 具有的 关系是______ 。 Ⅰ. 父子 关系 Ⅱ . 兄弟关 系 Ⅲ.u 的父 结点 与 v 的父 结点是 兄弟关 系 A . 只有 Ⅱ B . Ⅰ 和 Ⅱ C . Ⅰ 和 Ⅲ D . Ⅰ 、 Ⅱ 和 Ⅲ 7. 下列关于 无向连 通图特 性的叙 述中, 正确的 是______ 。 I. 所有顶点 的度之 和为偶 数 II. 边数大于 顶点个 数减 1 III. 至少有一 个顶点 的度 为 1 A . 只 有 Ⅰ B . 只 有 Ⅱ C . Ⅰ和 Ⅱ D . Ⅰ 和Ⅲ 8. 下列叙述 中, 不 . 符合 m 阶 B 树 定义要 求的是______ 。 A .根节点最 多有 m 棵 子树 B . 所有叶 结点都 在同一 层上 C . 各结点 内关键 字均升 序或降 序排列 D .叶 结点之 间通过 指针链 接 9. 已知关键 字序列 5 ,8 ,12 ,19 ,28 ,20 ,15 ,22 是小 根堆(最小 堆), 插入关 键字 3 , 调整后 得到的 小根 堆是______ 。 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 . 指 令和数 据所在 的存储 单元 12. 一个 C 语言程 序在一 台 32 位机 器上运 行。 程序 中定义 了三 个变 量 x 、 y 和 z , 其 中 x 和 z 为 int 型, y 为 short 型。当 x127 ,y-9 时 ,执行 赋值语 句 zxy 后,x 、y 和 z 的值分 别是 。 A . x0000007FH ,yFFF9H ,z00000076H B . x0000007FH ,yFFF9H ,zFFFF0076H C . x0000007FH ,yFFF7H ,zFFFF0076H D . x0000007FH ,yFFF7H ,z00000076H 13. 浮点数加 、 减 运算过 程一般 包括 对阶、 尾数运 算、规 格化 、舍入 和判溢 出等 步骤。 设浮点 数的阶 码和 尾数 均采用补 码表示 ,且位 数分别 为 5 位和 7 位 (均 含 2 位符 号位)。 若有两 个数 X2 7 29/32 ,Y2 5 5/8 ,则 用浮点加 法计 算 XY 的 最终结 果是 。 A .00111 1100010 B .00111 0100010 C .01000 0010001 D .发 生溢出 14. 某计算机 的 Cache 共有 16 块, 采 用 2 路组 相联映 射方式 ( 即每 组 2 块 ) 。 每个 主存 块大小 为 32 字节,按字 节编址。 主存 129 号单 元所在 主存块 应装入 到的 Cache 组 号是 。 A .0 B .1 C .4 D .6 15. 某计算机 主存容 量为 64KB , 其 中 ROM 区为 4KB , 其余 为 RAM 区, 按 字节编 址。 现要 用 2K 8 位的 ROM 芯片 和 4K 4 位的 RAM 芯片 来 设计 该 存 储器 , 则需 要 上 述规 格的 ROM 芯 片 数和 RAM 芯 片 数 分别 是 。 A .1 、15 B .2 、15 C .1 、30 D .2 、30 16. 某机器字 长 16 位, 主存按 字节编 址,转 移指令 采用相 对寻 址,由 两个字 节组成 ,第一 字节为 操作码 字段, 第二字节 为相对 位移量 字段。 假定取 指令时 ,每取 一个字 节 PC 自动加 1 。 若某 转移指 令所在 主存地 址为 2000H ,相对 位移量 字段的 内容 为 06H ,则 该转移 指令成 功转移 后的目 标地址 是_____ 。 A .2006H B .2007H C .2008H D .2009H 17. 下列关 于 RISC 的叙 述中, 错误 .. 的是 。 A .RISC 普 遍采用 微程序 控制 器 B .RISC 大多数 指令在 一个时 钟周期 内完成 C .RISC 的内部 通用寄 存器数 量相 对 CISC 多 D .RISC 的 指令数 、寻址 方式和 指令格 式种类 相对 CISC 少 18. 某计算机 的指 令流水 线由四 个功 能段组 成 , 指 令流经 各功 能段的 时间 ( 忽略 各功能 段之间 的缓存 时间 ) 分 别为 90 ns 、80 ns 、70 ns 、和 60 ns ,则该计 算机 的 CPU 时 钟周期 至少是 。 A .90 ns B .80 ns C .70 ns D .60 ns 19. 相对于微 程序控 制器, 硬布线 控制器 的特点 是 。 A .指令执行 速度慢 , 指令 功能的 修改和 扩展容 易 B . 指令执 行速度 慢 , 指 令功能 的修改 和扩展 难 C . 指令执 行速度 快 , 指 令功能 的修改 和扩展 容易 D .指 令执行 速度快 , 指令 功能的 修改和 扩展难20. 假设某系 统总线 在一个 总线周 期中并 行传输 4 字节信 息,一 个总线 周期 占用 2 个 时钟周 期,总 线时钟 频率 为 10MHz ,则总 线带宽 是______ 。 A .10MB/S B .20MB/S C .40MB/S D .80MB/S 21. 假设某计 算机的 存储系 统由 Cache 和 主存组 成, 某程序 执行过 程中访 存 1 000 次, 其 中访 问 Cache 缺失 (未 命中)50 次, 则 Cache 的命 中率是 。 A .5 B .9.5 C .50 D .95 22. 下列选项 中 , 能 引起外 部中断 的事件 是 。 A .键盘输入 B .除 数为 0 C . 浮点运 算下溢 D .访 存缺页 23. 单处理机 系统中 ,可并 行的是 。 Ⅰ 进 程与进 程 Ⅱ 处理 机 与设备 Ⅲ 处 理机与 通道 Ⅳ 设 备与设 备 A . Ⅰ 、 Ⅱ 和 Ⅲ B . Ⅰ 、Ⅱ 和Ⅳ C . Ⅰ 、 Ⅲ 和 Ⅳ D . Ⅱ 、 Ⅲ 和 Ⅳ 24. 下列进程 调度算 法中 , 综合考 虑进程 等待时 间和执 行时间 的是______ 。 A . 时间片轮 转调度 算法 B . 短进程 优先调 度算法 C . 先来先 服务调 度算法 D .高 响应比 优先调 度算法 25. 某计算机 系统中 有 8 台 打印机 , 由 K 个 进程竞 争使用 , 每 个进程 最多需 要 3 台 打印机 。该系统 可能会 发生 死锁的 K 的最小 值是______ 。 A .2 B .3 C .4 D .5 26. 分区分配 内存管 理方式 的主要 保护措 施是______ 。 A . 界地址 保护 B . 程 序代码 保护 C . 数 据保护 D . 栈 保护 27. 一个分段 存储管 理系统 中 ,地 址 长度 为 32 位, 其中段号占 8 位, 则最大 段长是______ 。 A .2 8 字节 B .2 16 字节 C .2 24 字节 D .2 32 字节 28. 下列文件 物理结 构中, 适合随 机访问 且易于 文件扩 展的是______ 。 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,170,180,195 C .110,170,180,195,12,35,45,68 D .12,35,45,68,110,170,180,195 30. 文件系统 中,文 件访问 控制信 息存储 的合理 位置是______ 。 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 、1 32. 程序员利 用系统 调用打 开 I/O 设备时 ,通常 使用的 设备标 识是 ______ 。 A . 逻辑设备 名 B . 物理设 备名 C . 主 设备 号 D . 从 设备 号 33. 在 OSI 参考 模型中 ,自下 而上第 一个提 供端到 端服务 的层次 是______ 。 A .数据链路 层 B . 传输层 C . 会话层 D .应 用层 34. 在无噪声 情况下 , 若某 通信 链路的 带宽 为 3kHz , 采 用 4 个 相位, 每个相 位具 有 4 种振 幅的 QAM 调 制技术 ,则该通信 链路的 最大数 据传输 速 率是______ 。 A .12kbps B .24 kbps C .48 kbps D .96 kbps 35. 数据链路 层采用 后退 N 帧( GBN ) 协议 ,发送方 已经发 送了编 号为 07 的帧 。 当计 时器超 时时 , 若发 送方 只收到 0 、2 、3 号帧的 确认, 则发送 方需要 重发的 帧数 是______ 。 A .2 B .3 C .4 D .5 36. 以太网交 换机进 行转发 决策时 使用 的 PDU 地址 是______ 。 A . 目的物理 地址 B . 目的 IP 地址 C . 源物理 地址 D . 源 IP 地址 37. 在一个采 用 CSMA/CD 协议 的网络 中,传 输介质 是一根 完整的 电缆, 传输速 率为 1Gbps ,电缆 中的信 号传 播速度 是 200 000km/s 。 若最 小数据 帧长度 减少 800 比特, 则最远 的两个 站点之 间的 距离至 少需要______ 。 A .增加 160m B . 增加 80m C . 减少 160m D .减 少 80m 38. 主机甲 与 主机乙 之 间已 建立一 个 TCP 连接 ,主机 甲向 主机乙 发送了 两个连 续的 TCP 段 ,分别 包含 300 字 节和 500 字节的 有效载 荷,第 一个 段的序 列号为 200 , 主机乙 正确接 收到两 个 段 后,发 送给主 机甲的 确认 序列号是______ 。 A .500 B .700 C .800 D .1000 39. 一个 TCP 连接 总 是以 1KB 的最大 段 长发送 TCP 段,发 送方 有 足够 多的数 据要发 送 。 当 拥塞窗 口为 16KB 时发生了 超时, 如果接 下来的 4 个 RTT ( 往返 时间 ) 时间 内的 TCP 段 的 传输 都是成功 的 , 那么 当 第 4 个 RTT 时间 内发送 的所 有 TCP 段都得 到肯定 应答时 ,拥塞 窗口大 小 是______ 。 A .7 KB B .8 KB C .9 KB D .16 KB 40. FTP 客户 和 服务器 间传 递 FTP 命 令时, 使用的 连接是______ 。 A .建立在 TCP 之 上的控 制连 接 B . 建立 在 TCP 之上的 数据连 接 C . 建立 在 UDP 之上 的控制 连接 D .建 立在 UDP 之上的 数据连 接 二、 综 合应用 题 第 4147 题 ,共 70 分 。 41. (10 分) 带权图(权 值非负 ,表示边 连接的 两顶点 间的距 离)的最短 路径问 题是 找出从 初始顶 点到目 标顶 点之间的 一条最 短路径 。 假设 从初始 顶点到 目标顶 点之间 存在 路径, 现有一 种解决 该问题 的方法 ① 设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点; ② 选择离u最近且尚未在最短路径中的一个顶点v ,加入到最短路径中 , 修改当前顶点uv ; ③ 重复步骤②,直到u是目标顶点时为止。 请问上述 方法能 否求得 最短路 径 若 该方法 可行, 请证明 之; 否则, 请举例 说明。 42. (15 分) 已知 一个带 有表头 结点的 单链表 ,结点 结构为 假设该链 表只给 出了头 指针 list 。 在不改变 链表的 前提下 , 请设 计一个 尽可能 高效的 算法, 查找链 表中 倒数第k 个位置上 的结点k 为正整数 。 若查 找成功,算法输 出该结 点的 data 域的 值, 并 返回 1 ; 否 则, 只 返回 0 。要 求 ⑴ 描 述算法 的基本 设计思 想; ⑵ 描 述算法 的详细 实现步 骤; ⑶ 根 据设计 思想和 实现步 骤, 采 用程序 设计语 言描述 算法 ( 使用 C 、C 或 Java 语言实 现) ,关键之 处请 给出简要 注释。 43. (8 分) 某 计算机 的 CPU 主频 为 500MHz ,CPI 为 5 (即执 行每条 指令平 均需 5 个时 钟周期 ) 。 假定某 外设 data link 的数据传 输率 为 0.5MB/s , 采用 中断 方式与 主机进 行数据 传送 ,以 32 位 为传输 单位 , 对 应的中 断服务 程序 包含 18 条指 令,中 断服务 的其他 开销相 当于 2 条指令 的执 行时间 。请回 答下列 问题, 要求给 出计算 过程。 1 ) 在中断方 式下,CPU 用于 该外 设 I/O 的时 间占 整个 CPU 时间的 百分 比是多 少 2 ) 当该外设 的数据 传输率 达到 5MB/s 时,改 用 DMA 方式传 送数据 。假定 每次 DMA 传送 块大小 为 5000B ,且 DMA 预 处理和 后处理 的总开 销为 500 个时 钟周 期, 则 CPU 用于 该外 设 I/O 的 时间占 整个 CPU 时间的百 分比是 多少 (假 设 DMA 与 CPU 之间没 有访存 冲突) 44. (13 分) 某计算 机字 长 16 位,采用 16 位定 长指 令字结 构 , 部分 数据通 路结构 如下图 所示 , 图 中所有 控制 信号为 1 时表示 有效 、 为 0 时表示 无效 。 例如 控制信 号 MDRinE 为 1 表示 允许数 据从 DB 打入 MDR , MDRin 为 1 表 示允许 数据 从 内总线 打入 MDR 。假设 MAR 的输 出一直 处于使 能状态 。加法 指令 ADD R1 ,R0 的 功能为R0R1 R1 , 即将 R0 中 的数据与 R1 的内 容所指 主存单 元的数 据相加 ,并将 结果送入 R1 的内容所 指主存 单元中 保存。 下表给出 了上述 指令取 指和译 码阶段 每个节 拍 时钟周 期 的 功能和 有效控 制信号, 请按 表中描 述方式 用 表格 . . 列出 指令 执行阶 段 . . . . . . 每个 节拍的 功能和 有效控 制信号 。 45. (7 分) 三个进 程 P1 、P2 、P3 互 斥使用 一个包 含 NN0 个单 元的缓 冲区 。P1 每 次用 produce 生成一 个正 整数并 用 put 送入 缓冲区 某一空 单元中 ;P2 每次 用 getodd 从该缓冲 区中取 出一个 奇数并 用 countodd 统 计奇数个 数;P3 每次 用 geteven 从该缓 冲区中 取出一 个偶 数并 用 counteven 统 计偶 数个数 。 请 用信号 量机 制实现这 三个进 程的同 步与互 斥活动 ,并说 明所定 义信号 量的 含义。 要求用 伪代码 描述。 46. (8 分) 请 求分页 管理系 统中, 假设某 进程的 页表内 容如 下表所 示 时钟 功能 有效控制信号 C1 MAR PC PCout, MARin C2 MDR MMDR PC PC1 MemR, MDRinE, PC1 C3 IR MDR MDRout, IRin C4 指令译码 无 页号 页框Page Frame 号 有效位 存在位 页面大小 为 4KB , 一 次内存 的访问 时间 是 100ns , 一次快 表TLB 的访 问时间 是 10ns , 处 理一次 缺页的 平均 时间 10 8 ns 已含更新 TLB 和页 表的 时间 ,进程 的驻留 集大小 固定 为 2 ,采用 最近最 少使用 置换算 法LRU 和局 部淘汰策 略。假 设 ①TLB 初始为 空; ② 地址转 换时先 访问 TLB ,若 TLB 未 命中, 再访问 页表 忽略 访问页 表之 后的 TLB 更新 时间 ; ③ 有效位为 0 表 示页面 不在内 存,产 生缺页 中断, 缺页中 断处 理后, 返回到 产生缺 页中 断的指令 处重新 执行。 设有虚 地址访 问序 列 2362H 、1565H 、25A5H , 请问 1 依次访 问上述 三个虚 地址, 各需多 少时间 给出 计算过 程。 2 基于上 述访问 序列, 虚地 址 1565H 的物理 地址是 多少 请说明 理由。 47. (9 分) 某网络 拓扑 如 下图所 示,路 由器 R1 通过 接口 E1 、E2 分 别连接 局域 网 1 、局域 网 2 , 通过接 口 L0 连接路由 器 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.118.3.1 ; 域名服务 器的 IP 地址 是 202.118.3.2 。 R1 和 R2 的路由 表结 构为 目的网 络 IP 地址 子网掩码 下一跳 IP 地址 接口 ⑴ 将 IP 地址空间 202.118.1.0/24 划分为 2 个子网 ,分别 分配 给局域网 1 、 局域网 2 ,每 个局域 网需分 配的 IP 地址数 不少 于 120 个 。请给 出子网 划分结 果,说 明理由 或给出 必要的 计算过 程。 ⑵ 请 给出 R1 的路由 表,使其 明确 包 括到局 域网 1 的路由、 局域 网 2 的路 由、域 名服务 器的主机 路 由 和互 联网的路 由。 ⑶ 请 采用路 由聚合 技术, 给出 R2 到局域 网 1 和 局域 网 2 的路 由。 0 101H 1 1 0 2 254H 1 参考答案 一、单项选择题(后附有解析) 1. B 2. C 3. D 4. B 5. C 6. B 7. A 8. D 9. A 10. B 11. C 12. D 13. D 14. C 15. D 16. C 17. A 18. A 19. D 20. B 21. D 22. A 23. D 24. D 25. C 26. A 27. C 28. B 29. A 30. A 31. B 32. A 33. B 34. B 35. C 36. A 37. D 38. D 39. C 40. A 二 、综 合应用 题 41 .解答 该方法 不 一定 能 (或不 能) 求 得最短 路径。 例如, 对于 下图所 示的带 权图, 如 果按照 题中 的原则,从 A 到 C 的最 短路径 是 A-B-C , 事实 上其最 短路 径是 A-D-C 。 42 .解答 (1 ) 算法的 基本设 计思想 (5 分) 问题的关 键是设 计一个 尽可能 高效的 算法, 通过链 表的一 趟遍 历,找 到倒数 第 k 个结点 的位置 。算法 的基 本设计思 想是 定义 两个指 针变 量 p 和 q ,初始 时均 指 向头结 点的下 一个结 点 (链 表的第 一个结 点)。p 指 针沿 链表移动 ;当 p 指针移 动到 第 k 个结 点时,q 指 针开始 与 p 指 针同步 移动; 当 p 指 针移动 到最后 一个结 点时,q 指针所指 示结点 为倒数 第 k 个 结点。 以上过 程对链 表仅进 行一 遍扫描 。 (2 ) 算法的 详细实 现步骤 (5 分) ① count0 ,p 和 q 指向 链表表 头结点 的下一 个结点 ; ② 若 p 为空 ,转 ⑤ ; ③ 若 count 等于 k ,则 q 指向下 一个结 点;否 则,countcount1 ; ④ p 指向 下一个 结点, 转 ② ; ⑤ 若 count 等于 k ,则查 找成功 ,输出 该结点的 data 域的值 ,返回 1 ;否 则,说明 k 值 超过了 线性表 的长 度,查找 失败, 返回 0 ; ⑥ 算 法结束 。 (3 ) 算法实 现(5 分 ) typedef int ElemType; ∥ 链表数 据的类 型定义 typedef struct LNode{ ∥ 链表结 点的结 构定义 ElemType data; ∥ 结点数 据 struct Lnode *link; ∥结点链 接指针 } *LinkList; int Search_kLinkList list, int k{ ∥ 查找链 表list 倒数 第k 个 结点, 并输出 该结 点data 域的值 LinkList p list-link, q list-link; ∥ 指针p 、q 指 示第一 个结点 2 1 3 10 A B D C int count 0; whilep NULL{ ∥ 遍历链表直 到最后 一个 结点 ifcount link; p p-link; ∥之后让p 、q 同步 移动 } ∥while ifcount data; return 1; } } ∥Search_k 提 示 算法程序题, 如果 能够写 出数据 结构类 型定 义、正 确的算 法思想 都会 至少给 一半以 上分数 ,如 果能 用伪代码 写出自 然更好 ,比较 复杂的 地方可 以直接 用文字 表达 。 若所给出 的算法 采用一 遍扫描 方式就 能得到 正确结 果,可 给满分 15 分;若 采用 两遍或 多遍扫 描才能 得到 正确结果 的, 最高 分 10 分 。 若采 用递归 算法得 到正确 结果 的, 最 高给 10 分 ; 若实 现算法 的空间 复杂度 过高 (使 用了大小 与 k 有 关的辅 助数组 ),但 结果正 确,最 高给 10 分。 43 .解答 1 按题意 , 外设 每秒传 送 0.5MB , 中 断时每 次传 送 4B 。 中 断方式 下,CPU 每次 用于数 据传送 的时钟 周期 为5 185 2100. 为达到外 设 0.5MB/s 的数 据传输 率,外 设每秒 申请的 中断次 数为0.5MB/4B125 000 。 1 秒 钟内用 于中断 的开销 100 125 00012 500 00012.5M 个时 钟周期 。 CPU 用于外 设 I/O 的 时间占 整个 CPU 时间 的百分 比12.5M/500M2.5 。 2 当外设 数据传 输率提 高到 5MB/s 时改用 DMA 方式 传送, 每次 DMA 传送 5 000B ,1 秒钟内 需产生 的 DMA 次数5 MB/5 000 B1 000. CPU 用于 DMA 处 理的总 开销1 000 500500 0000.5M 个时 钟周期 。 CPU 用于 外设 I/O 的时间 占整 个 CPU 时 间的百 分比0.5M/500M0.1 。 44 .解答 一条指令 的执行 过程通 常由取 指、译 码和执行 3 个步 骤完成 ,本题 中取指用 3 个节拍 、译码用 1 个节 拍, 执行加 法运算 并把 结果写 入主 存如何 完成 呢包 括划分 执行 步骤、 确定 完成的 功能 、要提 供的 控制信 号, 这是 本题要测 试的内 容。为 回答这 个问题 ,首先 要看清 图中给 出的 部件组 成情况 和信息 传送的 路径。 要完成的 功能时 (R0 )(( R1))  (R1 ) ,从图 中看到 1 R0 、R1 都有 送自己 内容到 内总线 的路径 ,控制 信号分 别 是 R0out 和 R1out ; 2 ALU 加 运算,2 个 数据由 工作寄 存器 A 和内总 线提 供,控制信 号是 Add ;A 只接收 内总线 的内 容, 控制 信号是 Ain ;结果 需存 AC , 控制信 号是 ACin ;AC 的内容 可送内 总线, 控制信 号 是 ACout; 3 PC 可 接收 内总线 的内容 , 还 可增 1 , 控制信 号是 PCin 和 PC1 , PC 的内容 可送内 总线 , 控制 信号是 PCout ; 4 指令寄 存器 IR 可 接收内 总线的 内容, 控制信 号是 IRin ; 5 读写存 储器时 ,地址 由 MAR 经 AB 提供,MAR 只 接收总 线上的 信息, 控制信 号是 MARin; 6 读存储 器,提供读 命令 MemR , 并 通过 DB 送入 MDR ,控制信 号是 MDRinE;MDR 的 内容可 送入总 线, 控制信号 是 MDRout; 7 写存储 器,提 供写命 令 MemW, 数据 由 MDR 通过 DB 送到 存储器 的数据 引脚 ,控制 信号 是 MDRoutE; 然后是 划分执 行步 骤、确 定每 一步完 成的 功能、 需要 提供的 控制 信号。 这是 由指令 应完 成的功 能和计 算机 硬件的 实际组 成情 况和信 息传 送的可 用路 径共同 决定的 ,基 本原则 是步 骤越少 越好 。硬件 电路 要能支 持, 可以 有多种 方案, 解题 时应参 照以 给出的 答题 格式, 即取指 和译 码阶段 的那 张表的 内容 ,但不 必把 表已有 的内 容再 抄一遍。 划分指令 执行步 骤,确 定每一 步完成 的功能 、给出 需要提 供的 控制信 号 请 注意 , (R0 )(( R1 ) ) 表 示R0 寄存器 的内容 与 R1 作 地址从 主存中 读出来 的数据 完成加 法运算 ; 而  (R1 ) 表示把 R1 的内容 作为主 存储器 的地址 完成写 主存操 作。为 防止出 现误解 ,题 中还特 地对此 作了文 字说 明。这条 指令的 功能是 先到主 存储器 取一个 数,之 后运算 ,再 将结果 写回主 存储器 。 1 执行相 加运算 , 需把 存储器 中的数 据读出 , 为 此首先 送地址 , 将 R1 的内容 送 MAR , 控 制信号 是 R1out 、 MARin 。 2 启动读 主存操 作, 读出 的内容 送入 MDR , 控 制信号 是 MemR 、MDRinE 。还可同 时把 R0 的内容 经内总 线送入 A , 用到的 控制信 号是 R0out 、Ain 。 3 执行加 法运算, 即 A 的 内容 与 MDR 的内容 相加, 结果保 存到 AC ,控 制信号 是 MDRout 、Add 、Acin 。 4 要把 AC 的 内容写 入主存 ,由于 R1 的内容 已经在 MAR 中,地 址已经 有了, 但需 要把写 入的数 据(已 经在 AC 中 )经内 总线送 入 MDR ,控制 信号 是 ACout 、MDRin 。 5 给出写 主存的 命令 , 把 MDR 的 内容 经 DB 送存 储器的 数据线 引脚 , 执行 写操作 , 控 制信号 是 MDRoutE 、 MemW 。 这几个 步骤是 有先 后次序 的, 前面的 完成 了 ,下 一步 才可以 执行 ,也保 证了 不会产 生硬 件线路 的冲突 。请 注意, 使用最 为频 繁的是 内总 线,它 在任 何时刻 只能接 收一 个输入 数据 ,并且 向内 总线发 送信 息的电 路只 能以 三态门器 件连接 到内总 线,5 个向 内总裁 发送信 息的控 制信 号(ACout ,PCout ,R0out ,R1out ,MDRout )最多 只能有一 个为 1 , 其他 4 个必须 全为 0 , 或者 5 个全 为 0. 仔细看一 下,发 现可以 把第 2 个步骤 的操作 划分到 两个步 骤中完 成,一 个步骤 中安排 MDR 接收从 存储器 中读出的 内容, 到 另外一 个步骤 实现 R0 的内容 送入 A , 这多 用了一 个操作 步骤, 指 令的执 行速度 会变慢。 有些 解题者在 写存储 器之前 ,还会 再执行 一次 把 R1 的内 容送 MAR ,尽 管无此 必要, 但不 属于原 理上的 错误。 当 然还 可以有 其他 的设计 结果。 解题时 这些叙 述内 容不必 写出 来(这 里写 出这些 内容 是希望 帮助 大家领 会本 题要测 试的 知识点 和指令 的执 行过程 ) ,直 接按照 已经给 出的表 格的形 式、按 照提供 的填 写办法 把设计 的表格 及其内 容填好 就可以 了。 请注意 ,题目 表格 内容( 告诉 你答题 的格 式和答 题内 容的表 达方 式)与 你答 题的表 格内 容合在 一起才 是这 条指令的 完整的 执行过 程,千 万不要 产生任 何错觉 。 参 考答 案一 时钟 功能 有效控制 信号 C5 MAR  (R1 ) R1out,MARin C6 MDR MMAR A R0 MemR,MDRinE, R0out,Ain C7 AC MDRA MDRout,Add,ACin C8 MDR AC ACout,MDRin C9 MMAR MDR MDRoutE,MemW  也 可在 C7  (MDR ) (A ) 之前单 列的 一个时 钟周期 内执行 。 参 考答 案二 时钟 功能 有效控制 信号 C5 MAR  (R1 ) R1out,MARin C6 MDR MMAR MemR,MDRinE C7 A MDR MDRout,Ain C8 AC AR0 R0out,Add,ACin C9 MDR AC ACout,MDRin C10 MMAR MDR MDRoutE,MemW 45 .解答 定义信号 量 odd 控制 P1 与 P2 之 间的同 步;even 控制 P1 与 P3 之 间的同 步;empty 控制 生产者 与消费 者之 间的同步 ;mutex 控制进 程间互 斥使用 缓冲区 。程序 如下 semaphore odd 0, even 0, empty N, mutex 1; P1 { x produce; ∥ 生成一 个数 Pempty; ∥ 判断缓 冲区是 否有空 单元 Pmutex; ∥ 缓冲区 是否被 占用 Put; Vmutex; ∥ 释放缓 冲区 ifx2 0 Veven; ∥ 如果是 偶数, 向P3 发出信 号 else Vodd; ∥ 如果是 奇数, 向P2 发出信 号 } P2 { Podd; ∥ 收到P1 发来 的信号 ,已产 生一个 奇数 Pmutex; ∥ 缓冲区 是否被 占用 getodd; Vmutex; ∥ 释放缓 冲区 Vempty; ∥ 向P1 发信号 ,多出 一个空 单元 countodd; } P3 { Peven; ∥ 收到P1 发来 的信号 ,已产 生一个 偶数 Pmutext; ∥ 缓冲区 是否被 占用 geteven; Vmutex; ∥ 释放缓 冲区 Vempty; ∥ 向P1 发信号 ,多出 一个空 单元 counteven; } 46 .解答 1 根据页 式管理 的工作 原理, 应先 考虑页 面大小 ,以便 将页号 和页内 位移 分解出 来。页 面大小为 4KB ,即 2 12 ,则得到页 内位移 占虚地 址的低 12 位, 页号占 剩余高 位。可 得三个 虚地址 的页号 P 如下 ( 十 六进制 的一 位数字转 换成 4 位二进 制,因 此,十 六进制 的低三 位正好 为页 内位移 ,最高 位为页 号 ) 2362H P2 , 访 问快 表 10ns , 因初始为 空, 访问 页表 100ns 得到 页框号,合成物 理地址 后访问 主存 100ns , 共计 10ns100ns100ns210ns 。 1565H P1 ,访问 快 表 10ns ,落空,访 问页 表 100ns 落空,进 行缺 页中断 处理 10 8 ns ,访问快表 10ns ,合 成
展开阅读全文

copyright@ 2018-2019 考拉文库网站版权所有
经营许可证编号:陕ICP备18022950号-1