2013年第十九届全国青少年信息学奥林匹克联赛初赛
普及组 C++语言试题
竞赛时间： 2013 年 10 月 13 日 14:30~16:30
选手注意：
考试用纸共有9页, 答题专用纸共2页, 满分100分.请考生按照规定, 在答题专用纸上填写答案.
不得使用任何电子设备（如计算器、手机、电子词典等） 或查阅任何书籍资料。
一、单项选择题（共 20 题， 每题 1.5 分， 共计 30 分； 每题有且仅有一个正确选 项）
1. 一个 32 位整型变量占用（ ）个字节。
A. 4 B. 8 C. 32 D. 128
2. 二进制数 11.01 在十进制下是（ ）。
A. 3.25 B. 4.125 C. 6.25 D. 11.125
3. 下面的故事与（ ）算法有着异曲同工之妙。
一座巍峨的山屹立于天地之间，在其幽深的山谷中矗立着一幢庙宇依山而建，在这座古朴的庙宇内住着一位年迈的老僧 overhead 小子们听故事。他以浑厚的声音讲述着从前的故事：一座巍峨的山，在其幽深的山谷中矗立着一幢古旧的庙宇依墙而建，在这座古老的建筑内住着一位智者与世无争地度过余生。他以浑厚的声音讲述着从前的故事：从前有一座高山，在其幽深之处藏着一个古老的寺庙，在寺庙内住着一位年迈的老者向弟子们讲述着关于过去的种种传闻。
A. 枚举 B. 递归 C. 贪心 D. 分治
4. 逻辑表达式（ ）的值与变量 A 的真假无关。
A. (A ˅ B) ˄ ¬A
C. (A ˄ B) ˅ (¬A ˄ B)
B. (A ˅ B) ˄ ¬B
D. (A ˅ B) ˄ ¬A ˄ B
将序列（2, 6, 10, 17）依次存入一个地址区间设定为0至10的线性探查法开放地址法哈希表中，在此方法下若采用模运算作为哈希函数，则 h(x) = x mod 11 将不会产生冲突
A. x mod 11 B. x 2 mod 11
C. 2 x mod 11 D. ⌊√ ⌋ mod 11，其中⌊√ ⌋表示√ 下取整
6. 在十六进制表示法中，字母 A 相当于十进制中的（ ）。
A. 9 B. 10 C. 15 D. 16
7. 下图中所使用的数据结构是（ ）
| 压入 A A. 哈希表 | ||
|---|---|---|
| A |
B.
|压入 B 栈|
| B |
|---|
| A |
C.
弹出 B
队列
| A |
D.
压入 C
二叉树
| C |
| A |
在Windows资源管理器中，在右键点击某个文件时会生成一个以"复制"命名的操作项，请问它的作用是什么？
A. 用剪切板中的文件替换该文件
B. 在该文件所在文件夹中， 将该文件克隆一份
C. 将该文件复制到剪切板， 并保留原文件
D. 将该文件复制到剪切板， 并删除原文件
9. 已知一棵二叉树有 10 个节点，则其中至多有（
A. 4 B. 5 C. 6
）个节点有 2 个子节点。
D. 7
在一个无向图中，在任何两个顶点之间都存在一条通路相连，则称该图为连通图。以下具体实例是一个有
4 个顶点、 6 条边的连通图。
A. 1 B. 2
若要使它不再是连通图，至少要删去其中的（ ）条边。
C. 3 D. 4
11. 二叉树的（
A. 先序遍历
）第一个访问的节点是根节点。
B. 中序遍历 C. 后序遍历 D. 以上都是
12. 以 A 0 作为起点，对下面的无向图进行 深度 优先遍历时，遍历顺序 不可能 是（ ）。
A. A 0, A 1, A 2, A 3 B. A 0, A 1, A 3, A 2 C. A 0, A 2, A 1, A 3 D. A 0, A 3, A 1, A 2
改写说明
A. 40 B. 48 C. 64 D. 128
14. （ ）的 平均 时间复杂度为 O(n log n)，其中 n 是待排序的元素个数。
A. 快速排序 B. 插入排序 C. 冒泡排序 D. 基数排序
15. 下面是根据欧几里得算法编写的函数，它所计算的是 a 和 b 的（ ）。
int euclid(int a, int b)
{
if (b == 0)
return a;
else
return euclid(b, a % b); }
A. 最大公共质因子
C. 最大公约数
B. 最小公共质因子
D. 最小公倍数
16. 通常在搜索引擎中， 对某个关键词加上双引号表示（ ）。
A. 排除关键词，不显示任何包含该关键词的结果
B. 将关键词分解， 在搜索结果中必须包含其中的一部分
C. 精确搜索， 只显示包含整个关键词的结果
D. 站内搜索， 只显示关键词所指向网站的内容
17. 中国的国家顶级域名是（ ）。
A. .cn B. .ch C. .chn D. .china
18. 把 64 位非零浮点数强制转换成 32 位浮点数后， 不可能 （ ）。
A. 大于原数
C. 等于原数
B. 小于原数
D. 与原数符号相反
19. 下列程序中， 正确计算 1, 2, … , 100 这 100 个自然数之和 sum （初始值为 0）的是（ ）。
| . | i = 1; do { sum += i; i++; } while (i <= 100); | . | i = 1; do { sum += i++; } while (i |
|---|
| . | i = 1; while (i < sum += i++; } | . | i = 1; while (i >= 100) { sum += i; i++; } |
|---|
20. CCF NOIP 复赛全国统一评测时使用的系统软件是（ ）。
A. NOI Windows B. NOI Linux C. NOI Mac OS D. NOI DOS
二、问题求解（共 2 题， 每题 5 分， 共计 10 分；每题全部答对得 5 分， 没有部 分分）
1. 7 个同学围坐一圈， 要选 2 个不相邻的作为代表，有_________种不同的选法。
2. 某系统声称通过一种防止窃听的技术来验证用户的密码输入。其中每个si都取值于0或1。该系统每次会随机生成一组ai（i=1到n），其中每个ai也都取值于0或1，请用户计算并报告∑(si·ai)模2的结果。如果经过多次验证用户的回答均准确无误，则视为掌握了相应的密码信息。然而即使这些交流过程被完整记录下来也不会泄露用户的密钥信息。
然而， 事与愿违。例如，当 n = 4 时， 有人窃听了以下 5 次问答：
| 问答编号 | 系统生成的 n 个数 | 掌握密码的用户的回答 | |||
|---|---|---|---|---|---|
| a 1 | a 2 | a 3 | a 4 | ||
| 1 | 1 | 1 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 1 | 0 |
| 3 | 0 | 1 | 1 | 0 | 0 |
| 4 | 1 | 1 | 1 | 0 | 0 |
| 5 | 1 | 0 | 0 | 0 | 0 |
就破解出了密码 s 1 = ， s 2 = ， s 3 = ， s 4 = 。
三、阅读程序写结果（共 4 题， 每题 8 分， 共计 32 分）
1. #include
int main()
{
int a, b;
cin>>a>>b;
cout<<a<<"+"<<b<<"="<<a+b<<endl;
}
输入： 3 5
输出： _________
2. #include
int main()
{
int a, b, u, i, num;
cin>>a>>b>>u;
num = 0;
for (i = a; i <= b; i++)
if ((i % u) == 0)
num++;
cout<<num<<endl;
return 0;
}
输入： 1 100 15
输出： _________
3. #include
int main()
{
const int SIZE = 100;
int n, f, i, left, right, middle, a[SIZE];
cin>>n>>f;
for (i = 1; i <= n; i++)
CCF NOIP2013 初赛普及组 C++语言试题
第 5 页 ， 共 9 页
cin>>a[i];
left = 1;
right = n;
do {
middle = (left + right) / 2;
if (f <= a[middle])
right = middle;
else
left = middle + 1;
} while (left < right);
cout<<left<<endl;
return 0;
}
输入：
12 17
2 4 6 9 11 15 17 18 19 20 21 25
输出： _________
4. #include
using namespace std;
int main()
{
const int SIZE = 100;
int height[SIZE], num[SIZE], n, ans;
cin>>n;
for (int i = 0; i < n; i++) {
cin>>height[i];
num[i] = 1;
for (int j = 0; j < i; j++) {
if ((height[j] < height[i]) && (num[j] >= num[i])) num[i] = num[j]+1;
}
}
ans = 0;
for (int i = 0; i < n; i++) {
CCF NOIP2013 初赛普及组 C++语言试题
第 6 页 ， 共 9 页
if (num[i] > ans) ans = num[i];
}
cout<<ans<<endl;
}
输入：
6
2 5 3 11 12 4
输出： _________
四、完善程序（共 2 题，每题 14 分，共计 28 分）
1. （序列重排） 全局数组变量 a 定义如下： const int SIZE = 100; int a[SIZE], n;
它记录着一个长度为 n 的序列 a[1], a[2], … , a[n]。
为了实现某个特定目标，在编程领域中我们需要设计并实现一个函数。该函数采用整数参数 p（满足条件：1 ≤ p ≤ n），其主要功能是将给定序列 a 的前 p 元素与后 n-p 元素进行交换位置，并且确保被交换的两个部分内部元素原有的顺序不变。举个例子，在长度为5的序列中取前两项与后三项交换位置后得到的结果是3、4、5、1、2。
一种典型的简单直接的方法可用于满足这一需求，并且其时间复杂度与空间复杂度均为 O(n)：
void swap1(int p)
{
int i, j, b[SIZE];
for (i = 1; i <= p; i++)
b[(1)] = a[i];
for (i = p + 1; i <= n; i++)
b[i - p] =(2) ;
for (i = 1; i <=(3) ; i++)
a[i] = b[i];
}
//（3 分）
//（3 分） //（2 分）
我们也可以用时间换空间， 使用时间复杂度为 O(n 2)、空间复杂度为 O(1)的算法：
void swap2(int p)
{
int i, j, temp;
for (i = p + 1; i <= n; i++) {
temp = a[i];
for (j = i; j >=(4) ; j--) a[j] = a[j - 1];
(5)__ = temp;
}
}
//（3 分）
//（3 分）
（binary search tree, BST）遵循以下规则：任何节点的值必须大于左子树中所有节点的值，并且小于右子树中所有节点的值。请判断以下给出的一棵树是否符合二叉查找树的标准
第一行包含一个整数 n（顶点总数），这些顶点的数量由第二行至第n行给出。这些顶点编号从1开始一直到n，并且第一个是根结点。每个节点的数据由三部分组成：分别是该节点的关键字值以及其左右子树的编号（若无则以0代替）。返回值为True时说明它是一棵二叉搜索树；返回值为False则不是。
#include
using namespace std;
const int SIZE = 100;
const int INFINITE = 1000000;
struct node {
int left_child, right_child, value;
};
node a[SIZE];
int is_bst(int root, int lower_bound, int upper_bound)
{
int cur;
if (root == 0)
return 1;
cur = a[root].value;
if ((cur > lower_bound) && ((1)) && //（3 分）
(is_bst(a[root].left_child, lower_bound, cur) == 1) &&
(is_bst((2) ,(3) ,(4)) == 1))
//（3 分，3 分，3 分）
return 1;
return 0;
}
int main()
{
int i, n;
cin>>n;
for (i = 1; i <= n; i++)
cin>>a[i].value>>a[i].left_child>>a[i].right_child;
cout<<is_bst((5) , -INFINITE, INFINITE)<<endl; //（2 分）
return 0;
}