首页 › 题库 › 信息学奥赛 › 8 算法复杂度与优化

信息学奥赛-提高级 题库

共 68 道题 ,第 2 / 4 页 · 按题型筛选,点「查看答案」核对解析
章节 8 算法复杂度与优化 清除
21 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

(2.5分)若输入的d[i]都为同一个数,此程序平均的时间复杂度是()

A
0(n)
B
0(log n)
C
0(n log n)
D
0(n^2)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
22 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

(3分)若输入的a数组是一个严格单调递增的数列,此程序的时间复杂度是( )。

A
0(log n)
B
0(n2)
C
0(nlog n)
D
0(n)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
23 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

最坏情况下,此程序的时间复杂度是( )。

A
0(n2)
B
0(log n)
C
0(n)
D
0(nlog n)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
24 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

此程序的时间复杂度是( )

A
O(n)
B
O(log n)
C
O(n^2)
D
O(n log n)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
25 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

设某算法的时间复杂度函数的递推方程是T(n) = T(n - 1) + n(n 为正整数)及T(0) = 1,则该算法的时间复杂度为( )。

A

O(log n)

B

O(n log n)

C

O(n)

D

O(n2)

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
26 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

若某算法的计算时间表示为递推关系式:

T(N)=,2T(N/2)+N log N

T(1)=1

则该算法的时间复杂度为( )。

A

p(N)

B

O(Nlog N)

C

O(Nlog2N)

D

O(N2)

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
27 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

假设某算法的计算时间表示为递推关系式

则算法的时间复杂度为( )。

A
O(n)
B
C
D
O(n2)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
28 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

设某算法的计算时间表示为递推关系式 T(n) = T(n - 1) + n(n 为正整数)及 T(0) = 1,则该算法的时间复杂度为( )。

A
O(log n)
B
O(n log n)
C
O(n)
D
O(n2)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
29 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

具有n个顶点,e条边的图采用邻接表存储结构,进行深度优先遍历和广度优先遍历运算的时间复杂度均为( )。

A
Θ(n2)
B
Θ(e2)
C
Θ(ne)
D
Θ(n + e)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
30 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

以下时间复杂度不是O(n2)的排序方法是( )。

A
插入排序
B
归并排序
C
冒泡排序
D
选择排序
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
31 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

斐波那契数列的定义如下:F1=1,F2=1,Fn=Fn–1+Fn–2(n≥3)。如果用下面的函数计算斐波那契数列的第 n 项,则其时间复杂度为( )。

int F(int n)

{

if(n<=2)

return 1;

else

return F(n-1)+F(n-2);

}

A
O(1)
B
O(n)
C
O(n2)
D
O(Fn)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
32 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

对一个 n 个顶点、m 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时,如果不使用堆或其它优先队列进行优化,则其时间复杂度为( )。

A
O(mn+n3)
B
O(n2)
C
O((m+n)log n)
D
O((m+n2)log n)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
33 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

在使用高级语言编写程序时,一般提到的“空间复杂度”中的空间是指( )。

A
程序运行时理论上所占的内存空间
B
程序运行时理论上所占的数组空间
C
程序运行时理论上所占的硬盘空间
D
程序源文件理论上所占的硬盘空间
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
34 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

应用快速排序的分治思想,可以实现一个求第 K 大数的程序。假定不考虑极端的最坏情况,理论上可以实现的最低的算法时间复杂度为( )。

A
O (n2)
B
O (n log n )
C
O (n)
D
O (1)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
35 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

具有n个顶点,e条边的图釆用邻接表存储结构,进行深度优先遍历运算的 时间复杂度为()

A
0(n+e)
B
0(n^2)
C
0(e^2)
D
0(n)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
36 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

对一个n个顶点、m条边的带权有向简単图用Dijkstra算法计算単源最短 路时,如果不使用堆或其它优先队列进行优化,则其时间复杂度为()。

A
0((m + n^2) log n)
B
0(mn + n^3)
C
0((m + n) log n)
D
0(n^2)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
37 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

(2.5分)若输入的d[i]为i,此程序①平均的时间复杂度和②最坏 情况下的时间复杂度分别是()

A
0(n), 0(n^2)
B
0(n), 0(n log n)
C
0(n log n), 0(n^2)
D
0(n log n), 0(n log n)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
38 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

(2.5分)若输入的d[i]都为同一个数,此程序平均的时间复杂度是()

A
0(n)
B
0(log n)
C
0(n log n)
D
0(n^2)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
39 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

考虑对 n 个数进行排序,以下最坏时间复杂度低于 O(n^2)的排序方法是( )。

A
插入排序
B
冒泡排序
C
归并排序
D
快速排序
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
40 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

对于给定的 n,分析以下代码段对应的时间复杂度,其中最为准确的时间复杂度为( )。

int i, j, k = 0; 

for (i = 0; i < n; i++) { 

for (j = 0; j < n; j*=2) { 

k = k + n / 2; 

} 

}

A
O(n)
B
O(n log n)
C
O(n√n)
D
O(n2)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情