NOIP 2017 提高组初赛试题

第 1 题
从( )年开始,NOIP 竞赛将不再支持 Pascal 语言。
A.2020
B.2021
C.2022
D.2023
正确答案: C
本题共 1.5

第 2 题
在 8 位二进制补码中,10101011 表示的数是十进制下的( )。
A.43
B.-85
C.-43
D.-84
正确答案: B
本题共 1.5

第 3 题
分辨率为 1600×900、16 位色的位图,存储图像信息所需的空间为( )。
A.2812.5KB
B.4218.75KB
C.4320KB
D.2880KB
正确答案: A
本题共 1.5

第 4 题
2017 年 10 月 1 日是星期日,1949 年 10 月 1 日是( )。
A.星期三
B.星期日
C.星期六
D.星期二
正确答案: C
本题共 1.5

第 5 题
设 G 是有 n 个结点、m 条边(n ≤ m)的连通图,必须删去 G 的( )条边, 才能使得 G 变成一棵树。
A.m – n + 1
B.m – n
C.m + n + 1
D.n – m + 1
正确答案: A
本题共 1.5

第 6 题
若某算法的计算时间表示为递推关系式:
T(N) = 2T(N / 2) + N log N
T(1) = 1
则该算法的时间复杂度为( )。
A.O(N)
B.O(N log N)O(NlogN)
C.O(N log^2 N)O(Nlog2N)
D.O(N^2
正确答案: C
本题共 1.5

第 7 题
表达式 a * (b + c) * d 的后缀形式是( )。
A.a b c d * + *
B.a b c + * d *
C.a * b c + * d
D.b + c * a * d
正确答案: B
本题共 1.5

第 8 题
由四个不同的点构成的简单无向连通图的个数是( )。
A.32
B.35
C.38
D.41
正确答案: C
本题共 1.5

第 9 题
将 7 个名额分给 4 个不同的班级,允许有的班级没有名额,有( )种不 同的分配方案。
A.60
B.84
C.96
D.120
正确答案: D
本题共 1.5

第 10 题
若 f[0] = 0, f[1] = 1, f[n + 1] = (f[n] + f[n – 1]) / 2,则随着 i 的增大,f[i]将接近于( )。
A.1/21/2
B.2/32/3
C.(√5 ? 1)/2
D.11
正确答案: B
本题共 1.5

第 11 题
设 A 和 B 是两个长为 n 的有序数组,现在需要将 A 和 B 合并成一个排好序的 数组,请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做 ( )次比较。
A.n^2
B.n log n
C.2n
D.2n-1
正确答案: D
本题共 1.5

第 12 题
在 n(n ≥ 3)枚硬币中有一枚质量不合格的硬币(质量过轻或质量过重),如果只有一架天平可以用来称重且称重的硬币数没有限制,下面是找出这枚不合格的硬币的算法。请把 a-c 三行代码补全到算法中。
a. A ← X ∪ Y
b. A ← Z
c. n ← |A| 算法 Coin(A, n)

正确的填空顺序是( )。
A.b, c, a
B.c, b, a
C.c, a, b
D.a, b, c
正确答案: D
本题共 1.5

第 13 题
有正实数构成的数字三角形排列形式如图所示。第一行的数为 a11;第二行的数从左到右依次为 a21, a22;… 第 n 行的数为 an1, an2, …, ann。从 a11 开始,每一行的数 aij 只有两条边可以分别通向 下一行的两个数 a(i+1)j 和 a(i+1)(j+1)。用动态规划算 法找出一条从 a11 向下通到 an1, an2, …, ann 中某个数的路径,使得该路径上的数之和达到最大。 令 C[i,j]是从 a11 到 aij 的路径上的数的最大和,并且 C[i,0]=C[0,j]=0, 则 C[i,j]=( )。
三角形排列
A.max{C[i-1,j-1], C[i-1,j]} + aij
B.C[i-1,j-1] + C[i-1,j]
C.max{C[i-1,j-1], C[i-1,j]} + 1
D.max{C[i,j-1],C[i-1,j]} + aij
正确答案: A
本题共 1.5

第 14 题
小明要去南美洲旅游,一共乘坐三趟航班才能到达目的地,其中第 1 个航班 准点的概率是 0.9,第 2 个航班准点的概率为 0.8, 第 3 个航班准点的概率为 0.9。如果存在第 i 个(i=1,2)航班晚点,第 i+1 个航班准点,则小明将赶不 上第 i+1 个航班,旅行失败;除了这种情况,其他情况下旅行都能成功。请 问小明此次旅行成功的概率是( )。
A.0.5
B.0.648
C.0.72
D.0.74
正确答案: D
本题共 1.5

第 15 题
欢乐喷球:儿童游乐场有个游戏叫“欢乐喷球”,正方形场地中心能不断喷出彩色乒乓球,以场地中心为圆心还有一 个圆形轨道,轨道上有一列小火车在匀速运动,火车有六节车厢。
假设乒乓球等概率落到正方形场地的每个地点,包括火车车厢。小朋友玩这个游戏时,只能坐在同一个火车车厢里,可以在自己的车厢里捡落在该车厢内的所有乒乓球,每个人每次游戏有三分钟时间,则一个小朋友独自玩一次游戏期望可以得到( )个乒乓球。假设乒乓球喷出的速度为 2 个/秒,每节车厢的面积是整个场地面积的 1/20。
欢乐喷球
A.60
B.108
C.18
D.20
正确答案: C
本题共 1.5

第 16 题
以下排序算法在最坏情况下时间复杂度最优的有( )。
A.冒泡排序
B.快速排序
C.归并排序
D.堆排
正确答案: CD
本题共 1.5

第 17 题
对于入栈顺序为 a, b, c, d, e, f, g 的序列,下列( )不可能是合法的出栈序 列。
A.a, b, c, d, e, f, g
B.a, d, c, b, e, g, f
C.a, d, b, c, g, f, e
D.g, f, e, d, c, b, a
正确答案: C
本题共 1.5

第 18 题
下列算法中,( )是稳定的排序算法。
A.快速排序
B.堆排序
C.希尔排序
D.插入排序
正确答案: D
本题共 1.5

第 19 题
以下是面向对象的高级语言的有( )。
A.汇编语言
B.C++
C.Fortran
D.Java
正确答案: BD
本题共 1.5

第 20 题
以下和计算机领域密切相关的奖项有( )。
A.奥斯卡奖
B.图灵奖
C.诺贝尔奖
D.王选奖
正确答案: BD
本题共 1.5

第 21 题
如右图所示,共有 13 个格子。对任何一个格子进行一 次操作,会使得它自己以及与它上下左右相邻的格子中 的数字改变(由 1 变 0,或由 0 变 1)。现在要使得所 有的格子中的数字都变为 0,至少需要_________次操作。
上下左右相邻
正确答案: 3
本题共 5

第 22 题
如下图所示,A 到 B 是连通的。假设删除一条细的边的代价是 1,删除一条粗的边的代价是 2,要让 A、B 不连通,最小代价是(________)(2 分),最小代价的不同方案数是(_______)(3 分)。(只要有一条删除的边不同,就 是不同的方案)
最小代价
1.正确答案: 4
2.正确答案: 9

本题共 5

第 23 题

输入:8 4
输出:_________
正确答案: 15
本题共 8

第 24 题

输入:3
输出:_________
正确答案: 17 24 1 8 15
本题共 8

第 25 题

输入:6
2 6 3 4 5 1
输出:_________
正确答案: 8
本题共 8

第 26 题

输入 1:4 3
输出 1:_________(2 分)
输入 2:2017 1014
输出 2:_________(3 分)
输入 3:987 321
输出 3:_________(3 分)

1.正确答案: 1 3
2.正确答案: 2017 1
3.正确答案: 1 321
本题共 8

第 27 题
(大整数除法)给定两个正整数p和q,其中p不超过10100, q不超过100000, 求 p 除以 q 的商和余数。(第一空 2 分,其余 3 分) 输入:第一行是 p 的位数 n,第二行是正整数 p,第三行是正整数 q。 输出:两行,分别是 p 除以 q 的商和余数。

1.正确答案: p[0]
2.正确答案: rest<q / q>rest
3.正确答案: rest/q
4.正确答案: rest%q*10+p[i]
5.正确答案: rest%q

本题共 14

第 28 题
(最长路径)给定一个有向无环图,每条边长度为 1,求图中的最长路径长度。(第五空 2 分,其余 3 分) 输入:第一行是结点数 n(不超过 100)和边数 m,接下来 m 行,每行两个整数 a, b,表示从结点 a 到结点 b 有一条有向边。结点标号从 0 到(n-1)。 输出:最长路径长度。 提示:先进行拓扑排序,然后按照拓扑序计算最长路径。

1.正确答案: degree[b]=degree[b]+1 / degree[b]++ / ++degree[b]
2.正确答案: degree[i]==0 / !degree[i]
3.正确答案: degree[i]=degree[i]-1 / degree[i]– / –degree[i]
4.正确答案: head=head+1 / head++ / ++head
5.正确答案: ans<len[a] / len[a]>ans

本题共 14