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

信息学奥赛-提高级 题库

共 842 道题 ,第 3 / 43 页 · 按题型筛选,点「查看答案」核对解析
41 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 5.2 同余与逆元

考虑一个自然数n以及一个模数m,你需要计算n的逆元(即n在模m意义下的乘法逆元)。下列哪种算法最为合适?( )

A
使用暴力方法依次尝试
B
使用扩展欧几里得解法
C
使用快速幂解法
D
使用线性筛法
答案与解析
正确答案:B

如果一个线性同余方程ax≡1(modb),则x称为a mod b的逆元,记作a-1。扩展欧几里德算法找到两个整数x和y满足ax+by=gcd(a, b)。当a和b互质时,即gcd(a,b)=1,这个方程变为ax+by=1。在模b意义下,ax与1在模b时同余,因此x就是a的模b的逆元。快速幂法使用了费马小定理,要求b是一个素数;而扩展欧几里得法只要求gcd(a,b)=1

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

在设计一个哈希表时,为了减少冲突,需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有n个键值对,表的装载因子为α(0<α≤1)。在使用开放地址法解决冲突的过程中,最坏情况下查找一个元素的时间复杂度为( )?

A
O(1)
B
O(log n)
C
O(1/(1-α))
D
O(n)
答案与解析
正确答案:D

开放地址法当计算出来的地址被占用时,用再寻址的方法寻找下一个地址,如果还是占用就接着寻找,直到找到一个空的地址,在最坏情况下可能会遍历所有已经占用的地址

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

假设有一颗h层的完全二叉树,该树最多包含( )个节点?

A
2h−1
B
2(h+1)−1
C
2h
D
2h+1
答案与解析
正确答案:A

第一层1,第二层2,第h层2h-1,加起来2h-1

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

设有一个10个顶点的完全图,每两个顶点之间都有一条边,有多少个长度为4的环( )?

A
120
B
210
C
630
D
5040
答案与解析
正确答案:C

完全图,所以任意找四个点都可以构成长度为4的环,选4个点的方案数是C(10,4)=210。4个点的圆排列4!/4=6;无向图,所以正反方向视为同一种环,6/2=3。210*3=630

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

对于一个整数n,定义f(n)为n的各个位数之和,问使f(f(x))=10的最小自然数x是( )?

A
29
B
199
C
299
D
399
答案与解析
正确答案:B

f(f(29))=f(11)=2,不满足,f(f(199))=f(19)=10,满足

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

设有一个长度为n的01字符串,其中有k个1,每次操作可以交换相邻两个字符。在最坏的情况下将这k个 1移到字符串最右边所需要的交换次数是( )?

A
K
B
K*(k-1)/2
C
(n-k)*k
D
(2n-k-1)*k/2
答案与解析
正确答案:C

最坏的情况是距离目标位置最远,也就是K个1都在最左侧,此时,第K个1移到第n,需要(n-k)步,一共k*(n-k)

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

如图是一张包含7个顶点的有向图。如果要删除一些边,使得从节点1到节点7没有可行路径,且删除的边数最少,请问总共有多少种可行的删除边的集合( )?

A
1
B
2
C
3
D
4
答案与解析
正确答案:D

首先发现至少需要删除两条边。枚举,可以找到四种删除方案,删除②→⑤和④→⑥、删除⑤→⑦和⑥→⑦、删除①→②和④→⑥、删除⑤→⑦和④→⑥

题目详情
48 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 5.3 排列组合

函数int logic(int x,int y)的功能是()?

A
按位与
B
按位或
C
按位异或
D
以上都不是
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
49 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

当输入为“10 100 100”时,输出的第100个数是()?

A

91

B

94

C

95

D

98

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

当n=10且m=10时,有多少种输入使得两行的结果完全一致?()

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

当n≤5时,solve()的最大可能返回值为()?

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

若n=8,m=8,solve和solve2的返回值的最大可能的差值为()?

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

在solve()函数种,h[]的合并顺序可以看作是()

A
二叉树的BFS序
B
二叉树的先序遍历
C
二叉树的中序遍历
D
二叉树的后序遍历
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
54 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

输入“10”,输出的第一行是( )?

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

输入“16”,输出的第二行是()?

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

①处应填()

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

②处应填()

A
a[mid]>ai
B
a[mid]≥ai
C
a[mid]<ai
D
a[mid]≤ai
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
58 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

③处应填()

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

④处应填()

A
a[n-1]+b[n-1]
B
a[n]+b[n]
C
2*maxn
D
maxn37.
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
60 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

处应填()

A
get_rank(mid)<k
B
get_rank(mid)≤k
C
get_rank(mid)>k
D
get_rank(mid)≥k
答案与解析
正确答案:A
这道题暂未补解析。
题目详情