2017年第二十三届NOIP（C语言）普及组初赛试题

一、单项选择题（共20题，每题1.5分，共计30分；每题有且仅有一个正确选项）

名字

在8位二进制补码中，10101011表示的数是十进制下的（ ）

计算机存储数据的基本单位是（ ）

下列协议中与电子邮件无关的是（ ）

分辨率为800*600、16位色的位图，存储图像信息所需的空间为（ ）

计算机应用的最早领域是（ ）

下列不属于面向对象程序设计语言的是（ ）

NOI的中文意思是（ ）

2017年10月1日是星期日，1999年10月1日是（ ）

甲、乙、丙三位同学选修课程，从4门课程中，甲选修2门，乙、丙各选修3门，则不同的选修方案共有（ ）

设G是有n个结点、m条边（n≤m）的连接图，必须删去G的（ ）条边，才能使得G变成一棵树。

对于给定的序列｛ak｝,我们把（i , j）称为逆序对当且仅当 iaj .那么序列1，7，2，3，5，4的逆序对数为（ ）个

表达式a*(b+c)*d的后缀形式是（ ）

向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时，应执行（ ）

若串S=“copyright”，其子串的个数是（ ）

十进制小数13.375对应的二进制数是（ ）

对于入栈顺序为a,b,c,d,e,f,g的序列，下列（ ）不可能是合法的出栈序列

设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做（ ）次比较

从（ ）年开始，NOIP竞赛将不再支持Pascal语言

一家四口人，至少两个人生日属于同一月份的概率是（ )(假定每个人生日属于每个月份的概率相同且不同人之间相互独立)

以下和计算机领域密切相关的奖项是（ ）

二、问题求解（共2题，每题5分，共计10分）

一个人站在坐标（0，0）处，面朝x轴正方向。第一轮，他向前走1单位距离，然后右转；第二轮，他向前走2单位距离，然后右转；第三轮，他向前走3单位 距离，然后右转……他一直这么走下去。请问第2017轮后，他的坐标是：（_,_）。（请在答题纸上用逗号隔开两空答案）

如右图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由1变0，或由0变1）。现在要使得所有的格子中的数字都变为0，至少需要_次操作。

三、阅读程序写结果（共4题，每题8分，共计32分）

#include stdio.h#include string.hint 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.hint 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.hint 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输出：________________.

#include stdio.hint main(){ int n, m; scanf(%d%d, n, m); int x = 1; int y = 1; int dx = 1; int dy = 1; int cnt = 0; int myCnt = 0; while(cnt != 2) { myCnt++; 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输出1： _____（3分）输入2：2017 1014 输出 2： ____ (5分)

四、完善程序 （共2题，每题14分，共计28分）

（快速幂）请完善下面的程序，该程序使用分治法求 xp mod m的值。（第一空2分，其余3分）输入：三个不超过 10000的正整数 x, p, m .输出：x^p mod m的值。提示：若p为偶数，x ^ p=(x ^ 2) ^ p/2 ; 若p为奇数，x ^ p=x*(x ^ 2) ^ ( p - 1)/2 .#include stdio.hint 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个不超过10 ^ 6的正整数，表示每条绳子的长度，第三行是一个不超过10 ^ 8的正整数m。 输出 ：绳段的最大长度，若无法切割，输出Failed.#include stdio.hint 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;}