2018 江苏南京航空航天大学计算机专业基础考研真题数据结构部分（50 分）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 的元素，输出两者所在的层数的间隔数。要求先给出算法思想，再写代码。组成原理部分（50 分）6.(8 分）如下为一流水和一非流水处理器的参数，请按要求计算：若一程序有 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) Instruction100 beq $R2, $R4, 7 # The address of register Rn is n执行上述指令前各寄存器的内容如下表：1）（2 分） 将上述指令转换为 2 进制表示的 32 位机器码，其中操作码对应的机器编码可以相同位数的*号代替，请按照 MIPS 32 指令的格式区分各部分以方便查阅。2）（10 分）除非特别声明，请以 10 进制方式填写下表中执行该指令时的数据通路信号值和控制信号值，若值未知或不需要，可用 x 表示。操作系统部分（50 分）11. 填空题（2 分 x7=14 分)1）操作系统的两大特征是（ ）。2）单道系统中，假设一批作业同时到达，若想平均周转时间最短，采用( )调度算法。3）时间片轮转调度算法中，如果时间片无穷大，该算法变成了（ ）调度算法。4）在某系统中有 5 个并发进程，都需要同类资源 6 个，问该系统肯定不会发生死锁时最少资源数是（ ）。5）对于首次适应算法、最佳适应算法和循环首次适应算法，可以保留高地址部分的大空闲区的算法是（ ）。6）有 m 个进程共享同一临界资源，若使用信...
