信息学竞赛选拔赛试题（满分100分，时间120分钟）一、选择题（15分）：1.十进制数2003等值于二进制数（ ）。

A ． 010******* B. 10000011 C. 110000111 D. 11111010011 E. 11110100112.已知数组中A 中，每个元素A （I ，J ）在存贮时要占3个字节，设I 从1变化到8，J 从1变化到10，分配内存时是从地址SA 开始连续按行存贮分配的。

试问：A （5，8）的起始地址为（ ）A.SA+141B. SA+180C. SA+222D. SA+2253.将 5 个数的序列排序，不论原先的顺序如何，最少都可以通过（ ）次比较，完成从小到大的排序。

A. 6B. 7C. 8D. 9E. 104.在 Pascal 语言中，表达式 (21 xor 2)的值是（ ）A. 441B. 42C.23D.24E.255.在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为（ ）A.2B.3C.4D.5 二、数学问题及算法分析：1.（5分）一棵二叉树的前序遍历和中序遍历分别如下，画出该二叉树。

前序遍历：ABCDEFGHIJ 中序遍历：CBEDAGHFJI 2. （5分）在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。

印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的６４片金片，这就是所谓的汉诺塔。

不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。

僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

不管这个传说的可信度有多大，我们先来做题！ 给定A 、B 、C 三根足够长的细柱，在A 柱上放有2n 个中间有孔的圆盘，共有n 个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情形）。

现要将这些圆盘移到C 柱上，在移动过程中可放在B 柱上暂存。

要求：（1）每次只能移动一个圆盘；（2）A 、B 、C 三根细柱上的圆盘都要保持上小下大的顺序； 任务：设An 为2n 个圆盘完成上述任务所需的最少移动次数，对于输入的N ，写出An 的解析式。

3. （10分）打水问题有N 个人在一个水龙头前排队接水，每个人接水的时间Ti 是互不相等的。

找到一种这N 个人排队接水的顺序，使他们平均等待的时间达到最小。

请写出这道题的解题思路。

4. （10分）合并果子在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。

多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。

可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。

多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。

假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有3种果子，数目依次为1，2，9。

可以先将 1、2堆合并，新堆数目为3，耗费体力为3。

接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。

所以多多总共耗费体力=3+12=15。

可以证明15为最小的体力耗费值。

对给定的果子的堆数和每堆果子的果子数目，请写出该题的解题思路。

.三、程序阅读（30分）：1. program ex2;var i,j,n:longint;b:array [0..31] of 0..1; begin n=1999; i:=0;while n<>0 do beginb[i]:=n mod 2; i:=i+1; n:=n div 2 end;for j:=i-1 downto 0 do write(b[j]); end.输出: 2. program primenumber; varflag :boolean; n,sum,i,j,p :integer;rec :array[1..25] of integer; begin n:=100;sum:=0;for i:=1 to n do beginflag:=true;if i=1 thenbeginflag:=false;endelsebeginp:=trunc(sqrt(i));for j:=2 to p do if i mod j =0 then flag:=false; end;if flag then begin inc(sum); rec[sum]:=i; end;end;for i:=1 to sum dobeginif (i mod 5=1)and(i<>1) then writeln;write(rec[i],' ');end;end.程序运行结果：3.program pascaltriangle;varf :array[0..20,0..20] of integer;i,j,n :integer;beginn:=9;for i:=0 to 20 dofor j:=0 to 20 do f[i,j]:=0;f[1,1]:=1;for i:=2 to n dofor j:=1 to j dof[i,j]:=f[i-1,j-1]+f[i-1,j];for i:=1 to n dobeginfor j:= 1 to i do write(f[i,j],' ');writeln;end;end.程序运行结果: 四、程序填空（25分）：1.每一趟从待排序的数据元素中选出最小（或最大）的一个元素用变量K记录该元素的位置，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

在该程序中用数组a记录待排序列。

program selectsort;var i,j,k,temp:integer;a:array[0..100] of integer;beginfor i:=n downto 2 dobegink:=1;for j:=1 to i do ①___________;temp:=a[k];②________________;a[j]:=temp;end;for i:=1 to n do write(a[i],' ');end.2.高精度算法，属于处理大数字的数学计算方法。

在一般的科学计算中,会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。

一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开方等运算。

对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中，用一个数组去表示一个数字，这样这个数字就被称谓是高精度数。

高精度算法就是能处理高精度数各种运算的算法。

在该题中，用数组A记录加数，B记录小数字加数，用数组C记录A与B的和,A[0]和c[0]存放该数字的位数。

program add;typedata =array[0..1000] of integer;vara,c :data;b :integer;procedure inputdata;vari,j,len :integer;s :string;beginreadln(s);①_______len:=length(s);for i:=1 to len do val(s[len+1-i],a[i]);a[0]:=len;end;procedure work(a:data; b:Integer; var c:data); vari,k :integer;beginfillchar(c,sizeof(c),0);for i:=1 to a[0] dobegin②_______c[i]:=k mod 10;c[i+1]:=k div 10;end;i:=i+1;while c[i] div 10 > 0 dobegink:=c[i];c[i]:=k mod 10;c[i+1]:=k div 10;i:=i+1;end;while (c[i]=0)and(i>1) do ③_______c[0]:=i;end;procedure outputdata(a:data);vari :integer;beginfor i:=a[0] downto 1 do write(a[i]);end;begininputdata;work(a,b,c);outputdata(c);end. 请将答案写在下面：一、选择题（15分）：1-5：二、数学问题与算法分析：1.（5分）2.（5分）3.（10分）4.（10分）三、程序阅读（30分）1.2.3.四、程序填空（25分）1. ①_______________________②_______________________2. ①_______________________②_______________________③_______________________。