NOIP提高组C试题无水印去水印文字版页.pdf

CCF NOIP2016 初赛提高组C+语言试题第 1 页，共 10 页第二十三届全国青少年信息学奥林匹克联赛初赛提高组 C+语言试题竞赛时间： 2017 年 10 月 14日 14:3016:30 选手注意：试题纸共有 10 页，答题纸共有 2 页，满分 100 分请在答题纸上作答，写在试题纸上的一律无效不得使用任何电子设备（如计算器、、电子词典等）或查阅任何书籍资料一、单项选择题（共15 题，每题 1.5 分，共计 22.5 分；每题有且仅有一个正确选项）1.从（）年开始， NOIP 竞赛将不再支持Pascal语言A.2020B.2021C.2022D.20232.在 8 位二进制补码中， 10101011表示的数是十进制下的（）A.43B.-85C.-43D.-843.分辨率为 1600 x900、16 位色的位图，存储图像信息所需的空间为（）A.2812.5KBB.4218.75KBC.4320KBD.2880KB4.2017年 10 月 1 日是星期日， 1949 年 10 月 1 日是（） A.星期三B.星期日C.星期六D.星期二5.设 G 是有 n 个结点、m 条边（n m）的连通图，必须删去 G 的（）条边，才能使得 G 变成一棵树。

A.m n + 1B.m - nC.m + n + 1D.n m + 16.若某算法的计算时间表示为递推关系式：T(N) = 2T(N / 2) + N log NT(1) = 1则该算法的时间复杂度为（）A.O(N)B.O(N log N)C.O(N log2 N)D.O(N2)7.表达式 a * (b + c) * d的后缀形式是（）A.a b c d * + *B.a b c + * d *C.a * b c + * dD.b + c * a * d8.由四个不同的点构成的简单无向连通图的个数是（）A.32B.35 C. 38D.41CCF NOIP2016 初赛提高组C+语言试题第 2 页，共 10 页9.将 7 个名额分给 4 个不同的班级，允许有的班级没有名额，有（）种不同的分配方案A.60B.84C.96D.12010. 若 f0 = 0, f1 = 1, fn + 1 = (fn + fn - 1) / 2，则随着 i 的增大， fi将接近于（）A.1/2B.2/3C. 5 - 12D.111. 设 A 和 B是两个长为 n 的有序数组，现在需要将 A 和 B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做（）次比较。

A.n2B.n log nC.2nD.2n-112. 在 n（n 3）枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重），如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法请把a-c 三行代码补全到算法中a.? ?b.? ?c.?|? |算法 Coin(A, n) 1.?/3?2.将 A 中硬币分成 X，Y，Z 三个集合，使得 |? | = |? | = ?, |? | = ? - 2?3.if ?(?)?(?)/W(X), W(Y) 分别为 X 或 Y 的重量4.then _5.else _6._7.if n2 then goto 18.if n=2 then 任取 A 中 1 枚硬币与拿走硬币比较，若不等，则它不合格；若相等，则 A 中剩下的硬币不合格 . 9.if n=1 then A 中硬币不合格正确的填空顺序是（）A.b, c, aB.c, b, aC.c, a, bD.a, b, c13. 有正实数构成的数字三角形排列形式如图所示第一行的数为 a11； 第二行的数从左到右依次为a21, a22； 第 n 行的数为 an1, an2, , ann。

从 a11开始，每一行的数 aij只有两条边可以分别通向下一行的两个数 a(i+1)j和 a(i+1)(j+1) 用动态规划算法找出一条从 a11向下通到 an1, an2, , ann中某a11a21a22a31a32a33an1an2 . annCCF NOIP2016 初赛提高组C+语言试题第 3 页，共 10 页个数的路径，使得该路径上的数之和达到最大令 Ci,j是从 a11到 aij的路径上的数的最大和，并且Ci,0=C0,j=0, 则 Ci,j=（）A.maxCi-1,j-1, Ci-1,j + aijB.Ci-1,j-1 + Ci-1,jC.maxCi-1,j-1, Ci-1,j + 1D.maxCi,j-1,Ci-1,j + aij14. 小明要去南美洲旅游，一共乘坐三趟航班才能到达目的地，其中第1 个航班准点的概率是 0.9，第 2 个航班准点的概率为0.8, 第 3 个航班准点的概率为0.9如果存在第 i 个（i=1,2）航班晚点，第 i+1 个航班准点，则小明将赶不上第 i+1 个航班，旅行失败；除了这种情况，其他情况下旅行都能成功请问小明此次旅行成功的概率是（）。

A.0.5B.0.648C.0.72D.0.7415. 欢乐喷球：儿童游乐场有个游戏叫 “欢乐喷球”，正方形场地中心能不断喷出彩色乒乓球，以场地中心为圆心还有一个圆形轨道，轨道上有一列小火车在匀速运动，火车有六节车厢 假设乒乓球等概率落到正方形场地的每个地点， 包括火车车厢 小朋友玩这个游戏时， 只能坐在同一个火车车厢里， 可以在自己的车厢里捡落在该车厢内的所有乒乓球，每个人每次游戏有三分钟时间， 则一个小朋友独自玩一次游戏期望可以得到（）个乒乓球假设乒乓球喷出的速度为 2 个/ 秒，每节车厢的面积是整个场地面积的 1/20 A.60B.108C.18D.20二、不定项选择题（共5 题，每题 1.5 分，共计 7.5 分；每题有一个或多个正确选项，多选或少选均不得分）1.以下排序算法在最坏情况下时间复杂度最优的有（）A.冒泡排序B.快速排序C.归并排序D.堆排序2.对于入栈顺序为 a, b, c, d, e, f, g的序列，下列（）不可能是合法的出栈序列A.a, b, c, d, e, f, gB.a, d, c, b, e, g, fC.a, d, b, c, g, f, eD.g, f, e, d, c, b, aCCF NOIP2016 初赛提高组C+语言试题第 4 页，共 10 页3.下列算法中，（）是稳定的排序算法。

A.快速排序B.堆排序C.希尔排序D.插入排序4.以下是面向对象的高级语言的有（）A.汇编语言B.C+C.FortranD.Java5.以下和计算机领域密切相关的奖项有（）A.奥斯卡奖B.图灵奖C.诺贝尔奖D.王选奖三、问题求解（共2 题，每题 5 分，共计 10 分）1.如右图所示，共有 13 个格子对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由 1 变 0，或由 0 变 1）现在要使得所有的格子中的数字都变为0，至少需要 _次操作2.如下图所示， A 到 B 是连通的假设删除一条细的边的代价是1，删除一条粗的边的代价是 2，要让 A、B不连通，最小代价是 _（2 分），最小代价的不同方案数是 _ （3 分）只要有一条删除的边不同，就是不同的方案）四、阅读程序写结果（共4 题，每题 8 分，共计 32 分）1.#include using namespace std;int g(int m, int n, int x) int ans = 0; int i; if (n = 1) CCF NOIP2016 初赛提高组C+语言试题第 5 页，共 10 页return 1; for (i = x; i m n; cout g(m, n, 0) endl; return 0; 输入： 8 4 输出： _ 2.#include using namespace std;int main() int n, i, j, x, y, nx, ny; int a4040; for (i = 0; i 40; i+) for (j = 0; j n; y = 0; x = n - 1; n = 2 * n - 1; for (i = 1; i = n * n; i+) ayx = i; ny = (y - 1 + n) % n; nx = (x + 1) % n; if (y = 0 & x = n - 1) | anynx != 0) y = y + 1; else y = ny; x = nx; for (j = 0; j n; j+) cout a0j ; cout endl; return 0; 输入： 3 CCF NOIP2016 初赛提高组C+语言试题第 6 页，共 10 页输出： _ 3.#include using namespace std;int n, s, a100005, t100005, 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 (aj ai) s += mid - i + 1; tp = aj; p+; j+; else tp = ai; p+; i+; while (i = mid) tp = ai; p+; i+; while (j = r) tp = aj; p+; j+; for (i = l; i n; for (i = 1; i ai; mergesort(1, n); cout s endl; return 0; 输入： 6 2 6 3 4 5 1 输出： _ 4.#include 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 CCF NOIP2016 初赛提高组C+语言试题第 8 页，共 10 页输出 2：_ （3 分）输入 3：987 321 输出 3：_ （3 分）五、完善程序（共2 题，每题 14分，共计 28 分）1.（大整数除法）给定两个正整数 p 和 q， 其中 p不超过 10100， q不超过 100000，求 p 除以 q 的商和余数。

第一空2 分，其余 3 分）输入：第一行是 p 的位数 n，第二行是正整数p，第三行是正整数q输出：两行，分别是p 除以 q 的商和余数include using namespace std; int p100; int n, i, q, rest; char c; int main() cin n; for (i = 0; i c; pi = c - 0; cin q; rest = (1) ; i = 1; while ( (2) & i n) rest = rest * 10 + pi; i+; if (rest q) cout 0 endl; else cout (3) ; while (i n) rest = (4) ;i+; cout rest / q; cout endl; CCF NOIP2016 初赛提高组C+语言试题第 9 页，共 10 页 cout (5)。