ccf考试题目及答案

NOIP2011普及组初赛（Pascal）参考答案一、BBCCB DBBCC BACCC DAAAC二(1) 128(2) 3(ABCDEFG BCDEFG BADEFG BADECG)三(1) 165(n..m的自然数求和)(2) 22366472011(手机键盘输入CCFNOIP2011要按什么键)(3) 3(中位数)(4) 20(杨辉三角)四.1(1) read(b[i][j]);或 read(b[i,j])(2) m1 - m2 + 1(3) good := true;(4) m2(5) haveAns := true;四.2(1) [i + j - 1](2) [i]:= [i] mod 10(3) [i] + [i] + [i](4) [i] mod 2(5) inc()(6) < (7) 48(8) times(middle, middle), target

CCF NOIP2011普及组（Pascal语言）参考答案与评分标准一、单项选择题（共20题，每题分，共计30分）1 2 3 4 5 6 7 8 9 10 B B C C B D C B C C 11 12 13 14 15 16 17 18 19 20 B A C C C D A A A C二、问题求解（共2题，每题5分，共计10分）1．1282．3三、阅读程序写结果（共4题，每题8分，共计32分）1．1652． 223664720113． 34．20四、完善程序（前11空，每空2分，后2空，每空3分，共计28分）（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查）1．① read(b[i][j])② m1 - m2 + 1③ good := true④ m2⑤ haveAns := true2．① [i + j - 1]② [i] := [i] mod 10;③ [i] + [i] + [i];④ [i] mod 2 (或 [i] and 1)⑤ inc() （或 := + 1）⑥ < ⑦ ord('0') (或48）⑧ times(middle, middle), target

数组下标不能使用用变量

scanf("%d %d",&n,&m);int sum[n];char a[n][3],b[m][3];for(i=0;i

单选就算了吧太多了~~~ 答案：A二、不定项选择题（共10题，每题分，共15分。每题有一个或多个正确选项。多选或少选均不得分。）（这部分较难得分，我错了很多题）1. 如果根节点的深度记为1，则一棵恰有2011个叶子结点的二叉树的深度可能是（ ）。A. 10B. 11C. 12D. 2011答案：CD2. 在布尔逻辑中，逻辑“或”的性质有（ ）。（原题ABCD选项里的或是个类似V的表示或的符号，为了该文档流通方便我都改成了“V”）A. 交换律：PVq=qVpB. 结合律：P V（Q V R）=（P V Q）V RC. 幂等律：P V P = PD. 有界率：P V 1 = 1 （1表示逻辑真）答案：ABCD3. 一个正整数在十六进制下有100位，则它在二进制下可能有（ ）位。A. 399B. 400C. 401D. 404答案：AB4. 汇编语言（ ）。A. 是一种与硬件无关的程序设计语言B. 在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试C. 可以直接访问寄存器、内存单元、I/O端口D. 随着高级语言的诞生，如今已完全被淘汰，不再使用答案：BC5. 现有一段文言文，要通过二进制哈弗曼编码进行压缩。简单起见，假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、400。那么，“也”字的编码长度可能是（ ）。A. 1B. 2C. 3D. 4答案：BC6. 生物特征识别是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下属于生物特征识别技术及其应用的是（ ）。A. 指静脉验证B. 步态验证C. ATM机密码验证D. 声音验证答案：ABD7. 对于序列“7、5、1、9、3、6、8、4”，在不改变顺序的情况下，去掉（ ）会使逆序对的个数减少. 7B. 5C. 3D. 6答案：CD8. 计算机中的数值信息分为整数和实数（浮点数）。实属之所以能表示很大或者很小的数是由于使用了（ ）。A. 阶码B. 补码C. 反码D. 较长的位数答案：A9. 对右图使用Dijkstra算法计算S点到其余各点的最短路径长度时，到B点的距离d【B】初始时赋值为8，在算法的执行过程中还会出现的值有（ ）。（原试题右图，为照顾手机党我字述边集（(a,b,c)代表a到b有条长c的边）：(S,A,2)，(S,B,8)，(S,D,3)，(A,B,5)，(B,C,1)，(B,D,3)，(C,D,1)A. 3B. 7C. 6D. 5答案：BCD10. 为计算机网络中进行数据交换而建立的规则、标准或约定的**称为（原题写的是“成为”）网络协议。下列英文缩写中，（ ）是网络协议。A. HTTPB. TCP/IPC. FTPD. WWW答案：ABC三、问题求解（共2题，每题5分，共计10分）1.平面图是可以画在平面上，且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至多有6条边，如右图所示。那么，5个顶点的平面图至多有____条边。（图我就不画了，比较简单，是一个口画一条对角线，然后没有对角线的那2个点从口外面连了一条曲线）答案：92.定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串“BCA”，可以将A移到B之前，变成字符串“ABC”。如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”，最少需要____次操作。答案：4四、阅读程序写结果（共4题，每题8分，共计32分）1. constSIZE=100;varn,i,sum,x:integer;A:array[1..SIZE]of integer;beginreadln(n);fillchar(a,sizeof(a),0);for i:=1 to n dobeginread(x);inc(a[x]);end;i:=0;sum:=0;while sum<(n div 2 + 1) dobegininc(i);sum:=sum+a[i];end;writeln(i);end.输入：114 5 6 6 4 3 3 2 3 2 1输出：__________答案：32. 啊varn:ineger;procedure f2(x,y:integer);forward;procedure f1(x,y:integer);beginif x ans thenans:=len;for i:=1 to n doif (not visited(i)) and(e[x,i] <> -1) thendfs(I,len+e[x,i]);visited[x] := false;end;beginreadln(n,m);for i:=1 to n dofor j:=1 to n doe[i][j] := -1;for i:=1 to m dobeginreadln(a,b,c);e[a][b]:=c;e[b][a]:=c;end;for i:=1 to n dovisited[i]:=false;ans:=0;for i:=1 to n dodfs(i,0);writeln(ans);end.输入：4 61 2 102 3 203 4 304 1 401 3 502 4 60输出：______答案：1504. 啊constSIZE = 10000;LENGTH = 10;varsum : longint;n,m,I,j : integer;a:array[1..SIZE , 1..LENGTH]of integer;function h(u , v :integer):integer;varans,i : integer;beginans:=0;for i:=1 to n doif a[u][i] <> a[v][i] theninc(ans);h := ans;end;beginreadln(n);fillchar(a,sizeof (a),0);m:=1;repeati := 1;while (i <=n) and (a[m][i] =1 ) doinc(i);if i>n thenbreak;a[m][i]:=1;for j:=i + 1 to n doa[m][j] := a[m-1][j];until false;sum := 0;for i := 1 to m dofor j := 1 to m dosum := sum + h(i,j);writeln(sum);end.输入：7输出：______答案：57344五、完善程序（第一题，每空2分，第二题，每空3分，共计28分）1.（大整数开方）输入一个正整数n（1<=n<10^100）,试用二分法计算它的平方根的整数部分。constSIZE=200;typehugeint = recordlen : integer;num : array[1..SIZE] of integer;end;//len表示大整数的位数；num[1]表示个位、num[2]表示十位，以此类推（这个注释不是我带鱼灰写的，是原试题带有的）vars : string;i : integer;target, left, middle, right : hugeint;function times(a, b : hugeint) : hugeint;vari, j : integer;ans : hugeint;beginfillchar(ans,sizeof(ans),0);for i:=1 to dofor j:=1 to do① :=[i + j - 1] + [i] * [j];for i:=1 to [i + 1] := [i + 1] + [i] div 10;② if [ + ] > 0then := + := + - 1;end;times := ans;end;function add(a,b : hugeint) : hugeint;vari : integer;ans: hugeint;beginfillchar((),0);if > := := ;for i := 1 to [i]:=③；[i+1] := [i+1] + [i] div 10;[i] := [i] mod 10;end;if [ + 1]>0then inc();add := ans;end;function average(a,b: hugeint) : hugeint;vari : integer;ans : hugeint;beginans := add(a,b);for i:= downto 2 [i-1] := [i-1] + (④) *10;[i]:=[i] div 2;end;[1]:=[1] div 2;if [] = 0then dec();average := ans;end;function plustwo(a : hugeint) : hugeint;vari : integer;ans : hugeint;beginans := a;[1] := [1] + 2;i:=1;while (i <= ) and ([i] >= 10) [i + 1] := [i + 1] + [i] div 10;[i] := [i] mod 10;inc(i);end;if [ + 1] > 0then ⑤；plustwo := ans;end;function over(a , b: hugeint) : boolean;vari: integer;beginif (⑥) thenbeginover := false;exit;end;if > thenbeginover := true;exit;end;for i := downto 1 dobeginif [i] < [i] thenbeginover := false;exit;end;if [i] > [i] thenbeginover := true;exit;end;end;over := false;end;beginreadln(s);fillchar((),0); := length(s);for i := 1 to [i] := ord(s[ - i +1]) - ⑦;fillchar((left,num),0);;[1]:=1;right:=target;repeatmiddle:=average(left,right);if over(⑧)then right := middleelse left := middle;until over(plustwo(left),right);for i:= downto 1 dowrite([i]);writeln;end.答案：① [i+j-1]② [i]:=[i] mod 10③ [i]+[i]+[i]④ [i] mod 2⑤ inc()⑥ <⑦ ord(‘0’)⑧ times(middle,middle),target2.（笛卡尔树）对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点外，每个结点的权值都大于父结点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵树对应的笛卡尔树。现输入序列的规模n（1<=n<100）和序列的n个元素，试求其对应的笛卡尔树的深度d（根节点深度为1），以及有多少个叶节点的深度为d。constSIZE = 100;INFINITY = 1000000;varn , maxDeep, num , i : integer;a : array[1..SIZE] of integer;procedure solve(left , right , deep : integer);vari,j,min: integer;beginif deep>maxDeep thenbeginmaxDeep :=deep;num := 1;endelse if deep=maxDeep then① ;min := INFINITY;for i := left to right doif min > a[i] then beginmin := a[i];②;end;if left < j then③;if j