信息奥赛试题.doc

1、第十四届全国青少年信息学奥林匹克联赛初赛试题（ 提高组 Pascal 语言 二小时完成 ） 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 一、单项选择题（共 10 题，每题 1.5 分，共计 15 分。每题有且仅有一个正确答案）。1在以下各项中，（ ）不是操作系统软件。ASolaris BLinux CSybase DWindows Vista ESymbian2微型计算机中，控制器的基本功能是（ ）。A控制机器的各个部件协调工作 B实现算数运算与逻辑运算 C存储各种控制信息D获取外部信息 E存放程序和数据3设字符串 S=“Olympic”，S 的非空字串的数目是（ ）。A29 B28

2、 C16 D17 E74完全二叉树有 2*N-1 的结点，则它的叶子结点数目是（ ）。AN-1 B2*N CN D2N-1 EN/25将数组8， 23，4，16，77，-5，53，100中元素从大到小按顺序排序，每次可以交换任意两个元素，最少要交换（ ）次。A4 B5 C6 D7 E86设栈 S 的初始状态为空，元素 a，b，c，d ，e，f 依次入栈，出栈顺序为b，d，c，f，e，a 那么栈容量至少应该是（ ）。A6 B5 C4 D3 E27与十进制数 28.5625 相等的四进制数是（ ）A123.21 B131.22 C130.22 D130.21 E130.208递归过程和函数调用时，

3、处理参数和返回地址，通常使用一种称为（ ）的数据结构。A队列 B多维数组 C线性表 D链表 E栈9TCP/IP 是一组构成互联网基础的网络协议，字面上包括两组协议：传输控制协议（TCP）和网际互联协议（IP）。TCP/IP 协议把 Internet 网络系统描述成具有 4 个层次功能的网络模型，其中提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能的是（）。A链路层 B网络层 C传输层 D应用层 E会话层10对有序数组5,13,19,21,37,56,64,75,88,92,100进行二分查找，等概率情况下，查找成功的平均查找长度（平均比较次数）是（）。A35/11 B34/1

4、1 C33/11 D32/11 E34/10二、不定项选择题（共 10 题，每题 1.5 分，共计 15 分。每题正确答案的个数大于或等于1。多选或少选均不得分）。11下列关于图灵的说法正确的有（ ）。A图灵奖是美国计算机协会与 1966 年设立的，专门鼓励那些对计算机做出重要贡献的个人B图灵奖有“计算机界诺贝尔奖”之称。 C迄今为止，还没有华裔计算机科学家获此殊荣。D图灵奖的名称取自计算机科学先驱、英国科学家阿兰图灵。12计算机在工作过程中，若突然停电，（ ）中不会丢失信息不会丢失。A硬盘 BCPU CROM DRAM13若 A=True，B=False，C=True，D=False，以下逻

5、辑运算表达式真的有（ ）。A（AB）V（CDVA） B（AB）VC）B C（BVCVD）VDA DA （DVC）B14Web2.0 是近年来互联网热门概念之一，其核心是互动与分享。下列网站中，（ ）是典型的 Web2.0 的应用。ASina BFlickr CYahoo DGoogle15(2008)10+ (5B)16 的结果是（）。A（833）16 B（2099）10 C（4063）8 D（100001100011）216二叉树 T，已知其先序遍历是 1 2 4 3 5 7 6（数字为节点编号，以下同），后序遍历是 4 2 7 5 6 3 1，则该二叉树的中根遍历是（ ）A4 2 1 7

6、5 3 6 B2 4 1 7 5 3 6 C4 2 1 7 5 6 4 D2 4 1 5 7 3 617面向对象的程序设计（Object-Oriented Programming）是一种程序设计的方法论，它将对象作为程序设计的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性、和扩展性。下面关于面向对象的程序设计说法中正确的是（ ）。A面向对象的程序设计方法通常采用自顶向下的设计方法进行设计。B面向对象的程序设计方法具有继承性（inheritance ）、封装性（encapsulation ）、多态性（polymorphism）等几大特点。C支持面向对象特性称为面向对象的编程语言，

7、目前较为流行的有 C+，JAVA，C#等。D面向对象的程序设计的雏形来自于 Simula 语言，后来在 SmallTalk 语言的完善和标准化的过程中得到更多的扩展和对以前的思想的重新注解。至今，SmallTalk 语言仍然被视为面向对象的基础。18设 T 是一棵有 n 个定点的树，以下说法正确的是（ ）。AT 是联通的，无环的 BT 是联通的，有 n-1 条边CT 是无环的，有 n-1 条边 D以上都不对19NOIP 竞赛推荐使用的语言环境有（ ）。ADev-C+ BVisual C+ CFree Pascal DLazarus20在下列防火墙（Firewall）的说法中，正确的有（ ）。A

8、防火墙是一项协助确保信息安全的设备，其会依照特定的规则，允许或是限制数据通过B防火墙可能是一台专属硬件或是安装在一般硬件上的一套软件C网络层防火墙可以视为一种 IP 数据包过滤器，只允许符合特定规定的数据包通过，其余的一概禁止穿越防火墙D应用层防火墙是在 TCP/IP 的“应用层”上工作，可以拦截进出某应用程序的所有数据包三、问题求解（共 2 题，每题 5 分，共计 10 分）1有 6 个城市，任何两个城市之间有一条道路连接，6 个城市之间两两之间的距离如下表表示，则城市 1 到城市 6 的最短距离为_ 。城市 1 城市 2 城市 3 城市 4 城市 5 城市 6城市 1 0 2 3 1 12

9、 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 02书架上有 21 本书，编号从 1 到 21 从中选 4 本，其中每两本的编号都不相邻的选法一共有_种。四、阅读程序写结果（共 4 题，每题 8 分，共计 32 分）。1vari,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;c:=(b*f1+a) div

10、f2;d:=f(b div c) mod 4;if (f(a+b+c+d) mod 4f2) thenbegina:=a+b;writeln(a)endelsebeginc:=c+d;writeln(c);end;end.输入： 9 19 29 39输出：_2procedure foo(a,b,c:integer);beginif ab then foo(c,a,b)elsewriteln(a,b,c)end;var a,b,c:integer;beginreadln(a,b,c);foo(a,b,c);end.输入：2 1 3输出：_3procedure f(a,b,c:integer);b

11、eginwrite(a,b,c,/);if (a=3)and(b=2)and(c=1) then exit;if (b=ord(A) and (ord(si)b) then begint:=a; a:=b; b:=t;end;end;Function FindKth(left,right,n:integer):integer;Var tmp,value,i,j:integer;beginif left=right then exit(left);tmp:=random(right-left)+left;swap(atmp,aleft);value:=_i:=left; j:=right;whi

12、le in then begin dec(j); exit(_);end;exit(i);end;var i:integer;beginrandomize;ans:=-1;m:=5;for i:=1 to m doread(ai);read(n);ans:=FindKth(1,m,n);writeln(aans);end.2（矩阵中的数字）有一个 n*n（1n5000)的矩阵 a，对于 1i0 do beginif an,jk dobeginwhile (_) and (i1) do dec(i);while (_) and (j value （或 ai = value） ai := value; i,right,n FindKth(left, i, n) 2. inc(j); (或者 j := j+1;) ai,j k ai,j k answerx := i; answery :=j;