资源描述
科 目 代 码 ： 8 2 9 科 目 名 称 ： 计 算 机 专 业 基 础 第 1 页 共 5 页 南 京 航 空 航 天 大 学 2 0 1 8 年 硕 士 研 究 生 入 学 考 试 初 试 试 题 （ A 卷 ） 科目代码: 829 满分: 150 分 科目名称: 计算机专业基础 注 意 : 认 真 阅 读 答 题 纸 上 的 注 意 事 项 ； 所 有 答 案 必 须 写 在 答 题 纸 上 ， 写 在 本 试 题 纸 或 草 稿 纸 上 均 无 效 ； 本 试 题 纸 须 随 答 题 纸 一 起 装 入 试 题 袋 中 交 回 ！ 数据 结构 部分（ 5 0 分） 1 （10 分）给定 n 个村庄之 间的交通图，边上 的值表示这条道路 的长度，现在要从 这 n 个 村 庄 中选 择 一 个 村庄 建 一 所医 院 ， 问 这所 医 院 应 建在 哪 个 村 庄， 才 能 使离 医 院 最 远的 村 庄 到 医 院的 路 程 最 短？ 试 选 择或 构 造 一 种适 当 的 数 据结 构 并 设 计一 个 算 法， 并 应 用 该算 法 解 答下图所示的实例，给出算法执行过程示意图。 2 （10 分） 详细解释哈希表的工作原理。 以此为例， 将关键字序列 （51， 83， 43， 15， 62， 59，74，61）存储在长度为 10 的哈希表中，使用哈希函数 H(key) = Key % 10 ，并采用链 地址法解决冲突，画出哈希表示意图。 3 （ 10 分 ） 设 有 一批 需 实 时处 理 的 数据 元 素 组 成集 合 S ， 实 时处 理 开 始后 ， 每 隔一 秒 钟 收 到一个新的数据元素加入 S。 现要求在每次接收一个新元素之前， 找出 S 中现有的最小元素 并将其输出 （从 S 中删除） 。 试选择或构造一种适当的数据结构并设计一个算法， 尽可能高 效地完成上述任务 。 例如： S=(59,31,29,18,78,26,48,10,65,35)， 新接受的数据为 39， 12， 46.。以此为例说明算法执行过程示意图。 4 （ 10 分 ） 设一 个 带 头结 点 的 单链 表 L ， 数 据元 素 为 整数 ， 其 中大 部 分 为 正数 ， 少 数为 负 数 ， 编写 函 数 ， 采用 高 效 的算 法 调 整 链表 ， 实 现 将负 数 结 点 移到 链 表 尾部 ， 并 返 回调 整 后 链表中的第一个负数结点位置。先给出算法思想，再写相应代码。 5. （ 10 分 ） 设二 叉 树 T， 用 二叉 链 表 结 构存 储 ， 元素 值 为 整 数且 互 不 相 同。 编 写 非 递归 函 数， 对给定的 2 个整数， 若 2 个都不是 T 的元素， 输出-2； 若 1 个不是 T 的元素， 输出 -1； 若 2 个都是 T 的元素，输出两者所在的层数的间隔数。要求先给出算法思想，再写代码。 V3 V2 V4 V1 3 4 6 10 2科 目 代 码 ： 8 2 9 科 目 名 称 ： 计 算 机 专 业 基 础 第 2 页 共 5 页 组成 原理 部分（ 5 0 分） 6.(8 分）如下为一流水和一非流水处理器的参数，请按要求计算： Parameter Pipelined Non-Pipelined Clock Rate 500MHZ 250MHZ CPI for ALU instruction 1 1 CPI for Control instruction 2 1 CPI for Memory instruction 2.5 1 若 一 程序 有 20% 的 ALU 指 令 , 10% 的 控 制指 令 和 70% 的 访 存指 令 ， 上 述哪 种 设 计 更 快？ 请 用合适的指标评估 。 7.（10 分）若有一源程序 hello.c 文件： 1) 简述如何生成 相应的可执行程序； 2）简述该可执行 程序如何在计算机上执行的过程。 8. （10 分） 对于一 n 位运算器， 通常得到其运算结果 F 的同时也输出相应的标志信号如 ZF （零标志位） ，SF（符号标志位） ，CF（进位标志位）和 OF（溢出标志位）等： 1）请用逻辑表达式表示出上述各标志信号如何根据运算结果 F 的相应位产生并做出解释 ； 2）若需完成两有符号数比大小，请问需采用何种运算且如何利用上述标志位判别； 9. （10 分） 假定计算机系统主存空间大小为 32Kx16 位， 且有一个 4K 字的 4 路组相联 Cache， 主存和 Cache 之间的数据交换块的大小为 64 字。 假定 Cache 开始为空， 处理器顺序地从存 储单元 0、 1、 、 4351 中取数， 一共重复 10 次。 设 Cache 比主存快 10 倍。 采用 LRU 算法。 试分析 Cache 的结构和主存地址的划分。说明采用 Cache 后速度提高了多少？ 10.(12 分）如图所示的单周期数据通路执行如下 MIPS 32 指令 Address (Byte) Instruction 100 beq $R2, $R4, 7 # The address of register Rn is n 执行上述指令前各寄存器的内容如下表： Register Value (10 进制 ) R1 12 R2 16 R3 8 R4 16科 目 代 码 ： 8 2 9 科 目 名 称 ： 计 算 机 专 业 基 础 第 3 页 共 5 页 1） （2 分） 将上述指令转换为 2 进制表示的 32 位机器码， 其中操作码对应的机器编码可以 相同位数的* 号代替，请按照 MIPS 32 指令的格式区分各部分以方便查阅。 2） （10 分） 除非特别声明， 请以 10 进制方式填写下表中执行该指令时的数据通路信号值和 控制信号值，若值未知或不需要，可用 x 表示。 Signal Value Register File Read Addr 1 Read Addr 2 Write Addr Write Data RegWrite ALUOp (2 进制显示) MemtoReg ALUSrc Zero The address to be stored in PC科 目 代 码 ： 8 2 9 科 目 名 称 ： 计 算 机 专 业 基 础 第 4 页 共 5 页 操作 系统 部分（ 5 0 分） 11. 填空题（ 2 分 x7=14 分) 1）操作系统的两大特征是（ ） 。 2） 单道系统中， 假设一批作业同时到达， 若想平均周转时间最短， 采用( )调度 算法。 3）时间片轮转调度算法中，如果时间片无穷大，该算法变成了（ ）调度算法。 4） 在某系统中有 5 个并发进程， 都需要同类资源 6 个， 问该系统肯定不会发生死锁时最 少资源数是（ ） 。 5） 对于首次适应算法、 最佳适应算法和循环首次适应算法， 可以保留高地址部分的大空 闲区的算法是（ ） 。 6） 有 m 个进程共享同一临界资源， 若使用信号量机制实现对一临界资源的互斥访问， 则 信号量的变化范围是（ ） 。 7）装入时动态链接和运行时动态链这两种方式， （ ）更节约内存。 12. （ 9 分 ） 多 道 程 序系 统 有 一 个 CPU 和 两 台 独占 设 备 ， 即 IO1 和 IO2， 现 在 有 3 个 优 先 级 别从高到低的作业 J1、J2、J3 到达，它们使用资源的先后顺序和占用时间分别是： J1：IO2（60 ） ；CPU（20） ；IO1（60） ；CPU（20） J2：IO1（40 ） ；CPU（40） ；IO2（80） J3：CPU（60 ） ；IO1（40） 假 设 处理 机 调 度 采用 可 抢 占的 优 先 级 算法 ， 设 备 不能 抢 占 ， 忽略 调 度 时间 ， 时 间 单位 为 分 钟。计算下列问题： 1）分别计算 3 个作业的周转时间（3 分） 2）3 个作业全部完成时 CPU 的利用率（3 分） 3）3 个作业全部完成时 IO1 的利用率（3 分） 13. （ 9 分 ） 磁 盘 请 求 柱 面 按 10, 22, 20, 2, 40, 6, 38 的 次 序 到 达 ， 当 前磁 头 在 柱 面 20 上。 1）磁盘访问时间由哪几部组成，如何计算？（3 分） 2）计算采用 SSTF，SCAN 算法（先由小到大）磁头移动顺序。 （3 分） 3）如何应用 RAID(廉价磁盘冗余阵列)提高磁盘的访问速度，请画图示意。 （3 分） 14.（9 分） 五个进程 P1 ，P2，P3，P4， P5 均需要使用 资源 A、 B、C。其中， A、B、C 资源 的总数分别为 10，5，7。当前已分配资源情况和各进程的最大资源需求如下表所示。科 目 代 码 ： 8 2 9 科 目 名 称 ： 计 算 机 专 业 基 础 第 5 页 共 5 页 进程 最大需求资源 已分配资源 P1 （7,5,3） （0,1,0） P2 （3,2,2） （2,0,0） P3 （9,0,2） （3,0,2） P4 （2,2,2） （2,1,1） P5 （4,3,3） （0,0,2） 1) 什么是安全状态？（ 2 分） 2) 系统进入不安全状态是否一定会产生死锁？（3 分） 3) P1 请求资源（ 1,0,2） ，请根据银行家算法判断是否应该为其分配资源(4 分) 15 （9 分）某教学楼 楼梯较窄，为了安 全规定课间，一旦 有人从上往下走， 则不允许任何 人 从 下 往 上 走 ， 但 此 时 可 以 允 许 多 人 同 时 往 下 走 ， 反 之 依 然 。 请 用 设 置 合 适 的 信 号 量 （ 2 分） ，应用 PV 操作完成此同步问题（5 分） ，并分析是否会产生饥饿现象（2 分）
展开阅读全文