首页 › 题库 › 信息学奥赛 › 1.2 图

信息学奥赛-提高级 题库

共 117 道题 ,第 1 / 6 页 · 按题型筛选,点「查看答案」核对解析
1 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 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选项均不符合。

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

假设一个包含n个顶点的无向图,且该图是欧拉图。以下关于该图的描述中哪项不一定正确?( )

A
所有顶点的度数均为偶数
B
该图联通
C
该图存在一个欧拉回路
D
该图的边数是奇数
答案与解析
正确答案:D

通过图G的每条边一次且仅一次的回路称为欧拉回路。存在欧拉回路的图,称为欧拉图。很容易构造一个偶数条边的欧拉图

题目详情
3 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 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

题目详情
4 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 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)

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

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

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

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

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

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


A

完全三叉树

B

平面图

C

边双连通图

D

欧拉图

答案与解析
正确答案:A

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

题目详情
7 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 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”。

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

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

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

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

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

如图是一张包含6个顶点的有向图,但顶点间不存在拓扑序。如果要删除其中一条边,使这6个顶点能进行拓扑排序,请问总共有多少条边可以作为候选的被删除边?

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

拓扑排序的前提条件是有向无环图,图中存在一个1→3→4→1的环,删除环上任意一条边就可以了。

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

强连通图的性质不包括( ):

A
每个顶点的度数至少为 1
B
任意两个顶点之间都有边相连
C
任意两个顶点之间都有路径相连
D
每个顶点至少都连有一条边
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
11 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

每个顶点度数均为 2 的无向图称为“2 正规图”。由编号为从 1 到 n 的顶点构成的所有 2 正规图,其中包含欧拉回路的不同 2 正规图的数量为( )

A
n!
B
(n-1)!
C
n!/2
D
(n-1)!/2
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
12 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

G 是一个非连通简单无向图(没有自环和重边),共有 36 条边,则该图至少有( )个点。

A
8
B
9
C
10
D
11
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
13 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

设一个三位数a, b, c 均为 1~9 之间的整数,若以 a、 b、 c 作为三角形的三条边可以构成等腰三角形(包括等边),则这样的 n 有( )个。

A
81
B
120
C
165
D
216
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
14 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

现有一段8分钟的视频文件,它的播放速度是每秒24帧图像,每帧图像是 一幅分辨率为2048x1024像素的32位真彩色图像。请问要存储这段原始无 压缩视频.需要多大的存储空间?()。

A
30G
B
90G
C
150G
D
450G
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
15 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

二分图是指能将顶点划分成两个部分,每一部分内的顶点间没有边相连的简单无向图。那么,24个顶点的二分图至多有()条边。

A
144
B
100
C
48
D
122
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
16 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

广度优先搜索时,一定需要用到的数据结构是()

A
栈
B
二叉树
C
队列
D
哈希表
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
17 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

(2.5分)若输入的第一个字符串长度由100个不同的字符构成,第二 个字符串是第一个字符串的倒序,输入的m为0,则输岀为()。

A
49
B
50
C
100
D
-1
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
18 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

(4分)若两个字符串的长度均为n, 且0<m<n-1,且两个字符串的构 成相同(即任何一个字符在两个字符串中出现的次数均相同),则下列 说法正确的是()。提示:考虑输入与输出有多少对字符前后顺序不 一样。

A
若n、m均为奇数,则输出可能小于0
B
若n、m均为偶数,则输出可能小于 0
C
若n为奇数、m为偶数,则输出可能小于0
D
若n为偶数、m为奇敎.则输出可能小于0
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
19 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

下列属于图像文件格式的有( )

A
WMV
B
MPEG
C
JPEG
D
AVI
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
20 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

G是一个非连通无向图(没有重边和自环),共有28条边,则该图至少有( )个顶点

A
10
B
9
C
11
D
8
答案与解析
正确答案:B
这道题暂未补解析。
题目详情