2015江苏南京航空航天大学计算机专业基础考研真题.doc-资料库

2015江苏南京航空航天大学计算机专业基础考研真题.doc.pdf-第1页.jpg

第1页 / 共4页

2015江苏南京航空航天大学计算机专业基础考研真题.doc.pdf-第2页.jpg

第2页 / 共4页

2015江苏南京航空航天大学计算机专业基础考研真题.doc.pdf-第3页.jpg

第3页 / 共4页

2015江苏南京航空航天大学计算机专业基础考研真题.doc.pdf-第4页.jpg

第4页 / 共4页

2015 江苏南京航空航天大学计算机专业基础考研真题数据结构部分（50 分） 1．（10 分）已知带权图如下所示，用 Prim 算法从顶点 2 开始产生最小生成树，说明算法思想，并给出求解所需的数据结构和每一步执行过程的相关数据变化。 2．（10 分）已知输入数据序列为 (68, 40, 25, 21, 33, 12, 58, 51, 16,36)，给出建立 3 阶 B-树示意图，再给出删除 51，16 后的 B-树。 3．（10 分））解释希尔排序的算法思想。对以下的数据序列，给出希尔排序过程的示意图。 (46,8,36,50,6,24,18,78,12,10) 4．（10 分）设一个带头结点的单链表 L，数据元素为整数，编写函数，通过调整该链表的结点指针，对该链表进行简单选择排序（元素值从小到大）。先给出算法思想，再写相应代码。 5.（10 分）设二叉树 T，用二叉链表结构存储。编写函数，输出最长一枝（根到叶子）上的所有结点值。要求先给出算法思想，再写出相应代码。操作系统部分（50 分） 1.（15 分）文件系统是操作系统的主要功能之一，请设计一个文件系统，需给出以下信息：（1）给出描述文件的数据结构（即文件控制块）和目录结构；（2 分）（2）以索引节点为文件系统的物理文件组织结构，图示索引节点结构，说明其优点；（3 分）（3）为该文件系统设计几个必要的系统调用，选其中一个为例，详细说明实现该系统调用的方法和过程（注意要使用以上设计中的数据结构）。（10 分） 2．（10 分）某机场只有一条飞机跑道，为了提高效率和安全性，现规定：当飞机跑道有飞机起飞时，不允许飞机降落，但此时可以让多架飞机逐个利用跑道起飞；反之，当有飞机降落进入跑道时则不允许起飞飞机进入跑道，但允许飞机依次降落在跑道上，然后驶出跑道。请解决以下问题：（1）请利用信号量和 P、V 操作正确实现飞机在跑道上起降。（要求：说明所设的信号量的意义及初值）；（2）若把飞机看作进程，为了合理实现对飞机进程的管理，给出描述飞机进程的数据结构。 3. （5 分）某段式存储管理系统中采用如下段表：(用十进制)

试回答： (1)计算[0，150]，[1，98]，[2，601]，[3，50]的内存地址，其中方号内的第一元素为段号，第二元素为段内地址。 (2)存取主存中的一条指令或数据至少要访问几次内存？如何提高速度？ 4. （10 分）完成以下两个有关操作系统算法的问题： (1)（5 分）LRU 算法的思想和依据是什么？请利用 LRU 算法解决下列问题：在一个请求分页系统中，假如系统分配给一个作业的物理块数为 3，此作业的页面走向为 3, 4，3, 3, 8， 3, 6, 8, 4, 3, 8, 3。试用 LRU 算法计算页面置换次数。 (2)（5 分）扫描算法(SCAN)是一种磁盘调度算法，它的优化目标是什么？设磁盘的 I/O 请求队列中的柱面号依次为：35, 58, 40, 28, 80, 160, 143, 38, 204，磁头初始位置为 95，若采用 SCAN(先由小到大开始扫描)磁盘调度算法，磁头移动多少个磁道。 5.（5 分）按照下图说明操作系统中引入缓冲的好处 6．（5 分）假设系统有五类独占资源：r1，r2，r3，r4，r5，各类资源分别有：2，2，2，1， 1 个单位的资源，有五个进程：P1，P2，P3，P4，P5,其中 P1 已占有 2 个单位的 r1，且申请一个单位的 r2 和一个单位的 r4；P2 已占有一个单位的 r2，且申请一个单位的 r1； P3 已占有一个单位的 r2 且申请一个单位的 r2 和一个单位的 r3；P4 已占有一个单位的 r4 和一个单位的 r5，且申请一个单位的 r3；P5 已占有一个单位的 r3 且申请一个单位的 r5。（1）试画出该时刻的资源分配图。（2 分）（2）什么是死锁定理，如何判断（1）给出的资源分配图中有无死锁，给出判断过程和结果。（3 分）计算机组成原理部分（50 分）一．选择题（1 分/题*10 题=10 分） 1. 下列正数中最大的数为（）。 A. (0010 0101)2 B. (36)10 C. (0101 0010)BCD D. (2B)16 2. 在补码加/减运算部件中，必须有( )电路，它一般用异或门来实现。 A. 译码 B. 编码 C. 溢出判断 D. 移位 3. 某计算机按字节编址，采用小端方式存储信息。其中，某指令的一个操作数为 32 位，该操作数的地址为 8000 00C0H，则该操作数的 MSB（最高有效字节）存放的地址是（）。 A. 8000 00C0H B. 8000 00C1H C. 8001 00C2H D. 8000 00C3H 4. 存储容量为 16K×4 位的 DRAM 芯片，其地址引脚和数据引脚数各是（）。 A. 7 和 1 B. 7 和 4 C. 14 和 1 D. 14 和 4 5. 以下寻址方式中，（）方式得到的操作数在通用寄存器中。

A. 寄存器寻址 B. 寄存器间接寻址 C. 直接寻址 D. 立即数寻址 6. 下列有关指令和微指令之间关系的描述中，正确的是（）。 A．一条指令的功能通过执行一个微程序来实现 B．一条指令的功能通过执行一条微指令来实现 C．一条微指令的功能通过执行一条指令来实现 D．一条微指令的功能通过执行一个微程序来实现 7. 下列有关程序计数器 PC 的叙述中，错误．．的是（）。 A. 每条指令执行后，PC 的值都会被改变 B. 指令顺序执行时，PC 的值总是自动加 1 C. 调用指令执行后，PC 的值一定是被调用过程的入口地址 D. 无条件转移指令执行后，PC 的值一定是转移目标地址 8. 假定一个同步总线的工作频率为 200MHz，总线中有 64 位数据线，每个总线时钟周期传输两次数据，则该总线的最大数据传输率为（）。 A. 800MB/s B. 1600MB/s C. 3200MB/s D. 6400MB/s 9. 假定一个磁盘存储器有 4 个盘片，用于记录信息的柱面数为 2000，每个磁道上有 3000 个扇区，每个扇区 512B，则该磁盘存储器的容量约为（）。 A.12MB B. 24MB C. 12GB D. 24GB 10. 单级中断系统中，中断服务程序内的中断处理顺序是（）。 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 二．（10 分）假定一台 16 位字长的机器中带符号整数用补码表示，浮点数的机器数表示如下图，寄存器 R1 和 R2 的内容分别为 R1：037AH，R2：F895H。不同指令对寄存器进行不同操作，因而，不同指令执行时寄存器内容对应的真值不同。假定执行下列运算指令时，操作数为寄存器 R1 和 R2 的内容，则 R1 和 R2 中操作数的真值分别为多少？ (1)无符号数加法指令（3 分） (2)带符号整数乘法指令（3 分） (3)单精度浮点数减法指令 (4 分) 假定浮点机器数的阶码和尾数分别用移码和补码表示，且数符 1 位，阶码 5 位，尾数 10 位，规格化表示，无隐含位，格式如下：三．（10 分）某高级语言语句“for (i=0;i

址和二地址三种格式： (1)若操作码长度固定，零地址指令有 M 种，一地址指令有 N 种，二地址指令有多少种？（4 分） (2)若操作码位数可变，则二地址指令最多允许有几种？（6 分）五．（10 分）设 16 位计算机，实现 Booth 算法的运算器框图如下所示，各寄存器符号位的约定依算法而定。假定被乘数存于寄存器 A 中。若控制器为组合逻辑。则：（1）请写出完成乘法指令 MULα (α 为主存地址)的全部微操作（8 分）；（2）指出实现该乘法所对应的加和移位节拍的执行次数（2 分）。

资料库

2015江苏南京航空航天大学计算机专业基础考研真题.doc

相关推荐

考研

热门标签

最新资料