科目代码：829科目名称：计算机专业基础第1页共5页南京航空航天大学2018年硕士研究生入学考试初试试题（A卷）科目代码:829满分:150分科目名称:计算机专业基础注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！数据结构部分（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的元素，输出两者所在的层数的间隔数。要求先给出算法思想，再写代码。V3V2V4V1346102科目代码：829科目名称：计算机专业基础第2页共5页组成原理部分（50分）6.(8分）如下为一流水和一非流水处理器的参数，请按要求计算：ParameterPipelinedNon-PipelinedClockRate500MHZ250MHZCPIforALUinstruction11CPIforControlinstruction21CPIforMemoryinstruction2.51若一程序有20%的ALU指令,10%的控制指令和70%的访存指令，上述哪种设计更快？请用合适的指标评估。7.（10分）若有一源程序hello.c文件：1)简述如何生成相应的可执行程序；2）简述该可...
