这是什么： NOIP 普及组初赛 12 套（2007–2018）的完整题面。只有题面，没有答案。
这 12 套不能当套卷限时做。 原因有两个：
① 题型已经作废。 2019 年 CSP 改制后，考法完全变了：
| NOIP 2007–2018 | CSP 2019 起（你要考的） | |
|---|---|---|
| 单选题 | 20 题 × 1.5 分 | 15 题 × 2 分 |
| 问题求解 | 有，填空作答 | 取消了 |
| 阅读程序 | 有，写出运行结果（填空） | 改成判断题 + 选择题 |
| 完善程序 | 填代码（填空） | 改成五选一 |
「填空作答」全部取消了——现在整张卷子都是选择题和判断题。按 NOIP 的方式练，练的是一种不再考的能力。
② 没有答案。 这些卷子的答案我没有逐题做（那是另外 400 多道题的工作量）。你自己做完无法核对，练了也不知道对错。
当知识点题库翻。 这 12 套里的单项选择题，考的知识点和现在完全一致——计算机常识、进制、排列组合、树与图、排序、复杂度。
📝 推荐用法：按知识点检索。 比如你学完
E5_树与二叉树.md
之后，在本文里搜「二叉树」「完全二叉树」「哈夫曼」，把搜到的题都做一遍，当作该章节的加练。
📝 看到不会的、拿不准的，记下来拿到答疑窗口问 —— 比做一整套更划算。
⚠️ 别在这份材料上花超过总复习时间的两成。
你的主战场是 E11（2019–2025 那 7 套带答案的）。
以下哪一种设备属于输出设备
A. 扫描仪 B. 键盘 C. 鼠标 D. 打印机
下列四个不同进制的数中，与其它三项数值上不相等的是
A. B. C. D.
等于（ ）
A. 字节 B. 字节 C. 字节 D. 字节
广域网的英文缩写是（ ）
A. LAN B. WAN C. MAN D. LNA
中国计算机学会于（ ）年创办全国青少年计算机程序设计竞赛。
A. 1983 B. 1984 C. 1985 D. 1986
如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照 CapsLock、 字母键 A、字母键 S、字母键 D、字母键 F 的顺序循环按键，即 CapsLock、A、S、D、F、CapsLock、A、S、D、F、……，屏幕上输出的第 81 个字符是字母 （ ）
A. A B. S C. D D. a
根节点深度为 ，一棵深度为 的满 叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 个子结点的树，共有（ ）个结点。
A. B. C. D.
以下排序算法中，不需要进行关键字比较操作的算法是（ ）。
A. 基数排序 B. 冒泡排序 C. 堆排序 D. 直接插入排序
给定一个含 个不相同数字的数组，在最坏情况下，找出其中最大或最小的 数，至少需要 次比较操作。则最坏情况下，在该数组中同时找最大与 最小的数至少需要（ ）次比较操作。（ 表示向上取整， 表示向下取整）
A. B. C. D.
下面的故事与（ ）算法有着异曲同工之妙。
从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’”
A. 枚举 B. 递归 C. 贪心 D. 分治
由四个没有区别的点构成的简单无向连通图的个数是（ ）。
A. 6 B. 7 C. 8 D. 9
设含有 个元素的集合的全部子集数为 ，其中由 个元素组成的子集数为 ，则 的值为（ ）。
A. B. C. D.
以内，与 互质的正整数有（ ）个。
A. 2000 B. 4000 C. 6000 D. 8000
为了统计一个非负整数的二进制形式中 的个数，代码如下：
int CountBit(int x)
{
int ret = 0;
while (x)
{
ret++;
___________;
}
return ret;
}则空格内要填入的语句是（ ）。
A. x >>= 1 B. x &= x - 1 C.
x |= x >> 1 D. x <<= 1
下图中所使用的数据结构是（ ）。
A. 哈希表 B. 栈 C. 队列 D. 二叉树
甲乙丙丁四人在考虑周末要不要外出郊游。
已知①如果周末下雨，并且乙不去，则甲一定不去；②如果乙去，则丁一定去；③如果丙去，则丁一定不去；④如果丁不去，而且甲不去，则丙一定不去。
如果周末丙去了，则甲________，乙________，丁________，周末________。
（1）（1 分）
A. 去了 B. 没去
（2）（1 分）
A. 去了 B. 没去
（3）（1 分）
A. 去了 B. 没去
（4）（2 分）
A. 下雨 B. 没下雨
从 到 这 个数中，共有__________个包含数字 的数。
阅读程序写结果:
#include <stdio.h>
char st[100];
int main() {
scanf("%s", st);
for (int i = 0; st[i]; ++i) {
if (‘A’ <= st[i] && st[i] <= ‘Z’)
st[i] += 1;
}
printf("%s\n", st);
return 0;
}输入：QuanGuoLianSai
阅读程序写结果:
#include <stdio.h>
int main() {
int x;
scanf("%d", &x);
int res = 0;
for (int i = 0; i < x; ++i) {
if (i * i % x == 1) {
++res;
}
}
printf("%d", res);
return 0;
}输入：15
阅读程序写结果:
#include <iostream>
using namespace std;
int n, m;
int findans(int n, int m) {
if (n == 0) return m;
if (m == 0) return n % 3;
return findans(n - 1, m) - findans(n, m - 1) + findans(n - 1, m - 1);
}
int main(){
cin >> n >> m;
cout << findans(n, m) << endl;
return 0;
}输入：5 6
阅读程序写结果:
#include <stdio.h>
int n, d[100];
bool v[100];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", d + i);
v[i] = false;
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (!v[i]) {
for (int j = i; !v[j]; j = d[j]) {
v[j] = true;
}
++cnt;
}
}
printf("%d\n", cnt);
return 0;
}输入：10 7 1 4 3 2 5 9 8 0 6
完善程序
（最大公约数之和）下列程序想要求解整数 的所有约数两两之间最大公约数的和对 求余后的值，试补全程序。（第一空 分，其余 分）
举例来说， 的所有约数是 。 和 的最大公约数为 ； 和 的最大公约数为 ； 和 的最大公约数为 。于是答案为 。
要求 getDivisor 函数的复杂度为 ，gcd 函数的复杂度为。
#include <iostream>
using namespace std;
const int N = 110000, P = 10007;
int n;
int a[N], len;
int ans;
void getDivisor() {
len = 0;
for (int i = 1; ① <= n; ++i)
if (n % i == 0) {
a[++len] = i;
if ( ② != i) a[++len] = n / i;
}
}
int gcd(int a, int b) {
if (b == 0) {
③ ;
}
return gcd(b, ④ );
}
int main() {
cin >> n;
getDivisor();
ans = 0;
for (int i = 1; i <= len; ++i) {
for (int j = i + 1; j <= len; ++j) {
ans = ( ⑤ ) % P;
}
}
cout << ans << endl;
return 0;
}（1）（2 分）
（2）（3 分）
（3）（3 分）
（4）（3 分）
（5）（3 分）
对于一个
到
的排列
（即
到
中每一个数在
中出现了恰好一次），令 q[i] 为第
个位置之后第一个比 P[i]
值更大的位置，如果不存在这样的位置，则
q[i] = n + 1。举例来说，如果 n = 5 且 P 为
1 5 4 2 3 ，则 q 为2 6 6 5 6。
下列程序读入了排列 ，使用双向链表求解了答案。试补全程序。
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int L[N], R[N], a[N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
① ;
}
for (int i = 1; i <= n; ++i) {
R[i] = ② ;
L[i] = i - 1;
}
for (int i = 1; i <= n; ++i) {
L[ ③ ] = L[a[i]];
R[L[a[i]]] = R[ ④ ];
}
for (int i = 1; i <= n; ++i) {
cout << ⑤ << " ";
}
cout << endl;
return 0;
}（1）（3 分）
（2）（2 分）
（3）（3 分）
（4）（3 分）
（5）（3 分）
在 位二进制补码中， 表示的数是十进制下的（ ）。
A. 43 B. -85 C. -43 D. -84
计算机存储数据的基本单位是（ ）。
A. bit B. Byte C. GB D. KB
下列协议中与电子邮件无关的是（ ）。
A. POP3 B. SMTP C. WTO D. IMAP
分辨率为 、 位色的位图，存储图像信息所需的空间为（ ）。
A. B. C. D.
计算机应用的最早领域是（ ）。
A. 数值计算 B. 人工智能 C. 机器人 D. 过程控制
下列不属于面向对象程序设计语言的是（ ）。
A. C B. C++ C. Java D. C#
NOI 的中文意思是（ ）。
A. 中国信息学联赛 B. 全国青少年信息学奥林匹克竞赛 C. 中国青少年信息学奥林匹克竞赛 D. 中国计算机协会
2017 年 10 月 1 日是星期日，1999 年 10 月 1 日是（ ）。
A. 星期三 B. 星期日 C. 星期五 D. 星期二
甲、乙、丙三位同学选修课程，从 4 门课程中，甲选修 2 门，乙、丙各选修3门，则不同的选修方案共有（ ）种。
A. 36 B. 48 C. 96 D. 192
设 是有 个结点、 条边 的连通图，必须删去 的（ ）条边，才能使得 变成一棵树。
A. B. C. D.
对于给定的序列 ，我们把 称为逆序对当且仅当 且 。那么序列 的逆序对数为（ ）个。
A. 4 B. 5 C. 6 D. 7
表达式 的后缀形式是（ ）。
A. B. C. D.
向一个栈顶指针为 的链式栈中插入一个指针 指向的结点时，应执行（ ）。
A. hs->next = s; B.
s->next = hs; hs = s; C.
s->next = hs->next; hs->next = s; D.
s->next = hs; hs = hs->next;
若串 ，其子串的个数是（ ）。
A. 72 B. 45 C. 46 D. 36
十进制小数 对应的二进制数是（ ）。
A. 1101.011 B. 1011.011 C. 1101.101 D. 1010.01
对于入栈顺序为 的序列，下列（ ）不可能是合法的出栈序列。
A. B. C. D.
设 和 是两个长为 的有序数组，现在需要将 和 合并成一个排好序的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做（ ）次比较。
A. B. C. D.
从（ ）年开始，NOIP 竞赛将不再支持 Pascal 语言。
A. 2020 B. 2021 C. 2022 D. 2023
一家四口人，至少两个人生日属于同一月份的概率是（ ）（假定每个人生日属于每个月份的概率相同且不同人之间相互独立）。
A. B. C. D.
以下和计算机领域密切相关的奖项是（ ）。
A. 奥斯卡奖 B. 图灵奖 C. 诺贝尔奖 D. 普利策奖
一个人站在坐标
处，面朝
轴正方向。第一轮，他向前走
单位距离，然后右转；第二轮，他向前走
单位距离，然后右转；第三轮，他向前走
单位距离，然后右转……他一直这么走下去。请问第
轮后，他的坐标是：（ _________ , _________
）。（请在答题纸上用逗号隔开两空答案）
如下图所示，共有
个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由
变
，或由
变
）。现在要使得所有的格子中的数字都变为
，至少需要_________次操作。
阅读程序写结果：
#include<iostream>
using namespace std;
int main()
{
int t[256];
string s;
int i;
cin >> s;
for (i = 0; i < 256; i++)
t[i] = 0;
for (i = 0; i < s.length(); i++)
t[s[i]]++;
for (i = 0; i < s.length(); i++)
if (t[s[i]] == 1)
{
cout << s[i] << endl;
return 0;
}
cout << "no" << endl;
return 0;
}输入：xyzxyw
输出：_________
阅读程序写结果：
#include<iostream>
using namespace std;
int g(int m, int n, int x)
{
int ans = 0;
int i;
if (n == 1)
return 1;
for (i = x; i <= m / n; i++)
ans += g(m - i, n - 1, i);
return ans;
}
int main()
{
int t, m, n;
cin >> m >> n;
cout << g(m, n, 0) << endl;
return 0;
}
输入：7 3
输出：_________
阅读程序写结果：
#include<iostream>
using namespace std;
int main()
{
string ch;
int a[200];
int b[200];
int n, i, t, res;
cin >> ch;
n = ch.length();
for (i = 0; i < 200; i++)
b[i] = 0;
for (i = 1; i <= n; i++)
{
a[i] = ch[i - 1] - '0';
b[i] = b[i - 1] + a[i];
}
res = b[n];
t = 0;
for (i = n; i > 0; i--)
{
if (a[i] == 0)
t++;
if (b[i - 1] + t < res)
res = b[i - 1] + t;
}
cout << res << endl;
return 0;
}输入：1001101011001101101011110001
输出：_________
阅读程序写结果：
#include<iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int x = 1;
int y = 1;
int dx = 1;
int dy = 1;
int cnt = 0;
while (cnt != 2)
{
cnt = 0;
x = x + dx;
y = y + dy;
if (x == 1 || x == n)
{
++cnt;
dx = -dx;
}
if (y == 1 || y == m)
{
++cnt;
dy = -dy;
}
}
cout << x << " " << y << endl;
return 0;
}输入 1：4 3
输出 1：_________（3 分）
输入 2：2017 1014
输出 2：_________（5 分）
（1）（3 分）
（2）（5 分）
完善程序：
（快速幂） 请完善下面的程序，该程序使用分治法求
的值。（第一空
分，其余
分）
输入：三个不超过
的正整数
。
输出：的值。
提示：若
为偶数，；若
为奇数，。
#include<iostream>
using namespace std;
int x, p, m, i, result;
int main(){
cin >> x >> p >> m;
result = ①;
while (②){
if (p % 2 == 1)
result = ③;
p /= 2;
x = ④;
}
cout << ⑤ << endl;
return 0;
}（1）（2 分）
（2）（3 分）
（3）（3 分）
（4）（3 分）
（5）（3 分）
完善程序：
（切割绳子） 有
条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出
条长度相同的绳段，求绳段的最大长度是多少。（第一、二空
分，其余
分）
输入：第一行是一个不超过 的正整数 ，第二行是 个不超过 的正整数，表示每条绳子的长度，第三行是一个不超过 的正整数 。
输出：绳段的最大长度，若无法切割，输出 Failed。
#include<iostream>
using namespace std;
int n, m, i, lbound, ubound, mid, count;
int len[100]; // 绳子长度
int main()
{
cin >> n;
count = 0;
for (i = 0; i < n; i++)
{
cin >> len[i];
①;
}
cin >> m;
if (②)
{
cout << "Failed" << endl;
return 0;
}
lbound = 1;
ubound = 1000000;
while (③)
{
mid = ④;
count = 0;
for (i = 0; i < n; i++)
⑤;
if (count < m)
ubound = mid - 1;
else
lbound = mid;
}
cout << lbound << endl;
return 0;
}（1）（2.5 分）
（2）（2.5 分）
（3）（3 分）
（4）（3 分）
（5）（3 分）
以下不是微软公司出品的软件是（）
A. Powerpoint B. Word C. Excel D. Acrobat Reader
如果 种颜色用二进制编码来表示，至少需要（ ）位。
A. 6 B. 7 C. 8 D. 9
以下不属于无线通信技术的是（ ）。
A. 蓝牙 B. Wifi C. GPRS D. 以太网
以下不是 CPU 生产厂商的是（ ）。
A. Intel B. AMD C. Microsoft D. IBM
以下不是存储设备的是（ ） 。
A. 光盘 B. 磁盘 C. 固态硬盘 D. 鼠标
如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照 CapsLock、字母键 A、字母键 S 和字母键 D 的顺序循环按键，即 CapsLock、A、S、D、CapsLock、A、S、D、……，屏幕上输出的第 个字符是字母（ ）。
A. A B. S C. D D. a
二进制数 和 的和（ ）。
A. 00101000 B. 01000001 C. 01000100 D. 00111000
与二进制小数 相等的八进制数是（）。
A. 0.8 B. 0.4 C. 0.2 D. 0.1
以下是 32 位机器和 64 位机器的区别是（ ）。
A. 显示器不同 B. 硬盘大小不同 C. 寻址空间不同 D. 输入法不同
以下关于字符串的判定语句中正确的是（）。
A. 字符串是一种特殊的线性表 B. 串的长度必须大于零 C. 字符串不可以用数组来表示 D. 空格字符组成的串就是空串
一棵二叉树如右图所示，若采用顺序存储结构，即用一
维数组元素存储该二叉树中的结点（根结点的下标为
，
若某结点的下标为
，则其左孩子位于下标
处、右孩 子位于下标
处），则图中所有结点的最大下标为（ ）。
A. 6 B. 10 C. 12 D. 15
若有如下程序段，其中 均已定义为整型变量，且 均已赋值 （ 大于 ）。
s = a;
for (b = 1;b <= c; b++ )
s = s + 1;则与上述程序段修改 值的功能等价的赋值语句是（）。
A. s = a + b; B. s = a + c; C.
s = s + c; D. s = b + c;
有以下程序：
#include <iostream>
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;
}程序运行后输出的结果是（ ）。
A. 2,2 B. 2,3 C. 3,2 D. 3,3
给定含有 个不同的数的数组 。如果 中存在 使得 ， 则称 是单峰的，并称 是 的“峰顶”。现在已知 是单峰的,请把 a-c 三行代码补全到算法中使得算法 正确找到 的峰顶。
a. Search(k+1, n)
b. Search(1, k-1)
c. return L[k]
Search(1, n)
1. k←⌊n/2⌋
2. if L[k] > L[k-1] and L[k] > L[k+1]
3. then __________
4. else if L[k] > L[k-1] 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
设简单无向图 有 条边且每个顶点的度数都是 ，则图 有( )个顶点。
A. 10 B. 12 C. 8 D. 16
有 个一模一样的苹果，放到 个一样的盘子中，一共有（）种放法。
A. B. C. D.
下图表示一个果园灌溉系统，有
四个阀门，每个阀门可以打开或关上，所有管道粗细相同，以下设置阀门的方法中，可以让果树浇上水的是（）。
A. B 打开，其他都关上 B. AB 都打开，CD 都关上 C. A 打开，其他都关上 D. D 打开，其他都关上
Lucia
和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表不是朋友。这个社交网站的规则是：如果某人
A 向他（她）的朋友 B 分享了某张照片，那么 B 就可以对该照片进行评论；如果
B
评论了该照片，那么他（她）的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照片进行评论（除非
A 也向他（她）分享了该照片）。现在 Lucia
已经上传了一张照片，但是她不想让 Jacob
看见这张照片，那么她可以向以下朋友 （ ）分享该照片。
A. Dana, Michael, Eve B. Dana, Eve, Monica C. Michael, Eve, Jacob D. Micheal, Peter, Monica
周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负责切菜、妈妈负责炒菜。假设做每道菜的顺序都是：先洗菜 10 分钟，然后切菜 10 分钟，最后炒菜 10 分钟。那么做一道菜需要 30 分钟。注意：两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗，也不能同时切。那么做完三道菜的最短时间需要（ ）分钟。
A. 90 B. 60 C. 50 D. 40
参加 NOI 比赛，以下不能带入考场的是（）。
A. 钢笔 B. 适量的衣服 C. U 盘 D. 铅笔
从一个 的棋盘（不可旋转）中选取不在同一行也不在同一列上的两个方格，共有_______种方法。
约定二叉树的根节点高度为 。一棵结点数为 的二叉树最少有（）个叶子结点；一棵结点数为 的二叉树最小的高度值是（ ）。
（1）（2 分）
（2）（3 分）
阅读程序写结果：
#include <iostream>
using namespace std;
int main()
{
int max, min, sum, count = 0;
int tmp;
cin >> tmp;
if (tmp == 0)
return 0;
max = min = sum = tmp;
count++;
while (tmp != 0)
{
cin >> tmp;
if (tmp != 0)
{
sum += tmp;
count++;
if (tmp > max)
max = tmp;
if (tmp < min)
min = tmp;
}
}
cout << max << "," << min << "," << sum / count << endl;
return 0;
}输入: 1 2 3 4 5 6 0 7 输出： _________
阅读程序写结果：
#include <iostream>
using namespace std;
int main()
{
int i = 100, x = 0, y = 0;
while (i > 0)
{
i--;
x = i % 8;
if (x == 1)
y++;
}
cout << y << endl;
return 0;
}输出：____
阅读程序写结果：
#include <iostream>
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;
}输出：____
阅读程序写结果：
#include <iostream>
using namespace std;
int main()
{
int i, length1, length2;
string s1, s2;
s1 = "I have a dream.";
s2 = "I Have A Dream.";
length1 = s1.size();
length2 = s2.size();
for (i = 0; i < length1; i++)
if (s1[i] >= 'a' && s1[i] <= 'z')
s1[i] -= 'a' - 'A';
for (i = 0; i < length2; i++)
if (s2[i] >= 'a' && s2[i] <= 'z')
s2[i] -= 'a' - 'A';
if (s1 == s2)
cout << "=" << endl;
else if (s1 > s2)
cout << ">" << endl;
else
cout << "<" << endl;
return 0;
}输出：_________
完善程序： （读入整数）
请完善下面的程序，使得程序能够读入两个 int 范围内的整数，
并将这两个整数分别输出，每行一个。（第一、五空
分，其余
分）
输入的整数之间和前后只会出现空格或者回车。输入数据保证合法。
例如：
输入：
123 -789 输出：
123
-789 程序：
#include <iostream>
using namespace std;
int readint(){
int num = 0; // 存储读取到的整数
int negative = 0; // 负数标识
char c; // 存储当前读取到的字符
c = cin.get();
while ((c < '0' || c > '9') && c != '-')
c = ①;
if (c == '-')
negative = 1;
else
②;
c = cin.get();
while (③){
④;
c = cin.get();
}
if (negative == 1)
⑤;
return num;
}
int main()
{
int a, b;
a = readint();
b = readint();
cout << a << endl
<< b << endl;
return 0;
}（1）（2 分）
（2）（3 分）
（3）（3 分）
（4）（3 分）
（5）（2 分）
完善程序：
（郊游活动）有 名同学参加学校组织的郊游活动，已知学校给这 名同学的郊游总经费为 元，与此同时第 位同学自己携带了 元。为了方便郊游，活动地点提供 辆自行车供人租用，租用第 辆自行车的价格为 元，每位同学可以使用自己携带的钱或者学校的郊游经费，为了方便账务管理，每位同学只能为自己租用自行车，且不会借钱给他人，他们想知道最多有多少位同学能够租用到自行车。（第四、五空 分，其余 分）
本题采用二分法。对于区间 ，我们取中间点 并判断租用到自行车的人数能否达到 。判断的过程是利用贪心算法实现的。
#include <iostream>
using namespace std;
#define MAXN 1000000
int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid;
bool check(int nn) {
int count = 0, i, j;
i = ①;
j = 1;
while (i <= n) {
if(②)
count += C[j] - M[i];
i++;
j++;
}
return ③;
}
void sort(int a[], int l, int r) {
int i = l, j = r, x = a[(l + r) / 2], y;
while (i <= j) {
while (a[i] < x) i++;
while (a[j] > x) j--;
if (i <= j) {
y = a[i]; a[i] = a[j]; a[j] = y;
i++; j--;
}
}
if (i < r) sort(a, i, r);
if (l < j) sort(a, l, j);
}
int main() {
int i;
cin >> n >> B >> A;
for (i = 1; i <= n; i++)
cin >> M[i];
for (i = 1; i <= B; i++)
cin >> C[i];
sort(M, 1, n);
sort(C, 1, B);
l = 0;
r = n;
while (l <= r) {
mid = (l + r) / 2;
if(④){
ans = mid;
l = mid + 1;
}else
r = ⑤;
}
cout << ans << endl;
return 0;
}（1）（3 分）
（2）（3 分）
（3）（3 分）
（4）（2 分）
（5）（2 分）
等于( )。
A. 字节 B. 字节 C. 字节 D. 字节
在 PC 机中，PENTIUM（奔腾）、酷睿、赛扬等 是指( )。
A. 生产厂家名称 B. 硬盘的型号 C. CPU 的型号 D. 显示器的型号
操作系统的作用是( )。
A. 把源程序译成目标程序 B. 便于进行数据管理 C. 控制和管理系统资源 D. 实现硬件之间的连接
在计算机内部用来传送、存贮、加工处理的数据或指令都是以( )形式进行的。
A. 二进制码 B. 八进制码 C. 十进制码 D. 智能拼音码
下列说法正确的是( )。
A. CPU 的主要任务是执行数据运算和程序控制 B. 存储器具有记忆能力，其中信息任何时候都不会丢失 C. 两个显示器屏幕尺寸相同，则它们的分辨率必定相同 D. 个人用户只能使用 Wifi 的方式连接到 Internet
二进制数 和 的和是( )。
A. B. C. D.
与二进制小数 相等的十六进制数是( )。
A. 0.8 B. 0.4 C. 0.2 D. 0.1
所谓的“中断”是指( )。
A. 操作系统随意停止一个程序的运行 B. 当出现需要时，CPU 暂时停止当前程序的执行转而执行处理新情况的过程 C. 因停机而停止一个程序的运行 D. 电脑死机
计算机病毒是( )。
A. 通过计算机传播的危害人体健康的一种病毒 B. 人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 C. 一种由于计算机元器件老化而产生的对生态环境有害的物质 D. 利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒
FTP 可以用于( )。
A. 远程传输文件 B. 发送电子邮件 C. 浏览网页 D. 网上聊天
下面哪种软件不属于即时通信软件( )。
A. QQ B. MSN C. 微信 D. P2P
个顶点的连通图的最小生成树，其边数为( )。
A. 6 B. 5 C. 7 D. 4
链表不具备的特点是( )。
A. 可随机访问任何一个元素 B. 插入、删除操作不需要移动元素 C. 无需事物估计存储空间大小 D. 所需存储空间与存储元素个数成正比
线性表若采用链表存储结构，要求内存中可用存储单元地址( )。
A. 必须连续 B. 部分地址必须连续 C. 一定不连续 D. 连续不连续均可
今有一空栈 ，对下列待进栈的数据元素序列 依次进行进栈，进栈，出栈，进栈， 进栈，出栈的操作，则此操作完成后，栈 的栈顶元素为:
A. f B. c C. a D. b
前序遍历序列与中序遍历序列相同的二叉树为( )。
A. 根结点无左子树 B. 根结点无右子树 C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树 D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树
如果根的高度为 ，具有 个结点的完全二叉树的高度为（ ）。
A. 5 B. 6 C. 7 D. 8
下列选项中不属于视频文件格式的是( )。
A. TXT B. AVI C. MOV D. RMVB
某算法的计算时间表示为递推关系式 （ 为正整数）及 ，则该算法的时间复杂度为( )。
A. B. C. D.
在 NOI 系列赛事中参赛选手必须使用累承办单位统一提供的设备。下列物品中不允许选手自带的是( )。
A. 鼠标 B. 笔 C. 身份证 D. 准考证
重新排列 使得每一个数字都不在原来的位置上，一共有__种排法。
一棵结点数为 的二叉树最多有___个叶子结点。
阅读程序写结果：
#include <iostream>
using namespace std;
int main()
{
int a, b, c; a = 1;
b = 2;
c = 3;
if(a > b)
if(a > c)
cout << a << ' ';
else
cout << b << ' ';
cout << c << endl;
return 0;
}输出：____
阅读程序写结果：
#include <iostream>
using namespace std;
struct point
{
int x;
int y;
};
int main()
{
int a, b, c;
struct EX
{
int a;
int b;
point c;
} e;
e.a = 1;
e.b = 2;
e.c.x= e.a + e.b;
e.c.y= e.a * e.b;
cout << e.c.x << ',' << e.c.y << endl;
return(0);
}阅读程序写结果：
#include <iostream>
#include <string>
using namespace std;
int main()
{
string str;
int i;
int count; count = 0;
getline( cin, str );
for ( i = 0; i < str.length(); i++ )
if ( str[i] >= 'a' && str[i] <= 'z' )
count++;
cout << "It has " << count << " lowercases" << endl; return(0);
}输入：NOI2016 will be held in Mian Yang.
输出：_______
阅读程序写结果：
#include <iostream>
#include <string>
using namespace std;
void fun( char *a, char *b )
{
a = b;
(*a)++;
}
int main()
{
char c1, c2, *p1, *p2;
c1 = 'A';
c2 = 'a';
p1 = &c1;
p2 = &c2;
fun( p1, p2 );
cout << c1 << c2 << endl;
return(0);
}完善程序：
（打印日历） 输入月份
，按一定格式打印
年第
月的月历。（第三、四空
分， 其余
分）
例如，
年
月的月历打印效果如下（第一列为周日）：
S M T W T F S
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31#include <iostream>
#include <string>
using namespace std;
const int dayNum[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int m, offset, i;
int main()
{
cin >> m;
cout << "S\tM\tT\tW\tT\tF\tS" << endl; /* '\t'为 TAB 制表符 */
①;
for (i = 1; i < m; i++)
offset = ②;
for (i = 0; i < offset; i++)
cout << '\t';
for (i = 1; i <= ③; i++)
{
cout << ④;
if (i == dayNum[m] || ⑤ == 0)
cout << endl;
else
cout << '\t';
}
return (0);
}（1）（3 分）
（2）（3 分）
（3）（2 分）
（4）（2 分）
（5）（3 分）
完善程序：
（中位数 median） 给定
（
为奇数且小于
）个整数，整数的范围在
之间，请使用二分法求这
个整数的中位数。所谓中位数，是指将这
个数排序之后，排在正中间的数。(第五空
分，其余
分)
#include <iostream>
using namespace std;
const int MAXN = 1000;
int n, i, lbound, rbound, mid, m, count;
int x[MAXN];
int main()
{
cin >> n >> m;
for (i = 0; i < n; i++)
cin >> x[i];
lbound = 0;
rbound = m;
while (①)
{
mid = (lbound + rbound) / 2;
②;
for (i = 0; i < n; i++)
if (③)
④;
if (count > n / 2)
lbound = mid + 1;
else
⑤;
cout << mid << " " << lbound << " " << rbound << " " << count << endl;
}
cout << rbound << endl;
return (0);
}（1）（3 分）
（2）（3 分）
（3）（3 分）
（4）（3 分）
（5）（2 分）
以下哪个是面向对象的高级语言( )。
A. 汇编语言 B. C++ C. Fortran D. Basic
代表的字节数是( )。
A. 的 次方 B. 的 次方 C. 的 次方 D. 的 次方
二进制数 和 的和是( )。
A. 00101000 B. 001010100 C. 01000101 D. 00111001
以下哪一种设备属于输出设备( )。
A. 扫描仪 B. 键盘 C. 鼠标 D. 打印机
下列对操作系统功能的描述最为完整的是( )。
A. 负责外设与主机之间的信息交换 B. 负责诊断机器的故障 C. 控制和管理计算机系统的各种硬件和软件资源的使用 D. 将没有程序编译成目标程序
CPU、存储器、I/O 设备是通过( )连接起来的。
A. 接口 B. 总线 C. 控制线 D. 系统文件
断电后会丢失数据的存储器是( )。
A. RAM B. ROM C. 硬盘 D. 光盘
以下哪一种是属于电子邮件收发的协议( )。
A. SMTP B. UDP C. P2P D. FTP
下列选项中不属于图像格式的是( )。
A. JPEG 格式 B. TXT 格式 C. GIF 格式 D. PNG 格式
链表不具有的特点是( )。
A. 不必事先估计存储空间 B. 可随机访问任一元素 C. 插入删除不需要移动元素 D. 所需空间与线性表长度成正比
下列各无符号十进制整数中，能用八位二进制表示的数中最大的是( )。
A. 296 B. 133 C. 256 D. 199
下列几个 位 IP 地址中，书写错误的是( )。
A. 162.105.135.27 B. 192.168.0.1 C. 256.256.129.1 D. 10.0.0.1
要求以下程序的功能是计算：。
#include <iostream>
using namespace std;
int main()
{
int n;
float s;
s = 1.0;
for(n = 10; n > 1; n--)
s = s + 1 / n;
cout << s << endl;
return 0;
} 程序运行后输出结果错误，导致错误结果的程序行是( )。
A. s = 1.0; B. for(n = 10; n > 1; n--)
C. s = s + 1 / n; D.
cout << s << endl;
设变量 为 float 型且已赋值，则以下语句中能将 中的数值保留到小数点后两位，并将第三位四舍五入的是( )。
A. x = (x * 100) + 0.5 / 100.0; B.
x = (x * 100 + 0.5) / 100.0; C.
x = (int)(x * 100 + 0.5)/100.0; D.
x = (x / 100 + 0.5) * 100.0;
有以下程序:
#include <iostream>
using namespace std;
int main()
{
int s, a, n;
s= 0;
a= 1;
cin >> n;
do
{
s+= 1;
a-= 2;
}
while ( a != n );
cout << s << endl;
return(0);
}若要使程序的输出值为 ，则应该从键盘给 输入的值是( )。
A. -1 B. -3 C. -5 D. 0
一棵具有 层的满二叉树中结点数为( )。
A. 31 B. 32 C. 33 D. 16
有向图中每个顶点的度等于该顶点的( )。
A. 入度 B. 出度 C. 入度和出度之和 D. 入度和出度之差
设有 个数据元素，采用折半搜索时，最大比较次数为( )。
A. 6 B. 7 C. 8 D. 10
若有如下程序段，其中 均已定义为整型变量，且 均已赋值，。
s = a;
for(b = 1; b <= c; b++) s += 1; 则与上述程序段功能等价的赋值语句是( )。
A. s = a + b B. s = a + c C.
s = s + c D. s = b + c
计算机界的最高奖是( )。
A. 菲尔兹奖 B. 诺贝尔奖 C. 图灵奖 D. 普利策奖
把 个同样的球放到 个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的放置方法？(用 表示)。
例如， 时，；在这里认为 和 是同一种放置方法。 问： 时，______
如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是__。
阅读程序写结果：
#include <iostream>
using namespace std;
int main()
{
int a, b, c, d, ans;
cin >> a >> b >> c;
d = a - b;
a = d + c;
ans = a * b;
cout << "Ans = " << ans << endl;
return(0);
}
输入：2 3 4
输出：Ans =____
阅读程序写结果：
#include <iostream>
using namespace std;
int fun(int n)
{
if(n == 1)
return 1;
if(n == 2)
return 2;
return fun(n -2) - fun(n - 1);
}
int main()
{
int n;
cin >> n;
cout << fun(n) << endl;
return 0;
} 输入：7 输出：__
阅读程序写结果：
#include <iostream>
#include <string>
using namespace std;
int main()
{
string st;
int i, len;
getline( cin, st );
len = st.size();
for ( i = 0; i < len; i++ )
if ( st[i] >= 'a' && st[i] <= 'z' )
st[i] = st[i] - 'a' + 'A';
cout << st << endl;
return(0);
}
输入：Hello, my name is Lostmonkey.
输出：________________________________
阅读程序写结果：
#include <iostream>
using namespace std;
const int SIZE = 100;
int main()
{
int p[SIZE];
int n, tot, i, cn;
tot = 0;
cin >> n;
for ( i = 1; i <= n; i++ )
p[i] = 1;
for ( i = 2; i <= n; i++ )
{
if ( p[i] == 1 )
tot++;
cn = i * 2;
while ( cn <= n )
{
p[cn] = 0;
cn += i;
}
}
cout << tot << endl;
return(0);
}输入：30
输出：___
完善程序：
(数字删除)
下面程序的功能是将字符串中的数字字符删除后输出。请填空。(每空 3 分，共
12 分)
#include <iostream>
using namespace std;
int delnum( char *s )
{
int i, j;
j = 0;
for ( i = 0; s[i] != '\0'; i++ )
if ( s[i] < '0' ① s[i] > '9' )
{
s[j] = s[i];
②;
}
return(③);
}
const int SIZE = 30;
int main()
{
char s[SIZE];
int len, i;
cin.getline( s, sizeof(s) );
len = delnum( s );
for ( i = 0; i < len; i++ )
cout << ④;
cout << endl;
return(0);
}（1）（3 分）
（2）（3 分）
（3）（3 分）
（4）（3 分）
（最大子矩阵和）给出
行
列的整数矩阵，求最大的子矩阵和(子矩阵不能为空)。
输入第一行包含两个整数
和
，即矩阵的行数和列数。之后
行，每行
个整数，描述整个矩阵。程序最终输出最大的子矩阵和。
（最后一空
分，其余
分，共
分）
比如在如下这个矩阵中：
4 4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2 拥有最大和的子矩阵为：
9 2
-4 1
-1 8 其和为
3 3
-2 10 20
-1 100 -2
0 -2 -3最大子矩阵和为
4 4
0 -2 -9 -9
-9 11 5 7
-4 -3 -7 -6
-1 7 7 5 最大子矩阵和为
#include <iostream>
using namespace std;
const int SIZE = 100;
int matrix[SIZE + 1][SIZE + 1];
int rowsum[SIZE + 1][SIZE + 1]; /* rowsum[i][j]记录第i行前j个数的和 */
int m, n, i, j, first, last, area, ans;
int main()
{
cin >> m >> n;
for ( i = 1; i <= m; i++ )
for ( j = 1; j <= n; j++ )
cin >> matrix[i][j];
ans = matrix ①;
for ( i = 1; i <= m; i++ )
②;
for ( i = 1; i <= m; i++ )
for ( j = 1; j <= n; j++ )
rowsum[i][j] = ③;
for ( first = 1; first <= n; first++ )
for ( last = first; last <= n; last++ )
{
④;
for ( i = 1; i <= m; i++ )
{
area += ⑤;
if ( area > ans )
ans = area;
if ( area < 0 )
area = 0;
}
}
cout << ans << endl;
return(0);
}（1）（3 分）
（2）（3 分）
（3）（3 分）
（4）（3 分）
（5）（4 分）
一个 位整型变量占用（ ）个字节。
A. 4 B. 8 C. 32 D. 128
二进制数 在十进制下是（ ）。
A. 3.25 B. 4.125 C. 6.25 D. 11.125
下面的故事与（ ）算法有着异曲同工之妙。 从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’”
A. 枚举 B. 递归 C. 贪心 D. 分治
逻辑表达式（）的值与变量 的真假无关。
A. (A ∨ B) ∧﹃A B. (A ∨ B) ∧﹃B C. (A ∧ B) ∨ (﹃ A ∧ B) D. (A ∨ B) ∧﹃A ∧ B
将 分别存储到某个地址区间为 的哈希表中，如果哈希函数 （ ），将不会产生冲突，其中 表示 除以 的余数。
A. B. C. D. $ \lfloor \sqrt{x} \rfloor \bmod 11$，其中 $\lfloor \sqrt{x} \rfloor $ 表示 $\sqrt{x} $ 下取整
在十六进制表示法中，字母 相当于十进制中的（ ）。
A. 9 B. 10 C. 15 D. 16
下图中所使用的数据结构是（ ）。
A. 哈希表 B. 栈 C. 队列 D. 二叉树
在 Windows 资源管理器中，用鼠标右键单击一个文件时，会出现一个名为“复制”的操作选项，它的意思是（ ）。
A. 用剪切板中的文件替换该文件 B. 在该文件所在文件夹中，将该文件克隆一份 C. 将该文件复制到剪切板，并保留原文件 D. 将该文件复制到剪切板，并删除原文件
已知一棵二叉树有 个节点，则其中至多有（ ）个节点有 个子节点。
A. 4 B. 5 C. 6 D. 7
在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有
个顶点、
条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。 
A. 1 B. 2 C. 3 D. 4
二叉树的（ ）第一个访问的节点是根节点。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 以上都是
以
作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（
）。
A. B. C. D.
IPv4 协议使用 位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被使用（ ）位地址的 IPv6 协议所取代。
A. 40 B. 48 C. 64 D. 128
（ ）的平均时间复杂度为 ，其中 是待排序的元素个数。
A. 快速排序 B. 插入排序 C. 冒泡排序 D. 基数排序
下面是根据欧几里得算法编写的函数，它所计算的是 和 的（ ）。
int euclid(int a, int b)
{
if (b == 0)
return a;
else
return euclid(b, a % b);
}A. 最大公共质因子 B. 最小公共质因子 C. 最大公约数 D. 最小公倍数
通常在搜索引擎中，对某个关键词加上双引号表示（ ）。
A. 排除关键词，不显示任何包含该关键词的结果 B. 将关键词分解，在搜索结果中必须包含其中的一部分 C. 精确搜索，只显示包含整个关键词的结果 D. 站内搜索，只显示关键词所指向网站的内容
中国的国家顶级域名是（ ）。
A. .cn B. .ch C. .chn D. .china
把 位非零浮点数强制转换成 位浮点数后，不可能（）。
A. 大于原数 B. 小于原数 C. 等于原数 D. 与原数符号相反
下列程序中，正确计算 这 个自然数之和 （初始值为 ）的是（ ）。
A. i = 1 do{ sum +=i; i++; }while(i<=100); B.
i = 1; do{ sum +=i; i++; }while(i > 100); C.
i = 1; while(i < 100){ sum+=i; i++; } D.
i = 1; while(i >= 100){ sum+=i; i++; }
CCF NOIP 复赛全国统一评测时使用的系统软件是（ ）。
A. NOI Windows B. NOI Linux C. NOI Mac OS D. NOI DOS
个同学围坐一圈，要选 个不相邻的作为代表，有_________种不同的选法。
某系统自称使用了一种防窃听的方式验证用户密码。密码是 个数 ，均为 或 。该系统每次随机生成 个数 ，均为 或 ，请用户回答 除以 的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。
然而，事与愿违。例如，当
时，有人窃听了以下
次问答：
就破解出了密码s1 =___ ，s2 = ___，s3 =___ ，s4 =___。
答案格式为：纯数字用,连接
阅读程序写结果：
#include <iostream>
using namespace std;
int main()
{
int a, b;
cin >> a >> b;
cout << a << "+" << b << "=" << a + b << endl;
}
输入： 3 5
阅读程序写结果：
#include <iostream>
using namespace std;
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
阅读程序写结果：
#include <iostream>
using namespace std;
int main()
{
const int SIZE = 100;
int n, f, i, left, right, middle, a[SIZE];
cin>>n>>f;
for (i = 1; i <= n; i++)
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
阅读程序写结果：
#include <iostream>
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++)
{
if (num[i] > ans) ans = num[i];
}
cout<<ans<<endl;
}输入：
6
2 5 3 11 12 4
完善程序： （序列重排）
全局数组变量
定义如下：
const int SIZE = 100;
int a[SIZE], n;它记录着一个长度为
的序列
。
现在需要一个函数，以整数
为参数，实现如下功能：将序列
的前
个数与后
个数对调，且不改变这
个数（或
个数）之间的相对位置。例如，长度为
的序列
，当
时重排结果为
。
有一种朴素的算法可以实现这一需求，其时间复杂度为
、空间复杂度为
：
void swap1( int p )
{
int i, j, b[SIZE];
for ( i = 1; i <= p; i++ )
b[①] = a[i]; // （3分）
for ( i = p + 1; i <= n; i++ )
b[i - p] = ②; // （3分）
for ( i = 1; i <= ③; i++ ) // （2分）
a[i] = b[i];
}我们也可以用时间换空间，使用时间复杂度为 、空间复杂度为 的算法：
void swap2( int p )
{
int i, j, temp;
for ( i = p + 1; i <= n; i++ )
{
temp = a[i];
for ( j = i; j >= ④; j-- ) // （ 3 分）
a[j] = a[j - 1];
⑤ = temp; // （ 3 分）
}
}（1）（3 分）
（2）（3 分）
（3）（2 分）
（4）（3 分）
（5）（3 分）
完善程序：
（二叉查找树） 二叉查找树具有如下性质：
每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。
输入的第一行包含一个整数
，表示这棵树有
个顶点， 编号分别为
，其中编号为
的为根结点。之后的第
行有三个数
，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点，则用
代替。输出
表示这棵树是二叉查找树，输出
则表示不是。
#include <iostream>
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) && ( ① ) && (is_bst( a[root].left_child, lower_bound, cur ) == 1) && (is_bst( ②, ③, ④ ) == 1) )
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( ⑤, -INFINITE, INFINITE ) << endl;
return(0);
}（1）（3 分）
（2）（3 分）
（3）（3 分）
（4）（3 分）
（5）（2 分）
计算机如果缺少（ ），将无法正常启动。
A. 内存 B. 鼠标 C. U 盘 D. 摄像头
（ ）是一种先进先出的线性表。
A. 栈 B. 队列 C. 哈希表（散列表） D. 二叉树
目前计算机芯片（集成电路）制造的主要原料是（ ），它是一种可以在沙子中提炼出的物质。
A. 硅 B. 铜 C. 锗 D. 铝
十六进制数 在（ ）进制下是 。
A. 四 B. 八 C. 十 D. 十二
（ ）不属于操作系统。
A. Windows B. DOS C. Photoshop D. NOI Linux
如果一棵二叉树的中序遍历是 ，那么它的先序遍历不可能是（ ）。
A. B. C. D.
目前个人电脑的（ ）市场占有率最靠前的厂商包括 Intel、AMD 等公司。
A. 显示器 B. CPU C. 内存 D. 鼠标
使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少 个逆序对，因此序列 需要执行（ ）次操作，才能完成冒泡排序。
A. 0 B. 5 C. 10 D. 15
1946 年诞生于美国宾夕法尼亚大学的 ENIAC 属于（ ）计算机。
A. 电子管 B. 晶体管 C. 集成电路 D. 超大规模集成电路
无论是 TCP/IP 模型还是 OSI 模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（ ）。
A. 中国公司的经理与波兰公司的经理交互商业文件 
B.
军队发布命令 
C.
国际会议中，每个人都与他国地位对等的人直接进行会谈 
D.
体育比赛中，每一级比赛的优胜者晋级上一级比赛 
矢量图（Vector Image）图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋转等都不会失真，是因为它（ ）。
A. 记录了大量像素块的色彩值来表示图像 B. 用点、直线或者多边形等基于数学方程的几何图元来表示图像 C. 每个像素点的颜色信息均用矢量表示 D. 把文件保存在互联网，采用在线浏览的方式查看图像
如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为 ，另有元素 已经出栈，则可能的入栈顺序是（ ）。
A. B. C. D.
（ ）是主要用于显示网页服务器或者文件系统的 HTML 文件的内容，并让用户与这些文件交互的一种软件。
A. 资源管理器 B. 浏览器 C. 电子邮件 D. 编译器
（ ）是目前互联网上常用的 E-mail 服务协议。
A. HTTP B. FTP C. POP3 D. Telnet
（ ）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题……直到最后的子问题可以简单地直接求解。而原问题的解就是子问题解的并。
A. 动态规划 B. 贪心 C. 分治 D. 搜索
地址总线的位数决定了 CPU 可直接寻址的内存空间大小，例如地址总线为 位，其最大的可寻址空间为 。如果地址总线是 位，则理论上最大可寻址的内存空间为（ ）。
A. B. C. D.
蓝牙和 Wi-Fi 都是（ ）设备。
A. 无线广域网 B. 无线城域网 C. 无线局域网 D. 无线路由器
在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。
A. 系统分配的栈空间溢出 B. 系统分配的堆空间溢出 C. 系统分配的队列空间溢出 D. 系统分配的链表空间溢出
原字符串中任意一段连续的字符所组成的新字符串称为子串。则字符 共有（ ）个不同的非空子串。
A. 3 B. 12 C. 36 D. 45
仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，并将这些原理移植于新兴的工程技术中。以下关于仿生学的叙述，错误的是（ ）
A. 由研究蝙蝠，发明雷达 B. 由研究蜘蛛网，发明因特网 C. 由研究海豚，发明声纳 D. 由研究电鱼，发明伏特电池
如果平面上任取 个整点（横纵坐标都是整数），其中一定存在两个点，它们连线的中点也是整点，那么 至少是__________。
在 NOI 期间，主办单位为了欢迎来自各国的选手，举行了盛大的晚宴。在第十八桌，有 名大陆选手和 名港澳选手共同进膳。为了增进交流，他们决定相隔就坐，即每个大陆选手左右旁都是港澳选手，每个港澳选手左右旁都是大陆选手。那么，这一桌一共有_______种不同的就坐方案。
注：如果在两个方案中，每个选手左右相邻的选手相同，则视为同一种方案。
阅读程序写结果
#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
阅读程序写结果
#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阅读程序写结果
#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 阅读程序写结果
#include <iostream>
#include <string>
using namespace std;
int n,i,j,ans;
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;
return 0;
}
输入：CBBADADA
完善程序
（坐标统计）输入 个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点（即 坐标都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。
#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;
}
（1）（2 分）
（2）（2 分）
（3）（3 分）
（4）（3 分）
（5）（3 分）
完善程序 （排列数） 输入两个正整数
，在
中任取
个数，按字典序从小到大输出所有这样的排列。
例如： 输入：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;
}（1）（3 分）
（2）（3 分）
（3）（3 分）
（4）（3 分）
（5）（3 分）
在二进制下， （ ） 。
A. B. C. D.
字符 的 ASCII 码为 ，则字符 的 ASCII 码为（ ）。
A. B. C. D. 视具体的计算机而定
一片容量为 的 SD 卡能储存大约（ ）张大小为 的数码照片。
A. B. C. D.
摩尔定律（Moore's law）是由英特尔创始人之一戈登·摩尔（Gordon Moore）提出来的。根据摩尔定律，在过去几十年一级在可预测的未来几年，单块集成电路的集成度大约每（ ）个月翻一番。
A. 1 B. 6 C. 18 D. 36
无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图 有 个顶点，则它共有（ ）条边。
A. 7 B. 21 C. 42 D. 49
寄存器是（ ）的重要组成部分。
A. 硬盘 B. 高速缓存 C. 内存 D. 中央处理器（CPU）
如果根结点的深度记为 ，则一棵恰有 个叶结点的二叉树的深度最少是（ ）。
A. 10 B. 11 C. 12 D. 13
体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（ ）算法。
A. 快速排序 B. 插入排序 C. 冒泡排序 D. 归并排序
一个正整数在二进制下有 位，则它在十六进制下有（ ）位。
A. 7 B. 13 C. 25 D. 不能确定
有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。这种想法是（ ）。
A. 正确的，将文件放入回收站以为着彻底删除、无法恢复 B. 不正确的，只有将回收站清空后，才意味着彻底删除、无法恢复 C. 不正确的，即使回收站清空，文件只是被标记为删除，仍可能通过回复软件找回 D. 不正确的，只要在硬盘上出现过的文件，永远不可能被彻底删除
广度优先搜索时，需要用到的数据结构是（ ）。
A. 链表 B. 队列 C. 栈 D. 散列表
在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（ ）。
A. 程序运行时理论上所占的内存空间 B. 程序运行时理论上所占的数组空间 C. 程序运行时理论上所占的硬盘空间 D. 程序源文件理论上所占的硬盘空间
在含有 个元素的双向链表中查询是否存在关键字为 的元素，最快情况下运行的时间复杂度是（ ）。
A. B. C. D.
生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。一下不属于生物特征识别技术及其应用的是（ ）。
A. 指静脉验证 B. 步态验证 C. ATM 机密码验证 D. 声音验证
现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由 个汉字“之”、“呼”、“者”、“也”组成，它们出现的次数分别为 。那么，“也”字的编码长度是（ ）。
A. 1 B. 2 C. 3 D. 4
关于汇编语言，下列说法错误的是（ ）
A. 是一种与具体硬件相关的程序设计语言 B. 在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试 C. 可以直接访问寄存器、内存单元、以及 I/O 端口 D. 随着高级语言的诞生，如今已完全被淘汰，不再使用
（ ）是一种选优搜索法，按选优条件向前搜索，以达到目标。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。
A. 回溯法 B. 枚举法 C. 动态规划 D. 贪心
1956 年（ ）授予肖克利、巴丁和布拉顿，以表彰他们对半导体的研究和晶体管效应的发现。
A. 诺贝尔物理学奖 B. 约翰·冯·诺依曼奖 C. 图灵奖 D. 高德纳奖
对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，下图就是一个强连通图。事实上，在删掉边（
）后，它依然是强连通的。
A. a B. b C. c D. d
从 ENIAC 到当前最先进的计算机，冯·诺依曼体系结构始终占有重要地位。冯诺依曼提醒结构的核心内容是（ ）。
A. 采用开关电路 B. 采用半导体器件 C. 采用存储程序和程序控制原理 D. 采用键盘输入
每份考卷都有一个 位二进制序列号。当且仅当一个序列号含有偶数个 时，它才是有效的。例如，、 都是有效的序列号，而 不是。那么，有效的序列号共有_____个。
定义字符串的基本操作为：删除一个字符、插入一个字符和将一个字符修改成另外一个字符这三种操作。将字符串 变成字符串 的最少操作步数，称为字符串 到字符串 的编辑距离。字符串 到字符串 的编辑距离为_____。
阅读程序写结果
#include<iostream>
using namespace std;
int main()
{
int i,n,m,ans;
cin>>n>>m;
i=n;
ans=0;
while(i<=m){
ans+=i;
i++;
}
cout<<ans<<endl;
return 0;
}
输入：10 20
阅读程序写结果
#include<iostream>
#include<string>
using namespace std;
int main()
{
string map= "2223334445556667778889999";
string tel;
int i;
cin>>tel;
for(i=0;i<tel.length();i++)
if((tel[i]>='0') && (tel[i]<='9') )
cout<<tel[i];
else if( (tel[i]>='A') && (tel[i]<='Z'))
cout<<map[tel[i]-'A'];
cout<<endl;
return 0;
}输入：CCF-NOIP-2011
阅读程序写结果
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 100;
int main()
{
int n,i,sum,x,a[SIZE];
cin>>n;
memset(a,0,sizeof(a));
for(i=1;i<=n;i++){
cin>>x;
a[x]++;
}
i=0;
sum=0;
while(sum<(n/2+1)){
i++;
sum+=a[i];
}
cout<<i<<endl;
return 0;
}输入：
11
4 5 6 6 4 3 3 2 3 2 1
阅读程序写结果
#include<iostream>
using namespace std;
int solve(int n,int m)
{
int i,sum;
if(m==1) return 1;
sum=0;
for(i=1;i<n;i++)
sum+= solve(i,m-1);
return sum;
}
int main()
{
int n,m;
cin>>n>>m;
cout<<solve(n,m)<<endl;
return 0;
}输入：7 4
完善程序 （子矩阵）给输入一个 的矩阵 ，和 的矩阵 ，问 中是否存在子矩阵和 相等。若存在，输出所有子矩阵左上角的坐标：若不存在输出 。
#include<iostream>
using namespace std;
const int SIZE = 50;
int n1,m1,n2,m2,a[SIZE][SIZE],b[SIZE][SIZE];
int main()
{
int i,j,k1,k2;
bool good ,haveAns;
cin>>n1>>m1;
for(i=1;i<=n1;i++)
for(j=1;j<=m1;j++)
cin>>a[i][j];
cin>>n2>>m2;
for(i=1;i<=n2;i++)
for(j=1;j<=m2;j++)
[ ① ];
haveAns=false;
for(i=1;i<=n1-n2+1;i++)
for(j=1;j<= [ ② ];j++){
[ ③ ];
for(k1=1;k1<=n2;k1++)
for(k2=1;k2<=[ ④ ] ;k2++){
if(a[i+k1-1][j+k2-1]!=b[k1][k2])
good=false;
}
if(good){
cout<<i<<' '<<j<<endl;
[ ⑤ ];
}
}
if(!haveAns)
cout<<"There is no answer"<<endl;
return 0;
}
（1）（2 分）
（2）（2 分）
（3）（2 分）
（4）（2 分）
（5）（2 分）
完善程序
（大整数开方） 输入一个正整数
，试用二分法计算它的平方根的整数部分。
#include<iostream>
#include<string>
using namespace std;
const int SIZE=200;
struct hugeint{
int len,num[SIZE];
};
//其中len表示大整数的位数；num[1]表示个位，num[2]表示十位，以此类推
hugeint times(hugeint a,hugeint b)
// 计算大整数a和b的乘积
{
int i,j;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
for(i=1;i<=a.len;i++)
for(j=1;j<=b.len;j++)
[ ① ] +=a.num[i]*b.num[j];
for(i=1;i<=a.len+b.len;i++){
ans.num[i+1]+=ans.num[i]/10;
[ ② ];
}
if(ans.num[a.len+b.len]>0)
ans.len=a.len+b.len;
else
ans.len=a.len+b.len-1;
return ans;
}
hugeint add(hugeint a,hugeint b)
//计算大整数a和b 的和
{
int i;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
if(a.len>b.len)
ans.len=a.len;
else
ans.len=b.len;
for(i=1;i<=ans.len;i++){
ans.num[i]+= [ ③ ] ;
ans.num[i+1]+= ans.num[i]/10;
ans.num[i]%=10;
}
if(ans.num[ans.len+1]>0)
ans.len++;
return ans;
}
hugeint average(hugeint a,hugeint b)
//计算大整数a和b的平均数的整数部分
{
int i;
hugeint ans;
ans=add(a,b);
for(i=ans.len;i>=2;i--){
ans.num[i-1]+=([ ④ ])*10;
ans.num[i]/=2;
}
ans.num[1]/=2;
if(ans.num[ans.len]==0)
ans.len--;
return ans;
}
hugeint plustwo(hugeint a)
// 计算大整数a加2之后的结果
{
int i;
hugeint ans;
ans=a;
ans.num[1]+=2;
i=1;
while( (i<=ans.len)&&(ans.num[i]>=10) ){
ans.num[i+1]+=ans.num[i]/10;
ans.num[i]%=10;
i++;
}
if(ans.num[ans.len+1]>0)
[ ⑤ ];
return ans;
}
bool over(hugeint a,hugeint b)
// 若大整数a>b则返回true，否则返回false
{
int i;
if([ ⑥ ])
return false;
if( a.len>b.len )
return true;
for(i=a.len;i>=1;i--){
if(a.num[i]<b.num[i])
return false;
if(a.num[i]>b.num[i])
return true;
}
return false;
}
int main()
{
string s;
int i;
hugeint target,left,middle,right;
cin>>s;
memset(target.num,0,sizeof(target.num));
target.len=s.length();
for(i=1;i<=target.len;i++)
target.num[i]=s[target.len-i]-[ ⑦ ];
memset(left.num,0,sizeof(left.num));
left.len=1;
left.num[1]=1;
right=target;
do{
middle=average(left,right);
if(over([ ⑧ ]))
right=middle;
else
left=middle;
}while(!over(plustwo(left),right) );
for(i=left.len;i>=1;i--)
cout<<left.num[i];
return 0;
}（1）（2 分）
（2）（2 分）
（3）（2 分）
（4）（2 分）
（5）（2 分）
（6）（2 分）
（7）（3 分）
（8）（3 分）
浮点数 2E+03 表示（ ）。
A. 2.03 B. 5 C. 8 D. 2000
一个字节（byte）由（ ）个二进制位组成。
A. 8 B. 16 C. 32 D. 以上都有可能
以下逻辑表达式的值恒为真的是（ ）。
A. P∨(¬P∧Q)∨(¬P∧¬Q) B. Q∨(¬P∧Q)∨(P∧¬Q) C. P∨Q∨(P∧¬Q)∨(¬P∧Q) D. P∨¬Q∨(P∧¬Q)∨(¬P∧¬Q)
Linux 下可执行文件的默认扩展名为（ ）。
A. exe B. com C. dll D. 以上都不是
如果树根算第 层，那么一棵 层的二叉树最多有（ ）个结点。
A. B. C. D.
提出“存储程序”的计算机工作原理的是（ ）。
A. 克劳德·香农 B. 戈登·摩尔 C. 查尔斯·巴比奇 D. 冯·诺依曼
设 分别代表三进制下的一位数字，若等式 在三进制下成立，那么同样在三进制下，等式 （ ）也成立。
A. B. C. D.
Pascal 语言、C 语言和 C++ 语言都属于（ ）。
A. 面向对象语言 B. 脚本语言 C. 解释性语言 D. 编译性语言
前缀表达式 + 3 * 2 + 5 12 的值是（ ）。
A. 23 B. 25 C. 37 D. 65
主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。而根据局部性原理，CPU 所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在 CPU 中引入了（ ）。
A. 寄存器 B. 高速缓存 C. 闪存 D. 外存
一个字长为 位的整数的补码是 ，则它的原码是（ ）。
A. B. C. D.
基于比较的排序时间复杂度的下限是（ ），其中 表示待排序的元素个数。
A. B. C. D.
一个自然数在十进制下有 位，则它在二进制下的位数与（ ）最接近。
A. B. C. D.
在下列 HTML 语句中，可以正确产生一个指向 NOI 官方网站的超链接的是（ ）。
A.
<a url="http://www.noi.cn">欢迎访问 NOI 网站</a>
B.
<a href="http://www.noi.cn">欢迎访问 NOI 网站</a>
C. <a>http://www.noi.cn</a> D.
<a name="http://www.noi.cn">欢迎访问 NOI 网站</a>
元素 入栈的顺序为 。如果第 个出栈的是 ，那么第 个出栈的不可能是（ ）。
A. B. C. D.
双向链表中有两个指针域 llink 和
rlink，分别指向该结点的前驱及后继。设
指向链表中的一个结点，它的左右结点均非空。现要求删除结点
，则下面语句序列中错误的是（
）。
A.
p->rlink->llink = p->rlink;p->llink->rlink = p->llink; delete p;
B.
p->llink->rlink = p->rlink; p->rlink->llink = p->llink; delete p;
C.
p->rlink->llink = p->llink;p->rlink->llink->rlink = p->rlink; delete p;
D.
p->llink->rlink = p->rlink;p->llink->rlink->llink = p->llink; delete p;
一棵二叉树的前序遍历序列是 ，后序遍历序列是 ，则根结点的左子树的结点个数可能是（ ）。
A. 2 B. 3 C. 4 D. 5
关于拓扑排序，下面说法正确的是（ ）。
A. 所有连通的有向图都可以实现拓扑排序 B. 对同一个图而言，拓扑排序的结果是唯一的 C. 拓扑排序中入度为 的结点总会排在入度大于 的结点的前面 D. 拓扑排序结果序列中的第一个结点一定是入度为 的点
完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的 号位置，则第 号结点的父结点如果存在的话，应当存放在数组的（ ）号位置。
A. B. C. D.
全国青少年信息学奥林匹克系列活动的主办单位是（ ）。
A. 教育部 B. 科技部 C. 共青团中央 D. 中国计算机学会
LZW 编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典，如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。
举例说明，考虑一个待编码的信息串：。初始词典只有 个条目，第一个为 ，编码为 ；第二个为 ，编码为 ；第三个为空格，编码为 ；于是串 的编码为 （其中 为编码分隔符），加上后面的一个空格就是 。但由于有了一个空格，我们就知道前面的 是一个单词，而由于该单词没有在词典中，我们就可以自适应的把这个词条添加到词典里，编码为 ，然后按照新的词典对后继信息进行编码，以此类推。于是，最后得到编码：。
现在已知初始词典的 个条目如上述，则信息串 的编码是_________。
队列快照是指在某一时刻队列中的元素组成的有序序列。例如，当元素 入队，元素 出队后，此刻的队列快照是 。当元素 也出队后，队列快照是""，即为空。现有 个正整数元素依次入队、出队。已知它们的和为 ，则共有_________种可能的不同的队列快照（不同队列的相同快照只计一次）。例如，""、""、""都是可能的队列快照；而""不是可能的队列快照，因为剩下的 个正整数的和不可能是 。
阅读程序写结果：
#include <iostream>
using namespace std;
void swap(int & a, int & b)
{
int t;
t = a;
a = b;
b = t;
}
int main()
{
int a1, a2, a3, x;
cin>>a1>>a2>>a3;
if (a1 > a2)
swap(a1, a2);
if (a2 > a3)
swap(a2, a3);
if (a1 > a2)
swap(a1, a2);
cin>>x;
if (x < a2)
if (x < a1)
cout<<x<<' '<<a1<<' '<<a2<<' '<<a3<<endl;
else
cout<<a1<<' '<<x<<' '<<a2<<' '<<a3<<endl;
else
if (x < a3)
cout<<a1<<' '<<a2<<' '<<x<<' '<<a3<<endl;
else
cout<<a1<<' '<<a2<<' '<<a3<<' '<<x<<endl;
return 0;
}输入：
91 2 20
77
阅读程序写结果：
#include <iostream>
using namespace std;
int rSum(int j)
{
int sum = 0;
while (j != 0) {
sum = sum * 10 + (j % 10);
j = j / 10;
}
return sum;
}
int main()
{
int n, m, i;
cin>>n>>m;
for (i = n; i < m; i++)
if (i == rSum(i))
cout<<i<<' ';
return 0;
}输入：
90 120
阅读程序写结果：
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
char m1, m2;
int i;
getline(cin, s);
m1 = ' ';
m2 = ' ';
for (i = 0; i < s.length(); i++)
if (s[i] > m1) {
m2 = m1;
m1 = s[i];
}
else if (s[i] > m2)
m2 = s[i];
cout<<int(m1)<<' '<<int(m2)<<endl;
return 0;
} 输入：Expo 2010 Shanghai China 输出：_________
提示：
| 字符 | 空格 | '0' | 'A' | 'a' |
|---|---|---|---|---|
| ASCII码 | 32 | 48 | 65 | 97 |
阅读程序写结果：
#include <iostream>
using namespace std;
const int NUM = 5;
int r(int n)
{
int i;
if (n <= NUM)
return n;
for (i = 1; i <= NUM; i++)
if (r(n - i) < 0)
return i;
return -1;
}
int main()
{
int n;
cin>>n;
cout<<r(n)<<endl;
return 0;
}（1）
输入：7
输出：_________（4分）
（2）
输入：16
输出：_________（4分）
（1）（4 分）
（2）（4 分）
完善程序：
（哥德巴赫猜想）哥德巴赫猜想是指，任一大于
的偶数都可写成两个质数之和。迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。试编写程序，验证任一大于
且不超过
的偶数都能写成两个质数之和。
#include <iostream>
using namespace std;
int main()
{
const int SIZE = 1000;
int n, r, p[SIZE], i, j, k, ans;
bool tmp;
cin>>n;
r = 1;
p[1] = 2;
for (i = 3; i <= n; i++) {
[ ① ];
for (j = 1; j <= r; j++)
if (i % [ ② ] == 0) {
tmp = false;
break;
}
if (tmp) {
r++;
[ ③ ] ;
}
}
ans = 0;
for (i = 2; i <= n / 2; i++) {
tmp = false;
for (j = 1; j <= r; j++)
for (k = j; k <= r; k++)
if (i + i == [ ④ ] ) {
tmp = true;
break;
}
if (tmp)
ans++;
}
cout<<ans<<endl;
return 0;
}若输入 为 ，则输出[ ⑤ ]时表示验证成功，即大于 且不超过 的偶数都满足哥德巴赫猜想。
（1）（2 分）
（2）（2 分）
（3）（2 分）
（4）（2 分）
（5）（3 分）
完善程序：
(过河问题）
在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸。在这伸手不见五指的黑夜里，过桥时必须借助灯光来照明，很不幸的是，他们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则将会坍塌。每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入
和这
个人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。
例如，有 个人甲、乙、丙，他们单独过桥的时间分别为 ，则总共最少需要的时间为 。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然后甲、丙再一起过桥到河的左岸，总时间为 。
#include <iostream>
using namespace std;
const int SIZE = 100;
const int INFINITY = 10000;
const bool LEFT = true;
const bool RIGHT = false;
const bool LEFT_TO_RIGHT = true;
const bool RIGHT_TO_LEFT = false;
int n, hour[SIZE];
bool pos[SIZE];
int max(int a, int b)
{
if (a > b)
return a;
else
return b;
}
int go(bool stage)
{
int i, j, num, tmp, ans;
if (stage == RIGHT_TO_LEFT) {
num = 0;
ans = 0;
for (i = 1; i <= n; i++)
if (pos[i] == RIGHT) {
num++;
if (hour[i] > ans)
ans = hour[i];
}
if ([ ① ])
return ans;
ans = INFINITY;
for (i = 1; i <= n - 1; i++)
if (pos[i] == RIGHT)
for (j = i + 1; j <= n; j++)
if (pos[j] == RIGHT) {
pos[i] = LEFT;
pos[j] = LEFT;
tmp = max(hour[i], hour[j]) +[ ② ];
if (tmp < ans)
ans = tmp;
pos[i] = RIGHT;
pos[j] = RIGHT;
}
return ans;
}
if (stage == LEFT_TO_RIGHT) {
ans = INFINITY;
for (i = 1; i <= n; i++)
if ([ ③ ]) {
pos[i] = RIGHT;
tmp =[ ④ ];
if (tmp < ans)
ans = tmp;
[ ⑤ ];
}
return ans;
}
return 0;
}
int main()
{
int i;
cin>>n;
for (i = 1; i <=n; i++) {
cin>>hour[i];
pos[i] = RIGHT;
}
cout<<go(RIGHT_TO_LEFT)<<endl;
return 0;
}（1）（3 分）
（2）（3 分）
（3）（3 分）
（4）（3 分）
（5）（3 分）
关于图灵机下面的说法哪个是正确的：
A. 图灵机是世界上最早的电子计算机。 B. 由于大量使用磁带操作，图灵机运行速度很慢。 C. 图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。 D. 图灵机只是一个理论上的计算模型。
关于计算机内存下面的说法哪个是正确的：
A. 随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。 B. 内存通常是指 字节大小的内存。 C. 计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。 D. 一般内存中的数据即使在断电的情况下也能保留 个小时以上。
关于 BIOS 下面说法哪个是正确的：
A. BIOS 是计算机基本输入输出系统软件的简称。 B. BIOS 里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。 C. BIOS 一般由操作系统厂商来开发完成。 D. BIOS 能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。
关于 CPU 下面哪个说法是正确的：
A. CPU 全称为中央处理器（或中央处理单元）。 B. CPU 可以直接运行汇编语言。 C. 同样主频下，32 位的 CPU 比 16 位的 CPU 运行速度快一倍。 D. CPU 最早是由 Intel 公司发明的。
关于 ASCII，下面哪个说法是正确的：
A. ASCII 码就是键盘上所有键的唯一编码。 B. 一个 ASCII 码使用一个字节的内存空间就能够存放。 C. 最新扩展的 ASCII 编码方案包含了汉字和其他欧洲语言的编码。 D. ASCII 码是英国人主持制定并推广使用的。
下列软件中不是计算机操作系统的是：
A. Windows B. Linux C. OS/2 D. WPS
关于互联网，下面的说法哪一个是正确的：
A. 新一代互联网使用的 IPv6 标准是 IPv5 标准的升级与补充。 B. 互联网的入网主机如果有了域名就不再需要 IP 地址。 C. 互联网的基础协议为 TCP/IP 协议。 D. 互联网上所有可下载的软件及数据资源都是可以合法免费使用的。
关于 HTML 下面哪种说法是正确的：
A. HTML 实现了文本、图形、声音乃至视频信息的统一编码。 B. HTML 全称为超文本标记语言。 C. 网上广泛使用的 Flash 动画都是由 HTML 编写的。 D. HTML 也是一种高级程序设计语言。
关于程序设计语言，下面哪个说法是正确的：
A. 加了注释的程序一般会比同样的没有加注释的程序运行速度慢。 B. 高级语言开发的程序不能使用在低层次的硬件系统如：自控机床或低端手机上。 C. 高级语言相对于低级语言更容易实现跨平台的移植。 D. 以上说法都不对。
已知大写字母 的 ASCII 编码为 （进制），则大写字母 的 进制 ASCII 编码为：
A. 71 B. 72 C. 73 D. 以上都不是
十进制小数 对应的 进制数是
A. 100.1 B. 175.175 C. 175.1 D. 100.175
有六个元素 从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？
A. B. C. D.
表达式a*(b+c)-d的后缀表达式是：
A. abcd*+- B. abc+*d- C.
abc*+d- D. -+*abcd
一个包含 个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为：
A. B. C. D.
快速排序最坏情况下的算法时间复杂度为：
A. B. C. D.
有一个由 个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素：
A. 次 B. 次 C. 次 D. 次
排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的：
A. 冒泡排序 B. 插入排序 C. 归并排序 D. 快速排序
已知 个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），则该图中最少有多少条有向边？
A. B. C. D.
全国信息学奥林匹克竞赛的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克竞赛官方网站的网址是：
A. http://www.noi.com/ B. http://www.noi.org/ C. http://www.noi.cn/ D. http://www.xinxixue.com/
在参加NOI系列竞赛过程中，下面哪一种行为是 不 被严格禁止的：
A. 携带书写工具，手表和不具有通讯功能的电子词典进入赛场。 B. 在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。 C. 通过互联网搜索取得解题思路。 D. 在提交的程序中启动多个进程以提高程序的执行效率。
小陈现有 个任务 要完成，每个任务分别有若干步骤如下：，。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如 是合法的，而 是不合法的。小陈从 B 任务的 步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务 A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有（ ）种。
有如下的一段程序：
1. a=1;
2. b=a;
3. d=-a;
4. e=a+d;
5. c=2*d;
6. f=b+e-d;
7. g=a*f+c;现在要把这段程序分配到若干台（数量充足）用电缆连接的 PC 上做并行执行。每台 PC 执行其中的某几个语句，并可随时通过电缆与其他 PC 通讯，交换一些中间结果。假设每台 PC 每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在[ ]单位时间内执行完毕。
注意：任意中间结果只有在某台 PC 上已经得到，才可以被其他 PC 引用。例如若语句 4 和 6 被分别分配到两台 PC 上执行，则因为语句 6 需要引用语句 4 的计算结果，语句 6 必须在语句 4 之后执行。
阅读程序写结果：
#include <iostream>
using namespace std;
int a,b;
int work(int a,int b){
if (a%b)
return work(b,a%b);
return b;
}
int main(){
cin >> a >> b;
cout << work(a,b) << endl;
return 0;
}
输入：20 12
阅读程序写结果：
#include <iostream>
using namespace std;
int main()
{
int a[3],b[3];
int i,j,tmp;
for (i=0;i<3;i++)
cin >> b[i];
for (i=0;i<3;i++)
{
a[i]=0;
for (j=0;j<=i;j++)
{
a[i]+=b[j];
b[a[i]%3]+=a[j];
}
}
tmp=1;
for (i=0;i<3;i++)
{
a[i]%=10;
b[i]%=10;
tmp*=a[i]+b[i];
}
cout << tmp << endl;
return 0;
}输入：2 3 5
阅读程序写结果：
#include <iostream>
using namespace std;
const int c=2009;
int main()
{
int n,p,s,i,j,t;
cin >> n >> p;
s=0;t=1;
for(i=1;i<=n;i++)
{
t=t*p%c;
for(j=1;j<=i;j++)
s=(s+t)%c;
}
cout << s << endl;
return 0;
}输入：11 2
阅读程序写结果：
#include <iostream>
using namespace std;
const int maxn=50;
void getnext(char str[])
{
int l=strlen(str),i,j,k,temp;
k=l-2;
while(k>=0&&str[k]>str[k+1]) k--;
i=k+1;
while(i<l&&str[i]>str[k]) i++;
temp=str[k];
str[k]=str[i-1];
str[i-1]=temp;
for(i=l-1;i>k;i--)
for(j=k+1;j<i;j++)
if(str[j]>str[j+1])
{
temp=str[j];
str[j]=str[j+1];
str[j+1]=temp;
}
return ;
}
int main()
{
char a[maxn];
int n;
cin >> a >> n;
while(n>0)
{
getnext(a);
n--;
}
cout << a << endl;
return 0;
}输入：NOIP 3
完善程序：
（最大连续子段和） 给出一个数列（元素个数不多于
），数列元素均为负整数、正整数、。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为
时，输出
和
；数列为
时，输出
和
。
#include <iostream>
using namespace std;
int a[101];
int n,i,ans,len,tmp,beg;
int main(){
cin >> n;
for (i=1;i<=n;i++)
cin >> a[i];
tmp=0;
ans=0;
len=0;
beg= [ ① ] ;
for (i=1;i<=n;i++){
if (tmp+a[i]>ans){
ans=tmp+a[i];
len=i-beg;
}
else if ( [ ② ] &&i-beg>len)
len=i-beg;
if (tmp+a[i] [ ③ ] ){
beg= [ ④ ] ;
tmp=0;
}
else
[ ⑤ ];
}
cout << ans << " " << len << endl;
return 0;
}（1）（3 分）
（2）（3 分）
（3）（3 分）
（4）（3 分）
（5）（3 分）
完善程序：
（国王放置） 在
的棋盘上放置
个国王，要求
个国王互相不攻击，有多少种不同的放置方法。假设国王放置在第
格，国王的攻击的区域是：，。读入三个数
，输出答案。题目利用回溯法求解。棋盘行标号为
，列标号为
。
#include <iostream>
using namespace std;
int n,m,k,ans;
int hash[5][5];
void work(int x,int y,int tot){
int i,j;
if (tot==k){
ans++;
return;
}
do{
while (hash[x][y]){
y++;
if (y==m){
x++;
y=[ ① ];
}
if (x==n)
return;
}
for (i=x-1;i<=x+1;i++)
if (i>=0&&i<n)
for (j=y-1;j<=y+1;j++)
if (j>=0&&j<m)
[ ② ];
[ ③ ];
for (i=x-1;i<=x+1;i++)
if (i>=0&&i<n)
for (j=y-1;j<=y+1;j++)
if (j>=0&&j<m)
[ ④ ];
y++;
if (y==m){
x++;
y=0;
}
if (x==n)
return;
}
while (1);
}
int main(){
cin >> n >> m >> k;
ans=0;
memset(hash,0,sizeof(hash));
[ ⑤ ] ;
cout << ans << endl;
return 0;
}（1）（3 分）
（2）（3 分）
（3）（3 分）
（4）（2 分）
（5）（2 分）
微型计算机中，控制器的基本功能是（ ）。
A. 控制机器各个部件协调工作 B. 实现算术运算和逻辑运算 C. 获取外部信息 D. 存放程序和数据
设
A=true,B=false,C=true,D=false，以下逻辑运算表达式值为真的是（
）。
A. (A∧B)∨(C∧D∨ -A) B. ((A∧B)∨C)∧ -D C. (B∨C∨D)∧D∧A D. A∧(D∨ C)∧B
在下列关于图灵奖的说法中，不正确的是（ ）。
A. 图灵奖是美国计算机协会于 1966 年设立的，专门奖励那些对计算机事业作出重要贡献的个人 B. 图灵奖有“计算机界诺贝尔奖”之称 C. 迄今为止，还没有华裔计算机科学家获此殊荣 D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵
计算机在工作过程中，若突然停电，（ ）中的信息不会丢失。
A. ROM 和 RAM B. CPU C. ROM D. RAM
完全二叉树共有 个结点，则它的叶节点数是（ ）。
A. B. C. D.
在以下各项中，（ ）不是操作系统软件。
A. Solaris B. Linux C. Windows Vista D. Sybase
设栈 的初始状态为空，元素 依次入栈 ，出栈的序列为 ，则栈 的容量至少应该是（ ）。
A. 6 B. 5 C. 4 D. 3
与十进制数 相等的四进制数是（ ）。
A. 123.21 B. 131.22 C. 130.22 D. 130.21
设字符串 ， 的非空子串的数目是（ ）。
A. 28 B. 29 C. 16 D. 17
Web2.0 是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中，（ ）是典型的 Web2.0 应用。
A. Sina B. Flickr C. Yahoo D. Google
递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（ ）的数据结构。
A. 队列 B. 多维数组 C. 线性表 D. 栈
的结果是（ ）。
A. B. C. D.
二叉树 ，已知其先根遍历是 （数字为结点的编号，以下同），中根遍历是 ，则该二叉树的后根遍历是（ ）。
A. B. C. D.
将数组 中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（ ）次。
A. 4 B. 5 C. 6 D. 7
对有序数组 进行二分查找，成功查找元素 的查找长度（比较次数）是（ ）。
A. 1 B. 2 C. 3 D. 4
面向对象程序设计（Object-Oriented Programming）是一种程序设计的方法论，它将对象作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。下面关于面向对象程序设计的说法中，不正确的是（ ）。
A. 面向对象程序设计通常采用自顶向下设计方法进行设计。 B. 面向对象程序设计方法具有继承性（inheritance）、封装性（encapsulation）、多态性（polymorphism）等几大特点。 C. 支持面向对象特性的语言称为面向对象的编程语言，目前较为流行的有 C++、JAVA、C# 等。 D. 面向对象的程序设计的雏形来自于 Simula 语言，后来在 SmallTalk 语言的完善和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今，SmallTalk 语言仍然被视为面向对象语言的基础。
在 点阵的“字库”中，汉字“北”与“京”的字模占用字节数之和是（ ）。
A. 512 B. 256 C. 384 D. 128
设 是一棵有 个顶点的树，下列说法不正确的是（ ）。
A. 有 条边 B. 是连通的 C. 是无环的 D. 有 条边
下列不属于 NOIP 竞赛推荐使用的语言环境的是（ ）。
编者注：由于试题为 年的试题，请根据 年的实际情况作答。
A. Dev-C++ B. Visual C++ C. free pascal D. Lazarus
在 C++ 程序中，表达式 200|10 的值是（ ）。
A. 20 B. 1 C. 220 D. 202
书架上有 本不同的书 A、B、C、D。其中 A 和 B 是红皮的，C 和 D 是黑皮的。把这 本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_____种。满足 A 必须比 C 靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有______种摆法。
（1）（2 分）
（2）（2 分）
有
个城市，任何两个城市之间都有一条道路连接，
个城市两两之间的距离如下表所示，则城市
到城市
的最短距离为_____________。 
阅读程序写结果:
#include<iostream>
using namespace std;
int main()
{
int i, a, b, c, d, f[4];
for(i = 0; i < 4; i++) cin >> f[i];
a = f[0] + f[1] + f[2] + f[3];
a = a / f[0];
b = f[0] + f[2] + f[3];
b = b / a;
c = (b * f[1] + a) / f[2];
d = f[(b / c ) % 4];
if(f[(a + b + c + d) % 4] > f[2])
cout << a + b<< endl;
else
cout << c + d << endl;
return 0;
}输入：9 19 29 39
阅读程序写结果:
#include<iostream>
using namespace std;
void foo(int a, int b, int c)
{
if(a > b)
foo(c, a, b);
else
cout<<a<<','<<b<<','<<c<<endl;
}
int main()
{
int a, b, c;
cin >> a >> b >> c;
foo(a, b, c);
return 0;
}输入: 3 1 2
阅读程序写结果:
#include <iostream>
using namespace std;
void func(int ary[], int n )
{
int i=0, j, x;
j=n-1;
while(i<j)
{
while (i<j&&ary[i]>0) i++;
while (i<j&&ary[j]<0) j--;
if (i<j){
x=ary[i];
ary[i++]=ary[j];
ary[j--]=x;
}
}
}
int main()
{
int a[20], i, m;
m=10;
for(i=0; i<m; i++)
{
cin>>a[i];
}
func(a, m);
for (i=0; i<m; i++)
cout<<a[i]<<" ";
cout<< endl;
return 0;
}输入：5 4 -6 -11 6 -59 22 -6 1 10
阅读程序写结果:
#include<iostream>
#include<cstring>
using namespace std;
#define MAX 100
void solve(char first[], int spos_f, int epos_f, char mid[], int spos_m, int epos_m)
{
int i, root_m;
if(spos_f > epos_f)
return;
for(i = spos_m; i <= epos_m; i++)
if(first[spos_f] == mid[i])
{
root_m = i;
break;
}
solve(first, spos_f + 1, spos_f + (root_m - spos_m), mid, spos_m, root_m - 1);
solve(first, spos_f + (root_m - spos_m) + 1, epos_f, mid, root_m + 1, epos_m);
cout << first[spos_f];
}
int main()
{
char first[MAX], mid[MAX];
int len;
cin >> len;
cin >> first >> mid;
solve(first, 0, len - 1, mid , 0, len - 1);
cout << endl;
return 0;
}输入：
7
ABDCEGF
BDAGECF
完善程序：
（字符串替换）给定一个字符串
（
仅包含大小写字母），下面的程序将
中的每个字母用规定的字母替换，并输出
经过替换后的结果。程序的输入是两个字符串，第一个字符串是给定的字符串
，第二个字符串
由
个字母组成，它是
的任一排列，大小写不定，
规定了每个字母对应的替换字母：
中的第一个字母是字母
和
的替换字母，即
中的
用该字母的大写替换，
中的
用该字母的小写替换；
中的第二个字母是字母
和
的替换字母，即
中的
用该字母的大写替换，
中的
用该字母的小写替换；……以此类推。
#include <iostream>
#include <string.h>
char change[26], str[5000];
using namespace std;
void CheckChangeRule()
{
int i;
for (i = 0;i < 26;i ++)
{
if ( [ ① ] )
change[i] -= 'A' - 'a';
}
}
void ChangeString()
{
int i;
for (i = 0;i <strlen(str);i ++)
{
if ( [ ② ] )
str[i] = change[str[i] - 'A'] -'a' + 'A';
else
[ ③ ]
}
}
int main()
{
int i;
cin >> str ;
cin >> change;
CheckChangeRule();
[ ④ ]
cout << str << endl;
return 0;
}（1）（2 分）
（2）（2 分）
（3）（2 分）
（4）（2 分）
完善程序：
（找第 大的数） 给定一个长度为 的无序正整数序列, 以及另一个数 , 然后以类似快速排序的方法找到序列中第 大的数（关于第 大的数：例如序列 中第 大的数是 ）。
#include <iostream>
using namespace std;
int a[1000001],n,ans = -1;
void swap(int &a,int &b)
{
int c;
c = a; a = b; b = c;
}
int FindKth(int left, int right, int n)
{
int tmp,value,i,j;
if (left == right) return left;
tmp = rand()% (right - left) + left;
swap(a[tmp],a[left]);
value =[ ① ];
i = left;
j = right;
while (i < j)
{
while (i < j && [ ② ]) j --;
if (i < j) {a[i] = a[j]; i ++;} else break;
while (i < j && [ ③ ]) i ++;
if (i < j) {a[j] = a[i]; j - -;} else break;
}
[ ④ ]
if (i < n) return FindKth([ ⑤ ] );
if (i > n) return [ ⑥ ]
return i;
}
int main()
{
int i;
int m = 1000000;
for (i = 1;i <= m;i ++)
cin >> a[i];
cin >> n;
ans = FindKth(1,m,n);
cout << a[ans];
return 0;
}（1）（3 分）
（2）（3 分）
（3）（3 分）
（4）（3 分）
（5）（3 分）
（6）（3 分）
在以下各项中，（ ）不是 CPU 的组成部分
A. 控制器 B. 运算器 C. 寄存器 D. 主板
在关系数据库中，存放在数据库中的数据的逻辑结构以（ ）为主。
A. 二叉树 B. 多叉树 C. 哈希表 D. 二维表
在下列各项中，只有（ ）不是计算机存储容量的常用单位。
A. Byte B. KB C. UB D. TB
ASCII 码的含义是（ ）。
A. 二→十进制转换码 B. 美国信息交换标准代码 C. 数字的二进制编码 D. 计算机可处理字符的唯一编码
一个完整的计算机系统应包括（ ）。
A. 系统硬件和系统软件 B. 硬件系统和软件系统 C. 主机和外部设备 D. 主机、键盘、显示器和辅助存储器
IT 的含义是（ ）。
A. 通信技术 B. 信息技术 C. 网络技术 D. 信息学
LAN 的含义是（ ）。
A. 因特网 B. 局域网 C. 广域网 D. 城域网
冗余数据是指可以由其它数据导出的数据。例如，数据库中已存放了学生的数学、语文和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看作冗余数据。冗余数据往往会造成数据的不一致。例如，上面 个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。下面关于冗余数据的说法中，正确的是（ ）。
A. 应该在数据库中消除一切冗余数据 B. 用高级语言编写的数据处理系统，通常比用关系数据库编写的系统更容易消除冗余数据 C. 为了提高查询效率，在数据库中可以保留一些冗余数据，但更新时要做相容性检验 D. 做相容性检验会降低效率，可以不理睬数据库中的冗余数据
在下列各软件，不属于 NOIP 竞赛（复赛）推荐使用的语言环境有（ ）。
编者注：由于试题为 年的试题，请根据 年的实际情况作答。
A. gcc B. g++ C. Turbo C D. Free Pascal
以下断电后仍能保存数据的有（ ）。
A. 硬盘 B. 高速缓存 C. 显存 D. RAM
在下列关于计算机语言的说法中，正确的有（ ）。
A. 高级语言比汇编语言更高级，是因为它的程序的运行效率更高 B. 随着 Pascal、C 等高级语言的出现，机器语言和汇编语言已经退出了历史舞台 C. 高级语言比汇编语言程序更容易从一种计算机上移植到另一种计算机上 D. C 是一种面向对象的高级计算机语言
近 20 年来，许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具。在下列关于递归算法的说法中，正确的是（ ）。
A. 在 1977 年前后形成标准的计算机高级语言 FORTRAN77 禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间 B. 和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些 C. 对于较复杂的问题，用递归方式编程一般比非递归方式更难一些 D. 对于已经定义好的标准数学函数 sin(x)，应用程序中的语句“y=sin(sin(x));”就是一种递归调用
一个无法靠自身的控制终止的循环成为“死循环”，例如，在 C++
语言程序中，语句 while(1) printf("*");
就是一个死循环，运行时它将无休止地打印 *
号。下面关于死循环的说法中，只有（ ）是正确的。
A. 不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环，因而，任何编译系统都不做死循环检查 B. 有些编译系统可以检测出死循环 C. 死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查出死循环 D. 死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也可以检测的
在 C++ 语言中,表达式 23|2^5 的值是( )
A. 18 B. 1 C. 23 D. 32
在 C++ 语言中,判断 等于 或 等于 或 等于 的正确的条件表达式是（ ）。
A. !((a!=0)||(b!=0)||(c!=0)) B.
!((a!=0)&&(b!=0)&&(c!=0)) C.
!(a==0&&b==0)||(c!=0) D.
(a=0)&&(b=0)&&(c=0)
地面上有标号为 A、B、C 的三根柱，在 A 柱上放有 个直径相同中间有孔的圆盘，从上到下依次编号为 ，将 A 柱上的部分盘子经过 B 柱移入 C 柱，也可以在 B 柱上暂存。如果 B 柱上的操作记录为“进、进、出、进、进、出、出、进、进、出、进、出、出”。那么，在 C 柱上，从下到上的编号为（ ）。
A. 2 4 3 6 5 7 B. 2 4 1 2 5 7 C. 2 4 3 1 7 6 D. 2 4 3 6 7 5
与十进制数 对应的八进制数是（ ）。
A. 3350 B. 3351 C. 3352 D. 3540
设
A=B=True，C=D=False，以下逻辑运算表达式值为假的有（ ）。
A. (﹁A∧B)∨(C∧D∨A) B. ﹁(((A∧B)∨C)∧D) C. A∧(B∨C∨D)∨D D. (A∧(D∨C))∧B
$(2070)_{16} + (34)_8 $ 的结果是（ ）。
A. B. C. D.
已知 个节点的二叉树的先根遍历是 （数字为节点的编号，以下同），中根遍历是 ，则该二叉树的后根遍历是（ ）。
A. B. C. D.
（子集划分）将 个数 划分成 个子集。每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为 。例如，，这 种不同的划分方法依次为 ，。当 时，______________。
（提示：先固定一个数，对于其余的 个数考虑 与 ，再分这两种情况对原固定的数进行分析。）
（最短路线）某城市的街道是一个很规整的矩形网络（见下图），有
条南北向的纵街，
条东西向的横街。现要从西南角的 A 走到东北角的 B
，最短的走法共有多少种？___________
看程序写结果：
#include<stdio.h>
int main()
{
int i, p[5], a, b, c, x, y = 20;
for ( i = 0; i <= 4; i++ )
scanf( "%d", &p[i] );
a = (p[0] + p[1]) + (p[2] + p[3] + p[4]) / 7;
b = p[0] + p[1] / ( (p[2] + p[3]) / p[4]);
c = p[0] * p[1] / p[2];
x = a + b - p[(p[3] + 3) % 4];
if ( x > 10 )
y += (b * 100 - a) / (p[p[4] % 3] * 5);
else
y += 20 + (b * 100 - c) / (p[p[4] % 3] * 5);
printf( "%d,%d\n", x, y );
return(0);
}
//注：本例中，给定的输入数据可以避免分母为 0 或数组元素下标越界。输入：6 6 5 5 3
看程序写结果：
#include<stdio.h>
void fun( int *a, int *b )
{
int *k;
k = a; a = b; b = k;
}
int main()
{
int a = 3, b = 6, *x = &a, *y = &b;
fun( x, y );
printf( "%d,%d ", a, b );
}输出：_______________________________
看程序写结果：
#include "math.h"
#include "stdio.h"
int main()
{
int a1[51] = { 0 };
int i, j, t, t2, n = 50;
for ( i = 2; i <= sqrt( n ); i++ )
if ( a1[i] == 0 )
{
t2 = n / i;
for ( j = 2; j <= t2; j++ )
a1[i * j] = 1;
}
t = 0;
for ( i = 2; i <= n; i++ )
if ( a1[i] == 0 )
{
printf( "%4d", i ); t++;
if ( t % 10 == 0 )
printf( "\n" );
}
printf( "\n" );
}（1）（4 分）
（2）（4 分）
看程序写结果：
#include "ctype.h"
#include "stdio.h"
void expand( char s1[], char s2[] )
{
int i, j, a, b, c;
j = 0;
for ( i = 0; (c = s1[i]) != '\0'; i++ )
if ( c == '-' )
{
a = s1[i - 1]; b = s1[i + 1];
if ( isalpha( a ) && isalpha( b ) || isdigit( a ) && isdigit( b ) )
/*函数 isalpha(a) 用于判断字符 a 是否为字母，isdigit(b) 用于判断字符 b 是否为数字,如果是,返回 1，否则返回 0 */
{
j--;
do
s2[j++] = a++;
while ( tolower( a ) < tolower( s1[i + 1] ) );
}
/*函数 tolower(a) 的功能是当字符 a 是大写字母,改为小写,其余情况不变*/
else s2[j++] = c;
}else s2[j++] = c;
s2[j] = '\0';
}
int main()
{
char s1[100], s2[300];
printf( "input s1:" );
gets( s1 );
expand( s1, s2 );
printf( "%s\n", s2 );
}输入：wer2345d-h454-82qqq
完善程序:
（求字符的逆序）下面的程序的功能是输入若干行字符串，每输入一行，就按逆序输出该行，最后键入
终止程序。请将程序补充完整。
#include <iostream.h>
#include <string.h>
int maxline = 200, kz;
int reverse( char s[] )
{
int i, j, t;
for ( i = 0, j = strlen( s ) - 1; i < j; 【①】 , 【②】 )
{
t = s[i]; s[i] = s[j]; s[j] = t;
}
return(0);
}
int main()
{
char line[100];
cout << "continue? -1 for end." <<endl;
cin>>kz;
while(【③】)
{
cin >> line;
【④】;
cout << line << endl;
cout << "continue ? -1 for end." << endl;
cin >> kz;
}
}（1）（2 分）
（2）（2 分）
（3）（2 分）
（4）（2 分）
完善程序：
（棋盘覆盖问题）在一个
个方格组成的棋盘中恰有一个方格与其它方格不同（图中标记为
的方格），称之为特殊方格。现 L 型（占
个小方格）纸片覆盖棋盘上除特殊方格的所有部分，各纸片不得重叠，于是，用到的纸片数恰好是
。在下表给出的一个覆盖方案中，，相同的
各数字构成一个纸片。下面给出的程序使用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下角、右下角，递归进行。请将程序补充完整。
2 2 3 3
2 -1 1 3
4 1 1 5
4 4 5 5#include <iostream.h>
#include <iomanip.h>
int board[65][65], tile; /* tile为纸片编号 */
void chessboard( int tr, int tc, int dr, int dc, int size )
/* dr,dc依次为特殊方格的行、列号 */
{
int t, s;
if ( size == 1 )
① ;
t = tile++;
s = size / 2;
if ( ② )
chessboard( tr, tc, dr, dc, s );
else{
board[tr + s -1][tc + s -1] = t;
[③];
}
if ( dr < tr + s && dc >= tc + s )
chessboard( tr, tc + s, dr, dc, s );
else{
board[tr + s -1][tc + s] = t;
④;
}
if ( dr >= tr + s && dc < tc + s )
chessboard( tr + s, tc, dr, dc, s );
else{
board[tr + s][tc + s -1] = t;
[⑤];
}
if ( dr >= tr + s && dc >= tc + s )
chessboard( tr + s, tc + s, dr, dc, s );
else{ board[tr + s][tc + s] = t;
[⑥]; }
}
void prtl( int b[][65], int n )
{
int i, j;
for ( i =1; i <= n; i++ )
{
for ( j =1; j <= n; j++ )
cout << setw( 3 ) << b[i][j];
cout << endl;
}
}
void main()
{
int size, dr, dc;
cout << "input size(4/8/16/64):" << endl;
cin >> size;
cout << "input the position of special block(x,y):" << endl;
cin >> dr >> dc;
board[dr][dc] = -1;
tile++;
chessboard( 1, 1, dr, dc, size );
prtl( board, size );
}（1）（3 分）
（2）（3 分）
（3）（3 分）
（4）（3 分）
（5）（3 分）
（6）（3 分）