NOIP2016提高组C++初赛试题


第二十二届全国青少年信息学奥林匹克联赛初赛

提高组 C++语言试题

竞赛时间：2016 年 10 月 22 日 1430~1630

选手注意
● 试题纸 13 页答题纸 2 页满分 100 分请答题纸作答写
试题纸律效

● 电子设备（计算器手机电子词典等）查阅书籍资料


单项选择题（ 15 题题 15 分计 225 分题仅正确 选项）
1 微软公司出品软件（ ）
Ａ Powerpoint Ｂ Word
Ｃ Excel Ｄ Acrobat Reader

2 果开始时计算机处写输入状态现老鼠反复 CapsLock字母键 A字母键 S 字母键 D 序回键 CapsLockASDSACapsLockASDSACapsLockASDSA……屏幕输出第 81 字符字母（ ）
Ａ A Ｂ S Ｃ D Ｄ A

3 二进制数 00101100 01010101 异结果（ ）
Ａ 00101000 Ｂ 01111001 Ｃ 01000100 Ｄ 00111000

4 二进制数 01 相等八进进制数（ ）

Ａ 08 Ｂ 04 Ｃ 02 Ｄ 01
5 较作基运算 N 数中找数少运算次数（ ）
Ａ N Ｂ N1 Ｃ N2 Ｄ log N

6 表达式 a*(b+c)d 缀表达形式（ ）
Ａ abcd*+ Ｂ abc+*d Ｃ abc*+d Ｄ +*abcd

7 棵二叉树右图示采二叉树链表存储该二叉 树（结点包括结点数左孩子指针右孩子指

针）果没左孩子者右孩子应空指针
该链表中空指针数目（ ）
A 6 B 7 C 12 Ｄ 14

8 G 非连通简单图 28 条边该图少（ ）顶点
Ａ 10 Ｂ 9 Ｃ8 Ｄ7



CCF NOIP2016 初赛提高组 C++语言试题 第 1 页 13 页

9 某计算机 CPU 存间址总线宽度 32 位（bit）台计算机 （ ）存

A 2GB B 4GB C 8GB D 16GB

10 程序：

#include using namespace std

int main() {

int k 4 n 0 while (n < k) {

n++

if (n 3 0) continue

k

}

cout << k << << n << endl return 0

}
程序运行输出结果（ ）
Ａ 22 Ｂ 23 Ｃ 32 Ｄ 33
11 7 模样苹果放 3 样盘子中（ ）种放法
Ａ 7 Ｂ 8 Ｃ 21 Ｄ 37

12 Lucia 朋友朋友朋友某社交网站注册账号图 间关系图两间边相连代表两朋友没边相连代表

朋友社交网站规：果某 A （）朋友 B 分享 某张片 B 该片进行评果 B 评该片 （）朋友见评评片该



















CCF NOIP2016 初赛提高组 C++语言试题 第 2 页 13 页

片进行评（非 A （）分享该片）现 Lucia 已传
张片想 Jacob 见张片朋友（ ）分享该片
Ａ Dana Michael Eve Ｂ Dana Eve Monica
Ｃ Michael Eve Jacob Ｄ Micheal Peter Monica

13 周末明爸爸妈妈三起想动手做三道菜明负责洗菜爸爸负责 切菜妈妈负责炒菜假设做道菜序：先洗菜 10 分钟然切 菜 10 分钟炒菜 10 分钟做道菜需 30 分钟注意：两道 菜相步骤时进行例第道菜第二道菜时洗

时切做完三道菜短时间需（ ）分钟

A 90 B 60 C 50 D 40

14 假设某算法计算时间表示递推关系式
T(n) 2T()+
T(1) 1
算法时间复杂度（ ）

AO(n) B O() C O( logn) D O(n2)

1 定含 n 数数组 L果 L 中存 x i（1 < i < n） x1 < x2 < < xi1 < xi > xi+1 > > xn 称 L 单峰称 xi L

峰顶现已知 L 单峰请 ac 三行代码补全算法中算法 正确找 L 峰顶

a Search(k+1 n)

b Search(1 k1)

c return L[k]

Search(1 n)
1 k← [n2]

2 if L[k] > L[k1] and L[k] > L[k+1]

3 then __________

4 else if L[k] > L[k1] and L[k] < L[k+1]

5 then __________

6 else __________

正确填空序（ ）

A c a b B c b a C a b c D b a c

二定项选择题（ 5 题题 15 分计 75 分题正确 选项选少选均分）



CCF NOIP2016 初赛提高组 C++语言试题 第 3 页 13 页

1 属线通信技术（ ）

A 蓝牙 B WiFi C GPRS D 太网

2 单计算机接入计算机网络中网络接入通讯设备（ ）

A 网卡 B 光驱 C 鼠标 D 显卡

3 列算法中运分治思想（ ）

A 快速排序 B 排序 C 泡排序 D 计数排序

4 图表示果园灌溉系统 ABCD 四阀门阀门开 关道粗细相设置阀门方法中果树浇水

水
水



果树









（ ）
A B 开关 B AB 开CD 关
C A 开关 D D 开关

5 参加 NOI 赛带入考场（ ）
A 钢笔 B 适量衣服 C U 盘 D 铅笔


三问题求解（ 2 题题 5 分计 10 分题全部答 5 分没部分分）

1 1×8 方格图形（旋转）黑白两种颜色填涂方格果 方格填涂种颜色允许两黑格相邻_________种填 涂方案

2 某中学安排期末考试时发现 7 学生参加 7 门课程考试表列 出学生参加考试（√表示参加相应考试） 少安排_________考试时间段避免突？









CCF NOIP2016 初赛提高组 C++语言试题 第 4 页 13 页

考试
学生 1
学生 2
学生 3
学生 4
学生 5
学生 6
学生 7








通技术
√



√

√
物理
√
√




√
化学

√

√



生物
√



√
√

历史


√
√

√

理

√
√



√
政治


√


√


四阅读程序写结果（ 4 题题 8 分计 32 分）

1 #include using namespace std

int main() {

int a[6] {1 2 3 4 5 6} int pi 0

int pj 5 int t i

while (pi < pj) {
t a[pi]
a[pi] a[pj]
a[pj] t pi++

pj

}

for (i 0 i < 6 i++) cout << a[i] <<

cout << endl return 0

}

输出：_________

2 #include using namespace std

int main() {

char a[100][100] b[100][100] string c[100]

string tmp

int n i 0 j 0 k 0 total_len[100] length[100][3]



CCF NOIP2016 初赛提高组 C++语言试题
第 5 页 13 页




cin >> n
getline(cin tmp)
for (i 0 i < n i++) {
getline(cin c[i])
total_len[i] c[i]size()
}
for (i 0 i < n i++) {
j 0
while (c[i][j] ＇＇) {
a[i][k] c[i][j]
k k + 1
j++
}
length[i][1] k 1
a[i][k] 0
k 0
for (j j + 1 j < total_len[i] j++) {
b[i][k] c[i][j]
k k + 1
}
length[i][2] k 1
b[i][k] 0
k 0
}
for (i 0 i < n i++) {
if (length[i][1] > length[i][2])
cout << NO
else {
k 0
for (j 0 j < length[i][2] j++) {
if (a[i][k] b[i][j])
k k + 1
if (k > length[i][1]) break
}
if (j length[i][2])
cout << NO
else
cout << YES
}

}
cout << endl
return 0



CCF NOIP2016 初赛提高组 C++语言试题
第 6 页 13 页


}

输入：3 ABACDEbFBkBD ARACDBrT
SARSSevere Atypical Respiratory Syndrome 输出：_________

（注：输入行前均空格）


3 #include
using namespace std

int lps(string seq int i int j) {
int len1 len2
if (i j) return 1
if (i > j) return 0
if (seq[i] seq[j])
return lps(seq i + 1 j 1) + 2
len1 lps(seq i j 1)
len2 lps(seq i + 1 j)
if (len1 > len2)
return len1
return len2
}

int main() {
string seq acmerandacm
int n seqsize()
cout << lps(seq 0 n 1) << endl
return 0
}

输出：_________


4 #include
#include
using namespace std

int map[100][100]
int sum[100] weight[100]
int visit[100]



CCF NOIP2016 初赛提高组 C++语言试题
第 7 页 13 页


int n

void dfs(int node) {
visit[node] 1
sum[node] 1
int v maxw 0
for (v 1 v < n v++) {
if (map[node][v] || visit[v])
continue
dfs(v)
sum[node] + sum[v]
if (sum[v] > maxw)
maxw sum[v]
}
if (n sum[node] > maxw)
maxw n sum[node]
weight[node] maxw
}

int main() {
memset(map 0 sizeof(map))
memset(sum 0 sizeof(sum))
memset(weight 0 sizeof(weight))
memset(visit 0 sizeof(visit))
cin >> n
int i x y
for (i 1 i < n i++) {
cin >> x >> y
map[x][y] 1
map[y][x] 1
}
dfs(1)
int ans n ansN 0
for (i 1 i < n i++)
if (weight[i] < ans) {
ans weight[i]
ansN i
}
cout << ansN << << ans << endl
return 0
}

输入：11



CCF NOIP2016 初赛提高组 C++语言试题
第 8 页 13 页


1 2
1 3
2 4
2 5
2 6
3 7
7 8
7 11
6 9
9 10
输出：_________


五完善程序（ 2 题题 14 分计 28 分）

1 （交朋友）根社会学研究表明喜欢找身高相做朋友 现 n 名身高两两相学次走入教室调查员想预测 走入教室瞬间想已进入教室做朋友两名学名 学身高差样时名学会更想高做朋友名身高 180 米学进入教室时名身高 179 米学名身高181米学教室里名身高 180 米学会更想身高 181 米学做朋友第走入教室学做预测
知道身高走进教室次序采离线做法解决样问题排序加链表方式帮助找 前进入教室身高相（第空 2 分余 3 分）

#include using namespace std #define MAXN 200000
#define infinity 2147483647

int answer[MAXN] height[MAXN] previous[MAXN] next[MAXN] int rank[MAXN]
int n

void sort(int l int r) {
int x height[rank[(l + r) 2]] i l j r temp while (i < j)
{
while (height[rank[i]] < x) i++ while (height[rank[j]] > x) j

if ( (1) ) {
temp rank[i] rank[i] rank[j] rank[j] temp



CCF NOIP2016 初赛提高组 C++语言试题
第 9 页 13 页

i++ j
}
}
if (i < r) sort(i r)
if (l < j) sort(l j)
}

int main()
{
cin >> n
int i higher shorter
for (i 1 i < n i++) {
cin >> height[i]
rank[i] i

sort(1 n)
for (i 1 i < n i++) {
previous[rank[i]] rank[i 1]
(2)
}
for (i n i > 2 i){
higher shorter infinity
if (previous[i] 0)
shorter height[i] height[previous[i]] if (next[i] 0)
(3)
if ( (4) )
answer[i] previous[i]
else
answer[i] next[i]
next[previous[i]] next[i]
(5)
}
for (i 2 i < n i++)
cout << i << << answer[i]
return 0
}

2 (交通中断）国家国家 n 座城市 m 条双道路条道路连接着两座城市中 1 号城市国家首震频繁导致某城市外界交通全部中断国家首脑想知道果第i(i>1)城市震导致交通中断时首少城市短路径长度会发生改变果法通第 i 城市导致首出发法达某城

CCF NOIP2016 初赛提高组C++语言试题
第 10 页 13 页



市认达该城市短路径长度改变
城市 i假定第 i 城市外界交通中断输出少 城市会导致首短路径长度改变
采邻接表方式存储图信息中 head[x]表示顶点 x 第条 边编号next[i]表示第 i 条边条边编号point[i]表示第 i 条边终点weight[i]表示第 i 条边长度（第空 2 分余 3 分）

#include #include using namespace std #define MAXN 6000 #define MAXM 100000

#define infinity 2147483647

int head[MAXN] next[MAXM] point[MAXM] weight[MAXM] int queue[MAXN] dist[MAXN] visit[MAXN]

int n m x y z total 0 answer

void link(int xint yint z) {
total++
next[total] head[x] head[x] total point[total] y weight[total] z total++
next[total] head[y] head[y] total point[total] x weight[total] z

}

int main() {
int i j s t cin >> n >> m
for (i 1 i < m i++) {
cin >> x >> y >> z link(x y z)
}
for (i 1 i < n i++) dist[i] infinity
(1)
queue[1] 1
visit[1] 1
s 1


CCF NOIP2016 初赛提高组 C++语言试题 第 11 页 13 页




t 1

SPFA 求出第点余点短路长度

while (s < t) {

x queue[s MAXN]

j head[x]

while (j 0) {

if ( (2) ) {

dist[point[j]] dist[x] + weight[j]

if (visit[point[j]] 0) {

t++

queue[t MAXN] point[j]

visit[point[j]] 1

}

}

j next[j]

}
(3)

s++

}

for (i 2 i < n i++) {

queue[1] 1

memset(visit 0 sizeof(visit))

visit[1] 1

s 1

t 1

while (s < t) { 判断短路长度否变

x queue[s]

j head[x]

while (j 0) {

if (point[j] i && (4)
&&visit[point[j]] 0) {

(5)

t++

queue[t] point[j]

}

j next[j]

}

s++

}

answer 0

for (j 1 j < n j++) answer + 1 visit[j]

cout << i << << answer 1 << endl



CCF NOIP2016 初赛提高组 C++语言试题
第 12 页 13 页

}
return 0

}


































































CCF NOIP2016 初赛提高组 C++语言试题 第 13 页 13 页
文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档