文档介绍：NOIP提高组C初赛试题
NOIP提高组C初赛试题
1
NOIP提高组C初赛试题
第二十二届全国青少年信息学奥林匹克联赛初赛
提高组C++语言试题
竞赛时间：2016年10月22日14:30~16:30
选手注意:后切菜10分钟，最后炒菜10分钟。那么做一道菜需要30分钟。注意：两道不同的菜
的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗，
也不能同时切。那么做完三道菜的最短时间需要（）分钟。
A. 90 B. 60 C. 50 D. 40
假设某算法的计算时间表示为递推关系式
T(n)=2T(
n)+
n
T(1)=1
4
则算法的时间复杂度为（
）。
(n)
(n)
(
nlogn)D.
O(n2)

n个不同的数的数组
L=<x
,x
,...,x>。如果L中存在
x
（1<i<n）使
1
2
n
i
得x1<x2<...<xi-1<xi>xi+1>...>xn，则称L是单峰的，并称xi是L的
“峰顶”。现在已知L是单峰的，请把a-c三行代码补全到算法中使得算法正确找到L的峰顶。
Search(k+1,n)
Search(1,k-1)
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 C. a,b,c D. b,a,c
二、不定项选择题（共5题，，；每题有一个或多个正确选项，多选或少选均不得分）
NOIP提高组C初赛试题
NOIP提高组C初赛试题
6
NOIP提高组C初赛试题
CCFNOIP2016初赛提高组 C++语言试题
第3页，共13页
NOIP提高组C初赛试题
NOIP提高组C初赛试题
7
NOIP提高组C初赛试题
以下属于无线通信技术的有（）。
A. 蓝牙 B. WiFi C. GPRS D. 以太网
可以将单个计算机接入到计算机网络中的网络接入通讯设备有（）。
A. 网卡 B. 光驱 C. 鼠标 D. 显卡
下列算法中运用分治思想的有（）。
A. 快速排序 B. 归并排序 C. 冒泡排序 D. 计数排序
下图表示一个果园灌溉系统，有A、B、C、D四个阀门，每个阀门可以打开或关上，所有管道粗细相同，以下设置阀门的方法中，可以让果树浇上水的
有水
有水
果树
有（）。
A. B打开，其他都关上 B. AB都打开，CD都关上
C. A打开，其他都关上 D. D打开，其他都关上
5. 参加NOI比赛，以下能带入考场的有（）。
A. 钢笔 B. 适量的衣服 C. U盘
三、问题求解（共2题，每题5分，共计10分；每题全部答对得5分，没有部分分）
一个1×8的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如
果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有_________
种填涂方案。
某中学在安排期末考试时发现，有7个学生要参加7门课程的考试，下表列出了哪些学生参加哪些考试（用√表示要参加相应的考试）。最少要安排_________个不同的考试时间段才能避免冲突？
NOIP提高组C初赛试题
NOIP提高组C初赛试题
8
NOIP提高组C初赛试题
CCFNOIP2016初赛提高组 C++语言试题
第4页，共13页
NOIP提高组C初赛试题
NOIP提高组C初赛试题
19
NOIP提高组C初赛试题
考试
学生1
学生2
学生3
学生4
学生5
学生6
学生7
通用技术
√
√
√
物理
√
√
√
化学
√
√
生物
√
√
√
历史
√
√
√
地理
√
√
√
政治
√
√
四、阅读程序写结果（共4题，每题8分