当前位置:首页 >> >>

NOIP2008提高组初赛 pascal 试题+答案

第十四届全国青少年信息学奥林匹克联赛初赛试题
( 提高组 Pascal 语言 二小时完成 )

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

每题有且仅有一个正确答案) 一、 单项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题有且仅有一个正确答案) 。 1. 在以下各项中, )不是操作系统软件。 ( A. Solaris Symbian ) 。 C. 存储 B. Linux C. Sybase D. Windows Vista E.

2.微型计算机中,控制器的基本功能是( A. 控制机器各个部件协调工作 各种控制信息 D. 获取外部信息

B. 实现算术运算和逻辑运算 E. 存放程序和数据

3. 设字符串S=”Olympic”,S的非空子串的数目是( )。 A. 29 B. 28 C. 16 D. 17 ) 。 D. 2N-1 E. N/2 E. 7

4.完全二叉树共有 2*N-1 个结点,则它的叶节点数是( A. N-1 B. 2*N C. N

5.将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列,每 次可以交换任意两个元素,最少需要交换( A. 4 B. 5 C. 6 )次。 D. 7 E. 8

6.设栈 S 的初始状态为空,元素 a,b,c,d,e,f 依次入栈 S,出栈的序列为 b,d,c, f,e,a,则栈 S 的容量至少应该是( A. 6 B. 5 ) 。 C. 4 D. 3 E. 2

7. 与十进制数 28.5625 相等的四进制数是( ) 。 A. 123.21 130.20 8. 递归过程或函数调用时,处理参数和返回地址,通常使用一种称为()的数据结构。 A. 队列 栈 B. 多维数组 C. 线性表 D. 链表 E. B. 131.22 C. 130.22 D. 130.21 E.

9. TCP/IP 是一组构成互联网基础的网络协议, 字面上包括两组协议: 传输控制协议 (TCP) 和网际协议(IP) 。TCP/IP 协议把 Internet 网络系统描述成具有四个层次功能的网络 模型,其中提供源节点和目的节点之间的信息传输服务,包括寻址和路由器选择等功能的是 () 。 A. 链路层 会话层 10. 对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查 找,等概率的情况下查找成功的平均查找长度(平均比较次数)是( A. 35/11 34/10 二、 不定项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题正确答案的个数大于或等 于 1。多选或少选均不得分) 。多选或少选均不得分) 。 11. 在下列关于图灵奖的说法中,正确的有( 献的个人 B. 图灵奖有“计算机界诺贝尔奖”之称 C. 迄今为止,还没有华裔计算机科学家获此殊荣 D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵 12.计算机在工作过程中,若突然停电, ( A. 硬盘 B. CPU C.ROM )中的信息不会丢失。 D. RAM )。 B. 34/11 C. 33/11 ) 。 E. B.网络层 C. 传输层 D. 应用层 E.

D. 32/11

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

13. 设A=true,B=false,C=true,D=false,以下逻辑运算表达式值为真的有( )。 A. (A∧B)∨(C∧D∨ ? A) C. (B∨C∨D)∨D∧A B. (( ? A∧B)∨C)∧ ? D D. A∧(D∨ ? C)∧B )

14. Web2.0 是近年来互联网的热门概念之一, 其核心思想是互动与分享。 下列网站中, ( 是典型的 Web2.0 应用。 A. Sina B. Flickr C. Yahoo D. Google

15. (2008)10 + (5B)16 的结果是( ) 。 A. (833)16 (100001100011)2 16. 二叉树 T,已知其先根遍历是 1 2 4 3 5 7 6(数字为结点的编号,以下同) ,后根 遍历是 4 2 7 5 6 3 1,则该二叉树的可能的中根遍历是( ) 。 B. (2099)10 C. (4063)8 D.

A. 4 2 1 7 5 3 6 C. 4 2 1 7 5 6 3

B. 2 4 1 7 5 3 6 D. 2 4 1 5 7 3 6

17. 面向对象程序设计(Object-Oriented Programming)是一种程序设计的方法论, 它将对象作为程序的基本单元,将数据和程序封装在对象中,以提高软件的重用性、灵活性 和扩展性。下面关于面向对象程序设计的说法中,正确的是( A. 面向对象程序设计通常采用自顶向下设计方法进行设计。 B. 面向对象程序设计方法具有继承性(inheritance) 、封装性(encapsulation) 、 多态性(polymorphism)等几大特点。 C. 支持面向对象特性的语言称为面向对象的编程语言,目前较为流行的有 C++、JAVA、 C#等。 D. 面向对象的程序设计的雏形来自于 Simula 语言,后来在 SmallTalk 语言的完善和 标准化的过程中得到更多的扩展和对以前思想的重新注解。至今,SmallTalk 语言仍然被 视为面向对象语言的基础。 18. 设 T 是一棵有 n 个顶点的树,下列说法正确的是( A. T 是连通的、无环的 C. T 是无环的,有 n-1 条边 )。 C. free pascal D. ) 。 ) 。

B. T 是连通的,有 n-1 条边 D. 以上都不对

19. NOIP竞赛推荐使用的语言环境有( A. Dev-C++ Lazarus

B. Visual C++

20. 在下列防火墙(firewall)的说法中,正确的有( 过

)。

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

城市1

城市2

城市3

城市4

城市5

城市6

城市1 城市2 城市3 城市4 城市5 城市6

0 2 3 1 12 15

2 0 2 5 3 12

3 2 0 3 6 5

1 5 3 0 7 9

12 3 6 7 0 2

15 12 5 9 2 0

2.书架上有 21 本书,编号从 1 到 21,从其中选 4 本,其中每两本的编号都不相邻的 选法一共有______种。 四.阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 阅读程序写结果(

1. var i,a,b,c,d:integer; f:array[0..3] of integer; begin for i:=0 to 3 do read(f[i]); a := f[0] + f[1] + f[2] + f[3]; a := a div f[0]; b := f[0] + f[2] + f[3]; b := b div a; c := (b * f[1] + a) div f[2]; d := f[(b div c) mod 4]; if (f[(a + b + c + d) mod 4] > f[2]) then begin a := a + b; writeln(a); end else begin c := c + d; writeln(c); end; end.

输入:9 19 29 39 输出:_______________

2.procedure foo(a,b,c:integer); begin if a>b 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.

输入:2 1 3 输出:__________ 3.procedure f(a,b,c:integer);
begin write(a, b, c, '/'); if (a = 3) and (b = 2) and (c = 1) then exit; if b<c then f(a,c,b) else if a<b then if a<c then f(c,a,b) else f(b,c,a); end;

var a,b,c:integer; begin read(a, b, c); f(a,b,c);

end. 输入: 1 3 2 输出: ________________________________________

4. var s:string; i,j,len,k:integer;

begin read(s); len:=length(s); for i:=1 to len do if (ord(s[i]) >= ord('A')) and (ord(s[i]) <= ord('Z')) then s[i] := chr(ord(s[i]) - ord('A') + ord('a')); for i:=1 to len do if (ord(s[i])<ord('x')) then s[i]:= chr(ord(s[i])+3) else s[i]:= chr(ord(s[i])-23); write(s); write('/'); for j:=1 to 3 do begin i:=1; while i<=len-j do begin s[i]:=s[i+j]; i:=i+j; end; end; writeln(s); end.

输入:ABCDEFGuvwxyz 输出:___________________________________________ 五.完善程序 (前 6 空,每空 3 分,后 5 空,每空 2 分,共 28 分) 前 1.(找第 k 大的数 给定一个长度为 1,000,000 的无序正整数序列,以及另一个数 找第 大的数) n(1<=n<=1000000),接下来以类似快速排序的方法找到序列中第 n 大的数(关于第 n 大 的数:例如序列{1,2,3,4,5,6}中第 3 大的数是 4) 。

var a:array[1..1000000] of integer; n,m,ans:integer;

procedure swap(var a,b:integer); var t:integer;

begin if (a <> b) 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(a[tmp],a[left]); value := i := left; j := right; while i<j do begin while (i<j) and ( if i<j then begin a[i] := a[j]; inc(i); end else break; while (i<j) and ( if i<j then begin a[j] := a[i]; dec(j); end else break; end; ④ if i<n then begin inc(i); exit(FindKth( if i>n then begin dec(i); exit( exit(i); end; ⑥ ⑤ ));end; ); end; ③ ) do inc(i); ② ) do dec(j); ① ;

var i:integer; begin

randomize; ans := -1; m:=5; for i:=1 to m do read(a[i]); read(n); ans:= FindKth(1,m,n); writeln(a[ans]); end.

2. 矩阵中的数字)有一个 n*n(1<=n<=5000)的矩阵 a, 对于 1<=i < n,1<=j<=n, (矩阵中的数字) 的数字 a[i,j] < a[i + 1,j] a[j,i] < a[j,i+1]。即矩阵中左右相邻的两个元素,右边 的元素一定比左边的大。上下相邻的两个元素,下面的元素一定比上面的大。给定矩阵 a 中的一个数字 k,找出 k 所在的行列(注意:输入数据保证矩阵中的数各不相同) 。

var n,k,answerx,answery:integer; a:array[1..5000,1..5000] of integer;

procedure FindKPosition; var i,j:integer; begin i:=n; j:=n; while j>0 do begin if a[n,j] < k then break; dec(j); end; ① while a[i,j]<>k do begin while ( while ( end; ④ ⑤ ② ③ ) and (i>1) do dec(i); ) and (j<=n) do inc(j);

end;

var i,j:integer; begin read(n); for i:=1 to n do for j:=1 to n do read(a[i,j]); read(k); FindKPosition; writeln(answerx, ' ', answery); end.

NOIP2008 年提高组(Pascal 语言)参考答案与评分标准 年提高组( 语言)
一、单项选择题: (每题 1.5 分) 1. C 6. D 2. A 7. D 3. B 8. E 4. C 9. B 5. B 10. C

二、 不定项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题正确答案的个 数大于或等于 1。多选或少选均不得分) 。 11. ABD 16. ABD 1.7 2.3060 四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. 23 (信心题) 2. 1,3,2 (简单递归) 3. 132/213/231/312/321/ (全排列) 4. defghijxyzabc/hfizxjaybcccc (字符串替换) 五.完善程序 (前 6 空,每空 3 分,后 5 空,每空 2 分,共 28 分) (说明:以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和 上机验证,不一定上报科学委员会审查) 1. ① a[left] ② a[j] < value (或 a[j] <= value) ③ a[i] > value (或 a[i] >= value) ④ a[i] := value; ⑤ i,right,n ⑥ FindKth(left, i, n) 2. ① inc(j); (或者 j := j+1;) ② a[i,j] > k ③ a[i,j] < k ④ answerx := i; ⑤ answery := j; 12. AC 17. BCD 13. BC 18. ABC 14. B 19. ACD 15. ABC 20. ABCD

三、问题求解: (共 2 题,每题 5 分,共计 10 分)


更多相关标签: