noip2008普及组初赛

第十四届全国青少年信息学奥林匹克联赛初赛试题（普及组Pascal语言二小时完成） 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效一、单项选择题 （共20题，每题1.5分，共计30 分。每题有且仅有一个正确答案.）。1微型计算机中，控制器的基本功能是（ ）。A. 控制机器各个部件协调工作B. 实现算术运算和逻辑运算C. 获取外部信息D. 存放程序和数据2. A=true， B=false C=true, D=false以下逻辑运算表达式值为真的是（）。A. （AAB） V （CADVA）B. （AAB） VC） ADc. （bVcVd） AdAad. aA （dVC） Ab3. 在下列关于图灵奖的说法中，不正确的是（ ）。A. 图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人B. 图灵奖有“计算机界诺贝尔奖”之称C. 迄今为止，还没有华裔计算机科学家获此殊荣D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰图灵4计算机在工作过程中，若突然停电（， ）中的信息不会丢失。A. ROM和 RAMB. CPUC.ROM D. RAM5. 完全二叉树共有2*N-1个结点，则它的叶节点数是（）。A. N-1B. NC. 2*ND. 2N-16. 在以下各项中，（ ）不是操作系统软件。A. Solaris B. LinuxC. Windows VistaD. Sybase7. 设栈S的初始状态为空，元素a, b, c, d, e, f依次入栈S,出栈的序列为b, d, f, e, c, a, 则栈S的容量至少应该是（）。A. 6B. 5C. 4D. 38. 与十进制数28.5625相等的四进制数是（ ）。A. 123.21B. 131.22C. 130.22D. 130.219. 设字符=Olympic”，S的非空子串的数目是（）。A. 28 B. 29C. 16D. 1710. Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中，）是典型 的 Web2.0 应用。A. SinaB. FlickrC. YahooD. Google11. 递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（）的数据结构。A. 队列B. 多维数组C. 线性表D. 栈12. (2008)10 +（5B）16的结果是（16）。A. (833)16B. (2089)10C. (4163)8D. (100001100011)213.二叉树T,已知其先根遍历是L 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, 16, 77, -5, 53, 100中的元素按从大到小的顺序排列，每次可以交换 任意两个元素，最少需要交换（ ）次。A. 4B. 5C. 6D. 715. 对有序数组5, 13, 19, 21, 37, 56, 64, 75, 8，892， 100进行二分查找，成功查找 元素1 9的查找长度（比较次数）是（ ）。A. 1B. 2C. 3D. 416. 面向对象程序设计Object-Oriented Programming是一种程序设计的方法论，它将对象 作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。下面关于 面向对象程序设计的说法中，不正确的是（ ）。A. 面向对象程序设计通常采用自顶向下设计方法进行设计。B. 面向对象程序设计方法具有继承性（inheritance）、封装性（encapsulation）多态性 （polymorphism等几大特点。C. 支持面向对象特性的语言称为面向对象的编程语言，目前较为流行的有、JAVA、C#等。D. 面向对象的程序设计的雏形来自于Simula语言，后来在SmallTalk语言的完善和标准化的过 程中得到更多的扩展和对以前思想的重新注解。至今SmallTalk语言仍然被视为面向对象语言的基 础。17. 在32*32点阵的“字库”中，汉字“北”与“京”的字模占用字节数之和是（。A. 512B. 256C. 384D. 12818. 设T是一棵有n个顶点的树，下列说法不正确的是（）。A. T有n条边B. T是连通的C. T是无环的D. T有n-1条边19. 下列不属于NOIP竞赛推荐使用的语言环境的是（）。A.Dev-C+B. VisualC+C. freepascalD. Lazarus20. 在PASCAL程序中，表达式200 or 10 的值是（）A. 20B. 1C. 220D. 202二. 问题求解（共2题，每题5分，共计10分）1. 书架上有4本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这!本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_J申。满足A必须比C靠左，所有红皮的书要摆放在 一起，所有黑皮的书要摆放在一起，共_有种摆法。2. 有6个城市，任何两个城市之间都有一条道路连接6，个城市两两之间的距离如下表所示，则城市1 到城市6 的最短距离为。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920三. 阅读程序写结果（共4题，每题8分，共计32分）1. vari,a,b,c,d:integer; f:array0.3 of integer;beginfor i:=0 to 3 doread(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 4 f2) thenbegina := a + b;writeln(a);end elsebeginc := c + d;writeln(c);end;end.输入：9 19 29 39输出：2procedure foo(a,b,c:integer);beginif ab then foo(c,a,b)else writeln(a, , b, , c);end;vara,b,c:integer;beginread(a, b, c);foo(a,b,c);end.输入: 3 1 2输出: 3typeTT= array0.20of integer;procedure func(var ary:TT; n:integer);vari,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 then begin root_m:=i;break;m,root_m-1);m+1,epos_m);end;solve(first,spos_f+1,spos_f+(root_m-spos_m),mid,spos solve(first,spos_f+(root_m-spos_m)+1,epos_f,mid,root write(firstspos_f);end;varfirst,mid:string;len:integer;beginreadln(len);readln(first);readln(mid);solve(first,1,len,mid,1,len);writeln;end.输入： 7ABDCEGFBDAGECF输出：四完善程序(前4空，每空2.5分，后6空，每空3分，共28分)1.(字符串替换)给定一个字符串s(S仅包含大小写字母)，下面的程序将S中的每个字母用规定的 字母替换，并输出S经过替换后的结果。程序的输入是两个字符串，第一个字符串是给定的字符串 第二个字符串S由26个字母组成，它是a-z的任一排列，大小写不定,S规定了每个字母对应的替 换字母：S中的第一个字母是字母和a的替换字母，即S中的A用该字母的大写替换,S中的a用 该字母的小写替换；中的第二个字母是字坯和b的替换字母，即S中的B用该字母的大写替换,S 中的b用该字母的小写替换；以此类推。varchange:string;str:string;procedure CheckChangeRule;vari:integer;beginfor i:=1 to 26 do beginif thenchangei:= chr(ord(changei) - ord(A) + ord(a);end;end;procedure ChangeString;varlen,i:integer;beginlen := length(str);for i:=1 to len do beginif thenbeginstri := upcase(changeord(stri- ord(A) + 1);endelsebeginend;end;end;beginreadln(str);readln(change);CheckChangeRule;writeln(str);end.2. (找第 k 大的数) 给定一个长度为 1,000,000 的无序正整数序列 , 以及另一个数 (1=n=1000000),然后以类似快速排序的方法找到序列中第大的数(关于第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:integer;beginif (a b) then begina;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 : =;left;j := right;while ij dobeginwhile (ij) and ( ) do dec(j);if ij then beginai := 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); exi) ; end;exit(i);end;vari:integer;beginrandomize;endm:=1000000;for i:=1 to m do read(ai);read(n);ans:= FindKth(1,m,n);writeln(aans);