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

《第十二届全国青少年信息学奥林匹克联赛初赛试题.doc》由会员分享，可在线阅读，更多相关《第十二届全国青少年信息学奥林匹克联赛初赛试题.doc（14页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第十二届全国青少年信息学奥林匹克联赛初赛试题提高组C 语言二小时完成全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效一、单项选择题共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.。1.在以下各项中。不是CPU的组成局部。A.控制器B.运算器C.存放器D.ALUE.RAM2. BIOS根本输入输出系统是一组固化在计算机内上一个ROM芯片上的程序。A.控制器B.CPUC.主板D.内存条E.硬盘3.在下面各世界顶级的奖项中，为计算机科学与技术领域作出出色奉献的科学家设立的奖项是。A.沃尔夫奖B.诺贝尔奖C.菲尔兹奖D.图灵奖E.南丁格尔奖4在编程时使用任一种高级语言，不一定是C，如

2、果需要从磁盘文件中输入一个很大的二维数组例如1000*1000的double型数组，按行读即外层循环是关于行的与按列读即外层循环是关于 列的相比，在输入效率上。A.没有区别B.有一些区别，但机器处理速度很快，可忽略不计C.按行读的方式要高一些D.按列读的方式要高一些E.取决于数组的存储方式。5在C语言中，表达式212的值是A.441B.42346在C语言中，判断a不等于0且b不等于0的正确的条件表达式是A.!a=0|!b=0B.!(a=0)&(b=0)C.!(a=0&b=0) D. a!=0 |b!=0E. a & b7某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。某时刻该车站状态

3、为空，从 这一时刻开场的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出。假设车辆入站的顺序为1，2，3，那么车辆出站的顺序为。A. 1, 2,3, 4,5B. 1, 2,4, 5,7C. 1, 4, 3, 7, 6D. 1, 4,3, 7,2E. 1, 4,3, 7, 58高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点， 那么该树的树高为。A.10B.11C.12D.13E.21019.与十进制数5对应的八进制数是。A.3352.5B.3350.5C

4、.D.151E.前4个答案都不对10将5个数的序列排序，不管原先的顺序如何，最少都可以通过次比拟，完成从小到大的排序。A.6B.7C.8D.9E.10二、不定项选择题共10题，每题1.5分，共计15分。每题正确答案的个数大于或等于1。多项选择 或少选均不得分。11.设A=B=D=true，C=E=false，以下逻辑运算表达式值为真的有。A.(AB)(CD)EB.(AB)C)DE)C. A(BCDE)D.(A(BC)DE12.(2021)16+ (32)8的结果是。A. (8234)10B.(202A)1613.设栈S的初始状态为空，元素a, b,c, d,e依次入栈，以下出栈序列不可能出现的

5、有。A.a,b,c,e,dB.b,c,a,e,dC.a,e,c,b,dD.d,c,e,b,a14.6个结点的二叉树的先根遍历是1 2 3456数字为结点的编号，以下同，后根遍历是3 2 5 641，那么该二叉树的可能的中根遍历是A. 3 2 1465B. 3 2 1 5 4 6C.231546D.23146515.在以下各数据库系统软件中，以关系型数据库为主体构造的是。A.ACCESSB.SQLServerC.OracleD.Foxpro16.在以下各软件中，属于NOIP竞赛复赛推荐使用的语言环境有。A.gcc/g+B.TurboPascalC.TurboCD.freepascal17.以下断

6、电之后将不能保存数据的有。A.硬盘B.ROMC.显存D.RAM18.在以下关于计算机语言的说法中，正确的有。A. Pascal和C都是编译执行的高级语言B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上C. C+是历史上的第一个支持面向对象的计算机语言D.高级语言比汇编语言更高级，是因为它的程序的运行效率更高19.在以下关于计算机算法的说法中，正确的有。A.一个正确的算法至少要有一个输入B.算法的改良，在很大程度上推动了计算机科学与技术的进步C.判断一个算法的好坏，主要依据它在某台计算机上具体实现时的运行时间D.目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机

7、上实施的有效算法20.在以下关于青少年信息学竞赛的说法中，你赞成的是此题不答复为0分，答题一律总分值。A.举行信息学竞赛的目的，是为了带动广阔青少年学科学、爱科学，为造就一大批优秀的计算机科学 与技术人才奠定良好的根底B.如果竞赛优胜者不能直接保送上大学，我今后就不再参与这项活动了C.准备竞赛无非要靠题海战术，为了取得好成绩，就得拼时间、拼体力D.为了取得好成绩，不光要看智力因素，还要看非智力因素。优秀选手应该有坚韧不拔的意志，有 严谨求实的作风，既要努力奋进，又要胜不骄败不馁三问题求解共2题，每题5分，共计10分1将2006个人分成假设干不相交的子集，每个子集至少有3个人，并且：1在每个子集

8、中，没有人认识该子集的所有人。2同一子集的任何3个人中，至少有2个人互不认识。3对同一子集中任何2个不相识的人，在该子集中恰好只有1个人认识这两个人。 那么满足上述条件的子集最多能有_个？2将边长为n的正三角形每边n等分，过每个分点分别做另外两边的平行线，得到假设干个正三角形， 我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最 下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上图中是n=5时一条通路的例子。设n=10，那么该正三角形的不同的通路的总数为

9、_。四阅读程序写结果共4题，每题8分，共计32分1. #include int main()int i,u4,v4,x,y=10;for(i=0;i10)y+=(v2*100-v3)/(uu0%3*5);elsey+=20+(v2*100-v3)/(uv0%3*5);printf(%d,%dn,x,y);return0; /*注：本例中，给定的输入数据可以防止分母为0或下标越界。*/输入：9 394输出：_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;jmi;j+)t*=2;printf(%ld,

10、(t*2-1)*t); printf(n);输出:_3#include stdio.h#defineN7int fun1(char s,char a,intn)intj;j=n;while(a0) j-;returnj;int fun2(char s,char a,intn)intj;j=1;while(asj & j=n) j+;returnj;void main()charsN+1;intk,p;for(k=1;k=N;k+)sk=A+2*k+1;p=fun1(s,M,N);printf(“%dn,p+fun2(s,M,N);输出：_4.#includevoid digit(long n,

11、long m)if(m0)printf(%2ld,n%10);if(m1)digit(n/10,m/10);printf(%2ld,n%10); main()longx,x2;printf(Inputanumber:n);scanf(%ld,&x);x2=1;while(x2x)x2*=10;x2/=10;digit(x,x2);printf(n); 输入：9734526输出：_五完善程序(前5空，每空2分，后6空，每空3分，共28分)1选排列下面程序的功能是利用递归方法生成从1到n(n10)的n个数中取k(1=k=n)个数的全部可能的排列不一定按升序输出。例如，当n=3，k=2时，应该输出每

12、行输出5个排列：121321233231程序：#include int n,k,a10; long count=0;void perm2(int j)int i,p,t;if()for(i=k;i=n;i+)count+;t=ak;ak=ai;ai=t;for()printf(%1d,ap);/*%1d中是数字1，不是字母l */printf();t=ak;ak=ai;ai=t;if(count%5=0)printf(n); return; for(i=j;i=n;i+)t=aj;aj=ai;ai=t;t=aj;main()int i;printf(nEntryn,k(k=n):n);scan

13、f(%d%d,&n,&k);for(i=1;i4-2-1-5-3。遗传算法的核心是通过两个个体的穿插操作，产生两 个新的个体。下面的程序给出了最简单的一种穿插算法。具体过程如下：(1)选定中间一段作为互换段，该段的起止下标为t1，t2，随机生成t1，t2后，互换两段。(2)互换后，在每个新的排列中可能有重复数字，因而不能作为新个体的编码，一般再做两步处理：)将两个互换段中，共同的数字标记为0，表示已处理完。)将两个互换段中其余数字标记为1，按顺序将互换段外重复的数字进展替换。 例如：n=12，两个个体分别是：a1:1354*2679*1012811a2: 3 2112 * 6 710 11 *

14、8 5 49 t1=5，t2=8。上述每一行中，两个星号间的局部为互换段。假定数组的下标从1开场，互换后有：a1: 1 354* 6 7 10 11* 10 12 8 11a2:32112*2679*8549然后，将数字6,7对应的项标记为0，星号内数字2,9,10,11对应的项标记为1，并且按顺序对 应关系为:102，119。于是，将a19=10替换为a19=2，将a22=2替换为a22=10，类似再做第2组替换。这样处理后，就得到了两个新个体：a1:1354 67101121289a2:3101122679854113输出两个新个体的编码。 程序：#include#include#defi

15、neN20int a1N,a2N,kz1N,kz2N，n;int rand1(int k)int t=0;while(tk)t=(int)(double)rand()/RAND_MAX*k);returnt;void read1(int a,int m)读入数组元素a1至am，a0=0，略。void wrt1(int a,int m)输出数组元素a1至am，略。void cross(int a1,int a2,int t1, int t2, intn)int i,j,k,t,kj;for(i=t1;i=t2; i+)t=a1i;；for(i=1;i=n;i+)if(it2)kz1i=kz2i=

16、-1;else；for(i=t1;i=t2;i+)for(j=t1;j=t2;j+)if(a1i=a2j);break; for(i=t1;i=t2;i+)if(kz1i=1)for(j=t1;j=t2;j+)if(kz2j=1)kj=j;break;for(j=1;j=n;j+)if()a1j=a2kj;break; for(j=1;j5):n);scanf(%d,&n);printf(input array1 (%dnumbers):n,n);read1(a1,n);printf(input array2 (%dnumbers):n,n);read1(a2,n);t1=rand1(n-1)

17、;dot2=rand1(n-1);while(t1=t2);if(t1t2)k=t1;t1=t2;t2=k; 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. ABCD16. 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. 114. 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) aj=ai;ai=t perm2(1)2 a1i=a2i;a2i=t kz1i=kz2i=1 kz1i=kz2j=0 a1j=a1i & kz1j=-1 a2j=a2kj & kz2j=-1 cross(a1,a2,t1,t2,n)