信息学校内选拔赛试题

《信息学校内选拔赛试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息学竞赛选拔赛试题（满分100分，时间120分钟）一、选择题（15分）：1.十进制数2003等值于二进制数（）。A．0100000111B.10000011C.110000111D.11111010011E.11110100112.已知数组中A中，每个元素A（I，J）在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A（5，8）的起始地址为（　　）A.SA+141　　B.SA+180　　C.SA+222　　D.SA+2253.将5个数的序列排序，不论原先的顺序如何，最少

2、都可以通过（）次比较，完成从小到大的排序。A.6B.7C.8D.9E.104.在Pascal语言中，表达式(21xor2)的值是（）A.441B.42C.23D.24E.255.在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为（）　A.2　B.3　C.4　D.5二、数学问题及算法分析：1.（5分）一棵二叉树的前序遍历和中序遍历分别如下，画出该二叉树。前序遍历：ABCDEFGHIJ中序遍历：CBEDAGHFJI2.（5分）在印度，有这么一个古老的传说：在世界中心贝拿

3、勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的６４片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。不管这个传说的可信度有多大，我们先来做题！给定A、B、C三根足够长的细柱，在A柱上放有2n个中间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有

4、两个相同的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情形）。现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求：（1）每次只能移动一个圆盘；（2）A、B、C三根细柱上的圆盘都要保持上小下大的顺序；任务：设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的N，写出An的解析式。3.（10分）打水问题有N个人在一个水龙头前排队接水，每个人接水的时间Ti是互不相等的。找到一种这N个人排队接水的顺序，使他们平均等待的时间达到最小。请写出这道题的解题思路。4.（10分）合并果子在一个果园里，多多已经将所有的果子打了下

5、来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并

6、，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。对给定的果子的堆数和每堆果子的果子数目，请写出该题的解题思路。.三、程序阅读（30分）：1.programex2;vari,j,n:longint;b:array[0..31]of0..1;beginn=1999;i:=0;whilen<>0dobeginb[i]:=nmod2;i:=i+1;n:=ndiv2end;forj:=i-1downto0dowrit

7、e(b[j]);end.输出:2.programprimenumber;varflag:boolean;n,sum,i,j,p:integer;rec:array[1..25]ofinteger;beginn:=100;sum:=0;fori:=1tondobeginflag:=true;ifi=1thenbeginflag:=false;endelsebeginp:=trunc(sqrt(i));forj:=2topdoifimodj=0thenflag:=false;end;ifflagthenbegininc(sum);re

8、c[sum]:=i;end;end;fori:=1tosumdobeginif(imod5=1)and(i<>1)thenwriteln;write(rec[i],'');end;end.程序运行结果：3.programpascaltriangle