武汉科技大学_计算机软件技术基础2006考研真题

发布于:2021-07-30 20:28:55

武汉科技大学 2006年硕士研究生入学考试试题 考试科目及代码:数据结构 421 说 明:1.适用招生专业:计算机应用技术 2.答题内容写在答题纸上,写在试卷或草稿纸上一律无效。 3.考试时间3小时,总分值150分。 共2页 第1页 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分) 1 四、设有n阶三对角矩阵A[0..n-1, 0..n1],将三条对角线上的元素逐行存放于数组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 课程名称 程序设计基础 离散数学 2 先决条件 无 C1 C3 C4 C5 数据结构 汇编语言 操作系统 C1,C2 C1 C3 假设每门课程的学*时间为一学期,试为该专业的学生设*萄Ъ苹 使他们能在最短的时间内修完这些课程。设计算法求出每个学期的课程 安排。(画出该问题的逻辑结构图4分,定义数据结构4分,描述算法思路 6分,算法8分,共22分) 八、有以下参赛选手比赛项目表: 姓名 丁一 马二 张三 李四 王五 项目1 跳高 标枪 标枪 铅球 跳远 项目2 跳远 铅球 100米 200米 200米 项目3 100米 200米 跳高 需要作一个竞赛日程安排,使得在尽可能短的时间内安排完比赛。为了 较好解决这个问题,首先表述安排竞赛项目的数据结构模型,然后设计 算法求出到底需要几个单位时间。(画出该问题的逻辑结构图6分,定义 数据结构4分,描述算法思路6分,算法8分,共24分) 试 题 完 3

相关推荐

最新更新

猜你喜欢