信息学竞赛普及组初赛模拟试题(46页).doc

《信息学竞赛普及组初赛模拟试题(46页).doc》由会员分享，可在线阅读，更多相关《信息学竞赛普及组初赛模拟试题(46页).doc（45页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、-信息学竞赛普及组初赛模拟试题-第 45 页信息学竞赛普及组初赛模拟试题(五)一、选择题：（每题分，共计30分。每题有5个选项，前10题为单选题，后10题为不定项选择题，全部选对才得分）。1.二进制数11011011的十进制值是（）A.202B.219C.193D.2092.我国研制的银河型的超级计算机通过基准程序的测试，其峰值速度是（）A.80亿次B.100亿次C.130亿次D.150亿次3.程序段如下：FORI:=1TO5DOFORJ:=2TOIDOWriteln(*)输出*的个数是（）A.5B.10C.15D.25E.304.设待排序的记录为（49，38，65，97，76，13，27,4

2、9,55,4），经过下过程将序列排序第一趟：13,27,49,55,4,49,38,65,97,76第二趟：13,4,49,38,27,49,55,65,97,76第三趟：4,13,27,38,49,49,55,65,76,97问它所用的方法是：(A.冒泡排序B.直接选择排序C.直接插入排序D.希尔排序5.设无向树T有7片树叶，其余顶点度均为3，则T中3度顶点有多少个（）A.5B.7C.9D.4E.86.设连通图G的顶点数和边数与一立方体相同，即有8个顶点和12条边。任意一棵G的生成树的总边数为（）A7B.8C.9D.10E.117.设有两个散列函数h1(k)=kmod13和h2(k)=kmo

3、d11+1，散列表为T012，用二次散列法解决冲突。函数h1用来计算散列地址，当发生冲突时，h2作为计算下一个探测地址的地址增量。假定某一时刻散列表的状态为：0123456789101112804435下一个被插入的关键码为57，其插入的位置为( 。A.4B.5C.6D.7E.8请根据下面是一段PASCAL程序,判断第8、9题。forh:=1ton-1dobeginx:=Ah+1;k:=h;while(k=1)and(Akx)dobeginAk+1:=Ak;k:=k1endAk+1:=xend8.假设在程序开始执行时，数组A1n是一组随机整数。下列答案中，哪一个最好的描述了最差情况下的程序排序

4、的时间复杂度？（）A.O(nlog2n)B.O(n)C.O(log2n)D.O(n2)E.O(2n)9.假设在程序开始执行时，数组A1n是按关键字非递减有序排列时，下列答案中，哪一个最好的描述了最好情况下的程序排序的时间复杂度？（）A.O(nlog2n)B.O(n)C.O(log2n)D.O(n2)E.O(2n)10.对下列四个序列用快速排序方法进行排序，以序列的第一个元素为划分的基准，在第一趟划分过程中，元素的移动数最多的是哪一个序列（）A.70,65,34,82,53,25,90B.82,53,25,70,65,34,90C.34,25,53,65,90,82,70D.53,25,65,7

5、0,34,90,82E.65,34,82,70,25,53,9011.在计算机运行时，把程序和数据一样存放在内存中，这是1946年由_所领导的研究小组正式提出并论证的。（）A.图灵B.冯诺依曼C.布尔D.赫夫曼E.哈希12.下面关于计算机的说法正确的是（）A.微机内存容量的基本计量单位是字节B.二进制数中右起第10位上的1相当于210C.CPU每执行一个指令，就完成一步基本运算或判断D.1T=1024MBE.32位的计算机中的“32”指的是字长13.为什么说PASCAL是“高级语言”，是因为它（）A.必须在性能较高的机器上运行B.必须经过良好培训的高水平的程序员使用C.离机器的硬件较远D.开发

6、的时间较长E.程序的性能较好14.以下数据结构中，哪一个是线性结构？（）A广义表B.二叉树C.稀疏矩阵D.串E.队列15.在下面关于计算机系统硬件的说法中不正确的是(A.没有外部设备的计算机称为祼机B.当关闭计算机电源后，RAM中的程序和数据就消失了C.软盘和硬盘上的数据均可由CPU直接存取D.软盘和硬盘驱动器既属于输入设备又属于输出设备E.CPU主要由运算器、控制器和寄存器组成16.下面关于算法的正确说法是（）A.算法必须有输出B.算法必须在计算机上用某种语言实现C.算法不一定有输入D.算法必须在有限步执行后能结束E.算法是程序的灵魂17.以下关于结构化程序的说法中，正确的是（）A.结构化程

7、序是由单入口，单出口和循环三种结构组成B.结构化程序是出顺序、单入中和单出口三种结构组成C.结构化程序是由顺序、循环和GOTO语句结构组成D.结构化程序是由顺序、循环和分支三种结构组成E.“自顶向下，逐步求精”是结构化程序设计方法的特点18.栈S最多能容纳4个元素。现有6个元素按1，2，3，4，5，6的顺序进栈，问下列哪一个序列是可能的出栈序列？（）A.5，4，3，2，1，6B.3,2,5,4,1,6C.2,3,5,6,1,4D.1,4,6,5,2,3E.4，5，3，6，2，119.下列排序算法中，哪些排序是不稳定的（）A快速排序B.基数排序C.希尔排序D.冒泡排序E.选择排序20.下列说法正

8、确的是（）A.解释程序是接受参数，按照某一样板产生机器语言的计算机程序B.BASIC语言程序通常需解释执行C.连接程序可以把经编译程序产生的目标程序变成可执行的机器语言程序D.就执行速度而言，编译程序比解释程序快E.PASCAL通常是先编译后执行二、问题求解题（每题5分，共计10分）1.由四个结点可以构造多少种不同的二叉树.2.下图是一个设想有11项活动的活动网。其中有9个事件V1，V2，V9,每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。V1表示整个工程的开始，V9表示结束，与每个活动相联系的数ax(x=111)是执行该活动所需的时间（单位：天）。问完成整项工程至少需要天，影响

9、工程进度的关键活动有哪些：。V2V7V1V5V9V3V8V4V6三、程序阅读理解题（每题8分，共计32分）1programex11_8;varn,i,j,k,p:longint;beginwrite(N=12);i:=2;j:=0;k:=1;repeatinc(i);p:=j+k;j:=k;k:=p;untili=12;writeln(F(,12,)=,p);end.运行结果为：2programexample;varn:byte;a:array1.100oflongint;functionf(n:byte):longint;vari:longint;beginifan-10theni:=an-

10、1elsei:=f(n-1);ifan-20theni:=i+an-2elsei:=i+f(n-2);an:=i;f:=i;end;beginfillchar(a,sizeof(a),0);a1:=1;a2:=1;writeln(F(,8,)=,f(8);end.运行结果为:3programexample3begina1:=1;t:=0;fori:=2to6dobegins:=0;forj:=1toi-1dos:=s+aj;ai:=s+1;end;fori:=1to6dot:=t+ai;writeln(t=,t);end.运行结果为：4programexample4vari,s,max:int

11、eger;beginfori:=1to10doread(ai);max:=a1;s:=a1;fori:=2to10dobeginifsmaxthenmax:=s;end;writeln(max=,max);end.输入：89124651115289运行结果为：四、程序完善题(每题14分，共计28分n方阵的每行每列都是自然数1.n的一个全排列，每行（列）无重复数字。例：n5时，1432553214421533154225431输入n（2）和第一行数字（不检查错误）输出一个满足要求的方阵因为只是要求每行（列）无重复数字，对第一行的每个数字，都四十五度斜向下写，写到行尽头就从行开头开始。这样就不会重

12、复。对于经过第y行，第x列的直线，斜率k=1设：y=x+b代入坐标，得出：b=y-x令y=1，取首行的数：x=y-bx从1开始，到n,如果x为0或负数，则x=x+n，取出第一行的数。程序只用一维数组，存第一行的数字。programexample2;constmaxn=10000;vara:array1.maxnofinteger;x,y,n:integer;functionf(x,y:integer):integer;varb:integer;begin(1)(2)ifx=0then(3)f:=ax;end;beginwrite(Entern:);readln(n);if(nmaxn)then

13、exit;write(Enterfirstline:);forx:=1tondoread(ax);writeln(Output:);forx:=1tondowrite(ax:4);writeln;fory:=2tondobeginforx:=1tondowrite(4):4);writeln;end;end.2程序说明设有个人依次围成一圈，从第个人开始报数，数到第个人出列，然后从出列的下一个人开始报数，数到第个人又出列，如此反复到所有的人全部出列为止。设个人的编号分别为1，2，n，打印出出列的顺序。本题用数组建立标志位等方法求解,用数组实现链式结构。数组ai作为指针变量来使用，ai存放下一个结

14、点的位置。设立指针j指向当前结点，则移动结点过程为j:=aj，当数到m时，m结点出链，则aj:=aaj。程序programexample;constn=14;m=4;vara:array1.nofinteger;i,j,k,p:integer;beginfori:=1ton-1doai:=i+1;an:=1;(1);k:=1;p:=0;repeat(2);k:=k+1;ifk=mthenbeginwrite(aj:4);p:=p+1;(3);(4);enduntilp=n;end.参考答案一、选择题：（每题分，共计30分。每题有5个选项，前10题为单选题，后10题为不定项选择题，全部选对才得分

15、）。题号12345678910答案BCBDAAEDBE题号11121314151617181920答案BACECDEACABCDEDEBEACBCDE二、问题求解题（每题5分，共计10分）1、142、19,（2分）a1,a4,a7,a10（3分）三、程序阅读理解题（每题8分，共计32分）1、F（12）=892、F（8）=213、t=634、max=77四、程序完善题(每题14分，共计28分)1、b:=y-x;x:=1-b;x:=x+n;f(x,y)2、j:=n;j:=aj;aj:=aaj;k:=1;grundfos 发表于 2004-10-18 10:16:57 全文 评论 引用 推荐 档案

16、推给好友 2004-10-18信息学竞赛普及组初赛模拟试题(四)信息学竞赛普及组初赛模拟试题(四)一、选择题：（选出每题正确的答案代码，填在括号里，110题为单选题，每小题只有一个正确答案，1120题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题，共30分）1、二进制数01100100转换成十六进制数是（）。A32B64C128D100E2562、操作系统是一类重要的系统软件，下面几个软件中，不属于系统软件的是（）。AJavaBMS-DOSCLinuxDWindows2000EUnix3、计算机病毒的传染是以计算机运行和（）为基础的，没有这两个条件，病毒是不会传染的。A编辑文

17、稿B读写磁盘C编程序D扫描图画E打印4、因特网不属于任何个人，也不属于任何组织。其中在网络知识这一块中有一个英文简写ISP，它的中文意思是（）。A因特网连接B因特网使用C因特网设计D因特网服务提供者E信息传输5、Internet给我们提供了资源共享、浏览、检索信息和远程登录等多种服务，下面几个选项中用于远程登录的是（）。AWWWBTCP/IPCTelnetDE-mailEFTP6、IE是目前流行的浏览器软件，它的工作基础是解释执行用（）语言书写的文件。AVCBHTMLCBASICDHTTPEVB7、给出3种排序：插入排序、冒泡排序、选择排序。这3种排序的时间代价分别是（）。AO(n)、O(n2

18、)、O(logn)BO(logn)、O(n)、O(n2)CO(n2)、O(n)、O(logn)DO(n2)、O(n)、O(n)EO(n2)、O(n2)、O(n2)8、一棵完全二叉树的结点总数为18，其叶结点数为（）。A7个B8个C9个D10个E11个9、在流程图的符号中，菱形框一般作为（）。A起始框B判断框C输入输出框D处理工作框E结速框10、在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主要将要输出打印的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个（）结构。A堆栈B数组C线性表D队列E链表11、多媒体技术中的“多媒体”的含义主要是指如（）等

19、多种表达信息的形式。A磁盘B音箱C显示器D声音E图像12、下面有关计算机知识说明，正确的是（）。A在WINDOWS98操作系统下，删除磁盘中的文件时都先存放在回收站中BFOXMAIL是用于收发电子邮件的工具C文件夹组织是一个有层次的树状结构，其中最顶层的是桌面D存储器具有记忆能力，其中的信息任何时候都不会丢失E为了提高软件的测试效率，应该选择发现错误的可能性大的测试数据13、对按关键字排序好的线性表进行二分查找，该线性表适合的存储结构为（）。A链接存储B索引存储C散列存储D顺序存储E循环存取14、一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的输出序列的是（）。A54312B2413

20、5C21543D12534E1234515、评价一个算法的好坏有多种指标，下列是算法评价指标的是（）。A正确性B运行时间C占用空间D迭代次数E简单性16、下面描述用多维数组表示的数据结构的语句中，正确的是（）。A多维数组存放的都是同一种类型的数据B多维数组各维的下标范围必须一样C多维数组在内存中的地址是连续的D多维数组中的下标不能是表达式E多维数组是随机存取的数据结构17、若已知一个栈的入栈顺序1，2，3，n，其输出序列为P1，P2，P3，Pn（它是输入序列的一个排列），则在输出序列中可能出现的情况是（）。APjPkPi，其中ijkBPkPjPi，其中ijkCPjPiPk，其中ijkDPiPk

21、Pj，其中ij=n;writeln(a);end.输入：415377输出：programtest4;varm,n,i,p,k：integer;r:array1200ofinteger;b:Boolean;beginm:=6;n:=2;forI:=1tom-1dori:=i+1;rm:=1;i:=0;p:=1;b:=true;whilebdobegini:=i+1;k:=p;p:=rp;ifk=pthenbeginwriteln(p);b:=falseendelseifi=n+1thenbeginwrite(p,);i:=0;p:=rp;rk:=p;endendend.输出：四、完善程序（共2题

22、，每题14分，共28分）第1题（7分）【问题描述】设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为XK，今从n种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于XK，而价值的和为最大。【程序清单】Programpackage;constmaxxk=400;maxn=20;typetlist=array1maxnofbyte;tmake=array0maxn,0maxxkofinteger;varn,xk:integer;w,u:tlist;f:tmake;procedureinit;vari:byte;beginfillchar

23、(w,sizeof(w),0);fillchar(u,sizeof(u),0);readln(n,xk);fori:=1tondo;end;proceduremake;vari,j:byte;beginfori:=1tondobeginforj:=1towi-1dofi,j:=fi-1,j;forj:=witoxkdoiffi-1,jfi,j-wi+uithen;else;end;end;procedureprint;varget:tlist;i,j:byte;beginfillchar(get,sizeof(get),0);i:=;j:=;whilei0doiffi,j=fi-1,jthen

24、dec(i)elsebegindec(j,wi);end;writeln(n=,n,xk=,xk);writeln(maxworth=,;fori:=1tondowriteln(no.,i,weight:,wi:2,worth:,ui:2,get,geti:2);end;begininit;make;print;end.第2题（7分）【问题描述】给定一个01串，请你找出长度介于a,b之间，重复出现次数最多的01串。输入：a,b(0a=b=12)由0，1组合的数列，由.结尾。输出：要求的串。提示：本程序中将01序列转换为2进制数存取。【程序清单】programshuchuan;vari,j,s,

25、k,a,b,max:integer;m:array18192ofinteger;two,v:array120ofinteger;c:char;beginfori:=1to13do;readln(a,b);read(c);s:=1;k:=1;whilec.dobegins:=sshl1+ord(c)-48;ifthens:=(s-twob+1)modtwob)+twob;inc(ms);ifk0thenforj:=atob-1dom(imodtwoj)+twoj:=;max:=0;fori:=twoatotwob+1doifmimaxthen;fori:=twoatotwob+1doifmi=m

26、axthenbeginj:=0;k:=I;repeatinc(j);vj:=kmod2;until;whilej0dobeginwrite(vj);dec(j)end;writeln;end;end.信息学命题(四)参考答案一、选择题：（选出每题正确的答案代码，填在括号里，110题为单选题，每小题只有一个正确答案，1120题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题，共30分）题号12345678910答案BABDCBECBD题号11121314151617181920答案DEBCEDCEABCEACEBCDAEACDEA二、问题解答：（共2题，每题5分，共10分）第1题

27、：7第2题：61三、写出程序的运行结果：（共4题，每题8分，共32分）第1题：25第2题：s=18第3题：911第4题：421365四、完善程序（共2题，每题14分，共28分）第1题：read(wi,ui)fi,j:=fi-1,jfi,j:=fi,j-wi+uii:=nj:=xkinc(geti)fn,xk第2题：twoi:=1shli；s=twob+1(或kb)inc（m(smodtwoi)+twoi）m(imodtwoj)+twoj+mimax:=mik:=kdiv2k=1信息学竞赛普及组初赛模拟试题(三)一、选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题分，多选无分，共3

28、0分）1、MAN英文缩写的含义是（）A.局域网B.城域网C.广域网D.增值网2、小张用十六进制，八进制和十进制写了如下一个等式：6413=33式中三个数是各不相同进位制的数，试问64，13，33，分别为_。A八进制，十进制，十六进制B十进制，十六进制，八进制C八进制，十六进制，十进制D十进制，八进制，十六进制3、表达式(4MOD(3)与(4MOD3)的值为：_。A1，1B1，1C1，1D1，14、试指出：下列if语句中，当x=80时,运行的结果为_。beginy:=0;readln(x);ifx0theny:=5elseifx10thenbeginy:=10;ifx100theny:=100;

29、endelsey:=200;write(y=,y);end.Ay=9By=200Cy=10Dy=1005、设栈S的初始状态为空，现有5个元素组成的序列1，2，3，4，5，对该序列在S栈上依次进行如下操作(从序列中的1开始，出栈后不再进栈)：进栈，进栈，进栈，出栈，进栈，出栈，进栈，试问出栈的元素序列是_。A5，4，3，2，1B2，1C2，3D3，46、ASCII码是（）。A国标码B二进制编码C十进制编码D美国标准信息交换码7、一台计算机的字长是4个字节，这意味着（）。A能处理的数值最大为4位十进制数9999B能处理的字符串最多由4个英文字母组成C在CPU中能够同时处理32位二进制数据D在CPU

30、中运算的最大结果为2的32次方8、假设一台计算机的地址总线为16，那么中央处理器CPU能访问的最大存储器容量为(A2*16KBB16KBC216BD16*1024*8B9、计算机最终处理的信息形式是（）AASCII码BBCD码C二进制D十六进制10、与十六进制数6F等值的八进制数是（）A166B139C157D18311、以下属非法用户自定义标识符的是()。AdateBdirClistDtype12、设X和Y是同一种枚举类型变量，则下列语句中合法的是()。AX:=ORD(Y)BX:=YCREAD(X,Y)DWRITE(T,Y)13、计算机能够直接识别和处理的程序是_程序A汇编语言B源程序C.机器语言D.高级语言14、设有说明VARA：ARRAYAE