NOIP 2012 普及组初赛试题
一、单项选择题（共 20 题，每题 1.5 分，共计 30 分；每题有且仅有一个正确选项）
- 计算机如果缺少（ ），将无法正常启动。 {{ select(1) }}
- 内存
- 鼠标
- U 盘
- 摄像头
- （ ）是一种先进先出的线性表。 {{ select(2) }}
- 栈
- 队列
- 哈希表（散列表）
- 二叉树
- 目前计算机芯片（集成电路）制造的主要原料是（ ），它是一种可以在沙子中提炼出的物质。 {{ select(3) }}
- 硅
- 铜
- 锗
- 铝
- 十六进制数9A在（ ）进制下是232。 {{ select(4) }}
- 四
- 八
- 十
- 十二
- （ ）不属于操作系统。 {{ select(5) }}
- Windows
- DOS
- Photoshop
- NOI Linux
- 如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（ ）。 {{ select(6) }}
- ABC
- CBA
- ACB
- BAC
- 目前个人电脑的（ ）市场占有率最靠前的厂商包括Intel、AMD等公司。 {{ select(7) }}
- 显示器
- CPU
- 内存
- 鼠标
- 使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列 5，4，3，2，1需要执行（ ）次操作，才能完成冒泡排序。 {{ select(8) }}
- 0
- 5
- 10
- 15
- 1946年诞生于美国宾夕法尼亚大学的ENIAC属于（ ）计算机。 {{ select(9) }}
- 电子管
- 晶体管
- 集成电路
- 超大规模集成电路
- 无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（ ）。 {{ select(10) }}
- 中国公司的经理与波兰公司的经理交互商业文件
- 军队发布命令
- 国际会议中，每个人都与他国地位对等的人直接进行会谈
- 体育比赛中，每一级比赛的优胜者晋级上一级比赛
- 矢量图（Vector Image）图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋转等都不会失真，是因为它（ ）。 {{ select(11) }}
- 记录了大量像素块的色彩值来表示图像
- 用点、直线或者多边形等基于数学方程的几何图元来表示图像
- 每个像素点的颜色信息均用矢量表示
- 把文件保存在互联网，采用在线浏览的方式查看图像
- 如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a，b，c，另有元素d已经出栈，则可能的入栈顺序是（ ）。 {{ select(12) }}
- a, d, c, b
- b, a, c, d
- a, c, b, d
- d, a, b, c
- （ ）是主要用于显示网页服务器或者文件系统的HTML文件的内容，并让用户与这些文件交互的一种软件。 {{ select(13) }}
- 资源管理器
- 浏览器
- 电子邮件
- 编译器
- （ ）是目前互联网上常用的E-mail服务协议。 {{ select(14) }}
- HTTP
- FTP
- POP3
- Telnet
- （ ）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题……直到最后的子问题可以简单地直接求解。而原问题的解就是子问题解的并。 {{ select(15) }}
- 动态规划
- 贪心
- 分治
- 搜索
- 地址总线的位数决定了CPU可直接寻址的内存空间大小，例如地址总线为16位，其最大的可寻址空间为64KB。如果地址总线是32位，则理论上最大可寻址的内存空间为（ ）。 {{ select(16) }}
- 128KB
- 1MB
- 1GB
- 4GB
- 蓝牙和Wi-Fi都是（ ）设备。 {{ select(17) }}
- 无线广域网
- 无线城域网
- 无线局域网
- 无线路由器
- 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。 {{ select(18) }}
- 系统分配的栈空间溢出
- 系统分配的堆空间溢出
- 系统分配的队列空间溢出
- 系统分配的链表空间溢出
- 原字符串中任意一段连续的字符所组成的新字符串称为子串。则字符“AAABBBCCC”共有（ ）个不同的非空子串。 {{ select(19) }}
- 3
- 12
- 36
- 45
- 仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，并将这些原理移植于新兴的工程技术中。以下关于仿生学的叙述，错误的是（ ） {{ select(20) }}
- 由研究蝙蝠，发明雷达
- 由研究蜘蛛网，发明因特网
- 由研究海豚，发明声纳
- 由研究电鱼，发明伏特电池
二、问题求解（共 2 题，每题 5 分，共计 10 分）
- 如果平面上任取 n 个整点（横纵坐标都是整数），其中一定存在两个点，它们连线的中点也是整点，那么 n 至少是{{ input(21) }}。
- 在 NOI 期间，主办单位为了欢迎来自全国各地的选手，举行了盛大的晚宴。在第十八桌，有 5 名大陆选手和 5 名港澳选手共同进膳。为了增进交流，他们决定相隔就坐，即每个大陆选手左右相邻的都是港澳选手、每个港澳选手左右相邻的都是大陆选手。那么，这一桌共有{{ input(22) }}种不同的就坐方案。注意：如果在两个方案中，每个选手左边相邻的选手均相同，则视为同一个方案。
三、阅读程序写结果（共 4 题，每题 8 分，共计 32 分）
#include <iostream>
using namespace std;
int a, b, c, d, e, ans;
int main()
{
cin >> a >> b >> c;
d = a + b;
e = b + c;
ans = d + e;
cout << ans << endl;
return 0;
}
输入：1 2 5
输出：{{ input(23) }}
#include <iostream>
using namespace std;
int n, i, ans;
int main()
{
cin >> n;
ans = 0;
for (i = 1; i <= n; i++)
if (n % i == 0)
ans++;
cout << ans << endl;
return 0;
输入：18
输出：{{ input(24) }}
#include <iostream>
using namespace std;
int n, i, j, a[100][100];
int solve(int x, int y)
{
int u, v;
if (x == n)
return a[x][y];
u = solve(x + 1, y);
v = solve(x + 1, y + 1);
if (u > v)
return a[x][y] + u;
else
return a[x][y] + v;
}
int main()
{
cin >> n;
for (i = 1; i <= n; i++)
for (j = 1; j <= i; j++)
cin >> a[i][j];
cout << solve(1, 1) << endl;
return 0;
}
输入:
5
2
-1 4
2 -1 -2
-1 6 4 0
3 2 -1 5 8
输出：{{ input(25) }}
#include <iostream>
#include <string>
using namespace std;
int n, ans, i, j;
string s;
char get(int i)
{
if (i < n)
return s[i];
else
return s[i - n];
}
int main()
{
cin >> s;
n = s.size();
ans = 0;
for (i = 1; i <= n - 1; i++)
{
for (j = 0; j <= n - 1; j++)
if (get(i + j) < get(ans + j))
{
ans = i;
break;
}
else if (get(i + j) > get(ans + j))
break;
}
for (j = 0; j <= n - 1; j++)
cout << get(ans + j);
cout << endl;
}
输入：CBBADADA
输出：{{ input(26) }}
四、完善程序（前 2 空每空 2 分，后 8 空每空 3 分，共计 28 分）
（坐标统计）输入n个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点（即x、y坐标都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。
#include <iostream>
using namespace std;
const int SIZE = 100;
int x[SIZE], y[SIZE], f[SIZE];
int n, i, j, max_f, ans;
int main()
{
cin >> n;
for (i = 1; i <= n; i++)
cin >> x[i] >> y[i];
max_f = 0;
for (i = 1; i <= n; i++)
{
f[i] = [ ① ];
for (j = 1; j <= n; j++)
{
if (x[j] < x[i] &&[ ② ])
[ ③ ];
}
if ([ ④ ])
{
max_f = f[i];
[ ⑤ ];
}
}
for (i = 1; i <= n; i++)
cout << f[i] << endl;
cout << ans << endl;
return 0;
}
{{ multiselect(27) }}
- 0
- 1
- 2
- -1
- -2
{{ multiselect(28) }}
- y[j] < y[i]
- y[i] > y[j]
- y[i] >= y[j]
- y[i] <= y[j]
{{ multiselect(29) }}
- f[i]++
- ++f[i]
- f[i] = f[i] + 1
- f[i] --
- --f[i]
- f[i] = f[i] - 1
{{ multiselect(30) }}
- f[i] >= max_f
- max_f <= f[i]
- f[i] > max_f
- max_f < f[i]
{{ multiselect(31) }}
- ans = i
- ans = j
完善程序（排列数）**输入两个正整数n，m（1<n<20,1<m<n），在1~n中任取m个数，按字典序从小到大输出所有这样的排列。 例如： 输入：3 2 输出：1 2 1 3 2 1 2 3 3 1 3 2
#include <iostream>
#include <cstring>
using namespace std;
const int SIZE = 25;
bool used[SIZE];
int data[SIZE];
int n, m, i, j, k;
bool flag;
int main()
{
cin >> n >> m;
memset(used, false, sizeof(used));
for (i = 1; i <= m; i++)
{
data[i] = i;
used[i] = true;
}
flag = true;
while (flag)
{
for (i = 1; i <= m - 1; i++)
cout << data[i] << " ";
cout << data[m] << endl;
flag = [ ① ];
for (i = m; i >= 1; i--)
{
[ ② ];
for (j = data[i] + 1; j <= n; j++)
if (!used[j])
{
used[j] = true;
data[i] = [ ③ ];
flag = true;
break;
}
if (flag)
{
for (k = i + 1; k <= m; k++)
for (j = 1; j <= [ ④ ]; j++)
if (!used[j])
{
data[k] = j;
used[j] = true;
break;
}
[ ⑤ ];
}
}
}
return 0;
}
{{ multiselect(32) }}
- false
- -1
{{ multiselect(33) }}
- used[data[i]] = false
- data[used[i]] = false
- used[data[i]] = true
- data[used[i]] = true
{{ multiselect(34) }}
- j
- i
{{ multiselect(35) }}
- n
- m
- i
- j
{{ multiselect(36) }}
- break
- continue