noip初赛模拟题

noip初赛模拟题一套

一、选择题（共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题，即

每题有且只有一个正确答案，选对得分；后10题为不定项选择题，即每题有1至5个正确答案，只

有全部选对才得分）。

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

A）内存 B）主板 C）中央处理器 D）硬盘 E）显示器

2. 128KB的存储器用十六进制表示，它的最大的地址码是( )

A)10000B)EFFF C)1FFFFD)FFFFF E)FFFF

3.能将高级语言程序转换为目标程序的是( ).

A)调试程序 B)解释程序 C)编辑程序 D)编译程序 E)连接程序

4．A=11001010B,B=00001111B,C=01011100B,则A∨B∧C=( )B

A)01011110 B)00001111 C)01011100 D)11001110 E)11001010

5.计算机病毒传染的必要条件是() 。

A)在内存中运行病毒程序

B)对磁盘进行读写 *** 作

C)在内存中运行含有病毒的可执行程序

D)复制文件

E)删除文件

6. TCP／IP协议共有()层协议

A)3 B)4 C)5 D)6 E)7

7.192.168.0.1是属于( ).

A)A类地址 B)B类地址 B)C类地址 D)D类地址 E)E类地址

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.一棵n个结点的完全二叉树,则二叉树的高度h为( ).

A)n/2 B)log2n C)(log2n)/2 D) [log2n]+1 E)2n-1

10.下图对该图进行广度优先拓朴排序得到的顶点序列正确的是( ).

A)1,2,3,4,5,6

B)1,3,2,4,5,6

C)1,3,2,4,6,5

D)1,2,3,4,6,5,

E)1,3,2,4,5,6

11.下列属于冯.诺依曼计算机模型的核心思想是( ).

A)采用二进制表示数据和指令

B)采用”存储程序”工作方式

C)计算机硬件有五大部件(运算器、控制器、存储器、输入和输出设备)

D)结构化程序设计方法

E)计算机软件只有系统软件

12.下列属于输入设备的是( ).

A)打印机B)扫描仪 C)光笔D)鼠标E)显示器

13.算式(1000)10-(100)16-(10)8的结果是( ).

A)(890)10B)(986)8 C)(1011100000)2 D)(2E0)16 E)(736)10

14.下面关于算法的正确的说法是( )

A)算法必须有输出

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

C)算法不一定有输入

D)算法必须在有限步执行后能结束

E)算法的每一步骤必须有确切的定义

15.下列关于十进制数100的正确说法是( ).

A)原码为01100100B

B)反码为64H

C)反码为9BH

D)补码为64H

E)补码为9BH

16.关于windows系统中的窗口和对话框的说法正确的是( ).

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,其中% 是求余数

运算。用二次探查法解决冲突,则对于序列(8、31、20、33、18、53、27),则下列说法正确

作者： maold 2007-5-22 20:57 回复此发言

--------------------------------------------------------------------------------

2 回复：noip初赛模拟题一套

的是( ) 。

A)27在1号格子中

B)33在6号格子中

C)31在5号格子中

D)20在7号格子中

E)18在4号格子中

二．问题求解（5分*2=10分）

1．一个商场有m种颜色的小球，每种小球足够多，在这m种小球中挑选n个小球的选法有多少种？

如 m=2，n=3 时有4种选法分别是：两种小球的个数分别为03，12，21，30．问：当m=4，n=4时

选法数=__________。

2．如果一棵m度树中有n1个度为1的结点，n2个度为2的结点，…….有

nm个度为m的结点,则该树中叶结点的的个数=______________.

三.阅读程序写出正确的程序运行结果(4分*8=32分)

1.program t1

var n:integer

function count(n:integer):integer

begin

if n=1 then count:=0 else

if n mod 2=0 then count:=count(n div 2)+1 else

count:=count(n*3+1)+1

end

begin

readln(n)

writeln(count(n))

end.

输入:99 输出:

2.program t2

var hi,lo:integer

procedure pl(m,n:integervar hi,lo:integer)

var I:integer

begin

I:=nhi:=0lo:=0

Repeat

I:=I-1lo:=lo+m

If lo>=10000 then

begin

Lo:=lo-10000

Hi:=hi+1

End

Until I=0

Write(hi:4,’, ‘,lo:4)

End

Begin

P1(200,343,hi,lo)

End.

输出:

3.program t3

Var d1,d2,X,Min : real

begin

Min:=10000X:=3

while X <15 do

begin

d1:=sqrt(9+(X-3)*(X-3))

d2:=sqrt(4+(15-X)*(15-X))

if (d1+d2) <Min then Min:=d1+d2

X:=x+0.001

end

writeln(Min:10:2)

end.

输出：

4.program t4

var i,k,n:integer

x,w:array[1..500] of integer

begin

readln(n)

for i:=1 to n do

begin

x[i]:=0w[i]:=1

end

for i:=2 to trunc(sqrt(n))+1 do

if x[i]=0 then

begin

k:=i*i

while K<=n do

begin

x[k]:=i

k:=k+i

end

end

for i:=n downto 1 do

if x[i]<>0 then

begin

w[x[i]]:=w[x[i]]+w[i]

w[i div x[i]]:=w[i div x[i]]+w[i]

w[i]:=0

end

writeln(w[2],w[3]:5,w[5]:5)

end.

输入:20 输出:

四.完善程序题(4分*7=28分)

1. 降序组合.给定两个自然数n,r(n>r),输出从数1 到n中按降序顺序取r个自然数的所有

组合.例如,n=5,r=3时,有如下组合:

5 4 3

5 4 2

5 4 1

5 3 2

5 3 1

5 2 1

4 3 2

4 3 1

4 2 1

3 2 1

程序如下:

program tk1

var n,r,i,j:integer

a:array[1..20] of integer

begin

write('n,r=')

repeat

readln(n,r)

until n>r

i:=1a[1]:=nwriteln('result:')

repeat

if i<>r then

if a[i]>r-i then

begin

___(1)___i:=i+1

end

else begin

___(2)___

a[I]:=a[I]-1 end

else

begin

for j:=1 to r do write(a[j]:3)

writeln

if a[r]=1 then

begin

i:=i-1a[i]:=a[i]-1

end else ___(3)___

end

until a[1]=r-1

end.

2. 现在政府计划在某个区域内的的城市间架设高速公路，以使任意两个城市间能够直接或

间接到达，怎样修路，费用最小。

输入文件：第一行一个整数 n(n<=100)表示城市数目。

第二行至第n+1行每行两个数xi,yi(0<=xi,yi<=100)表示第i个城市的坐标(单位:千米)；

输出最小费用(每千米一个单位价格)。

程序如下:

program t6

const maxn=100

type tcity=record

x,y:real

end

var c:array[1..maxn] of tcity

d:array[1..maxn,1..maxn] of real

p:array[1..maxn] of integer

n,i,j,k:integer

a,min:real

begin

readln(n)

for i:=1 to n do readln(c[i].x,c[i].y)

for i:=1 to n do

for j:=1 to n do

d[i,j]:=sqrt(sqr(c[i].x-c[j].x)+sqr(c[i].y-c[j].y))

p[1]:=0

for i:=2 to n do ___(4)___

for i:=1 to n-1 do

begin

min:=1e10

for j:=1 to n do

if ___(5)___ then

begin

min:=d[p[j],j]

___(6)___

end

a:=a+d[p[k],k]

p[k]:=0

for j:=1 to n do

if ___(7)___ then p[j]:=k

end

writeln(a:0:2)

end.

初赛模拟测试题答案：

一

1-10：CCDDB BCBDC

11-15:ABCBCDCDEACDEABD

16-20:BCABCDACDAEBCDE

二

1： 35

2： n2+2n3+…+(m-1)nm+1

三

. 1: 25

2: 6.8600

3: 13.00

4: 18 8 4

四

. 1.a[i+1]:=a[i]-1

2. i:=i-1

3. a[i]:=a[i]-1或a[r]:=a[r]-1

4. p[i]:=1

5. (p[j]>0) and (d[p[j],j]) <min)

6. k:=j

7. (p[j]>0) and (d[p[j],j]>d[k,j])

初赛的笔试题有四部分：选择题、问题求解、程序阅读理解、完善程序。

1、选择题：共20题，每题1．5分，共30分。每题有4个备选方案。

2、问题求解：共2题，每题5分，共10分。

3、程序阅读理解题：共4题，每题8分，共32分。

4、完善程序：共 2题，第一题10分，第二题18分，两题共28分。

复赛为上机编程题，题目包括4道题，每题100分，共计400分。测试时，测试程序为每道题提供了5~10组测试数据，考生程序每答对一组得10~20 分；累计分即为该道题的得分。

---