当前位置:首页 >> 学科竞赛 >> NOIP树习题汇总

NOIP树习题汇总


? 1、小球(DROP) 【问题描述】 许多的小球一个一个的从一棵满二叉树上掉下来组成 FBT(Full Binary Tree,满二 叉树) ,每一时间,一个正在下降的球第一个访问的是非叶子节点。然后继续下降时,或者 走右子树,或者走左子树,直到访问到叶子节点。决定球运动方向的是每个节点的布尔值。 最初,所有的节点都是 FALSE,当访问到一个节点时,如果这个节点是 FALSE

,则这个球 把它变成 TRUE,然后从左子树走,继续它的旅程。如果节点是 TRUE,则球也会改变它为 FALSE,而接下来从右子树走。满二叉树的标记方法如下图。

因为所有的节点最初为 FALSE,所以第一个球将会访问节点 1,节点 2 和节点 4,转变节点 的布尔值后在在节点 8 停止。第二个球将会访问节点 1、3、6,在节点 12 停止。明显地,第 三个球在它停止之前,会访问节点 1、2、5,在节点 10 停止。 现在你的任务是,给定 FBT 的深度 D,和 I,表示第 I 个小球下落,你可以假定 I 不超 过给定的 FBT 的叶子数,写一个程序求小球停止时的叶子序号。 【输入格式】 输 入 文 件 仅 一 行 包 含 两 个 用 空 格 隔 开 的 整 数 D 和 I 。 其 中 2<=D<=20 , 1<=I<=524288。 【输出格式】 对应输出第 I 个小球下落停止时的叶子序号。 【输入样例】DROP.IN 42 【输出样例】DROP.OUT 12

? 2、二叉树遍历(flist) 【问题描述】 树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序,给定中序和其它一种 遍历的序列就可以确定一棵二叉树的结构。 假定一棵二叉树一个结点用一个字符描述, 现在给出中序和按层遍历的字符串, 求该树 的先序遍历字符串。 【输入格式】 输入文件 flist.in 共两行,每行是由字母组成的字符串(一行的每个字符都是唯一的) , 分别表示二叉树的中序遍历和按层遍历的序列。 【输出格式】 输出文件 flist.out 就一行,表示二叉树的先序序列。 【输入样例】flist.in

DBEAC ABCDE

? 3、FBI 树(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 构造 R 的左子树 T1,由右子串 S2 构造 R 的右子树 T2。 现在给定一个长度为 2N 的“01”串,请用上述构造方法构造出一棵 FBI 树,并输 出它的后序遍历[ 后序遍历: 后序遍历是深度优先遍历二叉树的一种方法, 它的递归定义是: 先后序遍历左子树,再后序遍历右子树,最后访问根。]序列。 【输入文件】 输入文件 fbi.in 的第一行是一个整数 N(0 <= N <= 10) ,第二行是一个长度为 2N 的“01”串。 【输出文件】 输出文件 fbi.out 包括一行,这一行只包含 一个字符串,即 FBI 树的后序遍历序列。 【样例输入】fbi.in 3 10001011 【样例输出】fbi.out IBFBBBFIBFIIIFF 【数据规模】 对于 40%的数据,N <= 2; 对于全部的数据,N <= 10。

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

如果该结点有右子树就递归输出右子树。 假定一棵二叉树一个结点用一个字符描述, 现在给出先序和中序遍历的字符串, 用 树的凹入表示法输出该二叉树。 【输入格式】 输入文件 btout.in 共两行,每行是由字母组成的字符串(一行的每个字符都是唯一 的) ,分别表示二叉树的先序遍历和中序遍历的序列。 【输出格式】 输出文件 btout.out 的行数等于该树的结点数,每行的字母相同。 【输入样例】btout.in ABCDEFG CBDAFEG 【输出样例】btout.out AAAA BB C D EE F G

5、查找二叉树 【问题描述】 已知一棵二叉树用邻接表结构存储, 中序查找二叉树中值为 x 的结点, 并指出是第几个 结点。例:如图二叉树的数据文件的数据格式如下 7 15 523 12 4 5 10 0 0 29 0 0 15 6 7 800 23 0 0 第一行 n 为二叉树的结点个树,n<=100;第二行 x 表示要查找的结点的值;以下第一列数 据是各结点的值,第二列数据是左儿子结点编号,第三列数据是右儿子结点编号。 输出一个数即查找的结点编号。 本例的输出样例: 4

6、对称二叉树

【问题描述】 如果二叉树的左右子树的结构是对称的,即两棵子树皆为空,或者皆不空,则称该 二叉树是对称的。编程判断给定的二叉树是否对称. 例:如下图中的二叉树 T1 是对称的,T2 是不对称的。 二叉树用顺序结构给出,若读到#则为空,二叉树 T1=ABCDE,T2=ABCD#E,如果二叉树 是对称的,输出“Yes”,反之输出“No” 。 【输入样例】tree_c.in ABCDE 【输出样例】tree_c.out Yes

7、 单词查找树 【问题描述】 在进行文法分析的时候, 通常需要检测一个单词是否在我们的单词列表里。 为了提 高查找和定位的速度,通常都画出与单词列表所对应的单词查找树,其特点如下: 1.根结点不包含字母,除根结点外每一个结点都仅包含一个大写英文字母; 2.从根结点到某一结点,路径上经过的字母依次连起来所构成的字母序列,称为该结 点对应的单词。单词列表中的每个单词,都是该单词查找树某个结点所对应的单词; 3.在满足上述条件下,该单词查找树的结点数最少。 4.例如图左边的单词列表就对应于右边的单词查找树。注意,对一个确定的单词列表, 请统计对应的单词查找树的结点数(包含根结点) 。 【问题输入】 输入文件名为 word.in,该文件为一个单词列表,每一行仅包含一个单词和一个换行/回 车符。 每个单词仅由大写的英文字母组成, 长度不超过 63 个字母 。 文件总长度不超过 32K, 至少有一行数据。 【问题输出】 输出文件名为 word.out,该文件中仅包含一个整数,该整数为单词列表对应的单词查找 树的结点数。 【样例输入】 A AN ASP AS ASC ASCII BAS BASIC 【样例输出】 13

8、医院设置 【问题描述】 设有一棵二叉树(如图 3-8,其中圈中的数字表示结点中居民的人口,圈边上数字 表示结点编号。现在要求在某个结点上建立一个医院,使所有居民所走的路程之和为最小, 同时约定,相邻结点之间的距离为 1。就本图而言,若医院建在 1 处,则距离和 =4+12+2*20+2*40=136;若医院建在 3 处,则距离和=4*2+13+20+40=81?? 【输入格式】 输入文件名为 hospital.in,其中第一行一个整数 n,表示树的结点数(n<=100) 。接 下来的 n 行每行描述了一个结点的状况,包含三个整数,整数之间用空格(一个或多个)分 隔,其中:第一个数为居民人口数;第二个数为左链接,为 0 表示无链接;第三个数为右链 接,为 0 表示无链接。 【输出格式】 输出文件名为 hospital.out,该文件只有一个整数,表示最小距离和。 【样例输入】 1 13 5 2 13 2 3 3 4 12 400 12 4 5 5 4 20 0 0 20 40 40 0 0 【样例输出】 81

9、求后序遍历 【问题描述】 输入一棵二叉树的先序和中序遍历序列,输出其后序遍历序列。 【输入格式】 输入文件为 tree.in,共两行,第一行一个字符串,表示树的先序遍 历,第二行一个字符串,表示树的中序遍历。树的结点一律用小写 字母表示。 【输出格式】 输出文件为 tree.out,仅一行,表示树的后序遍历序列。 【样例输入】 abdec dbeac 【样例输出】 debca

10、扩展二叉树 【问题描述】

由于先序、 中序和后序序列中的任一个都不能唯一确定一棵二叉树, 所以对二叉树做如 下处理,将二叉树的空结点用·补齐,如图所示。我们把这样处理后的二叉树称为原二叉树 的扩展二叉树,扩展二叉树的先序和后序序列能唯一确定其二叉树。 现给出扩展二叉树的先序序列,要求输出其中序和后序序列。 【输入样例】tree_b.in ABD..EF..G..C.. 【输出样例】tree_b.out DBFEGAC DFGEBCA


更多相关文档:

树图例题

树图例题_其它_高等教育_教育专区。NOIP,树图例题1.FBI 树 【题目描述】 我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为 B 串,全“1”串...

第二讲:树及其应用练习题目

第二讲:树及其应用练习题目 NOIP&ACMNOIP&ACM隐藏>> [最优分解方案] 将一个正整数 n 分解成若干个互不相等的正整数的和,使得这些数的成绩最大。 输入:n(1...

NOIP试题集锦

NOIP试题集锦_IT认证_资格考试/认证_教育专区。NOIP试题集锦2013 年 10 月 16...个城市用 n-1 条双向道路相互连通构成一棵树,1 号城 市是首都,也是树中的...

pascal-noip历届精选试题

pascal-noip历届精选试题_电脑基础知识_IT/计算机_专业资料。04-12 年历届必须...的试题 0000000 【样例输出 2】 28 第2题 FBI 树 2004 年试题第 3 题 ...

NOIP《 数据结构》练习题及答案

NOIP《 数据结构》练习题及答案_学科竞赛_初中教育_教育专区。NOIP 数据结构复习...若知道一棵树中,度为 2 的节点 2 个,度为 3 的节点有 1 个,度为 4 ...

NOIP2015提高组解题报告

NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你幻方的构造方法,给...简单的方法是树链剖分,这样的时间复杂度是 O(mlg^3n)的, 理论上可以通过 ...

noip初赛试题1

(NOIP2005) A. 4 B.3 C.5 【答案】E。用上题的结论。 D. 2 E. 6 5. 高度为 n 的均衡的二叉树是指:如果去掉叶结点及相应的树枝,它应该是高度为 ...

试题(树型动规)

试题(树型动规)_理学_高等教育_教育专区。树型动规树型动规专题 1.加分二叉树(binary.c/cpp) NOIP2003 提高组第 3 组【问题描述】 设一个 n 个节点的二...

树的遍历

关键词:noip信息学竞赛 1/2 相关文档推荐 遍历树 4页 免费 遍历树 3页 2财富...输入样例 5 5 7 1 2 10 输出样例 145 31245 一、题意分析 1、在中序...

NOIP普及组试题精选

NOIP普及组试题精选_从业资格考试_资格考试/认证_教育专区。NOIP 普及组(初赛)试题...(数字为节点的编号,下同), 中根遍历 2 4 1 5 7 3 6,则该二叉树的后...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com