NOIP2015年初赛提高组模拟试题

第1页共6页信息学初赛模拟试题一、选择题（共20题，每题1.5分，共计30分。前10题为单选题；后10题为不定项选择题）。1.微型计算机的性能主要取决于（C）。A）内存B）主板C）中央处理器D）硬盘E）显示器2.128KB的存储器用十六进制表示，它的最大的地址码是(C)A)10000B)EFFFC)1FFFFD)FFFFFE)FFFF3.能将高级语言程序转换为目标程序的是(D).A)调试程序B)解释程序C)编辑程序D)编译程序E)连接程序4．A=11001010B,B=00001111B,C=01011100B,则A∨B∧C=(D)BA)01011110B)00001111C)01011100D)11001110E)110010105.计算机病毒传染的必要条件是(B)。A)在内存中运行病毒程序B)对磁盘进行读写操作C)在内存中运行含有病毒的可执行程序D)复制文件E)删除文件6.TCP／IP协议共有(B)层协议A)3B)4C)5D)6E)77.192.168.0.1是属于(C).A)A类地址B)B类地址C)C类地址D)D类地址E)E类地址8.对给定的整数序列(54,73,21,35,67,78,63,24,89)进行从小到大的排序时,采用快速排序的第一趟扫描的结果是(A).A)(24,21,35,54,67,78,63,73,89)B)(24,35,21,54,67,78,63,73,89)C)(24,21,35,54,67,63,73,78,89)D)(21,24,35,54,63,67,73,78,89)E)(24,21,35,54,67,63,73,78,89)9.一棵n个结点的完全二叉树,则二叉树的高度h为(D).A)2nB)n2logC)2log2nD)1log2nE)2n-110.对右图进行广度优先拓扑排序得到的顶点序列正确的是(C).A)1,2,3,4,5,6B)1,3,2,4,5,6C)1,3,2,4,6,5D)1,2,3,4,6,5E)1,3,2,4,5,611.下列属于冯.诺依曼计算机模型的核心思想是(ABC).A)采用二进制表示数据和指令B)采用“存储程序”工作方式C)计算机硬件有五大部件(运算器、控制器、存储器、输入和输出设备)第2页共6页D)结构化程序设计方法E)计算机软件只有系统软件12.下列属于输入设备的是(BCD).A)打印机B)扫描仪C)光笔D)鼠标E)显示器13.算式(1000)10-(100)16-(10)8的结果是(CDE).A)(890)10B)(986)8C)(1011100000)2D)(2E0)16E)(736)1014.下面关于算法的正确的说法是(ACDE)A)算法必须有输出B)算法必须在计算机上用某种语言实现C)算法不一定有输入D)算法必须在执行有限步后能结束E)算法的每一步骤必须有确切的定义15.下列关于十进制数100的正确说法是(ABD).A)原码为01100100BB)反码为64HC)反码为9BHD)补码为64HE)补码为9BH16.关于windows系统中的窗口和对话框的说法正确的是(BC).A)对话框能移动和改变大小B)窗口能移动和改变大小C)对话框只能移动但不能改变大小D)对话框不能移动但能改变大小E)窗口能移动但不能改变大小17．下列逻辑运算正确的是（C）。A)A·（A+B）=AB)A+（A·B）=AC)A·（B+C）=A·B+A·CD)A+（B·C）=（A+B）·（A+C）E)A+1=A18.下列关于排序说法正确的是(ABC).A)插入排序、冒泡排序是稳定的B)选择排序的时间复杂性为O(2n)C)选择排序、希尔排序、快速排序、堆排序是不稳定的D)希尔排序、快速排序、堆排序的时间复杂性为O(nn2log)E)快速排序是速度最快的排序19.对于一个大小为3的栈，若输入队列为123456，则下列输出队列有可能的是（AE）。A)123456B)654321C)432165D)431256E)32165420.设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key)=key%13,其中%是求余数运算。用二次探查法解决冲突,则对于序列(８、31、20、33、18、53、27),则下列说法正确的是(BCDE)。A)27在1号格子中B)33在6号格子中C)31在5号格子中D)20在7号格子中E)18在4号格子中二．问题求解（5分*2=10分）第3页共6页1．一个商场有m种颜色的小球，每种小球足够多，在这m种小球中挑选n个小球的选法有多少种？如m=2，n=3时有4种选法分别是：两种小球的个数分别为03，12，21，30．问：当m=4，n=4时选法有____35______种。2．如果一棵m度树中有1n个度为1的结点，2n个度为2的结点，…….有mn个度为m的结点,则该树中叶结点的个数=______________.三.阅读程序写出正确的程序运行结果(4分*8=32分)1.varn:integer;functioncount(n:integer):integer;beginifn=1thencount:=0elseifnmod2=0thencount:=count(ndiv2)+1elsecount:=count(n*3+1)+1;end;beginreadln(n);writeln(count(n));end.输入:99输出:252.Vard1,d2,X,Min:real;beginMin:=10000;X:=3;whileX15dobegind1:=sqrt(9+(X-3)*(X-3));d2:=sqrt(4+(15-X)*(15-X));if(d1+d2)MinthenMin:=d1+d2;X:=x+0.001;end;writeln(Min:10:2);end.输出：13.003.varhi,lo:integer;procedurepl(m,n:integer;varhi,lo:integer);varI:integer;beginI:=n;hi:=0;lo:=0;RepeatI:=I-1;lo:=lo+m;Iflo=10000thenbeginLo:=lo-10000;Hi:=hi+1;End;UntilI=0;Write(hi:4,’,‘,lo:4);End;BeginP1(200,343,hi,lo);End.输出:6,8600第4页共6页4.vari,k,n:integer;x,w:array[1..500]ofinteger;beginreadln(n);fori:=1tondobeginx[i]:=0;w[i]:=1;end;fori:=2totrunc(sqrt(n))+1doifx[i]=0thenbegink:=i*i;whileK=ndobeginx[k]:=i;k:=k+i;end;end;fori:=ndownto1doifx[i]0thenbeginw[x[i]]:=w[x[i]]+w[i];w[idivx[i]]:=w[idivx[i]]+w[i];w[i]:=0;end;writeln(w[2],w[3]:5,w[5]:5);end.输入:20输出:1884四.完善程序题(4分*7=28分)1.降序组合.给定两个自然数n,r(nr),输出从数1到n中按降序顺序取r个自然数的所有组合.例如,n=5,r=3时,有如下组合:543542541532531521432431421321程序如下:programtk1;varn,r,i,j:integer;a:array[1..20]ofinteger;beginwrite('n,r=');第5页共6页repeatreadln(n,r);untilnr;i:=1;a[1]:=n;writeln('result:');repeatifirthenifa[i]r-ithenbegin___a[i+1]:=a[i]-1___;i:=i+1;endelsebegin___i:=i-1___;a[I]:=a[I]-1endelsebeginforj:=1tordowrite(a[j]:3);writeln;ifa[r]=1thenbegini:=i-1;a[i]:=a[i]-1;endelse___a[i]:=a[i]-1;___end;untila[1]=r-1;end.2.现在政府计划在某个区域内的的城市间架设高速公路，以使任意两个城市间能够直接或间接到达，怎样修路，费用最小。输入文件：第一行一个整数n(n=100)表示城市数目。第二行至第n+1行每行两个数xi,yi(0=xi,yi=100)表示第i个城市的坐标(单位:千米)；输出最小费用(每千米一个单位价格)。程序如下:programt6;constmaxn=100;第6页共6页typetcity=recordx,y:realend;varc:array[1..maxn]oftcity;d:array[1..maxn,1..maxn]ofreal;p:array[1..maxn]ofinteger;n,i,j,k:integer;a,min:real;beginreadln(n);fori:=1tondoreadln(c[i].x,c[i].y);fori:=1tondoforj:=1tondod[i,j]:=sqrt(sqr(c[i].x-c[j].x)+sqr(c[i].y-c[j].y));p[1]:=0;fori:=2tondo___p[i]:=1;___fori:=1ton-1dobeginmin:=1e10;forj:=1tondoif__(p[j]0)and(d[p[j],j]min)____thenbeginmin:=d[p[j],j];___k:=j;___end;a:=a+d[p[k],k];p[k]:=0;forj:=1tondoif___(p[j]0)and(d[p[j],k]d[p[j],j])___thenp[j]:=k;end;writeln(a:0:2);end.