2014_829计算机专业基础试题

科目代码 829 科目名称 计算机专业基础 第 1 页 共 5 页 南京航空航天大学南京航空航天大学 20142014 年硕士研究生入学考试初试试题年硕士研究生入学考试初试试题 A A 卷卷 科目代码 829 满分 150 分 科目名称 计算机专业基础 注意 认真阅读答题纸上的注意事项认真阅读答题纸上的注意事项 所有答案必须写在所有答案必须写在答题纸答题纸上上 写在本试题纸或草稿纸上均无写在本试题纸或草稿纸上均无 效效 本试题纸须随答题纸一起装入试题袋中交回本试题纸须随答题纸一起装入试题袋中交回 一 数据结构部分 50 分 1 10 分 解释哈希表工作原理 将关键字序列 75 54 48 90 18 22 84 63 存 储在长度为 10 的哈希表中 使用哈希函数 H key Key 10 并采用二次探测再散列法 解决冲突 画出哈希表示意图 2 10 分 试用 Floyd 算法 求解下图中各顶点之间的最短路径 写出算法过程中每一步 的状态 3 10 分 设有 6 个字符 其权值为 12 40 16 8 14 10 给出进行 Huffman 编码 的数据结构和执行过程示意图 4 10 分 设一个带头结点的单链表 L 数据元素为 a1 a2 a3 a4 an 编写函数 调整该链表 使得数据元素次序为 a1 a3 an a4 a2 要求 T n O n 先 给出算法思想 再写出相应代码 5 10 分 设有一家谱树 T 用二叉链表结构存储 孩子兄弟表示法 树中的结点信息为 成员名字 编写函数 输出家谱中共有多少代以及最后一代人数和成员名字 要求先给出 算法思想 再写出相应代码 二 操作系统部分 50 分 一 填空题 共 10 小题 每小题 1 分 共 10 分 1 下列关于操作系统的四种陈述中 正确的是 A 批处理操作系统必须在响应时间内处理完一个任务 B 实时操作系统必须在规定时间内处理完来自外部的事件 C 分时操作系统必须在周转时间内处理完来自外部的事件 D 分时操作系统必须在调度时间内处理完来自外部的事件 V2 V4 V1 V3 12 2 3 7 15 科目代码 829 科目名称 计算机专业基础 第 2 页 共 5 页 2 设有两个进程 A B 各按以下顺序使用 P V 操作进行同步 A 进程 B 进程 a1 b1 P s1 P s2 a2 b2 P s2 P s1 a3 b3 V s2 V s1 a4 b4 V s1 V s2 a5 b5 试问在下列执行顺序中 哪种情况会发生死锁 A a1 a2 a3 a4 B b1 b2 b3 b4 b5 C a1 a2 b1 b2 a3 b3 D a1 b1 a2 b2 a3 b3 3 在内存管理中 内存利用率高且保护和共享容易的是 内存管理方式 A 分区管理 B 分页管理 C 分段管理 D 段页式管理 4 操作系统中 很多事件会引起调度程序的运行 但下列事件中不一定引起操作系统调度 程序运行是 A 当前运行着的进程出错 B 当前运行着的进程请求输入 输出 C 有新的进程进入就绪状态 D 当前运行的进程时间片用完 5 操作系统中调度算法是核心算法之一 下列关于调度算法的论述中正确的是 A 先来先服务调度算法对即对长作业有利也对段作业有利 B 时间片轮调度算法转只对长作业有利 C 实时调度算法也要考虑作业的长短问题 D 高相应比者优先调度算法既有利于短作业又兼顾长作业的作业还实现了先来先服务 6 操作系统中产生死锁的根本原因是 A 资源分配不当和 CPU 太慢 B 系统资源数量不足 C 作业调度不当和进程推进顺序不当 D 用户数太多和 CPU 太慢 7 内存管理中把作业地址空间中使用的逻辑地址转变为内存中的物理地址称为 A 链接 B 装入 C 重定位 D 虚拟化 8 I O 设备管理是操作系统的重要功能 那么下列对设备属性的描述正确的是 A 字符设备的基本特征是可寻址到字节 即能指定输入的源地址或输出的目标地址 B 共享设备必须是可寻址的和可随机访问的设备 C 共享设备是指同一时间内运行多个进程同时访问的设备 D 在分配共享设备和独占设备时都可能引起进程死锁 9 程序设计时需要调用操作系统提供的系统调用 被调用的系统调用命令经过编译后 形 成若干参数和 A 访管指令或软中断 B 启动 I O 指令 C 屏蔽中断指令 D 通道指令 10 以时间换空间或者以空间换时间是操作系统的基本技术 以下以空间换时间的机制是 科目代码 829 科目名称 计算机专业基础 第 3 页 共 5 页 A SPOOLING B 虚拟存储技术 C 通道技术 D 覆盖技术 二 简要分析题 共 2 小题 每小题 5 分 共 10 分 1 从操作系统设计角度谈谈进程控制块的作用 2 解释静态链接和动态链接是现代操作系统中两种重要的链接方式 试比较同一程序经过 静态链接和动态链接后的可执行文件大小 如果有不同分析原因 三 综合应用题 共 5 小题 共 30 分 1 6 分 某操作系统采用分页式虚拟存储管理方法 现有一个进程需要访问的地址序列 字 节 分别是 115 228 120 88 446 102 321 432 260 167 假设该进程的第 0 页 已经装入内存 并分配给该进程 300 字节内 页的大小为 100 字节 试回答以下问题 1 按LRU调度算法将产生多少次页面置换 依次淘汰的页号是什么 页面置换率为多少 2 LRU 页面置换算法的基本思想是什么 2 6分 设 磁 盘 的I O请 求 队 列 中 的 柱 面 号 分 别 为 155 158 139 118 190 260 250 138 284 磁头初始位置为 200 磁臂方向由小到大 1 请给出采用 SSTF 的磁盘调度算法的磁头的柱面移动次数 2 SSTF 的磁盘调度算法有何缺 点 3 6 分 简述消息缓冲队列通信机制 并用信号量和 wait signal 操作实现消息缓冲队 列通信机制中的发送和接受原语 4 6 分 设系统中有三种类型的资源 A B C 和五个进程 P1 P2 P3 P4 P5 A 的资源的数量为 17 B 的资源的数量为 5 C 的资源的数量为 20 在 T0 时刻状态如下 最大资源需求量 已分配资源需求量 A B C A A B C P1 5 5 9 2 1 2 P2 5 3 6 4 0 2 P3 4 0 11 4 0 5 P4 4 2 5 2 0 4 P5 4 2 4 3 1 4 剩 余 资 源 数 A B C 2 3 3 系统采用银行家算法实施死锁避免策略 1 T0 时刻是否为安全状态 若是请给出安全序列 2 在 T0 时刻 若进程 P2 请求资源 0 3 4 是否能实施资源分配 为什么 3 在 2 基础上 若进程 P4 请求资源 2 0 1 是否能实施资源分配 为什么 5 6 分 一个进程某时刻的页表如下图所示 页号 标志 内存块号 0 1 2 1 0 2 1 8 科目代码 829 科目名称 计算机专业基础 第 4 页 共 5 页 3 1 1 4 0 5 1 0 本题中的数字均为十进制 页号 块号都以 0 开始 页的大小为 2K 字节 标志为 1 表示页 面在内存 标志为 0 表示不在内存 请回答下列问题 1 简述分页式虚拟存储系统中 一个逻辑地址到物理地址的转换过程 并画出地址转换机 构图 2 逻辑地址 5188 和 3199 对应的物理地址是什么 三 计算机组成原理部分 50 分 1 10 分 关于浮点数的表示和运算 请回答下列问题 1 简单叙述浮点机器数加减运算所必需的 5 个步骤 5 分 2 若某机内部浮点机器数的阶码用移码表示 偏置常数为 2 4 尾数用规格化补码表示 无隐含位 基数为 2 格式如下 数符 阶码 尾数 1 位 5 位 14 位 已知按照该格式表示的浮点机器数 x 浮 56030H y 浮 D9F00H 求 x y 的和所对应的 机器数 x y 浮 请用 16 进制表示 5 分 2 10 分 关于总线以及通信请回答下列问题 1 假设 N 是总线允许接纳的最大设备数 针对总线的判优控制 即链式查询方式 计数 器定时查询方式以及独立请求方式 请问这三种方式各需要最少多少根额外的控制线 才能完成总线判优控制 6 分 2 某异步串行传输系统中 若字符格式为 1 位起始位 7 位数据位 1 位奇校验位 1 位终止位 每分钟最快能够传输 12000 个字符 则该系统的波特率和比特率分别是多 少 bps 位 秒 4 分 3 10 分 某 16 位机器所使用的指令格式和寻址方式如下所示 该机有两个 20 位基址寄 存器 四个 16 位变址寄存器 十六个 16 位通用寄存器 指令汇编后有三种格式 如下图 所示 其中的 S 源 D 目标 都是通用寄存器编码 M 是主存单元地址 MOV 是传送指令 采用格式 1 STA 为写数指令 LDA 为读数指令 它们都可以采用格式 2 或格式 3 16 进制 操作码分别为 MOV OP 9H STA OP 13H LDA OP 27H 格式 1 15 10 9 8 7 4 3 0 OP D S 其中第 9 8 位未定义 指令中汇编为 00 格式 3 与此类同 格式 2 15 10 9 8 7 4 3 0 OP 基址 S 或 D 变址 16 位位移量 其中第 9 8 位为 01 或 10 分别表示选用一个基址寄存器 其它编码无效 第 3 0 位 16 个编码中选用 4 个编码分别指明 1 个变址寄存器 其它编码无效 格式 3 15 10 9 8 7 4 3 0 OP S 或 D 20 位内存地址 其中 20 位内存地址由第一行的 3 0 位和第二行构成 要求 1 分析三种指令的寻址方式特点 3 分 2 分析处理机完成每一种格式的指令所花时间的长短 并说明原因 5 分 3 分析指令 9C268FA5 H 的功能 2 分 科目代码 829 科目名称 计算机专业基础 第 5 页 共 5 页 4 10 分 某计算机有 64KB 的主存和 1KB 的 Cache Cache 每组 2 块 每块 64 字节 存 储系统按组相联方式工作 要求 1 设计主存地址格式 2 若 Cache 原来是空的 CPU 以字节为单位依次从 0 号地址单元顺序访