全国青少年信息学奥林匹克联赛初赛练习卷（九）全国青少年信息学奥林匹克联赛初赛练习卷（九）答案答案(普及组 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. 192.168.0.3 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，10110101 C. 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 答：对应该存储结构的二叉树示意图为：2.为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为前缀运算符在前， 如 X/Y 写为/XY 和后缀 运算符在后，如 X/Y 写为 XY/的表达形式。在这样的表示中可以不用括号即可确定求值的顺序，如：（P+Q）*（R-S）*+PQ-RS 或 PQ + RS -* 试将下面的表达式改写成前缀与后缀的表示形式：A+B*C/D A-C*D+BEAFG EDCB 试将下面的前缀表示还原成中缀的表示形式，同时写出后缀表示：+A *BC 前缀式中表示一元运算符取负号，如A 表示（-A） 答：前缀形式为：+A/*BCD；后缀形式为：ABC*D/+前缀形式为：+-A*CDBE；后缀形式为：ACD*-BE+ 中缀形式为（-A）+B*（-C） ；后缀形式为：ABC*+3一个将角编了号的正三角形可以进行如下二种运动：(a) 沿过顶点 1 的高 H 翻转 1800，我们将这个运动用字母 a 来表示：1 1h a h2 3 3 2图一 图二(b) 沿过三角形的外心，垂直于三角形所在平面的有向轴 L（注意：三角形翻转时 L 轴也随着翻转的） ，按右手法则旋转 1200（右手法则是指用右手大拇指指向 L 轴的方向，由其余四指决定旋转方向的法则） ，我们将这样的运动用字母 b 来表示：1 3 L Lh b h2 3 1 2如果将 a,b 作为运算对象，并将两个运动连续进行看作是一种运算（这里不妨 也称为乘法）则对图一的三角形而言，aa 的结果便成为：1 2h h aa 2 3 3 1若将运动前后的三角形状态简称为元素，那么三角形状态就可与运动的表达式关 联。据此，请回答下列问题：从图一的三角形的原始状态出发，可以运动出多少种不同状态的三角形，试写出 最简单的运算表达式（借助于 a,b 与乘法运算） ； 这样定义的乘法运算是否符合交换律与结合律？ 如果将三角形的某种状态运动回到原始状态称之为该元素的逆元素，例如：1 3 1b bb2 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;beginfor i := 1 to 10 do read (ai);max := a1;s := a1;for i := 2 to 10 dobeginif smax then max：=send;writeln(max=, max)end. 输入：-2 13 -1 4 7 8 -1 -18 24 6输出：