1、信息学竞赛普及组初赛模拟试题(四)一、选择题：（选出每题正确的答案代码，填在括号里，110题为单选题，每小题只有一个正确答案，1120题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题1.5，共30分）1、二进制数01100100转换成十六进制数是（）。A32B64C128D100E2562、操作系统是一类重要的系统软件，下面几个软件中，不属于系统软件的是（）。AJavaBMS-DOSCLinuxDWindows2000EUnix3、计算机病毒的传染是以计算机运行和（）为基础的，没有这两个条件，病毒是不会传染的。A编辑文稿B读写磁盘C编程序D扫描图画E打印4、因特网不属于任何个
2、人，也不属于任何组织。其中在网络知识这一块中有一个英文简写ISP，它的中文意思是（）。A因特网连接B因特网使用C因特网设计D因特网服务提供者E信息传输5、Internet给我们提供了资源共享、浏览、检索信息和远程登录等多种服务，下面几个选项中用于远程登录的是（）。AWWWBTCP/IPCTelnetDE-mailEFTP6、IE是目前流行的浏览器软件，它的工作基础是解释执行用（）语言书写的文件。AVCBHTMLCBASICDHTTPEVB7、给出3种排序：插入排序、冒泡排序、选择排序。这3种排序的时间代价分别是（）。AO(n)、O(n2)、O(logn)BO(logn)、O(n)、O(n2)C
3、O(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、多媒体技术中的“多媒体”的含义主要是指如（）等多种表达信息的形式。A磁盘B音箱C显示器D声音E图像12、
4、下面有关计算机知识说明，正确的是（）。A在WINDOWS98操作系统下，删除磁盘中的文件时都先存放在回收站中BFOXMAIL是用于收发电子邮件的工具C文件夹组织是一个有层次的树状结构，其中最顶层的是桌面D存储器具有记忆能力，其中的信息任何时候都不会丢失E为了提高软件的测试效率，应该选择发现错误的可能性大的测试数据13、对按关键字排序好的线性表进行二分查找，该线性表适合的存储结构为（）。A链接存储B索引存储C散列存储D顺序存储E循环存取14、一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的输出序列的是（）。A54312B24135C21543D12534E1234515、评价一个算法的
5、好坏有多种指标，下列是算法评价指标的是（）。A正确性B运行时间C占用空间D迭代次数E简单性16、下面描述用多维数组表示的数据结构的语句中，正确的是（）。A多维数组存放的都是同一种类型的数据B多维数组各维的下标范围必须一样C多维数组在内存中的地址是连续的D多维数组中的下标不能是表达式E多维数组是随机存取的数据结构17、若已知一个栈的入栈顺序1，2，3，n，其输出序列为P1，P2，P3，Pn（它是输入序列的一个排列），则在输出序列中可能出现的情况是（）。APjPkPi，其中ijkBPkPjPi，其中ijkCPjPiPk，其中ijkDPiPkPj，其中ij=n;writeln(a);end.输入：4
6、15377输出：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题，每题14分，共28分）第1题（7分）【问题描述】设有n种
7、物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为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(w,sizeof(w),0);fillchar(u,si
8、zeof(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,jthendec(i)elsebegindec(j,wi);end;
9、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,k,a,b,max:integer;m:array1819
10、2ofinteger;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=maxthenbeginj:=0;k:=I;repeatin
11、c(j);vj:=kmod2;until;whilej0dobeginwrite(vj);dec(j)end;writeln;end;end.信息学命题(四)参考答案一、选择题：（选出每题正确的答案代码，填在括号里，110题为单选题，每小题只有一个正确答案，1120题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题1.5，共30分）题号12345678910答案BABDCBECBD题号11121314151617181920答案DEBCEDCEABCEACEBCDAEACDEA二、问题解答：（共2题，每题5分，共10分）第1题：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