资源描述：
《数据结构上机考试题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、注意事项1.考试时间2小时，13：00-15：002.题目4选23.所有题目均使用标准输入和标准输出3.只提交源程序，文件后缀名只能是.C或.CPP4.源文件大小不能超过10K,否则会被当作恶意提交而扣分5.严格按照题日要求输出，去掉不需要的提示信息或调试信息6.在程序中不要使用fflush(stdin)函数，否则会导致结果错误另外注意：本次是模拟测试，上机时间是4个小时，我们考试时间从14点开始到17点30分结束。同学视自己的能力，能做儿道做儿道。哈夫曼树时间限制:100second内存限制：100Kb描述构造哈夫曼树(最优二叉树)输入输入n个结点每个结点的权值输出
2、构造哈夫曼树(是最优二叉树)得到每个结点的哈夫曼编码输入样例2318664132232103211547571532205763151485180238输出样例1(186):002(64):10013(13):1011004(22):1100105(32):111006(103):0117(21):1100018(15):1011019(47):1101010(57):010111(1):10111100012(5):1011110113(32):1110114(20):11000015(57):101016(63):100017(15):1011101):10111
3、100119(48):1101120(51):010021(80):111122(23):11001123(8):1011111提示输入第一行是结点数23第二行是这几个结点的权值输出格式为结点号(权值)：哈夫曼编码Illllllllllllllllllllllllllllllllllllll计算huffman树WPL时间限制:5second内存限制：100Kb描述假设用于通信的电文由n(4输入仅一组数据，分为两行输入；第1行为n的值，第2行为n(0输出一个整数，表示所构造哈夫曼树的带权路径长度(输出整数后换行)。输入样例8719263232110输出样例261提示Hu
4、ffman树可以使用数组存储IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII求最小生成树的代价时间限制：5second内存限制：100Kb描述求无向网的最小生成树的代价。输入仅一组数据，输入数据笫一行为两个正整数n和m,分别表示顶点数和边数。后面紧跟m行数据，每行数据是一条边的信息，包括三个数字,分别表示该边的两个顶点和边上的权值。输出输出得到的最小生成树的代价。输入样例811123145161824725635103820461547115785812输出样例59提示每次找到最小生成树的一条边时累加其权值即可得到最小生成树的代价IIIIIIIII
5、IIIIIIIIIIIIIIIIII判断堆栈出栈序列是否有效时间限制:5second内存限制：100Kb描述如果以序列作为一个栈（初始为空）的输入，那么可得到输出序列“1,2,3,4”或“4,3,2,1”或“2,3,1,4"等等，但是肯定得不至IJ输出序歹lj或“3,1,2,4”等等。请编写一个程序，判断能否通过一个栈得到给定的输出序列。输入有多组数据；输入的第一行为整数n（1输出对于每一组数据，输出一个yes或no（表示能否通过栈得到该序列）。输入样例2634215643124输出样例yesno提示根据栈的后进先出特性进行判断IIIIIIIIIIIIIIIIIIII
6、IIIIIIII约瑟夫环时间限制:5second内存限制：100Kb描述编号为1,2n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0,从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始,重新从1开始报数，如此下去，直至所有的人全部出圈为止。输入仅有一组数据，输入数据第一行为两个正整数n和m,分别表示人的个数及初始随机数，第二行为n个整数，表示每个人持有的密码输出在一行输出n个整数表示依次出圈人的编号，整数之间用空格分隔输入样例7538122491
7、5输出样例5267431提示使用不带头节点的单循环链表IIIIIIIIIIIIIIIIIIIII根据二叉树的先序和中序列得到后序序列时间限制：5second内存限制:100Kb描述二叉树的每个节点用一个字符表示，如果知道二叉树的先序序列和中序序列则可以构造出一颗二叉树，进而可以得到该二叉树的后序序列输入仅一组数据，第一行为该二叉树的先序序列，第二行为该二叉树的屮序遍历序列。输出输出该二叉树的后序遍历序列输入样例ABDGCEFHDGBAECHF输出样例GDBEHFCA提示使用递归算法，根据先序序列找到树根，然后在屮序序列屮找到左右子树。此题不一定需要把
