文章 - 第5页 - 信奥网

信息学奥赛一本通T1367：树与二叉树查找二叉树

【题目描述】已知一棵二叉树用邻接表结构存储，中序查找二叉树中值为x的结点，并指出是第几个结点。例：如图二叉树的数据文件的数据格式如下:【输入】第一行n为二叉树的结点个树，n≤100；第二行x表示要查找的结点的值；以下第一列数据是各结点的值，第二列数据是左儿子结点编号，第三列数据是右儿子结点编号。【输出】一个数即查找的结点编号。【输入样例】7【输出样例】4【源程序】

0
0
轩爸
发布于 2020-05-14 10:20
阅读 ( 931 )

【题目描述】树的凹入表示法主要用于树的屏幕或打印输出，其表示的基本思想是兄弟间等长，一个结点的长度要不小于其子结点的长度。二叉树也可以这样表示，假设叶结点的长度为1，一个非叶结点的长度等于它的左右子树的长度之和。一棵二叉树的一个结点用一个字母表示（无重复），输出时从根结点开始：每行输出若干个结点字符（相同字符的个数等于该结点长度），如果该结点有左子树就递归输出左子树；如果该结点有右子树就递归输出右

0
1
轩爸
发布于 2020-05-14 10:20
阅读 ( 806 )

信息学奥赛一本通T1364：树与二叉树二叉树遍历

【题目描述】树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序，给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。假定一棵二叉树一个结点用一个字符描述，现在给出中序和按层遍历的字符串，求该树的先序遍历字符串。【输入】两行，每行是由字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的中序遍历和按层遍历的序列。【输出】一行，表示二叉树的先序序列。【输入样例】DBEAC【输出样例】

0
0
轩爸
发布于 2020-05-13 16:20
阅读 ( 1045 )

信息学奥赛一本通T1365：树与二叉树 FBI树

【题目描述】我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：T的根结点为R，其类型与串S的类型相同；若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1

0
0
轩爸
发布于 2020-05-13 16:20
阅读 ( 716 )

信息学奥赛一本通T1363：树与二叉树小球

【题目描述】许多的小球一个一个的从一棵满二叉树上掉下来组成FBT（Full Binary Tree，满二叉树），每一时间，一个正在下降的球第一个访问的是非叶子节点。然后继续下降时，或者走右子树，或者走左子树，直到访问到叶子节点。决定球运动方向的是每个节点的布尔值。最初，所有的节点都是false，当访问到一个节点时，如果这个节点是false，则这个球把它变成true，然后从左子树走，继续它的旅程。如

0
1
轩爸
发布于 2020-05-13 16:20
阅读 ( 1356 )

信息学奥赛一本通T1362：队列家庭问题

【题目描述】有n个人，编号为1,2,……n，另外还知道存在K个关系。一个关.系的表达为二元组（α，β）形式，表示α，β为同一家庭的成员。当n，k和k个关系给出之后，求出其中共有多少个家庭、最大的家庭中有多少人？例如：n＝6，k＝3，三个关系为（1,2），(1,3)，(4,5)此时，6个人组成三个家庭，即：｛1,2,3｝为一个家庭，｛4,5｝为一个家庭，｛6｝单独为一个家庭，第一个家庭的人数为最多。

0
0
轩爸
发布于 2020-05-13 16:20
阅读 ( 1538 )

信息学奥赛一本通T1361：队列产生数

【题目描述】给出一个整数n（n≤2000）和k个变换规则（k≤15）。规则： ① 1个数字可以变换成另1个数字； ② 规则中，右边的数字不能为零。例如：n=234，k=2规则为2 → 5，3 → 6上面的整数234经过变换后可能产生出的整数为（包括原数）234，534，264，564共4种不同的产生数。求经过任意次的变换（0次或多次），能产生出多少个不同的整数。仅要求输出不同整数个数。

0
0
轩爸
发布于 2020-05-13 16:20
阅读 ( 1130 )

信息学奥赛一本通T1360：队列奇怪的电梯

【题目描述】大楼的每一层楼都可以停电梯，而且第i层楼（1≤i≤N）上有一个数字Ki(0≤=Ki≤=N）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki（K1=3,K2=3,……），从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？【

0
0
轩爸
发布于 2020-05-13 10:20
阅读 ( 856 )

信息学奥赛一本通T1359：队列围成面积

【题目描述】编程计算由“*”号围成的下列图形的面积。面积计算方法是统计*号所围成的闭合曲线中水平线和垂直线交点的数目。如下图所示，在10×10的二维数组中，有“*”围住了15个点，因此面积为15。【输入】10×10的图形。【输出】输出面积【输入样例】0 0 0 0 0 0 0 0 0 0【输出样例】15【源程序】

0
0
轩爸
发布于 2020-05-13 10:20
阅读 ( 1294 )

信息学奥赛一本通T1358：栈中缀表达式值

【题目描述】输入一个中缀表达式（由0-9组成的运算数、加+减—乘*除/四种运算符、左右小括号组成。注意“—”也可作为负数的标志，表达式以“@”作为结束符），判断表达式是否合法，如果不合法，请输出“NO”；否则请把表达式转换成后缀形式，再求出后缀表达式的值并输出。【输入】一行为一个以@结束的字符串。【输出】如果表达式不合法，请输出“NO”，要求大写。【输入样例】1+2*8-9【输出样例】8【源程序】

0
0
轩爸
发布于 2020-05-13 10:20
阅读 ( 1246 )

信息学奥赛一本通T1357：栈车厢调度

【题目描述】有一个火车站，铁路如图所示，每辆火车从A驶入，再从B方向驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（n≤1000），分别按照顺序编号为1，2，3，…，n。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨，它就不能再回到车站

0
0
轩爸
发布于 2020-05-13 10:20
阅读 ( 799 )

信息学奥赛一本通T1356：栈计算

【题目描述】小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”，求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法)【输入】共1行，为一个算式。【输出】共1行，就是密码。【输入样例】1+(3+2)*(7^2+6*9)/(2)【输出样例】258【源程序】

0
3
轩爸
发布于 2020-05-13 10:20
阅读 ( 1912 )

信息学奥赛一本通T1355：栈字符串匹配问题

【题目描述】字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是<>,(),[],{}，例如。输入: [()] 输出:YES，而输入([])，([)]都应该输出NO。【输入】第一行为一个整数n，表示以下有多少个由括好组成的字符串。接下来的n行，每行都是一个由括号组成的长度不超过255的字符串。【输出】在输出文件

0
0
轩爸
发布于 2020-05-12 16:20
阅读 ( 1237 )

信息学奥赛一本通T1354：栈括弧匹配检验

【题目描述】假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如 ([]()) 或 [([][])] 等为正确的匹配，[(]) 或([]() 或 (()) 均为错误的匹配。【输入】输入仅一行字符（字符个数小于255）。【输出】匹配就输出 “OK” ，不匹配就输出“Wrong”。【输入样例】[(])【输出样例】Wrong【源程序】

0
0
轩爸
发布于 2020-05-12 16:20
阅读 ( 841 )

信息学奥赛一本通T1353：栈表达式括号匹配

【题目描述】假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。表达式长度小于255，左圆括号少于20个。【输入】一行数据，即表达式。【输出】一行，即“YES” 或“NO”。【输入样例】2*(x+y)/(1-x)@【输出样例】YES【源程序】

0
0
轩爸
发布于 2020-05-12 16:20
阅读 ( 1216 )

信息学奥赛一本通T1352：拓扑排序与关键路径奖金

【题目描述】由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元

0
0
轩爸
发布于 2020-05-12 16:20
阅读 ( 1066 )

信息学奥赛一本通T1351：最小生成树家谱树

【题目描述】有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的孩子的信息。输出一个序列，使得每个人的后辈都比那个人后列出。【输入】第1行一个整数N（1≤N≤100），表示家族的人数；接下来N行，第I行描述第I个人的儿子；每行最后是0表示描述完毕。【输出】输出一个序列，使得每个人的后辈都比那个人后列出；如果有多解输出任意一解。【输入样例】5【输出样例】2 4 5 3 1【源程序】

0
0
轩爸
发布于 2020-05-12 16:20
阅读 ( 969 )

信息学奥赛一本通T1350：最小生成树最短网络

【题目描述】农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000。【输入】第一行：农场的个

0
0
轩爸
发布于 2020-05-12 10:20
阅读 ( 680 )

信息学奥赛一本通T1348：最小生成树城市公交网建设问题

【题目描述】有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少？【输入】n（城市数，1<≤n≤100）e（边数）以下e行，每行3个数i,j,wij，表示在城市i,j之间修建高速公路的造价。【输

0
0
轩爸
发布于 2020-05-12 10:20
阅读 ( 948 )

信息学奥赛一本通T1349：最小生成树最优布线问题

【题目描述】学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。现在由你负责连接这些计算机，任务是

0
0
轩爸
发布于 2020-05-12 10:20
阅读 ( 579 )