NOIP-c++-.pdf

《NOIP-c++-.pdf》由会员分享，可在线阅读，更多相关《NOIP-c++-.pdf（9页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、尔奖4在编程时（使用任一种高级语言，不一定是C+），如果需要从磁盘文件中输入一个很大的二维数组（例如 1000*1000的 double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。A.没有区别B.有一些区别，但机器处理速度很快，可忽略不计 C.按行读的方式要高一些D.按列读的方式要高一些E.取决于数组的存储方式。5在 C+中，表达式 212 的值是（）A.441 B.42 C.23 D.24 E.25 6在 C+中，判断 a 不等于 0 且 b 不等于 0 的正确的条件表达式是（）A.!a=0|!b=0 B.!(a=0)&(b=0)C.!(a

3、=0&b=0)D.a!=0|b!=0 E.a&b 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 8高度为 n 的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1 的满二叉树。1在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381 个结点，则该树的树高为

4、（）。A.10 B.11 C.12 D.13 E.210 1 9.与十进制数 1770.625 对应的八进制数是（）。A.3352.5 B.3350.5 C.3352.1161 D.3350.1151 E.前 4 个答案都不对10 将 5 个数的序列排序，不论原先的顺序如何，最少都可以通过（）次比较，完成从小到大的排序。A.6 B.7 C.8 D.9 E.10 二、不定项选择题（共 10 题，每题 1.5分，共计 15 分。每题正确答案的个数大于或等于1。多选或少选均不得分）。11.设A=B=D=true，C=E=false，以下逻辑运算表达式值为真的有（）。A.(AB)(C D)?E B.?

5、(AB)C)DE)C.A(B CDE)D.(A(B C)DE 12.(2010)16+(32)8的结果是（）。A.(8234)10 B.(202A)16C.(100000000110)2 D.(2042)16 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 14.已知 6 个结点的二叉树的先根遍历是1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（）A.3 2 1 4 6 5 B.3 2

6、 1 5 4 6 C.2 3 1 5 4 6 D.2 3 1 4 6 5 15.在下列各数据库系统软件中，以关系型数据库为主体结构的是（）。A.ACCESS B.SQL Server C.Oracle D.Foxpro 16.在下列各软件中，属于NOIP 竞赛（复赛）推荐使用的语言环境有（）。A.gcc/g+B.Turbo Pascal C.Turbo C D.free pascal 217.以下断电之后将不能保存数据的有（）。A.硬盘 B.ROM C.显存 D.RAM 18.在下列关于计算机语言的说法中，正确的有（）。A.Pascal和C都是编译执行的高级语言B.高级语言程序比汇编语言程序更

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

8、批优秀的计算机科学与技术人才奠定良好的基础B.如果竞赛优胜者不能直接保送上大学，我今后就不再参与这项活动了C.准备竞赛无非要靠题海战术，为了取得好成绩，就得拼时间、拼体力D.为了取得好成绩，不光要看智力因素，还要看非智力因素。优秀选手应该有坚韧不拔的意志，有严谨求实的作风，既要努力奋进，又要胜不骄败不馁三问题求解（共 2 题，每题 5 分，共计 10 分）1将 2006 个人分成若干不相交的子集，每个子集至少有3 个人，并且：（1）在每个子集中，没有人认识该子集的所有人。（2）同一子集的任何 3 个人中，至少有 2 个人互不认识。（3）对同一子集中任何2 个不相识的人，在该子集中恰好只有1 个

9、人认识这两个人。则满足上述条件的子集最多能有_个？2将边长为 n 的正三角形每边 n 等分，过每个分点分别做另外两边的平行线，得到若干个正三角形，我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是n=5 时一条通路的例子）。设 n=10，则该正三角形的不同的通路的总数为_。3四阅读程序写结果（共4 题，每题 8 分，共计 32 分）1.#include void main()int i,u4,v4

10、,x,y=10;for(i=0;iui;v0=(u0+u1+u2+u3)/7;v1=u0/(u1-u2)/u3);v2=u0*u1/u2*u3;v3=v0*v1;x=(v0+v1+2)-u(v3+3)%4;if(x10)y+=(v2*100-v3)/(uu0%3*5);else y+=20+(v2*100-v3)/(uv0%3*5);cout x,yendl;/本例中，给定的输入数据可以避免分母为0 或下标越界。输入：9 3 9 4 输出：_ 2.#include void main()int i,j,m=2,3,5,7,13;long t;for(i=0;i=4;i+)t=1;for(j=1

11、;jmi;j+)t*=2;cout(t*2-1)*t ;cout endl;4输出:_ 3.#include iostream.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(asj&j=n)j+;return j;void main()char sN+1;int k,p;for(k=1;k=N;k+)sk=A+2*k+1;p=fun1(s,M,N);cout p+fun2(s,M,N)endl;输出：_ 4

12、.#include#include void digit(long n,long m)if(m0)cout setw(2)1)digit(n/10,m/10);cout setw(2)n%10;void main()long x,x2;cout Input a number:x;x2=1;while(x2x)x2*=10;x2/=10;digit(x,x2);cout endl;输入：9734526 输出：_ 五完善程序(前 5 空，每空 2 分，后 6 空，每空 3 分，共 28 分)1（选排列）下面程序的功能是利用递归方法生成从1 到 n(n10)的 n 个数中取 k(1=k=n)个数的全

13、部可能的排列（不一定按升序输出）。例如，当 n=3，k=2 时，应该输出（每行输出5 个排列）：12 13 21 23 32 31 程序：#include#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()coutsetw(1)ap;cout ;t=ak;ak=ai;ai=t;if(count%5=0)cout endl;return;for(i=j;i=n;i+)t=aj;aj=ai;ai=t;6 t=aj;void main()

14、int i;cout nEntry n,k(k=n)nnk;for(i=1;i=n;i+)ai=i;cout 4-2-1-5-3。遗传算法的核心是通过两个个体的交叉操作，产生两个新的个体。下面的程序给出了最简单的一种交叉算法。具体过程如下：(1)选定中间一段作为互换段，该段的起止下标为t1，t2，随机生成 t1，t2 后，互换两段。(2)互换后，在每个新的排列中可能有重复数字，因而不能作为新个体的编码，一般再做两步处理：(2.1)将两个互换段中，共同的数字标记为0，表示已处理完。(2.2)将两个互换段中其余数字标记为1，按顺序将互换段外重复的数字进行替换。例如：n=12，两个个体分别是：a1:

15、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，并且按顺序对应关系为:102，119。于是，将 a19=10替换为 a19=2，将 a22=2替换为 a22=10，类似再做第 2 组替换。这样处理后，就得到了两个新个体：

16、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 7#define N 20 int a1N,a2N,kz1N,kz2N,n;int rand1(int k)int t=0;while(tk)t=(int)(double)rand()/RAND_MAX*k);return t;void read1(int a,int m)读入数组元素 a1至 am，a0=0，略。void wrt1(int a,int m)输出数组元素 a1至 am，略。void cross(

17、int a1,int a2,int t1,int t2,int n)int i,j,t,kj;for(i=t1;i=t2;i+)t=a1i;；for(i=1;i=n;i+)if(it2)kz1i=kz2i=-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;j=n;j+)8 if()a2j=a1i;break;kz1i=kz2kj=0;void main()int k,t1,t2;cout 5):n;cout input array 1(n numbers):endl;read1(a1,n);cout input array 2(n numbers):t2)k=t1;t1=t2;t2=k;wrt1(a1,n);wrt1(a2,n);9