信息学奥赛试题及答案.

信息学奥赛试题

一、填空题（共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。

1.微型计算机的性能主要取决于（ ）。

A） 内存 B） 主板 C） 中央处理器 D） 硬盘 E） 显示器 2.能将高级语言程序转换为目标程序的是( ).

A）调试程序 B）解释程序C）编辑程序 D）编译程序E）连接程序 3．A=11001010B,B=00001111B,C=01011100B,则A∨B∧C=( )

A）01011110 B） 00001111 C）01011100 D） 11001110 E) 11001010 4.计算机设备，既是输入设备，又是输出设备的是( )。 A)键盘 B)触摸屏 C)扫描仪 D)投影仪 E)数字化仪 5.计算机病毒传染的必要条件是( ) 。

A) 在内存中运行病毒程序 B) 对磁盘进行读写操作

C) 在内存中运行含有病毒的可执行程序 D) 复制文件 E)删除文件

6．已知队列(13，2，11，34，4l，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的元素是( )。 A)5 B)41 C)77 D)13 E)18

7.在使用E-mail前，需要对Outlook进行设置，其中ISP发送电子邮件的服务器称为( )服务器。 A)POP3 B)SMTP C)DNS D)FTP E)HTTP

8.对给定的整数序列(54,73,21,35,67,78,63,24,89)进行从小到大的排序时,采用快速排序的第一趟扫描的结果是( ).

A)(24,21,35,54,67, 78,63,73,89) B)(24,35,21,54,67, 78,63,73,89) C)(24,21,35,54,67, 63,73,78,89) D)(21,24,35,54,63, 67,73,78,89) E)(24,21,35,54,67, 63,73,78,89)

9. 编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1，2，3，??,一圈又一圈,问当数到数字n ,所在的纸牌编号为多少?

A) n mod 13 B)1+(n-1) mod 13 C)(n+1) mod 13-1 D)(n+1) mod 13 E) (n-1) mod 13 10.对下图进行广度优先拓朴排序得到的顶点序列正确的是( ). A) 1,2,3,4,5,6 B) 1,3,2,4,5,6 C) 1,3,2,4,6,5D) 1,2,3,4,6,5, E) 1,3,2,4,5,6 11.下列属于冯.诺依曼计算机模型的核心思想是( ).

A) 采用二进制表示数据和指令; B) 采用”存储程序”工作方式

C) 计算机硬件有五大部件(运算器、控制器、存储器、输入和输出设备) D) 结构化程序设计方法 E) 计算机软件只有系统软件

12．CPU访问内存的速度比访问下列哪个(些)存储设备要慢( )。 A)寄存器 B)硬盘 C)软盘 D)高速缓存 E)光盘 13．下列电子邮件地址，哪个(些)是正确的( )。

A)wang@hotmail.com B)cai@jcc.pc.too1.rf.edu.jp

C)162.105.111. 22 D)ccf.edu.cn E) http://www.sina.com 14．数字图像文件可以用下列哪个(些)软件来编辑( )。

A)画笔(Paintbrush) B)记事簿(Notepad) C)Photoshop D)WmRAR E)MidiSoft 15．下列哪个(些)软件不是操作系统软件的名字( )。 A)Windows XP B)DOS C)Linux D)OS／2 E)Arch／Info 16.下面关于算法的正确的说法是( )

A)算法必须有输出 B)算法必须在计算机上用某种语言实现

C)算法不一定有输入 D)算法必须在有限步执行后能结束 E)算法的每一步骤必须有确切的定义 17．下列逻辑运算正确的是（ ）。

A) A·（A + B ）= A B) A +（A·B）= A

C) A·（B + C ）= A·B + A·C D)A +（B·C）=（A + B）·（A + C） E) A+1=A 18.下列关于排序说法正确的是( ).

A) 插入排序、冒泡排序是稳定的 B) 选择排序的时间复杂性为O(n2) C) 选择排序、希尔排序、快速排序、堆排序是不稳定的 D) 希尔排序、快速排序、堆排序的时间复杂性为O(nlog2n) E) 快速排序是速度最快的排序

19.对于一个大小为3的栈，若输入队列为123456，则下列输出队列有可能的是（ ）。 A) 123456 B)654321 C)432165 D)431256 E)321654

20. 设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key)=key % 13,其中% 是求余数运算。用二次探查法解决冲突,则对于序列(８、31、20、33、18、53、27),则下列说法正确的是( ) 。

A)27在1号格子中 B) 33在6号格子中 C) 31在5号格子中 D) 20在7号格子中E) 18在4号格子中 二.问题求解（5分*2=10分）

1.某年级学生共选修6门课程，期末考试前，必须提前将这6门课程考完，每人每天只在下午至多考一门课程，设6门课程分别为c1，c2，c3，c4，c5，c6，S(ci)为学习ci的学生集合。已知S(ci)∩S(c6)≠?，i=l，2，．．．，5，S(ci)∩S(ci+1)≠?，i=1，2，3，4，S(c5)∩S(c1)≠? ，问至少安排 天才能考完这6门课程。

2．设有一棵k*树，其中只有度为0和k两种结点，设n0，nk分别表示度为0和度为k的结点个数，试求出n0和nk之间的关系(n0=数学表达式，数学表达式仅含nk、k和数字)。 三.阅读程序写出正确的程序运行结果(4 *8分=32分) 1 program t1；

var n，k，s：longint； begin

readln(n); k:=0； s:=1；

while s <= n do begin

k:=k+1; n:=n-s; s:=s+6*k end;

writeln (k) end.

输入:1000000 输出:

2. program t2;

var x,y1,y2,y3:integer; begin

readln(x);

y1:=0;y2:=1;y3:=1; while y2<=x do begin

y1:=y1+1;y3:=y3+2;y2:=y2+y3; end; writeln(y1); end.

输人：x＝400 输出：

3. program t3；

var m，n，i，j：integer；

p，w，a，b：array[0．．19] of integer；

begin

read(n)； m：= 0； for i：= 0 to n-1 do

begin read (p[i])； b[i] ：=1； end； for i ：= 0 to n-1 do begin

if (i>0) then

a[m]：= p[i]-p[i-1] else

a[m]：= p[i]； m：= m+1：

while ((m>1) and (a[rn-1]=0)) do begin m ；= m-1； b[m] ：= l； end； if (m>0) then w[i]：=b[m-1] else

w[i]：=b[0]；

a[m-1] ：= a[m-1]-1；

for j ：= 0 to m-1 do b[j] ；= b[j]+1； while ((m>1) and (a[m-1]=0)) do begin

m ：= m-1； b[m] ：=1； end; end;

for i ：= 0 to n-1 do begin

write(w[i])； write(' '); end；

writeln(' ')； end． 输入：4 4 6 6 6 输出：

4. program t4； const

u：array[1．．4] of integer = (0，5，3，1)； v：array[1．．4] 0f integer = (0，7，6，5)； var a，b，c，d，e，f，x，y，z： integer； begin

read (a，b，c，d，e，f)；

z ：= f + e + d + (c+3) div 4； y ：= 5 * d + u [ c mod 4 ]； if (b>y) then begin

z ：= z+ (b-y+8) div 9；

x ：= ((b-y+8) div 9 * 9- (b-y)) * 4+11*e+V[c mod 4]； end else

x ：= (y-b) *4+11*e+v[c mod 4]； if (a>x) then

z ：= z + (a-x+35) div 36； writeln(z)； end．

输入: 4 7 9 20 56 47 输出:

四.完善程序题(2分+3*4分+2分+4*3分=28分)

1．问题描述：工厂在每天的生产中，需要一定数量的零件，同时也可以知道每天生产

一个零件的生产单价。在N天的生产中，当天生产的零件可以满足当天的需要，若当天用不完， 可以放到下一天去使用，但要收取每个零件的保管费，不同的天收取的费用也不相同。

问题求解：求得一个N天的生产计划(即N天中每天应生产零件个数)，使总的费用最少。 输入：N(天数 N<=29) 每天的需求量 (N个整数) 每天生产零件的单价(N个整数) 每天保管零件的单价(N个整数)

输出：每天的生产零件个数(N个整数) 例如：当N=3时，其需要与费用如下：

┌────┬────┬────┬────┐

│ │ 第一天 │ 第二天 │ 第三天 │ ├────┼────┼────┼────┤

│ 需要量 │ 25 │ 15 │ 30 │ ├────┼────┼────┼────┤

│生产单价│ 20 │ 30 │ 32 │ ├────┼────┼────┼────┤

│保管单价│ 5 │ 10 │ 0 │ └────┴────┴────┴────┘ 生产计划的安排可以有许多方案，如下面的三种：

┌────┬────┬────┬───────────┐

│ 第一天 │ 第二天 │ 第三天 │ 总的费用 │ ├────┼────┼────┼───────────┤

│ 25 │ 15 │ 30 │25*20+15*30+30*32=1910│ ├────┼────┼────┼───────────┤

│ 40 │ 0 │ 30 │40*20+15*5+30*32=1835 │ ├────┼────┼────┼───────────┤

│ 70 │ 0 │ 0 │70*20+45*5+30*10=1925 │ └────┴────┴────┴───────────┘ 程序说明：

bln]：存放每天的需求量 cln]：每天生产零件的单价 d[n]：每天保管零件的单价 e[n]：生产计划 程序：

program exp5; var

i,j,n,yu,jO,j1,s :integer;

b, c, d, e : array[O..30] of integer; begin

readln(n);

for i:=1 to n do readln(b[i] ,c[i] ,d[i]); for i:=1 to n do e[i]:=0;

____(1)____:=10000; c[n+2]:=0; b[n+1]:=0; j=1; while (jO<=n) do begin

yu:=c[jO]; j1:=jO; s:=b[jO]; while ____(2)____ do begin

____(3)____ j1:=j1+1;s:=s+b[j1]; end;

____(4)____ j0:=j1+1: end;

for i:=1 to n do write(e[I]:4); readln; end.

2. 问题描述]

将一个含有运算符为：(、)、+、-、*、/、^(乘幂运算)、~(求负运算)的中缀表达式， 如：((1+2)*5)^2-(3+5)/2转化为后缀表达式，如：12+5*2^35+2/-．

[解题思路]将中缀表达式转化为后缀表达式，首先规定运算符的优先数如下： ┌───┬───┬───┬─────┬──────┬───┬───┐ │运算符│ ( │ ) │ +，－ │ * ，/ │ ~ │ ~ │

├───┼───┼───┼─────┼──────┼───┼───┤ │优先数│ 0 │ 1

│ 2 │ 3 │ 4 │ 5 │ └───┴───┴───┴─────┴──────┴───┴───┘ 1．若输入是运算量，则将该运算量输出；

2．若是左括号“(”，则将该符号的优先数压入设置的运算符堆栈e[p]中去；

3．输入运算符优先数是2，3，4，5时，如果栈空，则将运算符的优先数进栈。如果栈不空， 则将它与栈顶元素进行比较，倘若优先数大于栈顶元素的优先数，则进栈；小于顶元的，则 顶元退栈并输出该运算符，然后再继续比较，直到大于顶元或栈空时进栈；

4．若是右括号“)”，同时栈顶元又为左括号“(”，则栈顶元退栈，并抹去右括号“)”． 否则转3处理；

5．输入完而栈非空，则将栈内内容逐一退栈并输出。所有输出的结果就为后缀表达式。 过程中用到的相关数据结构如下：

type arraydata = array[1..100] of string[20]; const fh:array[1..8] of string[1]

=('(',')','+','-','*','/','~','^'); b:array[1..8] of byte =(0,1,2,2,3,3,4,5); var d: arraydata; {存储运算量及运算符号} i,j,m,k: byte; [过程程序]

procedure hzbds(var d: arraydata; var m: byte ); var: array [ 1.. 100 ] of byte; i,p,k ,bi:byte; bl: boolean; begin

p:=O;k:=1;bj:=0; while k<=m do begin

if d[k]=’(‘ then begin

p:=p+1;e[p]:=1 end

else begin

for i:=2 to 8 do if ___(1)___ then begin

b1:= true; repeat

if ___(2)___ then begin

p:= p+1 ;e[p]:=i;bj:= 1 ;b1:= false end

else if ____(3)___ then if e[p] < >1 then begin

p:=p+1;e[p]:=i;bj:=1;b1:=false end

else if d[k] < >')' then begin

p:=p+1;e[p]:=i;bj:=1;b1:=false end

else begin

___(4)___;bj:= 1 ;b1:= false; end else begin

write(fh[e[p]] ,' ') ;p:=p-1 end; until b1 = false; end

if ___(5)___ then write(d[k] ,' ') else bj:=0; end; k:=k+1 end

b1:= true; repeat

if p=0 then b1:= false else begin

write(fh[e[p]],’’);p:=p-1; end until b1 = false; writeln; end;

参考答案 一．选择题

1-10:CDDBB BBBBC 11.ABC 12. AD 13.AB 14.AC 15.E 16.ABCDE 17.ABCD 18.ABCD 19.AE 20. BCDE 二．1．4 2．（k-1）nk+1

三．1．100 2．20 3．1 1 2 4 4．126

四．1．（1）c[n+1] （2）yu+d[j0] < c[j1+1] （3）yu:=yu+d[j1] （4）e[j0]:=s

2．（1）d[k]=fh[I] （2）p=0 （3）b[e[p]] < b[I] （4）p:=p-1 （5）bj=0 或 bj <> 1

本文来源：https://www.bwwdw.com/article/54v6.html