数据结构课程设计题目

着山芋的小孩退出游戏，然后从下一个小孩重新开始计数，如此不断，最后剩下的那个孩子就是幸运者。要求设计一个程序模拟次过程，并给出不同的n，k组合下那个幸运者是谁？

47.入学考试问题

某地大学入学考试，相关信息如下： (1)参加人数：10万。

(2)共有8门考试课程，每门课程满分均为100分，所有课程成绩均进行了4舍5入的处理，考生的总分也照此处理。

(3)所有考生的考试成绩保存在文件scores.txt中，文件格式如下：

每个考生成绩一行，每行格式如下：最开始为考生姓名，然后为每门课程的分数，考生姓名与课程分数之间，以及不同课程分数之间均用一个英文逗号隔开，如： 张三,98,92,60,54,87,75,86,92 个别考生成绩行的格式可能会有误。

(4)共招收三个批次的学生，第一批次30000人，第二批次60000人，第三批次10000人。录取顺序为：第一批次，第二批次，第三批次。 程序要求：

(1)确定每一批次的录取分数线，并将批次、分数线、实际录取人数输出到文本文件soutput.txt中，每一批次录取信息占一行，格式自定。确定分数线时，如果在分数线处有多名考生，则将这些考生全部录取，即每一批次的实际录取人数可能会超过预定人数。例如：假定在确定第一批次分数线时，有7800人的总分高于等于750分，有8050人的总分高于等于749分，则第一批次分数线应确定为749分，实际录取人数为8050人。

(2)如果考生成绩行的格式不对，则丢弃该考生的成绩，不作为确定分数线的依据，但要求将该考生姓名输出到文本文件serror.txt中，格式自定。

(3)将总分为650分的考生姓名输出到文本文件soutput.txt中，格式自定。

(4)将第三批次录取的所有考生的平均成绩（4舍5入）输出到文本文件soutput.txt中，格式自定。

(5)要求将下面两个时间值（单位为秒）输出到文件soutput.txt的最后：从打开scores.txt文件到读完所有考生成绩的时间；从打开scores.txt文件到程序结束的时间。

48.括号嵌套问题

某个序列完全由圆括号组成，一个“（”和一个“）”称为一对括号，且序列中的括号成对出现。设n为序列中出现的括号对数，k为序列中括号的最大嵌套深度；那么，序列“((()()()))()(())”的n为8，k为3。

1、请编程判断任意给定的圆括号序列，是否是一个深度为k的序列。 要求：（1）先输入嵌套深度k，然后输入任意一个序列，最后给出判定结果（是，不是，或者输入序列中的括号不配对）

（2）可以反复输入数据，当k为0时，程序结束。while(k!=0)

输入示例： 3

((()()()))()(()) 2

((()()()))()(()) 5

(()()()))()((((()))))

输出的判定结果： 测试1：YES 测试2：NO

测试3：括号不配对

2、编程输出括号对数为n，嵌套深度为k的所有序列。(1<=k<=n<=10) 比如，当n=3，k=2时，共有3个嵌套深度为2的序列，即“()(())”、“(()())”、“(())()”。 要求：（1）每一个输出序列单独占一行；并在末尾输出“×对括号，×层嵌套问题,共求出×××种序列”。

（2）可以反复输入数据，当k>n时，程序结束。

输出结果示例（n=5，k=3）： 1: ((()()())) 2: ((()())()) 3: ((()()))() 4: ((())(())) 5: ((())()()) 6: ((())())() 7: ((()))(()) 8: ((()))()() 9: (()(()())) 10: (()(())()) 11: (()(()))() 12: (()()(())) 13: (())((())) 14: ()((()())) 15: ()((())()) 16: ()((()))() 17: ()(()(())) 18: ()()((()))

5对括号，3层嵌套问题,共求出18种情况

3、求解括号对数为n，嵌套深度为k的序列的总数（不输出具体序列）。(1<=k<=n<=30) 输入示例： 3 2 15 3 20 11 输出结果： 3 2：3种

15 3：497845种 2011：94817125种

49.树重建

给出一棵标号树的BFS序列和DFS序列，设计一个算法重新建立这棵树（结点数n≤1000）。当某结点被扩展时，它的所有孩子应该按照编号从小到大的顺序访问。例如一棵树的BFS序列为43512876，DFS序列为43172658，则一棵满足条件的树如右图所示。 输入格式

第一行输入结点数n。第二行n个用空格隔开的整数，描述这棵树的BFS序列；第三行n个用空格隔开的整数，描述这棵树的DFS序列。 输出格式

一共输出n-1行，每行两个整数i,j描述一条边，表示第i个结点与第j个结点之间连一条边。 样例输入 8

4 3 5 1 2 8 7 6 4 3 1 7 2 6 5 8 样例输出 4 5 5 8 4 3 3 2 2 6 3 1 1 7

提示：我们曾经遇到过相似的题目，给出一棵二叉树的先序，中序，后续遍历中的其中两种，要你还原这棵二叉树。而这题改为了给出DFS和BFS序列，虽然形式上变了，但是原理还是相似的，我们只需抓住树的性质和充分利用这两个序列的特性就能把这种题目解决。 拿题目数据做例子。首先，无论是BFS（广度优先搜索）序列还是DFS（深度优先搜索）序列，第一个点都必定是根结点。接着我们看BFS序列，跟在根结点4后面的连续若干个结点就是4的儿子结点，但是究竟有多少个是4的儿子呢？首先，题目中的一个条件说：“某结点被扩展时，它的所有孩子应该按照编号从小到大的顺序访问”，因此4的儿子应该是按由小到大出现在BFS序列中的。后面3<5，但是5>1，所以1就肯定不是4的儿子。然而即使后面若干个数满足升序的条件，也不一定全都是4的儿子，这时我们就要借助DFS序列了。因为DFS的规律是遍历完一棵子树才到另一棵，所以4的儿子在DFS序列中也是按由小到大出现，只是它们之间可能被若干个结点隔开罢了。根据这两个条件，我们就能判断哪些是4的儿子了。例如在BFS序列中紧挨着4出现的3,5，在DFS序列中也是按照由小到大的顺序先出现3，再出现5，因此3,5都是4的儿子。

接下来怎么做呢？由于4的儿子都确定了，剩下的就是把4的每一棵子树都确定下来，而这就是一个子问题了。若我们确定了根结点有k个儿子，若第i个儿子在DFS中的位置为P1，第i+1个儿子在DFS中的位置为P2，则在DFS序列中位置P1与P2之间的所有结点就是以第i个儿子为根的子树的结点。而我们可以建立一个队列，每确定一个结点就把它加到队列里面去，模拟BFS的过程。在模拟广搜的过程中，若当前要处理的结点为k，由于以k为根的整棵子树在DFS序列中是连续的一段，而究竟是那一段在前面的广搜过程中是可以顺带求出的。然后我们利用BFS序列和DFS序列中连续的一段确定出k的所有儿子，并加到广搜队列里面。直到广搜结束，问题就解决了。

50.背包问题的求解

假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , ? , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + ? + wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2） （1，4，5） （8，2） （3，5，2）。

提示：可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品\太大\不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明\刚刚\装入背包的那件物品\不合适\，应将它取出\弃之一边\，继续再从\它之后\的物品中选取，如此重复，，直至求得满足条件的解，或者无解。

由于回溯求解的规则规则是\后进先出\因此自然要用到栈。

51.全国交通咨询模拟

【问题描述】处于对不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则希望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。

【基本要求】（1）提供对城市信息进行编辑（如：添加或删除）的功能。

（2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。

（3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。

（4）旅途中耗费的总时间应该包括中转站的等候时间。

（5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。

【测试数据】

【实现提示】（1）对全国城市交通图和班车时刻表及飞机航班表的编辑，应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需根据交通图给出各个路段的详细信息，例如：对于从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至各段的出发时间、到达时间和票价信息。

（2）以邻接表作交通图的存储结构，表示边的结点内除含有邻接点的信息外，包括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。

52.LZW压缩器/解压器

【问题描述】