数据结构实训题目(2011级).doc

题目一：约瑟夫生者死者游戏（顺序存储）（C）1题目二：约瑟夫生者死者游戏（链表存储）（C）2题目三：模拟停车场（B）2题目四：表达式求值（A）2题目五：迷宫的求解(B+)2题目六：舞伴配对问题（B）3题目七：皇后问题（B+）3题目八：排序算法动画演示（A）3题目九：哈夫曼编码和译码（A）3题目十：文本文件单词的检索与计数（A+）3题目十一：插队买票问题（A）3题目十二：交通咨询模拟系统（A）4题目十三：背包问题的研究和实现（A）5题目十四：村庄之间最小代价问题的设计和实现（A）5题目十五：基于huffman编码算法实现数据压缩问题（A）5题目十六：校园导游的设计与实现（A）5说明：一， 每个题目自己可以根据实际需求适当发挥：如考虑的需求更符合实际情况，或者界面的操作更加人性化等等。这些都可以酌情提高难度系数。二， 大家可以根据实际需求，结合数据结构的知识，自己设定实训题目，请与指导老师联系，指导老师通过后方可进行实训。题目一：约瑟夫生者死者游戏（顺序存储）（C）【内容与要求】 约瑟夫游戏的大意是：每30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入还中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人数起，依次报数，数到第9人，便把他投入大海中，然后再从他的下一个人数起，数到第9人，再将他扔进大海中，如此循环地进行，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。【提示1】为了解决这一问题，可以用一个长度为30的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每投入大海一个乘客，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。这样做不仅算法较复杂，而且效率低，还要移动大量的元素。题目二：约瑟夫生者死者游戏（链表存储）（C）同上【提示2】也可以采用单循环链表来解决这一问题，实现的方法相对要简单得多。首先要定义链表结点，单循环链表的结点结构于一般单链表的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成一个具有30个结点的单循环链表。接下来从位置为1的结点开始数，数到第8个结点，就将下一个结点开始数起，数到第8个结点，再将其下一个结点删去，如此进行下去，直至剩下15个结点为止。为了不失一般性，将30改为一个任意输入的正整数N，而报数上限（原为9）也为一个任选的正整数K。题目三：模拟停车场（B）题目四：表达式求值（A）【问题描述】：设计一个表达式求值的程序，该程序至少可以接受包含：（、）、/、%、运算符的中缀表达式。如果表达式正确，则输出表达式的结果，如果表达式非法，则输出错误信息。输入要求：程序从“inputexp.txt”文件中读取信息，在这个文件中有多个中缀表达式，每个表达式占一行，程序的读取操作在文件的结尾处停止。输出要求：对于每个表达式，将其结果放在“outputexp.txt”文件的每一行中。这些结果可能是值（精确到小数点后两位），也可以是错误信息：“The expression is error！”提示：表达式非法的情况请考虑尽量全面，如：12）一个表达式中只有着括号或右括号，则表达式非法。一个表达式中除数为0则表达式非法：2/0。还有其他的非法情况如：2.12等等，请自己思考总结。如果时间允许，请加入其更多的操作符。题目五：迷宫的求解(B+)【内容与要求】 迷宫有两个门，一个叫做入口，一个叫做出口。把一个老鼠从一个无顶盖的大盒子的入口赶进迷宫。迷宫中设置很多隔壁。对前进的方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。求解迷宫问题，即找从入口到出口的路径。【提示】对于迷宫问题，可使用栈这种数据结构实现，二维迷宫可通过矩阵表示，从出发点开始，每个点按照四个邻域计算，按照右，上，左，下的顺序搜索下一落脚点，有路则进，无路即退回前点再从下一个方向搜索。题目六：舞伴配对问题（B）【内容与要求】假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写程序模拟上述舞伴配对问题。【提示】对于此问题，可使用队列这种数据结构实现。请设计人性化的操作界面。题目七：皇后问题（B+）题目八：排序算法动画演示（A）题目九：哈夫曼编码和译码（A）【内容与要求】对于输入的字符串序列，根据各个字符出现的次数，以此构造权重值，构造哈夫曼树，进行哈夫曼编码，并能进行译码。【提示】采用树的顺序存储方式实现。题目十：文本文件单词的检索与计数（A+）要求编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写；统计给定单词在文本文件中出现的次数；检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。该设计要求可分为三个部分实现：其一，建立文本文件，文件名由用户用键盘输入；其二，给定单词的计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数；其三，检索给定单词，输入一个单词，检索并输出该单词所在的行号、该行中出现的次数以及在该行中的相应位置。题目十一：插队买票问题（A）问题描述：排队买票每个队伍允许插队。每次一个人入队列，如果这个入队的人发现队伍中有自己的朋友，则可以插入到这个朋友的后面；当队伍中朋友不止一个的时候，这个人要排在最后一个朋友的后面；如果队伍中没有朋友，则他只能排在这个队伍的最后面。当队伍前面的人买到车票之后，依次出队。输入要求：从文件“input.txt”中读入测试用例，一个文件可包含多个测试用例。每个用例第一行是朋友组的数目n（1=n=100）。对于一个朋友组以朋友的数目m开始（1=m=100），由朋友的名字组成，以空格分隔，每个人的名字都不同，每个人只能属于一个朋友组。如：2 /表示有两个朋友组3 Ann Bob Joe /第一个朋友组：共有3个朋友5 Zoe Jon Jim Jane Fat/第二个朋友组：共有5个朋友操作命令：ENQUEUE X-X入队；DEQUEUE-队头买完票出队；STOP-结束。输入例子如下：输出要求：测试结果输出到文件“output.txt”中，并显示在屏幕上。并对于每个DEQUEUE命令，输出刚出队的人名。对于以上输入，输出结果为：AnnBobJoeZonJimFat题目十二：交通咨询模拟系统（A）设计一个交通咨询模拟系统，能够让游客从任意一个城市到另外一个城市之间找到最短路径或者花费最低的路径，或者用时最少的路径。该设计共分为三个部分：1. 建立交通网络图的存储结构。2. 解决单源的最短路径问题。3. 实现任意两个城市之间的最短路径问题。如下图就是一个简单的交通网络，网络上的数字