1、第十八届全国青少年信息学奥林匹克联赛初赛 （普及组 Pascal 语言试题） 竞赛时间：2012 年 10 月 13 日 14:3016:30 选手注意 试题纸共有 10 页，答题纸共有 2 页，满分 100 分。请在答题纸上作答，写在试题纸上一律无效。 不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料 一、单项选择题（共 20 题，每题 1.5 分，共计 30 分；每题且仅有一个正确选项） 1. 计算机如果缺少（ A） ，将无法正常启动。 A. 内存 B. 鼠标 C. U 盘 D. 摄像头 2. （B ）是一种先进先出的线性表。A. 栈 B. 队列 C. 哈希表（散列表）
2、 D. 二叉树解析：1. 栈的定义(可参考：http:/ ，另一端称为栈底（Bottom ） 。(2)当表中没有元素时称为空栈。(3)栈为后进先出 （Last In First Out）的线性表，简称为 LIFO 表。栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中“最新“的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。2.队列：定义：队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。（1）允许删除的一端称为队头（Front） 。（2）允许插入的一端称为队尾（Rear） 。（3）当队列中没有元素时称为空队列。（4）队
3、列亦称作先进先出（First In First Out）的线性表，简称为 FIFO表。队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许“加塞“ ） ，每次离开的成员总是队列头上的（不允许中途离队） ，即当前“最老的“ 成员离队。【例】在队列中依次加入元素 a1，a2，an 之后，a1 是队头元素，an 是队尾元素。退出队列的次序只能是 a1，a2，an。3. 哈希表(散列表)散列方法是使用函数 h 将 U 映射到表 T0.m-1的下标上（m=O(|U|)） 。这样以 U 中关键字为自变量，以 h 为函数的运算结果就是相应结点的存储地址。从而达到在 O(1)时间内就可完成查找
4、。哈希表存在散列表的冲突现象：两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym) 。【例】上图中的 k2 k5，但 h(k2)=h(k5)，故 k2 和 K5 所在的结点的存储地址相同。-4. 在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树” （left subtree）和“右子树” （ right subtree）,次序不能颠倒。二叉树的 5 种形态：二叉树的遍历：3. 目前计算机芯片（集成电路）制造的主要原料是（ A） ，它是一种可以在沙
5、子中提炼出的物质。 A. 硅 B. 铜 C. 锗 D. 铝 4. 十六进制数 9A 在（B ）进制下是 232. A. 四 B. 八 C. 十 D. 十二 解析：9A 十六, 先转化成十进制 9*162-1 +10*161-1 十进制154 十进制, 再转化成二进制=10011010 二进制10 011 010 (从最右边起三个一组,分别转换成十进制数字, 就得到八进制表示的数) =2 3 2 八进制 注： 十进制,八进制和十六进制互化应以二进制作为桥梁，将二进制转化成 16或 8 进制：以小数点为界分别向左右每 4（或 3）个数字为一组进行分组，每组分别转化成二进制数，最后合并在一起，并把首
6、 0 去掉（尾 0 不可以去） 。如：( 001 101 001)2=(151)8 (0001 0110.0101 1011)2=(16.5B)165.（ C）不属于操作系统。 A. Windows B. DOS C. Photoshop D. NOI Linux 6. 如果一棵二叉树的中序遍历是 BAC，那么它的先序遍历不可能是（ C） 。 解析：从题目 “中序遍历是 BAC”得知:还原此二叉树可能是以下几种情况:A. ABC +中序遍历是 BAC，还原得到： B. CBA +中序遍历是 BAC，还原得到：C. ACB 还原得到： 这两个树的中序遍历都不是 BAC。D. BAC 中序遍历是
7、BAC，还原得到：前序：先根节点，然后遍历左子树,最后遍历右子树，根-左-右。 中序：先遍历左子树，再是根节点，最后遍历右子树，左-根-右 后序：先遍历左子树，再遍历右子树，最后是根节点，左-右-根在每个左右子树也遵守以上各自规则！7. 目前个人电脑的（B ）市场占有率最靠前的厂商包括 Intel、AMD 等公司。 A. 显示器 ：三星，LG，戴尔，宏碁，HP B. CPU ： INTEL ，AMD，台湾 VIA 威盛. .C. 内存 ：金士顿 Kingston，威刚，海盗船等 D. 鼠标 ：双飞燕雷柏(Rapoo)罗技(Logitech) 大水牛. .8. 使用冒泡排序对序列进行升序排列，每
8、执行一次交换操作系统将会减少 1 个逆序对，因此序列 ：5,4,3,2,1 需要执行（ C）次操作，才能完成冒泡排序。 A. 0 B. 5 C. 10 D. 15 冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第 1 个和第 2 个数，将小数放前，大数放后。然后比较第 2 个数和第 3 个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第 2 个数和第 3 个数的交换，使得第 1 个数不再小于第 2 个数） ，将
9、小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的） ，第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数） 。如此下去，重复以上过程，直至最终完成排序。此题答案：冒泡排序最多要排 n*(n-1)/2 次（本题这样的原本序列是逆序列） ，最少要 n-1次 冒泡次数（由小到大的正序列） 。9. 1946 年诞生于美国宾夕法尼亚大学的 ENIAC 属于（A ）计算机。 A. 电子管：电子管元件在运行时产生的热量太多，可靠性较差，运算速度不快，价格昂贵，体积庞大，这些都使计算机发展受到限制B. 晶体管 ：1954 年，美国贝尔实验室研制成功第一台使用
10、晶体管线路的计算机，取名“催迪克”（TRADIC ） ，装有 800 个晶体管。晶体管不仅能实现电子管的功能，又具有尺寸小、重量轻、寿命长、效率高、发热少、功耗低等优点C. 集成电路 ：1958 年，美国德州仪器的工程师 Jack Kilby 发明了集成电路（IC） ，将三种电子元件结合到一片小小的硅片上。更多的元件集成到单一的半导体芯片上，计算机变得更小，功耗更低，速度更快D. 超大规模集成电路 ：60 年代初期，美国的基尔比和诺伊斯发明了集成电路，引发了电路设计革命。随后，集成电路的集成度以每 3-4 年提高一个数量级的速度增长。大规模集成电路 (LSI) 可以在一个芯片上容纳几百个元件。
11、到了 80 年代，超大规模集成电路 (VLSI) 在芯片上容纳了几十万个元件，后来的甚大规模集成电路(ULSI) 上将数量扩充到百万级。 使得计算机的体积和价格不断下降，而功能和可靠性不断增强。10. 无论是 TCP/IP 模型还是 OSI 模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层” ，以下最恰当的是（ A） 。 分层思想是：对等层之间执行相同的操作，较低的层为它的上一层提供服务。下面左边是 OSI 模型，右边是 OSI 与 TCP/IP 模型对比：A. 中国公司的经理与波兰公司的经理交互商业文件 :B. 军队发布命令:C. 国际会议
12、中，每个人都与他国地位对等的人直接进行会谈:D. 体育比赛中，每一级比赛的优胜者晋级上一级比赛 :11.矢量图（Vector Image）图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋转等都不会失真，是因为它（B ） 。 A. 记录了大量像素块的色彩值来表示图像 B. 用点、直线或者多边形等基于数学方程的几何图元来表示图像 C. 每个像素点的颜色信息均用矢量表示 D. 把文件保存在互联网，采用在线浏览的方式查看图像 位图使用我们称为像素的一格一格的小点来描述图像，放大易失真矢量图用点、直线或者多边形等基于数学方程的几何图元来表示图像，放大不易失真12. 如果一个栈初始时为空，且当前栈
13、中的元素从栈底到栈顶依次为a，b，c，另有元素 d 已经出栈，则可能的入栈顺序是（ D）。 A. a, d, c, b B. b, a, c, d C. a, c, b, d D. d, a, b, c 解析：不管 d 在哪个位置，abc 的顺序肯定是先 a 后 b , 最后 c 入栈的。13. （B ）是主要用于显示网页服务器或者文件系统的 HTML 文件的内容，并让用户与这些文件交互的一种软件。 A. 资源管理器 B. 浏览器 C. 电子邮件 D. 编译器 14. （C ）是目前互联网上常用的 E-mail 服务协议。 A. HTTP B. FTP C. POP3 D. Telnet 解析
14、：HTTP：超文本传输协议；FTP：文件传输协议POP3 是 Post Office Protocol 3 的简称，即邮局协议的第 3 个版本,它规定怎样将个人计算机连接到 Internet 的邮件服务器和下载电子邮件的电子协议。它是因特网电子邮件的第一个离线协议标准,POP3 允许用户从服务器上把邮件存储到本地主机（即自己的计算机）上, 同时删除保存在邮件服务器上的邮件，而 POP3 服务器则是遵循 POP3 协议的接收邮件服务器，用来接收电子邮件的。SMTPSMTP 的全称是“Simple Mail Transfer Protocol”，即简单邮件传输协议。它是一组用于从源地址到目的地址传
15、输邮件的规范，通过它来控制邮件的中转方式。SMTP 协议属于 TCP/IP 协议簇，它帮助每台计算机在发送或中转信件时找到下一个目的地。SMTP 服务器就是遵循 SMTP 协议的发送邮件服务器。15. （ C ）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题直到最后的子问题可以简单地直接求解。而原问题的解就是子问题解的合并。 A. 动态规划 B. 贪心 C. 分治 D. 搜索 当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几
16、个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。给你一个装有 1 6 个硬币的袋子。1 6 个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币，工具是天平称。你可以一个一个称,最终也能找出伪币。这样要称 10 多次。如果用分治方法，把 1 6 硬币分为 AB 两组，每组 8 个硬币。轻的一组有伪币，假设 B是轻的那一组，因此再把它分成两组，每组有 4 个硬币。称其中一组为 B1，另一组为B2。比较这两组，肯定有一
17、组轻一些。如果 B1 轻，则伪币在 B1 中，再将 B1 又分成两组，每组有两个硬币，称其中一组为 B1a，另一组为 B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。这样只要 4 次就可以找出伪币。16. 地址总线的位数决定了 CPU 可直接寻址的内存空间大小，例如地址总线为 16 位，其最大的可寻址空间为 64KB。如果地址总线是 32 位，则理论上最大可寻址的内存空间为（D ） 。 A. 128KB B. 1MB C. 1GB D. 4GB 216=64K 232=（216
18、）*（216）4294967296/1024/1024/1024=4G 17. 蓝牙和 Wi-Fi 都是（ C）设备。 A. 无线广域网 B. 无线城域网 C. 无线局域网 D. 无线路由器 短程无线 10100 米左右 遇到阻碍更短18. 在程序运行过程中，如果递归调用的层数过多，会因为（A ）引发错误。 A. 系统分配的栈空间溢出 B. 系统分配的堆空间溢出 C. 系统分配的队列空间溢出 D. 系统分配的链表空间溢出 19. 原字符串中任意一段连续的字符所组成的新字符串称为子串。则字符“AAABBBCCC”共有（C ）个不同的非空子串。 A. 3 B. 12 C. 36 D. 45 穷举：
19、1 个字符：3 种，2 个字符：5 种，3 个字符 7 种，4 个字符 6 种，5 个字符 5 种，6 个字符 4 种，7 个字符 3 种，8 个字符 2 种，9 个字符 1 种。共 36 种不同的连续非空子串。20. 仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，并将这些原理移植于新兴的工程技术中。以下关于仿生学的叙述，错误的是（ B） A. 由研究蝙蝠，发明雷达 B. 由研究蜘蛛网，发明因特网 C. 由研究海豚，发明声纳 D. 由研究电鱼，发明伏特电池 A1938 年，研究蝙蝠领域的鼻祖 Griffin 在哈佛大学生物系学习期间，做过试验，把蝙蝠的眼睛手术
20、掉，蝙蝠的飞行不受丝毫影响，科学家经过反复研究，终于揭开了蝙蝠能在夜里飞行的秘密。它一边飞，一边从嘴里发出一种声音。这种声音叫做超声波，人的耳朵是听不见的，蝙蝠的耳朵却能听见。超声波像波浪一样向前推进，遇到障碍物就反射回来，传到蝙蝠的耳朵里，蝙蝠立刻改变飞行的方向。 科学家摹仿蝙蝠探路的办法，给飞机装上了雷达。雷达通过天线发出无线电波，无线电波遇到障碍物就反射回来，显示在荧光屏上。驾驶员从雷达的荧光屏上，能够看清楚前方有没有障碍物，所以飞机在夜里飞行也十分安全。B. 由研究海豚，发明声纳：回声定位原理，和蝙蝠差不多，介质不同，一个空气，一个水里。C.由研究蜘蛛网，发明了鱼网D 经过对电鱼的解剖
21、研究， 终于发现在电鱼体内有一种奇特的发电器官。这些发电器是由许多叫电板或电盘的半透明的盘形细胞构成的。由于电鱼的种类不同，所以发电器的形状、位置、电板数都不一样。经过对电鱼的解剖研究， 终于发现在电鱼体内有一种奇特的发电器官。这些发电器是由许多叫电板或电盘的半透明的盘形细胞构成的。由于电鱼的种类不同，所以发电器的形状、位置、电板数都不一样。电鲶的发电器起源于某种腺体，位于皮肤与肌肉之间,约有 500 万块 “电板” ，每片“电板”发电很微弱，但 500 万块“电板”却能使它发出几百伏特的电压！二、问题求解（共 2 题，每题 5 分，共计 10 分） 1. 如果平面上任取 n 个整点（横纵坐标
22、都是整数） ，其中一定存在两个点，它们连线的中点也是整点，那么 n 至少是_5_。 想象横纵交错的网格纸，就像棋盘那样的，每个横纵线交点就是一个整点。如下图如果 n=2，取两个连续的整点，那么连线中点不是整点。如果 n=3，取水平两个连续的点，垂直也两个连续的点，组成三角形。那么连线中点不是整点。如果 n=4，取四个整点组成一个正方形，则连线中点不是整点。而取 5 个点的话，必然有两个点的连线中点是整点。2. 在 NOI 期间，主办单位为了欢迎来自各国的选手，举行了盛大的晚宴。在第十八桌，有 5 名大陆选手和 5 名港澳选手共同进膳。为了增进交流，他们决定相隔就坐，即每个大陆选手左右旁都是港澳
23、选手，每个港澳选手左右旁都是大陆选手。那么，这一桌一共有_2880_种不同的就坐方案。注：如果在两个方案中，每个选手左右相邻的选手相同，则视为同一种方案。解：五个大陆人隔一个位置任意坐 5 个座位，1 个港澳人固定位置后其他 4 个港澳人任意坐剩下的 4 个位置，这样能保证不会出现每个选手左右相邻的选手相同的情况出现，故P55*P44=5*4*3*2*1 *4*3*2*1 = 2880 种 相当于 1 个圆，十个人。先随便找个座，让人去坐，有 10 个可能，然后顺时针走，下一个座就有 5 种可能，再下一个就 4 个，再下一个还是 4 个，以此类推，就是10*5*4*4*3*3*2*2*1*1。这其中有重复的，同一种坐法，可以绕着桌子走一圈，就是上一个人坐到下一个人的位置，串一下，这样所有坐法就算重复了 10 次，再除以 10 就行了。
