“共同的梦想”——OIFans.cn第一次NOIP初赛模拟赛试题

（  提高组  Pascal 语言  二小时完成  ）

●●    全部试题答案均要求使用答题辅助系统答题并按要求上交，格式、文件名不符一律无效    ●●

●●    点击http://www.oifans.cn/ans可辅助生成标准答题文件，答案请发送到up@oifans.cn    ●●

●●  这是闭卷考试，请不要查阅资料。如果您当地初赛允许使用计算器，那么现在您也可使用  ●●

 

一、单项选择题（共 10 题，每题 1.5 分，共计 15 分。每题有且仅有一个正确答案）

1.运算器的主要功能是（    ）。

A.控制计算机各部件协同工作并进行运算

B.进行算术运算和逻辑运算

C.控制输入输出数据

D.进行运算并存储结果

E.进行运算并存取结果

 

2.我们常用的CD-ROM的准确含义是（    ）。

A. 只读光盘     B.可擦写光盘    C.光盘驱动器    D.文件式存储盘    E.音乐CD唱机

 

3.下面（    ）不是开源软件Linux众多的发行版之一。

A.Fedora     B.Redhat AS     C.Ubuntu      D.Netware     E. 红旗桌面

 

4.设栈S和队列Q的初始状态为空，元素a1、a2、a3、a4、a5、a6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是a2、a4、a3、a6、a5、a1，则栈S的容量至少有（    ）。

A.2     B.3     C.4     D.5     E.6

 

5.在Pascal语言中，表达式（25 or 31）的值是（    ）。

A.6     B. 775     C.-7     D. 25     E. 31

 

6.在Pascal语言中，表达式（5 + 6 MOD 4 DIV 2）的值是（    ）。

A.1     B.5     C.6     D.17     E.此表达式错误，无输出值

 

7.在二叉树中，若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则我们称此二叉树称为完全二叉树。现在将有关二叉树的概念推广到三叉数，则一棵有244个结点的完全三叉数的高度是（    ）。

A.4     B.5     C.6     D.7     E.8

 

8.如果一个连通无向图具有n个顶点，那么它至少有（    ）条边。

A.n-1     B.n     C.n+1     D.nlon2n     E.1/2*n(n-1)

 

9.2007年初，（    ）击败了戴尔，在全球PC厂商市场占有率排行榜上名列第一。

A.联想     B.英特尔     C. 宏碁     D.华硕     E.惠普

 

10.八进制数133.64用十进制数表示的结果是（    ）。

A.91.52     B.85.416     C.85.52     D.91.8125     E.1011011.110101

 

 

二、多项选择题（共 10 题，每题 1.5 分，共计 15 分。每题正确答案的个数大于或等于 1。多选或少选均不得分）

11.在现行的IPv4标准中，下列符合公网IP地址标准的是（    ）。

A.60.213.14.35     B.192.168.0.3     C. 222.223.228.135     D. 219.137.239.256

 

12.在Pascal语言中，下列不符合标准的用户自定义标识符是（    ）。

A.end     B.name(5)     C.name+5     D.5name

 

13.(2007)8 + (7EC)16的结果是（    ）。

A.(101111110011)2     B.(5763)8     C.(3059)10    D.(BF3)16

 

14.若S是一个大小为4的栈，若元素1，2，3，4，5，6，7按顺序依次进栈，则这7个元素的出栈顺序可能为（    ）。

A.1,2,3,4,5,6,7     B.1,4,3,5,7,2,6     C.1,3,2,4,7,5,6      D.2,3,7,6,5,4,1

 

15.下面那个（些）操作系统属于多用户操作系统（    ）？

A.Windows ME     B.Windows 2003     C.Unix     D.Linux

 

16.下列关于排序的说法正确的是（    ）。

A.插入排序和冒泡排序都是稳定的排序算法。

B.选择排序的平均时间复杂度为O(n2)。

C.选择排序、快速排序、希尔排序、堆排序都是不稳定的排序算法。

D.希尔排序、快速排序、堆排序的平均时间复杂度都是O(nlog2n)。

 

17.以下列扩展名结尾的文件，一般表示图片文件的是（    ）。

A.GIF     B.OGG     C.PSD     D.PNG

 

18.下面关于阿兰·麦席森·图灵（Alan Mathison Turing）说法正确的有（    ）。

A.图灵是法国人。

B.图灵被称为人工智能之父。

C.人们为了纪念这位伟大的科学家将计算机界的最高奖定名为“图灵奖”。

D图灵提出计算机的基本工作原理是存储程序和程序控制。

 

19.以下断电之后将不能保存数据的有（      ）。

A.内存     B.L1高速缓存     C.CF卡     D.ROM

 

20.要将高级语言程序转换为可执行文件可以使用（    ）。

A.解释程序     B.翻译程序     C.编辑程序     D.编译程序

 

 

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

1.某商店有m种不同颜色的小球且每种小球的数量都足够多。要在这m种不同颜色的小球里挑选出n个小球，设共有s种不同的选法。例如当m=2，n=3时，s等于4，也就是说，共有4种不同的选法。（分别为：【0，3】，【1，2】，【2，1】，【3，0】）。现在，令m=6，n=5，试求出选法数s=__________。

 

2.现有10个外形一样的小球，其中只有一个是次品，次品的质量与正品不同，但并不知次品是比正品轻还是比正品重（亦无法用手感知）。现有一架无砝码及游标的天平，试找出次品并确定出次品到底是比正品轻还是比正品重，请问至少需要称量__________次，才能满足上述要求？

 

 

四、阅读程序写结果（共 4 题，每题 8 分，共计 32 分）本题请千万不要用程序算，真的没意思……

1.program ex401;

var x,y:integer;

    u,v:array[0..3] of integer;

begin

for x:= 0 to 3 do read(u[x]);

v[0]:=u[0]+u[2]; v[1]:=v[0]+u[2];

v[2]:=(u[0]-u[1]-u[2]) MOD u[1]-4;

v[3]:=(v[0]-v[1]-v[2]) DIV u[0];

x:= v[0]+v[1] MOD v[2] DIV v[3];

if x<10 then

  y:=v[0]+v[1]+v[2]+v[3]

else y:=10+u[0]+v[1]+v[2]+v[3];

write(x,':',y);

end.

输入：3 9 13 2

输出：____________________

 

2.program ex402;

var a,work:array[1..100] of integer;

    i,j,x,d,max:integer;

begin

read(max);

for i:=1 to max do begin read(a[i]); work[i]:=a[i]; end;

d:=max div 2;

while d>=1 do

begin

  for i:=d+1 to max do

  begin

    x:=work[i];

    j:=i-d;

    while (j>0) and (x<work[j]) do

    begin

    work[j+d]:=work[j];

    dec(j,d);

    end;

    work[j+d]:=x;

  end;

  d:=d div 2;

end;

for i:= max downto 1 do

  begin

    if a[i]=work[i] then write('1')

    else write('0');

  end;

end.

输入：10  71  149  32  11  90  119  9  130  95  144

输出：____________________

 

3.program ex403;

var

  s:string; n,p,q,i:integer;

  a:array[1..10]of char; c:char;

begin

  readln(n);

  s:='OIFans.cn-Fly with the same dream';

  p:=pos('s',s);

  s:=copy(s,p+19,255);

  s:=copy(s,n,255);

  c:='a'; q:=1;

  for i:=1 to length(s) do

  if s[i]>c then

    begin

      a[q]:=s[i]; c:=a[q]; inc(q);

    end;

  dec(q);

  for i:=1 to q do write(a[i]);

end.

输入：2

输出：____________________

 

4.program ex404;

var n,i:integer;

    total:longint;

function work(a,b:integer) : longint;

var c,d,e:longint;

    i:integer;

begin

  c:=1;

  for i:= 2 to a do c:= c*i;

  d:=1;

  for i:= 2 to b do d:= d*i;

  e:=1;

  for i:= 2 to a-b do e:= e*i;

  exit(c div d div e);

end;

 

begin

  read(n);

  total:=0;

  for i:= 1 to n do total:=total + work(n,i);

  write(total);

end.

输入：12

输出：____________________

 

 

五、完善程序(前 5 空，每空 2 分，后 6 空，每空 3 分，共 28 分)

1.【问题描述】

有形如：ax3+bx2+cx+d=0  这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d  均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。（记方程f(x)=0，若存在2个数x1和x2，且x1<x2，f(x1)*f(x2)<0，则在(x1，x2)之间一定有一个根。）

【算法分析】

如果是一般的求三次方程根的问题，那么只能直接使用求根公式，但这是非常复杂的。由于题目要求只精确到0.01，故我们考虑一下是否可以应用数值方法进行计算。由题目给出的方程在区间内存在根的条件可知，我们可以用一个变量从-100.000到100.000以步长0.001做循环。若，则可知在区间内存在方程的解。这样无论这个区间内的解是什么，在取两位小数的精度后都与取两位小数的结果是一样的。故我们就可以把取两位小数精度的作为问题的解。另外还有可能方程的根在区间端点的情况，我们可以通过判断是否为0来获得。

但这种方法由于用到了题目所要求的数值精度小的特殊性，故无法扩展。而在用数值方法求方程根的时候，我们最常用的方法就是二分法。该方法的应用在于如果确定了方程在区间内如果存在且只存在一个根，那么我们可以用逐次缩小根可能存在范围的方法确定出根的某精度的数值。该方法主要利用的就是题目所给的若在区间内存在一个方程的根，则这个事实，并重复执行如下的过程：

l         取当前可能存在解的区间；

l         若或，则可确定根为并退出过程；

l         若，则由题目给出的定理可知根在区间中，故对区间重复该过程；

l         若，则必然有，也就是说根在中，应该对此区间重复该过程。

最后，就可以得到精确到0.001的根。

再考虑什么样的区间内会有根。由于题目给出了所有的根都在-100到100之间，且根与根之间差不小于1的限制条件，故我们可知，在、、……、、这201个区间内，每个区间内至多只能存在一个根。这样对除去区间外的其他的区间，要么，要么时这个方程在此区间内才有解。若，显然为解；若，则可以利用上面所说的方法球出解来。这样就可求出这个方程的所有解。

【程序代码】

program ex501;

var

  x:array[1..3] of real;

  a,b,c,d,u,v:real;

  i,t:integer;

 

function f(x:real):real;

  begin

    f:=     ①     ;

  end;

 

begin

  read(a,b,c,d);

  t:=0;

  for i:=     ②     do

    begin

      u:=i;

      v:=u+0.99999;

      if (abs(f(u))<0.00001) or (f(u)*f(v)<=0) then

      begin

           ③     ;

      if abs(f(u))<0.00001 then x[t]:=u

      else begin

        while (u+0.001 < v) and (f((u+v)/2) <> 0) do

         if     ④     then v:=(u+v)/2

              else u:=(u+v)/2;

        x[t]:=(u+v)/2;

      end;

     end;

    end;

  for t:=1 to 3 do     ⑤     ;

  writeln;

end.

 

2.【问题描述】

对于任意给出的一个正整数n(n<=50000)，求出具有n个不同因子的最小正整数m。（例如：但n=4时m=6，因为6有4个不同整数因子：1、2、3、6，并且是最小的有4个因子的整数。）

【算法分析】

由于具有n个不同因子的正整数一定是形如，且n=(i1+1)*(i2+1)*…*(ik+1)，要让最小，显然p1、p2、…pk要等于前k个质数。同时i1>=i2>=…>=ik。

程序中递归过程resolve用来求出n的所有不同的因子分解式，如n=12时，其所有不同的因子分解式有：12、6*2、4*3、3*2*2四种，然后比较相应的数211、25*3、23*32、22*3*5的大小得到最小值为22*3*5=60，由于m的值可能很大，所以比较两数大小时转化为自然对数后再比较，最终结果使用了改良的高精度运算。

【程序代码】

program ex502;

const maxn=50000;

  p:array [1..16] of longint=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53);

var h,i,j,k,l,n,t,total:longint;

    mins,s:real;

    f,c,minc:array [1..500] of longint;

    m:array [0..20000] of longint;

procedure resolve(dep,m,r:longint);

var i:longint;

begin

  if r=1 then

    begin

      s:=0;

      for i:=1 to dep-1  do s:=s+     ①     ;

      if s<mins then

        begin mins:=s; l:=dep-1; minc:=c; end

    end

    else

      begin

      for i:=m to total do

        if     ②     then

          begin

           c[dep]:=f[i];

           resolve(dep+1,     ③     )

          end

      end

end;

 

procedure mul(t:longint);

begin

  for k:=0 to h do m[k]:=m[k]*t;

  for k:=0 to h do

  begin

    m[k+1]:=m[k+1]+m[k] div 10;

    m[k]:=m[k] mod 10

  end;

  while     ④     do

  begin

    m[h+2]:=m[h+1] div 10;

    m[h+1]:=m[h+1] mod 10;

    h:=h+1

  end;

end;

begin

  readln(n);

  total:=0;

  for i:=n downto 2 do

   if n mod i=0 then

    begin total:=total+1; f[total]:=i; end;

  mins:=maxlongint;

  resolve(1,1,n);

  for i:=1 to 15000 do m[i]:=0;

  m[0]:=1; h:=0;

  t:=1;

  for i:=1 to l do

   for j:=1 to minc[i]-1 do

    if p[i]<200000000 div t

     then t:=t*p[i]

    else begin mul(t);      ⑤     ; end;

       ⑥     ;

  for i:=h downto 0 do write(m[i]);

  writeln;

end.