NOIP初赛提高组C++试题资料下载.pdf
《NOIP初赛提高组C++试题资料下载.pdf》由会员分享，可在线阅读，更多相关《NOIP初赛提高组C++试题资料下载.pdf（9页珍藏版）》请在冰点文库上搜索。
（b=0）&
（c=0）E.!
（a=0）|（b=0）|（c=0）7地面上有标号为A、B、C的3根细柱，在A柱上放有10个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3，将A柱上的部分盘子经过B柱移入C柱，也可以在B柱上暂存。
如果B柱上的操作记录为：
“进，进，出，进，进，出，出，进，进，出，进，出，出”。
那么，在C柱上，从下到上的盘子的编号为（）。
A.243657B.241257C.243176D.243675E.214375NOIP2007初赛试题（提高组C+）中国计算机学会200728.与十进制数17.5625对应的8进制数是（）。
A.21.5625B.21.44C.21.73D.21.731E.前4个答案都不对9欧拉图G是指可以构成一个闭回路的图，且图G的每一条边恰好在这个闭回路上出现一次（即一笔画成）。
在以下各个描述中，不一定是欧拉图的是（）。
A.图G中没有度为奇数的顶点B.包含欧拉环游的图（欧拉环游是指通过图中每边恰好一次的闭路径）C.包含欧拉闭迹的图（欧拉迹是指通过图中每边恰好一次的路径）D.存在一条回路，通过每个顶点恰好一次E.本身为闭迹的图10.一个无法靠自身的控制终止的循环称为“死循环”，例如，在C语言程序中，语句“while
（1）printf（“*”）;
”就是一个死循环，运行时它将无休止地打印*号。
下面关于死循环的说法中，只有（）是正确的。
A.不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环，因而，任何编译系统都不做死循环检验B有些编译系统可以检测出死循环C.死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查出死循环D.死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也是可以检测的E.对于死循环，只能等到发生时做现场处理，没有什么更积极的手段二、二、不定项选择题不定项选择题（共（共10题，每题题，每题1.5分，共计分，共计15分。
每题正确答案的个数大于或等于分。
每题正确答案的个数大于或等于1。
多选或少选均不得分）。
11.设A=B=true，C=D=false，以下逻辑运算表达式值为真的有（）。
A.（AB）（CDA）B.（AB）C）D）C.A（BCD）DD.（A（DC）B12.命题“PQ”可读做P蕴涵Q，其中P、Q是两个独立的命题。
只有当命题P成立而命题Q不成立时，命题“PQ”的值为false，其他情况均为true。
与命题“PQ”等价的逻辑关系式是（）。
A.PQB.PQC.（PQ）D.（QP）13.（2070）16+（34）8的结果是（）。
A.（8332）10B.（208C）16C.（100000000110）2D.（20214）8NOIP2007初赛试题（提高组C+）中国计算机学会2007314.已知7个结点的二叉树的先根遍历是1245637（数字为结点的编号，以下同），后根遍历是4652731，则该二叉树的可能的中根遍历是（）A.4265173B.4256137C.4231547D.425617315.冗余数据是指可以由其他数据导出的数据，例如，数据库中已存放了学生的数学、语文和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看作冗余数据。
冗余数据往往会造成数据的不一致，例如，上面4个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。
下面关于冗余数据的说法中，正确的是（）。
A.应该在数据库中消除一切冗余数据B.与用高级语言编写的数据处理系统相比，用关系数据库编写的系统更容易消除冗余数据C.为了提高查询效率，在数据库中可以适当保留一些冗余数据，但更新时要做相容性检验D.做相容性检验会降低效率，可以不理睬数据库中的冗余数据16.在下列各软件中，属于NOIP竞赛（复赛）推荐使用的语言环境有（）。
A.gccB.g+C.TurboCD.freepascal17.以下断电之后仍能保存数据的有（）。
A.硬盘B.ROMC.显存D.RAM18.在下列关于计算机语言的说法中，正确的有（）。
A.高级语言比汇编语言更高级，是因为它的程序的运行效率更高B.随着Pascal、C等高级语言的出现，机器语言和汇编语言已经退出了历史舞台C.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上D.C是一种面向过程的高级计算机语言19.在下列关于算法复杂性的说法中，正确的有（）。
A.算法的时间复杂度，是指它在某台计算机上具体实现时的运行时间B.算法的时间复杂度，是指对于该算法的一种或几种主要的运算，运算的次数与问题的规模之间的函数关系C.一个问题如果是NPC类的，就意味着在解决该问题时，不存在一个具有多项式时间复杂度的算法。
但这一点还没有得到理论上的证实，也没有被否定D.一个问题如果是NP类的，与C有相同的结论20.近20年来，许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具。
在下列关于递归算法的说法中，正确的是（）。
NOIP2007初赛试题（提高组C+）中国计算机学会20074A.在1977年前后形成标准的计算机高级语言“FORTRAN77”禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间B.和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些C.对于较复杂的问题，用递归方式编程往往比非递归方式更容易一些D.对于已经定义好的标准数学函数sin（x），应用程序中的语句“y=sin（sin（x）;
”就是一种递归调用三问题求解（共三问题求解（共2题，每题题，每题5分，共计分，共计10分）分）1给定n个有标号的球，标号依次为1，2，n。
将这n个球放入r个相同的盒子里，不允许有空盒，其不同放置方法的总数记为S（n,r）。
例如，S（4,2）=7，这7种不同的放置方法依次为
（1）,（234）,
（2）,（134）,（3）,（124）,（4）,（123）,（12）,（34）,（13）,（24）,（14）,（23）。
当n=7,r=4时，S（7,4）=_。
2N个人在操场里围成一圈，将这N个人按顺时针方向从1到N编号，然后，从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。
依次做下去，直到操场只剩下一个人，记这个人的编号为J（N），例如，J（5）=3，J（10）=5，等等。
则J（400）=_。
（提示：
对N=2m+r进行分析，其中0r2m）。
四阅读程序写结果（共四阅读程序写结果（共4题，每题题，每题8分，共计分，共计32分）分）1#includevoidmain（）inti,p5,q5,x,y=20;
for（i=0;
ipi;
q0=（p0+p1）+（p2+p3+p4）/7;
q1=p0+p1/（p2+p3）/p4）;
q2=p0*p1/p2;
q3=q0*q1;
q4=q1+q2+q3;
x=（q0+q4+2）-p（q3+3）%4;
if（x10）y+=（q1*100-q3）/（pp4%3*5）;
elsey+=20+（q2*100-q3）/（pp4%3*5）;
coutx,yendl;
NOIP2007初赛试题（提高组C+）中国计算机学会20075/注：
本例中，给定的输入数据可以避免分母为0或数组元素下标越界。
输入：
66553输出：
_2#includevoidfun（int*a,int*b）int*k;
k=a;
a=b;
b=k;
voidmain（）inta=3,b=6,*x=&
a,*y=&
b;
fun（x,y）;
coutNo.1:
a,b;
fun（&
a,&
b）;
coutNo.2:
a,bendl;
输出:
_3#include#include#includemath.hvoidmain（）inta151=0;
inti,j,t,t2,n=50;
for（i=2;
i=sqrt（n）;
i+）if（a1i=0）t2=n/i;
for（j=2;
j=t2;
j+）a1i*j=1;
t=0;
i=n;
i+）if（a1i=0）coutsetw（4）i;
t+;
if（t%10=0）coutendl;
coutendl;
输出：
_NOIP2007初赛试题（提高组C+）中国计算机学会20076_4.#include#includecharch=q,A,S,O,R,T,E,X,A,M,P,L,E;
intn=12;
voidshift（intk,intn）charv;
intj;
v=chk;
j=k+k;
while（j=n）if（jn）&
（chjchj+1）j+;
if（v0;
k-）shift（k,n）;
;
for（k=1;
k=n;
k+）coutchk;
cout0;
k-）tmp=ch1;
ch1=chk;
chk=tmp;
shift（1,k-1）;
voidmain（）intk;
hpsrt（）;
NOIP2007初赛试题（提高组C+）中国计算机学会20077输出：
__五完善程序五完善程序（前前5空，每空空，每空2分，后分，后6空，每空空，每空3分，共分，共28分分）1（格雷码，（格雷码，GrayCode）格雷码是对十进制数的一种二进制编码。
编码顺序与相应的十进制数的大小不一致。
其特点是：
对于两个相邻的十进制数，对应的两个格雷码只有一个二进制位不同。
另外，最大数与最小数之间也仅有一个二进制位不同，以4位二进制数为例，编码如下：
十进制数格雷码十进制数格雷码00000811001000191101200111011113001011111040110121010501111310116010114100170100151000如果把每个二进制的位看作一个开关，则将一个数变为相邻的另一个数，只须改动一个开关。
因此，格雷码广泛用于信号处理、数-模转换等领域。
下面程序的任务是：
由键盘输入二进制数的位数n（n16），再输入一个十进制数m（0m2n），然后输出对应于m的格雷码（共n位，用数组gr存放）。
为了将程序补充完整，你必须认真分析上表的规律，特别是对格雷码固定的某一位，从哪个十进制数起，由0变为1，或由1变为0。
#include#includevoidmain（）intbound=1,m,n,i,j,b,p,gr15;
coutInputn,m:
nm;
for（i=1;
i+）bound=;
if（m=bound）coutDataerror!
endl;
b=1;
i+）NOIP2007初赛试题（提高组C+）中国计算机学会20078p=0;
b=b*2;
for（;
j=m;
j+）if（）p=1-p;
gri=p;
for（i=n;
）coutsetw
（1）gri;
2（连续邮资问题）（连续邮资问题）某国发行了n种不同面值的邮票，并规定每封信最多允许贴m张邮票，在这些约束下，为了能贴出1，2，3,，maxvalue连续整数集合的所有邮资，并使maxvalue的值最大，应该如何设计各邮票的面值？
例如，当n=5、m=4时，面值设计为1，3，11，15，32，可使maxvalue达到最大值70（或者说，用这些面值的1至4张邮票可以表示不超过70的所有邮资，但无法表示邮资71。
而用其他面值的1至4张邮票如果可以表示不超过k的所有邮资，必有k70）。
下面是用递归回溯求解连续邮资问题的程序。
数组x1:
n表示n种不同的邮票面值，并约定各元素按下标是严格递增的。
数组bestx1:
n存放使maxvalue达到最大值的邮票面值（最优解），数组ymaxl用于记录当前已选定的邮票面值x1:
i能贴出的各种邮资所需的最少邮票张数。
请将程序补充完整。
#include#defineNN20#definemaxint30000#definemaxl500intn,m,bestxNN,xNN,ymaxl,maxvalue=0;
voidresult（）intj;
coutr=maxvalueendl;
for（j=1;
j=n;
j+）coutbestxj;
coutendl;
voidbacktrace（inti,intr）intj,k,zmaxl;
for（j=0;
j=;
j+）if（yjm）for（k=1;
k=m-yj;
k+）NOIP2007初赛试题（提高组C+）中国计算机学会20079if（yj+k=y）y=yj+k;
while（yrn）if（r-1maxvalue）maxvalue=;
j+）bestxj=xj;
return;
for（k=0;
kmaxl;
k+）zk=yk;
for（j=;
j=r;
j+）xi=j;
k+）yk=zk;
voidmain（）intj;
coutinputn,m:
jmaxl;
j+）yj=maxint;
y0=0;
x0=0;
x1=1;
backtrace（2,1）;
result（）;
升级会员 