NOI初赛模拟练习.docx

NOI初赛模拟练习.docx

《NOI初赛模拟练习.docx》由会员分享，可在线阅读，更多相关《NOI初赛模拟练习.docx（71页珍藏版）》请在冰点文库上搜索。

NOI初赛模拟练习

NOI初赛模拟练习

（一）

时间：

120分钟总分：

100

一、选择题（1.5'*20=30'）

1、最近我国研制成功的具有自己的知识产权的微处理器的名称是：

A.奔芯B.龙芯C.长城芯D.新芯

2、有关万维网说法不正确的是：

A.可以简称为WebB.可以写为WWWC.英文是指WorldWideWebD.是指http

3、网络中Host是指：

A.主机B.服务器C.用户机D.客户机

4、网络中DNS是指

A.网络数据库B.数据库名称系统C.域名服务器D.数据传送系统

5、计算机的总线系统不包括：

A.文件总线B.数据总线C.控制总线D.地址总线

6、一般家里上网用的“猫”是一种调制解调器，因为电话线传输的是模拟信号，而计算机处理的是数据信号，因此要作一个转换。

调制与解调是相反的过程，这两个过程是：

A.D/A与A/DB.A/D与D/AC.A/A与D/DD.D/D与A/D

7、在计算机里如果用四个字节来表示有符号的整数，那么整数的范围最大的是：

A.-2^31+1到2^31-1B.-2^31到2^31-1C.-2^31到2^31D.-2^31+1到2^31

8、以下有关存储设备速度的描述正确的是：

A.RAM>HD>FD>CDROMB.HD>RAM>CDROM>FDC.RAM>CDROM>HD>FDD.RAM>HD>CDROM>FD

9、下面四个不同的进制的数，最小的一个数是：

A．（11011001）2B．（75）10C．（107）8D．（48）16

10、设循环队列中数组的下标范围是1-n，其中头尾指针分别是f和r，则其元素个数是：

A．r-fB．r-f+1C．（r-f）MODn+1D．（r-f+n）MODn

11、已知数组A中，每个元素A[I，J]在存储时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存储分配的。

试问：

A[5，8]的起始地址为：

A．SA+141B．SA+180C．SA+222D．SA+225

12、计算机病毒是指：

A．能传染给用户的磁盘病毒B．已感染病毒的磁盘

C．是一种寄生于计算机内的病毒D.是一种特殊的具有传播性的程序

13、直接通过总线与CPU连接的部件是：

A．显示器B．内存储器C．磁盘驱动器D．键盘

14、某台计算机的运算速度是1.7GIPS，它的含义是：

A．每秒执行17亿条指令B．每秒处理17亿个字符

C．每秒执行1.7亿条指令D．每秒处理1.7亿个字符

15、在Windows98中，PrintScreen键的作用是：

A.打印正在执行的一个任务B.将屏幕信息送到打印机

C.打印正在执行的各个任务名D.将屏幕信息复制到剪贴板

16、下列IP地址中属于公网地址的是：

A、10.10.10.10B、172.16.16.16C、172.32.32.32D、192.168.168.168

17、Linux中tail+10toyoumail.txt命令的执行作用是：

A、显示文件toyoumail.txt从第10行到文件最后；

B、显示文件toyoumail.txt最后10行；

C、显示文件toyoumail.txt当前行往后的10行；

D、显示文件toyoumail.txt当前行往前的10行。

8、Linux中用ls–l命令显示文件或目录的详细信息时，最左边的一列为：

A、文件主的是否可读的权限B、文件主的是否可写的权限

C、文件主的是否可查询或执行的权限D、文件的类型

19、某一子网的掩码为：

255.255.255.192，那么这个子网最多可能的主机数是：

A、190B、192C、62D、64

20、Telnet应用程序的主要目的是：

A、在计算机之间传输文件B、收取电子邮件

C、查看超文本文档D、远程登录到主计算机中

二、解答题（8'+12'=20'）

1、插件问题有N个如右图的插件：

↑↑

∧∧

其中↑可以插入∧,如两个插件时可有3种插入方法:

↑↑↑↑↑↑

∧∧∧∧∧∧

↑↑↑↑↑↑

∧∧∧∧∧∧

问n个插件时有多少种插入方法?

2（初中组题）有30个连续的自然数，在其中选三个数，这三个数的和能整除3，共有多少种选法？

（高中组题）密码锁问题

某部门有m个人，现在要设置一个密码锁，只有当m个人当中的任n个人到场时才能打开锁（n<=m）。

（1）这个密码锁共有多少个码？

（2）每个人分多个码？

提示：

只是考虑多少个码，不要考虑每个码是多少位。

每个人分配的码数是一样的，但具体的码不完全一样，即某两个人当中可能有重复的码。

当m个到场输入码时类似于集合的相加运算，但是n个集合相加的结果一定就是密码锁的总码。

三.写出程序运行结果（10'*2=20'）：

1、programread_program_1;

varn:

1..9;

procedurediamond（m:

integer）;

procedureline（k:

integer）;

varj:

integer;

begin

write（'':

10-k）;

forj:

=1to2*k-1doifj<=kthenwrite（j）elsewrite（2*k-j）;

writeln;

end;

begin

ifm=nthenline（m）

elsebeginline（m）;diamond（m+1）;line（m）;end;

end;

begin

write（'n='）;readln（n）;diamond

（1）;

end.

运行程序：

n=8

输出结果：

2.programread_program_2

consth:

string[16]='0123456789ABCDEF';

varn:

longint;i,j:

integer;

s:

array[1..16]ofinteger;

begin

write（'n='）;readln（n）;i:

=0;

whilen>0dobegin

i:

=i+1;

s:

=nmod16;

n:

=ndiv16;

end;

write（'h='）;forj:

=idownto1dowrite（h[s[j]+1]）;

writeln;

end.

运行程序：

输入：

n=347592

输出：

四.完成程序（3'*10=30'）:

1.已知两字符串S=S1S2…Sn和P=P1P2…Pm（1≤m≤n）,检查P是否为S的一个子序列,即是否存在i,使得Si=P1,Si+1=P2,…,Si+m-1=Pm。

如有，求最小i值。

如没有，置i=0。

programcomplete_program_1

vari,j,k,m,n:

integer;

found:

boolean;

s,p:

string;

begin

write（'Inputastring:

'）;readln（s）;

write（'Inputastring:

'）;readln（p）;

m:

=length（p）;n:

=length（s）;

（1）;

found:

=false;

while

（2）do

begin

i:

=i+1;

（3）;

k:

=1;

while（4）dobeginj:

=j+1;k:

=k+1end;

if（5）thenfound:

=true

end;

iffoundthenwriteln（i）elsewriteln（0）

end.

2.菲波那契数列的规律是：

前两个数均为1，第三个数开始每个数等于经前面两个数的和，即1，1，2，3，5，8，13，21，34，55，89……已知任意一个大于0的整数可以表示为若干个互不相同的菲波那契数。

程序的输入输出示例：

输入：

121输出：

121=89+21+8+3

程序的算法说明（以121为例）：

（1）寻找小于或等于n的最大菲波那契数a（如89），并以a作为组成n的一个数输出。

（2）若n不等于a，则以n-a作为新的任意正整数，重复

（1）步骤。

若n=a则结束。

（3）函数find返回小于或等于n有最大菲波那契数。

programcomplete_program_2;

varn:

integer;

functionfind（n:

integer）:

integer;

vara,b,c:

integer;

begin

a:

=1;b:

=1;

repeat

c:

=_____

（1）________;

a:

=_____

（2）________;

b:

=c;

untilb>=n;

ifb=nthenfind:

=______（3）______

elsefind:

=______（4）______;

end;

procedurep（n:

integer）;

vara:

integer;

begin

a:

=find（n）;

write（'+',a）;

ifa

end;

begin

readln（n）;

write（n,'='）;

p（n）;

writeln;

end.

参考答案:

一.选择题

题号1234567891011121314151617181920

选择BDACAABDCCADBADCADCD

二.解答题

1.3^（n-1）

2.初中组:

3*C（10,3）+C（10,1）*C（10,1）*C（10,1）=1360

高中组:

（1）C（M,N-1）

（2）C（M-1,N-1）

三.写程序运行结果:

1.（15行数字菱形,每一行由1到i,再由I-1到1）

2.h=54DC8

四.完成程序题

1.

（1）i:

=0

（2）not（found）and（im或k=m+1

2.

（1）a+b

（2）b（3）b或c或n（4）a（5）p（n-a）

2002年南海市青少年“赛思杯”NOI初赛试题

作者：

未知文章来源：

网络点击数：

210更新时间：

2004-10-3

初中、高中组初赛试题

（PASCAL语言，二小时完成）

◆◆请将正确答案在答卷上填写，在本试题卷上作答无效◆◆

一、选择题：

（选出每题正确的一个答案代码，填在横线上，每题1.5分，共30分）

1．已知X是一个三位数，下列式可以求出X的十位数数字。

A．INT（X/10）*10-X*10B.INT（X/10）*10-X/10

C.INT（X/10）-INT（X/100）*10D.INT（X/10）-INT（X/10）*100

2．算法指的是。

A．计算机程序B．解决问题的计算方法

C．排序算法D．解决问题的有限运算序列

3．线性表采用链式存储时，结点的存储地址。

A．必须是不连续的

B．连续与否均可

C．必须是连续的

D．和头结点的存储地址相连续

4．“A、B不能同时大于C”的PASCAL表达式为。

A．A>CANDB>CB.（A<=C）AND（B<=C）

C.AC）AND（B>C））

5．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为。

A．front=front+1B．front=（front+1）MOD（m-1）

C．front=（front-1）MODmD．front=（front+1）MODm

6．在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为

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

7．某班有50名学生，每位学生发一张调查卡，上写a,b,c三本书的书名，将读过的书打√，结果统计数字如下：

只读a者8人；只读b者4人；只读c者3人；全部读过的有2人；

读过a，b两本书的有4人；读过a，c两本书的有2人；读过b，c两本书的有3人；

问：

读过a的人数是。

（A）12人（B）30人（C）10人（D）24人（E）31人

8．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：

20，15，21，25，47，27，68，35，84

15，20，21，25，35，27，47，68，84

15，20，21，25，27，35，47，68，84

则所采用的排序方法是。

A．选择排序B．希尔排序C．归并排序D．快速排序

9．在串S=“structure”中，以t为首字符的子串有_________个。

A.18.B.20C.12D.13

10．已知一个图的广度优先生成树如右图所示，则与此相

应的广度优先遍历序列为。

A.abcdefgB.afgebcdC.abefcdgD.adcbegf

11．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为。

A．２B．3C．4D．1

12．对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。

若在逻辑上看一个环，则队列中元素的个数为。

A.R-FB.n+R-FC.（R-F+1）modnD.（n+R-F）modn

13．下面各程序段中，哪一个不能实现将A、B两变量中的数值交换。

A．B．C.D.

M=A;A=A+B;T=B;T=A;

N=B;B=A-B;B=A;B=A;

A=N;A=A-BA=TB=T

B=M

14．已知“9”的ASCII为39H，则数字“5”的ASCII的二进制表示为。

A．0110101B、1110101

C．35HD、0101011

15．已知N为非负整数，且

则F（5）的值为。

A．5B.2C.10D.7

二、阅读下列程序,写出程序运行结果（每题10分，共30分）

1.

programxx;

varn:

integer;

functions（n:

integer）:

longint;

begin

if（n=1）or（n=2）thens:

=n

elses:

=s（n-1）+s（n-2）

end;

begin

repeat

write（‘n=’）;readln（n）;

untiln>0

writeln（‘s=’,s（n））;

readln;

end.

当N=6时，写出程序的执行结果

2.

programex2（input,output）;

vara:

array[0..100]ofinteger;

i,j,r,p:

integer;

begin

fori:

=0to92doa[i]:

=i+1;

fori:

=1to92do

begin

forj:

=1to3do

begin

r:

=p;

p:

=a[p];

end;

a[r]:

=a[p];

end;

writeln（r）;

end.

3．

programplaying;

var

pc:

array[1..13]ofboolean;

i,t,s,k,p:

integer;

begin

fori:

=1to13dopc[i]:

=true;

i:

=1;t:

=0;s:

=2;p:

=0;k:

=0;

repeat

whilep<>idobegin

k:

=k+1;

ifk>13thenk:

=1;

ifpc[k]=truethenp:

=p+1;

end;

pc[k]:

=false;t:

=t+1;

i:

=i+s;s:

=s+1;

untilt=8;

write（k）;

readln;

end.

三、问题解答（每空5分，共10分）

1．平面上有7个点，共有3个点共线，其余再也没有3点共线，每两点连成一条直线，一共可以连成

（1）条不同直线。

以这些点为顶点可以连成

（2）个不同的三角形。

四、完善程序

（初中组只做第1、2两小题。

第1、2两小题每空3分，共30分；第3小题每空4分，本大题共50分）

1.由键盘输入N（1

的值.

例如输入:

10

输出:

3628800

[程序清单]

programex1（input,output）;

constmax=10000;

var

a:

array[1..max]ofinteger;

n,I,j,k:

integer;

begin

write（‘n=’）;

readln（n）;

forI:

=2tomaxdoa[i]:

=0;

（1）;

k:

=1;

forI:

=2tondo

begin

forj:

=1tokdo

（2）

forj:

=1tok-1do

begin

a[j+1]:

=a[j+1]+（a[j]div10）

（3）

end;

while（4）do

begin

a[k+1]:

=a[k+1]+（a[k]div10）;

a[k]:

=a[k]mod10;

（5）

end

end;

forI:

=kdownto1dowrite（a[i]）;

end.

2.自然数拆分:

任何一个大于1的自然数N,总可以折分成若干个自然数之和,且拆分的方法有多种,如N=5不同的拆分方法有以下7种:

5=1+1+1+1+1

5=1+1+1+2

5=1+2+2

5=1+1+3

5=1+4

5=2+3

5=5

5=1+4和5=4+1是同一种拆分,只选一种.

问题要求任何给定的自然数N（N>1）,求所有的拆分方法.

[程序清单]

programex4;

constm=100;

vars:

array[1..m]of0..m;

n,I,j,sum,count:

integer;

procedureprint;

vark:

integer;

begin

count:

=count+1;

write（count,’:

’,n,’=’,s[1]）;

fork:

=2toIdowrite（‘+’,s[k]）;

writeln;

end;

begin

write（‘Inputn:

’）;readln（n）;

____

（1）______;sum:

=0;j:

=0;count:

=0;

write（‘outputdata:

’）;

repeat

j:

=j+1;

________

（2）_________

if______（3）________

thenbegin

s[I]:

=j;

ifsum=n

thenbegin

print;

sum:

=sum-s[I];

i:

=I-1;

_______（4）_________;

j:

=s[I]

end

elsebegin

i:

=I+1;

________（5）_________;

end

end

elsebegin

sum:

=sum-j;

i:

=I-1;

sum:

=sum-s[I];

j:

=s[i];

end

untilI=0;

end.

3.求出一棵树的深度和宽度。

（本小题只要求高中组作答）

123400

200000

350000

460000

500000

670000

700000

例如有左下图的一棵树：

其树的深度为从根结点开始到叶结点结束的最大深度，树的宽度为同一层上结点数的最大值。

在左上图中树的深度为4，宽度为3。

用邻接表来表示树，左上图中的树的邻接表示如右上图：

程序说明：

数组tree表示树树（假设树的度为4）

数组q表示队列，其中SP1-取出指针，SP2-存入指针，q[i,0]表示层数

数组d，统计同一层上的结点数（假设≤20层）

程序清单

PROGRAMfoundfree;

VARI,J,SP1,SP2,L,MAX:

INTEGER;TREE:

ARRAY[1..20,1..6]OFINTEGER;

Q:

ARRAY[1..100,0..6]OFINTEGER;D:

ARRAY[0..20]OFINTEGER;

BEGIN

FORI:

=1TO14DOFORJ:

=1TO6DOTREE[I,J]:

=O;

FORJ:

=1TO14DOTREE[J,1]:

=J;

TREE[1,2]:

=2;TREE[1,3]:

=3;TREE[1,4]:

=4;TREE[2,2]:

=5;

TREE[2,3]:

=6;TREE[3,2]:

=7;TREE[3,3]:

=8;TREE[4,2]:

=9;

TREE[4,3]:

=10;TREE[4,4]:

=11;TREE[7,2]:

=12;

TREE[7,3]:

=13;TREE[13,2]:

=14;

SP1:

=1;SP2:

=1;

FORI:

=1TO6DOQ[1,I]：

=TREE[1，I]；

Q[1,0]:

=1;

WHILE

（1）DO

BEGIN

L:

=

（2）;J:

=2;

WHILE（3）DO

BEGIN

SP2:

=SP2+1;Q[SP2,0]:

=L;Q[SP2,1]:

=Q[SP1,J];

FORI:

=2TO6DO

Q[SP2,I]:

=TREE[Q[SP1,J],I];

J:

=J+1

END;

SP1：

=SP1+1

END；

WRITELN（4）

FORI:

=0TO20DOD[I]:

=0;

FORI:

=1TOSP2DO

D[Q[I,0]]:

=（5）

MAX:

=D[1];

FORI:

=2TO20DO

IFD[I]>MAXTHENMAX:

=D[I];

WRITELN（MAX）;

READLN;

END.

武进区第一届中学生NOI模拟试题（三）

一.单项选择题（共10题，每题1.5分，共计15分。

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

1.结构化程序的主要优点是________。

A、程序体积小,节省内存空间B、程序效率高,节省运行时间

C、程序结构清晰,可读性好,易维护与修改,可靠性高D、容易实现巧妙的算法

2.第一台计算机ENIAC的逻辑元件是________。

A、集成电路B、电子管C、晶体管D、继电器

3.高级语言编写的源程序变为目标程序要经过_________。

A、解释B、编译C、汇编D、编辑

4.十进制数25和–32相加，用补码法则，且结果亦用补码表示，则为________。

（设机器为8位机）