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

返回 相似
第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
点击查看更多>>
资源描述:
2010 年全 国硕 士研 究 生入 学统 一 考试 计 算机 科学 与 技术 学科 联 考 计 算机 学科 专 业基 础综 合 试题 一 、 单 项选择 题 第 140 小题, 每小 题 2 分 ,共 80 分。下 列每题 给出 的四个 选项 中,只 有一 个选项 最符 合试 题 要求 。 1. 若元素 a 、b 、c 、d 、e 、f 依次进 栈,允 许进栈 、退栈 操作交 替进行 ,但不 允许连 续三次 进行退 栈 操作 ,则 不 . 可能得 到的出 栈序列 是______ 。 A .d c e b f a B .c b d a e f C .b c a e f d D .a f e d c b 2. 某队列允 许在其 两端进 行入队 操作, 但仅允 许在一 端进行 出队 操作。 若元素 a 、b 、c 、d 、e 依 次入此 队列 后再进行 出队操 作,则 不 . 可能 得到的 出队序 列是______ 。 A .b a c d e B .d b a c e C .d b c a e D .e c b a d 3. 下列线索 二叉树 中(用 虚线表 示线索 ) , 符合后 序线索 树定 义的是______ 。 A . B . C . D . 4. 在 右 图 所 示的平 衡二叉 树中 , 插入关 键字 48 后 得到一 棵新 平衡二 叉树 。 在新平 衡二叉树 中, 关键 字 37 所在 结点的 左、 右子 结点中 保存的 关键 字分别 是______ 。 A .13 ,48 B .24 ,48 C .24 ,53 D 、24 ,90 5. 在一棵度 为 4 的树 T 中, 若有 20 个 度为 4 的结点 ,10 个度 为 3 的 结点 ,1 个度 为 2 的结 点,10 个度 为 1 的 结点, 则树 T 的 叶结点 个数是______ 。 A .41 B .82 C .113 D .122 6. 对 n (n 2 )个权 值均不 相同的 字符构 造 成哈 夫曼树 。下列 关于 该 哈夫 曼 树的 叙述中 , 错误 . . 的是______ 。 A . 该树一定 是一棵 完全二 叉树。 B . 树中一 定没有 度为 1 的结点 。 C . 树中两 个权值 最小的 结点一 定是兄 弟结点 。 D . 树 中任一 非叶结 点的权 值一定 不小于 下一层 任一结 点的权 值。 7. 若无向 图 G (V , E ) 中含 有 7 个顶点, 要 保证 图 G 在 任何情 况下都 是连通 的, 则 需要的 边数最 少是_____ 。 A .6 B .15 C .16 D .21 8. 对右 图进 行拓扑 排序, 可以得 到不同 的拓扑 序列的 个数是_____ 。 A .4 B . 3 C .2 D .1 9. 已知一个 长度 为 16 的顺序 表 L , 其 元素按 关键字 有序排 列 。 若采用 折半查 找法查找 一个 L 中 不存在 的元素 ,则 关 键字的 比较次 数最多 的是_____ 。 A .4 B .5 C .6 D .7 10. 采用递归 方式对 顺序表 进行快 速排序 。 下列 关于递 归次数 的叙 述中, 正确的 是______ 。 A . 递归次数 与初始 数据的 排列次序 无关 。 a b c d Null a b c d Null Null a b c d Null a b c d Null e d a b c 24 13 53 37 90 B . 每次划 分后, 先处理 较长的 分区可 以减少 递归次 数。 C . 每次划 分后, 先处理 较短的 分区可 以减少 递归次 数。 D . 递 归次数 与每次 划分后 得到的 分区 的 处理顺 序无关 。 11. 对一组数 据2 ,12 ,16 ,88 ,5 ,10 进 行排序 ,若前 三趟排 序结果 如下 第一趟 排 序结果 2 ,12 ,16 ,5 ,10 ,88 第二趟 排 序结果 2 ,12 ,5 ,10 ,16 ,88 第三趟 排 序结果 2 ,5 ,10 ,12 ,16 ,88 则采用的 排序方 法可能 是______ 。 A . 起 泡排序 B .希尔 排序 C . 归并排 序 D . 基 数排序 12. 下列选项 中,能 缩短程 序执行 时间的 措施是 。 Ⅰ . 提高 CPU 时钟 频率 Ⅱ . 优化数据通路 结构 Ⅲ . 对程序进行编 译优化 A . 仅 Ⅰ 和 Ⅱ B . 仅 Ⅰ 和 Ⅲ C . 仅 Ⅱ 和 Ⅲ D . Ⅰ 、 Ⅱ 和 Ⅲ 13. 假定有 4 个整 数用 8 位补 码分别 表示 r1FEH ,r2F2H ,r390H ,r4F8H ,若 将运 算结果 存放在 一个 8 位 寄存器中 ,则下 列运算 中 会发 生溢出 的是 。 A .r1 x r2 B .r2 x r3 C .r1 x r4 D .r2 x r4 14. 假定变 量 i 、f 和 d 的 数据类 型分别 为 int,float 和 double (int 用补 码表示 ,float 和 double 分别 用 IEEE754 单精度和 双精度 浮点数 格式表 示 ) , 已知 i785,f1.5678e3,d1.5e100 。 若在 32 位 机器中 执行下 列关系 表达 式,则结 果为 真 的是 。 (I )i intfloati IIf floatintf IIIf floatdoublef IVdf-d f A .仅 I 和 II B .仅 I 和 III C .仅 II 和 III D .仅 III 和 IV 15. 15 . 假 定用若 干个 2kx4 位 的 芯片 组成一个 8kx8 位 的存 储器 , 则地址 0B1FH 所 在芯 片的最 小地址 是 。 A .0000H B .0600H C .0700H D .0800H 16. 下列有 关 RAM 和 ROM 的 叙述中 ,正确 的是 。 I RAM 是易 失性存 储器,ROM 是 非易失 性存储 器 II RAM 和 ROM 都采用 随机存 取方式 进行信 息访问 III RAM 和 ROM 都可 用作 Cache IV RAM 和 ROM 都需要 进行刷 新 A .仅 I 和 II B .仅 II 和 III C .仅 I,II 和 IV D.仅 II ,III 和 IV 17. 下列 命中 组合情 况中, 一次访 存过程 中 不 . 可 能发生 的是 。 A .TLB 未命 中,Cache 未命 中,Page 未 命中 B .TLB 未命 中,Cache 命中 ,Page 命中 C .TLB 命中 ,Cache 未命中 ,Page 命中 D .TLB 命中 ,Cache 命中,Page 未命中 18. 下列寄存 器中, 汇编语 言程序 员可见 的是 。 A . 存储器地 址寄存 器MAR B . 程序计 数器PC C . 存储 器 数据寄 存器MDR D .指 令寄存 器IR 19. 下列 选项 中, 不 . 会引起 指令流 水 线 阻 塞的是 。 A . 数据旁路 (转发 ) B . 数据相 关 C . 条件转 移 D . 资 源冲突 20. 下列选项 中的英 文缩写 均为总 线标准 的是______ 。 A .PCI 、CRT 、USB 、EISA B .ISA 、CPI 、VESA 、EISA C .ISA 、SCSI 、RAM 、MIPS D .ISA 、EISA 、PCI 、PCI-Express 21. 单级中断 系统中 ,中断 服务程 序 内的 执行顺 序是______ 。 I 保护 现场 II 开中断 III 关 中断 IV 保 存断点 V 中 断事件 处理 VI 恢 复现场 VII 中断返 回 A .I-V-VI-II-VII B .III-I-V-VII C .III-IV-V-VI-VII D .IV-I-V-VI-VII 22. 假定一台 计算机 的显示 存储器用 DRAM 芯片实 现,若 要求显 示分辨 率为 1600*1200 ,颜色 深度 为 24 位, 帧频为 85HZ , 显存 总带 宽的 50 用来 刷新屏 幕,则 需要的 显存总 带宽至 少约为______ 。 A .245Mbps B .979Mbps C .1 958Mbps D .7 834Mbps 23. 下列选项 中,操 作系统 提供给 应用程 序的接 口是_____ 。 A . 系统调用 B . 中断 C . 库函数 D .原语 24. 下列 选项 中,导 致创建 新进程 的操作 是______ 。 Ⅰ 用户登录成功 Ⅱ 设备分配 Ⅲ 启动程序执行 A . 仅 Ⅰ 和 Ⅱ B . 仅 Ⅱ 和 Ⅲ C . 仅 Ⅰ 和 Ⅲ D . Ⅰ 、 Ⅱ 和 Ⅲ 25. 设与某资 源关联 的信号 量初值 为 3 ,当前 值为 1 。 若 M 表示该 资源的 可用个 数,N 表示 等待该 资源的 进程 数,则 M 、N 分别 是______ 。 A .0 、1 B .1 、0 C .1 、2 D .2 、0 26. 下列选项 中,降 低进程 优先级 的合理 时机是_____ 。 A. 进程的时 间片用 完 B. 进程刚完 成 I/O ,进 入就 绪列队 C. 进程长期 处于就 绪列队 中 D. 进程从就 绪态转 为运行 态 27. 进程 P0 和 P1 的共 享变量 定义 及 其初值 为 boolean flag[2]; int turn 0; flag[0] FALSE; flag[1] FALSE; 若进程 P0 和 P1 访 问临界 资源的 类 C 伪 代码 实现如 下 void P1 // 进程P1 { whileTRUE { flag[1]TRUE; turn0; whileflag[0] 临界区; flag[1]FALSE; } } void P0 // 进程P0 { whileTRUE { flag[0]TRUE; turn1; whileflag[1] 临界区; flag[0]FALSE; } } 则并发执 行进 程 P0 和 P1 时产生 的 情形 是______ 。 A. 不能保证 进程互 斥进入 临界区 ,会出 现 饥饿 现象 B. 不能保证 进程互 斥进入 临界区 ,不会 出现 饥饿 现象 C. 能保证进 程互斥 进入临 界区, 会出现 饥饿 现象 D. 能保证进 程互斥 进入临 界区, 不会出 现 饥饿 现象 28. 某基于动 态分区 存储管 理的计 算机 , 其主 存容量 为 55MB 初始 为空 闲 ,采用最 佳适配Best Fit 算 法,分配 和释放的 顺序为 分配 15M B , 分配 30MB ,释放 15M B ,分配 8M B ,分配 6M B ,此时 主存中 最大空 闲分 区的大小 是______ 。 A .7MB B .9MB C .10MB D .15MB 29. 某计算机 采用二 级页表 的分页 存储管 理方式 , 按字节 编址 , 页大 小为 2 10 字节, 页表项 大小 为 2 字节 , 逻辑 地址结构 为 页目录号 页号 页内偏移 量 逻辑地址 空间大 小为 2 16 页,则表 示整个 逻辑地 址空间 的页目 录表中 包含表 项的个 数 至少 . . 是______ 。 A . 64 B . 128 C . 256 D . 512 30. 设文件索 引节点 中有 7 个 地址项 ,其中 4 个 地址项 是 直 接地址 索引,2 个地址 项是 一级间 接 地址 索引,1 个地址项 是二级 间接地 址索引 , 每 个地址 项大小 为 4 字节 。 若磁盘 索引块 和磁盘 数据 块大小 均为 256 字节 , 则可表示 的单个 文件最 大长度 是______ 。 A .33 KB B .519 KB C .1 057 KB D .16 513 KB 31. 设置 当前 工作 目 录的主 要 目的 是_______ 。 A . 节省 外存 空间 B . 节省内 存空间 C . 加快文 件的检 索速度 D . 加 快文件 的读/ 写速 度 32. 本地用户 通过键 盘登陆 系统时 ,首先 获得键 盘输入 信息的 程序 是______ 。 A . 命令解释 程序 B . 中断处 理程序 C . 系统调 用 服务 程序 D . 用 户登录 程序 33. 下列选项 中, 不 . 属于网 络体系 结构所 描述的 内容是______ 。 A .网络的层 次 B . 每一层 使用的 协议 C . 协议的 内部实 现细节 D .每 一层必 须完成 的功能 34. 在下图所 示的采 用 存储- 转发 方式 的 分组交 换网络 中, 所 有链路 的数据 传输速 率为 100Mbps , 分组大 小为 1000B , 其中分组 头大 小为 20B 。 若主 机 H1 向主 机 H2 发送一 个大小 为 980 000B 的文 件 , 则在 不考虑 分组 拆装时间 和 传播 延迟的 情况下 ,从 H1 发送 开始 到 H2 接收 完为止 ,需要 的时间 至少 . . 是______ 。 A .80 ms B .80.08 ms C .80.16 ms D .80.24 ms 35. 某自治系 统 内采用 RIP 协 议, 若该自 治系统 内的路 由器 R1 收到其 邻居路 由器 R2 的 距离矢 量 , 距离矢 量 中 包含信息 ,则 能 得出的 结论是______ 。 A .R2 可 以经 过 R1 到达 net1 ,跳数 为 17 B .R2 可以 到达 net1 ,跳 数为 16 C .R1 可以 经过 R2 到达 net1 ,跳 数为 17 D .R1 不 能经 过 R2 到达 net136. 若路由 器 R 因 为拥塞 丢弃 IP 分组, 则此 时 R 可 向发出 该 IP 分组的 源主机 发送 的 ICMP 报文 类型是______ 。 A . 路由 重定 向 B . 目的 不 可达 C . 源点抑 制 D .超 时 37. 某网络的 IP 地址 空间为 192.168.5.0/24 ,采 用 定长 子网划 分,子 网掩码为 255.255.255.248 ,则 该网络 中 的 最大子网 个数 、 每个子 网内的 最大可 分配地 址个数 分别是______ 。 A .32 ,8 B .32 ,6 C .8 ,32 D .8 ,30 38. 下列网络 设备中 ,能够 抑制广播 风暴 的是______ 。 Ⅰ 中继器 Ⅱ 集线器 Ⅲ 网桥 Ⅳ 路由器 A .仅 Ⅰ 和 Ⅱ B .仅 Ⅲ C .仅 Ⅲ 和 Ⅳ D .仅 Ⅳ 39. 主机甲和 主机乙 之间已 建立 了 一个 TCP 连接,TCP 最大 段 长度 为 1 000 字节 。 若 主机甲 的当前 拥塞窗 口为 4 000 字节 , 在主 机甲向 主机乙 连续发 送 两个 最大段 后, 成功收 到主机 乙发送 的第一 个 段的 确认段 , 确 认段 中通告的 接收窗 口大小 为 2 000 字节, 则此时 主机甲 还可 以向主 机乙发 送的最 大字节 数是______ 。 A .1 000 B .2 000 C .3 000 D .4 000 40. 如果本地 域名 服务器 无缓存 ,当 采用递 归方法 解析另 一网 络某主 机域名 时, 用户主 机 、本 地域名 服务 器发 送的域名 请求消息 数分 别为______ 。 A . 一 条 、 一 条 B . 一 条、 多条 C . 多条 、 一 条 D .多 条 、多条 二、 综 合应用 题 第 4147 题 ,共 70 分 。 41. (10 分) 将关键 字序列 (7 、8 、30 、11 、18 、9 、14 )散 列存储 到散列 表中 。散列 表的存 储空间 是一个 下 标从 0 开 始的一 维数组 , 散 列函数 为Hkey keyx3 MOD 7 , 处理 冲突采 用线性 探测再 散列法 , 要 求装 填 ( 载 ) 因子 为 0.7 。 1 请画出 所构造 的散列 表。 2 分别计 算等概 率情况 下查找 成功和 查找不 成功的 平均查 找长度 。 42. (13 分) 设将 n (n1 ) 个整数 存放到 一维数组 R 中。 试 设计 一个在 时间和 空间 两方面 都 尽可 能高效 的算 法。将 R 中 保存 的 序列循 环左 移 p (0pn )个 位置, 即将 R 中 的数 据由 (X0, -1 ) 变 换为 (Xp, Xp -1, -1 ) 。 要求 ⑴ 给出算法的基本 设计思 想。 ⑵ 根据设计思想, 采用 C 或 C 或 JAV A 语 言描述 算法, 关键之 处给出 注释。 ⑶ 说明你所设计算 法的时 间复杂 度和空 间复杂 度。 43. (11 分) 某 计算机 字长 为 16 位 ,主存 地址空 间大小 为 128KB ,按字 编址 。 采用 单字 长 指令格 式,指 令各 字段定义 如下 15 12 11 6 5 0 OP Ms Rs Md Rd 源 操作数 目的 操作数 转移指令 采用相 对寻址 方式, 相对偏 移 量 用 补码表 示,寻 址方 式定义 如下 Ms/Md 寻址方式 助记符 含义 000B 寄存器直 接 Rn 操作数 (Rn ) 王道论坛 www.cskaoyan.com 予人玫瑰 手留余香 001B 寄存器间 接 (Rn ) 操作数 (Rn ) 010B 寄存器间 接、自 增 (Rn ) 操作数 (Rn ) , (Rn ) 011B 相对 D (Rn ) 转移目标 地址 (PC ) (Rn ) 注 (X )表示存储器地址 X 或寄存器 X 的内容 。 请回答下 列问题 ⑴ 该指令系统 最多 可有多 少条 指令 该 计算机 最多 有多 少个 通用寄 存器 存 储器地 址寄 存器 (MAR )和 存储器数 据寄存 器(MDR )至少 各需要 多少 位 ⑵ 转移指令的目标 地址范 围是多 少 ⑶ 若操作码0010B 表示加 法操作( 助记符 为 add ) ,寄存 器 R4 和 R5 的 编号分 别为100B 和101B ,R4 的 内容 为1234H ,R5 的内容 为5678H , 地 址1234H 中的内 容为5678H , 地址5678H 中的 内容为1234H , 则汇 编语言 为 add (R4),( R5 ) ( 逗号前 为 源 操 作数, 逗号后 为目的 操作数) 对应的 机器码 是什么( 用十六 进制表 示) 该指 令执行后 ,哪些 寄存器 和存储 单元 中 的内容 会改变 改变 后的 内容是 什么 44. (12 分) 某计算 机的主 存地址 空间大小 为 256MB ,按 字节编 址 。指令 Cache 和数 据 Cache 分离 , 均有 8 个 Cache 行, 每 个 Cache 行大 小为 64B , 数 据 Cache 采用 直接映 射方式 。 现有 两个功 能相同 的程 序 A 和 B , 其伪代码 如下所 示 假定 int 类型 数据用32 位补 码表 示,程 序编译 时 i ,j ,sum 均分 配在寄 存器中 ,数 组 a 按 行优先 方式存 放, 其 首 地址 为320 (十 进制数)。 请回答 下列问 题,要 求说明 理由 或给出 计算过 程。 1 若不考 虑用 于 cache 一致性 维护和 替换算 法的控 制位, 则数 据 Cache 的总容 量 为 多 少 2 数组元 素 a[0][31] 和 a[1][1] 各自所 在的主 存块对 应的 Cache 行 号分别 是多少 (Cache 行号从0 开 始) 3 程序 A 和 B 的 数据访 问命中 率各 是多少 哪个 程序的 执行时 间更短 45. (7 分) 假 设计算 机系统 采用 CSCAN ( 循环扫 描)磁 盘调度 策略, 使用 2KB 的 内存空 间记 录 16 384 个磁 盘块的空 闲状态 。 1 请说明 在上述 条件下 如何进 行磁盘 块空闲 状态 的 管理。 2 设某单 面磁盘 旋转速 度为每 分钟 6000 转, 每个 磁道 有 100 个 扇区, 相邻磁 道间的 平均移 动时间 为 1ms 。 若在某时 刻,磁 头位 于 100 号 磁道处 ,并沿 着磁道 号增大 的方向 移动( 如下 图所示 ) , 磁道号 请求队 列为 50 , 90 ,30 ,120 , 对请 求队列 中的每 个磁道 需读 取 1 个随 机分布 的扇区 , 则读 完这 4 个扇 区点共 需要多 少时间 要 求给出计 算过程 。 3 如果将 磁盘替 换为随 机访问的 Flash 半导体存储 器(如 U 盘、SSD 等 ) , 是否有比 CSCAN 更高效 的磁 盘调度策 略若 有,给 出磁盘 调度策 略的名 称并说 明理由 ;若 无,说 明理由 。 程序A int a[256][256] „„ int sum_array1 { int i, j, sum0; fori0; i256; i forj0; j256; j sum a[i][j]; return sum; } 程序B int a[256][256] „„ int sum_array2 { int i, j, sum0; forj0; j256; j fori0; i256; i sum a[i][j]; return sum; } 0 号磁道 随机分布的某扇区 100 号磁道 磁头移动方向 46. (8 分) 设 某计算 机的逻 辑地址 空间和 物理地 址空间 均为 64KB , 按字 节编址 。 若某 进程 最 多需 要 6 页Page 数据存储 空间, 页 的大小 为 1KB , 操作系 统采用 固定分 配局部 置换策 略为此 进程分 配 4 个 页框Page Frame 。 在时刻 260 前的 该进程 访问情 况如下 表所示 (访问 位即使 用位 ) 。 页号 页框号 装入时刻 访问位 0 7 130 1 1 4 230 1 2 2 200 1 3 9 160 1 当该 进程执 行到时 刻 260 时,要 访问逻 辑地址 为 17CAH 的 数据。 请回答 下列问 题 1 该逻辑地 址对应 的页号 是多少 2 若采用先 进先出 (FIFO ) 置 换算法 ,该逻 辑地址 对应的 物理地 址是多 少 要求 给出计 算过程。 3 若采用 时钟 (CLOCK ) 置换 算法 ,该 逻辑地 址对 应的 物理 地址是 多少 要 求给 出计算 过程 ( 设 搜索下一 页的指 针沿顺 时针方 向移动 ,且当 前指 向 2 号页 框, 示意图 如下 ) 。 图 3.15 页框 示意图 47. (9 分) 某 局域网 采用 CSMA/CD 协议实 现介质 访问控 制, 数 据传输 速率 为 10Mbps , 主机甲和 主机乙 之间 的距离 为 2 km ,信 号传播 速度 是 200 000 km/s 。请回 答下列 问题, 要求 说明理 由或写 出计算 过程。 ⑴ 若主机甲和主机 乙发送 数 据时 发生冲 突,则 从开始 发送 数据时 刻起, 到两台 主机均 检测到 冲突时刻 止, 最短需经 过多长 时间 最长需 经过多 长时间 (假设 主机甲 和主 机乙发 送数据 过程中 ,其他 主机不 发送数 据) ⑵ 若网络不存在任 何冲突 与差错 ,主机 甲总是 以标准 的最 长以太 网数据 帧(1 518 字节 )向主 机乙发 送数 据, 主机 乙每成 功收到 一个数 据帧后 立即向 主机甲 发送一 个 64 字节 的确 认帧, 主 机甲 收到确 认帧后 方可发 送下 一个数据 帧。此 时主机 甲的有 效数据 传输速 率是多 少(不 考虑 以太网 的前导 码) 0 号页 3 号页 2 号页 1 号页 9 号页框 2 号页框 4 号页框 7 号页框 参考答案 一、单项选择题(后附有解析) 1. D 2. C 3. D 4. C 5. B 6. A 7. C 8. B 9. B 10. D 11. A 12. D 13. B 14. B 15. D 16. A 17. D 18. B 19. A 20. D 21. A 22. D 23. A 24. C 25. B 26. A 27. D 28. B 29. B 30. C 31. C 32. B 33. C 34. C 35. D 36. C 37. B 38. D 39. A 40. A 二、综合 应用题 41 .解答 1 由装载 因子 0.7 , 数据 总数 为 7 , 得 一维 数组大小 为 7/0.710 , 数 组下标 为 09 。 所构 造的散 列函数 值如 下所示 key 7 8 30 11 18 9 14 Hkey 0 3 6 5 5 6 0 采用线性 探测 再 散列法 处理冲 突,所 构造的 散列表 为 地址 0 1 2 3 4 5 6 7 8 9 关键字 7 14 8 11 30 18 9 2 查 找成功 时, 是根据 每个元素 查找 次数 来 计算平 均长度 , 在等概 率的情 况下 , 各 关键字 的查找 次数为 故,ASL 成功 查找次 数 / 元 素个数 1211133 / 7 12/7 这里要特 别防止 惯性思 维 。 查找失 败时, 是根 据查找 失败 位 置计算 平均次 数,根据散 列函 数 MOD 7 ,初始 只可能 在 06 的位 置。等 概率情 况下, 查找 06 位置 查 找失败 的查找 次数为 故,ASL 不成功 查找 次数 / 散 列后 的地址 个数 3212154 / 7 18 / 7 42 .解答 (1 ) 算法的 基本设 计思想 可以将这 个问题 看做是 把数组 ab 转换成 数组 ba (a 代表数组 的前 p 个元素,b 代表 数组中 余下的 n-p 个元 素) ,先将 a 逆置 得到 a -1 b , 再将 b 逆置得 到 a -1 b -1 , 最后将整个 a -1 b -1 逆置 得到(a -1 b -1 ) -1 ba。设 Reverse 函数执 行将数组 元素逆 置的操 作, 对 abcdefgh 向左循环 移动 3 (p3 )个位 置的过 程如下 Reverse0,p-1 得到 cbadefgh ; Reversep,n-1 得到 cbahgfed ; Reverse0,n-1 得到 defghabc ; 注Reverse 中,两个 参数分 别表示 数组中 待转换 元素的 始末位 置。 (2 ) 使用 c 语言 描述算 法如下 void Reverseint R[],int from,int to { int i,temp; fori 0; i to-from1/2; i key 7 8 30 11 18 9 14 次数 1 1 1 1 3 3 2 Hkey 0 1 2 3 4 5 6 次数 3 2 1 2 1 5 4 { temp R[fromi]; R[fromi] R[to-i]; R[to-i] temp; } } ∥Reverse void Converseint R[],int n,int p{ ReverseR,0,p-1; ReverseR,p,n-1; ReverseR,0,n-1; } (3 ) 上述 算法中 三个 Reverse 函数 的时间 复杂度 分别为 / 2 p  、 / 2 np  和 / 2 n  , 故所 设计 的算法的 时间复 杂度为 n  , 空间 复杂度 为 1  。 另解 ,借助辅助数组 来实现 算法思想 创建 大小 为 p 的 辅助数 组 S ,将 R 中前 p 个 整数依 次暂存 在 S 中 ,同时 将 R 中后 n-p 个整 数左 移,然后 将 S 中暂 存的 p 个数 依次放 回到 R 中的后 续单元 。 时间复杂 度为 n  ,空间复 杂度为 p  。 43 .解答 1 操作码 占 4 位 , 则 该指令 系统最 多可 有 2 4 16 条 指令 ; 操 作数 占 6 位 , 寻址 方式 占 3 位 , 于 是寄存 器编 号占 3 位, 则 该机 最多 有 2 3 8 个 通用寄 存器 ;主 存容量 128KB ,按 字编 址,计 算机 字长 为 16 位 ,划 分为 128KB/2B2 16 个存储单 元, 故 MDR 和 MAR 至少 各需 16 位 。 2 PC 和 Rn 可表示 的地址 范围均为 0 ~2 16 -1 , 而主 存地址 空间为 2 16 , 故转移指 令的目 标地址 范围是 0000H ~ FFFFH (0 ~2 16 -1 ) 。 3 汇编语 句 “add R4, R5 ” ,对应 的机器 码为 0010 0011 0001 0101B2315H 。 该指令执 行后, 寄存器 R5 和 存储单元 5678H 的内容 会改变 。执行 后,R5 的内容从 5678H 变成 5679H 。存 储单元 5678H 中 的内容 变成该 加法 指 令计算 的结 果 5678H +1234H68ACH 。 44 .解答 1 数据 Cache 有 8 个 Cache 行 ,每 个 Cache 行大 小为 64B ,Cache 中每 个字块 的 Tag 字 段的 位数 是 28 -9 =19 位 ,此外 还需 使 用一个 有效位 ,合 计 20 位。因 此, 数据 Cache 的 总容量 应 为 8 64 +20 /8B =532B 。 2 数组 a 在主 存的存 放位置 及其 与 Cache 之间的 映射关 系如下 图所示 数组按行 优先方 式存放 , 首 地址 为 320 , 数 组元素 占四个 字节 。 a[0][31] 所 在的 主存块 对应 的 Cache 行号为 320 +31 4 DIV 64 6 ; a[1][1] 所 在的主 存块对 应的 Cache 行 号为 320 +256 4 +1 4 DIV 64 MOD 8 5 。 3 编译 时 i 、j 、sum 均分配 在寄存 器中, 故数据 访问命 中率仅 考虑数组 a 的情况 。 ① 该 程序的 特点是 数组中 的每一 个元素 仅被使 用一次 。 数 组 a 按行 优先存 放, 数 据 Cache 正好 放下数 组半 行中的全 部 元素 ,即元素 的存 储顺序 与使用 次序高 度的吻 合, 每个字 块的 16 个 int 型 元素 中 ,除访 问的第 一个 不会命中 ,接下 来的 15 个都会 命中。 访问全 部字块 都符合 这一规 律,故 命中率 为 15 /16 ,即 程序 A 的数据 访 问命中率 是 93.75 。 ② 程序 B 按 照数组 的列执 行外层 循环, 在执行 内层循 环的过 程中, 将连续 访问 不同行 的同一 列的数 据, 不同行的 同一列 数组使 用的是 同一 个 Cache 单元, 每次都 不会命 中, 故命中 率是 0 由于从 Cache 读 数据比 从 主 存 读数据 快很多 ,所以 程序 A 的执行 比程 序 B 快 得多 。 注 意 本题考查 Cache 容量 计算, 直接映 射方式 的地址 计算, 以及命 中率计 算( 注意 行优先 遍历与 列优 先遍历命 中率差 别很大 ) 。 45 .解答 1 用位图 表示磁 盘的空 闲状态 。 每一 位表示 一个磁 盘块的 空闲状 态, 共 需 要 16 384 /32512 个字512 4 个字节2KB , 正好可放 在系统 提供的 内存中 。 2 采用 CSCAN 调 度算法 ,访问 磁道的 顺序和 移动的 磁道 数如下 表所示 被访问的 下一个 磁道号 移动距离 (磁道 数) 120 20 30 90 50 20 90 40 移动 的 磁 道数 为 20902040170 ,故总 的移动 磁道时 间为 170ms 。 由于转速 为 6000r/m ,则平 均旋转 延迟 为 5ms , 总的旋 转延迟 时间20ms 。 由于转速 为 6000r/m , 则读取 一个磁 道上一 个扇区 的平均 读取时 间为 0.1ms , 总的 读取扇 区的时 间平均 读取 时间为 0.1ms ,总 的读取 扇区的 时间 为 0.4ms 。 综上,读 取上述 磁道上 所有扇 区所花 的总时 间为 190.4ms 。 3 采用 FCFS ( 先来 先服务 ) 调度 策略更 高效。 因为 Flash 半导体存 储器的 物理 结构不 需要考 虑寻道 时间 和旋转延 迟,可 直接 按 I/O 请 求的先 后顺序 服务。 46 .解答 1 由于该计 算机的 逻辑地 址空间 和物理 地址空 间均 为 64KB 2 16 B , 按字节 编 址, 且 页的大 小为 1K 2 10 , 故逻辑地 址和物 理地址 的地址 格式均 为 页号/ 页框号 (6 位) 页内偏移 量(10 位) 17CAH 0001 0111 1100 1010B , 可知该 逻辑地 址的页 号为 000101B 5 2 根据 FIFO 算法 , 需 要替换 装入时 间 最早 的页 , 故需 要置换 装入时 间最早 的 0 号页 , 即将 5 号页 装入 7 号 页框中 ,所以 物理地 址为 0001 1111 1100 1010B 1FCAH。 3 根据 CLOCK 算法 , 如果 当前指 针所指 页框的 使用 位为 0 ,则替 换该页 ;否则 将使 用位清 零,并 将指 针指向下 一个页 框,继 续查找 。根据 题设和 示意图 ,将 从 2 号页 框开始 ,前 4 次查 找页框 号的顺 序为2 →4 →7 →9 ,并 将对应 页框的 使用位 清零。 在第 5 次查找 中,指 针指 向 2 号 页框, 因 2 号 页框的 使用 位为 0 ,故淘 汰 2 号页框 对应的 2 号 页,把 5 号 页装入 2 号 页框中 ,并将 对应 使用位 设置为 1 , 所以 对应的物 理地址 为 0000 1011 1100 1010B 0BCAH 。 47 .解答 ⑴ 当主机甲 和主机 乙同时 向对方 发送数 据时, 信号在 信道 中发生 冲突后 ,冲突 信号继 续向两 个方向 传播。 这种情况 下 两台 主机均 检测到 冲突需 要经过 的时间 最短, 等于 单程的 传播时 延 t0 2km/200 000km/s 0.01ms 。 主机甲(或主 机乙 ) 先 发送一 个数据 帧,当该数 据帧即 将到达 主机乙( 或 主机 乙)时,主机乙( 或主机 甲) 也开始发 送一个 数据帧 , 这 时 , 主机 乙 ( 或主机 甲)将立 刻检测 到冲突 , 而 主机甲(或 主机乙 )要检测 到冲突 , 冲突信 号还需 要从 主机
展开阅读全文

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