《数据结构上机考试题》由会员分享，可在线阅读，更多相关《数据结构上机考试题（5页珍藏版）》请在金锄头文库上搜索。
1、注意事项 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
2、个结点每个结点的权值输出构造哈夫曼树(是最优二叉树)得到每个结点的哈夫曼编码输入样例23186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8输出样例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):
3、101016( 63):100017( 15):10111018( 1):10111100119( 48):1101120( 51):010021( 80):111122( 23):11001123( 8):1011111提示输入第一行 是结点数 23 第二行是这几个结点的权值 输出格式为 结点号 (权值)：哈夫 曼编码/计算 huffman 树 WPL时间限制: 5 second 内存限制: 100 Kb 描述假设用于通信的电文由n(4输入仅一组数据，分为两行输入；第1行为n的值，第2行为n(0 输出一个整数，表示所构造哈夫曼树的带权路径长度(输出整数后换行)。输入样例87 19 2 6 3
4、2 3 21 10输出样例261 提示Huffman 树可以使用数组存储/ 求最小生成树的代价时间限制: 5 second 内存限制: 100 Kb 描述求无向网的最小生成树的代价。输入仅一组数据，输入数据第一行为两个正整数n和m,分别表示顶点数和边数。后面紧跟m 行数据，每行数据是一条边的信息，包括三个数字，分别表示该边的两个顶点和边上的权值。 输出输出得到的最小生成树的代价。输入样例8 111 2 31 4 51 6 182 4 72 5 63 5 103 8 204 6 154 7 115 7 85 8 12输出样例59提示每次找到最小生成树的一条边时累加其权值即可得到最小生成树的代价
5、/判断堆栈出栈序列是否有效时间限制: 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 （表示能否通过栈得到该序列）。输入样例263 4 2 1 5 643 1 2 4输出样例yesno提示根据栈的后进先出特性进行判断 / 约瑟夫环时间限制: 5 seco
6、nd 内存限制: 100 Kb描述编号为 1,2,.,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。 报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始, 重新从 1 开始报数，如此下去，直至所有的人全部出圈为止。输入仅有一组数据，输入数据第一行为两个正整数n和m,分别表示人的个数及初始随机数， 第二行为 n 个整数，表示每个人持有的密码输出在一行输出 n 个整数表示依次出圈人的编号，整数之间用空格分隔输入样例7 53 8 1 22 4 9 15输出样例5 2 6
7、 7 4 3 1提示使用不带头节点的单循环链表/根据二叉树的先序和中序列得到后序序列时间限制: 5 second 内存限制: 100 Kb描述二叉树的每个节点用一个字符表示，如果知道二叉树的先序序列和中序序列则可以构造出一 颗二叉树，进而可以得到该二叉树的后序序列输入 仅一组数据，第一行为该二叉树的先序序列，第二行为该二叉树的中序遍历序列。输出输出该二叉树的后序遍历序列输入样例ABDGCEFHDGBAECHF输出样例GDBEHFCA提示使用递归算法，根据先序序列找到树根，然后在中序序列中找到左右子树。此题不一定需要 把树建立起来，可以在递归同时就得到后序序列。/求无向图连通子图时间限制: 5
8、second 内存限制: 100 Kb描述求无向图连通子图个数输入仅一组数据，输入数据第一行为两个正整数n (1输出输出由两行构成，第一行输出该图中连通子图的个数。第二行按照升序输出每个连通子图中 顶点个数。输入样例9 81 21 32 43 45 75 66 78 9输出样例32 3 4提示 图的连通性以吐得遍历为基础，因此本题需要在图的遍历算法基础上实现 / 根据给定的关键字构造小顶堆，输出堆的中序遍历序列时间限制: 5 second 内存限制: 100 Kb描述给出一组关键字（数字），根据这些关键字构造一个小顶堆，然后输出该小顶堆所对应的二 叉树的中序遍历序列。输入仅一组数据，输入数据第一行为1个正整数n表示关键字个数。第2行为n个整数表示n 个关键字。输出在一行上输出由这些关键字构成的小顶堆所对应的中序遍历序列。输入样例949 38 65 97 76 13 27 18 20输出样例97 20 38 18 76 13 65 27 49提示堆是一个完全二叉树，可以用数组存储
