41. 扑克牌游戏八皇后问题软件工程进度规划随机整数排序 ( 希尔排序 ) 随机整数排序 ( 快速排序 ) 随机整数排序 ( 堆排序 ) 随机整数排序 ( 归并排序 )...

Size: px

Start display at page:

Download "41. 扑克牌游戏八皇后问题软件工程进度规划随机整数排序 ( 希尔排序 ) 随机整数排序 ( 快速排序 ) 随机整数排序 ( 堆排序 ) 随机整数排序 ( 归并排序 )..."

勉奄糜
5 years ago
Views:

1 数据结构课程设计题目 1. 运动会分数统计集合的并交和差运算一元稀疏多项式计算器活期储蓄帐目管理系统宿舍管理系统学生成绩管理系统约瑟夫生者死者游戏约瑟夫双向生死游戏停车场管理迷宫问题马踏棋盘图书管理系统航空客运订票系统车厢调度数制转换算术表达式求值及评判系统表达式求值 ( 后缀法 ) 文本文件单词的检索与计数串基本操作实现稀疏矩阵运算器长整数四则运算通讯录的制作二叉树有关操作实现求先序序列求后序序列哈夫曼编码译码系统先序线索二叉树的操作实现中序线索二叉树的操作实现图的遍历的实现教学计划编制问题图的邻接矩阵表示图的邻接表表示最小生成树图的最短路径关键路径问题动态查找表平衡二叉树哈表的设计与实现学生搭配问题身份证信息管理系统... 25

2 41. 扑克牌游戏八皇后问题软件工程进度规划随机整数排序 ( 希尔排序 ) 随机整数排序 ( 快速排序 ) 随机整数排序 ( 堆排序 ) 随机整数排序 ( 归并排序 ) 电视大赛观众投票及排名系统多关键字排序运动会分数统计问题描述参加运动会的 n 个学院编号为 1~n 比赛分成 m 个男子项目和 w 个女子项目, 项目编号分别为 1~m 和 m+1~m+w 由于各项目参加人数差别较大, 有些项目取前五名, 得分顺序为 7,5,3,2,1; 还有些项目只取前三名, 得分顺序为 5,3,2 写一个统计程序产生各种成绩单和得分报表基本要求 1) 可以输入各个项目的前三名或前五名的成绩 ; 2) 能统计各学院总分, 3) 可以按学院编号或名称学院总分男女团体总分排序输出 ; 4) 可以按学院编号查询学院某个项目的情况 ; 可以按项目编号查询取得前三或前五名的学院 5) 数据存入文件并能随时查询 6) 规定 : 输入数据形式和范围 : 可以输入学院的名称, 运动项目的名称输出形式 : 有中文提示, 各学院分数为整型界面要求 : 有合理的提示, 每个功能可以设立菜单, 根据提示, 可以完成相关的功能要求存储结构 : 学生自己根据系统功能要求自己设计, 但是要求运动会的相关数据要存储在数据文件中测试数据

3 要求使用 1 全部合法数据;2 整体非法数据;3 局部非法数据进行程序测试, 以保证程序的稳定例如, 对于 n=4,m=3,w =2, 编号为奇数的项目取前五名, 编号为偶数的项目取前三名, 设计一组实例数据实现提示可以假设 n 20,m 30,w 20, 姓名长度不超过 20 个字符每个项目结束时, 将其编号类型符 ( 区分取前五名还是前三名 ) 输入, 并按名次顺序输入运动员姓名校名 ( 和成绩 ) 选作内容允许用户指定某项目采取其他名次取法 2. 集合的并交和差运算问题描述编制一个能演示执行集合的并交和差运算的程序基本要求 (1) 集合的元素限定为小写字母字符 [ a.. z ] (2) 演示程序以用户和计算机的对话方式执行测试数据 (1)Set1="magazine",Set2="paper", Set1 Set2="aegimnprz",Setl Set2="ae",Set1-Set2="gimnz" (2)Set1= " 012oper4a6tion89",Set2="error data", Set1 Set2="adeinoprt",Setl Set2="aeort",Set1-Set2="inp" 实现提示以有序链表表示集合选作内容 (1) 集合的元素判定和子集判定运算 (2) 求集合的补集 (3) 集合的混合运算表达式求值

4 (4) 集合的元素类型推广到其他类型, 甚至任意类型 3. 一元稀疏多项式计算器问题描述设计一个一元稀疏多项式简单计算器基本要求一元稀疏多项式简单计算器的基本功能是 : (1) 输入并建立多项式 ; (2) 输出多项式, 输出形式为整数序列 :n,c l,e l,c 2,e 2,,c n,e n, 其中 n 是多项式的项数,c i 和 e i, 分别是第 i 项的系数和指数, 序列按指数降序排列 ; (3) 多项式 a 和 b 相加, 建立多项式 a +b; (4) 多项式 a 和 b 相减, 建立多项式 a -b (5) 多项式 a 和 b 相乘, 建立乘积多项式 a*b 测试数据 (1)(2x+5x 8-3.1x 11 ) + (7-5x 8 +11x 9 )=(-3.lx x 9 +2x+7) (2)(6x -3 -x+4.4x 2-1.2x 9 ) -(-6x x 2 -x x 15 ) =(-7.8x x 9 +12x -3 -x) (3)(1 +x + x 2 +x 3 +x 4 +x 5 )+(-x 3 -x 4 )=(1+x+x 2 +x 5 ) (4)(x+x 3 )+(-x-x 3 )=0 (5)(x+x 100 )+(x 100 +x 200 )=(x+2x 100 +x 200 ) (6)(x+x 2 +x 3 )+0=x+x 2 +x 3 (7) 上述测试数据中的两个多项式的乘积实现提示用带表头结点的单链表存储多项式选作内容 (1) 计算多项式在 x 处的值 (2) 求多项式 a 的导函数 a

5 (3) 多项式的输出形式为类数学表达式例如, 多项式 -3x 8 +6x 3-18 的输出形式为 3x 8 6x 3 18,x 15 +(-8)x 7-14 的输出形式为 x 15 8x 7 14 注意, 数值为 1 的非零次项的输出形式中略去系数 1, 如项 1x 8 的输出形式为 x 8, 项 - 1x 3 的输出形式为 -x 3 (4) 计算器的仿真界面设计 4. 活期储蓄帐目管理系统问题描述编写一个活期储蓄帐目管理系统, 实现储户开户销户存入支出等活动其主要要求是能比较迅速地找到储户的帐户, 实现存款取款, 还要能比较简单迅速地实现插入和删除, 以实现开户和销户的需要基本要求 (1) 实现储户开户开户时需要填写登记卡, 记录储户信息 ( 包括姓名和帐号 ), 并设置开户余额为 0 (2) 实现储户销户需要先找到储户的帐户信息, 然后将其删除 (3) 向某帐户存款 (4) 从某帐户取款 (5) 排序显示所有帐户信息根据帐号对所有帐户信息排序 (6) 查询某帐户余额选作内容 (1) 查询某帐户交易记录 (2) 所有帐户及其交易信息存储至文件, 程序运行时从文件中读入 5. 宿舍管理系统问题描述要求为宿舍管理人员编写一套宿舍管理系统软件, 能够完成宿舍管理人员对宿舍住宿相关信息的管理与查询的功能, 如可以添加删除和修改住宿记录,

6 可以按照不同的关键字查询住宿情况为了查找方便, 可对所有住宿信息按姓名学号宿舍号分别进行排序要求住宿信息可以保存到文件中基本要求 (1) 添加学生住宿记录信息 (2) 编辑学生住宿记录 (3) 删除学生住宿记录 (4) 查询学生住宿信息 : 可以根据姓名学号宿舍号进行查找 (5) 排序 : 能够对所有住宿信息按姓名按学号按宿舍号进行排序选作内容读写文件 : 将所有住宿信息保存到文件中, 并且可以从文件中读出所有记录 6. 学生成绩管理系统问题描述学生成绩管理是学校教务部门日常工作的重要组成部分, 其处理信息量很大本项目是对学生成绩管理的简单模拟, 实质是完成对学生成绩信息的建立查找插入修改删除等功能基本要求 (1) 添加学生信息, 包括姓名学号三门以上的成绩总成绩等 (2) 编辑学生记录 (3) 删除学生记录 (4) 查询学生成绩 : 可以根据姓名学号进行查找 (5) 排序 : 能够按姓名按学号按不同科目按总成绩进行排序选作内容读写文件 : 将所有信息保存到文件中, 并且可以从文件中读出所有记录

7 7. 约瑟夫生者死者游戏问题描述约瑟夫生者死者游戏的大意是 :30 个旅客同乘一条船, 因为严重超载, 加上风高浪大, 危险万分 ; 因此船长告诉乘客, 只有将全船一半的旅客投入海中, 其余人才能幸免遇难无奈, 大家只得同意这种办法, 并议定 30 个人围成一圈, 由第一个人开始, 依次报数, 数到第 9 人, 便把他投入大海中, 然后从他的下一个人数起, 数到第 9 人, 再将他投入大海, 如此循环, 直到剩下 15 个乘客为止问哪些位置是将被扔下大海的位置实现提示可以采用单向循环链表作为存储结构假设 n 个旅客排成一个环形, 依次顺序编号 1,2,,n 从某个指定的第 1 号开始, 沿环计数, 每数到第 m 个人就让其出列, 且从下一个人开始重新计数, 继续进行下去这个过程一直进行到剩下 2/n 个旅客为止基本要求 (1) 输入 : 旅客的个数, 也就是 n 的值 ; 离开旅客的间隔数, 也就是 m 的值 ; (2) 输出 : a. 离开旅客的序号 ; b. 剩余旅客的序号 ; 8. 约瑟夫双向生死游戏问题描述约瑟夫双向生死游戏是在约瑟夫生者死者游戏的基础上, 正向计数后反向计数, 然后再正向计数具体描述如下 :30 个旅客同乘一条船, 因为严重超载, 加上风高浪大, 危险万分 ; 因此船长告诉乘客, 只有将全船一半的旅客投入海中, 其余人才能幸免遇难无奈, 大家只得同意这种办法, 并议定 30 个人围成一圈, 由第一个人开始, 顺时针依次报数, 数到第 9 人, 便把他投入大海中, 然后从他

8 的下一个人数起, 逆时针数到第 5 人, 将他投入大海, 然后从他逆时针的下一个人数起, 顺时针数到第 9 人, 再将他投入大海, 如此循环, 直到剩下 15 个乘客为止问哪些位置是将被扔下大海的位置基本要求本游戏的要求用户输入的内容包括 : (1) 旅客的个数, 也就是 n 的值 ; (2) 正向离开旅客的间隔数, 也就是 m 的值 ; (3) 反向离开旅客的间隔数, 也就是 k 的值 ; 本游戏要求输出的内容是包括 : (1) 离开旅客的序号 ; (2) 剩余旅客的序号 ; 实现提示用双向循环链表解决这一问题 9. 停车场管理问题描述设停车场内只有一个可停放 n 辆汽车的狭长通道, 且只有一个大门可供汽车进出汽车在停车场内按车辆到达时间的先后顺序, 依次由北向南排列 ( 大门在最南端, 最先到达的第一辆车停放在车场的最北端 ), 若车场内已停满 n 辆汽车, 则后来的汽车只能在门外的便道上等候, 一旦有车开走, 则排在便道上的第一辆车即可开入 ; 当停车场内某辆车要离开时, 在它之后开入的车辆必须先退出车场为它让路, 待该辆车开出大门外, 其它车辆再按原次序进入车场, 每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用试为停车场编制按上述要求进行管理的模拟程序基本要求以栈模拟停车场, 以队列模拟车场外的便道, 按照从终端读入的输入数据序列进行模拟管理每一组输入数据包括三个数据项 : 汽车到达或离去信息汽车牌照号码及到达或离去的时刻, 对每一组输入数据进行操作后的输出数据为 : 若是车辆到达, 则输出汽车在停车场内或便道上的停车位置 ; 若是车离去 ;

9 则输出汽车在停车场内停留的时间和应交纳的费用 ( 在便道上停留的时间不收费 ) 栈以顺序结构实现, 队列以链表实现测试数据设 n=2, 输入数据为 :( A, 1,5),( A, 2,10),( D, 1,15),( A, 3, 20), ( A, 4,25),( A, 5,30),( D, 2,35),( D, 4,40), ( E, 0,0) 每一组输入数据包括三个数据项: 汽车到达或离去信息汽车牌照号码及到达或离去的时刻, 其中, A 表示到达 ; D 表示离去, E 表示输入结束实现提示需另设一个栈, 临时停放为给要离去的汽车让路而从停车场退出来的汽车, 也用顺序存储结构实现输入数据按到达或离去的时刻有序栈中每个元素表示一辆汽车, 包含两个数据项 : 汽车的牌照号码和进入停车场的时刻 10. 迷宫问题问题描述以一个 m*n 的长方阵表示迷宫,0 和 1 分别表示迷宫中的通路和障碍设计一个程序, 对任意设定的迷宫, 求出一条从入口到出口的通路, 或得出没有通路的结论基本要求 (1) 迷宫的大小可以定义 (2) 迷宫入口默认为左上角, 出口默认为右下角, 也可以自定义 (3) 给出迷宫的生成和求解过程测试数据迷宫的测试数据如下 : 左下角 (1,1) 为入口, 右下角 (8,9) 为出口实现提示计算机解迷宫通常用的是穷举求解方法, 即从入口出发, 顺着某个方向进行探索, 若能走通, 则继续往前进 ; 否则沿着原路退回, 换一个方向继续探索, 直至出口位置, 求得一条通路假如所有可能的通路都探索到而未能到达出口, 则所设的迷宫没有通路

10 可以二维数组存储迷宫数据, 通常设定入口点的下标为 (1,1), 出口点的下标为 (m,n) 为处理方便起见, 可在迷宫的四周加一圈障碍对于迷宫中任一位置, 均可约定有东南西北四个方向可通选做内容 (1) 编写递归形式的算法, 求得迷宫中所有可能的通路 ; (2) 以方阵形式输出迷宫及其通路 11. 马踏棋盘问题描述设计一个国际象棋的马踏遍棋盘的演示程序基本要求将马随机放在国际象棋的 8 8 棋盘 Board[8][8] 的某个方格中, 马按走棋规则进行移动要求每个方格只进入一次, 走遍棋盘上全部 64 个方格编制非递归程序, 求出马的行走路线, 并按求出的行走路线, 将数字 1,2,,64 依次填入一个 8 8 的方阵, 输出之 12. 图书管理系统问题描述图书管理基本业务活动包括 : 对一本书的采编入库清除库存借阅和归还等等试设计一个图书管理系统, 将上述业务活动借助于计算机系统完成基本要求 (1) 每种书的登记内容至少包括书号书名著作者现存量和总库存量等五项 (2) 对书号建立索引表 ( 线性表 ) 以提高查找效率 ; (3) 系统应实现的操作及其功能定义如下 : 1 采编入库 : 新购入一种书, 经分类和确定书号之后登记到图书账目中去如果这种书在账中已有, 则只将总库存量增加

11 2 清除库存 : 某种书已无保留价值, 将它从图书账目中注销 3 借阅 : 如果一种书的现存量大于零, 则借出一本, 登记借阅者的图书证号和归还期限 4 归还 : 注销对借阅者的登记, 改变该书的现存量 13. 航空客运订票系统问题描述航空客运订票的业务活动包括 : 查询航线客票预订和办理退票等试设计一个航空客运订票系统, 以使上述业务可以借助计算机来完成基本要求 (1) 每条航线所涉及的信息有 : 终点站名航班号飞机号飞行周日 ( 星期几 ) 乘员定额余票量已订票的客户名单( 包括姓名订票量舱位等级 1,2 或 3) 以及等候替补的客户名单 ( 包括姓名所需票量 ); (2) 系统能实现的操作和功能如下 : 1 录入 : 可以录入航班情况, 全部数据可以只放在内存中, 最好存储在文件中 ; 2 查询航线 : 根据旅客提出的终点站名输出下列信息 : 航班号飞机号星期几飞行, 最近一天航班的日期和余票额 ; 3 承办订票业务 : 根据客户提出的要求 ( 航班号订票数额 ) 查询该航班票额情况, 若尚有余票, 则为客户办理订票手续, 输出座位号 ; 若已满员或余票额少于订票额, 则需重新询问客户要求若需要, 可登记排队候补 ; 4 承办退票业务 : 根据客户提供的情况 ( 日期航班 ), 为客户办理退票手续, 然后查询该航班是否有人排队候补, 首先询问排在第一的客户, 若所退票额能满足他的要求, 则为他办理订票手续, 否则依次询问其他排队候补的客户测试数据由读者自行指定实现提示两个客户名单可分别由线性表和队列实现为查找方便, 已订票客户的线性表应按客户姓名有序, 并且, 为插入和删除方便, 应以链表作存储结构由于预

12 约人数无法预计, 队列也应以链表作存储结构整个系统需汇总各条航线的情况登录在一张线性表上, 由于航线基本不变, 可采用顺序存储结构, 并按航班有序或按终点站名有序每条航线是这张表上的一个记录, 包含上述 8 个域其中乘员名单域为指向乘员名单链表的头指针, 等候替补的客户名单域为分别指向队头和队尾的指针选作内容当客户订票要求不能满足时, 系统可向客户提供到达同一目的地的其他航线情况还可充分发挥自己的想象力, 增加你的系统的功能和其他服务项目 14. 车厢调度问题描述假设停在铁路调度站入口处的车厢序列的编号一次为 1,2,3,,n 设计一个程序, 求出所有可能由此输出的长度为 n 的车厢序列基本要求 (1) 分别给出 n=1,2,3,4,5 时的结果 (2) 探究一般情况下可能出车厢序列与 n 之间的关系 15. 数制转换问题描述实现十进制二进制, 八进制十六进制数之间的相互转换基本要求任意给定一个 M 进制的数 x, 请实现如下要求 (1) 求出此数 x 的 10 进制值 (2) 实现 x 向任意的一个非 M 进制的数的转换 (3) 至少用两种或两种以上的方法实现上述要求 ( 用栈解决, 用数组解决, 其它方法解决 )

13 16. 算术表达式求值及评判系统问题描述设计一个算术表达式的求值及评判系统, 可供小学生作业, 并能给出分数基本要求 (1) 建立试题库文件, 随机产生 n 个题目 (2) 题目涉及加减乘除带括号的混合运算 ; (3) 随时可以退出 ; (4) 保留历史分数, 能回顾历史, 给出与历史分数比较后的评价 17. 表达式求值 ( 后缀法 ) 问题描述设计一个算术表达式的求值系统, 可以将包括加减乘除四则运算和括号的中缀表达式先转换为后缀表达式, 再求值基本要求 (1) 从键盘输入要求解的算术表达式 ; (2) 采用栈结构进行算术表达式的求解过程 ; (3) 能够判断算术表达式正确与否 ; (4) 对于错误表达式给出提示 ; (5) 对于正确中缀表达式转换为后缀表达式, 给出最后的结果 18. 文本文件单词的检索与计数问题描述要求编程建立一个文本文件, 每个单词不包含空格且不跨行, 单词由字符序列构成且区分大小写 ; 统计给定单词在文本文件中出现的总次数 ; 检索输出某个单词出现在文本中的行号在该行中出现的次数以及位置该设计要求可分为三个部分实现 : 其一, 建立文本文件, 文件名由用户用键盘输入 ; 其二, 给定单词

14 的计数, 输入一个不含空格的单词, 统计输出该单词在文本中的出现次数 ; 其三, 检索给定单词, 输入一个单词, 检索并输出该单词所在的行号该行中出现的次数以及在该行中的相应位置基本要求 (1). 建立文本文件 (2) 给定单词的计数 (3) 检索单词出现在文本文件中的行号次数及其位置 (4) 主控菜单程序的结构建立文件单词定位单词计数退出程序 19. 串基本操作实现问题描述如果语言没有把串作为一个预先定义好的基本类型对待, 又需要用该语言写一个涉及串操作的软件系统时, 用户必须自己实现串类型试实现串类型的基本操作基本要求用定长顺序表示或者堆分配存储表示, 实现以下抽象数据类型串的基本操作 ( 不使用 C 语言本身提供的串函数 ) (1) 串赋值 (2) 判相等 (3) 联接 (4) 求长度 (5) 求子串 (6) 子串定位 (7) 串替换 (8) 插入子串 (9) 删除

15 20. 稀疏矩阵运算器问题描述稀疏矩阵是指那些多数元素为零的矩阵利用 " 稀疏 " 特点进行存储和计算可以大大节省存储空间, 提高计算效率实现一个能进行稀疏矩阵基本运算的运算器基本要求 (1) 实现一个矩阵的转置运算 (2) 实现两个矩阵相加的运算 (3) 实现两个矩阵相乘的运算稀疏矩阵的输入形式采用三元组表示, 而运算结果的矩阵则以通常的阵列形式列出实现提示 (1) 以三元组顺序表表示稀疏矩阵, 首先应输入矩阵的行数和列数, 并判别给出的两个矩阵的行列数对于所要求作的运算是否相匹配可设矩阵的行数和列数均不超过 20 (2) 程序可以对三元组的输入顺序加以限制, 例如, 按行优先注意研究教科书节中的算法, 以便提高计算效率 (3) 在用三元组表示稀疏矩阵时, 相加或相减所得结果矩阵应该另生成, 乘积矩阵也可用二维数组存放 21. 长整数四则运算问题描述设计一个实现任意长的整数进行加法运算的演示程序基本要求利用双向循环链表实现长整数的存储, 每个结点含一个整形变量任何整形变量的范围是 -(2^15-1)~ (2^15-1) 输入和输出形式: 按中国对于长整数

16 的表示习惯, 每四位一组, 组间用逗号隔开测试数据 (1)0;0; 应输出 0 (2)-2345,6789;-7654,3211; 应输出 -1,0000,0000 (3)-9999,9999;1,0000,0000,0000; 应输出 999 (4)1,0001,0001;-1,0001,0001; 应输出 0 (5)1,0001,0001;-1,0001,0000; 应输出 1 (6)-9999,9999,9999;-9999,9999,9999; 应输出 1,9999,9999,9998 (7)1,0000,9999,9999;1; 应输出 1,0001,0000,0000 实现提示 (1) 每个结点中可以存放的最大整数为 32767, 才能保证两数相加不会溢出, 但若这样存放, 即相当于按进制存放, 在十进制与进制数之间的转换十分不方便, 故可以在每个结点中仅存十进制的 4 位, 即不超过 9999 的非负整数, 整个链表表示为万进制 (2) 可以利用头结点数据域的符号代表长整数的符号用其绝对值表示元素结点数目相加过程中不要破坏两个操作数链表两操作数的头指针存于指针数组中是简化程序结构的一种方法不能给长整数位数规定上限 22. 通讯录的制作问题描述用数据结构中的双向链表作数据结构编写一个手机通讯录管理系统以把所学数据结构知识应用到实际软件开发中去基本要求本系统应完成一下几方面的功能 : 添加信息显示信息 : 它可以按按固定电话排列按手机联系人名字的拼音顺序排列查找 : 可以不同的关键字作为查找的依据, 进行查找 ; 编辑信息

17 删除信息保存到文件 : 将以上信息保存到文件, 以便下次运行程序时能载入此通信录设计要求每条信息至包含 : 姓名 (NAME ), 手机号, 固定电话号, 电子邮箱,QQ 号码, 城市 (CITY) 邮编 (EIP) 几项作为一个完整的系统, 应具有友好的界面和较强的容错能力上机能正常运行, 并写出课程设计报告 23. 二叉树有关操作实现问题描述建立一棵二叉树, 并对其进行各种操作 (1) 采用递归算法 ( 先序中序后序 ) 进行二叉树遍历 ; (2) 采用非递归算法 ( 先序中序后序层序 ) 进行二叉树遍历 (3) 求二叉数的树深统计叶子结点的个数 (4) 判断此二叉树是否为完全二叉树, 若是, 返回 1, 若不是, 返回 0 (5) 交换其左右子树, 并输出交换后进行各种遍历的结果基本要求从键盘接受输入 ( 先序 ), 以二叉链表作为存储结构, 建立二叉树 ( 以先序来建立 ), 并采用递归算法对其进行遍历 ( 先序中序后序 ), 将遍历结果打印输出测试数据 ABC##DE#G##F###( 其中 # 表示建立空指针 ) 则输出结果为先序序列 :ABCDEGF 中序序列 :CBEGDFA 后序序列 :CGBFDBA 24. 求先序序列问题描述给出一棵二叉树的中序与后序序列求出它的先序序列 ( 约定树结点用不

18 同的大写字母表示 ) 基本要求输入格式两行, 每行一个字符串, 分别表示中序和后序序列输出格式一个字符串, 表示所求先序序列样例输入 BADC BDCA 样例输出 ABCD 25. 求后序序列问题描述给出一棵二叉树的先序与中序序列求出它的后序序列 ( 约定树结点用不同的大写字母表示 ) 基本要求输入格式两行, 每行一个字符串, 分别表示先序和中序序列输出格式一个字符串, 表示所求后序序列样例输入 ABCD BADC 样例输出 BDCA

19 26. 哈夫曼编码译码系统问题描述利用哈夫曼编码进行通讯可以大大提高信道利用率, 缩短信息传输时间, 降低传输成本, 但是, 这要求在发送端通过一个编码系统对待传数据进行预先编码 ; 在接受端将传来的数据进行解码 ( 复原 ) 对于双工信道 ( 即可以双向传输的信道 ), 每端都要有一个完整的编 / 译码系统试为这样的信息收发站写一个哈夫曼的编译码系统基本要求 A: 从终端读入字符集大小为 n, 及 n 个字符和 n 个权值, 建立哈夫曼树, 进行编码并且输出, 将其存于文件 hfmtree 中 B: 利用已建好的哈夫曼编码文件 hfmtree, 对键盘输入的正文进行译码测试数据用下表中给出的字符集和频度的统计数据建立哈夫曼树 : 字 A B C D E F G H I J K L M N 符频度 2 3 字符 O P Q R S T U V W X Y Z 空格频度并实现以下报文的译码和输出 : THIS PROGRAM IS MY FAVORITE 27. 先序线索二叉树的操作实现问题描述建立一棵先序线索二叉树, 并对其进行各种操作基本要求实现先序线索树建立插入删除遍历等操作的实现

20 28. 中序线索二叉树的操作实现问题描述建立一棵中序线索二叉树, 并对其进行各种操作基本要求实现中序线索树建立插入删除遍历等操作的实现 29. 图的遍历的实现问题描述对给定的有向图或无向图, 实现深度优先遍历及广度优先遍历基本要求 (1) 先任意创建一个图 ; (2) 图的 DFS,BFS 的递归和非递归算法的实现 ; (3) 要求用有向图和无向图分别实现 ; (4) 可以用邻接矩阵或邻接表结构存储实现 ; 30. 教学计划编制问题问题描述大学的每个专业都要制定教学计划假设任何专业都有固定的学习年限, 年学年含两学期每学期的时间长度和学分上限值均相等每个专业开设的课程都是确定的, 而且课程在开设时间的安排必须满足先修关系每门课程有哪些先修课程是确定的, 可以有任意多门, 也可以没有每门课恰好占一个学期试在这样的前提下设计一个教学计划编制程序基本要求 (1) 输入参数包括 : 学期总数据, 一学期的学分上限, 每门课的课程号 ( 固定占 3 位的字母字符串 ) 学分和直接先修课的课程号 (2) 允许用户指定下列两种编排策略之一 : 一是使学生在各学期中的学习负

21 担尽量均匀 ; 二是课程尽可能地集中在前几个学期中 (3) 若根据给定的条件无解, 则报告适当的信息 ; 否则将教学计划输出到用户指定的文件中计划的表格格式自行设计测试数据学期总数 :6; 学分上限 :10; 该专业共开设 12 门课, 课程号从 C01 到 C12, 学分顺序为 2,3,4,3,2,3,4,4,7,5,2,3 先修关系见教科书图图的邻接矩阵表示问题描述开发一个用邻接矩阵构造的图的操作程序, 要求兼容有向图无向图有向网无向网基本要求要求程序至少具备以下操作接口 : (1) 图的创建函数 ; (2) 图的销毁函数 ; (3) 通过顶点序号获取顶点值的函数 ; (4) 顶点序号获取函数 ; (5) 修改顶点值的函数 ; (6) 增加弧的函数 ; (7) 删除弧的函数 ; (8) 求顶点的度的函数 ; (9) 输出图的信息的函数 32. 图的邻接表表示问题描述开发一个用邻接表构造的图的操作程序, 要求兼容有向图无向图有向网无向网

22 基本要求要求程序至少具备以下操作接口 : (1) 图的创建函数 ; (2) 图的销毁函数 ; (3) 通过顶点序号获取顶点值的函数 ; (4) 顶点序号获取函数 ; (5) 修改顶点值的函数 ; (6) 增加弧的函数 ; (7) 删除弧的函数 ; (8) 求顶点的度的函数 (9) 输出图的信息的函数 33. 最小生成树问题描述给定一个地区的 n 个城市间的距离网, 用 Prim 算法或 Kruskal 算法建立最小生成树, 并计算得到的最小生成树的代价基本要求 (1) 城市间的距离网采用邻接矩阵表示,( 要求至少 6 个城市,10 条边 ) 若两个城市之间不存在道路, 则将相应边的权值设为自己定义的无穷大值 (2) 最小生成树中包括的边及其权值, 并显示得到的最小生成树的代价 34. 图的最短路径问题描述要求给定一个地图, 求出指定地点到另一个地点的最短路径基本要求 (1) 根据数据建立图 ; (2) 能够保存图文件 ;

23 (3) 能够从保存过的文件中读取图文件 ; (4) 能够求解指定地点到另一个地点的最短路径 35. 关键路径问题问题描述设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动基本要求 (1) 对一个描述工程的 AOE 网, 应判断其是否能够顺利进行 (2) 若该工程能顺利进行, 输出完成整项工程至少需要多少时间, 以及每一个关键活动所依附的两个顶点最早发生时间最迟发生时间 36. 动态查找表问题描述利用二叉排序树完成动态查找表的建立指定关键字的查找插入与删除指定关键字结点任务要求算法输入 : 指定一组数据算法输出 : 显示二叉排序树的中序遍历结果查找成功与否的信息插入和删除后的中序遍历结果 ( 排序结果 ) 算法要点 : 二叉排序树建立方法动态查找方法, 对树进行中序遍历测试数据自行设定, 注意边界等特殊情况 37. 平衡二叉树问题描述从一棵空树开始创建, 在创建过程中, 保证树的有序性, 同时还要针对树的平衡性做些调整最终要把创建好的二叉排序树转换为二叉平衡排序树

24 基本要求 (1) 创建 ( 插入调整 ) (2) 中序遍历输出 38. 哈表的设计与实现问题描述设计哈表实现电话号码查找系统基本要求 (1) 设每个记录有下列数据项 : 电话号码用户名地址 ; (2) 从键盘输入各记录, 分别以电话号码和用户名为关键字建立哈希表 ; (3) 采用一定的方法解决冲突 ; (4) 查找并显示给定电话号码的记录 ; (5) 查找并显示给定用户名的记录选做内容 (1) 系统功能的完善 ; (2) 设计不同的哈希函数, 比较冲突率 ; (3) 在哈希函数确定的前提下, 尝试各种不同类型处理冲突的方法, 考察平均查找长度的变化 39. 学生搭配问题问题描述一班有 m 个女生, 有 n 个男生 (m 不等于 n), 现要开一个舞会男女生分别编号坐在舞池的两边的椅子上每曲开始时, 依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴基本要求请设计一系统模拟动态地显示出上述过程, 要求如下 : (1) 输出每曲配对情况 ;

25 (2) 计算出任何一个男生 ( 编号为 X) 和任意女生 ( 编号为 Y), 在第 K 曲配对跳舞的情况. 至少求出 K 的两个值 ; (3) 尽量设计出多种算法及程序提示 : 用队列来解决比较方便 40. 身份证信息管理系统问题描述建立一个身份证信息管理系统, 能够进行身份证信息的录入查找, 要求考虑查找效率基本要求 (1) 能够进行身份证号码及相关信息的录入, 相关信息包括姓名地址和手机号 ; (2) 能够快速进行身份证号码的查询, 并输出相关信息 ; (3) 可以修改身份证号码对应的其他信息, 如姓名地址 ; (4) 可以完成身份证信息的删除 41. 扑克牌游戏问题描述编号为 1-52 张牌, 正面向上, 从第 2 张开始, 以 2 为基数, 是 2 的倍数的牌翻一次, 直到最后一张牌 ; 然后, 从第 3 张开始, 以 3 为基数, 是 3 的倍数的牌翻一次, 直到最后一张牌 ; 然后从第 4 张开始, 以 4 为基数, 是 4 的倍数的牌翻一次, 直到最后一张牌 ;... 再依次 5 的倍数的牌翻一次,6 的,7 的直到以 52 为基数的翻过, 输出 : 这时正面向上的牌有哪些? 42. 八皇后问题问题描述八皇后问题是一个古老而著名的问题, 是回溯算法的典型例题该问题是十九世纪著名的数学家高斯 1850 年提出 : 在 8 8 格的国际象棋棋盘上, 安放八个

26 皇后, 要求没有一个皇后能够吃掉任何其他一个皇后, 即任意两个皇后都不能处于同一行同一列或同一条对角线上, 求解有多少种摆法 43. 软件工程进度规划问题描述设计一个软件, 需要进行用户需求分析系统需求确认系统概要设计设计用例场景系统的详细设计数据库详细设计编码单元测试集成测试系统测试维护等活动用户需求分析需要在系统需求确认之前完成, 系统的系统的详细设计必须在系统的概要设计设计系统用例和设计用例场景之前完成如表所示, 是一系列活动之间的关系表系统活动之间的关系活动代码活动名称先需活动 A1 用户需求分析无 A2 系统需求确认 A1 A3 系统概要设计 A2 A4 设计用例场景无 A5 系统的详细设计 A3, A4 A6 数据库详细设计 A3 A7 编码 A5, A6 A8 单元测试 A7 A9 集成测试 A8 A10 系统测试 A7 A11 维护 A11 图所示是设计一个软件的 AOV 网示意图

27 请设计算法判断该软件设计流程是否有回路, 若无请给出该软件设计 AOV 网的拓扑序列 44. 随机整数排序 ( 希尔排序 ) 问题描述利用随机函数产生个以上随机整数, 并对这些整数进行多种方法进行排序, 并显示排序结果, 比较各种算法的效率基本要求 (1) 为了提高效率, 所产生的随机整数用文件保存, 供各排序算法共用 ; (2) 至少采用 3 种以上方法实现排序 ( 其中之一必须为希尔排序 ), 并分别保存排序结果 ; (3) 记录每种排序所耗费的时间 ; 并把排序后的结果保存在不同的文件中 (4) 比较各排序算法的效率, 得出效率最高者, 分析该算法效率高的原因 (5) 输出的形式 : 递增的数列 ( 提示, 可采用的方法有插入排序希尔排序起泡排序快速排序选择排序堆排序归并排序 ) 45. 随机整数排序 ( 快速排序 ) 问题描述利用随机函数产生个以上随机整数, 并对这些整数进行多种方法进行排序, 并显示排序结果, 比较各种算法的效率

28 基本要求 (1) 为了提高效率, 所产生的随机整数用文件保存, 供各排序算法共用 ; (2) 至少采用 3 种以上方法实现排序 ( 其中之一必须为快速排序 ), 并分别保存排序结果 ; (3) 记录每种排序所耗费的时间 ; 并把排序后的结果保存在不同的文件中 (4) 比较各排序算法的效率, 得出效率最高者, 分析该算法效率高的原因 (5) 输出的形式 : 递增的数列 ( 提示, 可采用的方法有插入排序希尔排序起泡排序快速排序选择排序堆排序归并排序 ) 46. 随机整数排序 ( 堆排序 ) 问题描述利用随机函数产生个以上随机整数, 并对这些整数进行多种方法进行排序, 并显示排序结果, 比较各种算法的效率基本要求 (1) 为了提高效率, 所产生的随机整数用文件保存, 供各排序算法共用 ; (2) 至少采用 3 种以上方法实现排序 ( 其中之一必须为堆排序 ), 并分别保存排序结果 ; (3) 记录每种排序所耗费的时间 ; 并把排序后的结果保存在不同的文件中 (4) 比较各排序算法的效率, 得出效率最高者, 分析该算法效率高的原因 (5) 输出的形式 : 递增的数列 ( 提示, 可采用的方法有插入排序希尔排序起泡排序快速排序选择排序堆排序归并排序 ) 47. 随机整数排序 ( 归并排序 ) 问题描述利用随机函数产生个以上随机整数, 并对这些整数进行多种方法进行排序, 并显示排序结果, 比较各种算法的效率

29 基本要求 (1) 为了提高效率, 所产生的随机整数用文件保存, 供各排序算法共用 ; (2) 至少采用 3 种以上方法实现排序 ( 其中之一必须为归并排序 ), 并分别保存排序结果 ; (3) 记录每种排序所耗费的时间 ; 并把排序后的结果保存在不同的文件中 (4) 比较各排序算法的效率, 得出效率最高者, 分析该算法效率高的原因 (5) 输出的形式 : 递增的数列 ( 提示, 可采用的方法有插入排序希尔排序起泡排序快速排序选择排序堆排序归并排序 ) 48. 电视大赛观众投票及排名系统问题描述在很多的电视大赛中, 通常当选手表演结束后, 现场观众通过手中的按键对参赛选手进行投票, 然后对选手获得的票数进行统计, 从高到低进行降序排序, 从而自动产生冠军亚军和季军现在要求编写一程序模拟实现上述系统的功能实现提示在本例中, 首先输入参赛选手的人数 ( 范围为 1-9 个 ), 然后根据人数通过 malloc 函数来开辟存放选手信息的顺序表将选手的编号和姓名依此存入顺序表单元中, 观众通过按键进行投票, 按 1 为 1 号选手投票, 按 2 为 2 号选手投票, 以此类推, 以按 0 作为投票结束标志投票结束后进行排序, 在此采用希尔排序, 然后为每个选手计算名次, 得票相同的名次也相同, 参赛选手信息存储类型的定义 : typedef struct node{ char name[8]; /* 选手姓名 */ int num; /* 选手编号 */ int score; /* 选手得分 */ int tax; /* 选手名次 */ }Node;

30 49. 多关键字排序问题描述多关键字的排序有其一定的实用范围例如 : 在进行高考分数处理时, 除了需对总分进行排序外, 不同的专业对单科分数的要求不同, 因此尚需在总分相同的情况下, 按用户提出的单科分数的次序要求排出考生录取的次序基本要求 (1) 假设待排序的记录数不超过 10000, 表中记录的关键字数不超过 5, 各个关键字的范围均为 0 至 100 按用户给定的进行排序的关键字的优先关系, 输出排序结果 (2) 约定按 LSD 法进行多关键字的排序在对各个关键字进行排序时采用两种策略 : 其一是利用稳定的内部排序法, 其二是利用 " 分配 " 和 " 收集 " 的方法并综合比较这两种策略测试数据由随机数产生器生成实现提示用 5 至 8 组数据比较不同排序策略所需时间由于是按 LSD 方法进行排序, 则对每个关键字均可进行整个序列的排序, 但在利用通常的内部排序方法进行排序时, 必须选用稳定的排序方法借助 " 分配 " 和 " 收集 " 策略进行的排序, 如同一趟 " 基数排序 ", 由于关键字的取值范围为 0 至 100, 则分配时将得到 104 个链表选作内容增添按 MSD 策略进行排序, 并和上述两种排序策略进行综合比较

<4D F736F F D B8BDBCFE4220D7A8D2B5BBF9B4A1D3EBBACBD0C4BFCEB3CCC3E8CAF62E646F6378>

<4D F736F F D B8BDBCFE4220D7A8D2B5BBF9B4A1D3EBBACBD0C4BFCEB3CCC3E8CAF62E646F6378> B212CC: 数据结构与算法课程描述 0 课程基本信息课程编号 : B212CC 课程名称 : 数据结构与算法英文名称 : Data Structures and Algorithms 英文简称 : DSA 预备课程 : 计算系统基础离散数学授课时间 : 二年级第一学期时间分配 : 课堂教学 (48 课时 )+ 实验安排 (48 课时 )+ 课后作业与阅读 (48 课时 ) 学分数 : 3

41. 扑克牌游戏 八皇后问题 软件工程进度规划 随机整数排序 ( 希尔排序 ) 随机整数排序 ( 快速排序 ) 随机整数排序 ( 堆排序 ) 随机整数排序 ( 归并排序 )...

41. 扑克牌游戏八皇后问题软件工程进度规划随机整数排序 ( 希尔排序 ) 随机整数排序 ( 快速排序 ) 随机整数排序 ( 堆排序 ) 随机整数排序 ( 归并排序 )...