信息学竞赛普及组初赛模拟试题

信息学竞赛普及组初赛模拟试题（五）一、选择题：（每题1.5分，共计30分。每题有5个选项，前10题为单选题，后10题为不定项选择题，全部选对才得分）。1.二进制数11011011的十进制值是（）202B.219C.193D.209我国研制的银河III型的超级计算机通过基准程序的测试，其峰值速度是（）80亿次B.100亿次C.130亿次D.150亿次程序段如下：FORI:=1TO5DOFORJ:=2TOIDOWriteln（‘*'）输出'*'的个数是（）A.5B.10C.15D.25E.30设待排序的记录为（49，38，65，97，76，13，27,49,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.希尔排序设无向树T有7片树叶，其余顶点度均为3,则T中3度顶点有多少个（）A.5B.7C.9D.4E.8设连通图G的顶点数和边数与一立方体相同，即有8个顶点和12条边。任意一棵G的生成树的总边数为（）A．7 B.8C.9D.10E.11设有两个散列函数h1（k）=kmod13和h2（k）=kmod11+1，散列表为T[0„12]，用二次散列法解决冲突。函数hl用来计算散列地址，当发生冲突时，h2作为计算下一个探测地址的地址增量。假定某一时刻散列表的状态为：0123456789101112804435804435下一个被插入的关键码为57，其插入的位置为(。A.4 B.5 C.6D.7E.8请根据下面是一段PASCAL程序,判断第8、9题。forh:=1ton-1dobeginx:=A[h+1];k:=h;while(k>=1)and(A[k]>x)dobeginA[k+1]:=A[k];k:=k-1endA[k+1]:=xend8•假设在程序开始执行时，数组A[l„n]是一组随机整数。下列答案中，哪一个最好的描述了最差情况下的程序排序的时间复杂度？()A.O(nlog2n)B.0(n)C.O(log2n)D.0(n2)E.0(2n)9•假设在程序开始执行时，数组A[1„n]是按关键字非递减有序排列时，下列答案中，哪一个最好的描述了最好情况下的程序排序的时间复杂度？()A.O(nlog2n)B.O(n)C.O(log2n)D.O(n2)E.O(2n)对下列四个序列用快速排序方法进行排序，以序列的第一个元素为划分的基准，在第一趟划分过程中，元素的移动数最多的是哪一个序列()70,65,34,82,53,25,9082,53,25,70,65,34,9034,25,53,65,90,82,7053,25,65,70,34,90,8265,34,82,70,25,53,90在计算机运行时，把程序和数据一样存放在内存中，这是1946年由 所领导的研究小组正式提出并论证的。()图灵冯•诺依曼C.布尔D.赫夫曼E.哈希下面关于计算机的说法正确的是（）微机内存容量的基本计量单位是字节B.二进制数中右起第10位上的1相当于210CPU每执行一个指令，就完成一步基本运算或判断D.1T=1024MBE.32位的计算机中的“32”指的是字长为什么说PASCAL是“高级语言”，是因为它（）必须在性能较高的机器上运行必须经过良好培训的高水平的程序员使用离机器的硬件较远开发的时间较长程序的性能较好以下数据结构中，哪一个是线性结构？（）E.队列广义表 B.二叉树C.稀疏矩阵 D.E.队列在下面关于计算机系统硬件的说法中不正确的是（口没有外部设备的计算机称为祼机当关闭计算机电源后，RAM中的程序和数据就消失了软盘和硬盘上的数据均可由CPU直接存取软盘和硬盘驱动器既属于输入设备又属于输出设备CPU主要由运算器、控制器和寄存器组成下面关于算法的正确说法是（）算法必须有输出算法必须在计算机上用某种语言实现算法不一定有输入算法必须在有限步执行后能结束算法是程序的灵魂以下关于结构化程序的说法中，正确的是（）A.结构化程序是由单入口，单出口和循环三种结构组成结构化程序是出顺序、单入中和单出口三种结构组成结构化程序是由顺序、循环和GOTO语句结构组成结构化程序是由顺序、循环和分支三种结构组成“自顶向下，逐步求精”是结构化程序设计方法的特点18.栈S最多能容纳4个元素。现有6个元素按1，2，3，4，5，6的顺序进栈，问下列哪一个序列是可能的出栈序列？（）A.5，4，3，2，1，63,2,5,4,1,62,3,5,6,1,41,4,6,5,2,3E.4，5，3，6，2，1下列排序算法中，哪些排序是不稳定的（）A.快速排序 B.基数排序 C.希尔排序D.冒泡排序E.选择排序下列说法正确的是（）解释程序是接受参数，按照某一样板产生机器语言的计算机程序BASIC语言程序通常需解释执行连接程序可以把经编译程序产生的目标程序变成可执行的机器语言程序就执行速度而言，编译程序比解释程序快PASCAL通常是先编译后执行二、问题求解题（每题5分，共计10分）由四个结点可以构造多少种不同的二叉树.下图是一个设想有11项活动的活动网。其中有9个事件VI,V2,…V9,每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。V1表示整个工程的开始，V9表示结束，与每个活动相联系的数ax（x=l„ll）是执行该活动所需的时间（单位：天）。问完成整项工程至少需要天,影响工程进度的关键活动有哪些： 。V2V7V1V5V9V3V8V6V4V6三、程序阅读理解题（每题8分，共计32分）1．programex11_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.运行结果为：2．programexample;varn:byte;a:array[1..100]oflongint;functionf(n:byte):longint;vari:longint;beginifa[n-1]>0theni:=a[n-1]elsei:=f(n-1);ifa[n-2]>0theni:=i+a[n-2]elsei:=i+f(n-2);a[n]:=i;f:=i;end;beginfillchar(a,sizeof(a),0);a[1]:=1;a[2]:=1;writeln('F(',8,')=',f(8));end.运行结果为:3．programexample3begina[1]:=1;t:=0;fori:=2to6dobegins:=0;forj:=1toi-1dos:=s+a[j];a[i]:=s+1;end;fori:=1to6dot:=t+a[i];writeln(‘t=',t);end.运行结果为：4．programexample4vari,s,max:integer;beginfori:=1to10doread(a[i]);max:=a[1];s:=a[1];fori:=2to10dobeginifs<0thens:=0;s:=s+a[i];ifs>maxthenmax:=s;end;writeln（‘max=',max）;end.输入：89-124651115-289运行结果为：四、程序完善题（每题14分，共计28分）nXn方阵的每行每列都是自然数l..n的一个全排列，每行（列）无重复数字。例：n=5时，1432553214421533154225431输入n（＞=2）和第一行数字（不检查错误）输出一个满足要求的方阵因为只是要求每行（列）无重复数字，对第一行的每个数字，都四十五度斜向下写，写到行尽头就从行开头开始。这样就不会重复。对于经过第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:array[1..maxn]ofinteger;x,y,n:integer;functionf（x,y:integer）:integer;varb:integer;begin(1)(2)ifx<=0then(3)f:=a[x];end;beginwrite('Entern:');readln(n);if(n<2)or(n>maxn)thenexit;write('Enterfirstline:');forx:=1tondoread(a[x]);writeln('Output:');forx:=1tondowrite(a[x]:4);writeln;fory:=2tondobeginforx:=1tondowrite((4):4);writeln;end;end.[程序说明]设有n个人依次围成一圈，从第1个人开始报数，数到第m个人出列，然后从出列的下一个人开始报数，数到第m个人又出列，…，如此反复到所有的人全部出列为止。设n个人的编号分别为1,2，„，n，打印出出列的顺序。本题用数组建立标志位等方法求解，用数组实现链式结构。数组a[i]作为"指针"变量来使用，a[i]存放下一个结点的位置。设立指针j指向当前结点，则移动结点过程为j:=a[j]，当数到m时，m结点出链，则a[j]:=a[a[j]]。[程序]programexample;constn=14;m=4;vara:array[1..n]ofinteger;i,j,k,p:integer;beginfori:=1ton-1doa[i]:=i+1;a[n]:=1;;k:=1;p:=0;repeat;k:=k+1;ifk=mthenbeginwrite(a[j]:4);p:=p+1;;;enduntilp=n;end.参考答案一、选择题：(每题1.5分，共计30分。每题有5个选项，前10题为单选题后10题为不定项选择题，全部选对才得分)。题号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)j:=n;j:=a[j];a[j]:=a[a[j]];k:=1;grundfos发表于＞2004-10-1810:16:5^Z1［全文］［评论］［引用］［推荐］［档案］［推给好友］2004-10-18信息学竞赛普及组初赛模拟试题（四）信息学竞赛普及组初赛模拟试题（四）一、选择题：（选出每题正确的答案代码，填在括号里，1—10题为单选题，每小题只有一个正确答案，11—20题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题1.5，共30分）1、二进制数01100100转换成十六进制数是（）。A．32B．64C．128D．100E．2562、 操作系统是一类重要的系统软件，下面几个软件中，不属于系统软件的是（）。A．JavaB．MS-DOSC．LinuxD．Windows2000E．Unix3、 计算机病毒的传染是以计算机运行和（）为基础的，没有这两个条件，病毒是不会传染的。编辑文稿B.读写磁盘C.编程序D.扫描图画E.打印4、因特网不属于任何个人，也不属于任何组织。其中在网络知识这一块中有一个英文简写ISP，它的中文意思是()。因特网连接B.因特网使用C.因特网设计D.因特网服务提供者E.信息传输5、 Internet给我们提供了资源共享、浏览、检索信息和远程登录等多种服务，下面几个选项中用于远程登录的是()。WWWB.TCP/IPC.TelnetD.E-mailE.FTP6、IE是目前流行的浏览器软件，它的工作基础是解释执行用()语言书写的文件。A.VCB.HTMLC.BASICD.HTTPE.VB7、 给出3种排序：插入排序、冒泡排序、选择排序。这3种排序的时间代价分别是()。A.O(n)、O(n2)、O(logn)B.O(logn)、O(n)、O(n2)C.O(n2)、O(n)、O(logn)D.O(n2)、O(n)、O(n)E.O(n2)、O(n2)、O(n2)8、一棵完全二叉树的结点总数为18，其叶结点数为( )。A.7个B.8个C.9个D.10个E.11个9、 在流程图的符号中，菱形框一般作为()。起始框B.判断框C.输入输出框D.处理工作框E.结速框10、 在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主要将要输出打印的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个()结构。A.堆栈B.数组C.线性表D.队列E.链表11、多媒体技术中的“多媒体”的含义主要是指如( )等多种表达信息的形式。A.磁盘B.音箱C.显示器D.声音E.图像12、 下面有关计算机知识说明，正确的是()。A.在WINDOWS98操作系统下，删除磁盘中的文件时都先存放在回收站中B．FOXMAIL是用于收发电子邮件的工具C．文件夹组织是一个有层次的树状结构，其中最顶层的是桌面D.存储器具有记忆能力，其中的信息任何时候都不会丢失E．为了提高软件的测试效率，应该选择发现错误的可能性大的测试数据13、 对按关键字排序好的线性表进行二分查找，该线性表适合的存储结构为（）。A.链接存储 B.索引存储 C.散列存储 D.顺序存储 E.循环存取14、 一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的输出序列的是（）。A．54312B．24135C．21543D．12534E．1234515、 评价一个算法的好坏有多种指标，下列是算法评价指标的是（）。A.正确性B.运行时间 C.占用空间D.迭代次数E.简单性16、 下面描述用多维数组表示的数据结构的语句中，正确的是（）。多维数组存放的都是同一种类型的数据多维数组各维的下标范围必须一样多维数组在内存中的地址是连续的多维数组中的下标不能是表达式多维数组是随机存取的数据结构17、 若已知一个栈的入栈顺序1,2,3,…，n其输出序列为Pl,P2,P3,…,Pn（它是输入序列的一个排列），则在输出序列中可能出现的情况是（）。PjvPkvPi，其中ivjvkPk<Pj<Pi，其中ivjvkPjvPivPk，其中ivjvkPivPkvPj,其中ivjvk以上都不可能出现18、线性表具有如下的结构特点：（ ）A.均匀性B.单一性C.简单性D.无序性E.有序性19、 下列关于数据结构的叙述中正确的是（）。A.数据结构是带有结构的数据元素的集合线性表的线性存储结构优于链式存储结构队列是限定仅在一端进行插入，在另一端进行删除的线性表二维数组是其数据元素为线性表的线性表图是一种非线性数据结构20、任意一棵树均可惟一地转换成与它对应的二叉树。由树转换成的二叉树中，顶点N的左右子女分别是N在原树里对应顶点的（）。最左子顶点/最邻近的右兄弟最右子顶点/最右的兄弟最邻近的右兄弟/最左的兄弟最邻近的左兄弟/最邻近的右兄弟最邻近的右兄弟/最右的兄弟二、 问题解答：（共2题，每题5分，共10分）1、 光明中学开设数学、英语和信息学三个兴趣学习小组，其中数学小组30人，英语小组15人，信息学小组18人，参加三个小组总人数为50人，其中有3人同时参加3个小组，那么同时只参加两个小组的同学有多少人？2、 给出一组顶点（顶点值用A,B,C,D,E,F表示），其对应权值分别为2,3、 1,7,8,4。请以A,B,C,D,E,F为叶子顶点构造一棵哈夫曼树，并求出它的最小带权路径长度WPL的值。三、 写出程序的运行结果（共4题,每题8分,共32分）第1题：programtest1；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输出：第2题：programtest2(input,output);vari,j,k,s:integer;begins:=0fori:=3downto1dobeginforj:=1to3dobegink:=0;repeatk:=k+1;s:=s+k;untilk=j;end;s:=s-(k+1);end;write(‘s=',s);end.输出：第3题：programtest3;vara,b,n:longint;beginreadln(n);a:=0;b:=0;repeata:=a+1;b:=b+a;untilb>=n;writeln(a);end.输入：415377输出：programtest4;varm,n,i,p,k：integer;r:array[1„200]ofinteger;b:Boolean;beginm:=6;n:=2;forI:=1tom-1dor[i]:=i+1;r[m]:=1;i:=0;p:=1;b:=true;whilebdobegini:=i+1;k:=p;p:=r[p];ifk=pthenbeginwriteln(p);b:=falseendelseifi=n+1thenbeginwrite(p,‘');i:=0;p:=r[p];r[k]:=p;endend输出：四、完善程序(共2题，每题14分，共28分)第1题(7分)【问题描述】设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为XK,今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于XK,而价值的和为最大。【程序清单】Programpackage;constmaxxk=400;maxn=20;typetlist=array[1„maxn]ofbyte;tmake=array[0„maxn,0„maxxk]ofinteger;varn,xk:integer;w,u:tlist;f:tmake;procedureinit;vari:byte;beginfillchar(w,sizeof(w),0);fillchar(u,sizeof(u),0);readln(n,xk);fori:=1tondo①;end;proceduremake;vari,j:byte;beginfori:=1tondobeginforj:=1tow[i]-1dof[i,j]:=f[i-1,j];forj:=w[i]toxkdoiff[i-1,j]>f[i,j-w[i]]+u[i]then②;else③;end;end;procedureprint;varget:tlist;i,j:byte;beginfillchar(get,sizeof(get),0);i:=④;j:=⑤;whilei>0doiff[i,j]=f[i-1,j]thendec(i)elsebegindec(j,w[i]);⑥;end;writeln(‘n=',n,‘,',‘xk=',xk);writeln(‘maxworth=', ⑦口fori:=1tondowriteln(‘no.',i‘,weight:',w[i]:2,‘worth:',u[i]:2,‘get',get[i]:2);end;begininit;make;print;第2题(7分)【问题描述】给定一个01串，请你找出长度介于a,b之间，重复出现次数最多的01串。输入：a,b(0vav=bv=12)由0，1组合的数列，由‘.'结尾。输出：要求的串。提示：本程序中将01序列转换为2进制数存取。【程序清单】programshuchuan;vari,j,s,k,a,b,max:integer;m:array[1„8192]ofinteger;two,v:array[1„20]ofinteger;c:char;beginfori:=1to13do①;readln(a,b);read(c);s:=1;k:=1;whilec<>‘.'dobegins:=sshl1+ord(c)-48;if②thens:=((s-two[b+1])modtwo[b])+two[b];inc(m[s]);ifk<bthenfori:=atok-1do③;inc(k);read(c);end;fori:=two[b]totwo[b+1]doifm[i]>0thenforj:=atob-1dom[(imodtwo[j])+two[j]]:=④;max:=0;fori:=two[a]totwo[b+1]doifm[i]>maxthen ⑤;fori:=two[a]totwo[b+1]doifm[i]=maxthenbeginj:=0;k:=I;repeatinc(j);v[j]:=kmod2;⑥;until⑦;whilej>0dobeginwrite(v[j]);dec(j)end;writeln;end;end.信息学命题(四)参考答案一、选择题：(选出每题正确的答案代码，填在括号里，1—10题为单选题，每小题只有一个正确答案，11—20题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题1.5，共30分)题号12345678910答案BABDCBECBD题号11121314151617181920答案DEBCEDCEABCEACEBCDAEACDEA二、问题解答：(共2题，每题5分，共10分)第1题：第2题：61三、写出程序的运行结果：(共4题，每题8分，共32分)第1题：25第2题：s=18第3题：911第4题：421365四、完善程序(共2题，每题14分，共28分)第1题：read(w[i],u[i])f[i,j]:=f[i-l,j]f[i,j]:=f[i,j-w[i]]+u[i]i:=nj:=xkinc(get[i])f[n,xk]第2题：two[i]:=1shli；s>=two[b+1](或k>b)inc(m[(smodtwo[i])+two[i]])m[(imodtwo[j])+two[j]]+m[i]max:=m[i]k:=kdiv2k=1信息学竞赛普及组初赛模拟试题（三）一、选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）1、MAN英文缩写的含义是（）A.局域网B.城域网C.广域网D.增值网2、 小张用十六进制，八进制和十进制写了如下一个等式：64－13=33TOC\o"1-5"\h\z式中三个数是各不相同进位制的数，试问64，13，33，分别为 。八进制，十进制，十六进制B.十进制，十六进制，八进制C.八进制，十六进制，十进制D.十进制，八进制，十六进制3、表达式（4MOD（－3））与（－4MOD3）的值为： 。A.－1，－1 B.1，－1C.－1，1 D.1，14、试指出：下列if语句中，当x=80时,运行的结果为 。beginy:=0;readln（x）;ifx<0theny:=5elseifx<10thenbeginy:=10;ifx<100theny:=100;endelsey:=200;write（'y=',y）;end.A.y=9 B.y=200 C.y=10 D.y=1005、 设栈S的初始状态为空，现有5个元素组成的序列｛1，2,3,4,5｝，对该序列在S栈上依次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈，进栈，进栈，出栈，进栈，出栈，进栈，试问出栈的元素序列是A．{5，4，3，2，1}B．{2，1}C．{2，3}D．{3，4}6、ASCII码是()。A.国标码B.二进制编码C.十进制编码D.美国标准信息交换码7、一台计算机的字长是4个字节，这意味着()。A.能处理的数值最大为4位十进制数9999B.能处理的字符串最多由4个英文字母组成在CPU中能够同时处理32位二进制数据在CPU中运算的最大结果为2的32次方8、 假设一台计算机的地址总线为16,那么中央处理器CPU能访问的最大存储器容量为(口A.2*16KBB.16KBC.216BD.16*1024*8B9、 计算机最终处理的信息形式是()A.ASCII码B.BCD码C.二进制D.十六进制10、 与十六进制数6F等值的八进制数是()A.166B.139C.157D.18311、 以下属非法用户自定义标识符的是()。A.date B.dirC.listD.type12、 设X和Y是同一种枚举类型变量，则下列语句中合法的是()。A.X:=ORD(Y) B.X:=YC.READ(X,Y)D.WRITE(T,Y)13、计算机能够直接识别和处理的程序是 程序A.汇编语言B.源程序 C.机器语言D.高级语言14、 设有说明VARA：ARRAY['A'..'E'，1..4，BOOLEAN]OFREA1；则A['A',3]是(匚I。一个实型的数组元素一个数组，该数组具有两个实型数组元素一个数组，该数组具有4*2个实型数组元素一个数组，该数组具有5*4*2个实型数组元素15、下列属于线性时间的排序算法是：（）A.快速排序 B.桶排序C.冒泡排序16、一棵包含n个节点的树有几条边：A.n B.n-1C.不一定TOC\o"1-5"\h\z17、 在Pascal语言中，表达式35div3mod4的值是 。A.O B.2 C.3 D.618、 在数据结构中，"树"结构下层结点出现三个以上的结点，这种结构称为A.三层树B.三叉树C.多层树D.多叉树19、在Pascal语言中，下列程序段所计算的公式是 。程序段：S：=0；T：=1；ForI：=1to10doBeginT：=T*I；S：=S+T；end;S=1+2+3+4+„„+10S=1*2*3*4*„„*10S=1！+2！+3！+4！+„„+10！S=1+2*3+3*4+4*5+„„+10*1120、 以下说法正确的是（）。A.CPU与内存不交换信息B.CPU与内存直接交换信息C.CPU与内存间接不交换信息D.CPU与内存部分交换信息二、阅读下列程序，写出程序运行结果（第1题5分，第2，3，4题各6分，共23分）programexp1;constn=5;varI,j,k:integer;r:array[0..10]ofinteger;beginforI:=1tondoread(r[I]);forI:=2tondobegink:=r[I];j:=I-1;while(k>r[j])and(j>0)dobeginr[j+1]:=r[j];j:=j-1;end;r[j+1]:=k;end;forI:=1tondowrite(r[I],'');writelnend.键盘输入:84935屏幕输出：programexp2;vara,b,f:integer;functiongd(m,n:integer):integer;beginifn=0thengd:=melsegd:=gd(n,mmodn);end;beginreadln(a,b);write(‘(‘,a,',',b,')=');f:=gd(a,b);writeln(f)end.键盘输入:17216屏幕输出：3、Programexp3(input,output);VARI,J,S:INTEGER;B:ARRAY[0..5]OFINTEGER;BEGINS:=1;FORI:=1TO5DOB[I]:=I;J:=1;WHILEJ>0DOBEGINJ:=5;WHILE(J>0)AND(B[J]=10+J-5)DOJ:=J-1;IFJ>0THENBEGINS:=S+1;B[J]:=B[J]+1;FORi:=J+1TO5DOB[i]:=B[J]+i-JEND;END;WRITELN('S=',S);END.4、programexp4(input,output);varm,n,g:integer;functiongcd(m,n:integer):integer;beginifn=0thengcd:=melsegcd:=gcd(n,mmodn)end;beginread(m,n);g:=gcd(m,n);writeln('m=',m,'n=',n,'gcd=',g)end.输入：489输出：三、问题解答（第1题每空4分，第2题8分）1、数据结构中，下面是一个树结构图，这个树的"先序遍历"结果是 中序遍历结果是： 。248+3*4107-*/@2、给出一个后缀算术表达式为写出对应的中缀算术表达式： 四、完善程序（第一题每空3分，第二题每空2分，第三题每空4分，共32分）1、连续整数平台问题已知一个含有多个整数的数组，其中相同的元素集中在一起形成一个平台。以下程序用于对输入的数组求出其中最大平台长度。例如，中元素个数为20，它们依次为22223333311111111144则它的最大平台长度为9。constmaxlength=100;vara:array[1..maxlength]ofinteger;i,maxi,n,s,t:integer;beginwrite('n=');readln(n);fori:=1tondoread(a[i]);readln;maxi:=0;t:=[1]s:=1;fori:=2tondoifa[i]=tthen[2]elsebeginifs>maxithenmaxi:=s;t:=a[i];[3]end;[4]writeln('maxi=',maxi);end.2、1000！尾0问题以下程序用于统计1000！末尾有多少个0。其中1000！=1´2´3´…´1000。实际上我们只要统计1000!有多少个因子10。由于10=5´2，因而只需统计有多少个因子5和2。显然在1〜1000的所有数中，5的因子个数比2的因子个数少。因此，只要统计1〜1000的所有数中共有多少个因子5就行了。vari,j,n:integer;beginn:=0;fori:=1to200dobeginj:=i*5;while[5]=0dobeginn:=n+1;j:=[6]end;end;writeln(n:4);end.3、[问题描述]找数问题：以下程序用在n个不同元素中找出第k个最小元素。程序中用分治策略来设计算法。把这n个元素放在一个数组中，然后取出第k个元素为标准m,把n个元素重新排列:小于标准m的元素放在数组前面，大于该标准的放在数组的后面。把该元素m放在两者之间。设小于标准的元素个数为j-1,如果j=k,则A(k)即为所求元素。如果j>k,则第k个元素必在区间[l,j]，因此取A[l],…，A[j]为新的元素集合，然后重复上述的”部分排序”的过程。如果jvk,则第k个元素必在区间[j+1,n],因此取A[j],„,A[n]为新的元素集合，重复过程。直至j=k为止。[程序清单]varj,k,n:integer;a:array[1..100]ofinteger;proceduresearch(b,e:integer);varI,m,t:integer;beginifb=ethenbeginj:=b;exitend;I:=b;j:=e;m:=[7];RepeatWhilea[I]<mdoinc(i);Whilem<a[j]do[8];IfI<jthenBegint:=a[I];a[I]:=a[j];a[j]:=tend;UntilI>=j;IfI=kthenexit;If[9]thensearch(b,j)elsesearch(j+1,e)End;procedure[10]varI:integer;beginforI:=1tondowrite(a[I],'');writeln;writeln(‘a[‘,k,']=',a[k]);end;beginwrite(‘n=');readln(n);write(‘a[1..',n,']=');fork:=1tondoread(a[k]);readln;write(‘k=');readln(k);search([11]口pr(n);readlnend.参考答案、单项选择题（每题1分，共30分）12345678910DCBBDDCCCC11121314151617181920DBCBBBCDDB二、阅读下列程序，写出程序运行结果(第1题5分，第2，3，4题各6分，共23分）1、985431、（172，16）=43、S=2524、m=48n=9gcd=3三、问题解答(第1题每空4分，第2题8分)1、ABCDE BADCE2、(24+8)*3/4*(10-7)四、完善程序(第一题每空3分，第二题每空2分，第三题每空4分，共32分)(1)a[1](2)s:=s+1(3)s:=1(4)ifs>maxithenmaxi:=s;(5)jmod5(6)jdiv5(7)a[k](8)de(j)(9)j>k(10)pr(n:integer);(11)Ln信息学竞赛普及组初赛模拟试题(二)(pascal语言)限时2小时完成，满分100分一、选择题：(共20小题，1-15小题为单选题，每题1分；16-20小题为多选题，每题2分。共25分)1.对存储器按字节进行编址，若某存储器芯片共有10根地址线的引脚，则该存储器芯片的存储容量为(口。512B(B)1KB(C)2KB(D)4KB(E)8KB2•在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是(口。(A)堆排序 (B)希尔排序 (C)冒泡排序 (D)快速排序(E)二分排序某数列有1000个各不相同的单元，由低至高按序排列，现要对该数列进行二分法检索，在最坏的情况下，需要检索(□单元。(A)1000 (B)10 (C)100 (D)500(E)300已知数组a中，每个元素a[i,j]在存储时要占3个字节，设i从1变化到8，j从1变化到10,分配内存实是从地址sa开始连续按行存储分配的。试问：a[5,8]的起始地址为(口。(A)sa+141 (B)sa+180 (C)sa+222 (D)sa+225(E)sa+1555•在pascal语言过程调用时，数值形参得到的是实际参数的(口。(A)数值(B)地址(C)值 (D)变量 (E)以上都不是—个24*24点阵的汉字字形信息所占的字节数为(口。(A)2 (B)8 (C)24 (D)32(E)72在微机系统中，最基本的输入输出模块BIOS存放在(□中。(A)RAM(B)ROM(C)硬盘(D)寄存器(E)控制器十进制算术表达式:3*512+5*64+2*8+1的运算中，用二进制表示为(口。(A)1011010001(B)10110100011(C)11101010001(D)11110100011(E)111000设栈S的初始状态为空，现对序列｛123,4,5｝在栈S上，依次进行如下操作(从元素1开始,出栈后不再进栈):进栈,出栈,进栈,进栈,出栈,出栈。试问出栈的元素序列是(口。(A){1,2,3}B){1,3,2}C){3,2,1}D){2,3,1}(E)以上都不对E-mail邮件本质上是一个(匚I(A)文件(B)电报(C)电话(D)传真(E)电讯一棵二叉树的高度为h,所有结点的度为0,或为2,则此树最少有(□个结点(A)2h-1 (B)2h-1 (C)2h+1 (D)h+1(E)h*h+112•无向图G=(V,E),其中V={a,b,c,d,e,f}E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}对该图进行深度优先遍历,得到的顶点序列正确的是(□(A)a,b,e,c,d,f(B)a,c,f,e,b,d(C)a,e,b,c,f,d(D)a,b,e,d,f,c(E)以上都不对pascal编译程序是(匚I.把pascal源程序转换成可运行的EXE文件的程序.把pascal源程序转换成等价的目标码的程序.生成和修改一个pascal语言源程序的等程序.把pascal的目标码程序转换成可运行的EXE文件的程序.生成一个等价的汇编程序将三封信投到4个邮筒,最多的投法有( )．种 (B)．种 (C)．种 (D)．34种E.电子信函(电子邮件)的特点之一是( )。.比邮政信函,电报,电话,传真都更快.在通信双方的计算机之间建立其直接的通信线路后即可快速传递数字信息.采用存储-转发方式在网络上逐步传递信息,不象电话那样直接、及时,但费用低廉.在通信双方的计算机都开机工作的情况下即可快速传递数字信息以下属于多媒体硬件的是( )(A).主机(B).光驱(C).声卡 (D).音箱 (E).超级解霸17.正确的二维数组类型说明是( )(A)typear2=array[1..5,5..1]ofinteger;typear2=array[1..5]ofarray[5.1]ofinteger;typear2=array[1..5,1..5]ofinteger;typear2=array[1..5]ofarray[1..5]ofintegertypear2=array[1..5,1..5]of0..1下列属于信息处理的是()(A)信息加工 (B)信息分类(C)信息技术(D)信息采集(E)信息存储在windows中,最小化一个应用程序窗口后，该程序将( )。(A)被终止执行(B)被暂停执行(C)被转入后台(D)继续执行(E)以上答案都不对下面的常量说明中，正确的是()(A)CONST(B)、CONST(C)、CONST(D)、CONST(E)CONSTt=trueb,C=45M=100，15N=1OR2a='A'二、问题求解：(第1小题5分，第2-3小题各4分,共13分)[问题1]:在所有三位数中，各位数字从高位到低位顺次减小的数共有 个。[问题2]："银条"一位银矿勘探员无力预付3月份的房租。他有一根长31英寸的纯银条，因此他和女房东达成如下协议。他说，他将把银条切成小段。3月份的第一天，他给女房东1英寸长的一段，然后每天给她增加1英寸，以此作为抵押。勘探员预期到3月份的最后一天，他能全数付清租金，而届时女房东将把银条小段全部还给他。3月份有31天，一种办法是把银条切成31段，每段长1英寸。可是这处花很多功夫。勘探员希望既履行协议，又能使银条的分段数目尽量减少。例如，他可以第一天给女房东1英寸的一段，第二天再给1英寸的一段，第三开他取回这两段1英寸的而给她3英寸的一段。假设银条的各段是按照这种方式来回倒换的话，勘探员至少需要把他的银条切成 段？[问题3]:"换不开的钞票"钱柜里有1.15美分，一位顾客提出：把1美元的钞票换成硬币，但出纳小姐说换不开，后来这位顾客提出：把50美分的钞票换成硬币，但出纳小姐又说换不开，而实际上，出纳小姐也无法把25美分、10美分、5美分的钞票换成硬币请问钱柜里到底有哪些硬币？他们分别有多少枚？答： 。三、写出程序的运行结果：（每小题6分，共30分）1.programtext1;constn=6;m=3;vari,j,k:integer;beginfori:=-ntondobegink:=n-abs(i);write('':39-k);forj:=-ktokdoifabs(j)>k-mthenwrite(n-(i+n)div2)elsewrite('');writeln;end;end.输出的结果为：PROGAMtext2；VARa:ARRAY[1..10]OFChark:Integer；ch:Char；BEGINFORk:=1TO10DOa[k]:=Chr(Ord('A')+k)；FORk:=1TO10DOBEGINch:=a[k]；a[k]:=a[11-k]；a[11-k]:=ch；END；FORk:=1TO10DOWrite(a[k])；WritelnEND.输出的结果为：programtext3(input,output);Varm,n,p:integer;x:real;proceduremm(varm:integer;x:real);varn:integer;beginm:=m+1;n:=m+1;x:=n*3;p:=n;end;beginm:=8;n:=5;p:=3;x:=1.0;mm(n,x);writeln(m:5,n:5,p:5,x:6:1);end.输出的结果为：programtext4;constn=5;typeary=array[0..n-1,0..n-1]ofinteger;vara:ary;i,j,k:integer;beginfori:=0ton-1doforj:=0ton-1doa[i,j]:=0;k:=1;fori:=1tondoforj:=n-1downtoidobegina[j,j-i]:=k;k:=k+1;end;fori:=0ton-1dobeginforj:=0ton-1dowrite(a[I,j]:4);writeln;end;end.输出的结果为：programtext5(input,output);varch:char;i,n,sum:integer;beginsum:=0;read(ch);casechof'A':fori:=4to6dobeginread(n):sum:=sum＋nend;'B'：beginread(n);fori:=1tondo

beginread(n);sum:=sum＋nend;end;'C':repeatread(n);sum:=sum＋nuntilsum>10;'D':beginread(n);whilen<=3dobeginsum:=sum＋n;read(n)endendend;writeln(sum:4)end.当程序运行(1)输入A4(2)输入B(1)输入A4(2)输入B4(3)输入C4(4)输入D4111123456723456723456723456788889时9时9时9时其输出为其输出为其输出为其输出为四、完善程序(第1题每空2分第2、3题每空3分，共32分)第1题孪生素数是指两个相差为2的素数，例如：3和5，5和7，11和13等下面程序可输出15对孪生素数，其中函数q判断整数a是否为素数。programp(output);vark,n:integerfuncti