数据结构竞赛题目集锦

1、数据结构竞赛题目集锦 1. 发现环（题目来源：2017蓝桥杯决赛） 问题描述 小明的实验室有 N台电脑，编号1No原本这N台电脑之间有N-1条数据链接相连，恰 好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。 不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接， 于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上 的数据传输出现了 BUG 为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？ 输入格式 第一行包含一个整数 No 以下N行每行两个整数 a和b,表示a和b之间有一条数据链接相连。 对于30%勺数据

2、，1 = N = 1000 对于 100%勺数据，1 = N = 100000,1 = a, b = N 输入保证合法。 输出格式 按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。 样例输入 5 1 2 3 1 2 4 2 5 5 3 样例输出 1 2 3 5 2. 小朋友排队（题目来源：第五届蓝桥杯预赛 C/C+本科B组） 问题描述 n个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位 置相邻的两个小朋友。 每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。 如果某个小朋友第一次被要求交换，则他的不高兴程度增加 1,如果第二次要求

3、他交换， 则他的不高兴程度增加 2 （即不高兴程度为 3），依次类推。当要求某个小朋友第k次交换 时，他的不高兴程度增加 k。 请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。 如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。 输入格式 输入的第一行包含一个整数 n,表示小朋友的个数。 第二行包含n个整数H1 H2Hn，分别表示每个小朋友的身高。 输出格式 输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。 样例输入 3 3 2 1 样例输出 9 3. 剪邮票（题目来源：2016年蓝桥杯） 问题描述 如图1所示,有12张连在一起的12生肖的邮票。现在你要从

4、中剪下 5张来，要求必须 是连着的（仅仅连接一个角不算相连）。比如，图 2,图3中，粉红色所示部分就是合格的 剪取。请你计算，一共有多少种不同的剪取方法。 图1 1 2 3 4 5 6 7 8 9 10 11 12 图2 1 2 3 4 5 6 7 8 9 10 11 12 图3 4. 泊松分酒（题目来源：第三届蓝桥杯） 问题描述 泊松是法国数学家、物理学家和力学家。他一生致力科学事业，成果颇多。有许多著名 的公式定理以他的名字命名，比如概率论中著名的泊松分布。 有一次闲暇时，他提出过一个有趣的问题，后称为：“泊松分酒”。在我国古代也提出 过类似问题，遗憾的是没有进行彻底探索，其中流传较多是：

5、“韩信走马分油”问题。 有3个容器，容量分别为 12升，8升，5升。其中12升中装满油，另外两个空着。要 求你只用3个容器操作，最后使得某个容器中正好有6升油。 下面的列表是可能的操作状态记录： 12,0,0 4,8,0 4.3.5 9,3,0 9,0,3 1,8,3 1.6.5 每行3个数据，分别表示12, 8，6升容器中的油量 第一行表示初始状态，第二行表示把12升倒入8升容器后的状态，第三行是8升倒入 5升， 当然，同一个题目可能有多种不同的正确操作步骤。 本题目的要求是，请你编写程序，由用户输入：各个容器的容量，开始的状态，和要求 的目标油量，程序则通过计算输出一种实现的步骤（不需要找

6、到所有可能的方法）。如果没 有可能实现，则输出：“不可能”。 例如，用户输入： 12,8,5,12,0,0,6 用户输入的前三个数是容器容量（由大到小），接下来三个数是三个容器开始时的油量 配置，最后一个数是要求得到的油量（放在哪个容器里得到都可以） 则程序可以输出（答案不唯一，只验证操作可行性）： 12,0,0 4,8,0 4.3.5 9,3,0 9,0,3 1,8,3 1.6.5 每一行表示一个操作过程中的油量状态。 5. 分巧克力（题目来源：第八届蓝桥杯 ） 问题描述 儿童节那天有 K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。 小明一共有N块巧克力，其中第i块是Hi x

7、Wi的方格组成的长方形。 为了公平起见，小明需要从这N块巧克力中切出 K块巧克力分给小朋友们。切出的巧 克力需要满足： 1. 形状是正方形，边长是整数 2. 大小相同 例如一块6x5的巧克力可以切出 6块2x2的巧克力或者2块3x3的巧克力。 当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？ 输入格式 第一行包含两个整数 N和K。（1 = N, K = 100000） 以下N行每行包含两个整数Hi和 Wi。（1 = Hi, Wi = 100000） 输入保证每位小朋友至少能获得一块1x1的巧克力。 输出格式 输出切出的正方形巧克力最大可能的边长。 样例输入: 2 10 6 5 5 6 样例输出： 2 6. 密文搜索（题目来源：2015年蓝桥杯决赛） 问题描述 福尔摩斯从X星收到一份资料，全部是小写字母组成。他的助手提供了另一份资料： 许多长度为8的密码列表。福尔摩斯发现，这些密码是被打乱后隐藏在先前那份资料中的。 请你编写一个程序，从第一份资料中搜索可能隐藏密码的位置。要考虑密码的所有排列可能 性。 输入格式 输入第一行：一个字符串s，全部由小写字母组成，长度小于1024*1024紧接着一行是 一个整数n,表示以下有n行密码，