信息学奥赛-提高级 题库
对一个大小为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树构建规则,依次插入各字符串,统计节点总数。
对于一个包含n个结点和m条边的有向无环图(DAG),其拓扑排序的结果有多少种可能?
只有1种
最多n种
等于n-m种
以上都不对
拓扑排序是找到n个节点的排列顺序,使图中每一条a指向b的边,在排列中a都出现在b前面。举例n=3、m=0时,任何1-3的排列都符合要求,数量为3!=6种,A、B、C选项均不符合。
如果一棵二叉搜索树的后序遍历序列是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。
一个0-1背包问题,背包容量为20,现有5个物品,重量和价值分别为7,5,4,3,6和15,12,9,7,13,装入背包的物品能获得的最大总价值是多少?
0-1背包中物品要么选要么不选,分类讨论:
装5个物品:总重量25>20,不合法;
装4个物品:移走一个物品使总价值最大,选重量3、4、6、7的物品,价值和7+9+13+15=44;
装3个物品:价值最大的3个物品价值和40<44。
在一棵以结点1为根的树中,结点12和结点18的最近公共祖先(LCA)是结点4,下列哪个结点的LCA组合是不可能出现的?
因树以1为根,1是所有节点的祖先,LCA(12,1)应为1,而非4。
在一个初始为空的最小堆(min-heap)中,依次插入元素20,12,15,8,10,5,然后连续执行两次“删除最小值”(delete-min)操作,此时堆顶元素是什么?
最小堆堆顶是最小值:
插入后堆为[5,8,12,20,10,15];
第一次删最小值5,堆调整为[8,10,12,20,15];
第二次删最小值8,堆调整为[10,15,12,20],堆顶为10。
1到1000之间,不能被2、3、5中任意一个数整除的整数有多少个?
设全集U(1-1000),集合X(2的倍数)、Y(3的倍数)、Z(5的倍数):
|U|=1000,|X|=500,|Y|=333,|Z|=200;
|X∩Y|=166,|X∩Z|=100,|Y∩Z|=66,|X∩Y∩Z|=33;
用容斥原理:1000-500-333-200+166+100+66-33=266。
有5个独立的、不可抢占的任务A1,A2,A3,A4,A5需在一台机器上执行(从时间0开始),每个任务有处理时长和截止时刻(原文部分数据表述可能存在排版问题),为使总惩罚最小,应选择哪个任务作为第一个执行任务?
举例“25 9 10 15”方案中,A3作为开头可使总惩罚为0,其他任务开头可能无法实现。
如果因为某些问题,导致程序运行第25行的dfs函数之前,数组p的初值并不全为0,则对程序的影响是?
假如删去第14行的“if (flag[i]) continue;”,输入3,得到的输出答案是?
函数guess2在运行过程中,最多使用的猜测次数的量级为?
O(√n)
O(logn)
当输入的n=100的时候,代码中t=1和t=2分别需要的猜测次数最多分别为?
本题所求出的是?
满足a,b,c∈[1,m]的整数方程a3 +b2=c2的解的数量
满足a,b,c∈[1,m]的整数方程a2 +b2=c2的解的数量
满足x∈[0,m]的整数方程Σk_i・x_i^p_i=0的解的数量
满足x∈[1,m]的整数方程Σk_i・x_i^p_i=0的解的数量