当前位置:首页 >> 学科竞赛 >>

第十二届全国青少年信息学奥林匹克联赛初赛试题


第十二届全国青少年信息学奥林匹克联赛初赛试题
( 提高组 C 语言

二小时完成



●● 全部试题答案均要求写在答卷纸上, 写在试卷纸上一律无效 ●● 一、 单项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题有且仅 有一个正确答案.) 。 1. 在以下各项中。 ( )不是 CPU 的组成部分。 C. 寄存 )上一 C. 主 E. 硬盘

A. 控制器 B. 运算器 器 D. ALU E. RAM 2. BIOS(基本输入输出系统)是一组固化在计算机内( 个 ROM 芯片上的程序。 A. 控制器 板 B. CPU D. 内存条

3.在下面各世界顶级的奖项中, 为计算机科学与技术领域作出杰出贡献的科学家设立的 奖项是 ( ) 。 A. 沃尔夫奖 奖 D. 图灵奖 C. 菲尔兹奖 E. 南丁格尔奖 B. 诺贝尔

4. 在编程时 (使用任一种高级语言, 不一定是 C) , 如果需要从磁盘文件中输入一个很大 的二维数组 (例 如 1000*1000 的 double 型数组) ,按行读(即外层循环是关于行 的)与按列读(即外层循环是关于 列的)相比,在输入效率上( ) 。 A. 没有区别 速度很快,可忽略不计 B. 有一些区别,但机器处理

C. 按行读的方式要高一些 D. 按列读的方式要高一 些 E. 取决于数组的存储方式。 5.在 C 语言中,表达式 21^2 的值是( A. 441 .24 E.25 B. 42 )
由 OIF ans.c n 收 集

C.23

D

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 7.某个车站呈狭长形,宽度只能容下一台车,并且只有一个出入口。已知某时刻该车 站状态为空,从 这一时刻开始的出入记录为: “进,出,进,进,进,出,出,进,进, 进, 出,出” 。 假设车辆入站的 顺序为 1, 2, 3, ……, 则车辆出站的顺序为 ( ) 。

A. 1, 2, 3, 4, 5 5, 7 D. 1, 4, 3, 7, 2

B. 1, 2, 4, C. 1, 4, 3, 7, 6 E. 1, 4, 3, 7, 5
由 OIFans.c n 收 集

8.高度为 n 的均衡的二叉树是指:如果去掉叶结点及相应的树枝,它应该是高度 为 n-1 的满二叉树。 在这里, 树高等于叶结点的最大深度, 根结点的深度为 0, 如果某个均衡的二叉树共 有 2381 个结点, 则该树的树高为( ) 。 A. 10 B. 11 C. 12 D. 13 E. 2 – 1
10

9. 与十进制数 1770.625 对应的八进制数是( A. 3352.5 C. 3352.1161 D. 3350.1151 B. 3350.5

) 。

E. 前 4 个答案都不对 ) D. 9

10. 将 5 个数的序列排序, 不论原先的顺序如何, 最少都可以通过 ( 次比较, 完成从小到大的排序。
由 OIFans .cn 收集

A. 6 E. 10

B. 7

C. 8

二、 不定项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题正确 答案的个数大于或等于 1。多选 或少选均不得分) 。 11. 设 A=B=D=true,C=E=false,以下逻辑运算表达式值为真的有 ( )。 A. (? A∧B)∨(C∧D)∨ ? E C. A∧(B∨C∨D∨E) 12. (2010)
10 16

B.? (((A∧B)∨C)∧D∧E) D. (A∧(B∨C)) ∧D∧E

+ (32) 的结果是(
8

) 。
16

A. (8234)

B. (202A)
2

C. (100000000110)

D. (2042)

16

13. 设栈 S 的初始状态为空,元素 a, b, c, d, e 依次入栈,以下出栈序列不可 能出现的有( )。 A. a, b, c, e, d C. a, e, c, b, d B. b, c, a, e, d D. d, c, e, b, a

14. 已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6 (数字为结点的编号, 以下同) ,后根遍历是 3 2 5 6 4 1,则该二叉树的可能的中根遍历是( )

A. 3 2 1 4 6 5 C. 2 3 1 5 4 6

B. 3 2 1 5 4 6 D. 2 3 1 4 6 5 ) 。
由 OIF ans .c n 收集

15. 在下列各数据库系统软件中, 以关系型数据库为主体结构的是 ( A. ACCESS C. Oracle B. SQL Server D. Foxpro

16.在下列各软件中,属于 NOIP 竞赛(复赛)推荐使用的语言环境有 ( ) 。 A. gcc/g++ C. Turbo C 17. 以下断电之后将不能保存数据的有( A. 硬盘 B. ROM B. Turbo Pascal D. free pascal )。 C. 显存 )。 D. RAM

18. 在下列关于计算机语言的说法中,正确的有( A. Pascal 和 C 都是编译执行的高级语言

B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 C. C++是历史上的第一个支持面向对象的计算机语言 D. 高级语言比汇编语言更高级,是因为它的程序的运行效率更高 19. 在下列关于计算机算法的说法中,正确的有( A. 一个正确的算法至少要有一个输入 B. 算法的改进,在很大程度上推动了计算机科学与技术的进步 C. 判断一个算法的好坏,主要依据它在某台计算机上具体实现时的运行时间 D. 目前仍然存在许多涉及到国计民生的重大课题,还没有找到能够在计算机上实施的 有效算法 20. 在下列关于青少年信息学竞赛的说法中, 你赞成的是 ( 题不回答为 0 分,答题一律满分)。 ) (本 )。

A. 举行信息学竞赛的目的,是为了带动广大青少年学科学、爱科学,为造就一大批优秀 的计算机科学 与技术人才奠定良好的基础 B. 如果竞赛优胜者不能直接保送上大学,我今后就不再参与这项活动了 C. 准备竞赛无非要靠题海战术,为了取得好成绩,就得拼时间、拼体力 D. 为了取得好成绩,不光要看智力因素,还要看非智力因素。优秀选手应该有坚韧不拔 的意志,有 严谨求实的作风,既要努力奋进,又要胜不骄败不馁 三.问题求解(共 2 题,每题 5 分,共计 10 分) 1.将 2006 个人分成若干不相交的子集,每个子集至少有 3 个人,并且:
由 OIFans .c n 收集

(1)在每个子集中,没有人认识该子集的所有人。 (2)同一子集的任何 3 个人中,至少有 2 个人互不认识。 (3)对同一子集中任何 2 个不相识的人,在该子集中恰好只 有 1 个人认识这两个人。 则满足上述条件的子集最多能有 ___________个? 2. 将边长为 n 的正三角形每边 n 等分, 过每个分点分别做另外两边的平行线, 得到若干个正三角形,我们称为小三角形。 正三角形的一条通路是一条连续的折线, 起点是最上面的一个小三角形, 终点是最 下面一行位于中间的小三角形。 在通路中, 只允许由一个小三角形走到另一个与其有公共边的且位于同 一行或下一行的小三 角形, 并且每个小三角形不能经过两次或两次以上 (图中是 n=5 时一条通路的 例 子) 。设 n=10,则该正三角形的不同的通路的总数为_____________。 四.阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. #include <stdio.h> 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)
由 OIFans .cn 收集 由 OIFans .c n 收集

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

输出:_______________

2.#include <stdio.h> main() {int i,j,m[]={2,3,5,7,13}; long t; for (i=0;i<=4;i++) {t=1; for(j=1;j<m[i];j++) printf("%ld } printf("\n"); } 输出:____________________ 3.#include "stdio.h" #define N 7 t*=2;
由 OIFans.c n 收 集

",(t*2-1)*t);

int fun1(char s[],char a,int n) {int j; j=n; while(a<s[j] && j>0) 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];
由 OIFans.c n 收 集

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)); } 输出:_____________

4.#include <stdio.h> 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"); x2=1; while(x2<x) x2/=10;
由 OIFans.c n 收集

scanf("%ld",&x);

x2*=10;

digit(x,x2); printf("\n"); } 输入:9734526

输出:______________________________

五.完善程序 (前 5 空,每空 2 分,后 6 空,每空 3 分,共 28 分)

1(选排列) . 下面程序的功能是利用递归方法生成从 1 到 n(n<10)的 n 个数中取 k(1<=k<=n)个数的 全部可能的排列(不一定按升序输出) 。例如,当 n=3,k=2 时, 应该输出(每行输出 5 个排列) : 12 13 31 程序: #include < stdio.h> int n,k,a[10]; long count=0; void perm2(int j) {int i,p,t; if( ① ) 21 23 32

{for(i=k;i<=n;i++) {count++; t=a[k]; a[k]=a[i]; a[i]=t; for( ② ) /* "%1d"中是数字 1,不是字母 l */

printf("%1d",a[p]); printf(" ");

t=a[k];a[k]=a[i];a[i]=t; if(count%5==0) printf("\n"); }
由 OIF ans.c 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++) ⑤ } 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,两个个体分别是:
由 OIFans.cn 收集

a[i]=i;

;

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 a2: 3 2 1 12 * 2 6 7 * 6 7 10 11 * 10 12 8 11 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 2 6 6 7 10 11 7 9 2 12 8 8 9 5

a2: 3 10 1 12 4 11 (3) 输出两个新个 体的编码。 程序: #include <stdio.h> #include <stdlib.h> #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++)




由 OIFans.c n 收 集

if(i<t1 || i>t2) kz1[i]=kz2[i]=-1; else




for(i=t1;i<=t2;i++) for(j=t1;j<=t2;j++) if(a1[i]==a2[j]) { } for(i=t1;i<=t2;i++) if(kz1[i]==1) {for(j=t1;j<=t2;j++)


;

break;

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"); printf("input array 1 (%d'numbers):\n",n); scanf("%d",&n);

read1(a1,n);

printf("input array 2 (%d'numbers):\n",n); t1=rand1(n-1); do {t2=rand1(n-1); }while(t1==t2); if(t1>t2) {k=t1; t1=t2; t2=k; }


read1(a2,n);

由 OIFans.c n 收集

wrt1(a1,n); }

wrt1(a2,n);

提高组(C 语言)参考答案与评分标准

一、单项选择题:(每题 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;p<=k;p++ ③ perm2(j+1) ④ a[j]=a[i];a[i]=t ⑤ perm2(1) 2.① a1[i]=a2[i];a2[i]=t ② kz1[i]=kz2[i]=1 ③ kz1[i]=kz2[j]=0 ④ a1[j]==a1[i] && kz1[j]==-1

⑤ a2[j]==a2[kj] && kz2[j]==-1 ⑥ cross(a1,a2,t1,t2,n)


赞助商链接
相关文章:
第十二届全国青少年信息学奥林匹克联赛初赛试题
第十二届全国青少年信息学奥林匹克联赛初赛试题_学科竞赛_小学教育_教育专区。第十二届全国青少年信息学奥林匹克联赛初赛试题( 提高组 C 语言 二小时完成 ) ●● ...
...2017全国青少年信息学奥林匹克联赛提高组初赛试题答...
NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案_学科竞赛_高中教育_教育专区。信息学奥林匹克联赛提高组初赛试题及答案。 ...
CCF NOIP2010全国青少年信息学奥林匹克联赛初赛试题
CCF NOIP2010全国青少年信息学奥林匹克联赛初赛试题 - 第十六届全国青少年信息学奥林匹克联赛初赛试题试题及答案 NOIP2010(Pascal 提高组) 一、单项选择题 1.与 16...
(2012)第十八届全国青少年信息学奥林匹克联赛初赛普及组
(2012)第十八届全国青少年信息学奥林匹克联赛初赛普及组_学科竞赛_高中教育_教育专区。第十八届全国青少年信息学奥林匹克联赛初赛(普及组 Pascal 语言试题) 竞赛时间:...
第十三届全国青少年信息学奥林匹克联赛初赛试题
第十三届全国青少年信息学奥林匹克联赛初赛试题( 提高组 C++ 语言二小时完成 )●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效●●一、 单项选择题 ...
第20届全国青少年信息学奥林匹克联赛pascal初赛试题及答案
第二十届全国青少年信息学奥林匹克联赛初赛 普及组 Pascal 语言试题 竞赛时间:2014 年 10 月 12 日 14:30-16:30 一、单项选择题(共 20 题,每题 1.5 分,...
第十七届全国青少年信息学奥林匹克联赛初赛试题
第十七届全国青少年信息学奥林匹克联赛初赛试题( 提高组●● C++语言 两小时完成 )●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 一、单项选择题 ...
2014第二十届全国青少年信息学奥林匹克联赛初赛试题
2014 第二十届全国青少年信息学奥林匹克联赛初赛 普及组 Pascal 语言试题 竞赛时间:2014 年 10 月 12 日 14:30-16:30 一、单项选择题(共 20 题,每题 1.5...
第十二届全国青少年信息学奥林匹克联赛初赛试题
第十二届全国青少年信息学奥林匹克联赛初赛试题_学科竞赛_高中教育_教育专区。第十二届全国青少年信息学奥林匹克联赛初赛试题 word 第十二届全国青少年信息学奥林匹克...
全国青少年信息学奥林匹克联赛初赛练习卷(六)答案
全国青少年信息学奥林匹克联赛初赛练习卷(六)答案 (普及组 PASCAL 语言 二小时完成) ●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一、单项...
更多相关标签: