(参考答案)第十三届初赛模拟试题(提高组pascal试题).doc

NOIP2008提高pascal第十三届全国青少年信息学奥林匹克联赛初赛模拟试题（ 提高组pascal 语言二小时完成 ）全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效一、 单项选择题 （共 10 题，每题 1.5 分，共计 15 分。每题有且仅有一个正确答案.）。1、字符串“ababacbab”和字符串“abcba”的最长公共子序列是（ ）。A. abcbaB. cbaC. abcD. abE. bcba2、计算机里如果用四个字节表示有符号的整数，则整数的范围最大的是：( ) A.-231+1到231-1 B. -231到231-1C. -231到231 D. -231+1到2313、设循环队列中数组的下标范围是1-n，其中头尾指针分别是f和r，则其元素个数是：( ) Ar-f Br-f+1C(r-f) MOD n+1D(r-f+n) MOD n+14、128KB的存储器用十六进制表示，它的最大的地址码是( ) A)10000 B)EFFF C)1FFFF D)FFFFF E)FFFF5、已知A=11001010B,B=00001111B,C=01011100B,则ABC=( )B A)01011110 B)00001111 C)01011100 D)11001110 E)110010106、下列关于十进制数100的正确说法是( ). A)原码为01100100B B)反码为64H C)反码为9BH D)补码为64H E)补码为9BH7、设a、b、c是三个布尔型(boolean)的变量，则表达式(ab)(bc)(ca)(aa)(bb)的值（ ）。 A. 始终为true B. 始终为false C. 当且仅当c为true时为false D. 当且仅当a与b均为true时为true E.依赖于a、b、c三者的值 8、一个三叉树（即每个节点最多有三个孩子）中，有k个孩子的结点数目表示为S(k)，则下列关系一定成立的是（ ）。 A. S(0)=2*S(3)+S(2)-1 B. S(0)3*S(3)+2*S(2)-1 C. S(0)3*S(3)+2*S(2)+1 D. S(0)2*S(3)+S(2) E. S(0)=6)，在任意两个点之间连一条弦，假设任何3条弦在圆的内部都没有公共点，问这些弦彼此相交能在圆内构成多少个三角形(只要求写出三角形总数的表示式而无需化简)? 提示：下图是N=6的情况，图中所示的4个三角形从某种意义上说具有一定的代表性。C(N,3)+4C(n,4)+5*C(n,5)+6*C(n,6) （是否有6倍）四阅读程序（共 4 题，每题 8 分，共计 32 分）第一题：var p,q:array0.5 of integer;i,x,y:integer;beginy:=20;for i:=0 to 4 do read(pi);readln;q0:=(p0+p1)+(p2+p3+p4) div 7;q1:=p0+p1 div (p2+p3) div p4);q2:=p0*p1 div p2;q3:= -q0*q1 mod 2;q4:=q1+q2+q3;x:=(q0+q4+2)-p(q3+3) mod 4;if (x10) theny:=y+(q1*100-q3) div (pp4 mod 3*5)elsey:=y+20+(q2*100-q3) div (pp4 mod 3*5);writeln(x,y);end./*注：本例中，给定的输入数据可以避免分母为0 或数组元素下标越界。 */输入：6 6 5 5 3输出：25，46第二题：var n:1.9;procedure diamond(m:integer); procedure line(k:integer); var j:integer; begin write(:10-k); for j:=1 to 2*k-1 do if j0 dobegini:=i+1; s:=n mod 16; n:=n div 16; end; write(h=);for j:=i downto 1 do write(hsj+1); writeln; end. 运行程序： 输入：n=347592输出：h=54DC8第四题：program ex4;var s:array0.99of integer; ii,i,j,n,swap:integer; r:boolean;procedure swp(i:integer; j:integer);var tmp:integer; begin tmp:=si; si:=sj; sj:=tmp; end; procedure rev(i:integer; j:integer);begin while ij do begin swp(i,j); inc(i);dec(j); end;end;beginread(n);for i:=0 to n-1 do read(si);i:=n-1;while true dobegin ii:=i; dec(i); if sisii then begin j:=n; repeat j:=j-1; until sisj; swp(i,j); rev(ii,n-1); break; end;end;for i:=0 to n-1 do write(si, );end. 输入：15 14 2 12 64 13 815 310 119 7 51 输出：14 2 12 64 13 815 3 11 1 5 7 9 10 求下一个全排列五完善程序 (前 5 空，每空 2 分，后 6 空，每空 3 分，共 28 分)第一题： 取余运算【问题描述】输入b，p，k的值，求bp mod k的值。其中b，p，k*k为长整型数。【样例】mod.inmod.out2 10 9210 mod 9=7【知识准备】进制转换的思想、二分法。【算法分析】下面先介绍一个原理：a*b mod k(a mod k)*(b mod k)mod k。 这是一个典型的分治问题，具体实现的时候是用递推的方法来处理的，如p=19，有19=2*9+1，9=2*4+1，4=2*2+0，2=2*1+0，12*0+1，反过来，我们可以从0出发，通过乘以2再加上一个0或1而推出1，2，4，9，19，这样就逐步得到了原来的指数，进而递推出以b为底，依次以这些数为指数的自然数除以k的余数。不难看出这里每一次乘以2后要加的数就是19对应的二进制数的各位数字，即1，0，0，1，1，而19(10011)2，求解的过程也就是将二进制数还原为十进制数的过程。program mod1;var b,p,k,i,len,rest,temp:longint; binary:array1.32 of longint;begin readln(b,p,k); 输入三个数 len:=0; temp:=p; while temp0 do 存放p的二进制转换 begin len:=len+1; binarylen:=temp mod 2; temp:=temp div 2 end; rest:=1; for i:=len downto 1 do 用二分法实现bp mod k begin temp:=rest*rest mod k; if binaryi=1 then rest:=b mod k * temp mod k else rest:=temp end; writeln(b,p,mod,k,rest); 输出bp mod kend.第二题：售货员的难题 【问题描述】 某乡有n个村庄(1n40)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0s1000)是已知的，且A村到B村与B村到A村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为1，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。【输入】村庄数n和各村之间的路程(均是整数)。【输出】最短的路程。【样例】salesman.in salesman.out3 村庄数30 2 1 村庄1到各村的路程1 0 2 村庄2到各村的路程2 1 0 村庄3到各村的路程【算法分析】 题目给定的村庄数不多(40)，所以可以用回溯的方法，从起点(第一个村庄)出发找出所有经过其他所有村庄的回路，计算其中的最短路程。当村庄数n比较大时这种方法就不太适用了。用一个过程road(step，line：byte)来描述走的状况，其中step是当前已到村庄数、line是当前所在的村庄。如果stepn，下面只能回起点了，直接看第line个村庄到第一个村庄的路程加上已走的总路程，如果比最小值还小则替换最小值(要保存路径的话也可保存，这是回溯算法的优点，考虑到达最小值的路径可能不止一条，不便于测试，题目没要求输出路径)。如果step还小于n，那么将还没有到过的村庄一个一个地试过去，再调用下一步road(step+1，新到的村庄号)。program salesman;var a:array1.40,1.40 of byte; n,i,j:byte; min ,m :longint; bj:array1.40 of boolean;procedure init;beginreadln(n); for i:=1 to n do for j:=1 to n do read(ai,j); fillchar(bj,sizeof(bj),true); min:=99999999; m:=0;end;procedure road(step,line:byte);var i,j,k:byte;begin if step=n then if m+aline,1min then min:=m+aline,1 else else for i:=2 to n do if (iline) and bji then begin m:=m+aline,i; bjline:=false; if m min then road(step+1,i); m:=m-aline,i; bjline:=true; end;end;procedure print;beginwriteln(min);end;begin init; road(1,1); printend.答题卷 姓名：一. 单项选择题 （共 10 题，每题 1.5 分，共计 15 分。每题有且仅有一个正确答案.）。题号1245678910选择二不定项选择题 （共 10 题，每题 1.5 分，共计 15 分。多选或少选均不得分）。题号11121314151617181920选择三问题解答（每题 5 分，共 10 分）1. 答： 2. 答： 四. 阅读程序，并写出程序的正确运行结果：