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