#1186. NOIP 2012 普及组初赛试题
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