一个班有M个女生,有N人男生(M不等于N),现要开一个舞会,男女生分别编号坐在舞池边的椅子上。每曲开始时,依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲舞伴。
请设计一系统模拟动态地显示出上述过程,要求如下: (1) 输出每曲配对情况。
(2) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的
情况。至少求出K的两个值。
19. **电话簿的存储与查找(树形结构分类,树的横向凹入)
设计电话簿存储结构,要求按类似以下树形结构分类,并将该棵树保存在文本文件中。实现查找、插入和删除元素操作,分析各算法效率。
全部
同学
中学同学 大学同学 研究生同学
同事
计算机系 通信系
20. **Huffman编码 1) 问题描述
设某编码系统共有n个字符,使用频率分别为{w1, w2, ?, wn},设计一个不等长的编码方案,使得该编码系统的空间效率最好。
2) 基本要求 (1) 设计数据结构; (2) 设计编码算法;
(3) 分析时间复杂度和空间复杂度。 3) 设计思想
利用Huffman编码树求得最佳的编码方案。
根据哈夫曼算法,建立哈夫曼树时,可以将哈夫曼树定义为一个结构型的一维数组HuffTree,保存哈夫曼树中各结点的信息,每个结点包括:权值、左孩子、右孩子、双亲,如图所示。由于哈夫曼树中共有2n-1个结点,并且进行n-1次合并操作,所以该数组的长
度为2n-1。
21. **各种排序算法时间性能的比较 1) 问题描述
对各种排序方法(直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序)的时间性能进行比较。
2) 基本要求
(1) 设计并实现上述各种排序算法;
(2) 产生正序和逆序的初始排列分别调用上述排序算法,并比较时间性能; (3) 产生随机的初始排列分别调用上述排序算法,并比较时间性能。 22. **哈希表设计 1)问题描述
针对某个集体中人名设计一个哈希表,使得平均查找长度不超过R,并完成相应的建表和查表程序。
2)基本要求
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。 3)测试数据
取周围较熟悉的30个人名。 23. 统计成绩 1)问题描述
给出n个学生的m门考试的成绩表,每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计,并打印统计表。 2)基本要求
(1) 按总数高低次序,打印出名次表,分数相同的为同一名次; (2) 按名次打印出每个学生的学号、姓名、总分以及各科成绩。 3)测试数据
由学生依据软件工程的测试技术自己确定。注意测试边界数据。
weight lchild rchild parent 图 哈夫曼树的结点结构
24. **学分管理程序 1) 问题描述
请设计一个学生的学分管理程序。
假设每位学生必须完成基础课50学分、专业课50学分、选修课24学分、人文类课程8学分、实验性课程20学分才能够毕业。因此在管理学分时,要考虑每个学分所属于的课程类别。学分信息应该包括学号、姓名、课程类别、学分等。
2) 基本要求
该程序应该具有下列功能:
(1) 通过键盘输入某位学生的学分;
(2) 给定学号,显示某位学生的学分完成情况;
(3) 给定某个班级的班号,显示该班所有学生学分完成情况; (4) 给定某位学生的学号,修改该学生的学分信息; (5) 按照某类课程的学分高低进行排序; (6) 提供一些统计各类信息的功能。 25. **销售管理系统 1)问题描述
某公司有四个销售员(编号:1-4),负责销售五种产品(编号:1-5)。每个销售员都将当天出售的每种产品各写一张便条交上来。每张便条包含内容:
1)销售员的代号 2)产品的代号
3)这种产品的当天的销售额
每位销售员每天可能上缴0-5张便条。假设,收集到了上个月的所有便条,编写一个处理系统,读取上个月的销售情况(自己设定),进行如下处理。
2) 基本要求
1)计算上个月每个人每种产品的销售额。
2)按销售额对销售员进行排序,输出排序结果(销售员代号)
3)统计每种产品的总销售额,对这些产品按从高到底的顺序,输出排序结果(需输出产品的代号和销售额)
26. **宿舍管理软件 1)问题描述
设某宿舍有:101,102,201,202四个房间,每个房间有4个床位,学生信息包括学号、姓名、房间号,为学生宿舍管理人员编写一个宿舍管理软件。
2) 基本要求
该程序应该具有下列功能: (1) 学生的入住处理; (2) 学生退房处理;
(3) 输出学生入住信息(按房间号和床号有序); (4) 修改入住信息;
(5) 学生调换宿舍或床位处理; (6) 按给定学号、姓名、房号查询; (7) 查询房间使用情况。 27. **库存管理系统 1)问题描述
试设计一库存管理系统,产品信息包括产品编号、名称、价格、数量等(产品编号不重复)。
2) 基本要求
该系统应具有以下功能:
(1)产品信息录入功能(产品信息用文件保存)--输入 (2)产品信息浏览功能 --输出 (3)产品入库 (4)产品出库 (5)查询和排序功能: (6)按价格从大到小排序 (7)按名称查询
(8) 产品信息删除、修改功能。 28. 迷宫问题 1)问题描述
迷宫求解是实验心理学中的一个经典问题,心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫,迷宫中设置很多隔壁,对前进方向形成了多处障碍,心理学家在迷宫的唯一出口处放置了一块奶酪,吸引老鼠在迷宫中寻找通路以到达出口。例如,图2所示为一个迷宫示意图,其中双边矩形表示迷宫,1代表有障碍,0代表无障碍。
0 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 1 1 1 1 1 入口(1, 1) 1 1 0 1 1 1 0 1 1 1 1 2 1 1 0 1 0 1 1 1 1 1 3 1 0 1 0 0 0 0 0 1 1 4 1 0 1 1 1 0 1 1 1 1 5 1 1 0 0 1 1 0 0 0 1 6 1 0 1 1 0 0 1 1 0 1 出口(6, 8) 7 1 1 1 1 1 1 1 1 1 1 图2 迷宫示意图,其中1代表有障碍,0代表无障碍
前进的方向有八个,分别是上、下、左、右、左上、左下、右上、右下
2) 基本要求
(1) 设计数据结构存储迷宫;
(2) 设计存储结构保存从入口到出口的通路; (3) 设计算法完成迷宫问题的求解; (4) 分析算法的时间复杂度。 3) 设计思想
可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的搜索方法。从入口出发,按某一方向向前探索,若能走通(未走过的),即某处可以到达,则到达新点,否则试探下一方向;若所有的方向均没有通路,则沿原路返回前一点,换下一个方向再继续试探,直到所有可能的通路都搜索到,或找到一条通路,或无路可走又返回到入口点。
在求解过程中,为了保证在任何位置上都能沿原路退回,需要一个后进先出的栈来保存从入口到当前位置的路径。
29. 最小生成树问题 1)问题描述
若要在n个城市之间建设通信网络,只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网,是一个网的最小生成树问题。
2) 基本要求
以邻接多重表存储无向带权图,利用克鲁斯卡尔算法或普瑞姆算法求网的最小生成树。 30. 带变量的表达式求值
设一个表达式中带有多个变量标识符,要求:① 识别出其中所有变量标识符;② 为所有变量标识符设置取值;③ 对于任意一组变量取值,求得表达式的运算结果值。
31. 压缩存储下三角矩阵
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读,免费范文网,提供经典小说综合文库数据结构课程设计任务书(2)在线全文阅读。
相关推荐: