1999年至历年信息学奥赛提高组初赛试题 本文关键词：初赛，历年，信息学，试题，奥赛
1999年至历年信息学奥赛提高组初赛试题 本文简介：福建省莆田第一中学信息学奥赛兴趣小组整理：林梓雨第十七届（2011）全国青少年信息学奥林匹克联赛初赛试题（提高组Pascal语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分。共计30分。每题有且仅有一个正确选项。）1．在二进制下，11
1999年至历年信息学奥赛提高组初赛试题 本文内容：
福建省莆田第一中学
信息学奥赛兴趣小组
整理：林梓雨
第十七届（2011）全国青少年信息学奥林匹克联赛初赛试题
（
提高组
Pascal语言
两小时完成
）
●●
全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效
●●
一、单项选择题（共20题，每题1.5分。共计30分。每题有且仅有一个正确选项。）
1．在二进制下，1100011
+（
）=
1110000。
A．1011B．1101C．1010
D．1111
2．字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（
）。
A．66
B．5AC．50
D．视具体的计算机而定
3．右图是一棵二叉树，它的先序遍历是（
）。
A．ABDEFC
B．DBEFACC．DFEBCA
D．ABCDEF
4．寄存器是（
）的重要组成部分。
A．硬盘
B．高速缓存
C．内存D．中央处理器（CPU）
5．广度优先搜索时，需要用到的数据结构是（
）。
A．链表
B．队列C．栈D．散列表
6．在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（
）。
A．程序运行时理论上所占的内存空间
B．程序运行时理论上所占的数组空间
C．程序运行时理论上所占的硬盘空间
D．程序源文件理论上所占的硬盘空间
7．应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（
）。
A．O(n2)B．O(n
log
n)C．O(n)D．O(1)
8．为解决Web应用中的不兼容问题，保障信息的顺利流通，（
）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。
A．微软
B．美国计算机协会（ACM）
C．联台国教科文组织D．万维网联盟（W3C）
9．体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（
）算法。
A．快速排序B．插入排序C．冒泡排序D．归并排序
10．1956年（
）授予肖克利（William
Shockley）、巴丁（John
Bardeen）和布拉顿（Walter
Brattain)，以表彰他们对半导体的研究和晶体管效应的发现。
A．诺贝尔物理学奖
B．约翰?冯?诺依曼奖
C．图灵奖
D．高德纳奖（Donald
E．Knuth
Prize）
二、不定项选择题（共10题，每题1．5分，共计15分。每题有一个或多个正确选项。多选或少选均不得分。）
1．如果根结点的深度记为1，则一棵恰有2011个叶子结点的二叉树的深度可能是（
）。
A．10B．11C．12
D．2011
2．在布尔逻辑中，逻辑“或”的性质有（
）。
A．交换律：P
V
Q
=
Q
V
P
B．结台律：P
V
(
Q
V
R
)
=
(
P
V
Q
)
V
R
C．幂等律：P
V
P
=
P
D．有界律：P
V
1
=
1
（1表示逻辑真）
3．一个正整数在十六进制下有100位，则它在二进制下可能有（
）位。
A．399B．400C．401
D．404
4．汇编语言（
）。
A．是一种与具体硬件无关的程序设计语言
B．在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试
C．可以直接访问寄存器、内存单元、I/O端口
D．随着高级语言的诞生，如今已完全被淘汰，不再使用
5．现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、400。那么，“也”字的编码长度可能是（
）。
A．1B．2C．3
D．4
6．生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术己广泛应用于政府、银行、安全防卫等领域。以下属于生物特征识别技术及其应用的是（
）。
A．指静脉验证B．步态验证C．ATM机密码验证D．声音验证
7．对于序列“7、5、1、9、3、6、8、4”，在不改变顺序的情况下，去掉（
）会使逆序对的个数减少3。
A．7B．5C．3
D．6
8．计算机中的数值信息分为整数和实数（浮点数）。实数之所以能表示很大或者很小的数，是由于使用了（
）。
A．阶码B．补码C．反码D．较长的尾数
9．对右图使用Dijkstra算法计算S点到其余各点的最短路径
长度时，到B点的距离d[B]初始时赋为8，在算法的执行过程
中还会出现的值有（
）。
A．3B．7C．6
D．5
10．为计算机网络中进行数据交换而建立的规则、标准或约定的集合成为网络协议。下列英文缩写中，（
）是网络协议。
A．HTTPB．TCP/IPC．FTP
D．WWW
三、问题求解（共2题，每题5分，共计10分）
1．平面图是可以画在在平面上，且它的边仅在顶点上才能相交的简单
无向图。4个顶点的平面图至多有6条边，如右图所示。那么，5个顶
点的平面图至多有______条边。
2．定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串”BcA”，可以将A移到B之前，变成字符串”ABC”。如果要将字符串”DACHEBGIF”变成”ABCDEFGHI”，最少需要________次操作。
四、阅读程序写结果（共4题，每题8分，共计32分）
1．
Const
SIZE
=
100;
var
n,i,sum,x
:
integer;
a
:
array[1SIZE]
of
integer;
begin
readln(n);
fillchar(a,sizeof(a),0);
for
i:=
1
to
n
do
begin
read(x);
inc(a[x]);
end;
i
:=
0;
sum
:=
0;
while
sum
ans
then
ans
:=
len;
for
i
:=
1
to
n
do
if
(not
visited[i])
and
(e[x,i]
-1)
then
dfs(i,len
+
e[x,i]);
visited[x]
:=
false;
end;
begin
readln(n,m);
for
i
:=
1
to
n
do
for
j
:=
1
to
n
do
e[i][j]
:=
-1;
for
i
:=
1
to
m
do
begin
readln(a,b,c);
e[a][b]
:=
c;
e[b][a]
:=
c;
end;
for
i
:=
1
to
n
do
visited[i]
:=
false;
ans
:=
0;
for
i
:=
1
to
n
do
dfs(i,0);
writeln(ans);
end.
输入：
4
6
1
2
10
2
3
20
3
4
30
4
1
40
1
3
50
2
4
60
输出：__________
4.
const
SIZE
=
10000;
LENGTH
=
10;
var
sum
:
longint;
n,m,i,j
:
integer;
a
:
array[1SIZE,1LENGTH]
of
integer;
function
h(u,v
:
integer)
:
integer;
var
ans,i
:
integer;
begin
ans
:=
0;
for
i
:=
1
to
n
do
if
a[u][i]
a[v][i]
then
inc(ans);
h
:=
ans;
end;
begin
readln(n);
filichar(a,sizeof(a),0);
m
:=
1;
repeat
i
:=
1;
while
(i
n
then
break;
inc(m);
a[m][i]
:=1;
for
j
:=
i
+
1
to
n
do
a[m][j]
:=
a[m
-
1][j];
until
false;
sum
:=0;
for
i
:=
1
to
m
do
for
j
:=
1
to
m
do
sum
:=
sum
+
h(i,j);
writeln(sum);
end.
输入：7
输出：____________
五、完善程序（第1题，每空2分，第2题，每空3分，共计28分）
1.
（大整数开方）输入一个正整数n（1≤n
0
then
ans.len
:=
a.1en
+
b.1en
else
ans.len
:=a.1en
+
b.1en
–
1;
end;
times
:=
ans;
end;
function
add(a,b
:
hugeint)
:
hugeint;
var
i
:
integer;
ans
:
hugeint;
begin
fillchar(ans.num,sizeof(ans.num),0);
if
a.1en
>
b.1en
then
ans.len
:=
a.1en
else
ans.len
:=
b.len;
for
i
:=
1
to
ans.1en
do
begin
ans.num[i]
:=___③___;
ans.num[i
+
1]
:=
ans.num[i
+
1]
+
ans.num[i]
div
10;
ans.num[i]
:=
ans.num[i]
mod
10;
end;
if
ans.num[ans.1en
+
1]
>
0
then
inc(ans.len);
add:=ans;
end;
function
average(a,b
:
hugeint)
:
hugeint;
var
i
:
integer;
ans
:
hugeint;
begin
ans
:=
add(a,b);
for
i
:=
ans.1en
downto
2
do
begin
ans.num[i
-
1]
:=
ans.num[i
-
1]
+
(___④___)
10;
ans.num[i]
:=
ans.num[i]
div
2;
end;
ans.num[i]
:=
ans.num[i]
div
2;
if
ans.num[ans.len]
=
0
then
dec(ans.len);
average
:=
ans;
end;
function
plustwo(a
:
hugeint)
:
hugeint;
var
i
:
integer;
ans
:
hugeint;
begin
ans
:=
a;
ans.num[1]
:=
ans.num[1]
+
2;
i
:=
1;
while(i
=
10)
do
begin
ans.num[i
+
1]
:=
ans.num[i
+
1]
+
ans.num[i]
div
10;
ans.num[i]
:=
ans.num[i]
mod
10;
inc(i);
end;
if
ans.num[ans.len
+
1]
>
0
then___⑤___;
plustwo
:=
ans;
end;
function
over(a,b
:
hugeint)
:
boolean;
var
i
:
integer;
begin
if(___⑥___)then
begin
over
:=
false;
exit;
end;
if
a.1en
>
b.1en
then
begin
over
:=
true;
exit;
end;
for
i
:=
a.len
downto
1
do
begin
if
a.num[i]
b.num[i]
then
begin
over
:=
true;
exit;
end;
end;
over
:=
false;
end;’
begin
readln(s);
fillchar(target.num,sizeof(target.num),0);
target.1en
:=
1ength(s);
for
i
:=
1
to
target.1en
do
target.num[i]
:=
ord(s[target.1en
–
i
+
1])
-
___⑦___;
filichar(left.num,sizeof(1eft.num),0);
left.1en
:=
1;
left.num[i]
:=
1;
right
:=
target;
repeat
middle
:=
average(1eft,right);
if
over(___⑧___)
then
right
:=
middle
else
1eft
:=
middle;
until
over(plustwo(1eft),right);
for
i
:=
left.1en
downto
1
do
write(1eft.num[i]);
writeln;
end.
2.
（笛卡尔树）对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点外，每个结点的权值都大于父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵对应的笛卡尔树。现输入序列的规模n（1≤n
maxDeep
then
begin
maxDeep
:=
deep;
num
:=
1;
end
else
if
deep
=
maxDeep
then
___①___;
min
:=
INFINITY;
for
i
:=
1eft
to
right
do
if
min
>
a[i]
then
begin
min
:=
a[i];
___②___;
end;
if
left
欢迎访问NOI网站
B．欢迎访问NOI网站
C．h
t
t
p
:
/
/
w
w
w
.
n
o
i
.
c
n
D．欢迎访问NOI网站
7.
关于拓扑排序，下列说法正确的是(
)。
A．所有连通的有向图都可以实现拓扑排序
B．对同一个图而言，拓扑排序的结构是唯一的
C．拓扑排序中入度为0的结点总会排在入度大于0的结点的前面
D．拓扑排序结果序列中的第一个结点一定是入度大于0的点
8.
一个平面的法线是指与该平面垂直的直线。过点(1,1,1)、（0,3,0）、(2,0,0)的平面的法线是（
）。
A．过点（1，1，1）、（2，3，3）的直线B．过点（1，1，1）、（3，2，1）的直线
C．过点（0，3，0）、（-3，1，1）的直线D．过点（2，0，0）、（5，2，1）的直线
9.双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，他的左右结点均为非空。现要求删除结点p，则下列语句序列中正确的是(
)。
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->link
=
p->llink;
delete
p;
10.
今年(2010年)发生的事件有（
）。
A．惠普实验室研究员Vinay
Deolalikar
自称证明了P≠NP
B．英特尔公司收购计算机安全软件公司迈克菲(McAfee)
C．苹果公司发布iPhone
4手机D．微软公司发布Windows
7
操作系统
三、问题求解
1．LZW编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典，如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。
举例说明，考虑一个待编码的信息串：“xyx
yy
yy
xyx”。初始词典只有3个条目，第一个为x,编码为1；第二个为y，编码为2；第三个为空格，编码为3；于是串“xyx”的编码为1-2-1（其中-为编码分隔符），加上后面的一个空格就是1-2-1-3。但由于有了一个空格，我们就知道前面的“xyx”是一个单词，而由于该单词没有在词典中，我们就可以自适应的把这个词条添加到词典里，编码为4，然后按照新的词典对后继信息进行编码，以此类推。于是，最后得到编码：1-2-1-3-2-2-3-5-3-4。
我们可以看到，信息被压缩了。压缩好的信息传递到接受方，接收方也只要根据基础词典就可以完成对该序列的完全恢复。解码过程是编码过程的逆操作。现在已知初始词典的3个条目如上述，接收端收到的编码信息为2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6，则解码后的信息串是”____________”。
2.无向图G有7个顶点，若不存在由奇数条边构成的简单回路，则它至多有__________条边。
3.记T为一队列，初始时为空，现有n个总和不超过32的正整数依次入列。如果无论这些数具体为何值，都能找到一种出队的方式，使得存在某个时刻队列T中的数之和恰好为9，那么n的最小值是___________。
四、阅读程序写结果
1.
const
size
=
10;
var
i,j,cnt,n,m
:
integer;
data
:
array[1size]
of
integer;
begin
readln(n,m);
for
i
:=
1
to
n
do
read(data[i]);
for
i
:=
1
to
n
do
begin
cnt
:=
0;
for
j
:=
1
to
n
do
if
(data[i]
right
then
begin
if
successful
then
begin
for
i
:=
1
to
n
do
writeln(r[i],);
found
:=
true;
end;
exit;
end;
for
i:=
left
to
right
do
begin
swap(r[left],r[i]);
perm(left
+
1,right);
swap(r[left],r[i]);
end;
end;
begin
readln(n,m);
fillchar(map,sizeof(map),false);
for
i
:=
1
to
m
do
begin
readln(x,y);
map[x][y]
:=
true;
map[y][x]
:=
true;
end;
for
i
:=
1
to
n
do
r[i]
:=
i;
found
:=
false;
perm(1,n);
if
not
found
then
writeln(
No
soloution
);
end.
输入:
9
12
1
2
2
3
3
4
4
5
5
6
6
1
1
7
2
7
3
8
4
8
5
9
6
9
输出：__________
五、完善程序
1.(过河问题)
在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入N(2
b
then
max
:=
a
else
max
:=
b;
end;
function
go(stage
:
boolean)
:
integer;
var
i,j,num,tmp,ans
:
integer;
begin
if
(stage
=
RIGHT_TO_LEFT)
then
begin
num
:=
0;
ans
:=0;
for
i
:=
1
to
n
do
if
pos[i]
=
Rignt
then
begin
inc(num);
if
time[i]
>
ans
then
ans
:=
time[i];
end;
if
__________
then
begin
go
:=
ans;
exit;
end;
ans
:=
INFINITY;
for
i
:=
1
to
n
–
1
do
if
pos[i]
=
RIGHT
then
for
j
:=
i+1
to
n
do
if
pos[j]
=
RIGHT
then
begin
pos[i]
:=
LEFT;
pos[j]
:=
LEFT;
tmp
:=
max(time[i],time[j])
+
_______;
if
tmp
=1，它的叶结点数目为：
A)
nk
+
1
B)
nk-1
C)
(k+1)n-1
D.
(k-1)n+1
6.
表达式a*(b+c)-d的后缀表达式是：
A)
abcd*+-
B)
abc+*d-
C)
abc*+d-
D)
-+*abcd
7、最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。
A)（00，01，10，11）
B)（0，1，00，11）
C)（0，10，110，111）
D)（1，01，000，001）
8、快速排序平均情况和最坏情况下的算法时间复杂度分别为：
A)
平均情况
O(nlog2n)，最坏情况O(n2)
B)
平均情况
O(n)，
最坏情况O(n2)
C)
平均情况
O(n)，
最坏情况O(nlog2n)
D)
平均情况
O(log2n)，
最坏情况O(n2)
9、左图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。则依次加入最小生成树的顶点集合的顶点序列为：
A)
V0,V1,V2,V3,V5,V4
B)
V0,V1,V5,V4,V3,V3
C)
V1,V2,V3,V0,V5,V4
D)
V1,V2,V3,V0,V4,V5
10、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是：
A)
http://www.jsfw8.com/B)
http://www.jsfw8.com/
二．
不定项选择题
（共10题，每题1.5分，共计15分。每题正确答案的个数不少于1。多选或少选均不得分）。
1、关于CPU下面哪些说法是正确的：
A)
CPU全称为中央处理器（或中央处理单元）。
B)
CPU能直接运行机器语言。
C)
CPU最早是由Intel公司发明的。
D)
同样主频下，32位的CPU比16位的CPU运行速度快一倍。
2、关于计算机内存下面的说法哪些是正确的：
A)
随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。
B)
一般的个人计算机在同一时刻只能存/取一个特定的内存单元。
C)
计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。
D)
1MB内存通常是指1024*1024字节大小的内存。
3、关于操作系统下面说法哪些是正确的：
A.
多任务操作系统专用于多核心或多个CPU架构的计算机系统的管理。
B.
在操作系统的管理下，一个完整的程序在运行过程中可以被部分存放在内存中。
C.
分时系统让多个用户可以共享一台主机的运算能力，为保证每个用户都得到及时的响应通常会采用时间片轮转调度的策略。
D.
为了方便上层应用程序的开发，操作系统都是免费开源的。
4、关于计算机网络，下面的说法哪些是正确的：
A)
网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方案。
B)
新一代互联网使用的IPv6标准是IPv5标准的升级与补充。
C)
TCP/IP是互联网的基础协议簇，包含有TCP和IP等网络与传输层的通讯协议。
D)
互联网上每一台入网主机通常都需要使用一个唯一的IP地址，否则就必须注册一个固定的域名来标明其地址。
5、关于HTML下面哪些说法是正确的：
A)
HTML全称超文本标记语言，实现了文本、图形、声音乃至视频信息的统一编码。
B)
HTML不单包含有网页内容信息的描述，同时也包含对网页格式信息的定义。
C)
网页上的超链接只能指向外部的网络资源，本网站网页间的联系通过设置标签来实现。
D)
点击网页上的超链接从本质上就是按照该链接所隐含的统一资源定位符（URL）请求网络资源或网络服务。
6、若3个顶点的无权图G的邻接矩阵用数组存储为{{0，1，1}，{1，0，1}，{0，1，0}}，假定在具体存储中顶点依次为:
v1，v2，v3
关于该图，下面的说法哪些是正确的：
A)该图是有向图。
B)该图是强连通的。
C)该图所有顶点的入度之和减所有顶点的出度之和等于1。
D)从v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。
7、在带尾指针（链表指针clist指向尾结点）的非空循环单链表中每个结点都以next字段的指针指向下一个节点。假定其中已经有2个以上的结点。下面哪些说法是正确的：
A)
如果p指向一个待插入的新结点，在头部插入一个元素的语句序列为：
p^.next:=
clist^.next;
clist^.next:=
p;
B)
如果p指向一个待插入的新结点，在尾部插入一个元素的语句序列为：
p^.next:=
clist;
clist^.next:=
p;
C)
在头部删除一个结点的语句序列为：
p:=
clist^.next;
clist^.next:=
clist^.next^.next;
dispose(p);
D)
在尾部删除一个结点的语句序列为。
p:=
clist;
clist:=
clist
^.next;
dispose(p);
8、散列表的地址区间为0-10,散列函数为H(K)=K
mod
11。采用开地址法的线性探查法处理冲突，并将关键字序列26，25，72，38，8，18，59存储到散列表中，这些元素存入散列表的顺序并不确定。假定之前散列表为空，则元素59存放在散列表中的可能地址有：
A)
5
B)
7
C)
9
D)
10
9、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪些排序算法是稳定的：
A)
插入排序
B)
基数排序
C)
归并排序
D)
冒泡排序
10、在参加NOI系列竞赛过程中，下面哪些行为是被严格禁止的：
A)
携带书写工具，手表和不具有通讯功能的电子词典进入赛场。
B)
在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。
C)
通过互联网搜索取得解题思路。
D)
在提交的程序中启动多个进程以提高程序的执行效率。
三．问题求解（共2题，每空5分，共计10分）
1．拓扑排序是指将有向无环图G中的所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若
∈E(G)，则u在线性序列中出现在v之前，这样的线性序列成为拓扑序列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为
。
3
2
1
5
4
7
6
8
9
2．某个国家的钱币面值有1,7,72,73共计四种，如果要用现金付清10015元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通
张钱币。
四．阅读程序写结果（共4题，每题8分，共计32分
篇2：深入开展信息学奥赛之我见
深入开展信息学奥赛之我见 本文关键词：我见，深入开展，信息学，奥赛
深入开展信息学奥赛之我见 本文简介：深入开展信息学奥赛之我见安徽省蚌埠第九中学张恩权[email protected]摘要：信息学奥林匹克竞赛是一项益智性的竞赛活动，核心是考查参赛选手的智力、分析问题解决问题能力、使用计算机编程解题的能力。它的外在表现是用计算机来解决问题，实质是多学科、多种能力的综合体现。关键词：信息学奥赛政策学生辅
深入开展信息学奥赛之我见 本文内容：
深入开展信息学奥赛之我见
安徽省蚌埠第九中学
张恩权
[email protected]
摘要：信息学奥林匹克竞赛是一项益智性的竞赛活动，核心是考查参赛选手的智力、分析问题解决问题能力、使用计算机编程解题的能力。它的外在表现是用计算机来解决问题，实质是多学科、多种能力的综合体现。
关键词：信息学
奥赛
政策
学生
辅导
全国青少年信息学奥林匹克竞赛是由中国计算机学会主办的一项面向全国青少年的信息学竞赛和普及活动。也是与联合国教科文组织提倡的国际信息学奥林匹克竞赛，同步进行的一项竞赛活动。旨在向那些在中学阶段学习的青少年普及计算机科学知识；给学校的信息技术教育课程提供动力和新的思路；给那些有才华的学生提供相互交流和学习的机会；通过竞赛和相关的活动培养和选拔优秀计算机人才。
信息学奥林匹克竞赛是一项益智性的竞赛活动，核心是考查参赛选手的智力、分析问题解决问题能力、使用计算机编程解题的能力。信息学奥林匹克竞赛要求参赛选手有如下能力：针对竞赛题目中的要求构建数学模型，构造出有效的算法和选用相应的数据结构，写出高级语言程序，上机调试通过。现从我自己近几年来信息学辅导教学实践经验出发谈谈体会。
一、
政策上的支持
一个省、市的竞赛成绩，很大程度上取绝于相关领导是否重视该项比赛、是否在政策上给予该项竞赛一定的扶持。信息学奥赛更需要这些政策的支持。
1.争夺家长的关注
信息学奥赛所涉及的知识范畴大大的超越了学生在中学阶段“文化课”学习中所学习的内容，那么必然需要学生利用大量的课余时间去学习很多、很难、期末考试不考、中高考不考的算法、数据结构……面对着中、高考的压力，家长是否能关注到这项竞赛？家长是否能支持学生？
很多家长宁愿把孩子送去学唱歌、舞蹈、书法也不学编程，原因就是将来对他们没用。当然我不否认艺术对一个人的成长的重要，但是对于一个学生学习思维的培养，我认为信息学奥赛所涉及的知识内容、对问题的思考方式甚至是学习方式更有利于他们的养成一个好的学习习惯、思维方式。
2.激发学生的兴趣
兴趣永远是最好的老师，兴趣也是学生学习的最大动力。对于还没有认识到程序魅力的学生，如何把他吸引到信息学奥赛家庭中来？如果有一定的政策照顾，我想在学生的第一印象里会对我们这项奥赛产生好感。
3.调动老师的积极性
在这里要谈一谈这个很庸俗的问题——辅导老师的待遇，从事信息学奥赛辅导老师要比从事其他学科奥赛的老师耗费更多的时间和精力，而然他们在学校里的地位、待遇与付出是不成正比的。所以有些老师就产生了消极情绪，以一种所谓的“靠天收”方式去应付比赛，给学生一本书，自己看成什么样就什么样，反正考好考坏都那样。
这些年，全国各级部门都开始重视这项奥赛，NOI的保送、NOIP的自主招生资格，都在积极引起社会的关注。我市教育局也大力的推出了一系列的政策，来激励我市选手。如中考加分，理科实验班招生降低20分录取等等，大大调动了选手们和家长们的积极性。
二、梯队的培养
无论金字塔的塔尖如何炫彩夺目，它必然需要一个庞大而坚固的底座在支撑着它。我们信息学奥赛也应该建造出这种结构的梯队，层层选拔。
1.小学基础语言培训
低年级开展Logo语言培训，初步培养学生编程思维。高年级开展pascal或c++培训。让学生能熟练应用一种高级语言，了解编程的思想。
2.初中基础算法和数据结构培训
已在小学阶段解决了语言关的学生，可以放手开展基础算法和数据结构的培训。同时可以让学生的战场转移到网上题库（在线测试平台），通过练习让学生打下坚实的编程基础。
3.高中拔高
学习更为高深的算法、数据结构和数学知识。如：动态规划、网络流、二分图、线段树、平衡树、组合数学、离散数学……
这是从一个市的角度去看待梯队的建设，当然在一个学校也需要建设一支好的梯队。每年都有学生要毕业，每年都有新生加入，在老选手培养的同时千万不能忽视新生的培训，以老带新是一种非常有效的手段。
三、老师的付出
一个选手从起步到收获，这中间是一个漫长而曲折的过程，在这个过程里，老师充当着一个指引者的角色。为了让学生少走弯路，那么这些弯路就要靠老师去走，走过了以后才知道哪些地方是弯路，这就赋予了老师更多的责任。
1.老师必须有着扎实的编程基础
与各学科的奥赛一样,信息学竞赛的内容超出了现行的中学教学大纲，其难度甚至超越了高考试题的等级。作为一个好的指导老师，必须具备独立解决各种奥赛难题的能力。当然这不是件容易的事，尤其是随着竞赛历史的发展，试题的范围也越来越宽阔，我们必须去不断的学习，才能适应试题的变化。
2.教师要成为学生学习的指引者
《老子》中指出“授人以鱼不如授人以渔”，在培训辅导的工作中，要把重点放在指导学生如何去学，如何去思考，如何去总结他所学的。
3.老师要注重学生综合素质的发展
一个真正优秀的选手必须是一个综合素质健全的人，正如信息学国际金牌选手何林同学给吴文虎教授的一封信中说道：“我认为我真正学到的是习惯、态度和方法。我学会了批判性的看问题、我学会了用开阔的胸怀去接受所有不同的想法、我学会了分析问题、总结问题、乃至提出问题的一系列方法和经验。这些才是无价之宝，是一辈子在任何地方任何时候都不会丢的宝贝。”
四、选手的勤奋
要做一个成功的竞赛选手，就必须具备两样素质，一是良好的学习态度，二是良好的学习方法。态度决定这成败，也决定着你在竞赛之路上会走多远。对于我们信息学竞赛选手，最重要的学习方法就是自学，因为信息学竞赛涉及到的知识面太广了，老师不可能逐一讲到，而且更多的算法是要考选手自己悟出其中的道理，才能熟练应用并加以变化。这就需要选手要花费大量的时间、精力去研究各种算法和数学上的书籍。
值得注意的是，如果仅仅只是看书还是远远不够的，必须通过大量的练习去把看到的知识融会贯通，学为己用。现在网络上有很多优秀的在线测试平台，应该鼓励学生去网上写题。在写题的过程中熟练编程语言、总结学习效果、完善自己的知识体系。
信息学奥赛的外在表现是用计算机来解决问题，实质是多学科、多种能力的综合体现。我们所做的一切都是为了使学生在将来学习生活的道路上能够更好的发展。信息学奥赛是项光荣的事业，让我们把有限的生命奉献给无限的事业吧！
参考文献
李学武
《关于开展信息学奥林匹克活动的一些思考》
http://www.gzlfdn.cn/article.php?id=160
《全国青少年信息学奥林匹克竞赛系列活动简介》
http://www.noi.cn
篇3：信息学奥赛中级班总复习题
信息学奥赛中级班总复习题 本文关键词：复习题，信息学，奥赛，中级班
信息学奥赛中级班总复习题 本文简介：备考注意事项：1.6条语句的空模板2.路径：file-changdir3.时间的控制3个小时4个题目，或者3.5个小时5个题目。4.环境笔，草稿纸，计算机（不能上网的！）循环结构的程序设计For循环语句：如果希望重复执行一组语句，而且重复的次数事先是确定的，而不依赖于循环中语句的运行结果。While
信息学奥赛中级班总复习题 本文内容：
备考注意事项：
1.
6条语句的空模板
2.
路径：file-chang
dir
3.
时间的控制3个小时4个题目，或者3.5个小时5个题目。
4.
环境
笔，草稿纸，计算机（不能上网的！）
循环结构的程序设计
For循环语句：如果希望重复执行一组语句，而且重复的次数事先是确定的，而不依赖于循环中语句的运行结果。
While
循环语句：不知道重复的次数，只知道满足某条件要执行或不执行，所以布尔表达式所含变量在循环语句中一定要有更改，否则变死循环。
Repeat
循环语句
数组
A[i]
前移
i:=i-1
后退
i:=i+1
位置关系：A[I,j]
上一行
I-1
下一行i+1
前一列
j-1
后一列j+1
主对角线：i=j
对称关系a[I,j]
a[j,i]
上三角
I=j
次对角线：I+j=n+1
对称关系
a[I,j]
a[n+1-j,n+1-i]
上三角
I+j=n+1
排序，一定要滚瓜烂熟
=================================================================================
1.
计算1+2+3+4…+n之和
1*2*3*···*n
2+4+6+···+n
1+1/2+1/3+···+1/n
12+22+32+···+n2
2.
键入一个自然数x，求这个自然数的所有约数（包括1和x本身）之和
3.
编程找出四位整数abcd中满足下述关系的数：（ab+cd）*（ab+cd）=abcd
4.
输出1-n之间的所有奇数
5.
输入若干个字符（以‘#’作为结束），计算输入的字符串字母‘a’或‘A’出现的次数
6.
求输入的一个整数的各位数字之和
7.
求两个自然数m，n的最小公倍数
8.
从n个数中挑选出最大的数
9.
求100-999中的水仙花数。什么是水仙花数呢？若三位数abc，满足：abc=a3+b3+c3，则成为abc为水仙花数。如153，13+53+33=1+125+27=153，所以153是水仙花数。
10.
请编程输出图形（以前上课时候涉及到的所有图形）
11.
求出2-n之间的所有质数（素数）
12.
求两个自然数M和N的最大公约数
13.
已知faibonacai数列的前几个数分别为0，1，1，2，3，5，8，13.。。。，编程求此数列的前n项
14.
按照顺序输入n个数据，以逆序方式输出
15.
将a数组中第一个元素移到数组末尾，其余数据依次往前平移一个位置。
16.
对于数组a，假设它的所有元素师按照递增顺序存放的。现在输入一个x，如果x存在于数组a中，则要把x元素删除；否则将x插在相应的位置，保持a数值的所有元素仍然递增。
17.
从键盘输入n个数，将它们按照从小到大的顺序存储并输出。
18.读入n个数，输出偶数项及它们的和；输出奇数项及它们的平均数。
19.读入n个数，输出其中的最大数及其位置号。
20.有一数组（设有n个），其排列顺序如下：3，6，11，45，23，70，67，34，26，89，90，15，56，50，20，10。编一程序交换这组数中任意指定的两段不重合数据。
21.给定一串整数数列，求出所有的递增和递减子序列的数目。如数列7，2，6，9，8，3，5，2，1可分为（7，2），（2，6，9），（9，8，3），（3，5），（5，2，1）5个子序列，答案就是5。我们称2，9，3，5为转折元素。
22.将1-9这9个数字分为三组（每个数字只能使用一次），分别组成三个三位数，且这三个三位数的值构成为1：2：3的比例，试求出所有满足条件的三个三位数。
23.设数组a是一个有n个元素的整数数组，从中找出最大和的子序列。
24.已知数组a中含有n个整数元素，求a中有多少个最大数？多少个次大数？。。。。多少个互不相同的数？
25.打印出n以内以二进制和十进制正读和反读都一样的整数。
26读入n个正整数，将其按从小到大的顺序排列，输出每个数出现的次数及其在原序列中的位置。
27.约瑟夫问题。
N个人围成一圈，从第一个人开始报数，数到k的人出圈。再由下一个开始报数，数到k的人出圈，。。。。依次出圈的为6、4、3、5、8、7、2、1.
28.多项式的和。
对于一个一元多项式，可以表示为：y=a1xb1+
a2xb2+
a3xb3+···+
anxbn，可以约定b1，b2····bn从大到小排列，且a1，a2···an均不为0。求任意两个多项式的和。输出时只需打印a、b序列值即可。如3x4+2x+1输出格式为：
3
4
2
1
1
0
多项式的输入可以模仿以上格式。
29.回文算术
任给一个三位数abc（10进制），算出abc与cba之和。若该和数不是回文数（即从左向右读与从右向左读是同一数，如19391），再按上述方法求和。以此类推，直到得到回文形式的和数或者和数位数已超过15位时中止计算。
30．找马鞍数
求一个n*n数阵中的马鞍数，输出它的位置。所谓马鞍数，是指在行赏最小而在列上最大的数。如下为一个n=5的例子：
5
6
7
8
9
4
5
6
7
8
3
4
5
2
1
2
3
4
9
0
1
2
5
4
8
则第一行第一列个的数5就是马鞍数。思考：马鞍数一定有吗？是唯一的吗？
31.数学黑洞6174
已知：一个任意的四位正整数。将数字重新组合成一个最大的数和最小的数相减，重复这个过程，最多七步，必得6174.将永远出不来。求证：所有四位数数字（全相同的除外），均能得到6174.输出掉进黑洞的步数。
32.做一个加法器
完成30000以内的加法，两个加数间用“+”连接，可以连加，回车表示式子输入完成；“#”表示结束运算，退出加法器
33.
将用逗号隔开的两个英语单词交换位置输出
34.
输入一行字符，包含若干个单词，约定相邻的两个单词用空格隔开，编程统计单词的个数
35.
对输入的一句子实现查找且置换的功能（找到某个子串并换成另一子串）。