1、第十四届全国青少年信息学奥林匹克联赛pascal初赛试题及答案第十四届全国青少年信息学奥林匹克联赛初赛试题 （ 普及组 Pascal语言 二小时完成 ） 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 一、单项选择题（共20题，每题1.5分。每题有且仅有一个正确答案。） 1微型计算机中，控制器的基本功能是（ ）。 A控制机器各个部件协调工作 B实现算术运算和逻辑运算 C获取外部信息 D存放程序和数据 2设A=True，B=False，C=True，D=False，以下逻辑运算表达式值为真的是（ ）。 A(AB)(CDA) B(AB) C)D C(BCD) DA DA（DC）B 3在下列关
2、于图灵奖的说法中，不正确的是（ ）。 A图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人 B图灵奖有“计算机界诺贝尔奖”之称 C迄今为止，还没有华裔计算机科学家获此殊荣 D图灵奖的名称取自计算机科学的先驱、英国科学家阿兰图灵 4计算机在工作过程中，若突然停电，（ ）中的信息不会丢失。 AROM 和 RAM BCPU CROM DRAM 5完全二叉树共有2*N-1个结点，则它的叶节点数是（ ）。 AN-1 BN C2*N D2N-1 6在以下各项中，( ）不是操作系统软件。 ASolaris BLinux CWindows Vista DSybase 7设栈S
3、的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（ ）。 A6 B5 C4 D3 8与十进制数28.5625相等的四进制数是（ ）。 A123.21 B131.22 C130.22 D130.21 9设字符串S=”Olympic”，S的非字串的数目是（ ）。 A28 B29 C16 D17 10Web2.0 是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中，（ ）是典型的Web 2.0应用。 ASina BFlicker CYahoo DGoogle 11递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（
4、 ）的数据结构。 A队列 B多维数组 C线性表 D栈 12(2008)10+(5B)16的结果是（ ）。 A（833）16 B（2089）10 C（4163）8 D（100001100011）2 13二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为节点的编号，下同），中根遍历2 4 1 5 7 3 6，则该二叉树的后根遍历是（ ）。 A4 2 5 7 6 3 1 B4 2 7 5 6 3 1 C7 4 2 5 6 3 1 D4 2 7 6 5 3 1 14将数组8，23，4，16，77，-5，53，100中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换（ ）次。
5、 A4 B5 C6 D7 15对有序数组 5，13，19，21，37，56，64，75，88，92，100进行二分查找，成功查找元素19的查找长度（比较次数）是（ ）。 A1 B2 C3 D4 16 面向对象程序设计（Object-Oriented Programming）是一种程序设计的方法论，它将对象作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。下面关于面向对象设计的说法中，不正确的是（ ) A面向对象程序设计通常采用自顶向下设计方法进行设计。 B面向对象程序设计方法具有继承性（inheritance）、封装性（encapsulation）、多态性 (p
6、olymorphism）等几大特点。 C支持面向对象特性的语言称为面向对象的编程语言，目前较为流行的有C+，JAVA，C# 等。 D面向对象的程序设计的雏形来自于Simula语言，后来在SmallTalk语言的完善和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今，SmallTalk语言仍然被视为面向对象语言的基础 17在32*32点阵的“字库”中，汉字“北”与“京”的字模占用字节数之和是（ ）。 A512 B256 C384 D128 18设T是一棵有n个顶点的树，下列说法不正确的是（ ）。 AT有n条边 BT是连通的 CT是无环的 DT有n-1条边 19下列不属于NOIP竞赛推荐使
7、用的语言环境的是（ ）。 ADev-C+ BVisual C+ CFree Pascal DLazarus 20在Pascal程序中，表达式（200 or 10）的值是（ ）。 A20 B1 C220 D202 二、问题求解（共2题，每题5分，共计10分） 1书架上有4本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_种。满足A必须比C靠左，所有红皮的书要摆在一起，所有黑皮的书要摆放在一起，共有_种摆法。 2有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为_。 城市
8、1 城市2 城市3 城市4 城市5 城市6 城市1 0 2 3 1 12 15 城市2 2 0 2 5 3 12 城市3 3 2 0 3 6 5 城市4 1 5 3 0 7 9 城市5 12 3 6 7 0 2 城市6 15 12 5 9 2 0 三、阅读程序写结果（共4题，每题8分，共计32分） 1VAR i,a,b,c,d:integer; f:array0.3 of integer; BEGIN for i:=0 to 3 do read(fi); a:=f0+f1+f2+f3; a:=a div f0; b:=f0+f2+f3; b:=b div a; c:=(b*f1+a) div
9、f2; d:=f(b div c) mod 4; if (f(a+b+c+d) mod 4f2) then begin a:=a+b; writeln(a); end else begin c:=c+d; writeln(c); end; END. 输入：9 19 29 39 输出：_ 2procedure foo(a,b,c:integer); begin if ab then foo(c,a,b) else writeln(a,b,c); end; var a,b,c:integer; begin read(a,b,c); foo(a,b,c); end. 输入：3 1 2 输出：_ 3t
10、ype TT=array0.20of integer; prodecure func(var ary:TT;n:integer); var i,j,x:integer; begin i:=0;j:=n-1; while ij do begin while (i0) do inc(i); while (ij) and (aryj0) do dec(j); if i epos_f then exit; for i:=spos_m to epos_m do if firstspos_f=midi then begin root_m:=i; break; end; solve(first,spos_f
11、+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; begin readln(len); readln(first); readln(mid); solve(first,1,len,mid,1,len); writeln; end. 输入：7 ABDCEGF BDAGECF 输出：_ 四完善程序（前四空
12、，每空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用该字母的小写替换； 以此类推。 Var change:string; Str:string; P
13、rocedure CheckChangeRule; Var i:integer; Begin for i:=1 to 26 do begin if _ then changei:=chr(ord(changei)-ord(A)+ord(a); end; end; Procedure ChangeString; Var len,i:integer; begin len:=length(str); for i:=1 to len do begin if _ then begin stri:=upcase(changeord(stri-ord(A)+1); end; else begin _ end
14、; end; end; begin readln(str); readln(change); CheckChangeRule; _ writeln(str); end. 2（找第k大的数）给定一个长度为1,000,000的无序正整数序列，以及另一个数n（1n1000000），然后以类似快速排序的方法找到序列中第n大的数（关于第n大的数：例如序列1，2，3，4，5，6中第3大的数是4。） VAR a:array1.1000000 of integer; n,m,ans:integer; Procedure swap(var a,b:integer); var t:integer; begin i
15、f (ab) then begin t:=a; a:=b; b:=t; end; end; function FindKth(left,right,n:integer):integer; var tmp,value,i,j:integer; begin if left=right then exit(left); tmp:=random(right-left)+left; swap(atmp,aleft); value:=_; i:=left; j:=right; while ij do begin while (ij) and (_) do dec(j); if ij then begin
16、ai:=aj; inc(i); end else break; while (ij) and (_) do inc(i); if ij then begin aj:=ai; dec(j); end else break; end; _ if in then begin dec(i); exit(_); end; exit(i); end; var i:integer; begin randomize; m:=1000000; for i:=1 to m do read(ai); read(n); ans:=FindKth(1,m,n); writeln(aans); end. NOIP2008
17、年普及组（Pascal语言）参考答案与评分标准 一、单项选择题：（每题1.5分） 1. A 2. B 3. C 4. C 5. B 6. D 7. C 8. D 9. A 10. B 11. D 12. A 13. B 14. B 15. B 16. A 17. B 18. A 19. B 20. D 二、问题求解：（共2题，每题5分，共计10分） 112 4 27(1-2-5-6) 三、阅读程序写结果（共4题，每题8分，共计32分） 1. 23 2. 2,3,1 3. 5 4 10 1 6 22 -59 -6 -11 -6 4. DBGEFCA （求树的后序遍历） 四完善程序 (前4空，每空2.5分，后6空，每空3分，共28分) （说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查） 1. (changei = A) and (changei = Z) (只写(changei = A) and (stri = Z) （只写stri = Z也对） stri := changeord(stri) - ord(a) +1; ChangeString; 2 aleft aj value (或aj value （或ai = value） ai := value; i,right,n FindKth(left, i, n)
