2018江苏南京航空航天大学数据结构与操作系统考研真题

2018 江苏南京航空航天大学数据结构与操作系统考研真题数据结构部分1．（5 分）设 n*n 的矩阵 A[1..n,1..n]为三角特殊矩阵，其逆对角线以上为 0，逆对角线以及逆对角线以下的所有元素按行序压缩存储在一维数组 B[1..n*(n+1)/2]中， 根据 i、j在满足何种条件下，计算元素 Aij 的存储位置，给出推导过程。2．（10 分）给出下图所示树的二种存储结构示意图。（1）带双亲的孩子链表表示法（2）孩子兄弟表示法并说明这二种存储结构的优缺点。3．（10 分）给定 n 个村庄之间的交通图，边上的值表示这条道路的长度，现在要从这 n 个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短？试选择或构造一种适当的数据结构并设计一个算法，并应用该算法解答...