第十五届全国青少年信息学奥林匹克联赛初赛试题.doc

第十五届全国青少年信息学奥林匹克联赛初赛试题红旗中学网站n1DAq&v0eQ4（ 提高组 Pascal 语言 二小时完成）红旗中学网站| g,i8(F一.单项选择题 （共10题，每题1.5分，共计15分，每题有且仅有一个正确答案。）t4qV,Mn0?%?:Pf:01、 关于图灵机下面的说法哪个是正确的：M/aLd)WG0 A） 图灵机是世界上最早的电子计算机。?%qo-f3P0 B） 由于大量使用磁带操作，图灵机运行速度很慢。红旗中学网站!c&I4D?C） 图灵机只是一个理论上的计算模型。红旗中学网站w u*GM3I VB2uD） 图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。红旗中学网站9#K-v3b c_2、 关于BIOS下面的说法哪个是正确的：红旗中学网站$Ab#k rqnA） BIOS是计算机基本输入输出系统软件的简称。#T!h-Z!D:k1_0 B） BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。红旗中学网站jX T3ImX*f83!n-hC） BIOS一般由操作系统厂商来开发完成。#kc6iXcja0 D） BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。KA!O M03、 已知大写字母A的ASCII编码为65（十进制），则大写字母J的十六进制ASCII编码为：红旗中学网站o*7aJ.n!hzdA）48 B）49 C）50 D）以上都不是红旗中学网站 sU2K vg Yy5_4、 在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。其对应的十进制整数应该是：o u#Y:wN%SI0 A）19 B）-19 C）18 D）-18红旗中学网站w$_ FJ%NEtI*O4y5、 一个包含n个分支结点（非叶结点）的非空满k叉树，k=1，它的叶结点数目为：&k2FPS3Wp-_0 A） nk+1 B）nk-1 C）(k+1)n-1 D）(k-1)n+1红旗中学网站%OCj:X!DB6、 表达式a*(b+c)-d的后缀表达式是：红旗中学网站7T)O wr(V4LH(_;rA） abcd*+- B）abc+*d- C）abc*+d- D）-+*abcd红旗中学网站2HeaJ)t7、 最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码：q#|xnd!A:v0 A）（00，01，10，11）红旗中学网站*jVV/X-nx? n2 B）（0，1，00，11）&U6j-K8j$c1U!S3/L0 C）（0，10，110，111）红旗中学网站0Ac0Z1!Y!Mx:g D）（1，01，000，001）红旗中学网站0Og8kDI:k8、 快速排序平均情况和最坏情况下的算法时间复杂度分别为：红旗中学网站 s,|5Md7MEA） 平均情况O(nlog(2,n)，最坏情况O(n2)/W3RU-a uR9h%R0 B） 平均情况O(n)，最坏情况O(n2)红旗中学网站Hyi:XO8A?9XfC） 平均情况O(n)，最坏情况O(nlog(2,n)%a-Pl-S*q0 D） 平均情况O(log(2,n)，最坏情况O(n2)红旗中学网站OkP(L$r m/b 9、 左图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。则依次加入最小生成树的顶点集合的顶点序列为：红旗中学网站Md2!a)_pc红旗中学网站3D w?%a1QHz1f)KA） V0，V1，V2，V3，V5，V4htem)A3T0 B） V0，V1，V5，V4，V3，V3红旗中学网站TR0E%WmNCxC） V1，V2，V3，V0，V5，V4IMr2gR0 D） V1，V2，V3，V0，V4，V5红旗中学网站$ty5rAD$10、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是：p N#j:J?2W7u60 A） /红旗中学网站VTC6hn O b B） /红旗中学网站/?Q7Ic3GgC） /mA VD!t0 D） /,N O N jRHc,x0 二.不定项选择题（共10题，每题1.5分，共计15分，每题正确答案的个数不少于1。多选或少选均不得分）。xc9Se4faW E 0 1、关于CPU下面哪些说法是正确的：d%KDALW(Vta0 A）CPU全称为中央处理器（或中央处理单元）。gZPee3jV0 B）CPU能直接运行机器语言。红旗中学网站c)bN1$Srq MUC）CPU最早是由Intel公司发明的。红旗中学网站F(a.h| U4SD）同样主频下，32位的CPU比16位的CPU运行速度快一倍。qbVa0C0 2、关于计算机内存下面的说法哪些是正确的：红旗中学网站Gi%bna: kA）随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。hMPin%k|p0 B）一般的个人计算机在同一时刻只能存/取一个特定的内存单元。红旗中学网站4q&s,ny gcsC）计算机内存严格来说包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。i yc2Ac.F0 D）1MB内存通常是指1024*1024字节大小的内存。红旗中学网站4Sj1a _3、关于操作系统下面说法哪些是正确的：红旗中学网站 Qt2vE C m$GvA.多任务操作系统专用于多核心或多个CPU架构的计算机系统的管理。,Sy&b9WL00 B.在操作系统的管理下，一个完整的程序在运行过程中可以被部分存放在内存中。N EqoQ)e!X-A0 C.分时系统让多个用户可以共享一台主机的运算能力，为保证每个用户都得到及时的响应通常会采用时间片轮转调度的策略。MCO9HiP8V0 D.为了方便上层应用程序的开发，操作系统都是免费开源的。)a&D,K0 4、关于计算机网络，下面的说法哪些是正确的：#xbl7;f,c,0 A）网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方案。/jTP5V d K0 B）新一代互联网使用的IPv6标准是IPv5标准的升级与补充。红旗中学网站/bb0v-%z*fC）TCP/IP是互联网的基础协议簇，包含有TCP和IP等网络与传输层的通讯协议。红旗中学网站8wM*FlsPYyjD）互联网上每一台入网主机通常都需要使用一个唯一的IP地址，否则就必须注册一个固定的域名来标明其地址。红旗中学网站nLDg2f,yD%z?kEv5、关于HTML下面哪些说法是正确的：红旗中学网站%TlV8b5M$f$mXR0JA）HTML全称超文本标记语言，实现了文本、图形、声音、乃至视频信息的统一编码。;I v5Dd7p Y0 B）HTML不单包含有网页内容信息的描述，同时也包含对网页格式信息的定义。红旗中学网站.qkOgn ttC）网页上的超链接只能指向外部的网络资源，本网站网页间的联系通过设置标签来实现。红旗中学网站5d0c*T!kK!TkV; OD）点击网页上的超链接从本质上就是按照该链接所隐含的统一资源定位符（URL）请求网络资源或者网络服务。a/pZL#Oi0 6、若3个顶点的无权图G的邻接矩阵用数组存储为0，1，11，0，10，1，0，假定在具体存储中顶点依次为：v1，v2，v3 关于该图，下面的说法哪些是正确的：红旗中学网站i!nenHX)x+uA）该图是有向图。B z/V6y0J0 B）该图是强联通的。红旗中学网站X(D59lSLkGC）该图所有顶点的入度之和减所有顶点的出度之和等于1。红旗中学网站A pb0Ao%? e%GD）从v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。红旗中学网站rH:DxLMM+U7、在带尾指针（链表指针clist指向尾结点）的非空循环单链表中每个结点都以next字段的指针指向下一个节点。假定其中已经有了2个以上的结点。下面哪些说法是正确的：Im(T15L A0 A）如果p指向一个待插入的新结点，在头部插入一个元素的语句序列为：红旗中学网站2B lO as7H p.next:=clist.next;clist.next:=p;Q0nXR)uGW l-O0 B）如果p指向一个待插入的新结点，在尾部插入一个元素的语句序列为：红旗中学网站Gm$4p$ z&E!O$lp.next:=clist;clist.next:=p;,g5q5cT-Ue0 C）在头部删除一个结点的语句序列为：红旗中学网站Kdx*c5|p:=clist.next;clist.next:=clist.next.next;dispose(p);红旗中学网站Gf5k j d.zwD）在尾部删除一个结点的语句序列为：r)V4K6N a0 p:=clist;clist:=clist.next;dispose(p);-y gIp$R/Y)jB0Z1v0 8、散列表的地址区间为0-10，散列函数为H(K)=K mod 11。采用开地址法的线性探查法处理冲突，并将关键字序列26，25，72，38，8，18，59存储到散列表中，这些元素存入散列表的顺序并不确定。假 定之前散列表为空，则元素59存放在散列表中的可能地址有：3w.FEfQ8f0 A）5 B）7 C）9 D）106xu3Qw.V|?;R%x0 9、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪些排序算法是稳定的：红旗中学网站 b C C /s)L8YE/h.AA）插入排序 B）基数排序 C）归并排序 D）冒泡排序tH5_)S4x9V0 10、在参加NOI系列竞赛过程中，下面哪些行为是被严格禁止的：ku aVW+a h3o00 A）携带书写工具，手表和不具有通讯功能的电子词典进入赛场。红旗中学网站G.t9i ? EBB）在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。G6B)yn1XY0 C）通过互联网搜索取得解题思路。h.qZA D8IC0 D）在提交的程序中启动多个进程以提高程序的执行效率。红旗中学网站+IX#O!uR v三.问题求解（共2题，每空5分，共计10分）红旗中学网站-MJPgh L6A1.拓扑排序是指将有向无环图G中的所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若E(G)，则u在线性序列中出现在v之前，这样的线性序列成为拓扑序列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为_。红旗中学网站Z p P/Ms红旗中学网站/|t0TLs红旗中学网站e!t1cJ5_2、某个国家的钱币面值有1，7，72，73共计四种，如果要用现金付清10015元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通_张钱币。红旗中学网站 T?9G11:OEK x anM01%pM s(0 四.阅读程序写结果（共4题，每题8分，共计32分）rf8hu0hug0 1./x9cK!s?L z0 varR)kCo m6IN0 a,b:integer;红旗中学网站T9zaAk _pmfunction work(a,b:integer):integer;$?r32?.u0 begin红旗中学网站%W2ZGKQ S6if a mod b 0 then5ctKF u2d0 work := work(b,a mod b)红旗中学网站y(o%G-t Pelse红旗中学网站 R p9? yx work := b;红旗中学网站-w-q-J)L $9r2Dend;红旗中学网站 z&Ay x,a l-p1cbegin红旗中学网站 g;ZqQ EK Nread(a,b);2HL xTz,K%I&i0 writeln(work(a,b);7M B7Go0 end.输入：123 321红旗中学网站5w2ly2B*h L%:o7G输出：_红旗中学网站pbk f,_4sn!T u2.红旗中学网站C/S*Q+xjE4WKs0Kzvar红旗中学网站4M6R(Z B/wQka,b:array0.3of integer;9Rt JEz4?0 i,j,tmp:integer;c4P _,PZx0 beginF9TQ oT0 for i := 0 to 3 dogC H3qq,z;J ?Yi rs)0 read(bi);.P cv b7L;W1zo0 for i := 0 to 3 do红旗中学网站c.Is?t, lZ&n& begin!P!Q8O!s7M&z0 ai := 0;红旗中学网站 x(On!| z rmbJ for j := 0 to i doA G D*baY0gOp0 begin6E9v3p r,A_1h0 inc(ai,bj);)+r-MUN0 inc(bai mod 4,aj);红旗中学网站A.ED S5cLE$KL5Ig end;5g S1A0 end;红旗中学网站I*P,W3L,hS|4Qtmp:=1;红旗中学网站6KMC WT/u#rG_,Nfor i := 0 to 3 dozRD/gfBuV/Q T0 begin红旗中学网站48E1Jip ai := ai mod 10;红旗中学网站hVJi/F(VhX bi := bi mod 10;红旗中学网站(_wS.p+By1o z tmp := tmp * (ai + bi);红旗中学网站-gN4Ba*lend;Z7gp|Ihul.Y0 writeln(tmp);)L gi-MV3p0 end.&FT%H)N0 输入：2 3 5 7红旗中学网站zIFe( dQ%aSH4输出：_红旗中学网站RD U3z&dT!Q0Cu;c红旗中学网站S$S!c4w)j#|3.红旗中学网站!dbq f5R#N I)h|Y1)pWconstw.Uq$aq A&b2(d0 y = 2009;Q5H?h(J)10 maxn = 50;红旗中学网站EJ,X+Hv-b3_7vvarlt9kmbA-w,v0 n,i,j,s:longint;红旗中学网站+q u7Da C(_c:array0.maxn,0.maxnof longint;红旗中学网站6_fr gh+L gXbegin红旗中学网站sz1K h4u-.F$Ds := 0;ap L7?,E0d0 read(n);8L|It-S0 c0,0 := 1;红旗中学网站lxh$+qfor i := 1 to n dof i$c W k|)t)v0 begin红旗中学网站 i+A3p2f$o+k ci,0 := 1;红旗中学网站v/) xR-He*T2q for j := 1 to i - 1 do红旗中学网站!VI-aH#n ci,j := ci-1,j-1 + ci-1,j;$eY|d-LM0 ci,i := 1;:ekS9aW0 end;红旗中学网站 e9uUc5LG6Pfor i := 0 to n do红旗中学网站)t*K*Ge:lH e s := (s + cn,i) mod y;红旗中学网站y3M?t:twrite(s);YN+GUYSA0 end.ddTVa7Q I#r0 输入：170uQ;&s pIe,-D0 输出：_1H#KXe O&G!)BHQ:Go0 4.?M-?v7 l0 var4w(pkKt 0 n,m,i,j,k,p:integer;红旗中学网站x/mA(D0a,b:array0.100of integer;&E5A )A)dq7e0 begin红旗中学网站 fp;A&Jf fWCuread(n,m);红旗中学网站 s.U, w(pZ3T/ta0 := n;红旗中学网站_5L9wCqji := 0;红旗中学网站f gyA*uH$r8kp := 0;EJJu OT2L0 k := 0;红旗中学网站 J)|.o9C5V.vrepeat红旗中学网站wf UvWC/FZ for j := 0 to i - 1 do7onU2yh#E0 if ai = aj then红旗中学网站:#ul4mYHBP begin+KDUH| 0 p := i;红旗中学网站)zx2t9qZn K k := j;E PN!E5HU?0 break;%Ro4I&e5s0 end;红旗中学网站ao9EOC if p 0 then红旗中学网站#c il7AH-t break;红旗中学网站yd*W pm8G:JP+p bi := ai div m;KshL4rNA90 ai+1 := (ai mod m) * 10;h WE FPU%l0 inc(i);红旗中学网站_L2IZauntil ai = 0;红旗中学网站gm V P ?write(b0,.);nu,V0h4BrQs0 for j := 1 to k - 1 do7OP!R4YHH)p0 write(bj);+x5tm0 if p 0 then? c1QLP0 write();红旗中学网站8e$K?|)f:|9w1r+zfor j := k to i - 1 do红旗中学网站8J?yF2d2R write(bj);红旗中学网站?WP)#ry Ffs bif p 0 then红旗中学网站1M5fR9p)OE oF write();v;lUC%I2o0 writeln;红旗中学网站z1R h2oaqc|Wend.? AN.m+6t#lK0 输入：5 13红旗中学网站bzmTC+B,_Cp输出：_+Xkg0 五.完善程序（前5空，每空2分，后6空，每空3分，共28分）红旗中学网站KL(T&D_W1.（最大连续子段和）给出一个数列（元素个数不多于100），数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列，使得这个子数列中 包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为 4，-5，3，2，4时，输出9和3；数列为1 2 3 -5 0 7 8时，输出16和7。红旗中学网站q5s$#wlvvar红旗中学网站UEauJ2wa:array1.100 of integer;4k2qylBS1zY o0 n,i,ans,len,tmp,beg:integer;红旗中学网站#k,u9U D!LmwEbegin红旗中学网站X#T|vPf8read(n);vx.V!X*d4i0 for i := 1 to n do红旗中学网站!G,yZ4a/tUWy_d read(ai);红旗中学网站 ?5fAy/K-CKtmp := 0;.b.Z2F2AW ;?;z0 ans := 0;红旗中学网站1Hq A+x:Slen := 0;红旗中学网站8l7u;u1S:| |4l|beg :=_;红旗中学网站D5GTz,OtPfor i := 1 to n dohBxQ5O&W; R0 begin红旗中学网站2A BR3 E if tmp + ai ans thenG2C4Y-Bc -e K0 beginU0h0X Ij1Yab0 ans := tmp + ai;红旗中学网站jJ M+v1xz!L len := i - beg;红旗中学网站3xrvQ S end红旗中学网站9v&W%LfYK0R else if (_) and (i - beg len) thenswc|L*B0 len := i - beg;红旗中学网站,I/d2PLcJfF$| if tmp + ai _ then红旗中学网站FTiR*g0XlL H begin红旗中学网站$6l!InA beg := _;l6i:fR Mdnm9aO0 tmp := 0;红旗中学网站9F4uQR!u2r8rMs n C end3 XV/h#/jO0 else红旗中学网站/Uu x*WRT _;.m6J d V0 end;红旗中学网站TR F2l w?%DH5writeln(ans, ,len);)G%ia)o?;q6Izp0 end.红旗中学网站knFW7M2.（寻找等差数列）有一些长度相等的等差数列（数列中每个数都为059的整数），设长度均为L，将等差数列中的所有数打乱顺序放在一起。现在给 你这些打乱后的数，问原先，L最大可能为多大？先读入一个数n（1=n maxnum then红旗中学网站J Nlgcabegin红旗中学网站4(b,PRsYvf work := true;红旗中学网站e:eaS2a7xJkJ exit;红旗中学网站 q2JPtend;红旗中学网站i/oX)u2Ae)Hk)first := now;红旗中学网站 mJ/Sa%Vfor second := first to maxnum do红旗中学网站vDj9|B? if hashsecond 0 then红旗中学网站yT+iaMg E begin红旗中学网站Jj0l)c:O4H delta :=_;红旗中学网站e9_AxE| if first + delta * _ maxnum then红旗中学网站b pa*k%K8Q$w5a-C break;红旗中学网站5i5e!:l9R_ Z0Qa if delta = 0 then0i/aZz3I0df0PVG 0 ok := (_)4r0g6c&tadJ9t7:Ty0 else红旗中学网站+NwH-g/d beginD iN%t O%b1G0 ok := true;红旗中学网站)vF4s L)5Ch for i := 0 to ans - 1 do红旗中学网站RA(wL6ut+v ok :=_ and (hashfirst+delta*i0);红旗中学网站1G-Ip Xf(J end;红旗中学网站!V it?;p if ok then红旗中学网站N!q!wd(P W begin6Y(D3Yd-_ r#qnt0 for i := 0 to ans - 1 do!p3H Cb?W 8XRq0 dec(hashfirst+delta*i);红旗中学网站&nT%dY(x/I4z?x&R if work(first) then红旗中学网站za5M,ib begin/KciT52G0 work := true;#r 6G$X JH$D0 exit;红旗中学网站 k C end;)WFmP.0 for i := 0 to ans - 1 do红旗中学网站&xX*P%gi5A3S inc(hashfirst+delta*i);g w6P%j;n3$?6Iy:IX0 end;红旗中学网站t9_1e2?R!Lv end;红旗中学网站b9V5 kR.uwork := false;红旗中学网站I(K*Jryend;2bvAl2#b9h$IXg kx0 begin:H0R-(Y*o90 fillchar(hash,sizeof(hash),0);K0O5q1%s2-q!s0 read(n);红旗中学网站Ds-%fYmaxnum := 0;红旗中学网站Hih-Xe2iB4nfor i := 1 to n do(g TMH11d q7e0 begin红旗中学网站 tW x y.d y6O2r)L read(x);(pDCsK;Zo0 inc(hashx);红旗中学网站A_%h+?pZ)/HP if x maxnum then#SV%jOW0 maxnum := x;k FWn 5uL_!?zr0 end;7|P:R0 for ans := n downto 1 do$Z,xX 0 if (n mod ans = 0) and _ theniyFZ.R.j V d)d0 begin红旗中学网站1C(#