原创力文档- 1、本文档共5页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
注意事项1.考试时间2小时，13：00-15：002.题目4选23.所有题目均使用标准输入和
标准输出3.只提交源程序，文件后缀名只能是.C或.CPP4.源文件大小不能超过10K，否则
会被当作恶意提交而扣分5.严格按照题目要求输出，去掉不需要的提示信息或调试信息6.
在程序中不要使用fflush(stdin)函数，否则会导致结果错误另外注意：本次是模拟测试，上
机时间是4个小时，我们考试时间从14点开始到17点30分结束。同学视自己的能力，能
做几道做几道。
哈夫曼树
时间限制:100second内存限制:100Kb
描述
构造哈夫曼树（最优二叉树）
输入
输入n个结点每个结点的权值
输出
构造哈夫曼树（是最优二叉树）得到每个结点的哈夫曼编码
输入样例
23
18664132232103211547571532205763151485180238
输出样例
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)
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
时间限制:5second内存限制:100Kb
描述
假设用于通信的电文由ｎ（4
输入
仅一组数据，分为两行输入；第１行为ｎ的值，第２行为ｎ（0
输出
一个整数，表示所构造哈夫曼树的带权路径长度（输出整数后换行）。
输入样例
8
719263232110
输出样例
261
提示
Huffman树可以使用数组存储
//////////////////////////////////
求最小生成树的代价
时间限制:5second内存限制:100Kb
描述
求无向网的最小生成树的代价。
输入
仅一组数据，输入数据第一行为两个正整数n和m，分别表示顶点数和边数。后面紧跟m
行数据，每行数据是一条边的信息，包括三个数字，分别表示该边的两个顶点和边上的权值。
输出
输出得到的最小生成树的代价。
输入样例
811
123
145
1618
247
256
3510
3820
4615
4711
578
5812
输出样例
59
提示
每次找到最小生成树的一条边时累加其权值即可得到最小生成树的代价
///////////////////////////
判断堆栈出栈序列是否有效
时间限制:5second内存限制:100Kb
描述
如果以序列“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
342156
4
3124
输出样例
yes
no
提示
根据栈的后进先出特性进行判断
////////////////////////////
约瑟夫环
时间限制:5second内存限制:100Kb
描述
编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定
一个随机数m0
文档评论（0）