首页 › 题库 › 信息学奥赛 › 3.1 一维数组

信息学奥赛-入门级 题库

共 65 道题 ,第 1 / 4 页 · 按题型筛选,点「查看答案」核对解析
章节 3.1 一维数组 清除
1 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

假设输入的a数组和k均为正整数,执行第18行代码时,一定满足的条件不包括()。

A
j<=i
B
a[i]-ai]>k
C
j<=n
D
a[i]<a[i]
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
2 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

假设输入的a数组和k均为正整数,但a数组不一定有序,若误删去第13行的"std::sort(a+1,a+n+1);",程序有可能出现的问题有()。

A
输出的答案比原本答案更大
B
输出的答案比原本答案更小
C
出现死循环行为
D
以上均可能发生
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
3 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

如果输入的a={1,2,…,n},而且b数组中数字均为1~n中的正整数,则上述代码等价于下面哪个问题:()。

A
求b数组去重后的长度
B
求b数组的最长上升子序列
C
求b数组的长度
D
求b数组的最大值
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
4 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

以下哪个序列对应数组 0 至 8 的 4 位二进制格雷码(Gray code)?

A
0000,0001,0011,0010,0110,0111,0101,1000
B
0000,0001,0011,0010,0110,0111,0100,0101
C
0000,0001,0011,0010,0100,0101,0111,0110
D
0000,0001,0011,0010,0110,0111,0101,0100
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
5 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

当输入的 cost 数组为{1,100,1,1,1,100,1,1,100,1}时,程序的输出为( )。

A
“6”
B
“7”
C
“8”
D
”9”
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
6 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

如果输入的 cost 数组为{10,15,30,5,5,10,20},程序的输出为( )

A
"25"
B
"30"
C
"35"
D
"40"
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
7 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

若将代码中的 min(dp[i-1],dp[i-2])+cost[i-1]修改为 dp[i-1]+cost[i-2],输入 cost 数组为{5,10,15}时,程序的输出为( )

A
"10"
B
"15"
C
"20"
D
"25"
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
8 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

考虑一个有向无环图,该图包括4条有向边:(1,2),(1,3),(2,4),和(3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序?( )

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

访问2,3之前要先访问1,访问4之前要先访问3或4,所以一个有效的拓扑序列为:1,2,3,4。

题目详情
9 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

链表和数组的区别包括( )。

A
数组不能排序,链表可以
B
链表比数组能存储更多的信息
C
数组大小固定,链表大小可动态调整
D
以上均正确
答案与解析
正确答案:C

这个题其实不太严谨,但C相比其他更正确。

题目详情
10 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

一棵有 n 个结点的完全二叉树用数组进行存储与表示,已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点,则它的兄弟结点和右子结点的位置分别是( )。

A
8,18
B
10,18
C
8,19
D
10,19
答案与解析
正确答案:C

考察完全二叉树的线性数组表示法。根节点i的左右孩子分别是2i和2i+1。也可以直接画出二叉树观察。

题目详情
11 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

以下排序算法的常见实现中,哪个选项的说法是错误的:( )。

A
冒泡排序算法是稳定的
B
简单选择排序是稳定的
C
简单插入排序是稳定的
D
归并排序算法是稳定的
答案与解析
正确答案:B

考察排序的稳定性。选择排序是不稳定的,冒泡、插入、归并都是稳定的。

题目详情
12 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

一棵二叉树如右图所示,若釆用顺序存储结构,即用一维数组元素存储该二叉 树中的结点(根结点的下标为1,若某结点的下标为i,则其左孩子位于下标2i 处,右孩子位于下标2i+l处),则该数组的最大下标至少为?

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

堆式编号,最大值是最深的那层最靠右侧的节点, 编号为((1*2+1)*2+1)*2+1=15

题目详情
13 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

当n=10时,若b数组满足,对任意0<=i<n,都有b [i]=i + 1,那么输出最 大为()。

A
386
B
383
C
384
D
385
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
14 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

当n二100时,若b数组满足,对任意0 S i < 71,都有b [i]二1,那 么输出最小为()。

A
582
B
580
C
579
D
581
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
15 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

以下排序算法中,不需要进行关键字比较操作的算法是( )。

A
基数排序
B
冒泡排序
C
堆排序
D
直接插入排序
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
16 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

给定一个含N个不相同数字的数组,在最坏情况下,找出其中最大或最小的 数,至少需要N - 1次比较操作。则最坏情况下,在该数组中同时找最大与  最小的数至少需要( )次比较操作。(⌈ ⌉表示向上取整, ⌊ ⌋表示向下取整)

A
⌈3N / 2⌉ - 2
B
⌊3N / 2⌋ - 2
C
2N - 2
D
2N - 4
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
17 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

设 A 和 B 是两个长为 n 的有序数组,现在需要将 A 和 B 合并成一个排好序 的数组,任何以元素比较作为基本运算的归并算法在最坏情况下至少要做  ( ) 次比较。

A
n2
B
n log n
C
2n
D
2n-1
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
18 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

一棵二叉树如右图所示,若采用顺序存储结构,即用一维数组元素存储该二叉树中的结点(根结点的下标为1 ,若某结点的下标为i ,则其左孩子位于下标2i 处、右孩子位于下标(2i+1)处) ,则图中所有结点的最大下标为  ( ) 。

A
6
B
10
C
12
D
15
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
19 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

给定含有n个不同的数的数组L=<x1,x2, ...,xn>。如果 L 中存在xi(1<i<n) 使得 x1<x2< ... <xi-1<xi>xi+1>... >xn, 则称L是单峰的,并称xi 是L的“峰顶”。现在已知 L 是单峰的,请把a-c 三行代码补全到算法中使得算法 正确找到L的峰顶。

 Search(k+1, n)

 Search(1, k-1)

 return L[k]


Search(1, n)

1. k←⌊n/2⌋

2. if L[k] > L[k-1] and L[k] > L[k+1]

3. then

4. else if L[k] > L[k-1] and L[k] < L[k+1]

5. then

6. else

正确的填空顺序是( )。

A
c, a, b
B
c, b, a
C
a, b, c
D
b, a, c
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
20 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

( )的平均时间复杂度为 O(nlog n),其中 n 是待排序的元素个数。

A
快速排序
B
插入排序
C
冒泡排序
D
基数排序
答案与解析
正确答案:A
这道题暂未补解析。
题目详情