第 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)
1 2 3 4 5 6 7 8 9 10 |
1. k ← ?n/3? 2. 将 A 中硬币分成 X,Y,Z 三个集合,使得|X| = |Y| = k,|Z| = n - 2k 3. if W(X) ≠ W(Y) //W(X), W(Y)分别为 X 或 Y 的重量 4. then __________ 5. else __________ 6. ___ 7. if n>2 then goto 1 8. if n=2 then 任取 A 中1枚硬币与拿走硬币比较,若不等,则它不合格; 若相等,则 A 中剩下的硬币不合格. 9. if n=1 then A 中硬币不合格 |
正确的填空顺序是( )。
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 题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> using namespace std; int g(int m, int n, int x) { int ans = 0; int i; if (n == 1) return 1; for (i = x; i <= m / n; i++) ans += g(m - i, n - 1, i); return ans; } int main() { int t, m, n; cin >> m >> n; cout << g(m, n, 0) << endl; return 0; } |
输入:8 4
输出:_________
正确答案: 15
本题共 8 分
第 24 题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> using namespace std; int main() { int n, i, j, x, y, nx, ny; int a[40][40]; for (i = 0; i < 40; i++) for (j = 0; j < 40; j++) a[i][j] = 0; cin >> n; y = 0; x = n - 1; n = 2 * n - 1; for (i = 1; i <= n * n; i++) { a[y][x] = i; ny = (y - 1 + n) % n; nx = (x + 1) % n; if ((y == 0 && x == n - 1) || a[ny][nx] != 0) y = y + 1; else { y = ny; x = nx; } } for (j = 0; j < n; j++) cout << a[0][j] << " "; cout << endl; return 0; } |
输入:3
输出:_________
正确答案: 17 24 1 8 15
本题共 8 分
第 25 题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <iostream> using namespace std; int n, s, a[100005], t[100005], i; void mergesort(int l, int r) { if (l == r) return; int mid = (l + r) / 2; int p = l; int i = l; int j = mid + 1; mergesort(l, mid); mergesort(mid + 1, r); while (i <= mid && j <= r) { if (a[j] < a[i]) { s += mid - i + 1; t[p] = a[j]; p++; j++; } else { t[p] = a[i]; p++; i++; } } while (i <= mid) { t[p] = a[i]; p++; i++; } while (j <= r) { t[p] = a[j]; p++; j++; } for (i = l; i <= r; i++) a[i] = t[i]; } int main() { cin >> n; for (i = 1; i <= n; i++) cin >> a[i]; mergesort(1, n); cout << s << endl; return 0; } |
输入:6
2 6 3 4 5 1
输出:_________
正确答案: 8
本题共 8 分
第 26 题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> using namespace std; int main() { int n, m; cin >> n >> m; int x = 1; int y = 1; int dx = 1; int dy = 1; int cnt = 0; while (cnt != 2) { cnt = 0; x = x + dx; y = y + dy; if (x == 1 || x == n) { ++cnt; dx = -dx; } if (y == 1 || y == m) { ++cnt; dy = -dy; } } cout << x << " " << y << endl; return 0; } |
输入 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> using namespace std; int p[100]; int n, i, q, rest; char c; int main() { cin >> n; for (i = 0; i < n; i++) { cin >> c; p[i] = c - '0'; } cin >> q; rest = (1); i = 1; while ((2) && i < n) { rest = rest * 10 + p[i]; i++; } if (rest < q) cout << 0 << endl; else { cout << (3); while (i < n) { rest = (4); i++; cout << rest / q; } cout << endl; } cout << (5) << endl; return 0; } |
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <iostream> using namespace std; int n, m, i, j, a, b, head, tail, ans; int graph[100][100]; // 用邻接矩阵存储图 int degree[100]; // 记录每个结点的入度 int len[100]; // 记录以各结点为终点的最长路径长度 int queue[100]; // 存放拓扑排序结果 int main() { cin >> n >> m; for (i = 0; i < n; i++) for (j = 0; j < n; j++) graph[i][j] = 0; for (i = 0; i < n; i++) degree[i] = 0; for (i = 0; i < m; i++) { cin >> a >> b; graph[a][b] = 1; (1); } tail = 0; for (i = 0; i < n; i++) if ((2)) { queue[tail] = i; tail++; } head = 0; while (tail < n - 1) { for (i = 0; i < n; i++) if (graph[queue[head]][i] == 1) { (3); if (degree[i] == 0) { queue[tail] = i; tail++; } } (4); } ans = 0; for (i = 0; i < n; i++) { a = queue[i]; len[a] = 1; for (j = 0; j < n; j++) if (graph[j][a] == 1 && len[j] + 1 > len[a]) len[a] = len[j] + 1; if ((5)) ans = len[a]; } cout << ans << endl; return 0; } |
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 分