p1,p2,??pk,定义整数S
为:S=(p1-p2)2+(p1-p3)2+??+(p1-pk)2+(p2-p3)2+??+(pk-1-pk)2 问题求解:求出一种分法,使S为最大(若有多种方案仅记一种〉 程序说明:
数组:a[1],a[2],...A[N]存放原数 p[1],p[2],...,p[K]存放每个部分的积 b[1],b[2],...,b[N]穷举用临时空间 d[1],d[2],...,d[N]存放最佳方案 程序: program t6;
Var i,j,n,k : integer; Sum,cmax:longint;
a :array [1..100] of integer; b,d:array [0..100] of integer; p :array[1..30] of integer; begin
readln(n,k);
for I:=1 to n do read(a[I]); for I:=0 to n do b[I]:=1; cmax:=0;
while (b[0]=1) do begin
for I:=1 to k do ___（5）___; for I:=1 to n do ___（6）___; sum:=0;
for I:=1 to k-1 do
for j:=___（7）___ do
sum:=sum+(p[I]-p[j])*(p[I]-p[j]); if ___（8）___ then begin
cmax:=sum;
for I:=1 to n do d[I]:=b[I]; end; j:=n;
while ___（9）___ do j:=j-1; b[j]:=b[j]+1;
for I:=j+1 to n do ___（10）___ ; end;
writeln(cmax);
for I:=1 to n do write(d[I]:40); writeln; end.
6
初赛模拟试题（一）答案 一、选择题（共20题，每题1.5分，共计30分） 1、C 2、A 3、D
4、D。中缀表达式是对二叉树-A*+B/CDE的中序遍历，其后缀表达式， 即后序遍历结果为ABCD/+E*-
5、B。数组元素A[66,65]存储的起始地址是SA+13128，而结束地址则 是SA+13130-1 6、C 7、B 8、B 9、A 10、D 11、ABD 12、ABD 13、ACDE 14、ACDE 15、ACE 16、BCD 17、ACD
18、ACD。IP地址是由4个10进制数组成，每个数都在0～255之间，且彼此用.分隔。 19、BCDE 20、ACE
二.问题求解（5分*2=10分） 1、266 2、42
三.阅读程序写出正确的程序运行结果(4分*8=32分) 1、200。b=(1+a)*a/2，即b>=20100??
2、实际上是求1～50以内的质数，并按要求输出： 47 43 41 37 31 29 23 19 17 11 7 5 3 2 3、输出：
G A F F B B E E E C C C D D D D D D D C C C E E E B B F F A G 4、输出： 5＝ 1＋1＋3 5＝ 1＋2＋2 5＝ 1＋3＋1 5＝ 2＋1＋2 5＝ 2＋2＋1 5＝ 3＋1＋1
四、完善程序题(4分*4+2分*6=28分) 1． (1)path[i]:=[i]
(2)not (j in s) and (d[j] < mm) (3)(d[k]+cost[k,j]) < d[j] (4)path[j]+[k] 2．
(5)p[i]:=1
(6)p[b[i]]:=p[b[i]]*a[i] (7)i+1 to k (8)cmax < sum (9)b[j]=k (10)b[i]:=1
7
信息学竞赛初中组初赛模拟试题(二) 及答案
一、选择题：（共20小题，1-15小题为单选题，每题1分；16-20小题为多选题，每题2分。共25分）
1.对存储器按字节进行编址，若某存储器芯片共有10根地址线的引脚，则该存储器芯片的存储容量为( )。
(A) 512B (B) 1KB (C) 2KB (D)4KB (E)8KB
2.在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是( )。 (A)堆排序 (B)希尔排序 (C)冒泡排序 (D)快速排序 (E)二分排序
3.某数列有1000个各不相同的单元，由低至高按序排列，现要对该数列进行二分法检索，在最坏的情况下，需要检索( 单元。
(A)1000 (B)10 (C)100 (D)500 (E) 300
4.已知数组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+225 (E)sa+155 5.在pascal语言过程调用时，数值形参得到的是实际参数的( 。 (A) 数值 (B) 地址 (C)值 (D)变量 (E)以上都不是 6.一个24*24点阵的汉字字形信息所占的字节数为( 。 (A) 2 (B) 8 (C) 24 (D) 32 (E) 72
7. 在微机系统中，最基本的输入输出模块BIOS存放在( 中。 (A) RAM (B) ROM (C) 硬盘 (D)寄存器 (E)控制器
8. 十进制算术表达式:3*512+5*64+2*8+1的运算中,用二进制表示为( 。
(A)1011010001 (B) 10110100011 (C) 11101010001 (D) 11110100011 (E)111000
9.设栈S的初始状态为空,现对序列{1,2,3,4,5}在栈S上,依次进行如下操作(从元素1开始,出栈后不再进栈):进栈,出栈,进栈,进栈,出栈,出栈。试问出栈的元素序列是( 。 (A){1,2,3} B) {1,3,2} C) {3,2,1} D) {2,3,1} (E)以上都不对 10.E-mail邮件本质上是一个(
(A)文件 (B)电报 (C)电话 (D)传真 (E)电讯
11.一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有( 个结点 (A)2h-1 (B)2h-1 (C)2h+1 (D)h+1 (E)h*h+1 12.无向图G=(V，E)，其中V={a,b,c,d,e,f}
E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}对该图进行深度优先遍历,得到的顶点序列正确的是(
(A)a,b,e,c,d,f (B)a,c,f,e,b,d (C)a,e,b,c,f,d (D)a,b,e,d,f,c (E)以上都不对 13.pascal 编译程序是(
（A）. 把pascal 源程序转换成可运行的EXE文件的程序 （B）. 把pascal 源程序转换成等价的目标码的程序 （C）. 生成和修改一个pascal语言源程序的等程序
（D）. 把pascal的目标码程序转换成可运行的EXE文件的程序 （E）. 生成一个等价的汇编程序
14. 将三封信投到4个邮筒，最多的投法有（ ）
（A）． 种 （B）． 种 （C）． 种 （D）．种 E. 15. 电子信函(电子邮件)的特点之一是（ ）。 （A）.比邮政信函，电报，电话，传真都更快
8
（B）.在通信双方的计算机之间建立其直接的通信线路后即可快速传递数字信息
（C）.采用存储-转发方式在网络上逐步传递信息,不象电话那样直接、及时,但费用低廉 （D）.在通信双方的计算机都开机工作的情况下即可快速传递数字信息 16. 以下属于多媒体硬件的是（ ）
（A）．主机 （B）.光驱 （C）.声卡 （D）. 音箱 （E）. 超级解霸 17. 正确的二维数组类型说明是( )
(A) type ar2=array[1..5,5..1] of integer;
(B) type ar2=array[1..5] of array[5.1] of integer; (C) type ar2=array[1..5,1..5] of integer;
(D)type ar2=array[1..5] of array[1..5] of integer (E)type ar2=array[1..5,1..5] of 0..1 18.下列属于信息处理的是（ ）
（A）信息加工 （B）信息分类 （C）信息技术 （D）信息采集 （E）信息存储 19.在windows中,最小化一个应用程序窗口后，该程序将（ ）。
(A)被终止执行 (B) 被暂停执行 (C)被转入后台 (D)继续执行 （E）以上答案都不对 20. 下面的常量说明中，正确的是（ ）（A）CONST （B）、CONST （C）、CONST （D）、CONST （E）CONST t = true b, C = 45 M = 100，15 N = 1 OR 2 a= ’A’
二、问题求解：（第1小题5分，第2-3小题各4分,共13分）
[问题1]: 在所有三位数中，各位数字从高位到低位顺次减小的数共有 个。 [问题2]：\银条\
一位银矿勘探员无力预付3月份的房租。他有一根长31英寸的纯银条，因此他和女房东达成如下协议。他说，他将把银条切成小段。3月份的第一天，他给女房东1英寸长的一段，然后每天给她增加1英寸，以此作为抵押。勘探员预期到3月份的最后一天，他能全数付清租金，而届时女房东将把银条小段全部还给他。3月份有31天，一种办法是把银条切成31段，每段长1英寸。可是这处花很多功夫。勘探员希望既履行协议，又能使银条的分段数目尽量减少。例如，他可以第一天给女房东1英寸的一段，第二天再给1英寸的一段，第三开他取回这两段1英寸的而给她3英寸的一段。假设银条的各段是按照这种方式来回倒换的话，勘探员至少需要把他的银条切成______段？ [问题3]:\换不开的钞票\
钱柜里有1.15美分，一位顾客提出：把1美元的钞票换成硬币，但出纳小姐说换不开，后来这位顾客提出：把50美分的钞票换成硬币，但出纳小姐又说换不开，而实际上，出纳小姐也无法把25美分、10美分、5美分的钞票换成硬币。请问钱柜里到底有哪些硬币？他们分别有多少枚？ 答：_________________。
三、写出程序的运行结果：（每小题6分，共30分）1. program text1; const n=6;m=3; var i,j,k:integer; begin
for i:=-n to n do begin
k:=n-abs(i);
write(' ': 39-k); for j:=-k to k do if abs(j)>k-m
9
then write(n-(i+n)div 2) else write(' '); writeln; end; end.
输出的结果为： 2. PROGAM text2；
VAR a:ARRAY[1..10] OF Char； k:Integer； ch:Char； BEGIN
FOR k:=1 TO 10 DO a[k]:=Chr(Ord('A')+k)； FOR k:=1 TO 10 DO BEGIN
ch:=a[k]；
a[k]:=a[11-k]； a[11-k]:=ch； END；
FOR k:=1 TO 10 DO Write(a[k])； Writeln END.
输出的结果为：
3. program text3(input,output); Var m,n,p:integer; x:real;
procedure mm(var m:integer;x:real); var n:integer; begin
m:=m+1; n:=m+1; x:=n*3; p:=n; end; begin
m:=8;n:=5;p:=3;x:=1.0; mm(n,x);
writeln (m:5,n:5,p:5,x:6:1); end.
输出的结果为： 4. program text4; const n=5;
type ary=array[0..n-1,0..n-1]of integer; var a:ary;i,j,k:integer; begin
for i:=0 to n-1 do
10