首页 › 题库 › 信息学奥赛 › 1 数据结构进阶

信息学奥赛-提高级 题库

共 682 道题 ,第 3 / 35 页 · 按题型筛选,点「查看答案」核对解析
章节 1 数据结构进阶 清除
41 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

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

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

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

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

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

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

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

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

①处应填()

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

②处应填()

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

③处应填()

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

④处应填()

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

处应填()

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

⑤处应填()

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

在Linux系统终端中,以下哪个命令用于创建一个新的目录?

A
newdir
B
mkdir
C
create
D
mkfold
答案与解析
正确答案:B

考察基本的Linux命令,mk是make的缩写,dir是Directory file(目录文件)的缩写。

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

0,1,2,3,4中选取4个数字,能组成(  )个不同四位数。(注:最小的四位数是1000最大的四位数是9999)

A
96
B
18
C
120
D
84
答案与解析
正确答案:A

因为0不能做最高位,首先从1,2,3,4中选出一个数字做最高位,接下来百位有4种选择,十位有3种选择,个位有2种选择,按照乘法原理4×4×3×2=96。

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

假设有n根柱子,需要按照以下规则依次放置编号为1、2、3、…的圆环:每根柱子的底部固定,顶部可以放入圆环;每次从柱子顶部放入圆环时,需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有4根柱子时,最多可以放置(  )个圆环

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

在4根柱子的时候每个圆环只有一种放置方法,直接模拟就可以得到答案了。

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

以下对数据结构的表述不恰当的一项是:

A
队列是一种先进先出(FIFO)的线性结构
B
哈夫曼树的构造过程主要是为了实现图的深度优先搜索
C
散列表是一种通过散列函数将关键字映射到存储位置的数据结构
D
二叉树是一种每个结点最多有两个子结点的树结构
答案与解析
正确答案:B

哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近,构造过程使用贪心法,与深度优先搜索和图都无关。

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

以下连通无向图中,(  )一定可以用不超过两种颜色进行染色


A

完全三叉树

B

平面图

C

边双连通图

D

欧拉图

答案与解析
正确答案:A

能用两种颜色染色的图必须是二分图,而任何一棵树都可以按照深度划分成二分图。

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

最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下:给定两个序列X={x1,x2,x3,…,xm}和Y={y1,y2,y3,…yn},最长公共子序列(LCS)问题的目标是找到一个最长的新序列Z={z1,Z2,Z3,…,Zk},使得序列Z既是序列X的子序列,又是序列Y的子序列,且序列Z的长度k在满足上述条件的序列里是最大的。(注:序列A是序列B的子序列,当且仅当在保持序列B元素顺序的情况下,从序列B中删除若干个元素,可以使得剩余的元素构成序列A。)则序列“ABCAAAABA”和"ABABCBABA"的最长公共子序列长度为(  )

A
4
B
5
C
6
D
7
答案与解析
正确答案:C

可以使用经典的动态规划算法,可以看出最长公共子序列是“ABAABA”。

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

一位玩家正在玩一个特殊的掷骰子的游戏,游戏要求连续掷两次骰子,收益规则如下:玩家第一次掷出x点,得到2x元;第二次掷出y点,当y=x时玩家会失去之前得到的2x元而当y*x时玩家能保住第一次获得的2x元。上述x,y∈{1,2,3,4,5,6}。例如:玩家第一次掷出3点得到6元后,但第二次再次掷出3点,会失去之前得到的6元,玩家最终收益为0元;如果玩家第一次掷出3点、第二次掷出4点,则最终收益是6元。假设骰了挑出任意一点的概率均为1/6,玩家连续掷两次般子后,所有可能情形下收益的平均值是多少?

A
7元
B

35/6元

C

16/3元

D

19/3元

答案与解析
正确答案:B

可以算出每种收益的出现概率乘以对应的收益:获得2元的概率是1/6×5/6=5/36,获得4元、6元、8元、10元、12元同理,获得0元的概率是1-5/36*6=1/6,所以收益的平均值是:(2+4+6+8+10+12)×5/36=35/6元。

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

假设我们有一下的C++代码:

int a = 5, b = 3, c = 4;

bool res = a &b || c ^ b && a  | c;

请问res的值是什么?()

提示:在C++中,逻辑运算的优先级从高到低依次为:逻辑非(!),逻辑与(&&),逻辑或(||)。位运算的优先级从高到低依次为:位非(~),位与(&),位异或(^),位或(|)。同时,双目位运算的优先级高于双目逻辑运算:逻辑非和位非优先级相同,且高于所有双目运算符。

A
true
B
false
C
1
D
0
答案与解析
正确答案:A

首先把位运算算出来,得到res = 1 || 7 && 5,然后执行逻辑运算(非0的数字在逻辑运算中都视为true)得到true。

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

假设快速排序算法的输入是一个长度为n的已排序数组,且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?

A
快速排序对于此类输入的表现最好,因为数组已经排序。
B
快速排序对于此类输入的时间复杂度是0(nlogn)。
C
快速排序对于此类输入的时间复杂度是0(n2)。
D
快速排序无法对此类数组进行排序,因为数组已经排序。
答案与解析
正确答案:C

如果数组已经排序,并且每次都取第一个元素作为基准元素。那么每次递归时,待排序区间都只会减少一个数,所以深度会达到n层,总复杂度是O(n2)。

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

以下哪个命令,能将一个名为"main.cpp"的C++源文件,编译并生成一个名为"main"的可执行文件?(  )

A
g++-o main main,cpp
B
g++-0 main.cpp main
C
g++  main -o main.cpp
D
g++  main.cpp  -o main.cpp
答案与解析
正确答案:A

基础编译命令,-o后面是需要生成的可执行文件的名字(Linux中可执行文件不需要后缀名),然后接上需要被编译的C++文件名。

题目详情