历届奥赛试题解析-初赛讲解(5)

省淳中信息学奥赛辅导 奥赛试题解析

B.军队发布命令

C.国际会议中，每个人都与他国地位对等的人直接进行会谈

D.体育比赛中，每一级比赛的优胜者晋级上一级比赛

11.矢量图（Vector Image）图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋

转等都不会失真，是因为它（ B ）。 A.记录了大量像素块的色彩值来表示图像

B.用点、直线或者多边形等基于数学方程的几何图元来表示图像

21

省淳中信息学奥赛辅导 奥赛试题解析

C.每个像素点的颜色信息均用矢量表示

D.把文件保存在互联网，采用在线浏览的方式查看图像

12.如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a，b，c，

另有元素d已经出栈，则可能的入栈顺序是（ D ）。 A.a, d, c, b B.b, a, c, d C.a, c, b, d D.d, a, b, c

13.（ B ）是主要用于显示网页服务器或者文件系统的HTML文件的内容，并让用户与这些文

件交互的一种软件。

A.资源管理器 B.浏览器 C.电子邮件 D.编译器 14.（ C ）是目前互联网上常用的E-mail服务协议。

A.HTTP B.FTP C.POP3 D.Telnet

15.（ C ）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更

小的子问题……直到最后的子问题可以简单地直接求解。而原问题的解就是子问题解的并。 A.动态规划 B.贪心 C.分治 D.搜索

16.地址总线的位数决定了CPU可直接寻址的内存空间大小，例如地址总线为16位，其最大的

可寻址空间为64KB。如果地址总线是32位，则理论上最大可寻址的内存空间为（ D ）。 A.128KB B.1MB C.1GB D.4GB 17.蓝牙和Wi-Fi都是（ C ）设备。

A.无线广域网 B.无线城域网 C.无线局域网 D.无线路由器 【分析】Wi-Fi：WirelessFidelity，标准发音为'wai.fai，无线保真 18.在程序运行过程中，如果递归调用的层数过多，会因为（ A ）引发错误。

A.系统分配的栈空间溢出 B.系统分配的堆空间溢出 C.系统分配的队列空间溢出 D.系统分配的链表空间溢出

19.原字符串中任意一段连续的字符所组成的新字符串称为子串。则字符“AAABBBCCC”共有

（ C ）个不同的非空子串。

A.3 B.12 C.36 D.45

【分析】包含1个字串即A、B、C共3个；包含2个字符即AA、AB、BB、BC、CC共5个；包含3个字符即共7个；包含4个字符即共6个；包含5个字符即共5个；……包含9个字符即共1个；3+5+7+6+5+5+3+2+1=36

20.仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，

并将这些原理移植于新兴的工程技术中。以下关于仿生学的叙述，错误的是（ B ） A.由研究蝙蝠，发明雷达 B.由研究蜘蛛网，发明因特网 C.由研究海豚，发明声纳 D.由研究电鱼，发明伏特电池

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

22

省淳中信息学奥赛辅导 奥赛试题解析

1. 如果平面上任取n个整点（横纵坐标都是整数），其中一定存在两个点，它们连线的中点也

是整点，那么n至少是___5___。 【分析】：平面上的点如同棋盘

（1）如果n=2，取两个连续的整点（例A、B），那么连线中点不是整点。

（2）如果n=3，取水平两个连续的点，垂直也两个连续的点，组成三角形。那么连线中点

不是整点。（例A、B、C）

（4）如果n=4，取四个整点组成一个正方形，则连线中点不是整点。（例A、B、C、F） （5）而取5个点的话，必然有两个点的连线中点是整点。（例A、B、C、D、E），CE两点的

中点是D。

2. 在NOI期间，主办单位为了欢迎来自各国的选手，举行了盛大的晚宴。在第十八桌，有5

名大陆选手和5名港澳选手共同进膳。为了增进交流，他们决定相隔就坐，即每个大陆选手左右旁都是港澳选手，每个港澳选手左右旁都是大陆选手。那么，这一桌一共有_2880__种不同的就坐方案。注：如果在两个方案中，每个选手左右相邻的选手相同，则视为同一种方案。 【分析】

（1）下图1 2 3 4 5 的排列方式是5!，1 2 3 4 5、5 1 2 3 4、4 5 1 2 3、3 4 5 1 2、2 3

4 5 1 这5种排列方式如果围成一圈只算一种排列 （2）所以下图1 2 3 4 5 的围成一圈排列方式是5!/5

(3) 1 2 3 4 5 之间的abcde5个位置的排列方式：a b c d e 与e a b c d不同，所以abcde

的排序方式有 5!,方案总数5!* 5!/5=2880

23

省淳中信息学奥赛辅导 奥赛试题解析

三、阅读程序写结果。（共4题，每题8分，共计32分） 1.

var a,b,c,d,e,ans: integer; begin

readln(a,b,c);

d:=a+b; e:=b+c; ans:=d+e; writeln(ans); end. 输入：1 2 5 输出：___10______

2. 【求1——18中是18的因子数量】 Var n,i,ans: integer; begin

readln(n); ans:= 0;

for i:= 1 to n do

if (n mod i)= 0 then ans := ans+1; writeln(ans); end. 输入：18 输出：____6____

【分析】18的因子数：1 2 3 6 9 18 3.

var n,i,j: integer;

a: array[1..100,1..100] of integer; function solve(x,y:integer): integer; var u,v: integer; begin

if x = n then

24

省淳中信息学奥赛辅导 奥赛试题解析

begin

solve:= a[x,y]; exit; end;

u:= solve(x+1,y); v:= solve(x+1,y+1);

if u>v then solve := a[x,y] + u else solve := a[x,y] + v; end; begin

read(n);

for i:= 1 to n do

for j:=1 to i do read(a[i,j]); writeln(solve(1,1)); end. 输入： 5 2 -1 4 2 -1 -2 -1 6 4 0 3 2 -1 5 8 输出：___14______

【分析】: 动态规划：数字三角形，计算从顶至底的某处的一条路径，使该路径经过的数字和

最大。每步的走法可沿直线向下或右斜线向下走 【1.状态描述】 （1）n是三角形的行数

（2）a[i,j]表示三角形第 i行、第j列的数 （3）u、v是两条路径的数字和，

（4）solve(x,y):点(x,y)达到底部的最优解 【2.状态转移】

（1）初始状态：底部最优解solve= a[x,y]三角形元素值

if x = n then

begin solve:= a[x,y]; exit;

（2）转移方程：点(x,y)达到底部的最优解solve(x,y)。它的前驱状态沿直线向下或右斜线

的点 (x+1,y)、 (x+1,y+1)到底部最优解

solve(x,y)= MAX{ solve (x+1,y)、 solve (x+1,y+1) }+ a[x,y] （3）目标状态：顶点到底部最优解solve(1,1)

25