武汉科技大学2006数据结构考研试题研究生入学考试试题考研真题
● 摘要
武汉科技大学
2006年硕士研究生入学考试试题 考试科目及代码：数据结构 421 共2页 第1页 说 明：1．适用招生专业：计算机应用技术
2．答题内容写在答题纸上，写在试卷或草稿纸上一律无效。
3．考试时间3小时，总分值150分。
4．本试卷共8大题，除特别说明外，算法描述可用类PASCAL 、C 语言。
一、选择合适的数据结构表示两个集合:
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 个备选点。假设选定n i 为供应站，则该供应站到其余各顶点 1