第六年全国青少年信息学奥林匹克分区普组初赛联赛试题

1、第六年全国青少年信息学(计算机)奥林匹克分区普及组初赛联赛试题第六年全国青少年信息学(计算机)奥林匹克分区普及组初赛联赛试题8/8第六年全国青少年信息学(计算机)奥林匹克分区普及组初赛联赛试题第六年全国青少年信息学（计算机）奥林匹克分区普及组初赛联赛试题普及组PASCAL语言二小时完成全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效【一】选择一个正确答案代码A/B/C/D，填入每题的括号内(每题1.5共30分分，多项选择无分，1、以下无符号数中，最小的数是、A、110110012B、7510C、378D、2A162、在外面设备中，绘图仪属于、A、输入设备B、输出设备C、辅外储藏器D、主内储

2、藏器3、GB2312-80规定了一级汉字3755个，二级汉字3008个，其中二级汉字字库中的汉字是以为序排列的、A、以笔划多少B、以部首C、以ASCII码D、以机内码4、算法是指、A、为解决问题而编制的计算机程序B、为解决问题而采用的方法与步骤C、为解决问题而需要采用的计算机语言D、为解决问题而采用的计算方法5、RAM中的信息是、A、生产厂家起初写入的B、计算机工作时随机写入的C、防范计算机病毒侵入所使用的D、特地用于计算机开机时自检用的6、计算机主机是由CPU与组成的、A、控制器B、运算器C、输入、输出设备D、内储藏器7、计算机病毒的特点是、A、流传性、暗藏性、易读性与隐蔽性B、破坏性、流传

3、性、暗藏性与安全性C、流传性、暗藏性、破坏性与隐蔽性D、流传性、暗藏性、破坏性与易读性8、设循环队列中数组的下标范围是1n，其头尾指针分别为f和r，那么其元素个数为、A、r-fB、r-f+1C、r-fMODn+1D、r-f+nMODn9、在待排序的数据表差不多为有序时，以下排序算法中开销时间反而多的是、A堆排序B希尔排序C冒泡排序D快速排序10、Internet的规范译名应为、A、英特尔网B、因特网C、万维网D、以太网11、WINDOWS9X是一种操作系统、A、单任务字符方式B、单任务图形方式C、多任务字符方式D、多任务图形方式12、某种计算机的内存容量是640K,那个地方的640K容量是指(

4、)个字节、A、640B、640*1000C、640*1024D、640*1024*102413、在Windows9X中，菜单项后带有符号“”，表示该菜单项()、A、能够进行开关选择B、执行时有对话框C、有假设干子命令D、不能够执行14、某数列有1000个各不相同的单元，由低至高挨次排列；现要对该数列进行二分法检索(binarysearch)，在最坏的情況下，需检视()个单元、A、15、数组A中，每个元素AI，J在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A5，8的初步地址为、A、SA+141B、SA+180C、SA+222D、S

5、A+22516、大伙理解，不相同种类的储藏器组成了多层次结构的储藏器系统，排列是、按存取速度从快到慢的A、快存C、快存/辅存/主存/主存/辅存B、外存D、主存/主存/辅存/辅存/外存17、线性表假设采用链表存贮结构，要求内存中可用存贮单元地址、A、必定连续B、部分地址必定连续C、必然不连续D、连续不连续均可18、以下表达中，正确的选项是、A线性表的线性存贮结构优于链表存贮结构B队列的操作方式是先进后出C栈的操作方式是先进先出D、二维数组是指它的每个数据元素为一个线性表的线性表19、电线上停着两种鸟A，B，能够看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类：一类是两端的小鸟相同；另一

6、类那么是两端的小鸟不相同、：电线两个极点上正好停着相同的小鸟，试问两端为不相同小鸟的线段数目必然是A、奇数B、偶数C、可奇可偶D、数目固定20、请仔細閱读以下程序段:PASCAL语言BASIC语言、上列程序段的正确輸出是A、-1B、-2C、-3D、-4、【二】问题解答每题7分，共14分1、，按中序遍历二叉树的结果为：abc问：有多少种不相同形态的二叉树能够获取这一遍历结果，并画出这些二叉树。2、有2n的一个长方形方格，用一个此刻用一个12的骨牌铺满方格，共有12的骨牌铺满方格。比方3种铺法：n=3时，为23方格。试对给出的任意一个nn0，求出铺法总数的递推公式。【三】阅读程序，并写出程序正确的

7、运行结果10+16分，共1、PROGRAMNOI_002;26分VARI,J,L,N,K,S,T:INTEGER;B:ARRAY1.10OF0.9;BEGINREADLN(L,N);S:=L;K:=1;T:=L;WHILES0DOBEGINJ:=J-1;BJ:=NMODL;N:=NDIVLEND;FORI:=10-K+1TO10DOWRITE(CHR(ORD(A)+BI);END.输入：4167输出：2、PROGRAMNOI_004;VARI,J,J1,J2,P,Q:INTEGER;P1:BOOLEAN;B,C:ARRAY1.100OFINTEGER;BEGINREADLN(Q,P);J:=1

8、;P1:=TRUE;BJ:=Q;J1:=0;WHILE(Q0)ANDP1DOBEGINJ1:=J1+1;CJ1:=Q*10DIVP;Q:=Q*10-CJ1*P;IFQ0THENBEGINJ2:=1;WHILE(BJ2Q)AND(J2=J)DOJ2:=J2+1;IFBJ2=QTHENBEGINP1:=FALSE;WRITE(0.);FORI:=1TOJ2-1DOWRITE(CI:1);WRITE();FORI:=J2TOJ1DOWRITE(CI:1);WRITELN()ENDELSEBEGINJ:=J+1;BJ:=QENDENDEND;IFQ=0THENBEGINWRITE(0.);FORI:=

9、1TOJ1DOWRITE(CI:1);WRITELNEND;READLNEND.输入18输出输入27输出【四】完满程序每题15分，共30分1.将2n个0和2n个1，排成一圈。从任一个地址开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的2个二进制数都不相同。比方，当n=2时,即个0和个1排成以下一圈：A00101110比方，从A地址开始，逆时针方向取三个数000，尔后再从B地址上开始取三个数001，接着从C开始取三个数010，、能够获取000，001，010，101，011，111，110，100共8个二进制数且都不相同。程序说明以n=4为例，

10、即有16个0，16个1，数组a用以记录32个0，1的排法，数组b统计二进制数可否已出现过。程序清单PROGRAMNOI00;VARA:ARRAY1.36OF0.1;B:ARRAY0.31OFINTEGER;I,J,K,S,P:INTEGER;BEGINFORI:=1TO36DOAI:=0;FORI:=28TO32DOAI:=1;P:=1;A6:=1;WHILE(P=1)DOBEGINJ:=27;WHILEAJ=1DOJ:=J-1;FORI:=J+1TO27DOFORI:=0TO31DOBI:=0;FORI:=1TO32DOBEGINFORK:=ITOI+4DOS:=S*2+AK;END;S:=

11、0;FORI:=0TO31DOS:=S+BI;IFTHENP:=0END;FORI:=1TO32DOFORJ：=ITOI+4DOWRITE(AJ);WRITELNEND.2、多项式的乘法。比如有以下多项式：P(X)=2X2-X+1,Q(X)=X+1那么：P(X)Q(X)=(2X2-X+1)(X+1)=2X3+X2+1程序说明：多项式的表示：系数、指数如上例中：P(X)：系数指数Q(X)系数指数2211-1110100000PXQ的结果存入C中。其输出格式是：依次用一对括号内的系数，指数分别来表示。如上例的输出结果表示为：2，31，21，0程序清单PROGRAMNOI_007;VARI,J,K,

12、L,JP,JQ,JC,X,Y,X1,Y1:INTEGER;P,Q:ARRAY1.10,1.2OFINTEGER;C:ARRAY1.20,1.2OFINTEGER;BEGINJP:=0;READLN(X,Y);WHILEX0DOBEGINJP:=JP+1;PJP,1:=X;PJP,2:=Y;READLN(X,Y)END;JQ:=0;READLN(X,Y);WHILEX0DOBEGINJQ:=JQ+1;QJQ,1:=X;QJQ,2:=Y;READLN(X,Y)END;JC:=1;CJC,1:=0;CJC,2:=-1000;FORI:=1TOJPDOBEGINY:=PI,2;FORJ:=1TOJQD

13、OBEGINY1:=Y+QJ,2;K:=1;WHILEY10，用FN表示其铺法的总数的递推公式为:7分赛区市学校姓名=密封线=【三】阅读程序，并写出程序的正确运行结果10+16分，共26分（1）程序的运行结果是:（2）程序的运行结果是:【四】依照题意，将程序补充完满(每个点3分，共30分)PASCAL语言BASIC语言题一70110140180220题二190240280300350第六届全国青少年信息学计算机奥林匹克分区联赛初赛试题普及组参照答案【一】选择一个正确答案代码A/B/C/D，填入每题的括号内(每题1.5分，多项选择无分，共30分题号1245678910选择CBBBBDCDDB题号11121314151617181920选择DCBBACDDBA【二】问题解答第1题的第1问2分，第2问5分，第2题7分，两题共14分1、答：有5种不相同形态的二叉树能够获取这一遍历结果；可画出的这些二叉树为:abacc/baccab/cbba2、对给出的任意一个nn0，用Fn表示其铺法的总数的递推公式为:F1=1F2=2Fn=Fn-2+Fn-1n3【三】阅读程序，并写出程序的正确运行结果10+16分，共26分程序的运行结果是:BBAC程序的运行结果是:0.1250.2