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

题目一：约瑟夫生者死者游戏（顺序存储）（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） 【问题描述： 【提示】对于此问题，可使用队列这种数据结构实现。请设计人性化的操作界面。 题目七：皇后问题（B+） 题目八：排序算法动画演示（A） 题目九：哈夫曼编码和译码（A） 【内容与要求】 对于输入的字符串序列，根据各个字符出现的次数，以此构造权重值，构造哈夫曼树，进行哈夫曼编码，并能进行译码。 【提示】采用树的顺序存储方式实现。 题目十：文本文件单词的检索与计数（A+） 要求编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写；统计给定单词在文本文件中出现的次数；检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。该设计要求可分为三个部分实现：其一，建立文本文件，文件名由用户用键盘输入；其二，给定单词的计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数；其三，检索给定单词，输入一个单词，检索并输出该单词所在的行号、该行中出现的次数以及在该行中的相应位置。 题目十一：插队买票问题（A） 问题描述：排队买票每个队伍允许插队。每次一个人入队列，如果这个入队的人发现队伍中有自己的朋友，则可以插入到这个朋友的后面；当队伍中朋友不止一个的时候，这个人要排在最后一个朋友的后面；如果队伍中没有朋友，则他只能排在这个队伍的最后面。当队伍前面的人买到车票之后，依次出队。输入要求：从文件“input.txt”中读入测试用例，一个文件可包含多个测试用例。每个用例第一行是朋友组的数目n。对于一个朋友组的数目m开始，由朋友的名字组成，以空格分隔，每个人的名字都不同，每个人只能属于一个朋友组。操作命令：ENQUEUE X-----X入队；DEQUEUE----头完票出队；STOP----结束。输出要求：测试结果输出到文件“output.txt”中，并显示在屏幕上。对于每个DEQUEUE命令，输出刚出队的人名。 题目十三：背包问题的研究和实现（A） 题目十四：村庄之间最小代价问题的设计和实现（A） 题目十五：基于huffman编码算法实现数据压缩问题（A） 题目十六：校园导游的设计与实现（A） 704 651 349 157