信息学奥赛-提高级 题库
对一个大小为16(下标0-15)的数组构建满线段树,查询区间[3,11]时,最少需要访问多少个树结点(包括路径上的父结点和完全包含在查询区间内的结点)?
满线段树结构为:
[0,15]分为[0,7]和[8,15];
[0,7]分为[0,3]和[4,7];
[8,15]分为[8,11]和[12,15];
[0,3]分为[0,1]和[2,3]。
查询[3,11]时,需访问[0,15]、[0,7]、[8,15]、[0,3]、[4,7]、[8,11]、[2,3]、[3,3],共8个节点。
将字符串“cat”“car”“cart”“case”“dog”“do”插入一个空的Trie树(前缀树)中,构建完成的Trie树(包括根节点)共有多少个结点?
按Trie树构建规则,依次插入各字符串,统计节点总数。
如果一棵二叉搜索树的后序遍历序列是2,5,4,8,12,10,6,那么该树的前序遍历是什么?
二叉搜索树性质为“树根左子树点权≤树根点权,右子树点权≥树根点权,且左右子树也为二叉搜索树”。
后序遍历最后一个数为根节点6;
左子树节点为2、5、4,根为4(左子树2,右子树5);
右子树节点为8、12、10,根为10(左子树8,右子树12);
前序遍历为6,4,2,5,10,8,12。
在一棵以结点1为根的树中,结点12和结点18的最近公共祖先(LCA)是结点4,下列哪个结点的LCA组合是不可能出现的?
因树以1为根,1是所有节点的祖先,LCA(12,1)应为1,而非4。
假设有一颗h层的完全二叉树,该树最多包含( )个节点?
第一层1,第二层2,第h层2h-1,加起来2h-1
在图论中,树的重心是树上的一个结点,以该结点为根时,使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心?( )
考虑一条链的情况下,如果树的结点是偶数个数,那么中间的两个点都可以是重心,所以必须是奇数个结点的树。
一个深度为 5(根结点深度为 1)的完全 3 叉树,按前序遍历的顺序给结点从 1 开始编号,则第 100 号结点的父结点是第( )号。
前序遍历和中序遍历相同的二叉树为且仅为( )。
设根节点深度为0,一棵深度为h的满k(k>1)叉树,即除最后一层无任何子节点外,每一层上的所有结点都有k个子结点的树,共有( )个结点。
设G是有n个结点、m条边(n≤m)的连通图,必须删去G的( )条边,才能使得G变成一棵树。
一棵二叉树如右图所示,若采用二叉树链表存储该二叉树(各个结点包括结点的数据、左孩子指针、右孩子指针)。如果没有左孩子或者右孩子,则对应的为空指针。那么该链表中空指针的数目为( )。

14
前序遍历序列与后序遍历序列相同的二叉树为( )。
已知一棵二叉树有2013个节点,则其中至多有( )个节点有2个子节点。
二叉查找树具有如下性质:每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。那么,二叉查找树的( )是一个有序序列。
一个深度为 5(根结点深度为 1)的完全 3 叉树,按前序遍历的顺序给结点从 1 开始编号,则第 100 号结点的父结点是第( )号。
