武汉科技大学2006年数据结构考研试题

一、        选择合适的数据结构表示两个集合:
A={ai,i=1,2……,m|ai∈Z}
B={bi,i=1,2……,n|bi∈Z}，Z表示整数集合。
定义数据结构（2分），设计算法求它们的并集（6分）和差集（6分）以及差集中的数据元素个数（4分）。（共18分）

二、设计一种数据结构表述一个体育班级，在空间复杂度为O(1)的前提下写出将该体育班级分解成男、女两个集合的算法，并要求每个集合中都按身高非递减顺序排列。（定义数据结构2分，算法12分，共14分）

三、车厢分为：硬座、硬卧和软卧。假设在铁道转轨网的输入端有n节车厢等待调度（车厢的顺序是混乱的），设计一种数据结构和算法（可用伪码表示），要求这三种车厢在输出端铁道上的排列次序为：硬座在前，软卧在中，硬卧在后。（描述数据结构6分，算法8分，共14分）

四、设有n阶三对角矩阵A[0..n-1, 0..n-1]，将三条对角线上的元素逐行存放于数组B[0..3n-3]中，使得B[k]=A[i, j]，写出将A存入数组B中的算法（6分）以及由数组B确定A[i, j]的算法（10分），并写一算法求三对角矩阵在这种压缩存储表示下的转置矩阵C[0..3n-3]（6分）。（共22分）

五、一对老夫妻生有多个子女，有些子女已成亲并生有多个子女，……，如此繁衍下去（一夫一妻制，不考虑丧偶）。设计一种数据结构表述这样的大家族，并设计算法求任意家族成员的所有子女。（描述、定义数据结构8分，算法10分，共18分）

六、给定n个点的交通网，现要在这n个点中选一个建立供应站，显然供应站有n个备选点。假设选定ni为供应站，则该供应站到其余各顶点的最短路程中的最大值为Di，求出使得Di最小的ni。即要求选择合适的点作为供应站，希望离供应站最远的点到供应站的路程最短，设计算法求出该点。（定义数据结构4分，描述算法思路6分，算法8分，共18分）

七、软件专业的学生要学习一系列课程，其中有些课程必须在其先修课程完成后才能学习，具体关系如下：
课程编号                课程名称                先决条件
C1     程序设计基础                         无
C2                 离散数学                                 C1
C3                 数据结构                         C1，C2
C4                 汇编语言                                 C1
C5                 操作系统                                 C3
假设每门课程的学习时间为一学期，试为该专业的学生设计教学计划，使他们能在最短的时间内修完这些课程。设计算法求出每个学期的课程安排。（画出该问题的逻辑结构图4分，定义数据结构4分，描述算法思路6分，算法8分，共22分）

八、有以下参赛选手比赛项目表：
姓名        项目1        项目2        项目3
丁一        跳高        跳远        100米
马二        标枪        铅球       
张三        标枪        100米        200米
李四        铅球        200米        跳高
王五        跳远        200米       
需要作一个竞赛日程安排，使得在尽可能短的时间内安排完比赛。为了较好解决这个问题，首先表述安排竞赛项目的数据结构模型，然后设计算法求出到底需要几个单位时间。（画出该问题的逻辑结构图6分，定义数据结构4分，描述算法思路6分，算法8分，共24分）