08年第十四届信息学奥赛初赛普及组.docx

08年第十四届信息学奥赛初赛普及组.docx

《08年第十四届信息学奥赛初赛普及组.docx》由会员分享，可在线阅读，更多相关《08年第十四届信息学奥赛初赛普及组.docx（12页珍藏版）》请在冰点文库上搜索。

08年第十四届信息学奥赛初赛普及组

第十四届信息学奥赛联赛普及组Pascal初赛题

                  （普及组 Pascal语言 二小时完成）

●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●

一、单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确答案.）。

 1．微型计算机中，控制器的基本功能是（  ）。

A.控制机器各个部件协调工作     B.实现算术运算和逻辑运算       

C.获取外部信息              D.存放程序和数据

 2.设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的是（ ）。

A.（A∧B）∨（C∧D∨A）         B.（（A∧B）∨C）∧D

C.（B∨C∨D）∧D∧A              D.A∧（D∨C）∧B

 3.在下列关于图灵奖的说法中，不正确的是（  ）。

A.图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人

B.图灵奖有“计算机界诺贝尔奖”之称

C.迄今为止，还没有华裔计算机科学家获此殊荣

D.图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵

 4．计算机在工作过程中，若突然停电，（   ）中的信息不会丢失。

A.ROM和RAM     B.CPU      C.ROM     D.RAM

 5．完全二叉树共有2*N-1个结点，则它的叶节点数是（  ）。

A.N-1        B.N          C.2*N       D.2N-1

 6.在以下各项中，（ ）不是操作系统软件。

A.Solaris     B.Linux           C.WindowsVista        D.Sybase

 7．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（  ）。

A.6          B.5          C.4           D.3

 8.与十进制数28.5625相等的四进制数是（ ）。

A.123.21      B.131.22       C.130.22      D.130.21

 9.设字符串S=”Olympic”，S的非空子串的数目是（ ）。

A.28    B.29      C.16           D.17

 10．Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享。

下列网站中，（  ）是典型的Web2.0应用。

 A.Sina        B.Flickr         C.Yahoo           D.Google

 11．递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（   ）的数据结构。

A.队列         B.多维数组        C.线性表            D.栈

 12. （2008）10+（5B）16的结果是（  ）。

A.（833）16      B.（2089）10        C.（4163）8         D.（100001100011）2

 13.二叉树T，已知其先根遍历是1243576（数字为结点的编号，以下同），中根遍历是2415736，则该二叉树的后根遍历是（  ）。

A.4257631          B.4275631 

C.7425631          D.4276531

 14．将数组{8,23,4,16,77,-5,53,100}中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（  ）次。

A.4           B.5          C.6           D.7

 15．对有序数组{5,13,19,21,37,56,64,75,88，92，100}进行二分查找，成功查找元素19的查找长度（比较次数）是（  ）。

A.1           B.2          C.3            D.4

 16.面向对象程序设计（Object-OrientedProgramming）是一种程序设计的方法论，它将对象作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。

下面关于面向对象程序设计的说法中，不正确的是（  ）。

A.面向对象程序设计通常采用自顶向下设计方法进行设计。

B.面向对象程序设计方法具有继承性（inheritance）、封装性（encapsulation）、多态性（polymorphism）等几大特点。

C.支持面向对象特性的语言称为面向对象的编程语言，目前较为流行的有C++、JAVA、C#等。

D.面向对象的程序设计的雏形来自于Simula语言，后来在SmallTalk语言的完善和标准化的过程中得到更多的扩展和对以前思想的重新注解。

至今，SmallTalk语言仍然被视为面向对象语言的基础。

 17.在32*32点阵的“字库”中，汉字“北”与“京”的字模占用字节数之和是（  ）。

 A.512         B. 256        C. 384         D.128

 18.设T是一棵有n个顶点的树，下列说法不正确的是（   ）。

A.T有n条边                    B.T是连通的

C.T是无环的                    D.T有n-1条边

 19.下列不属于NOIP竞赛推荐使用的语言环境的是（  ）。

A.Dev-C++         B.VisualC++          C.freepascal         D.   Lazarus

 20．在PASCAL程序中，表达式（200or10）的值是（  ）

 A.20        B.1           C.220        D.202

 二．问题求解（共2题，每题5分，共计10分）

 1.书架上有4本不同的书A、B、C、D。

其中A和B是红皮的，C和D是黑皮的。

把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_____种。

满足A必须比C靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有______种摆法。

 2．有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为_____________。

城市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分）

 1.var

    i,a,b,c,d:

integer;

    f:

array[0..3]ofinteger;

begin

    fori:

=0to3do

         read（f[i]）;

    a:

=f[0]+f[1]+f[2]+f[3];

    a:

=adivf[0];

    b:

=f[0]+f[2]+f[3];

    b:

=bdiva;

    c:

=（b*f[1]+a）divf[2];

    d:

=f[（bdivc）mod4];

    if（f[（a+b+c+d）mod4]>f[2]）then

    begin

        a:

=a+b;

        writeln（a）;

    endelse

    begin

        c:

=c+d;

        writeln（c）;

    end;

end.

输入：

9192939   

输出：

_______________

 2．procedurefoo（a,b,c:

integer）;

begin

    ifa>bthenfoo（c,a,b）

    elsewriteln（a,',',b,',',c）;

end;

 var

   a,b,c:

integer;

begin

    read（a,b,c）;

     foo（a,b,c）;

end.

 输入:

312

输出:

__________

 3．type

       TT=array[0..20]ofinteger;

procedurefunc（varary:

TT;n:

integer）;

var

       i,j,x:

integer;

begin

       i:

=0;j:

=n-1;

       whilei

            while（i0）doinc（i）;

            while（i

            ifi

                 x:

=ary[i];

                 ary[i]:

=ary[j];

                 ary[j]:

=x;

                 inc（i）;

                 dec（j）;

            end;

       end;

end;

 var

       a:

TT;

       i,m:

integer;

begin

       m:

=10;

       fori:

=0tom-1do

               read（a[i]）;

       func（a,m）;

       fori:

=0tom-1do

               write（a[i],''）;

       writeln;

end.

输入：

54-6-116-5922-6110

输出：

____________________________________

4.

proceduresolve（first:

string;spos_f,epos_f:

integer;mid:

string;spos_m,epos_m:

integer）;

var

   i,root_m:

integer;

begin

   ifspos_f>epos_fthenexit;

   fori:

=spos_mtoepos_mdo

     iffirst[spos_f]=mid[i]thenbegin

       root_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（first[spos_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

输出：

____________________________________

四．完善程序（前4空，每空2.5分，后6空，每空3分，共28分）

1．（字符串替换）给定一个字符串S（S仅包含大小写字母），下面的程序将S中的每个字母用规定的字母替换，并输出S经过替换后的结果。

程序的输入是两个字符串，第一个字符串是给定的字符串S，第二个字符串S’由26个字母组成，它是a-z的任一排列，大小写不定，S’规定了每个字母对应的替换字母：

S’中的第一个字母是字母A和a的替换字母，即S中的A用该字母的大写替换，S中的a用该字母的小写替换；S’中的第二个字母是字母B和b的替换字母，即S中的B用该字母的大写替换，S中的b用该字母的小写替换；……以此类推。

var

    change:

string;

    str:

string;

procedureCheckChangeRule;

var

       i:

integer;

begin

       fori:

=1to26dobegin

       if               ①                  then

                change[i]:

=chr（ord（change[i]）-ord（'A'）+ord（'a'））;

       end;

end;

procedureChangeString;

var

       len,i:

integer;

begin

       len:

=length（str）;

       fori:

=1tolendobegin

             if               ②                  then

             begin

                   str[i]:

=upcase（change[ord（str[i]）–ord（‘A’）+1]）;

             end

             else

             begin

                                     ③                     

             end;

       end;

end;

begin

       readln（str）;

     readln（change）;

       CheckChangeRule;

                     ④               

       writeln（str）;

end.

2.      （找第k大的数）给定一个长度为1,000,000的无序正整数序列,以及另一个数n（1<=n<=1000000）,然后以类似快速排序的方法找到序列中第n大的数（关于第n大的数：

例如序列{1，2，3，4，5，6}中第3大的数是4）。

var

   a:

array[1..1000000]ofinteger;

   n,m,ans:

integer;

procedureswap（vara,b:

integer）;

vart:

integer;

begin

    if（a<>b）thenbegin

         t:

=a;

         a:

=b;

         b:

=t;

    end;

end;

functionFindKth（left,right,n:

integer）:

integer;

var

       tmp,value,i,j:

integer;

begin

       ifleft=rightthenexit（left）;

       tmp:

=random（right-left）+left;

       swap（a[tmp],a[left]）;

       value:

=      ①     ;

       i:

=left;

       j:

=right;

       whilei

       begin

            while（i

            ifi

                 a[i]:

=a[j];inc（i）;

            endelsebreak;

            while（i

            ifi

                 a[j]:

=a[i];dec（j）;

            endelsebreak;

       end;

                  ④         

       ifi

       ifi>nthenbegindec（i）;exit（            ⑥              ）;end;

       exit（i）;

end;

var

     i:

integer;

begin

    randomize;

    m:

=1000000;

    fori:

=1tomdo

       read（a[i]）;

    read（n）;

    ans:

=FindKth（1,m,n）;

    writeln（a[ans]）;

end.