2016年NOIP提高组初赛.doc

第二十二届全国青少年信息学奥林匹克联赛初赛
提升组C++语言试题（2小时）
选手注意:
●
不得使用任何电子设施（如计算器、手机、电子字典等）或查阅任何书本资料。
一
10分钟，而后切
菜10
分钟，最后炒菜
10
分钟。那么做一道菜需要
30
分钟。注意：两道不
同的菜的同样步骤不可以够同时进行。
比如第一道菜和第二道的菜不可以同时洗，
也不可以同时切。那么做完三道菜的最短时间需要（）
分钟。
A.
14.
假定某算法的计算时间表示为递推关系式
T(n)=2T(
n)+
n
T(1)=1
4
则算法的时间复杂度为（
）。
(n)(
n)
(
n
logn)
2
(n)
1.
给定含有
n个不一样的数的数组
L=<X1,X2,...,Xn>。假如L中存在Xi（1<i<n）使
得
X1<X2<...<Xi-1<Xi>xi+1>...>Xn
，则称L
是单峰的，并称xi
是L的“峰顶”。
此刻已知L是单峰的，请把
a-c
三行代码补全到算法中使得算法
正确找到L的峰顶。
a.
Search(k+1,n)
b.
Search(1,k-1)
c.
returnL[k]
Search(1,n)
k←[n/2]
ifL[k]>L[k-1]andL[k]>L[k+1]
then__________
elseifL[k]>L[k-1]andL[k]<L[k+1]
then__________
else__________
正确的填空次序是（）。
A.
c,a,b
B.
c,b,a
,b,c
D.
b,a,c
二、不定项选择题（共
5
题，每题
分，合计
分；每题有一个或多个正确
选项，多项选择或
少选均不得分）
1.
以部下于无线通信技术的有（
）。
A.
蓝牙
B.
WiFiC.
GPRS
D.
以太网
2.
能够将单个计算机接入到计算机网络中的网络接入通信设施有（
）。
A.
网卡
B.
光驱

D.
显卡
3.
以下算法中运用分治思想的有（
）。
A.
迅速排序
B.
合并排序
C.
冒泡排序

，有A、B、C、D四个阀门，每个阀门能够翻开
所有管道粗细同样，以下设置阀门的方法中，能够让果树浇上水的有（）。
有水有水

或关上，
果树
A.
B翻开，其余都关上
B.
AB都翻开，CD都关上
C.
A翻开，其余都关上
D.
D翻开，其余都关上
5.
参加NOI竞赛，以下能带入考场的有（
）。
A.

钢笔




三、问题求解（共2题，每题5分，合计10分；每题所有答对得
×8的方格图形（不行旋转）用黑、白两种颜色填涂每个方格。
能填涂一种颜色，且不一样意两个黑格相邻，共有种填涂方案。

5分，没有部分分）假如每个方格只
，有7个学生要参加7门课程的考试，下表列出了哪些学生参加哪些考试（用√表示要参加相应的考试）。最少要安排个不一样的考试时间段才能防止矛盾？
考试

学生1

学生2

学生3

学生4

学生5

学生6

学生7
通用技术

√

√

√
物理

√

√

√
化学

√

√
生物

√

√

√
历史

√

√

√
地理

√

√