注意事项1. 考试时间2小时，13：00-15：00 2. 题目4选2 3. 所有题目均使用标准输入和标准输出3. 只提交源程序，文件后缀名只能是.C或.CPP 4. 源文件大小不能超过10K，否则会被当作恶意提交而扣分5. 严格按照题目要求输出，去掉不需要的提示信息或调试信息6. 在程序中不要使用fflush(stdin)函数，否则会导致结果错误另外注意：本次是模拟测试，上机时间是4个小时，我们考试时间从14点开始到17点30分结束。
同学视自己的能力，能做几道做几道。
哈夫曼树
时间限制: 100 second 内存限制: 100 Kb
描述
构造哈夫曼树（最优二叉树）
输入
输入n个结点每个结点的权值
输出
构造哈夫曼树（是最优二叉树）得到每个结点的哈夫曼编码
输入样例
23
186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8
输出样例
1( 186):00
2( 64):1001
3( 13):101100
4( 22):110010
5( 32):11100
6( 103):011
7( 21):110001
8( 15):101101
9( 47):11010
10( 57):0101
11( 1):101111000
12( 5):10111101
13( 32):11101
14( 20):110000
15( 57):1010
16( 63):1000
17( 15):101110
18( 1):101111001
19( 48):11011
20( 51):0100
21( 80):1111
22( 23):110011
23( 8):1011111
提示
输入第一行是结点数23 第二行是这几个结点的权值输出格式为结点号（权值）：哈夫曼编码
///////////////////////////////////////
计算huffman树WPL
时间限制: 5 second 内存限制: 100 Kb
描述
假设用于通信的电文由ｎ（4
输入
仅一组数据，分为两行输入；第１行为ｎ的值，第２行为ｎ（0
输出
一个整数，表示所构造哈夫曼树的带权路径长度（输出整数后换行）。
输入样例
8
7 19 2 6 32 3 21 10
输出样例
261
提示
Huffman树可以使用数组存储
//////////////////////////////////
求最小生成树的代价
时间限制: 5 second 内存限制: 100 Kb
描述
求无向网的最小生成树的代价。
输入
仅一组数据，输入数据第一行为两个正整数n和m，分别表示顶点数和边数。
后面紧跟m 行数据，每行数据是一条边的信息，包括三个数字，分别表示该边的两个顶点和边上的权值。
输出
输出得到的最小生成树的代价。
输入样例
8 11
1 2 3
1 4 5
1 6 18
2 4 7
2 5 6
3 5 10
3 8 20
4 6 15
4 7 11
5 7 8
5 8 12
输出样例
59
提示
每次找到最小生成树的一条边时累加其权值即可得到最小生成树的代价
///////////////////////////
判断堆栈出栈序列是否有效
时间限制: 5 second 内存限制: 100 Kb
描述
如果以序列“1,2,3,4”作为一个栈（初始为空）的输入，那么可得到输出序列“1,2,3,4”或“4,3,2,1”或“2,3,1,4”等等，但是肯定得不到输出序列“4,1,2,3”或“3,1,2,4”等等。
请编写一个程序，判断能否通过一个栈得到给定的输出序列。
输入
有多组数据；输入的第一行为整数n（1
输出
对于每一组数据，输出一个yes或no（表示能否通过栈得到该序列）。
输入样例
2
6
3 4 2 1 5 6
4
3 1 2 4
输出样例
yes
no
提示
根据栈的后进先出特性进行判断
////////////////////////////
约瑟夫环
时间限制: 5 second 内存限制: 100 Kb
描述
编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。
报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出圈为止。
输入
仅有一组数据，输入数据第一行为两个正整数n和m，分别表示人的个数及初始随机数，第二行为n个整数，表示每个人持有的密码
输出
在一行输出n个整数表示依次出圈人的编号，整数之间用空格分隔
输入样例
7 5
3 8 1 22
4 9 15
输出样例
5 2
6
7 4 3 1
提示
使用不带头节点的单循环链表
/////////////////////
根据二叉树的先序和中序列得到后序序列
时间限制: 5 second 内存限制: 100 Kb
描述
二叉树的每个节点用一个字符表示，如果知道二叉树的先序序列和中序序列则可以构造出一颗二叉树，进而可以得到该二叉树的后序序列
输入
仅一组数据，第一行为该二叉树的先序序列，第二行为该二叉树的中序遍历序列。
输出
输出该二叉树的后序遍历序列
输入样例
ABDGCEFH
DGBAECHF
输出样例
GDBEHFCA
提示
使用递归算法，根据先序序列找到树根，然后在中序序列中找到左右子树。
此题不一定需要把树建立起来，可以在递归同时就得到后序序列。
///////////////////////////
求无向图连通子图
时间限制: 5 second 内存限制: 100 Kb
描述
求无向图连通子图个数
输入
仅一组数据，输入数据第一行为两个正整数n（1
输出
输出由两行构成，第一行输出该图中连通子图的个数。
第二行按照升序输出每个连通子图中顶点个数。
输入样例
9 8
1 2
1 3
2 4
3 4
5 7
5 6
6 7
8 9
输出样例
3
2 3 4
提示
图的连通性以吐得遍历为基础，因此本题需要在图的遍历算法基础上实现
////////////////////////////////////
根据给定的关键字构造小顶堆，输出堆的中序遍历序列
时间限制: 5 second 内存限制: 100 Kb
描述
给出一组关键字（数字），根据这些关键字构造一个小顶堆，然后输出该小顶堆所对应的二叉树的中序遍历序列。
输入
仅一组数据，输入数据第一行为1个正整数n，表示关键字个数。
第2行为n个整数表示n 个关键字。
输出
在一行上输出由这些关键字构成的小顶堆所对应的中序遍历序列。
输入样例
9
49 38 65 97 76 13 27 18 20
输出样例
97 20 38 18 76 13 65 27 49
提示
堆是一个完全二叉树，可以用数组存储。