信息学初赛模拟试题一二及答案

信息学初赛模拟试题（一）（普与组PASCAL语言 二小时完成满分100分）一、选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）1、MAN英文缩写的含义是（ ）A.局域网 B.城域网

C.广域网 D.增值网2、小张用十六进制，八进制与十进制写了如下一个等式：64－13=33式中三个数是各不相同进位制的数，试问64，13，33，分别为________。A．八进制，十进制，十六进制B．十进制，十六进制，八进制C．八进制，十六进制，十进制D．十进制，八进制，十六进制3、表达式(4MOD(－3))与(－4MOD3)的值为：_______。A．－1，－1B．1，－1C．－1，1D．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=9B．y=200C．y=10D．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个英文字母组成C．在CPU中能够同时处理32位二进制数据D．在CPU中运算的最大结果为2的32次方8、假设一台计算机的地址总线为16，则中央处理器CPU能访问的最大存储器容量为()A．2*16KBB．16KBC．216BD．16*1024*8B9、计算机最终处理的信息形式是（）A．ASCII码

B．BCD码

C．二进制

D．十六进制10、与十六进制数6F等值的八进制数是（）A．166

B．139

C．157

D．18311、以下属非法用户自定义标识符的是()。A．dateB．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]是()。A．一个实型的数组元素B．一个数组，该数组具有两个实型数组元素C．一个数组，该数组具有4*2个实型数组元素D．一个数组，该数组具有5*4*2个实型数组元素15、下列属于线性时间的排序算法是：（）A.快速排序B.桶排序C.冒泡排序16、一棵包含n个节点的树有几条边：A.nB.n-1C.不一定17、在Pascal语言中，表达式35div3mod4的值是________。

A．０B．２C．３D．６18、在数据结构中，"树"结构下层结点出现三个以上的结点，这种结构称为________。

A．三层树B．三叉树C．多层树D．多叉树19、在Pascal语言中，下列程序段所计算的公式是________。

程序段：S：=0；T：=1；

ForI：=1to10do

Begin

T：=T*I；

S：=S+T；

end;A.S=1+2+3+4+……+10

B.S=1*2*3*4*……*10

C.S=1！+2！+3！+4！+……+10！

D.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;begin ifn=0thengcd:=melsegcd:=gcd(n,mmodn)end;begin read(m,n); g:=gcd(m,n); writeln('m=',m,'n=',n,'gcd=',g)end.输入：489输出：三、问题解答（第1题每空4分，第2题8分）1、数据结构中，下面是一个树结构图，这个树的"先序遍历"结果是________，中序遍历结果是：________________。248+3*4107-*/@2、给出一个后缀算术表达式为

写出对应的中缀算术表达式：___________________________________________248+3*4107-*/@四、完善程序（第一题每空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个元素必在区间[1,j],因此取A[1],…,A[j]为新的元素集合,然后重复上述的”部分排序”的过程。如果j<k,则第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分）12345678910DCBBDDCCCC111281920DBCBBBCDDB二、阅读下列程序，写出程序运行结果（第1题5分，第2，3，4题各6分，共23分）1、98543（172，16）=43、S=2524、m=48n=9gcd=3三、问题解答（第1题每空4分，第2题8分）1、ABCDEBADCE2、(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信息学初赛模拟试题(二)选择题：（选出每题正确的答案代码，填在括号里，1—10题为单选题，每小题只有一个正确答案，11—20题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题1.5，共30分）1、二进制数01100100转换成十六进制数是（）。A．32B．64C．128D．100E．2562、操作系统是一类重要的系统软件，下面几个软件中，不属于系统软件的是（）。A．JavaB．MS-DOSC．LinuxD．Windows2000E．Unix3、计算机病毒的传染是以计算机运行与（）为基础的，没有这两个条件，病毒是不会传染的。A．编辑文稿B．读写磁盘C．编程序D．扫描图画E．打印4、因特网不属于任何个人，也不属于任何组织。其中在网络知识这一块中有一个英文简写ISP，它的中文意思是（）。A．因特网连接B．因特网使用C．因特网设计D．因特网服务提供者E．信息传输5、Internet给我们提供了资源共享、浏览、检索信息与远程登录等多种服务，下面几个选项中用于远程登录的是（）。A．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、在流程图的符号中，菱形框一般作为（）。A．起始框B．判断框C．输入输出框D．处理工作框E．结速框10、在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主要将要输出打印的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个（）结构。A．堆栈B．数组C．线性表D．队列E．链表11、多媒体技术中的“多媒体”的含义主要是指如（）等多种表达信息的形式。A．磁盘B．音箱C．显示器D．声音E．图像12、下面有关计算机知识说明，正确的是（）。在WINDOWS98操作系统下，删除磁盘中的文件时都先存放在回收站中FOXMAIL是用于收发电子邮件的工具C．文件夹组织是一个有层次的树状结构，其中最顶层的是桌面D．存储器具有记忆能力，其中的信息任何时候都不会丢失E．为了提高软件的测试效率，应该选择发现错误的可能性大的测试数据13、对按关键字排序好的线性表进行二分查找，该线性表适合的存储结构为（）。A．链接存储B．索引存储C．散列存储D．顺序存储E．循环存取14、一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的输出序列的是（）。A．54312B．24135C．21543D．12534E．1234515、评价一个算法的好坏有多种指标，下列是算法评价指标的是（）。正确性B．运行时间C．占用空间D．迭代次数E．简单性16、下面描述用多维数组表示的数据结构的语句中，正确的是（）。多维数组存放的都是同一种类型的数据多维数组各维的下标范围必须一样多维数组在内存中的地址是连续的多维数组中的下标不能是表达式多维数组是随机存取的数据结构17、若已知一个栈的入栈顺序1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn（它是输入序列的一个排列），则在输出序列中可能出现的情况是（）。A．Pj<Pk<Pi，其中i<j<kB．Pk<Pj<Pi，其中i<j<kC．Pj<Pi<Pk，其中i<j<kD．Pi<Pk<Pj，其中i<j<kE．以上都不可能出现18、线性表具有如下的结构特点：（）A．均匀性B．单一性C．简单性D．无序性E．有序性19、下列关于数据结构的叙述中正确的是（）。A．数据结构是带有结构的数据元素的集合B．线性表的线性存储结构优于链式存储结构C．队列是限定仅在一端进行插入，在另一端进行删除的线性表D．二维数组是其数据元素为线性表的线性表E．图是一种非线性数据结构20、任意一棵树均可惟一地转换成与它对应的二叉树。由树转换成的二叉树中，顶点N的左右子女分别是N在原树里对应顶点的（）。最左子顶点/最邻近的右兄弟最右子顶点/最右的兄弟C．最邻近的右兄弟/最左的兄弟D．最邻近的左兄弟/最邻近的右兄弟最邻近的右兄弟/最右的兄弟问题解答：（共2题，每题5分，共10分）光明中学开设数学、英语与信息学三个兴趣学习小组，其中数学小组30人，英语小组15人，信息学小组18人，参加三个小组总人数为50人，其中有3人同时参加3个小组，则同时只参加两个小组的同学有多少人？给出一组顶点（顶点值用A，B，C，D，E，F表示），其对应权值分别为2，3，1，7，8，4。请以A，B，C，D，E，F为叶子顶点构造一棵哈夫曼树，并求出它的最小带权路径长度WPL的值。信息学命题(二)参考答案选择题：（选出每题正确的答案代码，填在括号里，1—10题为单选题，每小题只有一个正确答案，11—20题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题1.5，共30分）题号12345678910答案BABDCBECBD题号111281920答案DEBCEDCEABCEACEBCDAEACDEA二、问题解答：（共2题，每题5分，共10分）第1题：7第2题：61信息学初赛模拟试题(二)选择题：（选出每题正确的答案代码，填在括号里，1—10题为单选题，每小题只有一个正确答案，11—20题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题1.5，共30分）1、二进制数01100100转换成十六进制数是（）。A．32B．64C．128D．100E．2562、操作系统是一类重要的系统软件，下面几个软件中，不属于系统软件的是（）。A．JavaB．MS-DOSC．LinuxD．Windows2000E．Unix3、计算机病毒的传染是以计算机运行与（）为基础的，没有这两个条件，病毒是不会传染的。A．编辑文稿B．读写磁盘C．编程序D．扫描图画E．打印4、因特网不属于任何个人，也不属于任何组织。其中在网络知识这一块中有一个英文简写ISP，它的中文意思是（）。A．因特网连接B．因特网使用C．因特网设计D．因特网服务提供者E．信息传输5、Internet给我们提供了资源共享、浏览、检索信息与远程登录等多种服务，下面几个选项中用于远程登录的是（）。A．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、在流程图的符号中，菱形框一般作为（）。A．起始框B．判断框C．输入输出框D．处理工作框E．结速框10、在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主要将要输出打印的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个（）结构。A．堆栈B．数组C．线性表D．队列E．链表11、多媒体技术中的“多媒体”的含义主要是指如（）等多种表达信息的形式。A．磁盘B．音箱C．显示器D．声音E．图像12、下面有关计算机知识说明，正确的是（）。在WINDOWS98操作系统下，删除磁盘中的文件时都先存放在回收站中FOXMAIL是用于收发电子邮件的工具C．文件夹组织是一个有层次的树状结构，其中最顶层的是桌面D．存储器具有记忆能力，其中的信息任何时候都不会丢失E．为了提高软件的测试效率，应该选择发现错误的可能性大的测试数据13、对按关键字排序好的线性表进行二分查找，该线性表适合的存储结构为（）。A．链接存储B．索引存储C．散列存储D．顺序存储E．循环存取14、一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的输出序列的是（）。A．54312B．24135C．21543D．12534E．1234515、评价一个算法的好坏有多种指标，下列是算法评价指标的是（）。正确性B．运行时间C．占用空间D．迭代次数E．简单性16、下面描述用多维数组表示的数据结构的语句中，正确的是（）。多维数组存放的都是同一种类型的数据多维数组各维的下标范围必须一样多维数组在内存中的地址是连续的多维数组中的下标不能是表达式多维数组是随机存取的数据结构17、若已知一个栈的入栈顺序1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn（它是输入序列的一个排列），则在输出序列中可能出现的情况是（）。A．Pj<Pk<Pi，其中i<j<kB．Pk<Pj<Pi，其中i<j<kC．Pj<Pi<Pk，其中i<j<kD．Pi<Pk<Pj，其中i<j<kE．以上都不可能出现18、线性表具有如下的结构特点：（）A．均匀性B．单一性C．简单性D．无序性E．有序性19、下列关于数据结构的叙述中正确的是（）。A．数据结构是带有结构的数据元素的集合B．线性表的线性存储结构优于链式存储结构C．队列是限定仅在一端进行插入，在另一端进行删除的线性表D．二维数组是其数据元素为线性表的线性表E．图是一种非线性数据结构20、任意一棵树均可惟一地转换成与它对应的二叉树。由树转换成的二叉树中，顶点N的左右子女分别是N在原树里对应顶点的（）。最左子顶点/最邻近的右兄弟最右子顶点/最右的兄弟C．最邻近的右兄弟/最左的兄弟D．最邻近的左兄弟/最邻近的右兄弟最邻近的右兄弟/最右的兄弟问题解答：（共2题，每题5分，共10分）光明中学开设数学、英语与信息学三个兴趣学习小组，其中数学小组30人，英语小组15人，信息学小组18人，参加三个小组总人数为50人，其中有3人同时参加3个小组，则同时只参加两个小组的同学有多少人？给出一组顶点（顶点值用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;endendend.输出：四、完善程序（共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:=1tondoend;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;end.第2题（7分）【问题描述】给定一个01串，请你找出长度介于a,b之间，重复出现次数最多的01串。输入：a,b(0<a<=b<=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:=1to13doreadln(a,b);read(c);s:=1