发布时间 : 星期二 文章数据结构课程设计题目2015更新完毕开始阅读
28. 文档集合上的查询
(1) 问题描述
设计数据结构完成在一个文档集合的存储，并构造算法实现其内容的查询。该设计包括三个部分：
(一)应用数据结构完成文档集合的内容(基于单词的)存储，并为下一步的查询建立
索引。
(二)就单个单词的查询请求，设计算法进行查询。
(三)对多个单词通过AND和OR构造的复杂查询进行处理(此处可只做两个单词的情
况)。
具体情形如下面的例子：
Example
Doc1: I like the class on data structures and algorithms. Doc2: I hate the class on data structures and algorithms.
Doc3: Interesting statistical data may result from this survey. Here are the answers to some queries:
Query 1: data
Doc1, Doc2, Doc3
Query2: data AND structures
Doc1, Doc2
Query 3: like OR survey
Doc1, Doc3
文档集合上的查询实例
基本要求
① 文档集合中的文档数不能少于20个。
② 数据结构的设计以及查找算法的构造应考虑如何最大程度的提高查询效率。 ③ 查询效率的提高应是综合多种查询的，而不是只针对一种查询的优化。 ④ 给出查询效率的模拟实验数据。
实现提示
AND和OR查询可转变为单个单词查询结果的组合。
29. 教学计划编制问题
问题描述
大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。 基本要求
（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。
（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是是课程尽可能地集中在前几个学期中。
（3）若根据给定的条件问题无解，则报告适当的信息；否则，将教学计划输出到用户指定的文件中。计划的表格格式自行设计。
30. 最小生成树—Prim算法
设计实现无向网结构，针对随机无向网实例和随机起点，用PRIM算法的基本思想求解出所有的最小生成树，并给出求解过程的动态图形演示。 可考虑实现不同存储结构上的实现。
31. 最小生成树—Kruskal算法
设计实现无向网结构，针对随机无向网实例和随机起点，用Kruskal算法的基本思想求解出所有的最小生成树，并给出求解过程的动态图形演示。 可考虑实现不同存储结构上的实现。
32. 最短路径—Dijkstra算法
设计实现有向网结构，针对随机有向网实例和随机源点，用Dijkstra算法求解出单源点到其他各顶点的最短路径，给出求解过程的动态演示。 可考虑实现不同存储结构上的实现。
33. 拓扑排序
对给定的AOV网，产生所有的拓扑序列，给出求解过程的动态演示。
34. 成绩分析问题
问题描述
录入、保存一个班级学生多门课程的成绩，并对成绩进行分析。 基本要求
（1）通过键盘输入个学生的多门课程的成绩，建立相应的文件input.dat。 （2）对文件input.dat中的数据进行处理，要求具有以下功能： 1）按各门课程成绩排序，并生成相应的文件输出。
2）计算每人的平均成绩，按平均成绩排序，并生成文件。
3）求出各门课程的平均成绩、最高分、最低分、不及格人数、60~69分人数、70~79分人数、80~89分人数、90分以上人数。
4）根据姓名或学号查询某人的各门课成绩，重名情况也能处理 （3）界面美观
35. 检查网络
给定一个计算机网络以及机器间的双向连线列表，每一条连线与允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。 要求实现功能：
任意指定两台计算机，判断它们之间是否可以进行文件传输？
判断整个网络中是否任意两台机器间都可以文件传输？若不可以，请给出当前网络中连通分量的个数及各个连通分量中的机器。 增加两台计算机之间的连线。 基本要求：
至少使用两种结构实现。
36. 调度问题
（1）机器调度
现有n件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为si，完成时间为fi， si < fi 。[si, fi]为处理任务i的时间范围。两个任务i，j重叠是指两个任务的时间范围区间有重叠，而并非是指i，j的起点或终点重合。每台机器在任何时刻最多只处理一个任务。最优分配是指使用的机器最少的可行分配方案。 要求：
输入任务个数及每个任务的名称，开始时间，完成时间 给出最优分配方案。 （2）任务调度
现在有n项作业，J1，J2，?Jn，要求按顺序执行，已知各作业对应的运行所需时间分别为t1，t2，?tn，要求这些作业在一个处理器上运行，并且要求完成这n个作业的平均完成时间最小。注：每个作业的完成时间等于作业的等待时间与它的执行时间的和，这里假设一旦开始运行一个作业，那么在该作业完成之前，其他作业都只能等待。 要求：
输入作业个数及每个作业的名称，执行时间 给出最优调度方案。
37. 学校超市选址问题（带权有向图的中心点）。
基本要求：对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。
38. 设计散列表实现电话号码查找系统。
基本要求：
（1）设每个记录有下列数据项：电话号码、用户名、地址；
（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表； （3）查找并显示给定电话号码的记录； （4）查找并显示给定用户名的记录。
（5）尝试不同类型处理冲突的方法，考察平均查找长度的变化。
39. 学生搭配问题。
一班有m个女生,有n个男生（m不等于n），现要开一个舞会。男女生分别编号坐在舞池的两边的椅子上。每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴。
请设计一系统模拟动态地显示出上述过程，要求如下： （1）输出每曲配对情况；
（2）计算出任何一个男生（编号为X）和任意女生（编号为Y），在第K曲配对跳舞的情况。至少求出K的两个值；
（3）尽量设计出多种算法及程序。 提示：用队列来解决比较方便。
40. 扫雷游戏
实现一个N*M的扫雷游戏。
41 马的遍历问题：
设计程序完成如下要求：在中国象棋盘上，对任意位置上放置一个马，均能选择一个合适的路线，使得该棋子能够按照象棋的规则不重复的走过棋盘上的每一位置。 要求：（1）依次输出走过的各位置的坐标
（2）最好能画出棋盘的图形形式，并在其上动态的标注行走过程 （3）程序能方便的移植到其他规格的棋盘上。
42．在 8×8的国际象棋棋盘上，如果放置若干个马后，使得整个棋盘的任意空位置上所
放置的棋子均能被这些马吃掉，则称这组放置为棋盘的一个满覆盖。若去掉满覆盖中的任意一个棋子都会使这组放置不再是满覆盖，则称这一满覆盖为极小满覆盖。设计程序完成如下要求：
（1）求解一个极小满覆盖
（2）最好能画出棋盘的图形形式，并在其上动态的演示试探过程 （3）程序能方便的移植到其他规格的棋盘上。
43．在中国象棋上实现上一课题的任务。