資源簡介

第二十三屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽
普及組
C++語言試題
競賽時間：2017
年
10
月
14
日
14:30~16:30
選手注意：

試題紙共有
7
頁，答題紙共有
2
頁，滿分
100
分。請在答題紙上作答，寫在
試題紙上的一律無效。

不得使用任何電子設(shè)備（如計算器、手機、電子詞典等）或查閱任何書籍資
料。
一、單項選擇題（共
20
題，每題
1.5
分，共計
30
分；每題有且僅有一個正確選
項）
1.
在
8
位二進制補碼中，10101011
表示的數(shù)是十進制下的（
）。
A.
43
B.
-85
C.
-43
D.
-84
2.
計算機存儲數(shù)據(jù)的基本單位是（
）。
A.
bit
B.
Byte
C.
GB
D.
KB
3.
下列協(xié)議中與電子郵件無關(guān)的是（
）。
A.
POP3
B.
SMTP
C.
WTO
D.
IMAP
4.
分辨率為
800x600、16
位色的位圖，存儲圖像信息所需的空間為（
）。
A.
937.5KB
B.
4218.75KB
C.
4320KB
D.
2880KB
5.
計算機應(yīng)用的最早領(lǐng)域是（
）。
A.
數(shù)值計算
B.
人工智能
C.
機器人
D.
過程控制
6.
下列不屬于面向?qū)ο蟪绦蛟O(shè)計語言的是（
）。
A.
C
B.
C++
C.
Java
D.
C#
7.
NOI
的中文意思是（
）。
A.
中國信息學(xué)聯(lián)賽
B.
全國青少年信息學(xué)奧林匹克競賽
C.
中國青少年信息學(xué)奧林匹克競賽
D.
中國計算機協(xié)會
8.
2017
年
10
月
1
日是星期日，1999
年
10
月
1
日是（
）。
A.
星期三
B.
星期日
C.
星期五
D.
星期二
9.
甲、乙、丙三位同學(xué)選修課程，從
4
門課程中，甲選修
2
門，乙、丙各選修
3
門，則不同的選修方案共有（
）種。
CCF
NOIP2017
初賽普及組
C++語言試題
第
1
頁，共
7
頁
江
西
江
西
A.
36
B.
48
C.
96
D.
192
10.
設(shè)
G
是有
n
個結(jié)點、m
條邊（n
≤
m）的連通圖，必須刪去
G
的（
）條
邊，才能使得
G
變成一棵樹。
A.
m
–
n
+
1
B.
m
-
n
C.
m
+
n
+
1
D.
n
–
m
+
1
11.
對于給定的序列{ak}，我們把
(i,
j)
稱為逆序?qū)Ξ?dāng)且僅當(dāng)
i
<
j
且
ai
>
aj。那么
序列
1,
7,
2,
3,
5,
4
的逆序?qū)?shù)為（
）個。
A.
4
B.
5
C.
6
D.
7
12.
表達(dá)式
a
(b
+
c)
d
的后綴形式是（
）。
A.
a
b
c
d
+
B.
a
b
c
+
d
C.
a
b
c
+
d
D.
b
+
c
a
d
13.
向一個棧頂指針為
hs的鏈?zhǔn)綏Ｖ胁迦胍粋€指針
s指向的結(jié)點時，應(yīng)執(zhí)行（
）。
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”，其子串的個數(shù)是（
）。
A.
72
B.
45
C.
46
D.
36
15.
十進制小數(shù)
13.375
對應(yīng)的二進制數(shù)是（
）。
A.
1101.011
B.
1011.011
C.
1101.101
D.
1010.01
16.
對于入棧順序為
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.
設(shè)
A
和
B
是兩個長為
n
的有序數(shù)組，現(xiàn)在需要將
A
和
B
合并成一個排好序
的數(shù)組，任何以元素比較作為基本運算的歸并算法在最壞情況下至少要做
（
）次比較。
A.
n2
B.
n
log
n
C.
2n
D.
2n
-
1
18.
從（
）年開始，NOIP
競賽將不再支持
Pascal
語言。
A.
2020
B.
2021
C.
2022
D.
2023
19.
一家四口人，至少兩個人生日屬于同一月份的概率是（
）（假定每個人
生日屬于每個月份的概率相同且不同人之間相互獨立）。
A.
1/12
B.
1/144
C.
41/96
D.
3/4
CCF
NOIP2017
初賽普及組
C++語言試題
第
2
頁，共
7
頁
江
西
江
西
20.
以下和計算機領(lǐng)域密切相關(guān)的獎項是（
）。
A.
奧斯卡獎
B.
圖靈獎
C.
諾貝爾獎
D.
普利策獎
二、問題求解（共
2
題，每題
5
分，共計
10
分）
1.
一個人站在坐標(biāo)（0,
0）處，面朝
x
軸正方向。
第一輪，他向前走
1
單位距離，然后右轉(zhuǎn)；第二
輪，他向前走
2
單位距離，然后右轉(zhuǎn)；第三輪，
他向前走
3
單位距離，然后右轉(zhuǎn)……他一直這么
走下去。請問第
2017
輪后，他的坐標(biāo)是：
（_________，_________）。（請在答題紙上用
逗號隔開兩空答案）
2.
如右圖所示，共有
13個格子。對任何一個格子進行一
次操作，會使得它自己以及與它上下左右相鄰的格子中
的數(shù)字改變（由
1變
0，或由
0變
1）。現(xiàn)在要使得所
有的格子中的數(shù)字都變?yōu)?br/>0，至少需要_________次操
作。
三、閱讀程序?qū)懡Y(jié)果（共
4
題，每題
8
分，共計
32
分）
1.
#include

using
namespace
std;
int
main()
{
int
t[256];
string
s;
int
i;
cin
>>
s;
for
(i
=
0;
i
<
256;
i++)
t[i]
=
0;
for
(i
=
0;
i
<
s.length();
i++)
t[s[i]]++;
for
(i
=
0;
i
<
s.length();
i++)
if
(t[s[i]]
==
1)
{
cout
<<
s[i]
<<
endl;
return
0;
}
cout
<<
"no"
<<
endl;
return
0;
}
CCF
NOIP2017
初賽普及組
C++語言試題
第
3
頁，共
7
頁
江
西
江
西
輸入：xyzxyw
輸出：_________
2.
#include

using
namespace
std;
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;
cin
>>
m
>>
n;
cout
<<
g(m,
n,
0)
<<
endl;
return
0;
}
輸入：7
3
輸出：_________
3.
#include

using
namespace
std;
int
main()
{
string
ch;
int
a[200];
int
b[200];
int
n,
i,
t,
res;
cin
>>
ch;
n
=
ch.length();
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];
CCF
NOIP2017
初賽普及組
C++語言試題
第
4
頁，共
7
頁
江
西
江
西
t
=
0;
for
(i
=
n;
i
>
0;
i--)
{
if
(a[i]
==
0)
t++;
if
(b[i
-
1]
+
t
<
res)
res
=
b[i
-
1]
+
t;
}
cout
<<
res
<<
endl;
return
0;
}
輸入：1001101011001101101011110001
輸出：_________
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
CCF
NOIP2017
初賽普及組
C++語言試題
第
5
頁，共
7
頁
江
西
江
西
輸出
1：_________（3分）
輸入
2：2017
1014
輸出
2：_________（5分）
四、完善程序（共
2
題，每題
14
分，共計
28
分）
1.
（快速冪）請完善下面的程序，該程序使用分治法求
xp
mod
m
的值。（第
一空
2
分，其余
3
分）
輸入：三個不超過
10000
的正整數(shù)
x，p，m。
輸出：xp
mod
m
的值。
提示：若
p
為偶數(shù)，xp=(x2)p/2；若
p
為奇數(shù)，xp=x
(x2)(p-1)/2。
#include

using
namespace
std;
int
x,
p,
m,
i,
result;
int
main()
{
cin
>>
x
>>
p
>>
m;
result
=
(1)
;
while
(
(2)
)
{
if
(p
%
2
==
1)
result
=
(3)
;
p
/=
2;
x
=
(4)
;
}
cout
<<
(5)
<<
endl;
return
0;
}
2.
（切割繩子）有
n
條繩子，每條繩子的長度已知且均為正整數(shù)。繩子可以以
任意正整數(shù)長度切割，但不可以連接。現(xiàn)在要從這些繩子中切割出
m
條長度
相同的繩段，求繩段的最大長度是多少。（第一、二空
2.5
分，其余
3
分）
輸入：第一行是一個不超過
100
的正整數(shù)
n，第二行是
n
個不超過
106
的正整數(shù)，表示每條繩子的長度，第三行是一個不超過
108
的正整數(shù)
m。
輸出：繩段的最大長度，若無法切割，輸出
Failed。
#include

using
namespace
std;
int
n,
m,
i,
lbound,
ubound,
mid,
count;
int
len[100];
//
繩子長度
CCF
NOIP2017
初賽普及組
C++語言試題
第
6
頁，共
7
頁
江
西
江
西
int
main()
{
cin
>>
n;
count
=
0;
for
(i
=
0;
i
<
n;
i++)
{
cin
>>
len[i];
(1)
;
}
cin
>>
m;
if
(
(2)
)
{
cout
<<
"Failed"
<<
endl;
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;
}
cout
<<
lbound
<<
endl;
return
0;
}
CCF
NOIP2017
初賽普及組
C++語言試題
第
7
頁，共
7
頁
江
西
江
西

展開更多......

收起↑