竞赛时间: 2017 年 10 月 14 日 14:30~ 16:30
选手注意: 不得使用任何电子设备 (如计算器, 手机, 电子词典等) 或查阅任何书籍资料
一, 单项选择题(共 20 题, 每题 1.5 分, 共计 30 分; 每题有且仅有一个正确选项)
1. 在 8 位二进制补码中, 10101011 表示的数是十进制下的( )
A. 43 B. -85 C. -43 D. -84
2. 计算机存储数据的基本单位是( )
A. bit B. Byte C. GB D. KB
3. 下列协议中与电子邮件无关的是( )
A. POP3 B. SMTP C WTO D IMAP
4. 分辨率为 800*600,16 位色的位图, 存储图像信息所需的空间为( )
A. 937.5KB B. 4218.75KB C. 4320KB D. 2880KB
5. 计算机应用的最早领域是( )
A. 数值计算 B. 人工智能 C. 机器人 D. 过程控制
6. 下列不属于面向对象程序设计语言的是( )
A. C B. C++ C. Java D. C#
NOI 的中文意思是( )
A. 中国信息学联赛 B. 全国青少年信息学奥林匹克竞赛
C. 中国青少年信息学奥林匹克竞赛 D. 中国计算机学会
2017 年 10 月 1 日是星期日, 1999 年 10 月 1 日是( )
A. 星期三 B. 星期日 C. 星期五 D. 星期二
9. 甲, 乙, 丙三位同学选修课程, 从 4 门课程中, 甲选修 2 门, 乙, 丙各选修 3 门, 则不同的选修方案共有( )
A. 36 B. 48 C. 96 D. 192
10. 设 G 是有 n 个结点, m 条边 (nm) 的连接图, 必须删去 G 的 ( ) 条边, 才能使得 G 变成一棵树.
A. m-n+1 B. m-n C. m+n+1 D. n-m+1
11. 对于给定的序列{ak}, 我们把 (i , j) 称为逆序对当且仅当 i<j 且 ai> aj . 那么序列 1,7,2,3,5,4 的逆序对数为 ( ) 个
A. 4 B. 5 C. 6 D. 7
12. 表达式 a*(b+c)*d 的后缀形式是( )
- A. abcd*+*
- B. abc+*d*
C. a*bc+*d
D. b+c*a*d
13. 向一个栈顶指针为 hs 的链式栈中插入一个指针 s 指向的结点时, 应执行( )
A. hs->next =s ; B. s->next=hs; hs=s ;
C. s->next=hs->next;hs->next=s; D. s->next=hs; hs=hs->next;
14. 若串 S="copyright", 其子串的个数是( )
A. 72 B. 45 C. 46 D. 36
15. 十进制小数 13.375 对应的二进制数是( )
A. 1101.011 B. 10111.011 C. 1101.101 D. 1010.01
对于入栈顺序为 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
17. 设 A 和 B 是两个长为 n 的有序数组, 现在需要将 A 和 B 合并成一个排好序的数组, 任何以元素比较作为基本运算的归并算法在最坏情况下至少要做 ( ) 次比较.
A. n2 B. n log n C. 2n D. 2n-1
从 ( ) 年开始, NOIP 竞赛将不再支持 Pascal 语言.
A. 2020 B. 2021 C. 2022 D. 2023
一家四口人, 至少两个人生日属于同一月份的概率是( ) (假定每个人生日属于每个月份的概率相同且不同人之间相互独立).
A. 1/12 B. 1/144 C. 41/96 D. 3/4
20. 以下和计算机领域密切相关的奖项是( )
A. 奥斯卡奖 B. 图灵奖 C. 诺贝尔奖 D. 普利策奖
二, 问题求解(共 2 题, 每题 5 分, 共计 10 分)
1. 一个人站在坐标 (0,0) 处, 面朝 x 轴正方向. 第一轮, 他向前走 1 单位距离, 然后右转; 第二轮, 他向前走 2 单位距离, 然后右转; 第三轮, 他向前走 3 单位 距离, 然后右转...... 他一直这么走下去. 请问第 2017 轮后, 他的坐标是:(___,____).(请在答题纸上用逗号隔开两空答案)
1.png
2. 如右图所示, 共有 13 个格子. 对任何一个格子进行一次操作, 会使得它自己以及与它上下左右相邻的格子中的数字改变(由 1 变 0, 或由 0 变 1). 现在要使得所有的格子中的数字都变为 0, 至少需要_____次操作.
三, 阅读程序写结果(共 4 题, 每题 8 分, 共计 32 分)
- #include <stdio.h>
- #include <string.h>
- int main( )
- int t[256];
- char s[10];
- int I;
- scanf("%s", s);
- for ( i=0; i<256; i++)
- t[i]=0;
- for ( i=0; i< strlen(s); i++)
- t[s[i]]++ ;
- for ( i=0 ; i< strlen (s) ; i++)
- if (t[s[i]]==1 {
- printf("%c\n",s[i] ;
- return 0 ;
- }
- Printf( "no\n");
- Return 0;
- }
输入: xyzxyw
输出:___________.
- #include < stdio.h>
- 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;
- scanf("%d%d", &m,&n);
- printf("%d\n",g( m , n, 0 ));
- return 0;
- }
输入: 7 3
输出:__________.
- #include <stdio.h>
- #include <string.h>
- int main( ) {
- char ch[200];
- int a[200];
- int b[200];
- int n, i , t, res ;
- scanf("%s", ch );
- n=strlen( ch );
- for ( i=0 ; i<200 ; i++ )
- b[i]=0 ;
- for ( i=1 ; i<=n ; i++) {
- a[i]=ch[i-1]-'0';
- b[i]=b[i-1]+a[i];
- }
- res=b[n];
- t= 0;
- for ( i=n ; i>0 ; i--) {
- if ( a[i]==0 )
- t++;
- if ( b[i-1]+t<res )
- res =b[i-1]+t;
- }
- printf( "%d\n", res );
- return 0;
- }
输入: 1001101011001101101011110001
输出:____________________________.
- int main( ) {
- int n, m;
- scanf( "%d%d", &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 ;
- }
- }
- printf( "%d %d\n" , x, y );
- return 0 ;
- }
输入 1: 4 3
输出 2: _________________.(3 分)
输入 2: 2017 1014
输出 2: ________________ ( 5 分).
四, 完善程序 (共 2 题, 每题 14 分, 共计 28 分)
(快速幂)请完善下面的程序, 该程序使用分治法求 xp mod m 的值.(第一空 2 分, 其余 3 分)
输入: 三个不超过 10000 的正整数 x, p, m .
输出: xp mod m 的值.
提示: 若 p 为偶数, xp=(x2)p/2 ; 若 p 为奇数, xp=x*(x2) ( p - 1)/2 .
- #include <stdio.h>
- int x, p, m, i , result ;
- int main( ) {
scanf( "%d%d%d", &x, &p, &m) ;
- result = __(1)_____;
- while ( __(2)______) {
- if ( p % 2 ==1 )
- result = __(3)_______;
- p/=2 ;
- x = __(4)_______;
- }
- printf( "%d\n", __(5)_____) ;
- return 0 ;
- }
(切割绳子) 有 n 条绳子, 每条绳子的长度已知且均为正整数. 绳子可以以任意正整数长度切割, 但不可以连接. 现在要从这些绳子中切割出 m 条长度相同的绳段, 求绳段的最大长度是多少.(第一, 二空 2.5 分, 其余 3 分)
输入: 第一行是一个不超过 100 的正整数 n, 第二行是 n 个不超过 106 的正整数, 表示每条绳子的长度, 第三行是一个不超过 108 的正整数 m.
输出 : 绳段的最大长度, 若无法切割, 输出 Failed.
- #include <stdio.h>
- int n , m, i, lbound, ubound, mid, count ;
- int len[100]; // 绳子长度
- int main( ) {
- scanf( "%d", &n) ;
- count=0 ;
- for ( i=0; i <n ; i++ ) {
- scanf( "%d" , &len[i] );
- ____(1)________.
- }
- scanf( "%d", &m );
- if ( ___(2)_____) {
- printf("Failed\n" ) ;
- return 0 ;
- }
- lbound =1 ;
- ubound =1000000 ;
- while ( ____(3)______ ) {
- mid = ___(4)______;
- count =0 ;
- for ( i=0 ; i < n ; i++ )
- ___(5)_____ ;
- if ( count < m)
- ubound = mid - 1 ;
- else
- lbound = mid ;
- }
- printf ( "%d\n", lbound );
- return 0 ;
- }
参考答案
一, 单项选择题
1 B
原码, 反码, 补码请参考 https://www.jianshu.com/p/b53fe5765884
正数的原码与反码, 补码相同.
负数的反码为原码取反, 最高位符号位不变; 负数的补码为原码取反加 1, 最高位符号位不变.
所以, 负数的原码为补码减 1 取反, 最高位为符号位不用变.
10101011 减 1 变成 10101010, 再取反变成 11010101
- 11010101 = -(64 + 16 + 4 + 1) = -85
- 2 B
- 3 C
POP3: Post Office Protocol - Version 3, 邮局协议 3
SMTP: Simple Mail Transfer Protocol, 简单邮件传输协议
WTO: World Trade Organization, 世界贸易组织
IMAP: Internet Mail Access Protocol, 因特网邮件访问协议
- 4 A
- 8 bit = 1 B
- 1024 B = 1KB
- 800 * 600 * 16 / (8 * 1024) = 937.5kB
- 5 A
美国最早用于计算弹道和射击路线, 即数值分析
6 A
C 语言是面向过程的语言
7 B
NOI: National Olypiad in Infomatics, 全国青少年信息学奥林匹克竞赛
NOIP: National Olypiad in Infomatics in Provices, 全国青少年信息学奥林匹克联赛
8 C
非闰年, X 年 10 月 1 日到 X+1 年 10 月 1 日, 经过 365 天. 365 % 7 = 1, 在星期上相当于过了一天.
闰年一年 366 天, 366 % 7 = 2, 在星期上相当于过了二天.
判断闰年有两个条件: 能被 400 整除; 或能被 4 整除且不能被 100 整除.
1999 年 10 月 1 日~ 2017 年 10 月 1 日, 这 18 年里有 13 个非闰年 5 个闰年(2000,2004,2008,2012,2016), 相当于经过 13 + 5 * 2 = 23 天, 23 % 7 = 2, 相当于经过了天.
星期日 - 2 = 星期五.
9 C
求组合数: C(4, 2) * C(4, 3) * C(4, 3) = 6 * 4 * 4 = 96
10 A
a-1.jpg
树的节点数 = 边数 + 1, 比如上图中节点 10 个, 边有 9 条.
题目中, 图要变成树, 只能保留 n - 1 条边. m - (n - 1) = m - n + 1
11 B
7 2, 7 3, 7 5, 7 4, 5 4. 共五对.
12 B
考察二叉树数据结构, 可参考 https://www.jianshu.com/p/c95ea81b726d
a-2.png
如果没有指明是前缀 (前序), 中缀(中序) 还是后缀(后序), 那么默认指的是中序遍历.
上图二叉树中,
中序遍历为 a*(b+c)*d
后序遍历为 abc+*d*
前序遍历为 **a+bcd
13 B
考察栈的数据结构, 可参考 https://www.jianshu.com/p/f9e4961bf145
新元素入栈后, 要把栈顶指针指到新元素的位置.
14 C
长度为 9 的子串有 9-9+1=1 个, 即 S 本身.
长度为 8 的子串有 9-8+1=2 个, 即 "copyrigh" 和 "opyright".
长度为 7 的子串有 9-7+1=3 个, 即 "copyrig", "opyrigh" 和 "pyright"
......
长度为 1 的子串有 9-1+1=9 个, 即 "c", "o", "p", "y", "r", "i", "g", "h", "t"
长度为 0 的子串有 1 个, 即空串 ""
公式 cnt = len * (len + 1) / 2 + 1
15 A
整数部分, 1101 = 2^3 + 2^2 + 2^0 = 13, 排除 BD
小数部分, 小数十进制转二进制, 就是小数部分不断乘以 2 直到小数完全消失, 计算过程中每次取整数部分作为二进制值.
0.375 * 2 = 0.75 , 取整数部分 0
0.75 * 2 = 1.5, 取整数部分 1, 其小数部分 0.5 参与下次计算
0.5 * 2 = 1, 取整数部分 1
所以小数部分为 011
16 C
A 中, 每次进栈一个字母, 然后该字母立马出栈
B 中, 先入栈 a, 弹出 a; 再入栈 bcd, 弹出 dcb; 第三次入栈 e, 弹出 e; 最后入栈 fg, 弹出 gf
C 中, 无论怎样入栈, 都不会有 db 的出栈顺序
D 中, 把所有字母进栈, 再把所有字母出栈
17 D
考察归并排序, 可参考 https://www.jianshu.com/p/5b08c571762d
设 A 中的元素为 a1, a2, a3; B 中的元素为 b1, b2, b3; 依题意有 a1 < a2 < a3 且 b1 < b2 < b3
比较的代码为
- while (left <= center && centerNext <= right) {
- // 从两个数组中取出最小的放入临时数组
- if (data[left] <= data[centerNext]) {
- tmpArr[tmp++] = data[left++];
- } else {
- tmpArr[tmp++] = data[centerNext++];
- }
- }
这段代码是每比较一次, 就把一个元素放到 tmpArr 中.
(1)比较最多的情况, 比如 tmpArr = {a1, b1, a2, b2, a3}, 或者 tempArr = {a1, a2, b1, b2, a3}, 或者 tmpArr = {b1, b2, a1, a2, a3}, 或者 {b1, b2, a1, a2, b3} 之类的.
注意最后一个元素肯定放在最后, 不用比较. 所以是 2n - 1 次.
(2)更少的情况, 比如 tmpArr = {a1, a2, b1, a3}, 这样比较 2n - 2 次就可以了.
(3)最少的情况, 比如 a3 < b1, 则有 tmpArr = {a1, a2, a3}, 这样比较 n 次就可以了.
所以, 最多比较 2n - 1 次.
18 C
从 2022 年开始, 不可使用 C 和 Pascal, 只能使用 C++
19 C
设 P(A)表示至少两个人生日在同一月份的概率, P(A')表示四个人的生日都不在同一月份的概率, 则 P(A) = 1 - P(A')
- P(A') = A(12, 4) / 12 ^ 4 = 12 * 11 * 10 * 9 / (12 * 12 * 12 * 12)= 55 / 96
- P(A) = 1 - P(A') = 41 / 96
- 20 B
奥斯卡是电影类的奖项
诺贝尔有六种奖项: 物理, 化学, 生物和医疗, 文学, 经济, 和平
普利策是新闻类的奖项
未完待续
TopCoder & Codeforces & AtCoder 交流 QQ 群: 648202993
来源: http://www.jianshu.com/p/8d884cef7ab5