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

2018 江苏南京航空航天大学计算机专业基础考研真题数据结构部分（50 分）1．（10 分）给定 n 个村庄之间的交通图，边上的值表示这条道路的长度，现在要从这 n 个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短？试选择或构造一种适当的数据结构并设计一个算法，并应用该算法解答下图所示的实例，给出算法执行过程示意图。2．（10 分）详细解释哈希表的工作原理。以此为例，将关键字序列（51，83，43，15，62，59，74，61）存储在长度为 10 的哈希表中，使用哈希函数 H(key) = Key % 10 ，并采用链地址法解决冲突，画出哈希表示意图。3．（10 分）设有一批需实时处理的数据元素组成集合 S，实时处理开始后，每隔一秒钟收到一个新的数据元素加...