计算机科学与工程学院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:00
11-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中的整数递增排序。
样例输入
5
1
2
5
6
7
1
2
4
6
9
样例输出
3 1 2 6
B. 无所遁形
题目描述
在BBS上，有些人可能注册多个ID，其中一个称为主ID，其余的称为马甲。咱挨踢人都知道，虽然换了马甲，但是IP地址是不变的。假定每个人的IP是不同的，每个人仅有一个主ID和一个马甲。通过读取BBS上的帖子，要求找出主ID和对应的马甲。
输入格式
每个测试用例的第一行是一个偶数n(0<=n<=20)，表示BBS上的帖子数目。紧接着有n 行信息，每行由两个字符串组成：
BBS_ID IP_Address
BBS_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升序排列。每一个测试用例后应该输出一个空行。
样例输入
8
inkfish 192.168.29.24
zhi 192.168.29.235
magicpig 192.168.50.170
pegasus 192.168.29.235
iamcs 202.116.77.131
finalBob 192.168.29.24
tomek 202.116.77.131
magicduck 192.168.50.170
4
mmmmmm 172.16.72.126
kkkkkk 192.168.49.161
llllll 192.168.49.161
nnnnnn 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 zhi
llllll is the MaJia of kkkkkk nnnnnn is the MaJia of mmmmmm
C 车站调度
题目描述
有顺序排列的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 6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
0 0
样例输出
YES
YES
YES
YES
NO
