NOIP2001提高组初赛试题答案

第七届分区联赛提高组初赛(提高组PASCAL语言二小时完成)一、选择一个正确答案代码(A/B/C/D)，填入每题的括号内(每题1.5分，多选无分，共30分)1、中央处理器CPU能访问的最大存储器容量取决于()A)地址总线B)数据总线C)控制总线D)内存容量2、计算机软件保护法是用来保护软件()的。A)编写权B)复制权C)使用权D)著作权3、64KB的存储器用十六进制表示，它的最大的地址码是()A)10000B)FFFFC)1FFFFD)EFFFF4、在树型目录结构中，不允许两个文件名相同主要指的是()A)同一个磁盘的不同目录下B)不同磁盘的同一个目录下C)不同磁盘的不同目录下C)同一个磁盘的同一个目录下5、下列设备哪一项不是计算机输入设备()A)鼠标B)扫描仪C)数字化仪D)绘图仪6、在计算机硬件系统中，cache是()存储器A)只读B)可编程只读C)可擦除可编程只读D)高速缓冲7、若我们说一个微机的CPU是用的PII300，此处的300确切指的是()A)CPU的主时钟频率B)CPU产品的系列号C)每秒执行300百万条指令D)此种CPU允许最大内存容量8、Email邮件本质上是一个()A)文件B)电报C)电话D)传真9、2KB的内存能存储()个汉字的机内码A)1024B)516C)2048D)21810、以下对Windows的叙述中，正确的是()A)从软盘上删除的文件和文件夹，不送到回收站B)在同一个文件夹中，可以创建两个同类、同名的文件C)删除了某个应用程序的快捷方式，将删除该应用程序对应的文件D)不能打开两个写字板应用程序11、运算式(2047)10—(3FF)16+(2000)8的结果是()A)(2048)10B)(2049)10C)(3746)8D)(1AF7)1612、TCP/IP协议共有()层协议A)3B)4C)5D)613.若已知一个栈的入栈顺序是1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn，若P1是n，则Pi是()A)iB)n-1C)n-i+1D)不确定14.计算机病毒是()A)通过计算机传播的危害人体健康的一种病毒B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合C)一种由于计算机元器件老化而产生的对生态环境有害的物质D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒15.下面关于算法的错误说法是()A)算法必须有输出B)算法必须在计算机上用某种语言实现C)算法不一定有输入D)算法必须在有限步执行后能结束16.[x]补码=10011000，其原码为()A)011001111B)11101000C)11100110D)0110010117.以下哪一个不是栈的基本运算()A)删除栈顶元素B)删除栈底的元素C)判断栈是否为空D)将栈置为空栈18.在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为()A)2B)3C)4D)519.一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有()个结点A)2h-1B)2h-1C)2h+1D)h+120.无向图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,fB)a,c,f,e,b,dC)a,e,b,c,f,dD)a,b,e,d,f,c二、问题求解(5+7=12分)1.已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为：2.平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？三、阅读程序，写出程序正确的运行结果(4+7+8+9=28分)1.PROGRAMGAO7_1：FUNCTIONACK(M，N：INTEGER)：INTEGER；BEGINIFM=0THENACK：=N+1ELSEIFN=0THENACK:=ACK(M-1，1)ELSEACK:=ACK(M-1，ACK(M，N-1))END；BEGINWRITELN(ACK(3，4))；READLN；END.输出2.PROGRAMGAO7_2；VARP，Q，S，T：INTEGER；BEGINREADLN(P)；FORQ：=P+1TO2*PDOBEGINT:=0；S:=(P*Q)MOD(Q-P)；IFS=0THENBEGINT:=P+Q+(P*Q)DIV(Q-P)；WRITE(T：4)；END；END；END.输入12输出3.PROGRAMGAO7_3；VARI，J，H，M，N，K：INTEGER；B：ARRAY[1..10]OFINTEGER；BEGINREADLN(N)；FORI:=1TO10DOBEGINM：=N；J：=11；WHILEM0DOBEGINJ:=J-1；B[J]：=MMOD10；M:=MDIV10END；FORH:=JTO10DON:=N+B[H]；END；WRITELN(N)；END.输入1234输出：4.PROGRAMGAO7_4；VARX，Y1，Y2，Y3：INTEGER；BEGINREADLN(X)；Y1：=0；Y2：=1；Y3：=1；WHILEY2=XDOBEGINY1：=Y1+1；Y3：=Y3+2；Y2：=Y2+Y3END；WRITELN(Y1)；END.输入：23420输出：四、完善程序(每空3分，共30分)1.存储空间的回收算法。设在内存中已经存放了若干个作业A，B，C，D。其余的空间为可用的(如图一中(a))。此时，可用空间可用一个二维数组dk[1..100，1..2]表示，(如下表一中(a))，其中：dk[i，1]对应第i个可用空间首址，dk[i，2]对应第i个可用空间长度如上图中，dk：10050300100501000010050300100500100100000表一(a)表一(b)现某个作业释放一个区域，其首址为d，长度为L，此时将释放区域加入到可用空间表中。要求在加入时，若可用空间相邻时，则必须进行合并。因此出现下面的4种情况(如上图一(b)所示)。(1)下靠，即回收区域和下面可用空间相邻，例如，d=80，L=20，此时成为表二中的(a)。(2)上靠，例如，d=600，L=50，此时表成为表二中的(b)。(3)上、下靠，例如，d=150，L=150，此时表成为表二中的(c)。(4)上、下不靠，例如，d=430，L=20，此时表成为表二中的(d)。807030010050100100503001005001501003005001001005030010043020500100表二(a)(下靠)表二(b)(上靠)表二(c)(上，下靠)表二(d)(上，下不靠)程序说明：对数组dk预置2个标志，即头和尾标志，成为表二中(b)，这样可使算法简单，sp为dk表末地址。程序清单：vari,j,sp,d,l:integer;dk:array[0..100,1..2]ofinteger;beginreadln(sp);fori:=1tospdoreadln(dk[i,1],dk[i,2]);dk[0,1]:=0;dk[0,2]:=0;___①____;dk[sp,1]:=10000;dk[sp,2]:=0;readln(d,l);i:=1;whiledk[i,1]ddoi:=i+1;___②____;if(dk[i,1]+dk[i,2]=d)thenif(d+l=dk[i+1,1])thenbegindk[i,2]:=___③___;forj:=i+1tosp-1dodk[j]:=dk[j+1];sp:=sp-1;endelsedk[i,2]:=dk[i,2]+l//l不是1elseif(d+l=dk[i+1,1])thenbegindk[i+1,1]:=____④____;dk[i+1,2]:=dk[i+1,2]+lendelsebeginforj:=spdowntoi+1dodk[j+1]:=dk[j];___⑤____:=d;dk[i+1,2]:=l;sp:=sp+1;end;fori:=1tosp-1dowriteln(dk[i,1]:4,dk[i,2]:4);readln;end.2.求关键路径设有一个工程网络如下图表示(无环路的有向图)：其中，顶点表示活动，①表示工程开始，⑤表示工程结束(可变，用N表示)，边上的数字表示活动延续的时间。如上图中，活动①开始5天后活动②才能开始工作，而活动③则要等①、②完成之后才能开始，即最早也要7天后才能工作。在工程网络中，延续时间最长的路径称为关键路径。上图中的关键路径为：①—②—③—④—⑤共18天完成。关键路径的算法如下：1.数据结构：R[1..N，1..N]OFINTEGER；表示活动的延续时间，若无连线，则用-1表示；EET[1..N]表示活动最早可以开始的时间ET[1..N]表示活动最迟应该开始的时间关键路径通过点J，具有如下的性质：EET[J]=ET[J]2.约定：结点的排列已经过拓扑排序，即序号前面的结点会影响序号后面结点的活动。程序清单：vari,j,n,max,min,w,x,y:integer;r:array[1..20,1..20]ofinteger;eet,et:array[1..20]ofinteger;beginreadln(n);fori:=1tondoforj:=1tondor[i,j]:=-1;readln(x,y,w);whilex0dobeginr[x,y]:=w;___①____;end;eet[1]:=0;fori:=2tondobeginmax:=0;forj:=1tondoifr[j,i]-1thenif___②___thenmax:=r[j,i]+eet[j];eet[i]:=max;end;____③____fori:=n-1downto1dobeginmin:=1000;forj:=1tondoifr[i,j]-1thenif___④___thenmin:=et[j]-r[i,j];et[i]:=min;end;writeln(eet[n]);fori:=1ton-1doif___⑤___thenwrite(i,'→');writeln(n);readln;end.第七届全国青少年信息学(计算机)奥林匹克分区联赛初赛试题(普及组参考答案)一、选择一个正确答案代码(A/B/C/D)，填入每题的括号内(每题1.5分，多选无分，共30分)题号12345678910选择CDBDBCDCAA题号11121314151617181920选择ACBAABCDCC二、问题解答(5+7分，两题共12分)1.答：在a,b,c,d,e,f六件物品中，按条件能选出的物品是：a,b,c,f2.答：用这些点为顶点，能组成751个不同三角形三、阅读程序，并写出程序的正确运行结果：(5+8+9+9分，共31分)(1)程序的运行结果是：7(2)程序的运行结果是：1361012021504036(3)程序的运行结果是：181110877666626160(4)程序的运行结果是：6734四、根据题意，将程序补充完整(每个点3分，共30分)题一①B[X]+1;②K:=0;③B[I]0④I:4⑤KMOD8=0题二①B[0]=0②S+D[I,B[I]];③B[J]=D[J,0]④S:=S+G[I]