发布时间 : 星期二 文章数据结构课程设计题目2015更新完毕开始阅读
③要对作业调度的结果给出清晰的输出信息，包括：何时作业进入，何时调度哪个作业，何时离开，每个作业等待多长时间，优先数的动态变化情况等。 ④
17. 哈夫曼编/译码器
问题描述
利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编译码系统。 基本要求
一个完整的系统应具有以下功能： （1）I：初始化（Initialization）。从终端读入字符集大小n及n个字符和m个权值，建立哈夫曼树，并将它存于文件hfmtree中。 （2）C：编码（Coding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree中读入），对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。 （3）D：解码（Decoding）。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。
（4）P：打印代码文件（Print）。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时，将此字符形式的编码文件写入文件codeprint中。 （5）T：打印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。
18. AVL树的实现及分析
基本要求 ① 编写AVL树判别程序，并判别一个二叉搜索树是否为AVL树。二叉搜索树用其先序遍
历结果表示，如：5，2，1，3，7，8。 ② 实现AVL树，其上的基本操作包括：Search，Insert，Delete，和Ascend； ③ 实现基本操作的动态演示(图形演示)。 ④ 扩展：
a.实现带索引的AVL搜索树，实现其上的基本操作：Search，Insert，Delete，
IndexSearch，IndexDelete和Ascend。前5种函数的时间复杂性应为O(logn)，最后一种函数的时间复杂性应为O(n)。
b. 搜索树中有一些元素的关键值相同。
19. 直方图问题
问题描述：
在直方图问题中，从一个具有n个关键值的集合开始，要求输出不同关键值的列表以及每个关键值在集合中出现的次数（频率）。下图给出了一个含有10个关键值的例子。图a给出了直方图的输入，直方图的表格形式如图b所示，直方图的图形形式如图c 所示。直方图一般用来确定数据的分布，例如，考试的分数、图象中的灰色比例、在生产商注册的汽车和居住
在洛杉矶的人所获得的最高学位都可以用直方图来表示。
基本要求：
分别使用三种结构（数组、链表散列、二叉搜索树），写出求解直方图问题的程序，通过图形显示运行时间的比较。
20. 箱子装载问题
问题描述：
在箱子装载问题中，有若干个容量为c的箱子和n个待装载入箱子中的物品。物品i需占s[i]个单元（0 至少给出求解箱子装载问题的三种方案，并进行性能比较。 21. B-树的实现及分析 基本要求 ① 实现在B-树上的查找，并分析其时间复杂性。 ② 实现B-树的ADT，包括其上的基本操作：结点的加入和删除。 ③ 要求B-树结构中的M=3或5，实现其中的一种即可。 ④ 实现基本操作的动态演示(图形演示)。 22. 图的实现与分析—1 问题描述 分别对有向图、无向图、带权有向图、带权无向图实现对图的基本操作（创建、求顶点的度数、增加/删除边、判断边是否存在、DFS、BFS、判断是否连通、连通构件的标识，求生成树等）。 基本要求 图使用邻接矩阵存储。 提供随机案例，对任意随机案例，实现DFS和BFS实现过程的动态演示(图形演示)。 对DFS提供递归与非递归两种方法的实现，并通过输出进行性能比较。 23. 图的实现与分析—2 问题描述 分别对有向图、无向图、带权有向图、带权无向图实现对图的基本操作（创建、求顶点的度数、增加/删除边、判断边是否存在、DFS、BFS、判断是否连通、连通构件的标识，求生成树等）。 基本要求 图使用邻接链表存储。 提供随机案例，对任意随机案例，实现DFS和BFS实现过程的动态演示(图形演示)。 对DFS提供递归与非递归两种方法的实现，并通过输出进行性能比较。 24. 校园导游 3、用无向网表示校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。 基本要求： ① 查询任意景点的相关信息； ② 查询图中任意两个景点间的最短路径。 ③ 查询图中任意两个景点间的所有路径。 ④ 增加、删除、更新有关景点和道路的信息。 （选作）* 求多个景点的最佳（最短）游览路径。 25. 全国交通咨询模拟 问题描述 处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能地短，出门旅游的旅客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编织一个全国城市间的交通资讯程序，为旅客提供两种或三种最优决策的交通咨询。 设计要求 （1）提供对城市信息进行编辑（如添加或删除）的功能。 （2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。 （3）提供两种最优决策：最快到达和最省钱到达。全程只考虑一种交通工具。 （4）旅途中耗费的总时间应该包括中转站的等候时间。 （5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具。输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或那一次班机到何地。 实现提示 （1）对全国城市交通图和列车时刻表及飞机航班表进行编辑，应该提供文件形式输入和键 盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需根据交通图给出各个路段的详细信息，例如：对从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至上海各段的出发时间、到达时间及票价等信息。 （2）以邻接表座交通图的存储结构，表示边的结构内除含有邻接点的信息外，还应包括交通工具、路程中耗费的时间和花费以及出发和到达的时间等多种属性。 （3）增加旅途中转次数最少的最优决策。 26. 公交线路上优化路径的查询 问题描述 最短路径问题是图论中的一个经典问题，其中的Dijkstra算法一直被认为是图论中的好算法，但有的时候需要适当的调整Dijkstra算法才能完成多种不同的优化路径的查询。 对于某城市的公交线路，乘坐公交的顾客希望在这样的线路上实现各种优化路径的查询。设该城市的公交线路的输入格式为： 线路编号：起始站名(该站坐标)；经过的站点1名(该站坐标)；经过的站点2名(该站坐标)；??；经过的站点n名(该站坐标)；终点站名(该站坐标)。该线路的乘坐价钱。该线路平均经过多少时间来一辆。车速。 例如：63：A(32,45)；B(76,45)；C(76,90)；??；N(100,100)。1元。5分钟。1/每分钟。 假定线路的乘坐价钱与乘坐站数无关，假定不考虑公交线路在路上的交通堵塞。 对这样的公交线路，需要在其上进行的优化路径查询包括：任何两个站点之间最便宜的路径；任何两个站点之间最省时间的路径等等。 基本要求 ① 根据上述公交线路的输入格式，定义并建立合适的图模型。 ② 针对上述公交线路，能查询获得任何两个站点之间最便宜的路径，即输入站名S，T后，可以输出从S到T的最便宜的路径，输出格式为：线路x：站名S，?，站名M1；换乘线路x：站名M1，?，站名M2；?；换乘线路x：站名MK，?，站名T。共花费x元。 ③ 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（不考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名S，?，站名M1；换乘线路x：站名M1，?，站名M2；?；换乘线路x：站名MK，?，站名T。共花费x时间。 ④ 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（要考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名S，?，站名M1；换乘线路x：站名M1，?，站名M2；?；换乘线路x：站名MK，?，站名T。共花费x时间。 (4) 实现提示 需深入考虑，应根据不同的应用目标，即不同的优化查询来建立合适的图模型。 27. 多叉路口交通灯的管理问题 通常，在十字交叉路口只需设红、绿两色的交通灯便可保持正常的交通秩序，而在多叉路口需设几种颜色的交通灯才能既使车辆相互之间不碰撞，又能达到车辆的最大流通。假设有一个如图(a)所示的五叉路口，其中C和E为单行道。在路口有13条可行的通路，其中有的可以同时通行，如A→B和E→C，而有的不能同时通行，如E→B和A→D。那么，在路口应如何设置交通灯进行车辆的管理呢？