NOIP2015年初赛提高组模拟试题(带答案)

-回复 -浏览
楼主 2018-12-05 17:42:35
举报 只看此人 收藏本贴 楼主
点击上面微信号关注我关注我哟定期推送帐号信息学新闻竞赛自主招生信息学专业知识信息学疑难解答信息学训练营信息等诸多优质内容的微信平台!

考前热身

信息学初赛模拟试题

一、选择题(共20题,每题1.5分,共计30分。前10题为单选题;后10题为不定项选择题)。

1.微型计算机的性能主要取决于(C )。

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

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

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

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

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

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

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

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

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

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

6. TCP/IP协议共有(  B  )层协议

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

7.192.168.0.1是属于( C ).

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

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

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为( D ).

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

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.下列属于冯.诺依曼计算机模型的核心思想是(ABC ).

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

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

D)结构化程序设计方法          E)计算机软件只有系统软件

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

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

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

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

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

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

C)算法不一定有输入    D)算法必须在执行有限步后能结束

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

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

A)原码为01100100B     B)反码为64H  C)反码为9BH    D)补码为64H    E)补码为9BH

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

A)对话框能移动和改变大小          B)窗口能移动和改变大小

C)对话框只能移动但不能改变大小    D)对话框不能移动但能改变大小

E)窗口能移动不能改变大小

17.下列逻辑运算正确的是(C )。

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.下列关于排序说法正确的是( ABC ).

A)插入排序、冒泡排序是稳定的      B)选择排序的时间复杂性为O()

C)选择排序、希尔排序、快速排序、堆排序是不稳定的

D)希尔排序、快速排序、堆排序的时间复杂性为O()

E)快速排序是速度最快的排序

19.对于一个大小为3的栈,若输入队列为123456,则下列输出队列有可能的是( AE )。

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),则下列说法正确的是(  BCDE  ) 。

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时选法____35______

2.已知一棵度为m的树中,有n1个度为1的结点,n2个度为2的结点,…,nm个度为m的结点,问该树中有多少个叶子结点?


四、完善程序题

    

第1题(14分)以下程序是将一组整数按从小到大的顺序排列。排序的方法是将长度为n的数a分为两个长度分别为(n div 2)与(n-n div 2)的子数组a1,a2。然后递归调用排序过程,将a1,a2分别排序,最后将a1,a2归并成数组a。例如a=(3,1,2,4),那么a1=(3,1),a2=(2,4)。调用排序过程将a1,a2排序,得到a1=(1,3),a2=(2,4),然后进行合并排序。 

从键盘输入数的长度n以及n个整数,存在数组a中,调用子过程sort进行排序,最后输出排序结果。 

program wsh; 

const maxn=100;. 

type arr:array[1..maxn] of integer; 

var 

a:array[1..maxn] of integer; 

n,i:integer; 

procedure sort(n:integer; var a:arr); 

var 

i, p1, p2, n1, n2: integer; 

a1,a2 :arr; 

begin 

if n = 1 then exit; 

fillchar(a1,sizeof(a1) ,0); 

fillchar(a2,sizeof(a2) ,0); 

n1:=0; n2:=0; 

n1:=n div 2; n2:=(_(1)_); 

for i:= 1 to n1 do a1[i]:=a[i]; 

for i:= 1 to n2 do a2[i]:=_(2)_; 

_(3)_; 

sort(n2, a2); 

p1:=1; p2:=1; 

n:=0; 

while (p1 <= n1) and (_(4)_) do 

begin 

n:=n+1; 

if _(5)_ 

then begin a[n]:=a1[p1] ;inc(p1); end 

else begin _(6)_; inc(p2) ;end; 

end; 

if p1 <= n1 

then for i:= _(7)_ to n1 do begin n:=n+1;a[n]:=a1[i] end 

else for i:=p2 to n2 do begin n:=n+1; a[n]:=a2[i]; end; 

end; 

begin 

write(‘n = ‘); 

readln (n); 

for i:= 1 to n do read(a[i]); 

readln; 

sort(n,a); 

for i:=1 to n do write(a[i],”); 

writeln; 

end. 

答案: 

n-n1 

a[n1+i] 

sort(n1,a1) 

(p2 < =n2) 

a1[p1] < a2[p2] 

a[n]:=a2[p2] 

p1 


第2题(8分)有n(1≤n≤100)个同学种m(1≤n≤m≤100)种小树苗,例如:4个同学(1、2、3、4)每小时种4种树苗(A、B、C、D)的数量估算如下表所示,编程输出每人种1种苗所用的总时间最少的安排方案和所花费的时间。 

学 生 A B C D 

1 5 2 4 5 

2 4 3 5 3 

3 5 2 4 2 

4 3 2 3 3 

program wsh; 

const 

maxn=100; maxm = 100; 

var 

a: array[1..maxn, 1..maxm] of integer; 

m, n: integer; 

i, j, t: integer; 

procedure work(k,t1: integer); 

var i: integer; 

begin 

if _(1)_ then 

begin 

if t1 < t then t1:=t; 

exit; 

end; 

for i:= (2) to (3) do 

work(k+1,(4)); 

end; 

begin 

readln(n,m); 

for i:=1 to n do 

begin 

for j:=1 to m do read (a[i,j]); 

readln 

end; 

t:= maxint; 

work(1,0); 

writeln(t) 

end.


答案: 

k>n 

t1+t[k,i]


第3题(10分)程序的任务是用0…9中的数字填入如下乘法运算的*处,数字可重复使用,且所用的数字至少有一个是素数,要求输出满足下列算式的方案数。 

* * *
x * *
----------------
* * *
* * *
----------------
* * * 


      program wsh; 

    const p:set of 0…9 = [2,3,5,7]; 
    var 
    s:set of 0..9; 
    n: integer; 
    ans: longint; 
    f: text; 
    procedure init; 
    var 
    i: integer; 
    t:byte; 
    begin 
    readln(n); 
    s:=[]; 
    for i:=1 to n do 
    begin 
    read(t); 
    s:=s+[t]; 
    end; 
    close(f); 
    end; 
    function ok(x,l:integer):boolean; {此函数判断x是否符合条件} 
    var t: byte; 
    begin 
    ok:=false; 
    if (1)< > l then exit; 
    while x< >0 do 
    begin 
    t:=x mod 10; 
    if not ( t in s) then exit; 
    x:=x div 10; 
    end; 
    ok:=true; 
    end; 
    function inset(x:integer):boolean; {此函数判断x中是否包含素数字} 
    var t: byte; 
    begin 
    inset:= false; 
    while (2) do 
    begin 
    t:=x mod 10; 
    if t in p then 
    begin 
    inset:= true; 
    exit; 
    end; 
    (3)
    end; 
    end; 
    procedure work; 
    var i,i1,i2,i3,j1,j2:integer; 
    begin 
    ans:=0; 
    for i1:=1 to 9 do 
    if i1 in s then 
    for i2:=1 to 9 do 
    if i2 in s then 
    for i3:=1 to 9 do 
    if i3 in s then 
    begin 
    (4)
    for j1:=1 to 9 do 
    if (j1 in s) and ok(j1*i,3) then 
    for j2:=1 to 9 do 
    if (j2 in s) and ok(j2*i,3) and (5) then 
    begin 
    if (i1 in p) or (i2 in p) or (i3 in p) 
    or (j1 in p) or (j2 in p) or inset(j1*i) or inset(j2*i) 
    then inc(ans); 
    end; 
    end; 
    writeln(ans); 
    end; 
    begin 
    init; 
    work; 
    end.


答案: 
trunc(ln(x)/ln(10))+1 
x>0 
x:=x div 10 
i:=i1*100+i2*10+i3 
ok(j1*i*10+j2*i,4) 
  

第4题(15分)下列程序是对冒泡排序的一种改进,数组elem中有n个元素elem[1]、elem[2]…、elem[n]。要排序的关键字是key。先从一端开始扫描,进行比较、交换,然后改变下一趟的扫描方向进行同样的处理。请完善下面的过程。 

program wsh; 
type 
Td = record 
key: integer; 
inf: real; 
end; 
var 
elem:array[1..1000] of Td; 
n, i: integer; 
procedure shakesort(n: integer); 
var 
i, t, h: integer; 
c: boolean; 
temp: Td; 
begin 
h:=1; 
t:=n; 
repeat 
_(1)_
for i:=h to t-1 do 
if elem[i].key > elem[i+1].key then begin 
temp:=elem[i]; 
elem[i]:=elem[i+1]; 
elem[i+1]:=temp; 
_(2)_
end; 
_(3)_
for i:=t-1 downto h do 
if elem[i].key > elem[i+1].key then begin 
temp:=elem[i]; 
elem[i]:=elem[i+1]; 
elem[i+1]:=temp; 
_(4)_
end ; 
_(5)_
until c ; 
end; 
begin{主过程} 
…{略} 
end. 
答案: 
c:=true 
c:=false 
t:=t-1 
c:=false 
h:=h+1

第5题(15分)读入一个10x10的数字矩阵,矩阵中的数字各不相同,输出这个矩阵经过旋转、翻转后的7种不同样式。 
program wsh; 
var 
matrix: array [0..7,1..10,1..10] of integer; 
lr, lc, which: integer; 
procedure overturn( which: integer); 
var 
lr, lc: integer; 
begin 
for lr:= 1 to 10 do 
for lc:= 1 to 10 do 
matrix[which,lr,lc]:=matrix[which-1,(1),(2)]; 
end; 
procedure rotate( which: integer); 
var 
lr, lc: integer; 
begin 
for lr:=1 to 10 do 
for lc:=1 to 10 do 
matrix[which,lr,lc]:=matrix[which-1,(3),(4)]; 
end; 
begin 
for lr:= 1 to 10 do 
for lc:=1 to 10 do 
read(matrix[0,lr,lc]); 
readln; 
for which:= 1 to 7 do 
begin 
if (5) then overturn(which) 
else rotate(which); 
for lr:=1 to 10 do 
begin 
for lc:= 1 to 10 do 
write(matrix[which,lr,lc]:3); 
writeln; 
end; 
readln; 
end; 
end. 
答案: 
11-lr 
lc 
11-lc 
lr 
which=4 

第6题(16分)[问题描述]在n个元素的集合S中,找最大和最小元素(设n的值为2m). 
[解题思路]把集合S分成两个子集S1和S2,每个子集有n/2个元素.应用递归过程search(S,Y,MAX,MIN)(S中有2k个元素),过程返回一对(MAX,MIN)值,为最大和最小元素,最后,把S1和S2中的最大和最小元素进行比较,从而得到S中的最大和最小元素. 
[程序] 
program wsh; 
type data = array[1..256] of byte; 
jh = set of byte; 
var s,ss:jh; 
a:data; 
i ,j, d,largest, smallest: byte; 
function sq(k: byte): byte; 
begin 
if k =1 then sq:=2 else sq:=2*sq(k-1); 
end; 
procedure seareh(x:jh; y:byte; var max,rain:byte); 
var k,p,w,nxl,nx2,ni1,ni2,n: byte; 
m:array[1..2] of byte; 
s1 ,s2:jh; 
begin 
if y = 2 then 
begin 
p:=0; 
for k:=1 to i do 
if (1) then 
begin 
p:=p+1;m[p]:=(2)
end; 
if (3) then 
begin 
w:=m[1];m[1]:=m[2];m[2]:=w; 
end; 
max:= m[1] ;min:= m[2] ;exit; 
end 
else 
begin 
si:=[];n:=O;y:=(4)
for k:=1 to i do 
if (5) then 
begin 
n:=n+1;if n <= y then s1:=(6)
end; 
s2:=(7)
search(s1,y,nx1,ni1);search(s2,y,nx2,ni2); 
if nx1 > nx2 then max:=nx1 else max:=nx2; 
if ni1 < ni2 then min:=ni1 else min:=ni2; 
end 
end; 
begin 
i:=0;s:=[];ss:=[]; 
for j:=1 to 7 do ss:=ss+[sq(j)]; 
writeln(‘enter 2^n data:’); 
repeat 
while not eoln do 
begin 
i:=i + 1; read(d); 
if (8) then i:= i - 1 
else begin 
a[i]:=d;s:=s+[a[i]]; 
end; 
end; readln; 
until i in ss; 
search(s,i,largest,smallest); 
writeln(‘largest-data:’,largest,’smallest-data:’,smallest) 
end. 
答案: 
a[k] in x 
m[p]:=a[k] 
m[1] < =m[2] 
y:=trunc(y/2) 
a[k] in x 
s1:=s1+[a[k]] 
s2:=x-s1 
d in s 
第7题(15分)以下程序完成对数组每个元素向后移动n个单位。数组元素的下标依次为0到m-1,对任意一个数组元素a[i]而言,它的值移动后将存储在数组元素a[(i+n) mod m]中。 
例如,m=10,n=3,移动前数组中存储的数据如下前一行所示,则程序运行后数组中存储的数据如下后一行所示。 
0 3 86 20 27 67 31 16 37 42 
16 37 42 0 3 86 20 27 67 31 
程序清单: 
program wsh; 
const maxm = 10000; 
var i, k, m, n, rest, start, temp: longint; 
a:array [0..maxm] of longint; 
begin 
write(‘input m, n: ‘); 
readln(m ,n); 
for i:=0 to m-1 do a[i]:= random(100); 
writeln(‘before move’); 
for i:=0 to m -1 do write(a[i]:5); 
writeln; 
rest:= m; start:= 0; 
while (1) do 
begin 
k:= start; 
repeat 
k:=(k+n) mod m 
until k <= start; 
if (2) then 
begin 
temp:= a[k]; 
repeat 
a[k]:=a[(m*n+k-n) mod m]; 
k:=(m*n+k-n) mod m; 
(3)
until k = start; 
(4)
end; 
(5)
end; 
writeln(‘after move’); 
for i:=0 to m - 1 do write(a[i]:5); 
writeln 
end. 
答案: 
rest>0 
k:=start 
rest:=rest-1 
a[(k+n) mod m]:=temp 
start:=start+1 
第8题(15分)设m叉树采用列表法表示,即每棵子树对应一个列表,表的结构为:子树根顶点的值部分(设为一个字符)和用“( )”括起来的各树的列表(如有子树的话),各子列表间用“,”分隔。例如下面的三叉树可用表a(b(c,d),e,f(g,h,i))表示。

本程序输入列表,生成一棵m叉树,并由m叉树输出列表。假定输入无错误。 
程序清单: 
program wsh; 
const m=3; 
type pointer =^node; 
node = record 
val: char; 
subtree: array [1..m] of pointer 
end; 
var 
i: integer; 
bur: string; 
root: pointer; 
procedure maketree(var s: pointer); {由列表生成m叉树} 
var k: integer; 
begin 
(1)
s^.val:= buf[i]; 
i:=i+1; 
for k:=1 to m do s^.subtree[k]:=nil; 
if buf[i]=’(’ then 
begin 
k:=1; 
repeat 
i:=i+1; 
(2)
if buf[i] =’)’ then 
begin i:= i + 1; break end; 
k:=k+1 
until (3)
end 
end; 
procedure walktree(t:pointer); {由m叉树输出列表} 
var i: integar; 
begin 
if t < > nil then 
begin 
(4)
if t^.subtree[1] < > nil then 
begin 
write(‘(‘); 
for i:=1 to m do 
begin 
(5)
if (i< >m)and(t^.subtree[i+1] < >nil) then write(‘,’) 
end; 
write(‘)’) 
end 
end 
end; 
begin { main program } 
write(‘input list: ‘); 
readln(buf); 
i:=1; 
maketree(root); 
walktree(root); 
writeln 
end. 
答案: 
new(s) 
maketree(s^.subtree[k]) 
buf[i] < >’,’ 
write(t^.val) 
walktree(s^.subtree[i])

第9题现在政府计划在某个区域内的的城市间架设高速公路,以使任意两个城市间能够直接或间接到达,怎样修路,费用最小。

输入文件:第一行一个整数 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 ___p[i]:=1;___   

  for i:=1 to n-1 do

  begin

    min:=1e10;

    for j:=1 to n do

    if __(p[j]<>0)and(d[p[j],j]<min)____ then

      begin

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

        ___k:=j;___

      end;

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

    p[k]:=0;

    for j:=1 to n do

    if ___(p[j]<>0)and(d[p[j],k]<d[p[j],j])___ then p[j]:=k;

  end;

  writeln(a:0:2);

end.







关注「信息学竞赛」

看更多信息学趣闻与知识

↓↓


往期精彩

1.信息学竞赛,你想了解的知识都在这里!(答家长问题)

    2.信息学奥赛(NOIP)初赛学习方法推荐

    3.信息学奥赛(NOIP)复赛学习方法推荐

    4.信息学竞赛之路<<<<<

    5.大牛为你推荐十本最适合信息学竞赛的书籍

    6.信息学奥赛有那么重要吗?

    7.参加编程竞赛对实际工作的用处

    8.考前必备!!! 清北学堂独家录制NOIP考试技巧讲座

    9.在线编程挑战赛第一名:我是这么学算法的

    10.最新发布NOI2017 笔试题库

    11.信息学竞赛如何学习及准备攻略!

    12.NOI 2017获奖名单,几家欢喜几家愁?

    13.凭什么我得了信息学奥赛国家一等奖(山东)

14.榜样 | 北大降200分要这个诸暨天才少年

15.IOI2017 | 厉害了中国队!!!

16.OI金牌教练胡芳:爱和成长的故事

17.信息学竞赛,一个让孩子不需要再去挤独木桥的方向

18.新学期必须了解的学科竞赛与自主招生时间!

19.北大录取生陈代超:在信息学中找到“思维图谱”

20.国务院发文支持编程教育进入中小学,中国人工智能厚积薄发


更多信息学基础知识请戳我查看历史文章<<<

我要推荐
转发到

友情链接