数据结(00006

1、 数据结构编程题 二叉树基础周第4 4-2:文本二叉树: 65536kB 内存限制: 1000ms总时间限制 描述 如上图，一棵每个节点都是一个字母，且字母可以用以下若干行文本表互不相同的二叉树，: A-B-* -C -D -E -* -F 在这若干行文本中： 1) 每个字母代表一个节点。该字母在文本中是第几行，就称该节点的行号是几。根在第1行 2) 每个字母左边的-字符的个数代表该结点在树中的层次（树根位于第0层） 3) 若某第 i 层的非根节点在文本中位于第n行，则其父节点必然是第 i-1 层的节点中，行号小于n,且行号与n的差最小的那个 4) 若某文本中位于第n行的节点(层次是i) 有两

2、个子节点，则第n+1行就是其左子节点，右子节点是n+1行以下第一个层次为i+1的节点 5) 若某第 i 层的节点在文本中位于第n行，且其没有左子节点而有右子节点，那么它的下一行就是 i+1个- 字符再加上一个 * 给出一棵树的文本表示法，要求输出该数的前序、后序、中序遍历结果 输入 n 第一行是树的数目不是结尾。0接下来是n棵树，每棵树以0 树的一部分 个节点每棵树不超过100 输出对每棵树，分三行先后输出其前序、后序、中 序遍历结果 两棵树之间以空行分隔 样例输2A-B-*-C-D-E-*-F0 A -B -C 0 样例输出ABCDEF CBFEDA BCAEFD ABCBCABAC 4-3

3、:由中根序列和后根序列重建二叉树 总时间限制: 500ms内存限制: 65535kB 描述 我们知道如何按照三种深度优先次序来周游一棵二叉树，来得到中根序列、前根序列和后根序列。反过来，如果给定二叉树的中根序列和后根可以重建或者给定中根序列和前根序列，序列， 一二叉树。本题输入一棵二叉树的中根序列和后根序列，要求在内存中重建二叉树，最后输出这棵二叉树的前根序列。 用不同的整数来唯一标识二叉树的每一个结点，下面的二叉树 中根序列是9 5 32 67 后根序列9 32 67 5 前根序列5 9 67 32 输入 两行。第一行是二叉树的中根序列，第二行是后根序列。每个数字表示的结点之间用空格隔开。结

4、点数字范围065535。暂不必考虑不合理的输入数据。 输出 由输入中的中根序列和后根序列重建的一行。每个数字表示的结点之间二叉树的前根序列。 用空格隔开。 样例输入9 5 32 67 9 32 67 5 样例输出5 9 67 32 4-4:表达式表达式树表达式求值 总时间限制: 1000ms内存限制: 65535kB 描述 众所周知，任何一个表达式，都可以用一棵表达式树来表示。例如，表达式a+b*c，可以表示为如下的表达式树： + / a * / b c 现在，给你一个中缀表达式，这个中缀表达式用变量来表示（不含数字），请你将这个中缀表达式用表达式二叉树的形式输出出来。 输入 输入分为三个部分

5、。 第一部分为一行，即中缀表达式。中缀表达式可能含有小写字母代表变量（a-z），也可能含有运算符（+、-、*、/、小括号），不含有数字，也不含有空格。 第二部分为一个整数n，表示中缀表达式的变量数。 第三部分有n行，每行格式为C x，C为变 为该变量的值。x量的字符， 输出 输出分为三个部分，第一个部分为该表达式的逆波兰式，即该表达式树的后根遍历结果。占 一行。 第二部分为表达式树的显示，如样例输出所示。如果该二叉树是一棵满二叉树，则最底部的叶子结点，分别占据横坐标的第1、3、5、7个位置（最左边的坐标是1），然后它们的父结点的横坐标，在两个子结点的中间。如果不是满二叉树，则没有结点的地方，用

6、空格填充（但请略去所有的行末空格）。每一行父结点与子结点中隔开一行，用斜杠（/）与反斜杠（）来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格，出现的横坐标位置为父结点的横坐标偏右一格。也就是说，如果树高为m，则输出就有2m-1行。 第三部分为一个整数，表示将值代入变量之后，该中缀表达式的值。需要注意的一点是，除法代表整除运算，即舍弃小数点后的部分。 的现象。同时，测试数据保证不会出现除以0 样例输入 a+b*c 3 a 2 b 7 c 5 样例输出abc*+ + / a * / b c37 第5周 二叉树应用 5-1:实现堆结构 : 65535kB 内存限制: 3000ms总时间限制

7、 描述 定义一个数组，初始化为空。在数组上执行两种操作： 1、增添1个元素，把1个新的元素放入数组。 2、输出并删除数组中最小的数。 使用堆结构实现上述功能的高效算法。 输入 第一行输入一个整数t，代表测试数据的组数。 对于每组测试数据，第一行输入一个整数n，代表操作的次数。 每次操作首先输入一个整数type。 当type=1，增添操作，接着输入一个整数u，代表要插入的元素。 当type=2，输出删除操作，输出并删除数组中最小的元素。 。1=n=100000 输出 每次删除操作输出被删除的数字。 样例输入2 5 1 1 1 2 1 3 2 241 51 11 72 样例输出121 提示 每组测

8、试数据的复杂度为O(nlgn)的算法才 能通过本次，否则会返回TLE(超时) 需要使用最小堆结构来实现本题的算法 5-2:二叉搜索树 总时间限制: 1000ms内存限制: 1024kB 描述 二叉搜索树在动态查表中有特别的用处，一个无序序列可以通过构造一棵二叉搜索树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉搜索树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。 这里，我们想探究二叉树的建立和序列输出。 输入 只有一行，包含若干个数字，中间用空格隔开。 （数字可能会有重复） 输出对输入数字建立二叉搜索树后进

9、行输出一行， 前序周游的结果。 样例输入464 962 724 169 478 358 41 467 334 500 705 145 281 827 961 491 995 942 827 436 样例输出 41 467 334 169 145 281 358 464 436 500478 491 724 705 962 827 961 942 995 5-3:Huffman编码树 总时间限制: 1000ms内存限制: 65535kB 描述每个外部节点的扩充二叉树，个构造一个具有n外部节点Ki有一个Wi对应，作为该外部节点的权。使得这个扩充二叉树的叶节点带权外部路径长度总和最小： Min( W

10、1 * L1 + W2 * L2 + W3 * L3 + + Wn * Ln) 每个节点的权值。Wi: 个外部叶子节点的距离。根节点到第iLi: 编程计算最小外部路径长度总和。 输入 ，代表测试数据的组数。第一行输入一个整数t，n对于每组测试数据，第一行输入一个整数代表个整数，第二行输入n外部节点的个数。 各个外部节点的权值。2=N 1 / 4 5 2 / 4 3 5 现在请你将一些一般的树用这种方法转换为二叉树，并输出转换前和转换后树的高度。 输入 输入包括多行，最后一行以一个#表示结束。 每行是一个由“u”和“d”组成的字符串，表示一棵树的深度优先搜索信息。比如，dudduduudu可以用

11、来表示上文中的左树，因为搜索过程为：0 Down to 1 Up to 0 Down to 2 Down to 4 Up to 2 Down to 5 Up to 2 Up to 0 Down to 3 Up to 0。 你可以认为每棵树的结点数至少为2，并且不超过10000。 输出 对于每棵树，按如下格式输出转换前和转换后树的高度： Tree t: h1 = h2 是转换前树h1是树的编号（从1开始），t其中 的高度，h2是转换后树的高度。 样例输入dudduduudu ddddduuuuu dddduduuuu dddduuduuu # 样例输Tree 1: 2 = 4Tree 2: 5

12、= 5Tree 3: 4 = 5Tree 4: 4 = 4 6-3:宗教信仰 总时间限制: 5000ms内存限制: 65536kB 描述 世界上有许多宗教，你感兴趣的是你学校里的同 学信仰多少种宗教。 你的学校有n名学生（0 n = 50000），你不太可能询问每个人的宗教信仰，因为他们不太愿意透露。但是当你同时找到2名学生，他们却 愿意告诉你他们是否信仰同一宗教，你可以通过很多这样的询问估算学校里的宗教数目的上限。你可以认为每名学生只会信仰最多一种宗教。 输入 输入包括多组数据。 每组数据的第一行包括n和m，0 = m = n(n-1)/2，其后m行每行包括两个数字i和j，表示学生i和学生j

13、信仰同一宗教，学生被标号为1至n。输入以一行 n = m = 0 作为结束。 输出 对于每组数据，先输出它的编号（从1开始），接着输出学生信仰的不同宗教的数目上限。 样例输入 10 9 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 10 42 34 54 85 80 0 样例输出Case 1: 1Case 2: 7 6-4:电话号码: 65536kB 总时间限制: 1000ms内存限制 描述给你一些电话号码，请判断它们是否是一致的， 即是否有某个电话是另一个电话的前缀。比如：Emergency 911 Alice 97 625 999 Bob 91 12 54 26

14、 的电话，Bob在这个例子中，我们不可能拨通的电话是它的前缀，当拨打Emergency因为所以这些，EmergencyBob的电话时会先接通电话号码不是一致的。 输入 第一行是一个整数t，1 t 40，表示测试数据的数目。 n 1 ，n每个测试样例的第一行是一个整数 位n，其后行每行是一个不超过10 10000 的电话号码。 输出出输是一致的，测对于每个试数据如果 ”，如果不是输出“NO”。“YES 样例输入2 3 91197625999911254265113123401234401234598346 样例输出NO YES 第7周 图 7-1:我爱北大 总时间限制: 1000ms内存限制:

15、65535kB 描述 “红楼飞雪，一时英杰”耳边传来了那熟悉的歌声。而这，只怕是我最后一次听到这个声音了。 想当年，我们曾经怀着豪情壮志，许下心愿，走过静园，走过一体，走过未名湖畔的每个角落。 想当年，我们也曾慷慨高歌，瞻仰民主与科学，瞻仰博雅塔顶，那百年之前的遗韵。 没错，我爱北大，我爱这个校园。 然而，从当我们穿上学位服的那一刻起，这个校园，就再也不属于我。它只属于往事，属于我的回忆。 没错，这，是我在北大的最后一日。此时，此景， 此生，此世，将刻骨难忘。 再也没有了图书馆自习的各种纷纭，再也没有了运动场上的挥汗如雨，有的，只是心中永远的不舍，与牵挂。 夜，已深。人，却不愿离去。天边有一颗

16、流星划过，是那般静，宁谧。 忍不住不回头，我的眼边，有泪光，划过。 这时候，突然有一位路人甲从你身旁出现，问你：从XX到XX怎么走？ 索性，就让我再爱你一次。因为，北大永远在你心中。北大的地图，永远在你的心中。 轻手挥扬，不带走一分云彩。 输入 输入分为三个部分。 第一个部分有P+1行，第一行为一个整数P，之后的P行表示北大的地点。 第二个部分有Q+1行，第一行为一个整数Q，行每行分别为两个字符串与一个整Q之后的 数，表示这两点有直线的道路，并显示二者之 。间的矩离（单位为米），行，第一行为一个整数RR+1第三个部分有 表示需要求的R行每行为两个字符串，之后的 路线。p30,Q50,R相隔其中

17、两个点之间，用-(矩离 样例输6XueYiShiTangCanYinZhongXinXueWuShiTangXueYiXiaoBaiFangBaiNianJiangTangGongHangQuKuanJi6 XueYiShiTang CanYinZhongXin 80 XueWuShiTang CanYinZhongXin 40 XueYiShiTang XueYiXiaoBaiFang 35 XueYiXiaoBaiFang XueWuShiTang 85 CanYinZhongXin GongHangQuKuanJi 60 BaiNianJiangTang GongHangQuKuanJi

18、 35 1 XueYiXiaoBaiFang BaiNianJiangTang 样例输出XueYiXiaoBaiFang-(35)-XueYiShiTng-(80)-CanYinZhongXin-(60)-GngHangQuKuanJi-(35)-BaiNianJianTang 提示 很O疼的一道题。说出不少伤感事啊。两个最短路的算法都是可以用的，可以视情况选择你习惯的那个算法。 宝昌县长要修路7-2: 总时间限制: 1000ms内存限制: 10000kB 描述 宝昌县长意气风发，他决定整修之前县里的道路。县里的道路很多，但维护费用昂贵。具体如图A所示。线段上面的数据表示两个节点之间的所需要的

19、维修费用，现在需要对乡村进行道路优化，最基本的要求是将所有的村庄节点都要联通起来，并且要求每月的维护费用最小。比如优化后的图如B所示。 输入 第一行只包含一个表示村庄个数的数n，n不大于26，并且这n个村庄是由大写字母表里 的前n个字母表示。接下来的n-1行是由字母表的前n-1个字母开头。最后一个村庄表示的字母不用输入。对于每一行，以每个村庄表示的字母开头，然后后面跟着一个数字，表示有多少条道路可以从这个村到后面字母表中的村庄。如果k是大于0，表示该行后面会表示k条道路的k个数据。每条道路的数据是由表示连接到另一端村庄的字母和每月维修该道路的花费组成。维修费用是正整数的并且小于100。该行的所

20、有数据字段分隔单一空白。该公路网将始终连接所有的村庄。该公路网将永远不会超过75条道路。没有任何一个村庄会有超过15条的道路连接到其他村庄（之前或之后的字母）。在下面的示例输入，数据是与上面 的地图相一致的。 输出表示每个数据集中每月维持输出是一个整数， 道路系统连接到所有村庄所花费的最低成本。 样例输入9 A 2 B 12 I 25 B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44 E 2 F 60 G 38F 0G 1 H 35H 1 I 35 样例输出216 提示 考虑看成最小生成树问题，注意输入表示。 拓扑排序7-3: : 1000kB 内存限制总时间限制: 10000ms 描述 要求输出其拓扑排序序列，给出一个图的结构， 在同等条件下，编号小的顶点在前 输入个数，分别为顶点数若干行整数，第一行有2个数，2，接下来有a行，每一行有v和弧数a 分别是该条弧所关联的两个顶点编号 输出用小写字(若干个空格隔开的顶点构成的序列) 母 样例输6 81 21 31 43 2 3 5 4 5 6 4 6 5 样例输出 v1 v3 v2 v6 v4 v5 7-4:地震之后 总时间限制: 100