第十四届全国青少年信息学奥林匹克联赛普及组初赛试题.

1、第十四届全国青少年信息学奥林匹克联赛初赛试题(普及组Pascal语言二小时完成) 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 一、单项选择题(共 20 题，每题 1.5 分。每题有且仅有一个正确答案。 ) 1微型计算机中，控制器的基本功能是()。A. 控制机器各个部件协调工作B.实现算术运算和逻辑运算C.获取外部信息D.存放程序和数据2 .设A=True, B=False, C=True, D=False,以下逻辑运算表达式值为真的是()。A. (AA B) V (CA A)B. (AA B) V C)ADC. (BV CV D) A DA A D. AA( DVC)A B3 .在下

2、列关于图灵奖的说法中，不正确的是()。A 图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人B. 图灵奖有“计算机界诺贝尔奖”之称C. 迄今为止，还没有华裔计算机科学家获此殊荣D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰图灵4.计算机在工作过程中，若突然停电，( )中的信息不会丢失。A. ROM 和 RAMB. CPUC. ROMD. RAM5.完全二叉树共有A. N-12*N-1 个结点,则它的叶节点数是(B. NC. 2*N)。D. 2N-16.A.在以下各项中,Solaris( )不是操作系统软件。B. LinuxC. Windows Vist

3、aD. Sybase7.8.A.设栈S的初始状态为空，元素 a, c, a,则栈S的容量至少应该是(A. 6B. 5与十进制数 28.5625 相等的四进制数是123.21B. 131.22b，c, d, e, f依次入栈)。S,出栈的序列为b, d, f, e,C.C.）。130.22D. 3D. 130.219.A.设字符串S=Olympic”，S的非字串的数目是(28B. 29C.）。16D. 1710. Web2.0 是近年来互联网的热门概念之一， 其核心思想是互动与分享。 下列网站中，( ) 是典型的 Web 2.0 应用。A. SinaB. FlickerC. YahooD. Go

4、ogle11递归过程或函数调用时，处理参数和返回地址，通常使用一种称为()的数据结构。A.队列B.多维数组C.线性表D.栈12（2008）10+（5B）16 的结果是（）。C.（4163） 8D . （100001100011 ）2A . （833） 16B . （2089） 1013. 二叉树T,已知其先根遍历是 1 2 4 3 5 7 6 (数字为节点的编号，下同)，中根遍历2 4 1 5 7 3 6，则该二叉树的后根遍历是()。A. 4 2 5 7 6 3 1B. 4 2 7 5 6 3 1C. 7 4 2 5 6 3 1D. 4 2 7 6 5 3 114. 将数组 8， 23， 4，

5、 16， 77， -5， 53， 1 00中的元素按从小到大的顺序排列，每次可以交 换任意两个元素，最少需要交换( )次。A. 4B. 5C. 6D. 715. 对有序数组 5， 13， 19， 21， 37， 56， 64， 75， 88， 92， 100进行二分查找，成功查找元素 19 的查找长度(比较次数)是()。A. 1B. 2C. 3D. 416 .面向对象程序设计( Object-Oriented Programming )是一种程序设计的方法论，它将对 象作为程序的基本单元， 将数据和程序封装在对象中， 以提高软件的重用性、 灵活性和扩展 性。下面关于面向对象设计的说法中，不正确

6、的是()A. 面向对象程序设计通常采用自顶向下设计方法进行设计。B. 面向对象程序设计方法具有继承性(inheritanee )、圭寸装性(encapsulation )、多态性 (polymorphism )等几大特点。C. 支持面向对象特性的语言称为面向对象的编程语言，目前较为流行的有 C+, JAVA C#等。D. 面向对象的程序设计的雏形来自于Simula语言，后来在 SmallTalk语言的完善和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今，SmallTalk语言仍然被视为面向对象语言的基础17. 在 32*32 点阵的“字库”中,汉字“北”与“京”的字模占用字节数之和是

7、()。A. 512B. 256C. 384D. 12818. 设 T 是一棵有 n 个顶点的树,下列说法不正确的是()。A. T有n条边B. T是连通的C. T 是无环的D. T有n-1条边19下列不属于 NOIP竞赛推荐使用的语言环境的是()。A. Dev-C+B. Visual C+C. Free PascalD. Lazarus20.在Pascal程序中，表达式（200 or 10）的值是（）。A. 20B. 1C. 220D. 202二、问题求解(共 2 题,每题 5分,共计 10 分)1. 书架上有4本不同的书 A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这 4 本书摆在书

8、架上，满足所有黑皮的书都排在一起的摆法有 种。满足A必须比C靠左，所有红皮的书要摆在一起，所有黑皮的书要摆放在一起，共有种摆法。2 .有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为 。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3 ；320365城市4153079城市51236702城市615125920三、阅读程序写结果(共 4题，每题8分，共计32分)1. VAR i,a,b,c,d:integer;f:array0.3 of in teger;BEGINfor i:=0 to 3 dore

9、ad(fi);a:=f0+f1+f2+f3;a:=a div f0;b:=f0+f2+f3;b:=b div a;c:=(b*f1+a) div f2;d:=f(b div c) mod 4;if (f(a+b+c+d) mod 4f2) the nbegina:=a+b;writel n(a);end elsebeginc:=c+d; write In (c);en d;END.输入：9 19 29 39输出：2. procedure foo(a,b,c:integer);beginif ab the n foo(c,a,b) else writel n( a,b,c);en d;vara,

10、b,c:integer;beginread(a,b,c);foo(a,b,c);end.输入： 3 1 2输出： 3 typeTT=array0.20of integer;prodecure func(var ary:TT;n:integer);var i,j,x:integer;begini:=0;j:=n-1;while ij do beginwhile (i0) do inc(i);while (ij) and (aryj0) do dec(j);if i epos_f then exit;for i:=spos_m to epos_m doif firstspos_f=midi the

11、n beginroot_m:=i;break;end;solve(first,spos_f+1,spos_f+(root_m-spos_m),mid,spos_m,root_m-1); solve(first,spos_f+(root_m-spos_m)+1,epos_f,mid,root_m+1,epos_m);write(firstspos_f);end;var first,mid:string;len:integer;beginreadln(len);readln(first);readln(mid);solve(first,1,len,mid,1,len);writeln;end.输入

12、： 7ABDCEGFBDAGECF输出： 四完善程序(前四空，每空 2.5分，后 6空，每空 3分，共 28 分)1 .(字符串替换) 给定一个字符串 S( S仅包含大小写字母)，下面的程序将S中的每个字母 用规定的字母替换，并输出S经过替换后的结果。程序的输入是两个字符串，第一个字符串是给定的字符串S,第二个字符串S由26个字母组成，它是az的任一排列，大小写不定，S规定了每个字母对应的替换字母：S中的第一个字母是字母A和a的替换字母，即S中的A用该字母的大写替换，S中的a用该字母的小写替换；S中的第二个字母是字母B和b的替换字母，即S中的B用该字母的大写替换，S中的b用该字母的小写替换；以

13、此类推。Var change:string;Str:string;Procedure CheckChangeRule;Var i:integer;Beginfor i:=1 to 26 do beginif thenchangei:=chr(ord(changei)-ord(A)+ord(a);end;end;Procedure ChangeString;Var len,i:integer;beginlen:=length(str);for i:=1 to len do beginif thenbeginstri:=upcase(changeord(stri-ord(A)+1);end;els

14、ebegin end;end;end;beginreadln(str);readln(change);CheckChangeRule; writeln(str);end.n( 1 w n例如序2(找第 k 大的数) 给定一个长度为 1,000,000 的无序正整数序列，以及另一个数w 1000000)，然后以类似快速排序的方法找到序列中第n大的数(关于第n大的数:列1， 2， 3， 4， 5， 6中第 3 大的数是 4。)VARa:array1.1000000 of integer;n,m,ans:integer;Procedure swap(var a,b:integer);var t:in

15、teger;beginif (ab) then begint:=a; a:=b; b:=t;end;end;function FindKth(left,right,n:integer):integer;vartmp,value,i,j:integer;beginif left=right then exit(left);tmp:=random(right-left)+left;swap(atmp,aleft);value:= ;i:=left; j:=right;while ij do beginwhile (ij) and ( ) do dec(j);if ij then beginai:=

16、aj; inc(i);end else break;while (ij) and ( ) do inc(i);if ij then beginaj:=ai; dec(j);end else break;end; if in then begin dec(i); exit( ); end;exit(i);end;var i:integer;beginrandomize;m:=1000000;for i:=1 to m do read(ai);read(n);ans:=FindKth(1,m,n); writeln(aans);end.NOIP2008 年普及组（ Pascal 语言）参考答案与评

17、分标准（修正）一、单项选择题：（每题1.5 分）1. A2. B3. C4.C5. B6. D7. C8. D9.A10. B11. D12. A13. B14.B15. B16. A17. B18. A19.B20. D二、问题求解：（共 2 题，每题 5 分，共计 10 分）112 42 7（1-2-5-6）三、阅读程序写结果（共 4 题，每题 8 分，共计 32 分）1. 23 2. 2,3,13. 5 4 10 1 6 22 -59 -6 -11 -64. DBGEFCA （求树的后序遍历）四完善程序 （前 4 空，每空 2.5 分，后 6 空，每空 3 分，共 28 分 ） （说明：以下各程序