1、第二十四届全国青少年信息学奥林匹克联赛初赛提高组含答案WORD重新整理排版第二十四届全国青少年信息学奥林匹克联赛初赛提高组 C+语言试题竞赛时间：2018 年 10 月 13 日 14:3016:30(WORD重新整理排版)选手注意：试题纸共有 9 页，答题纸共有 2 页，满分 100 分。请在答题纸上作答，写在试题纸上的一律无效。不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。一、单项选择题（共 10 题，每题 2 分，共计 20 分 ； 每题有且仅有一个正确选项）1. 下列四个不同进制的数中，与其它三项数值上不相等的是（ ）。A. (269)16B. (617)10C
2、. (1151)8D. (1001101011)22. 下列属于解释执行的程序设计语言是（ ）。A. CB. C+C. PascalD. Python3. 中国计算机学会于（ ）年创办全国青少年计算机程序设计竞赛。A. 1983B. 1984C. 1985D. 19864. 设根节点深度为 0，一棵深度为 h 的满 k（k1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 k 个子结点的树，共有（ ）个结点。A. (kh+1 - 1) / (k - 1)B. kh-1C. khD. (kh-1 ) / (k - 1)5. 设某算法的时间复杂度函数的递推方程是 T(n) = T(n -
3、 1) + n（n 为正整数）及 T(0) = 1，则该算法的时间复杂度为（ ）。A. O(log n) B. O(n log n) C. O(n) D. O(n2 )6. 表达式 a * d - b * c 的前缀形式是（ ）。A. a d * b c * -B. - * a d * b cC. a * d - b * cD. - * * a d b c7. 在一条长度为 1 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（ ）。A. 1 / 2B. 1 / 3C. 2 / 3D. 3 / 58. 关于 Catalan 数 Cn = (2n)! / (n + 1)! / n!，下
4、列说法中错误的是（ ）。A. Cn 表示有 n + 1 个结点的不同形态的二叉树的个数。B. Cn 表示含 n 对括号的合法括号序列的个数。C. Cn 表示长度为 n 的入栈序列对应的合法出栈序列个数。D. Cn 表示通过连接顶点而将 n + 2 边的凸多边形分成三角形的方法个数。9. 假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于（ ）。A. 1 : 2B. 2 : 1C. 1
5、: 3D. 1 : 110. 为了统计一个非负整数的二进制形式中 1 的个数，代码如下：int CountBit(int x) int ret = 0; while (x) ret+; _; return ret;则空格内要填入的语句是（ ）。A. x = 1B. x &= x - 1C. x |= x 1D. x = 1二 、 不定项选择题（共 5 题，每题 2 分，共计 10 分 ；每题有一个或多个正确选项，多选或少选均不得分 ）1. NOIP 初赛中，选手可以带入考场的有（ ）。A. 笔B. 橡皮C. 手机（关机）D. 草稿纸2. 2-3 树是一种特殊的树，它满足两个条件：（1）每个内部
6、结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同。如果一棵 2-3 树有 10 个叶结点，那么它可能有（ ）个非叶结点。A. 5B. 6C. 7D. 83. 下列关于最短路算法的说法正确的有（ ）。A. 当图中不存在负权回路但是存在负权边时，Dijkstra 算法不一定能求出源点到所有点的最短路。B. 当图中不存在负权边时，调用多次 Dijkstra 算法能求出每对顶点间最短路径。C. 图中存在负权回路时，调用一次 Dijkstra 算法也一定能求出源点到所有点的最短路。D. 当图中不存在负权边时，调用一次 Dijkstra 算法不能用于每对顶点间最短路计算。4. 下列说法中，是树
7、的性质的有（ ）。A. 无环B. 任意两个结点之间有且只有一条简单路径C. 有且只有一个简单环D. 边的数目恰是顶点数目减 15. 下列关于图灵奖的说法中，正确的有（ ）。A. 图灵奖是由电气和电子工程师协会（IEEE）设立的。B. 目前获得该奖项的华人学者只有姚期智教授一人。C. 其名称取自计算机科学的先驱、英国科学家艾伦麦席森图灵。D. 它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。三、 问题求解（共 2 题，每题 5 分，共计 10 分）1. 甲乙丙丁四人在考虑周末要不要外出郊游。已知如果周末下雨，并且乙不去，则甲一定不去；如果乙去，则丁一定去；如果丙去，则丁一定
8、不去；如果丁不去，而且甲不去，则丙一定不去。如果周末丙去了，则甲_（去了/没去）(1 分)，乙_（去了/没去）(1 分)，丁_（去了/没去）(1 分)，周末_（下雨/没下雨）(2 分)。2. 方程 a*b = (a or b) * (a and b)，在 a,b 都取 0, 31 中的整数时，共有_组解。（*表示乘法；or 表示按位或运算；and 表示按位与运算）四 、阅读程序写结果（共 4 题，每题 8 分，共计 32 分）1.#include int main() int x; scanf(%d, &x); int res = 0; for (int i = 0; i x; +i) if
9、(i * i % x = 1) +res; printf(%d, res); return 0;输入：15输出：_2.#include int n, d100;bool v100;int main() scanf(%d, &n); for (int i = 0; i n; +i) scanf(%d, d + i); vi = false; int cnt = 0; for (int i = 0; i n; +i) if (!vi) for (int j = i; !vj; j = dj) vj = true; +cnt; printf(%dn, cnt); return 0;输入： 10 7
10、1 4 3 2 5 9 8 0 6输出：_3.#include using namespace std;string s;long long magic(int l, int r) long long ans = 0; for (int i = l; i s; int len = s.length(); int ans = 0; for (int l1 = 0; l1 len; +l1) for (int r1 = l1; r1 len; +r1) bool bo = true; for (int l2 = 0; l2 len; +l2) for (int r2 = l2; r2 len; +
11、r2) if (magic(l1, r1)=magic(l2, r2) &(l1!=l2 | r1!=r2) bo = false; if (bo) ans += 1; cout ans endl; return 0;输入：abacaba输出：_4.#include using namespace std;const int N = 110;bool isUseN;int n, t;int aN, bN;bool isSmall() for (int i = 1; i = n; +i) if (ai != bi) return ai n) return isSmall(); for (int
12、i = 1; i = n; +i) if (!isUsei) bpos = i; isUsei = true; if (getPermutation(pos + 1) return true; isUsei = false; return false;void getNext() for (int i = 1; i = n; +i) isUsei = false; getPermutation(1); for (int i = 1; i = n; +i) ai = bi; int main() scanf(%d%d, &n, &t); for (int i = 1; i = n; +i) sc
13、anf(%d, &ai); for (int i = 1; i = t; +i) getNext(); for (int i = 1; i = n; +i) printf(%d, ai); if (i = n) putchar(n); else putchar( ); return 0;输入1：6 10 1 6 4 5 3 2输出1：_（3分）输入2：6 200 1 5 3 4 2 6输出2：_（5分）五、完善程序 （共 共 2 题，每题 14 分 ， 共计 28 分 ）1. 对于一个1到n的排列P（即1到n中每一个数在P中出现了恰好一次），令qi为第𝑖个位置之后第一个比Pi
14、值更大的位置，如果不存在这样的位置，则qi=n +1。举例来说，如果n = 5且P为1 5 4 2 3，则P为2 6 6 5 6。下列程序读入了排列P，使用双向链表求解了答案。试补全程序。（第二空2 分，其余 3 分）数据范围 1 n 105 。#include using namespace std;const int N = 100010;int n;int LN, RN, aN;int main() cin n; for (int i = 1; i x; (1) ; for (int i = 1; i = n; +i) Ri = (2) ; Li = i - 1; for (int i
15、= 1; i = n; +i) L (3) = Lai; RLai = R (4) ; for (int i = 1; i = n; +i) cout (5) ; cout endl; return 0;2. 一只小猪要买 N 件物品（N 不超过 1000）。它要买的所有物品在两家商店里都有卖。第 i 件物品在第一家商店的价格是ai，在第二家商店的价格是 bi，两个价格都不小于 0 且不超过 10000。如果在第一家商店买的物品的总额于 不少于 50000，那么在第一家店买的物品都可以打 95 折(价格变为原来的 0.95 倍)。求小猪买齐所有物品所需最少的总额。输入：第一行一个数 N。接下来
16、 N 行，每行两个数。第 i 行的两个数分别代表 ai，bi。输出：输出一行一个数，表示最少需要的总额，保留两位小数。试补全程序。（第一空 2 分，其余 3 分）#include #include using namespace std;const int Inf = 1000000000;const int threshold = 50000;const int maxn = 1000;int n, amaxn, bmaxn;bool put_amaxn;int total_a, total_b;double ans;int fthreshold;int main() scanf(%d, &
17、n); total_a = total_b = 0; for (int i = 0; i n; +i) scanf(%d%d, a + i, b + i); if (ai = bi) total_a += ai; else total_b += bi; ans = total_a + total_b; total_a = total_b = 0; for (int i = 0; i n; +i) if ( (1) ) put_ai = true; total_a += ai; else put_ai = false; total_b += bi; if ( (2) ) printf(%.2f,
18、 total_a * 0.95 + total_b); return 0; f0 = 0; for (int i = 1; i threshold; +i) fi = Inf; int total_b_prefix = 0; for (int i = 0; i = 0; -j) if ( (3) = threshold & fj != Inf) ans = min(ans, (total_a + j + ai) * 0.95+ (4) ); fj = min(fj + bi, j = ai ? (5) : Inf); printf(%.2f, ans); return 0;第二十四届全国青少年
19、信息学奥林匹克联赛初赛提高组参考答案一、单项选择题（共10 题，每题2 分，共计20 分）12345678910DDBADBBADB二、不定项选择题（共5 题，每题2 分，共计10 分；每题有一个或多个正确选项，没有部分分）12345ABCDABDABDBCD三、问题求解（共2题，每题5分，共计10分）1. 去了 没去 没去 没下雨 （第4 空2分，其余1分）2. 454四、阅读程序写结果（共4题，每题8分，共计32 分）1. 42. 63. 164. 输出1： 2 1 3 5 6 4 （3 分） 输出2： 3 2 5 6 1 4 （5 分）五、完善程序（共计28分，以下各程序填空可能还有一些等价的写法，由各省赛区组织本省专家审定及上机验证，可以不上报CCF NOI科学委员会复核）Pascal语言C+语言C 语言分值1(1)ax := iax = i 3(2)i + 12(3)Rai 3(4)ai3(5)Ri32(1)ai * 0.95 = ai * 0.952(2)total_a = threshold 或 threshold = 50000 或 50000 = total_a3(3)total_a + j + ai3(4)fj + total_b - total_b_prefix3(5)fj - ai2
