第十二届全国青少年信息学奥林匹克联赛初赛试题
（提高组C 语言二小时完成）
● ● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●
一、单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.）。
1. 在以下各项中。（）不是CPU的组成部分。
A. 控制器
B. 运算器
C. 寄存器
D. ALU
E. RAM
答案：E
知识点：
寄存器是中央处理器内的组成部份。寄存器是有限存贮容量的高速存贮部件，它们可用来暂存指令、数据和位址。在中央处理器的控制部件中，包含的寄存器有指令寄存器(IR)和程序计数器(PC)。在中央处理器的算术及逻辑部件中，包含的寄存器有累加器(ACC)。
寄存器是内存阶层中的最顶端，也是系统获得操作资料的最快速途径。寄存器通常都是以他们可以保存的位元数量来估量，举例来说，一个“8 位元寄存器”或“32 位元寄存器”。寄存器现在都以寄存器档案的方式来实作，但是他们也可能使用单独的正反器、高速的核心内存、薄膜内存以及在数种机器上的其他方式来实作出来。
寄存器通常都用来意指由一个指令之输出或输入可以直接索引到的暂存器群组。更适当的是称他们为“架构寄存器”。
例如，x86 指令及定义八个 32 位元寄存器的集合，但一个实作x86 指令集的 CPU 可以包含比八个更多的寄存器。
寄存器是CPU内部的元件，寄存器拥有非常高的读写速度，所以在寄存器之间的数据传送非常快。
算术逻辑单元 (Arithmetic-Logic Unit, ALU)是中央处理器(CPU)的执行单元，是所有中央处理器的核心组成部分，由"And Gate" 和
"Or Gate"构成的算术逻辑单元，主要功能是进行二位元的算术运算，如加减乘(不包括整数除法)。基本上，在所有现代CPU体系结构中，二进制都以补码的形式来表示。
2. BIOS（基本输入输出系统）是一组固化在计算机内（）上一个ROM芯片上的程序。
A. 控制器
B. CPU
C. 主板
D. 内存条
E. 硬盘
答案：C
分析：BIOS是英文"Basic Input Output System"的缩略语，直译过来后中文名称就是"基本输入输出系统"。其实，它是一组固化到计算机内主板上一个ROM
芯片上的程序，它保存着计算机最重要的基本输入输出的程序、系统设置信息、开机后自检程序和系统自启动程序。其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。BIOS芯片是主板上一块长方型或正方型芯片。
3. 在下面各世界顶级的奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是（）。
A. 沃尔夫奖
B. 诺贝尔奖
C. 菲尔兹奖
D. 图灵奖
E. 南丁格尔奖
答案：D
根据知识迁徙，有第十五届第一题可知
1、关于图灵机下面的说法哪个是正确的：
A)图灵机是世界上最早的电子计算机。
B)由于大量使用磁带操作，图灵机运行速度很慢。
C)图灵机只是一个理论上的计算模型。
D)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
【分析】选择C
A最早的计算机是ENIAC B图灵机是计算机模型，没有运行速度，更谈不上磁带操作
C图灵机是英国人阿兰图灵提出的理论，
阿兰图灵本人在二战中破译德军密码系统发挥重要作用，而不是图灵机发挥作用。
4．在编程时（使用任一种高级语言，不一定是C），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。
A. 没有区别
B. 有一些区别，但机器处理速度很快，可忽略不计
C. 按行读的方式要高一些
D. 按列读的方式要高一些
E. 取决于数组的存储方式。
答案：E
5．在C语言中，表达式21^2的值是（）
A. 441
B. 42
C.23
D.24
E.25
答案：C
解析：需将其转化成二进制再计算
（21）10=（10101）2
（2）10=（10）2
21^2=（10101）2^（10）2=（10110）2=（23）10
答案：A
6．在C语言中，判断a不等于0且b不等于0的正确的条件表达式是（）
A. !a==0 || !b==0
B. !((a==0)&&(b==0))
C. !(a==0&&b==0)
D. a!=0 || b!=0
E. a && b
分析：’！’为取反符号，所以“||”取反为“&&”,”&&”取反为“||”
答案：E
7．某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（）。
A. 1, 2, 3, 4, 5
B. 1, 2, 4, 5, 7
C. 1, 4, 3, 7, 6
D. 1, 4, 3, 7, 2
E. 1, 4, 3, 7, 5
答案：C
分析：1 1 2 3 4 43 5 6 7 7 6
8．高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。
在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（）。
A. 10
B. 11
C. 12
D. 13
E. 210 – 1
答案：B
分析：log(2,2381)=11
9. 与十进制数1770.625 对应的八进制数是（）。
A. 3352.5
B. 3350.5
C. 3352.1161
D. 3350.1151
E. 前4个答案都不对
答案：C
分析：解析：（1770）10=（3352）8
0.625*8=5取整5
所以：（1770.625）10=（3352.5）8
答案：A
10．将5个数的序列排序，不论原先的顺序如何，最少都可以通过（）次比较，完成从小到大的排序。
A. 6
B. 7
C. 8
D. 9
E. 10
答案：B
见于十四届T5
二、不定项选择题（共10题，每题1.5分，共计15分。每题正确答案的个数大于或等于1。多选或少选均不得分）。
11. 设A=B=D=true，C=E=false，以下逻辑运算表达式值为真的有（）。
A. (A∧B)∨(C∧D)∨?E
B. ??(((A∧B)∨C)∧D∧E)
C. A∧(B∨C∨D∨E)
D. (A∧(B∨C)) ∧D∧E
答案：ABC
分析：见于十三届，十四届
12. (2010)16 + (32)8的结果是（）。
A. (8234)10
B. (202A)16
C. (100000000110)2
D. (2042)16
答案：AB
分析：见于十三届，十四届
13. 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（）。
A. a, b, c, e, d
B. b, c, a, e, d
C. a, e, c, b, d
D. d, c, e, b, a
答案：C
根据先进先出原则可判断C错误
14. 已知6个结点的二叉树的先根遍历是1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（）
A. 3 2 1 4 6 5
B. 3 2 1 5 4 6
C. 2 3 1 5 4 6
D. 2 3 1 4 6 5
答案：BC
分析：见于十三届，十四届
插图
1
2 4
3 5 6
15. 在下列各数据库系统软件中，以关系型数据库为主体结构的是（）。
A. ACCESS
B. SQL Server
C. Oracle
D. Foxpro
答案：ABCD
16.在下列各软件中，属于NOIP竞赛（复赛）推荐使用的语言环境有（）。
A. gcc/g++
B. Turbo Pascal
C. Turbo C
D. free pascal
答案：AD
分析：综合见十三届T16.十四届T19
17. 以下断电之后将不能保存数据的有（）。
A. 硬盘
B. ROM
C. 显存
D. RAM
答案：CD
见于十三届T17
18. 在下列关于计算机语言的说法中，正确的有（）。
A. Pascal和C都是编译执行的高级语言
B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上
C. C++是历史上的第一个支持面向对象的计算机语言
D. 高级语言比汇编语言更高级，是因为它的程序的运行效率更高
答案：AB
根据常识
19. 在下列关于计算机算法的说法中，正确的有（）。
A. 一个正确的算法至少要有一个输入
B. 算法的改进，在很大程度上推动了计算机科学与技术的进步
C. 判断一个算法的好坏，主要依据它在某台计算机上具体实现时的运行时间
D. 目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法
答案：BD
20. 在下列关于青少年信息学竞赛的说法中，你赞成的是（）（本题不回答为0分，答题一律满分）。
A. 举行信息学竞赛的目的，是为了带动广大青少年学科学、爱科学，为造就一大批优秀的计算机科学与技术人才奠定良好的基础
B. 如果竞赛优胜者不能直接保送上大学，我今后就不再参与这项活动了
C. 准备竞赛无非要靠题海战术，为了取得好成绩，就得拼时间、拼体力
D. 为了取得好成绩，不光要看智力因素，还要看非智力因素。优秀选手应该有坚韧不拔的意志，有严谨求实的作风，既要努力奋进，又要胜不骄败不馁
答案：自选
三．问题求解（共2题，每题5分，共计10分）
1．将2006个人分成若干不相交的子集，每个子集至少有3个人，并且：
（1）在每个子集中，没有人认识该子集的所有人。
（2）同一子集的任何3个人中，至少有2个人互不认识。
（3）对同一子集中任何2个不相识的人，在该子集中恰好只有1个人认识这两个人。
则满足上述条件的子集最多能有 401 个？
2．将边长为n的正三角形每边n等分，过每个分点分别做另外两边的平行线，得到若干个正三角形，我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是n=5时一条通路的例子）。设n=10，则该正三角形的不同的通路的总数为 9! 。
四．阅读程序写结果（共4题，每题8分，共计32分）
1. #include
int main()
{int i,u[4],v[4],x,y=10;
for(i=0;i<=3;i++)
scanf("%d", &u[i]);
v[0]=(u[0]+u[1]+u[2]+u[3])/7;
v[1]=u[0]/((u[1]-u[2])/u[3]);
v[2]=u[0]*u[1]/u[2]*u[3];
v[3]=v[0]*v[1];
x=(v[0]+v[1]+2)-u[(v[3]+3)%4];
if(x>10)
y+= (v[2]*100-v[3])/(u[u[0]%3]*5);
else
y+=20+(v[2]*100-v[3])/(u[v[0]%3]*5);
printf("%d,%d\n", x,y);
return 0;
} /*注：本例中，给定的输入数据可以避免分母为0或下标越界。*/
输入：9 3 9 4
输出： -13,57
2．#include
main()
{int i,j,m[]={2,3,5,7,13};
long t;
for (i=0;i<=4;i++)
{t=1;
for(j=1;j
printf("%ld ",(t*2-1)*t);
}
printf("\n");
}
输出: 6 28 496 8128 33550336
3．#include "stdio.h"
#define N 7
int fun1(char s[],char a,int n)
{int j;
j=n;
while(a0) j--;
return j;
}
int fun2(char s[],char a,int n)
{int j;
j=1;
while(a>s[j] && j<=n) j++;
return j;
}
void main()
{char s[N+1];
int k,p;
for(k=1;k<=N;k++)
s[k]='A'+2*k+1;
p=fun1(s,'M',N);
printf(“%d\n”,p+fun2(s,'M',N));
}
输出：__11
4.#include
void digit(long n,long m)
{if(m>0)
printf("%2ld",n%10);
if(m>1)
digit(n/10,m/10);
printf("%2ld",n%10);
}
main()
{long x,x2;
printf("Input a number:\n"); scanf("%ld",&x);
x2=1;
while(x2
x2/=10;
digit(x,x2);
printf("\n");
}
输入：9734526
输出： 6 2 3 4 5 2 9 9 7 3 4 5 2 6
五．完善程序(前5空，每空2分，后6空，每空3分，共28分)
1．（选排列）下面程序的功能是利用递归方法生成从1到n(n<10)的n个数中取k(1<=k<=n)个数的全部可能的排列（不一定按升序输出）。例如，当n=3，k=2时，应该输出（每行输出5个排列）：
12 13 21 23 32
31
程序：
#include
int n,k,a[10];
long count=0;
void perm2(int j)
{int i,p,t;
if( ①)
{for(i=k;i<=n;i++)
{count++;
t=a[k]; a[k]=a[i]; a[i]=t;
for( ②)
printf("%1d",a[p]); /* "%1d"中是数字1，不是字母l */
printf(" ");
t=a[k];a[k]=a[i];a[i]=t;
if(count%5==0) printf("\n");
}
return;
}
for(i=j;i<=n;i++)
{t=a[j];a[j]=a[i];a[i]=t;
③;
t=a[j]; ④;
}
}
main()
{int i;
printf("\nEntry n,k (k<=n):\n");
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++) a[i]=i;
⑤;
}
2．（TSP问题的交叉算子）TSP问题(Traveling Salesman Problem)描述如下：给定n个城市，构成一个完全图，任何两城市之间都有一个代价（例如路程、旅费等），现要构造遍历所有城市的环路，每个城市恰好经过一次，求使总代价达到最小的一条环路。
遗传算法是求解该问题的一个很有效的近似算法。在该算法中，一个个体为一条环路，其编码方法之一是1到n这n个数字的一个排列，每个数字为一个城市的编号。例如当n=5时，“3 4 2 1 5”表示该方案实施的路线为3->4->2->1->5->3。遗传算法的核心是通过两个个体的交叉操作，产生两个新的个体。下面的程序给出了最简单的一种交叉算法。具体过程如下：
(1)选定中间一段作为互换段，该段的起止下标为t1，t2，随机生成t1，t2后，互换两段。
(2)互换后，在每个新的排列中可能有重复数字，因而不能作为新个体的编码，一般再做两步处理：(2.1) 将两个互换段中，共同的数字标记为0，表示已处理完。
(2.2) 将两个互换段中其余数字标记为1，按顺序将互换段外重复的数字进行替换。
例如：n=12，两个个体分别是：
a1: 1 3 5 4 * 2 6 7 9 * 10 12 8 11
a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9
t1=5，t2=8。上述每一行中，两个星号间的部分为互换段。假定数组的下标从1开始，互换后有：
a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11
a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9
然后，将数字6,7对应的项标记为0，星号内数字2,9,10,11对应的项标记为1，并且按顺序对应关系为: 10<->2 ，11<->9。于是，将a1[9]=10替换为a1[9]=2，将a2[2]=2替换为a2[2]=10，类似再做第2组替换。这样处理后，就得到了两个新个体：
a1: 1 3 5 4 6 7 10 11 2 12 8 9
a2: 3 10 1 12 2 6 7 9 8 5 4 11
（3）输出两个新个体的编码。
程序：
#include
#include
#define N 20
int a1[N],a2[N],kz1[N],kz2[N]，n;
int rand1(int k)
{int t=0;
while(t<2|| t>k)
t=(int)((double)rand()/RAND_MAX*k);
return t;
}
void read1(int a[],int m)
{读入数组元素a[1]至a[m]，a[0]=0，略。}
void wrt1(int a[],int m)
{输出数组元素a[1]至a[m]，略。}
void cross(int a1[], int a2[],int t1, int t2, int n)
{int i,j,k,t,kj;
for(i=t1; i<=t2; i++)
{t=a1[i]; ①；
}
for(i=1;i<=n;i++)
if(it2)
kz1[i]=kz2[i]=-1;
else
②；
for(i=t1;i<=t2;i++)
for(j=t1;j<=t2;j++)
if(a1[i]==a2[j])
{ ③; break;
}
for(i=t1;i<=t2;i++)
if(kz1[i]==1)
{for(j=t1;j<=t2;j++)
if(kz2[j]==1)
{kj=j; break;
}
for(j=1;j<=n;j++)
if( ④)
{a1[j]=a2[kj];break;
}
for(j=1;j<=n;j++)
if( ⑤)
{a2[j]=a1[i]; break;
}
kz1[i]=kz2[kj]=0;
}
}
main()
{int k,t1,t2;
printf("input (n>5):\n"); scanf("%d",&n);
printf("input array 1 (%d'numbers):\n",n); read1(a1,n); printf("input array 2 (%d'numbers):\n",n); read1(a2,n); t1=rand1(n-1);
do
{t2=rand1(n-1);
}while(t1==t2);
if(t1>t2)
{k=t1; t1=t2; t2=k;
}
⑥
wrt1(a1,n); wrt1(a2,n);
}
参考答案与评分标准
一、单项选择题：（每题1.5分）
1. E
2. C
3. D
4. E
5. C
6. （满分）
7. C
8. B
9. A 10. B
二、不定项选择题：（每题1.5分）
11. ABC 12. AB 13. C 14. BC 15. ABCD
16. AD 17. CD 18.AB 19. BD 20. （满分，空白0分）
三、问题求解：（每题5分）
1. 401
2. 9! （或362880）
四、阅读程序写结果
1. -13，57 （对1个数给4分，无逗号扣1分）
2. 6 28 496 8128 33550336
（前2个对1个数给1分，后3个对1个数给2分）
3. 11
4. 6 2 5 4 3 7 9 9 7 3 4 5 2 6（数字之间无空格扣2分）
五、完善程序(前5空，每空2分，后6空，每空3分)
1．①j=k （或k=j）
②p:=1 to k
③perm2(j+1)
④a[j]:=a;a:=t
⑤perm2(1)
2．①a1:=a2;a2:=t
②kz1:=1;kz2:=1;
③kz1:=0;kz2[j]:=0;
④(a1[j]=a1)and(kz1[j]=-1)
⑤(a2[j]=a2[kj])and(kz2[j]=-1)
⑥cross(a1,a2,t1,t2,n)
《第十二届全国青少年信息学奥林匹克联赛初赛试题及参考答案》相关文档：
奥林匹克的认识09-30
《奥林匹克精神》教案10-23
奥林匹克精神教案10-23
《奥林匹克精神》教案10-23
幼儿园奥林匹克精神教育教案10-23
庆祝奥林匹克运动复兴25周年》教案10-23
奥林匹克精神优秀教案教学设计10-23
高中语文奥林匹克精神获奖教案苏教必修410-23
