计算机科学与工程学院2010级数据结构课程设计任务指导书湖南科技大学计算机学院陈燕晖编2011年8月相关事项说明一：每人独立完成，不允许抄袭。

二：遵循机房管理条例。

三：在机房只能做与课程设计相关的事情，玩游戏、浏览无关网页等情况指导教师可给出本次课程设计不合格的处理。

四：课程设计结束后及时提交课程设计报告，报告格式见数据结构习题集p83。

五：本次课程设计题目提交网址http://125.221.232.254/acmhome，每位同学必须在网站注册，User Name 必须使用学号，Nickname必须写上班级和真实姓名。

六：时间安排如下，其中第一周星期一下午为讲解时间，具体安排：讲解地点：逸夫楼108讲解时间：14:30-15:50 网络、信息安全专业16:00-17:20 计算机科学与技术专业第一周星期二正式开始上机。

第二周星期五为测试时间。

实验时间：上午8：00-11:30；下午14:30-18:0011-12-1学期数据结构课程设计安排表地点：逸夫楼二楼目录A 交集 (1)B. 无所遁形 (2)C 车站调度 (4)D 简单表达式求值 (6)E. 二叉树遍历 (7)F赫夫曼编码 (8)G 二叉排序树 (9)H 查找 (10)I 自来水管道 (11)J 最小时间 (13)K Repairing a Road (14)A 交集题目描述有两个相等长度的正整数序列A和B，都是有序的(递增排序)，同时一个序列中没有重复元素，现在需要求这两个序列的交——序列C，同时打印输出。

输入格式每个测试用例一共有2*n+1行，第一行输入为数列的长度n，然后下面2~n+1行，依次输入序列A中的数。

n+2~2*n+1行，依次输入序列B中的数。

其中 1 <= n <= 50000 , 序列中每个数大小不会超过1000000。

当程序输入n为0时表示结束。

输出格式每个测试用例输出一行，先输出序列C的长度，然后依次输出C中的整数，两个数之间间隔一个空格。

注意行末不要出现空格。

C中的整数递增排序。

样例输入51256712469样例输出3 1 2 6B. 无所遁形题目描述在BBS上，有些人可能注册多个ID，其中一个称为主ID，其余的称为马甲。

咱挨踢人都知道，虽然换了马甲，但是IP地址是不变的。

假定每个人的IP是不同的，每个人仅有一个主ID和一个马甲。

通过读取BBS上的帖子，要求找出主ID和对应的马甲。

输入格式每个测试用例的第一行是一个偶数n(0<=n<=20)，表示BBS上的帖子数目。

紧接着有n 行信息，每行由两个字符串组成：BBS_ID IP_AddressBBS_ID是发帖人的ID，只包含小写字母，长度不超过12。

每个BBS_ID在每个测试用例中只出现一次。

IP_Address是该人的IP地址，格式为“A.B.C.D”，其中A,B,C,D是0-255范围内的整数。

每一个IP地址正好对应两个BBS_ID，首次出现的ID为主ID，后面出现的为马甲。

当程序输入n为0时表示结束。

输出格式对于每一个测试用例，输出n/2行，每行格式如下：“MJ_ID is the MaJia of main_ID”输出要求按main_ID升序排列。

每一个测试用例后应该输出一个空行。

样例输入8inkfish 192.168.29.24zhi 192.168.29.235magicpig 192.168.50.170pegasus 192.168.29.235iamcs 202.116.77.131finalBob 192.168.29.24tomek 202.116.77.131magicduck 192.168.50.1704mmmmmm 172.16.72.126kkkkkk 192.168.49.161llllll 192.168.49.161nnnnnn 172.16.72.126样例输出tomek is the MaJia of iamcs finalBob is the MaJia of inkfish magicduck is the MaJia of magicpig pegasus is the MaJia of zhillllll is the MaJia of kkkkkk nnnnnn is the MaJia of mmmmmmC 车站调度题目描述有顺序排列的1,2, 3,…,n节车厢在入站口等待调度。

车站设置了一个栈作为缓冲，这样的话只可能进行下列两个操作之一：（1）如果还有车厢在入站口，将最前面的入栈缓冲（2）将栈顶的车厢驶出车站给定一个1至n的排列，问其作为出站系列是否合法。

提示：参见习题集p21 题3.1.输入格式输入包含若干测试用例。

每一个测试用例由多行组成。

第一行是两个整数n（1<=n <= 100）和m，n表示入站系列为1至n。

m表示有随后有m行出站系列。

当n，m均为0时表示输入结束输出格式对应每一个出站系列，合法则输出一行YES，否则输出一行NO。

样例输入3 61 2 31 3 22 1 32 3 13 1 23 2 10 0样例输出YESYESYESYESNOYESD 简单表达式求值题目描述给出简单的表达式，运算符只有加减乘除，运算数是非负整数，计算其值。

输入格式输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。

没有非法表达式。

当一行中只有0时输入结束，相应的结果不要输出。

输出格式对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。

样例输入13 - 8 / 4样例输出1.001.00E. 二叉树遍历题目描述对于二叉树T，可以有先序遍历、中序遍历和后序遍历三种遍历方式。

我们知道，任意给定一颗二叉树的两种遍历方式，就可以唯一确定该树。

现在我们要求给出一棵二叉树的先序遍历序列和中序遍历序列，输出它的广度优先遍历序列。

输入格式第一行为一个整数t（0<t<10），表示测试用例个数。

以下t行，每行输入一个测试用例，包含两个字符序列s1和s2，其中s1为一棵二叉树的先序遍历序列，s2为中序遍历序列。

s1和s2之间用一个空格分隔。

序列只包含大写字母，并且每个字母最多只会出现一次。

输出格式为每个测试用例单独一行输出广度优先遍历序列。

样例输入2DBACEGF ABCDEFGBCAD CBAD样例输出DBEACGFBCADF赫夫曼编码题目描述赫夫曼编码能够产生最短的报文。

以报文“ABCDABCDABCABDABAA”为例，A编为0，B对应10，C对应110，D对应111，整体的报文长度为35位二进制。

相比于定长的ASCII码，压缩比达到了18*8/35=4.1。

输入格式输入有一系列的字符串组成，每个字符串占据一行。

字符串仅包含大写字母和下划线。

字符串“END” 表示处理结束，不应对其处理。

输出格式对每一个字符串，输出其ASCII编码的比特位长度，赫夫曼编码的比特位长度，以及二者之比，精确到小数点后一位。

样例输入ABCDABCDABCABDABAAAAAAAAAAAAAAAAAAAAEND样例输出144 35 4.1144 18 8.0G 二叉排序树题目描述N个数可以有N!个排列，每个排列都可以生成一棵二叉排序树。

对于其中任意两个排列，它们生成的二叉排序树可能相同，也可能不同。

现在需要你编程序判断。

输入格式每个测试用例由多行组成。

第一行是一个整数数n，(1<=n<=20) 表示有n个需要判断，如果n= 0表示输入结束。

第二行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉排序树。

接下去的n行有n个序列，每个序列格式和第二行序列一样。

现在以第二行的序列为模板，判断这这n行序列的每一行否能生成与第二行序列一样的二叉排序树。

输出格式如果序列相同则输出YES，否则输出NO样例输入3321546987123456789321564987987654321样例输出NOYESNOH 查找题目描述给定一个集合，查找元素是否在集合中出现。

输入格式每个测试用例由多行组成，第一行是两个整数n和m，两个数范围在1到100000之间。

自第二行起一共有n+m个整数，其中前面n个整数代表集合的元素，随后的m个整数是待查询的数。

所有的整数在范围[-2^31,2^31)内。

输出格式对于每个待查询的数，如果在集合中则输出yes,否则输出no.样例输入5 37 9 3 2 -54 9 -55 3-2 1 0 -2 10 -2 3样例输出noyesyesyesyesnoI 自来水管道题目描述你领到了一个铺设校园内自来水管道的任务。

校园内有若干需要供水的点，每两个供水点可能存在多种铺设路径。

对于每一种铺设路径，其成本是预知的。

任务要求最终铺设的管道保证任意两点可以直接或间接的联通，同时总成本最低。

输入格式每个测试用例由多行组成，第一行是两个整数P和R，P代表供水点数（1<=P<=50），每个点都对应1到P中的一个唯一编号。

R代表可能的铺设路径数，路径数可能有非常多。

接下有R行，每行格式如下：节点A编号节点B编号路径成本路径成本不超过100。

测试用例之间有一空行分开。

输入结束用P=0表示，注意没有R值。

输出格式每个测试用例占用一行输出最低总成本。

样例输入1 02 31 2 372 1 171 2 683 71 2 192 3 113 1 71 3 52 3 893 1 911 2 325 71 2 52 3 72 4 84 5 113 5 101 5 64 2 12样例输出171626J 最小时间题目描述有多个城市组成一个铁路交通网络。

任意两个城市之间有直连铁路，或者通过其他城市间接到达。

给定某个城市，要求min时间内能到达任意指定的另一城市，求最小min。

输入格式每个测试用例由多行组成，第一行是整数n（1 <= n <= 100），表示城市的数目。

其余行表示邻接矩阵A。

A(i,j)的值如果是一个整数t，表示城市i与城市j有铁路直连，需要t时间到达另一方。

如果A(i,j)的值为x，表明城市i与城市j之间没有直连铁路。

很明显有A(i,i) = 0。

由于对称关系和A(i,i) 为0，输入只给出矩阵的下三角。

第一行A(1,1)在输入中省略，第二行只有A(2,1)，下一行则是A(3,1) 和A(3,2)，依此类推。

输出格式输出城市1所对应的min。

样例输入55030 5100 20 5010 x x 10样例输出35K Repairing a Road题目描述You live in a small town with R bidirectional roads connecting C crossings and you want to go from crossing 1 to crossing C as soon as possible. You can visit other crossings before arriving a t crossing C, but it’s not mandatory.You have exactly one chance to ask your friend to repair exactly one existing road, from the time you leave crossing 1. If he repairs the i-th road for t units of time, the crossing time after that would be viai-t. It's not difficult to see that it takes vi units of time to cross that road if your friend doesn’t repair it.You cannot start to cross the road when your friend is repairing it.输入格式There will be at most 25 test cases. Each test case begins with two integers C and R(2<=C<=100, 1<=R<=500). Each of the next R lines contains two integers x i, y i (1<=x i, y i<=C) and two positive floating-point numbers v i and a i (1<=v i<=20,1<=a i<=5), indicating that there is a bidirectional road connecting crossing x i and y i, with parameters v i and a i (see above). Each pair of crossings can be connected by at most one road. The input is terminated by a test case with C=R=0, you should not process it.输出格式For each test case, print the smallest time it takes to reach crossing C from crossing 1, rounded to 3 digits after decimal point. It’s always possible to reach crossing C from crossing 1.样例输入3 21 2 1.5 1.82 3 2.0 1.52 11 2 2.0 1.80 0样例输出2.5891.976。