数据结构与OOP课程设计题目.doc

一、单项分值：20分1、约瑟夫环游戏（本题10分）2、八皇后问题(图形表示加20分)3、表达式的求值问题4、迷宫问题(图形表示加10分)二、单项分值：50分5、HTML文档标记匹配算法【基本要求】输入一段HTML代码，判断该代码是否符合HTML的语法【提示】HTML文档由不同的标记划分为不同的部分与层次。与括号类似，这些标记需要成对出现，对于名为的起始标记，相应的结束标记为。常用的HTML标记：l :HTML文档l :文档标题l :文档体l :节的头部l :居中对齐l :左对齐l :段落l 。HTML语言有合理的嵌套，如 6、程序源代码的相似性【问题描述】对于两个C+语言的源程序代码，用哈希表的方法分别统计两个程序中使用C+语言关键字的情况，并最终按定量的计算结果，得出两份程序的相似性。 【基本要求】建立C+语言关键字的哈希表，统计在每个源程序中C+关键字出现的频度, 得到两个向量X1和X2，通过计算向量X1和X2的相对距离来判断两个源程序的相似性。例如: 关键字 Void Int For Char if else while do break class程序1关键字频度 4 3 0 4 3 0 7 0 0 2程序2关键字频度 4 2 0 5 4 0 5 2 0 1 X1=4,3,0,4,3,0,7,0,0,2X2=4,2,0,5,4,0,5,2,0,1 设s是向量X1和X2的相对距离，s=sqrt( (xi1-xi2) 2 )，当X1=X2时，s=0, 反映出可能是同一个程序；s值越大，则两个程序的差别可能也越大。【测试数据】选择若干组编译和运行都无误的C+程序，程序之间有相近的和差别大的，用上述方法求s, 对比两个程序的相似性。 【提高要求】建立源代码用户标识符表，比较两个源代码用户标识符出现的频度，综合关键字频度和用户标识符频度判断两个程序的相似性。三、单项分值：60分 （含O(nlogn)排序算法及折半、索引查找算法的，各加10分，含基数排序及动态表的，各加20分）7、飞机订票系统【问题描述】通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）； 可以输入起飞抵达城市，查询飞机航班情况；订票：订票情况可以存在一个数据文件中，结构自己设定，可以订票，如果该航班已经无票，可以提供相关可选择航班； 退票： 可退票，退票后修改相关数据文件； 客户资料：有姓名，证件号，订票数量及航班情况，订单要有编号； 修改航班信息：当航班信息改变可以修改航班数据文件；【基本要求】根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；8、图书管理系统【问题描述】设计一个计算机管理系统完成图书管理基本业务。【基本要求】1)每种书的登记内容包括书号、书名、著作者、现存量和库存量；2)对书号建立索引表（线性表）以提高查找效率；3)系统主要功能如下：*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加； *借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量； *归还：注销对借阅者的登记，改变该书的现存量。【进一步完成内容】1)系统功能的进一步完善；2)索引表采用树表。3)设计内容4)程序流程图5)源程序6)软件测试报告（包括所用到的数据及结果）9、小型英汉词典【问题描述】设计一个英汉词典，支持Member(查找)、Insert(插入)、Delete(删除)操作。【基本要求】实现字典的常用方法有：有序线性表（Memeber用二分检索实现）、AVL树（二叉搜索树）、Patricia Trie、散列表等，任选一种方法实现字典的操作，查找单词、插入单词（插入时，先查找，找不到插入，找到提示用户）、删除单词（删除时，先查找，找到删除，找不到提示用户）。【测试数据】任一英文单词。【提高要求】选用两种以上的方法实现字典的操作，并比较不同实现算法的时间复杂度和空间复杂度。【提示】字典可以自己建立，但必须按字母az建立26个文件，建议从网上下载，文件类型为txt。四、单项分值：80分 （图形显示加20分）10、校园导航问题【问题描述】以我校为例，设计一个校园导游程序，主要为来访的客人提供信息查询。【基本要求】提供至少5个景点的校园导游咨询（包括景点介绍、景点间距离等）。本程序的目的是为来客提供路径咨询和景点查询（根据用户指定的始点和终点输出相应最短简单路径或者输出用户指定景点的详细信息）；系统管理员又可根据实际情况对导游图进行修改，删除路径或景点。选取九个大家熟悉的景点，抽象成一张带权无向图（如图所示）。以图中顶点表示景点，存放景点名称、代号等信息；以边表示路径，边上的权值表示两地的距离，为此图选择适当的数据结构：154239876500m200m200m100m200m50m100m500m700m100m100m本演示程序采用C语言编写，完成了无向图的建立和其他操作： 输入的形式和输入值的范围：主函数中调用图表建立函数之后，通过输入1到6不同的阿拉伯数字进行功能选择；在查找景点详细信息操作时需要输入景点的的序号；在求路径函数中，也是输入对应景点序号值；在删除路线函数里，输入构成边的两个景点的序号对；。在所有输入操作中，输入的值都是整数 输出的形式：菜单函数，输出功能菜单目录；查找函数信息操作，输出景点序号，名称，还有详细介绍；求最短路径函数，输出路线经过的顶点和路线的长度！删除函数，当删除成功后会输出删除成功；求删除操作后显示删除的元素的值。 程序所能达到的功能：完成无向带权图的生成（通过建立顶点数组和邻接矩阵）、通过选择菜单进行不同操作，查看景点信息、求景点间最短路径、删除景点或路线。 测试数据：A 查看景点详细信息操作中输入3B 查询最短路径操作中输入3，5C 删除操作中先后输入1（删除景点），2）（删除边）D 删除景点操作中输入1E 删除边操作中输入1,5F 查看一个景点到其他景点所有路线输入1 11、并查集：检查网络【问题描述】给定一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。请写出程序判断：任意指定两台计算机，它们之间是否可以进行文件传输？【输入要求】输入若干测试数据组成。对于每一组测试，第1行包含一个整数N（10000），即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。接下来的几行输入格式为I C1 C2或者 C或者C C1C2或者S，其中C1和C2是两台计算机的序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。当N为0时，表示全部测试结束，不要对该数据做任何处理。【输出要求】对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。当读到S时，检查整个网络。若网络中任意两机器间都可以传输文件，则在一行中输出“The network is connected.”，否则输出“There are k components.”,其中k是网络中连通集的个数。两组测试数据之间请输出一空行分隔。12、哈夫曼编码/译码器【问题描述】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。【基本要求】1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2)分别采用动态和静态存储结构3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；4)编码：利用建好的哈夫曼树生成哈夫曼编码；5)输出编码；6)设字符集及频度如下表：字符 空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 【进一步完成内容】1)译码功能；2)显示哈夫曼树；3)界面设计的优化。13、全国交通咨询模拟【问题描述】处于对不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则希望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。【基本要求】（1）提供对城市信息进行编辑（如：添加或删除）的功能。（2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。（3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。（4）旅途中耗费的总时间应该包括中转站的等候时间。（5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。【测试数据】【实现提示】（1）对全国城市交通图和班车时刻表及飞机航班表的编辑，应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需根据交通图给出各个路段的详细信息，例如：对于从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至各段的出发时间、到达时间和票价信息。（2）以邻接表作交通图的存储结构，表示边的结点内除含有邻接点的信息外，包括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。五、单项分值：100分14、LZW压缩器/解压器【问题描述】为了节省存储空间，常常需要把文本文件采用压缩编码的方式储存。例如：一个包含1000个x的字符串和2000个y的字符串的文本文件在不压缩时占用的空间为3002字节（每个x或每个y占用一个字节，两个字节用来表示串的结尾）。同样是这个文件，采用游程长度编码（run-length coding），可以存储为字符串1000x2000y，仅为10个字母，占用12个字节。若采用二进制表示游程长度（1000和2000）可以进一步节约空间。如果每个游程长度占用2个字节，则可以表示的最大游程长度为2*pow(16)，这样，上例中的字符串只需要用8个字节来存储。当要读取编码文件时，需要对其进行解码。由压缩器（compressor）对文件进行编码，由解压器（decompressor）进行解码。（1）长度-游程编码的压缩/解压；+（2）LZW压缩/解压（散列）；（1）长度-游程编码的压缩/解压；+（3）霍夫曼编码压缩/解压 (霍夫曼树) 【基本要求】要求选用二种压缩/解压策略实现压缩/解压器（1）为必选。输入的为本文文件（.txt），输出的为一种自定义的文件（.nz）。考虑当构成文本的字符集合为a,b,c,z,0,1,2,9时，请用实例测试你的压缩/解压器。你的压缩器会不会出现抖动？（压缩后的文本比原来的还要大）。扩充构成文本的字符集合以便使它适应更一般的情况。【实现提示】LZW：由Lempel、Ziv和Welch这三位科学家所开发的技术。该方法把文本的字符串映射为编码，首先，为该文本中所有可能出现的字母分别分配一个代码。例如：要压缩的对象是aaabbbbbbbaabaaba，由a和b组成。为a分配代码0,为b分配代码1。字符串和编码的关系被存储在字典中。字典如下：Key 01234567CodeAbAaaabbbbbbbbbaaaba LZW压缩器不断的在输入文件中寻找在字典中出现的最长的前缀p,并输出其相应的代码。若输入文件的下一个字符为c，则为pc分配下一个代码，并插入字典，这种策略称为LZW规则。相反，在解压时，编码表由压缩文件重新构造，LZW原则使这种重建成为可能。 如上例子，压缩时，文件中第一个在字典中出现的最长前缀是a, 输出其编码0,然后为字符串aa分配代码2，并插入到字典中。余下的字符串在字典中出现的最长前缀是aa,输出aa的对应代码2，同时为字符串aab分配代码3并将其插入到字典中。依次类推，由此，输出0214537 解压时，要输入代码，然后用代码所表示的文本来替换这些代码。代码到文本的映射可按下面的方法重建：首先把分配给单一字母的代码插入到字典中。象前面一样，字典的入口为key-code对。然而此时是根据给定的代码（key）去寻找相应的入口（而不是根据文本Code）。压缩文件中的第一个代码对应于单一的字母，因此可以由该字母代替。对于压缩文件中的其他代码p,要考虑两种情况：1）在字典中；2）不在字典中。在1）情况下，找到p对应的文本text(p)输出。并且，根据压缩原理可知，若在压缩文件中代码q写在p之前且text(q)是与q对应的文本，则压缩器会为文本text(q)（其后紧跟fc(p)，text(p)的第一个字符）分配一新代码。因此在字典中插入序偶（下一个代码，text(q)fc(p)）。 情况2）时，只有在当前文本段形如text(q)text(q)fc(q)且text(p)=text(q)fc(q)时才会发生。相应的压缩文件段是qp。在压缩过程中，为text(q)fc(q)分配的代码为p。在解压过程中，在用text(q)代替q后，又遇到代码p。然而，此时字典中没有与p对应的文本。因为这种情况只在