1、科目代码：829 科目名称：计算机专业基础 第 1 页 共 5 页 南京航空航天大学南京航空航天大学2015 年硕士研究生入学考试初试试题（ A 卷 ） 2015 年硕士研究生入学考试初试试题（ A 卷 ） 科目代码: 829 科目名称: 计算机专业基础 满分: 150 分 注意: 认真阅读答题纸上的注意事项；所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无 认真阅读答题纸上的注意事项；所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；本试题纸须随答题纸一起装入试题袋中交回！效；本试题纸须随答题纸一起装入试题袋中交回！数据结构部分（50 分） 数据结构部分（50 分） 1 （10 分
2、）已知带权图如下所示，用 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，数据元素为整数，编写函数，通过调整该链表的结点指针，对该链表进行简单选择排序（
3、元素值从小到大） 。先给出算法思想，再写相应代码。 5.（10 分）设二叉树 T，用二叉链表结构存储。编写函数，输出最长一枝（根到叶子）上的所有结点值。要求先给出算法思想，再写出相应代码。 操作系统部分（50 分） 操作系统部分（50 分） 1.（15 分）文件系统是操作系统的主要功能之一，请设计一个文件系统，需给出以下信息：（1）给出描述文件的数据结构（即文件控制块）和目录结构； （2 分） （2）以索引节点为文件系统的物理文件组织结构，图示索引节点结构，说明其优点； （3分） V4 V2V6V3V5 V1 2 15 4 5 8 3 6 6 4科目代码：829 科目名称：计算机专业基础 第
4、2 页 共 5 页 （3）为该文件系统设计几个必要的系统调用，选其中一个为例，详细说明实现该系统调用的方法和过程（注意要使用以上设计中的数据结构） 。 （10 分） 2 （10 分）某机场只有一条飞机跑道，为了提高效率和安全性，现规定：当飞机跑道有飞机起飞时，不允许飞机降落，但此时可以让多架飞机逐个利用跑道起飞；反之，当有飞机降落进入跑道时则不允许起飞飞机进入跑道，但允许飞机依次降落在跑道上，然后驶出跑道。请解决以下问题： （1）请利用信号量和 P、V 操作正确实现飞机在跑道上起降。 （要求：说明所设的信号量的意义及初值） ； （2）若把飞机看作进程，为了合理实现对飞机进程的管理，给出描述飞机
5、进程的数据结构。 3. （5 分） 某段式存储管理系统中采用如下段表：(用十进制) 段号 段的长度（字节）主存起始地址 0 500 150 1 180 800 2 600 1000 3 1680 1850 试回答： (1)计算0，150，1，98，2，601，3，50的内存地址，其中方号内的第一元素为段号，第二元素为段内地址。 (2)存取主存中的一条指令或数据至少要访问几次内存？如何提高速度？ 4. （10 分）完成以下两个有关操作系统算法的问题： (1)（5 分）LRU 算法的思想和依据是什么？请利用 LRU 算法解决下列问题：在一个请求分页系统中，假如系统分配给一个作业的物理块数为 3，此
6、作业的页面走向为 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(先由小到大开始扫描)磁盘调度算法，磁头移动多少个磁道。 科目代码：829 科目名称：计算机专业基础 第 3 页 共 5 页 5.（5 分）按照下图说明操作系统中引入缓冲的好处 6 （5 分）假设系统有五类独占资源：r1，r2，r3，r4，r5
7、，各类资源分别有：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 分） 计算机组成原理部分 （
8、50 分） 一选择题（1 分/题*10 题=10 分） 计算机组成原理部分 （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.
9、 8000 00C0H B. 8000 00C1H C. 8001 00C2H D. 8000 00C3H 4. 存储容量为 16K4 位的 DRAM 芯片，其地址引脚和数据引脚数各是（ ） 。 A. 7 和 1 B. 7 和 4 C. 14 和 1 D. 14 和 4 5. 以下寻址方式中， （ ）方式得到的操作数在通用寄存器中。 A. 寄存器寻址 B. 寄存器间接寻址 C. 直接寻址 D. 立即数寻址 6. 下列有关指令和微指令之间关系的描述中，正确的是（ ） 。 A一条指令的功能通过执行一个微程序来实现 B一条指令的功能通过执行一条微指令来实现 科目代码：829 科目名称：计算机专业基础
10、 第 4 页 共 5 页 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
11、. 6400MB/s 9. 假定一个磁盘存储器有 4 个盘片，用于记录信息的柱面数为 2000，每个磁道上有 3000个扇区，每个扇区 512B，则该磁盘存储器的容量约为（ ） 。 A.12MB B. 24MB C. 12GB D. 24GB 10. 单级中断系统中，中断服务程序内的中断处理顺序是（ ） 。 I保护现场 II开中断 III关中断 IV保存断点 V中断事件处理 VI恢复现场 VII中断返回 AIVVIIIVII BIIIIVVII CIIIIVVVIVII DIVIVVIVII 二 （10 分）假定一台 16 位字长的机器中带符号整数用补码表示，浮点数的机器数表示如下图，寄存器
12、R1 和 R2 的内容分别为 R1：037AH，R2：F895H。不同指令对寄存器进行不同操作，因而，不同指令执行时寄存器内容对应的真值不同。假定执行下列运算指令时，操作数为寄存器 R1 和 R2 的内容，则 R1 和 R2 中操作数的真值分别为多少？ (1)无符号数加法指令（3 分） (2)带符号整数乘法指令（3 分） (3)单精度浮点数减法指令 (4 分) 假定浮点机器数的阶码和尾数分别用移码和补码表示，且数符 1 位，阶码 5 位，尾 数 10 位，规格化表示，无隐含位，格式如下： 数符 阶码 尾数 1 位 5 位 10 位 三 （10 分）某高级语言语句“for (i=0;iN;i+)
13、 sum=sum+ai;” ，其中 N=100，假定数组 a 中每个元素都是 short 类型，依次连续存放在首地址为 0 x0000 0c00 的内存区域中。运行上述代码的处理器带有一个数据区容量为 64KB 的 data cache，其主存块大小为 64B，采用 2 路组相联映射、随机替换和回写（Write Back）方式；可寻址的最大主存地址空间为 4GB，配置的主存容量为 2GB，按字节编址。请回答下列问题。 （1）主存地址至少占几位？（1 分） （2）data cache 共有多少组？主存地址如何划分？（3 分） （3）数组 a 占用几个主存块？所存放的主存块号分别是什么？ （3 分
14、） 科目代码：829 科目名称：计算机专业基础 第 5 页 共 5 页 （4）在访问数组 a 的过程中数据缺失率为多少？（3 分） 四 （10 分）某机指令字长 16 位，每个操作数的地址码为 6 位，指令分为零地址、一地址和二地址三种格式： (1)若操作码长度固定，零地址指令有 M 种，一地址指令有 N 种，二地址指令有多少种？（4分） (2)若操作码位数可变，则二地址指令最多允许有几种？（6 分） 五 （10 分）设 16 位计算机，实现 Booth 算法的运算器框图如下所示，各寄存器符号位的约定依算法而定。假定被乘数存于寄存器 A 中。若控制器为组合逻辑。则 （1）请写出完成乘法指令 MUL(为主存地址)的全部微操作（8 分） ； （2）指出实现该乘法所对应的加和移位节拍的执行次数（2 分） 。 0 A n+1n+2 位加法位加法器器控控制制0 X n+10 Q n n+1移位和加移位和加控制逻辑控制逻辑计数器计数器 CGM00,10110右移右移
