首页 › 题库 › 信息学奥赛 › 信息学奥赛-提高级

信息学奥赛-提高级 题库

共 842 道题 ,第 1 / 43 页 · 按题型筛选,点「查看答案」核对解析
1 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 5.3 排列组合

有5个红色球和5个蓝色球,除颜色外完全相同,将10个球排成一排,要求任意两个蓝色球都不能相邻,有多少种不同的排列方法?


A

25

B

30

C

6

D

120

答案与解析
正确答案:C

先将所有红色球排成一排,会形成6个空隙,每个空隙最多放一个蓝色球,从6个空隙中选5个放蓝球,方案数为C(6,5)=6。

题目详情
2 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 6.1 KMP

在KMP算法中,对于模式串P='abacaba',其next数组(next[i]定义为模式串P[0...i]最长公共前后缀的长度,且数组下标从0开始)的值是什么?

A
{0,0,1,0,1,2,3}
B
{0,1,2,3,4,5,6}
C
{0,0,1,1,2,2,3}
D
{0,0,0,0,1,2,3}
答案与解析
正确答案:A

next[i]定义为P[0..i]最长公共前后缀(不能是P[0..i]本身,需同时是前缀与后缀)的长度。  

i=0时,P[0..i]为“a”,长度0;  

i=1时,P[0..i]为“ab”,长度0;  

i=2时,P[0..i]为“aba”,长度1;  

i=3时,P[0..i]为“abac”,长度0;  

i=4时,P[0..i]为“abaca”,长度1;  

i=5时,P[0..i]为“abacab”,长度2;  

i=6时,P[0..i]为“abacaba”,长度3。

题目详情
3 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

对一个大小为16(下标0-15)的数组构建满线段树,查询区间[3,11]时,最少需要访问多少个树结点(包括路径上的父结点和完全包含在查询区间内的结点)?

A
7
B
8
C
9
D
10
答案与解析
正确答案:B

满线段树结构为:  

[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个节点。 

题目详情
4 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

将字符串“cat”“car”“cart”“case”“dog”“do”插入一个空的Trie树(前缀树)中,构建完成的Trie树(包括根节点)共有多少个结点?

A
8
B
9
C
10
D
11
答案与解析
正确答案:D

按Trie树构建规则,依次插入各字符串,统计节点总数。

题目详情
5 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

对于一个包含n个结点和m条边的有向无环图(DAG),其拓扑排序的结果有多少种可能? 


A

只有1种

B

最多n种

C

等于n-m种

D

以上都不对

答案与解析
正确答案:D

拓扑排序是找到n个节点的排列顺序,使图中每一条a指向b的边,在排列中a都出现在b前面。举例n=3、m=0时,任何1-3的排列都符合要求,数量为3!=6种,A、B、C选项均不符合。

题目详情
6 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

在一个大小为13的哈希表中,使用闭散列法的线性探查来解决冲突,哈希函数为H(key)=key mod 13,依次插入关键字18、26、35、9、68、74,插入74后,它最终被放置在哪个索引位置? 

A
5
B
7
C
9
D
11
答案与解析
正确答案:D

哈希冲突指key1≠key2但H(key1)=H(key2),计算各关键字哈希值及插入位置:  

18 mod 13=5,插入下标5;  

26 mod 13=0,插入下标0;  

35 mod 13=9,插入下标9;  

9 mod 13=9(冲突),插入下标10;  

68 mod 13=3,插入下标3;  

74 mod 13=9(冲突,9、10均被占),插入下标11。

题目详情
7 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 4.1 最小生成树

一个包含8个顶点的完全图(顶点编号1到8),任意两点之间的边权重等于两顶点编号的差的绝对值,该图的最小生成树总权重是多少?

A
7
B
8
C
9
D
10
答案与解析
正确答案:A

最小生成树是选边构成树且权值和最小。用Kruskal算法,将边权从小到大排序,边权最小的边为(1,2)、(2,3)、(3,4)、(4,5)、(5,6)、(6,7)、(7,8),权值均为1,总和7。

题目详情
8 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

如果一棵二叉搜索树的后序遍历序列是2,5,4,8,12,10,6,那么该树的前序遍历是什么?

A
6,4,2,5,10,8,12
B
6,4,5,2,10,12,8
C
2,4,5,6,8,10,12
D
12,8,10,5,2,4,6
答案与解析
正确答案:A

二叉搜索树性质为“树根左子树点权≤树根点权,右子树点权≥树根点权,且左右子树也为二叉搜索树”。  

后序遍历最后一个数为根节点6;  

左子树节点为2、5、4,根为4(左子树2,右子树5);  

右子树节点为8、12、10,根为10(左子树8,右子树12);  

前序遍历为6,4,2,5,10,8,12。

题目详情
9 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

一个0-1背包问题,背包容量为20,现有5个物品,重量和价值分别为7,5,4,3,6和15,12,9,7,13,装入背包的物品能获得的最大总价值是多少?

A
43
B
41
C
45
D
44
答案与解析
正确答案:D

0-1背包中物品要么选要么不选,分类讨论:  

装5个物品:总重量25>20,不合法;  

装4个物品:移走一个物品使总价值最大,选重量3、4、6、7的物品,价值和7+9+13+15=44;  

装3个物品:价值最大的3个物品价值和40<44。

题目详情
10 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

在一棵以结点1为根的树中,结点12和结点18的最近公共祖先(LCA)是结点4,下列哪个结点的LCA组合是不可能出现的?

A
LCA(12,4)=4
B
LCA(18,4)=4
C
LCA(12,18,4)=4
D
LCA(12,1)=4
答案与解析
正确答案:D

因树以1为根,1是所有节点的祖先,LCA(12,1)应为1,而非4。

题目详情
11 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

递归关系式T(n)=2T(n/2)+O(n²)描述了某个分治算法的时间复杂度,该算法的时间复杂度是多少?

A
O(n)
B
O(nlogn)
C
O(n2)
D
O(n2logn)
答案与解析
正确答案:C

用主定理或递归树法。递归树中:  

第1层总时间复杂度n2;  

第2层2*(n/2)2=n2/2;  

第3层4*(n/4)2=n2/4;  

……总和为n2*(1+1/2+1/4+…)≤2n2,时间复杂度为O(n2)。 

题目详情
12 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.3 堆

在一个初始为空的最小堆(min-heap)中,依次插入元素20,12,15,8,10,5,然后连续执行两次“删除最小值”(delete-min)操作,此时堆顶元素是什么?  

A
10
B
12
C
15
D
20
答案与解析
正确答案:A

最小堆堆顶是最小值:  

插入后堆为[5,8,12,20,10,15];  

第一次删最小值5,堆调整为[8,10,12,20,15];  

第二次删最小值8,堆调整为[10,15,12,20],堆顶为10。

题目详情
13 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

1到1000之间,不能被2、3、5中任意一个数整除的整数有多少个?  

A
266
B
267
C
333
D
734
答案与解析
正确答案:A

设全集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。

题目详情
14 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

斐波那契数列定义为F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2),使用朴素递归方法计算F(n)的时间复杂度是指数级的,而使用动态规划(或迭代)方法的时间复杂度是线性的,造成这种差异的根本原因是?

A
递归函数调用栈开销过大
B
操作系统对递归深度有限制
C
朴素递归中存在大量的重叠子问题未被重复利用
D
动态规划使用了更少的数据存储空间
答案与解析
正确答案:C

朴素递归会重复计算大量重叠子问题(如计算F(5)需算F(4)和F(3),算F(4)又需算F(3)和F(2)),动态规划通过存储子问题结果避免重复计算。

题目详情
15 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

有5个独立的、不可抢占的任务A1,A2,A3,A4,A5需在一台机器上执行(从时间0开始),每个任务有处理时长和截止时刻(原文部分数据表述可能存在排版问题),为使总惩罚最小,应选择哪个任务作为第一个执行任务?  

A
处理时间最短的任务A5
B
截止时间最早的任务A3
C
处理时间最长的任务A4
D
任意一个任务都可以
答案与解析
正确答案:B

举例“25 9 10 15”方案中,A3作为开头可使总惩罚为0,其他任务开头可能无法实现。

题目详情
16 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

当输入的n=4的时候,程序输出的答案为?

A
11
B
12
C
24
D
9
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
17 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

如果因为某些问题,导致程序运行第25行的dfs函数之前,数组p的初值并不全为0,则对程序的影响是?

A
输出的答案比原答案要小
B
无法确定输出的答案
C
程序可能陷入死循环
D
没有影响
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
18 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

假如删去第14行的“if (flag[i]) continue;”,输入3,得到的输出答案是?

A
27
B
3
C
16
D
12
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
19 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

函数guess1在运行过程中,cnt_broken的值最多为?

A
0
B
1
C
2
D
n
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
20 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

函数guess2在运行过程中,最多使用的猜测次数的量级为? 

A
O(n)
B
O(n²)
C

O(√n)

D

O(logn)

答案与解析
正确答案:C
这道题暂未补解析。
题目详情