全国青少年信息学奥林匹克联赛初赛练习卷new答案

全国青少年信息学奥林匹克联赛初赛练习卷（九）答案(普及组PASCAL语言 二小时完成) 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 1. 一棵树T有2个度数为2的结点、1个度数为3的结点、3个度数为4的结点，那么树T有（ ）个树叶。A. 14 B. 6 C. 18 D. 7设树T有n个结点、m条边。；边数为结点的度数之和，即m=2*2+1*3+3*4=19，n=m+1=20。N个结点中有1+2+3=6个分支结点，有叶结点20-6=14个。2. 在一棵二叉树中，假设n0、n1、n2分别是度数为0、1、2的顶点数，则下列判断中正确的是（ ）。A. n0=n2+1 B. n1=n0+1 C. n2=n0+1 D. n2=n0+1设二叉树共有N个结点，有B条边。则N=N0+N1+N2，B=N1+N2*2，又因为除根外的每个结点都有一条边进入，所以N-1=B。综合以上三式，有N0+N1+N2-1=N1+N2*2，故N 0=N2+1。3. 若一个具有N个顶点、K条边的无向图是森林，则此森林中有（ ）棵树。A. K B. N C. N - K D. 1因为每棵树中除根以外的每个结点有且仅有一条入边，所以每棵树的边数=结点数-1，即森林中树的棵数为“结点数 - 边数”。4. 设G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。A. 6 B. 8 C. 9 D. 10该图分为两个连通分量，且其中一个连通分量只有一个结点，另一个连通分量是一个无向完全图。这时，图中的顶点是最少的；又因为n个顶点构成的无向完全图最多有(n(n-1)/2条边，因此，(n(n-1)/2=28的最小正整数解即为除孤立点之外最少顶点个数，而此题答案为n+1，解上式得n=8，所以结果为n+1=9。5. 评价一个算法的好坏有多种指标，下列各个指标：正确性运行时间占用空间迭代次数简单性中是算法的评价指标的是（ ）。A. B. C. D. 6. 在流程图的符号中，菱形框一般作为（ ）。 A. 起止框 B. 输入输出框 C. 判断框 D. 处理工作框7. 算法的三种结构是（ ）。A. 顺序、分支、循环 B. 顺序、重复、循环C. 顺序、分支、判断 D. 顺序、流程、循环8. 汉字国标码GB2312-80收入的汉字有6763个，其中一级汉字有（ ）个。（二级有3008个）A. 3755个 B. 3008个 C. 682个 D. 3690个9. 在程序设计语言中，一个过程通常由四个要素组成：过程名、一组称为（ ）的名字所组成的参数表、过程中的说明部分、过程体。A. 值参数 B. 变量参数 C. 实在参数 D. 形式参数10. 按照网络覆盖范围和计算机之间相距的远近，计算机网络可以分为（ ）。A. 广域网和局域网 B. 信息交换网和广域网 C. 分布式系统和集中式系统 D. 公用网和专用网11. 连接在Internet上的任何一台计算机，都有自己的（ ）。 A. 网址 B. 域名 C. IP地址 D. 网页12. 下列IP地址中正确的是（ ）。 A. 202.300.12.4 C. 100:128:35:91 D. 111-102-35-2113. 因特网不属于任何个人，也不属于任何组织，其中在网络知识这一块中，有一个英文缩 写ISP，它的中文意思是（ ）。（若问的是ICP，则含义为“因特网信息内容提供商”，如新浪网公司等）A. 因特网连接 B. 因特网使用 C. 因特网设计 D. 因特网服务提供商14. Windows系统对信息进行管理和使用是以（ ）为基本单位的。A. 文件 B. 盘片 C. 字节 D. 命令15. 中缀表达式A -（B+C/D）* E的后缀形式是（ ）。A. ABC+D/E* B. ABC+D/-E* C. ABCD/E*+- D. ABCD/+E*-可以先画出对应的表达式二叉树，再对其进行后根遍历即可。16. 已知待排序的N个元素可分为N / K个组，每个组包含K个元素，且任一组内的各元素均分别大于前一组内的所有元素、小于后一个组内的所有元素，那么，若采用基于比较的排序算法，其时间下界为（ ）。A. O(nlog2n) B. O(nlog2k) C. O(klog2n) D. O(klog2k)在计算那些基于比较的排序算法的时间下界时，会自然地想起快速排序等时间复杂度为O(log2n)的算法，对每组进行的排序，每个时间复杂度是O(klog2k)，共有N/K组，所以总的时间复杂度为O(n/k*klog2k)=O(nlog2k)。而题目给出任何一组内各元素均分别大于前一组内的所有元素、小于后一个组内的所有元素，故只需在每一个分组内进行排序，就达到了整个数列排序的目的。17. 下列各排序算法中，最坏情况下的时间复杂度最低的是（ ）。A. 堆排序 B. 选择排序 C. 快速排序 D. 插入排序因为最坏情况对堆排序的影响不大，其时间复杂度仍为O(nlog2n)。18. 设有一个1.100, 1.100的二维数组A，其每个元素Ai,j存储时占两个字节，将A数组按行优先的顺序存入从SA开始的连续存储单元中，则元素A66，65存储的结束地址为（ ）。A. SA+13130 B. SA+13129 C. SA+6565 D. SA+656419. 在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出打印的数据依次写入该缓冲区，而打印机从该缓存区中取出数据打印。该缓冲区是一个（ ）结构。A. 堆栈 B. 队列 C. 数组 D. 线性表20. 一个汉字的机内码目前通常用二个字节来表示：第一个字节是区位码的区号加（160）10；第二个字节是区位码的位码加（160）10 。 已知：汉字“却”的区位码是4020，试写出机内码两个字节的二进制的代码：A. 11001000，10110100 B. 11001001，10110101C. 11001010，10110110 D. 11001100，10111100二、问题求解1. 下面是一个利用完全二叉树特性，用顺序表来存储的一棵二叉树，结点数据为字符型（结点层次号从小到大，同一层从左到右顺序存储，#表示空结点，表示存储数据结束）。 现要求画出对应该存储结构的二叉树示意图。（7分） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B C # # D E # # # # # G F 答：对应该存储结构的二叉树示意图为：AFG EDCB2. 为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为前缀运算符在前，如X/Y写为/XY 和后缀 运算符在后，如X/Y写为XY/的表达形式。 在这样的表示中可以不用括号即可确定求值的顺序，如： （P+Q）*（R-S）*+PQ-RS 或 PQ + RS -* 试将下面的表达式改写成前缀与后缀的表示形式： A+B*C/D A-C*D+BE 试将下面的前缀表示还原成中缀的表示形式，同时写出后缀表示：+A *BC 前缀式中表示一元运算符取负号，如A表示（-A）答： 前缀形式为：+A/*BCD；后缀形式为：ABC*D/+ 前缀形式为：+-A*CDBE；后缀形式为：ACD*-BE+ 中缀形式为（-A）+B*（-C）；后缀形式为：ABC*+3 一个将角编了号的正三角形可以进行如下二种运动： (a) 沿过顶点1的高H翻转1800，我们将这个运动用字母a来表示： 1 1 h a h 2 3 3 2 图一 图二 (b) 沿过三角形的外心，垂直于三角形所在平面的有向轴L（注意：三角形翻转时L轴也随着翻转的），按右手法则旋转1200（右手法则是指用右手大拇指指向L轴的方向，由其余四指决定旋转方向的法则），我们将这样的运动用字母b来表示： 1 3 L L h b h 2 3 1 2 如果将a,b作为运算对象，并将两个运动连续进行看作是一种运算（这里不妨也称为乘法）则对图一的三角形而言，aa的结果便成为： 1 2 h h aa 2 3 3 1若将运动前后的三角形状态简称为元素，那么三角形状态就可与运动的表达式关联。据此，请回答下列问题： 从图一的三角形的原始状态出发，可以运动出多少种不同状态的三角形，试写出最简单的运算表达式（借助于a,b与乘法运算）； 这样定义的乘法运算是否符合交换律与结合律？ 如果将三角形的某种状态运动回到原始状态称之为该元素的逆元素，例如： 1 3 1 b bb 2 3 1 2 2 3 bb的逆元素为b ,可以表示为（bb）-1 =b 试求：（1）a-1 = （2）（ab）-1 = (3) (aa)a) -1 = (4) b-1 = 答： 可有如下6种情况：（1）b （2）bb或b2或aba （3）bbb或b3或aa（4）a （5）ab或b2a或bba （6）abb或ab2或ba 符合结合律而不符合交换律（1）a-1=a （2）(ab)-1=bba （3）(aa)a)-1=a （4）b-1=bb三、阅读程序1. program exp9_3_1; var i, s, max : integer; a : array 1.10 of integer; begin for i := 1 to 10 do read (ai); max := a1;s := a1; for i := 2 to 10 do begin if smax then max：=s end; writeln(max=, max) end. 输入：-2 13 -1 4 7 8 -1 -18 24 6 输出：max=422. program ex9_3_2;var i, j, k : integer; a : array0.100of integer; begin for i := 0 to 100 do ai := i; for k := 5 downto 2 do begin for i := 1 to 100 do if ( i mod k) = 0 then ai := 0; for i := 1 to 99 do for j := 1 to 100 - i do if aj aj+1 then begin aj := aj + aj+1; aj+1 := aj - aj+1; aj := aj - aj+1; end; end; j := 1; while (aj = 0) and (j100) do j := j + 1; for i:=j to 100 do a0 := a0 + ai; writeln(a0); end. 本题的运行结果是: 970 3. 设数组a1，a2，an中已存入了数据，调用不同的排序程序，则数据比较的次数将会不同，试计算分别调用下列不同的排序过程后，所执行的比较运算的次数。其中swap（i，j）表示ai与aj进行交换。（1）procedure sort1（n：integer）； var i，j ：integer ； begin for i：=1 to n-1 do for j：=1 to n do if aj ai then swap (i,j); end; 调用该过程的语句为sort1（n），比较运算的次数为：_ n(n-1)_。（2）procedure sort2（i，n：integer）； var j ：integer ； begin if i= n then write（an） else for j := i + 1 to n do begin if aj 0 dobegin j := 5; while (j 0) and (bj = 10 + j - 5) do j := j - 1; if j 0 then begin s := s + 1; bj := bj + 1; for i := j + 1 to 5 do bi := bj + i - j end;end; writeln(s=, s); end.输出结果为：s=252四、完善程序1、求出两个整形数组错位相加的最大面积 1）数组面积的定义：（限定数组头尾不为0）481216111 设有一个数组C=（4，8，12，0，6） 则C的面积为： Sc=(4+8)/2 + (8+12)/2 + 12/2 + 6/2也就是说，Sc=各梯形面积之和（其中梯形的高约定为1，三角形作为梯形的特殊情况处理）。 又如D=(12, 24, 6)时，其面积的定义为Sd=(12+24)/2 + (24+6)/22461211 2）数组错位相加的定义 设有2个正整数的数组a，b，长度为n，当n=5时： a=(34,26,15,44,12) b=(23,46,4,0,18) 对a、b进行错位相加，可能有下列情况 34 26 15 44 12 +) 23 46 4 0 18 34 26 15 44 12 23 46 4 0 18 或： 34 26 15 44 12 +） 23 46 4 0 18 - 34 26 15 44 35 46 4 0 18 或： 34 26 15 44 12 +） 23 46 4 0 18 34 26 15 67 58 4 0 18 或： 最后有： 34 26 15 44 12 +) 23 46 4 0 18 - 23 46 4 0 18 34 26 15 44 12 可以看到：由于错位不同，相加的结果也不同。 【程序要求】找出一个错位相加的方案，使得输出的数组面积为最大。 【算法提要】设a，b的长度为10，用a,b: array1.10 of integer表示，其结果用数组C, D : array1.30 of integer表示。错位相加的过程可以从开始不重叠，然后逐步重叠，再到最后的不重叠。 梯形面积的计算公式为：(上底+下底)高2 其中由于约定高为1，故可写为（上底+下底）2。【程序清单】const n = 10; function sea : real; 计算数组c面积 begin j1 := 1; while _ cj1=0 and j1j1_ do j2 := j2 - 1; if j1 = j2 then sea := 0 else begin j3 := cj1 + cj2; for j4 := j1 + 1 to j2 - 1 do inc(j3,cj4*2); sea := j3 / 2 end; end;end; of function seabegin main program for i := 1 to n do read(ai); for j := 1 to n do read(bj); _ s:=0_; for i := 1 to 2 * n + 1 do beginfor j := 1 to 3 * n do _ cj:=0;_ for j := 1 to n docj + n := aj; for j := 1 to n do _ci+j-1:=ci+j-1+bj_; p := sea; if p s then begin d := c; s := p end; end; of for loop for i := 1 to 3 * n do write(dI, ); write(s); end.2. 设有一个实数，以字符串形式存放于数组x中，用x：array1.nof char表示。其中x1若为-，表示负数；若为+、.或 ，则表示正数。若为数字，也认为是正数。 例如 x = ( , 2, 0, , 3, ., 5, %) 表示203.5 x = (-, 1, ., , 2, 0, %) 表示-1.2 约定：在字符串x中，除x1外，其后可以包含有若干个.与 ，但仅以第一次出现的为准，空格不起任何作用，并以字符%作为结束标志。【程序要求】将输入的字符串还原成实数输出（小数点后无用的0应除去），还原的结果以下列形式存放（不需要输出）。 F：数符。正数放0，负数放1。 A：array1.N of integer; 存放数字，不放小数点。 K：表示A中有效数字的个数。 J：表示小数点后的位数。 例如：数203.24，还原后结果的存放是： F=0 A=(2, 0, 3, 2, 4) K=5 J=2 又如：数-33.0740，还原后结果的存放是： F=1 A=(3, 3, 0, 7, 4) K=5 J=3【数据结构及算法提要】数组x : array1.10 of char;可放长度定为10；首先读入字符串，然后处理数的符号，在还原的过程中，需要判定整数部分与小数部分，同时去除多余的空格和小数点，并约定输入是正确的，不用作出错检查。【主要程序片段】 for i := 1 to 10 do ai := 0; for i := 1 to 10 do read(xi); j := 0; f := 0; k := 0; b := 0; if x1 = - then begin _ f：=1；_ _ i：=2； end else if x1 := then i := 2 else i := 1; endif; endif; while _（xi= ）and （i10）_ do i := i + 1; endwhile while _ xi %_ do beginif (xi = 0) and (xi 0 then while ak=0 do begin _ j:=j-1;_ _ k:=k-1;_ end;end.3. 积木游戏设有n 个小木块排成一排，如下图： 游戏开始时，每个小木块向下的一面涂有红、黄、蓝三种颜色之中的一种（约定：0表示红色，1表示黄色，2表示兰色）。要求通过翻看与交换方式对小木块重新排列（翻看的规则为每个小木快只能看一次），最终成为下面的形状： 红 蓝 黄亦即，相同颜色的木块排列在一起，设计一个翻看与交换的方案，使得用最少的交换次数实现上面的要求。【算法描述】翻看小木块时，可以从两端进行。例如，设中间状态如下： A B C 红 未翻过 蓝 黄此时，可以从两个方向看，即从A或B处开始：（1）若看A则有三种可能性：为红色，则不用交换为兰色，交换一次，即A与B交换为黄色，交换两次，即C与B交换一次，然后A与C再交换一次此时，平均交换次数为1。（2）若看B，也有三种可能性：为兰色，则不用交换为红色，交换一次，即B与A交换。为黄色，交换一次，即B与C交换。此时，平均交换次数为2/3。由此可见，从B处翻看直到游戏结束，次数最少符合题目要求。【程序清单】const n=20;var i,tem,r,b,y:integer; a:array1.n of 0.2;begin for i:=1 to n do read(ai); r:=1; 1 b：=n； ; y:=n; while 2 r=b doif 3 ab=0 then begin tem:=ar;ar:=ab;ab:=tem; r:=r+1endelse if 4 ab=1 then begin tem:=ab;ab:=ay;ay:=tem; 5 y：=y-1 ; 6 b：=b-1； ;endelse b:=b-1 for i:=1 to n do write(ai:3)end.