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

全国青少年信息学奥林匹克联赛初赛练习卷（九）全国青少年信息学奥林匹克联赛初赛练习卷（九）答案答案 (普及组 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 B. C. 100:128:35:91 D. 111-102-35-21 13. 因特网不属于任何个人，也不属于任何组织，其中在网络知识这一块中，有一个英文 缩 写 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. 设有一个1100, 1100的二维数组 A，其每个元素 Ai,j存储时占两个字节，将 A 数 组按行优先的顺序存入从 SA 开始的连续存储单元中，则元素 A66，65存储的结束地 址为（ ） 。 A. SA+13130 B. SA+13129 C. SA+6565 D. SA+6564 19. 在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区， 主机将要输出打印的数据依次写入该缓冲区，而打印机从该缓存区中取出数据打印。 该缓冲区是一个（ ）结构。 A. 堆栈 B. 队列 C. 数组 D. 线性表 20. 一个汉字的机内码目前通常用二个字节来表示：第一个字节是区位码的区号加（160） 10；第二个字节是区位码的位码加（160）10 。 已知：汉字“却”的区位码是 4020，试写出机内码两个字节的二进制的代码： A. 11001000，10110100 B. 11001001，10110101 C. 11001010，10110110 D. 11001100，10111100 二、问题求解二、问题求解 1.下面是一个利用完全二叉树特性，用顺序表来存储的一棵二叉树，结点数据为字符型 （结点层次号从小到大，同一层从左到右顺序存储，#表示空结点，表示存储数据结 束） 。 现要求画出对应该存储结构的二叉树示意图。 （7 分） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C # # D E # # # # # G F 答： 对应该存储结构的二叉树示意图为： 2.为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为前缀运算符在前， 如 X/Y 写为/XY 和后缀 运算符在后，如 X/Y 写为 XY/的表达形式。 在这样的表示中可以不用括号即可确定求值的顺序，如： （P+Q）*（R-S）*+PQ-RS 或 PQ + RS -* 试将下面的表达式改写成前缀与后缀的表示形式： A+B*C/D A-C*D+BE A FG E D C B 试将下面的前缀表示还原成中缀的表示形式，同时写出后缀表示： +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 110 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=42 2.program ex9_3_2; var i, j, k : integer; a : array0100of 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 (j 0 do begin 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） 设有一个数组 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)/2 24 4 8 1 2 1 6 111 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: array110 of integer 表示，其结果用数组 C, D : array130 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 126 11 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 sea begin 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 begin for j := 1 to 3 * n do _ cj:=0;_ for j := 1 to n do cj + 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：array1nof char 表示。其中 x1若为-，表示负数；若为+、.或 ，则表示正数。若为数字，也认为是正数。 例如 x = ( , 2, 0, , 3, ., 5, %) 表示 203.5 x = (-, 1, ., , 2, 0, %) 表示-1.2 约定：在字符串 x 中，除 x1外，其后可以包含有若干个.与 ，但仅以第一次出现的 为准，空格不起任何作用，并以字符%作为结束标志。 【程序要求程序要求】 将输入的字符串还原成实数输出（小数点后无用的 0 应除去） ，还原的结果以下列形式 存放（不需要输出） 。 F：数符。正数放 0，负数放 1。 A：array1N 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 : array110 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 （i %_ do begin if (xi = 0) and (xi 0 then while ak=0 do begin _ j:=j-1;_ _ k:=k-1;_ end; end. 3.积木游戏