2018 年第二十三届全国青少年信息学奥林匹克联赛初赛
目录
一、单项选择题 (共 20 题，每题 1.5 分，共计 30 分；每题有且仅有一个正确选项)
二、问题求解 (共 2 题，每题 5 分，共计 10 分)
三、阅读程序写结果 (共 4 题，每题 8 分，共计 32 分)
四、完善程序 (前 11 空，每空 2 分，后 2 空，每空 3 分，共计 28 分)
2018 年第二十三届全国青少年信息学奥林匹克联赛初赛
( c++语言) 参考答案与评分标准
2018 年第二十三届全国青少年信息学奥林匹克联赛初赛
( 普及班 c****++**** 语言 完成时间为两小时 ) ●● 所有试题的答案必须要求写在答卷纸上，写在试卷纸上一律不得作答 ●●
选手注意：
试题纸共有 8 页，答题纸共有 2 页，满分 100 分。请在答题纸上作答，写在试题
纸上的一律无效。
不得使用任何电子设备 (如计算器、手机、 电子词典等) 或查阅任何书籍资料。
一、单项选择题 (共 20 题，每题 1.5 分，共计 30 分；每题有且仅有一个正确选项)
1、c++中“a=b=c ”( a，b，c 均为变量或表达式) 的作用是：( )
A、判定 a，b，c 相等。B、将 a 的值给 b，c。
C、将 c 的值给 a，b。D、将 b 的值给 a，c。
2、smalltalk 是一种：( )
A、汇编语言。B、面向对象的高级语言。
C、面向过程的高级语言。D、算法。
3、11 进制的所有基数是：( )
A、0，1,2,3,4,5,6,7,8,9，A
B、1,2，3,4,5,6,7,8,9，A，B
C、1,2,3,4,5,6,7,8,9,10,11
D、0,1,2,3,4,5,6,7,8,9,10
4、以下代码中能实现 s=a+b 的是：( )
A
、
s=a;
for (int i=1;i<b;i++) s++;
B
、
s=b;
for (int i=0;i<=a;i++) ++s;
、
s=0;
for (int i=1;i<=a;i++)
for (int j=1;j<=b;j++) s++;
CCF NOIP2018 初赛
普及组 c++ 1
D
、
s=a*b+b;
for (int i=1;i<b;i++) s-=a;
5、FTP 协议是：( )
A：远程登录协议 B：文件传输协议
C：电子邮件收发协议 D：快速文件传输协议
6、(2^10 (此处指乘方)) 2= ( )
A、10000000000 B、1111111111 C、1023 D、1024
7、2018 的二进制位数为：( )
A、9 B、10 C、11 D、2018
8、2TB= ( )
A、10^3GB B、2^10KB C、2^20MB D、10^9B
9、高速缓存的英文缩写是：( )
A、TCP/IP B、CPU C、ROM D、Cache
10、以下不属于计算机病毒性质的是：( )
A、简便性 B、寄生性 C、潜伏性 D、隐蔽性
11、满足 ( ) 的题目，可以使用动态规划。
A、时限较小 B、递推式不明显 C、数据范围很大
D、最优化原理
当运算结果超出long long范围时，开发人员以下不推荐采用的解决方案为：（）
A、使用无符号整型，用另一个变量表示符号 B、使用高精度算法
C、将数据对一个数求余 D、使用双精度实型，最后取整
13、以下合法的 IPv 地址是：( )
A、10 .0 .255 .0 B、192 .0 .0 .0 C、1.1.1.256 D、0.113 .75.2 14、对数列：9,8,7,4,1,5 进行冒泡排序 (升序)，需要交换 () 次。
A、0 B、11 C、13 D、17
15、可以使用 ( ) 来实现 cout 的场宽输出，包含于 ( ) 头文件：
A、print，string print B、open file，string print C、string convert，string print D、long，iostream 16、NOIP 的意思是：全国青少年信息学奥林匹克竞赛 ( )
A、竞赛 B、联赛 C、联赛普及组 D、竞赛提高组
17、( ) 头文件包含了 sort 函数，它的意思是“算法”。
A、algorithm B、cmath C、iostream D、bits/stdc++.h 18、c++表达式 6322 的值是：
A、61 B、59 C、15752961 D、63
19、利用指针可以构造出 ( )，在使用完后可以立即释放所用空间。
CCF NOIP2018 初赛
普及组 c++ 2
A、线性表 B、堆栈 C、图 D、链表
20、stl 队列所用头文件是：( )
A、map B、queue C、vector D、iostream
二、问题求解 (共 2 题，每题 5 分，共计 10 分)
1、排列 1 2 3 4 5，所有数字可重复使用，要求 2 不在 5 号位上，3 不在 1 号位上，则 总方案数为____________。
商店：某个商店销售不同数量的同一种货物。无论顾客需要多少数量的货物，该店总能在第一时间整理出所需的货物量，这是因为该店会预先将所有货物按不同数量包装成箱。当收到订单时，依据所需数量取出相应的箱子（可能一次取出多个箱子）。现有一个订单数量在100以内，请求计算所需箱子的数量，并列出各个箱子按货物数量从小到大排列时所包含的货物数量：
三、阅读程序写结果 (共 4 题，每题 8 分，共计 32 分)
1、
#include
using namespace std;
int main ()
{
int n,m,s=0;scanf ("%d%d",&n,&m);
bool visit [200]={0};
for (int k=0;k<n;k++){
for (int i=0;i<m;i++){if (++s>n)s=1;if (visit [s])i--;}
printf ("%d ",s);visit [s]=true;
}
return 0;
}
输入：10 3
输出：__________
2、
#include<stdio .h>
#include<string.h>
int n;char a [10000];
int main (){
scanf ("%d%s",&n,a);
int l=strlen (a);
int i;
CCF NOIP2018 初赛
普及组 c++ 3
if (a [0]== '0 ') printf ("0");
for (i=0;i<l;i++){
if (a [i]== '0 ') goto A;
else if (a [i]> '0 ' && a [i]<= '9 ')
printf ("%d*%d^%d",a [i]- '0 ',n,l-i-1);
else if (a [i]>= 'a ' && a [i] <= 'z ')
printf ("%d*%d^%d",a [i]- 'a '+10,n,l-i-1);
else if (a [i]>= 'A' && a [i] <= 'Z ')
printf ("%d*%d^%d",a [i]- 'A'+10,n,l-i-1);
A: if (a [i+1] != '0 ' && a [i+1] !=0) printf ("+");
}
return 0;
}
输入：2 10101
输出：__________
3、#include
#include
#include
using namespace std;
int main (){
const int MAXN = 20010;
int f [MAXN];
int v [40];
memset (f,0,sizeof (f));
memset (v,0,sizeof (v));
int n;
int m;
cin>>n;
cin>>m;
for (int i=1;i<=m;i++){
cin>>v [i];
}
for (int i=1;i<=m;i++){
for (int j=n;j>=v [i];j--){
if (f [j]<f [j-v [i]]+v [i]){
f [j]=f [j-v [i]]+v [i];
CCF NOIP2018 初赛
普及组 c++ 4
}
}
}
cout<<n-f [n];
return 0;
}
输入：
24 6
8 3 12 7 9 7
输出：_________
4、
#include<bits/stdc++ .h>
using namespace std;
int a [101],n,i,m;
int function (int x)
{
int left=0;
int right=n-1;
while (left<=right)
{
int middle= (left+right)/2;
if (a [middle]==x)
return middle;
if (x>=a [middle])
left=middle+1;
else
right=middle-1;
}
return -1;
}
int main ()
{
cin>>n;
for (i=1;i<=n;i++) cin>>a [i];
sort (a,a+n+1);
for (i=n;i>=1;i--) cout<<a [i]<< ' ';
cin>>m;
cout<<function (m);
cout<<endl;
}
(1)输入：
10
10 5 9 1 7 2 9 0 10 6
5
输出：____________
(2)输入：
20
4 23 89 6 0 99 87 5 95 1 25 78 92 45 26 32 93 96 0 57
56
输出：_____________
四、完善程序 (前 11 空，每空 2 分，后 2 空，每空 3 分，共计 28 分)
1、(Catalan 数列)：对于输入的 n，输出 Catalan 数列的第 n 项。
(1) Catalan 公式：ans = f [0]*f [n-1] + f [1]*f [n-2] + .. . + f [n-1]*f [0];
****#****include <cstdio>
int n****,**** f [30];
int mai********n ()
{
scanf ("%d", &n);
f [0] = 1,
f [1] = (1) ; ( 2 分)
for (int i=2; i<=n; i++)
for (int j=0; (2) ; j++) ( 2 分)
f [i] += f [j] * f [ (3) ]; ( 3 分)
printf ("%d", f [n]);
return 0;
}
(2) Catalan(n)=C(2n,n)/(n+1) = >2n!/n!/n!/n+1 = >π (n+2 < =i<=2n,i)/n!
#include
int main()
{
int n,i;
long long ans=1;
scanf("%d",&n);
for( (4) ；i++) (3 分)
ans=ans* (5) ; (3 分)
printf("%lld",ans/(n+1));
return 0;
}
归并排序：归并排序法是一种具有稳定的 O(nlogn) 时间复杂度的排序算法。该算法的核心思想是将原序列划分为两个部分，分别对这两个子序列进行归并排序，然后将这两个子序列合并，体现了二分法的基本原理。
现要求完成以下归并排序的子程序段：
void merge (int *data,int start,int end,int *result) //归并
{
int left_length = __(__1 ) ; (3 分)
int left index = start;
int right_index = start + left_length;
int result index = start;
while ((__2 ) &&(__3 ) ) (2 分，2 分)
{
if (data [left_index] <= data [right_index])
result [result_index++] = data [left_index++];
else
result [result_index++] = data [right_index++];
}
while (left_index < start + left_length)
result [result_index++] = data [left_index++];
while (__(__4 ) ) (3 分)
result [result_index++] = data [right_index++];
}
void merge_sort (int *data, int start, int end, int *result) //
分解
{
if (1 == end - start)
{
if (__(__5 ) ) (2 分)
{
int temp = data [start];
data [start] = data [end];
data [end] = temp;
}
return;
}
else if (0 == end - start)
return;
else
{
merge_sort (data,start, (end-start+1)/2+start,result);
merge_sort (data, (end-start+1)/2+start+1,end,result);
__(__6 ) ; (3 分)
for (int i = start;i <= end;++i)
data [i] = result [i];
}
CCF NOIP2018 初赛
普及组 c++ 8
2018 年第二十三届全国青少年信息学奥林匹克联赛初赛
( c****++**** 语言) 参考答案与评分标准
一、单项选择题 (共 20 题，每题 1.5 分，共计 30 分)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| C | B | A | D | B | A | C | B | D | A |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| D | C | A | C | C | B | A | D | D | B |
二、问题求解 (共 2 题，每题 5 分，共计 10 分)
1．1000
2．7 个：1 2 4 8 16 32 64
三、阅读程序写结果 (共 4 题，每题 8 分，共计 32 分)
1．3 6 9 2 7 1 8 5 10 4
2．124+1*22+12^0
3．0
4． (1)
10 10 9 9 7 6 5 2 1 0
4
(2)
99 96 95 93 92 89 87 78 57 45 32 26 25 23 6 5 4 1 0 0
-1
四、完善程序 (共 28 分)
说明：其中各程序填空处可能还有其他等价的表达方式，各省份均可委托本省份的专家进行审定以及上机验证工作，无需上报科学委员会进行审查。
1．①1
②j<i
③i-j-1
④i=n+1;i<=2*n;i++
⑤i/ (i-n)
2．① (end - start + 1) / 2 + 1
②left_index < start + left_length
③right_index < end+1
④right_index < end+1
⑤data [start] > data [end]
⑥merge (data,start,end,result)