第十五届（2009年）信息学奥赛初赛试题答案

1、第十五届（2009年）信息学奥赛初赛试题答案一. 单项选择题 （共10题，每题1.5分，共计15分，每题有且仅有一个正确答案。） 1 、关于图灵机下面的说法哪个是正确的：答案（C） A）图灵机是世界上最早的电子计算机。B）由于大量使用磁带操作，图灵机运行速度很慢。 C）图灵机只是一个理论上的计算模型。 D）图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。最早的计算机是ENIAC    图灵机是计算机模型，没有运行速度，更谈不上磁带操作图灵机是英国人阿兰图灵提出的理论，阿兰图灵本人在二战中破译德军密码系统发挥重要作用，而不是图灵机发挥作用。图灵是英

2、国著名的数学家和逻辑学家，被称为计算机科学之父、人工智能之父，是计算机逻辑的奠基者，提出了“图灵机”和“图灵测试”等重要概念。人们为纪念其在计算机领域的卓越贡献而设立“图灵奖”。1936年，阿兰.图灵提出了一种抽象的计算模型 图灵机 (Turing Machine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作： 在纸上写上或擦除某个符号； 把注意力从纸的一个位置移动到另一个位置；“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想像得到的可计算函数。装置由一个控制器和一根假设两端无界的

3、工作带（起存储器的作用）组成。工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，它带有一个读写出一个你期待的结果。外行人看了会坠入云里雾里，而内行人则称它是“阐明现代电脑原理的开山之作”，并冠以“理想计算机”的名称。“图灵机”更在电脑史上与“冯·诺依曼机”齐名，被永远载入计算机的发展史中。回顾20世纪科学技术的辉煌发展时，不能不提及20世纪最杰出的数学家之一的冯·诺依曼（美籍匈牙利人）。20世纪40年代，冯·诺依曼在参与世界上第一台计算机-ENIAC的研制小组工作时，发现ENIAC有两个致命的缺陷：一是采用十进制运算，逻

4、辑元件多，结构复杂，可靠性低；二是没有内部存贮器，操纵运算的指令分散存贮在许多电路部件内，这些运算部件如同一副积木，解题时必须像搭积木一样用人工把大量运算部件搭配成各种解题的布局，每算一题都要搭配一次，非常麻烦且费时。 针对这两个问题，诺依曼和其他合作者一起呕心沥血地进行了半年多时间的改革性研究，结果取得了令人满意的成果。但是，由于ENIAC的制造已接近尾声，因此它未能采用诺依曼的改进意见。 诺依曼的研究成果得到了ENIAC研制小组专家的青睐，他们在ENIAC尚未竣工之前，就着手计划一个结构全新的电子计算机EDVAC方案。1945年6月底，由诺依曼执笔写出了EDVAC计划草案。在这个方案中，诺

5、依曼提出了在计算机中采用二进制算法和设置内存贮器的理论，并明确规定了电子计算机必须由运算器、控制器、存贮器、输入设备和输出设备等五大部分构成的基本结构形式。他认为，计算机采用二进制算法和内存贮器后，指令和数据便可以一起存放在存贮器中，并可作同样处理，这样，不仅可以使计算机的结构大大简化，而且为实现运算控制自动化和提高运算速度提供了良好的条件。EDVAC于1952年建成，它的运算速度与ENIAC相似，而使用的电子管却只有5900多个，比ENIAC少得多。EDVAC的诞生，使计算机技术出现了一个新的飞跃。它奠定了现代电子计算机的基本结构，标志着电子计算机时代的真正开始。 根据冯·诺依曼提

6、出的原理制造的计算机被称为冯·诺依曼结构计算机，现代计算机虽然结构更加复杂，计算能力更加强大，但仍然是基于这一原理设计的，也是冯诺依曼机。最简单的来说，他的精髓贡献是2点：2进制思想与程序内存思想。2、关于BIOS下面的说法哪个是正确的：答案（A）A）BIOS是计算机基本输入输出系统软件的简称。 B）BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。C）BIOS一般由操作系统厂商来开发完成。 D）BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。其实bios=Basic Input Output System。但

7、是对于是否是软件这一说法还存在争议呢！  BIOS只存一些系统启动的基本信息，这些设备的驱动程序是不存的。    BIOS一般是由单独的芯片厂家生产的，最著名的都是台湾的三家。  固件BIOS根本这些功能。BIOS是"基本输入输出系统"。其实，它是一组固化到计算机内主板上一个ROM芯片上的程序，它保存着计算机最重要的基本输入输出的程序、系统设置信息、开机后自检程序和系统自启动程序。 其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。3 、已知大写字母A的ASCII编码为65（十进制），则大写字母J的十六进制ASCII

8、编码 为：答案（D）A）48 B）49 C）50 D）以上都不是 “0”的ASCII编码为48“A”的ASCII编码为65“a”的ASCII编码为974 、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为。其对应的十进制整数应该是：答案（B）A）19 B）-19 C）18 D）-18 最高位为符号位补码 1再取反原码：1000000000010011十进制整数：-195 、一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数目为：答案（D）A)nk+1 B）nk-1 C）(k+1)n-1 D）(k-1)n+1 多叉树的性质，N0=(K-1)N+1，考试的时

9、带入K=2时候，验证二叉树能得到结果。二叉树的性质：N0=N2+1 即叶子节点比二叉节点数多一个。（1）完全二叉树的定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。特点：叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1（2）满二叉树：一棵深度为k，且有2的(k)次方1个节点的二叉树特点：每一层上的结点数都是最大结点数满二叉树肯定是完全二叉树完全二叉树不一定是满二叉树一棵深度为K且有2的K次方减1个结点的二叉树称为满二叉树。深度为K的，

10、有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至N的结点一一对应，称之为完全二叉树。            0                  0            &

11、#160;   0          /                  /               /     

12、       0     0             0     0          0     0      

13、60;  /     /           /                      /        0   0 0  &

14、#160;0     0                      0   0           (1)        

15、0;        (2)             (3)1、是满二叉树，也是完全二叉树。2、是完全二叉树。3、非完全二叉树。简单的讲，将节点按层次从1-n编号：             1         &

16、#160;/             2      3        /     /       4   5 6   7  . . . .缺少的节点只能是大号的，即：如果n号节点存在，则1到

17、n-1号节点必定存在， 同样，若n号节点不存在，则n+1号及更大号的节点也必定不存在可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0n21，则n= n0n1n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n11，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0（n1）/2或n0n/2，合并成一个公式：n0（n1）/2，就可根据完全二叉树的结点总数计算出叶子结点数。6 、表达式a*(b+c)-d的后缀表达式是：答案（B）A)abcd*+- B）abc+*d

18、- C）abc*+d- D）-+*abcd   主要是考树的遍历，要明白前缀、中缀和后缀表达式。  构造二叉树，操作数做叶子节点，运算符做非叶节点。按中序遍历就可以得到中缀表达式。根据所给表达式（其实正常的都是中缀表达式）可以构造二叉树 * d a + b c中缀表达式就是中序遍历a*(b+c)-d后缀表达式就是后续遍历abc+*d-前缀表达式就是前序遍历-*a+bcd7 、最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码：答案（B）A）（00，01，10，11

19、）B）（0，1，00，11） C）（0，10，110，111） D）（1，01，000，001） 0是00的前缀码，这部分是数据结构中哈夫曼编码处的知识。哈夫曼编码从哈夫曼树根结点开始，对左子树分配代码“0”，右子树分配代码“1”，一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。例，对电文 EMCAD 编码。若等长编码，则 EMCAD => 000001010011100 共15位设各字母的使用频度为 E,M,C,A,D=1,2,3,3,4。用频度为权值生成哈夫曼树，并在叶子上标注对应的字母，树枝分配代码“0”或“1”:各字母的编码即为哈夫曼编

20、码： EMCAD => 000001011011 共12位8 、快速排序平均情况和最坏情况下的算法时间复杂度分别为：答案（A）A）平均情况O(nlog(2,n)，最坏情况O(n2) B）平均情况O(n)，最坏情况O(n2) C）平均情况O(n)，最坏情况O(nlog(2,n) D）平均情况O(log(2,n)，最坏情况O(n2) 最好的时候是n×log（2，n），最坏情况的是退化成冒泡排序，复杂度为O（n2）。选择排序：O(n2)冒泡排序：O(n2)计数排序：O(n2)比较排序：O(log(2,n)-1.44n)堆排序： O(log(2,n)9 、左图给出了一个加权无向图，从顶

21、点V0开始用prim算法求最小生成树。则依次加 入最小生成树的顶点集合的顶点序列为：答案（A）A）V0，V1，V2，V3，V5，V4 B）V0，V1，V5，V4，V3，V3 C）V1，V2，V3，V0，V5，V4 D）V1，V2，V3，V0，V4，V5 加入的边依次为v0v1、v1v2、v1v3（或v2v3）、v1v5、v3v4。Prim算法用于求无向图的最小生成树。假设V是图中顶点的集合,E是图中边的集合,设图G =（V，E），其生成树的顶点集合为U。、把v0放入U。、在所有uU，vV-U的边(u，v)E中找一条最小权值的边，加入生成树。、把找到的边的v加入U集合。如果U集合已有n个元素，则

22、结束，否则继续执行。其算法的时间复杂度为O(n2) 做法：任取一个顶点加入生成树，然后对那些一个端点在生成树中，而另一个端点不在生成树中的边进行排序，取权值最小的边，将它和另一个端点加进生成树中。重复步骤直到所有顶点都加进了生成树。加入的边依次为v0v1、v1v2、v1v3（或v2v3）、Prim算法实现： （1）集合：设置一个数组set(i=0,1,.,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1） （2）图用邻接矩阵或邻接表表示，路径不通用无穷大表示，在计算机中可用一个大整数（如 1 << 30）代替。 10、全国信息学奥林匹克的官方网站为

23、参与信息学竞赛的老师同学们提供相关的信息 和资源，请问全国信息学奥林匹克官方网站的网址是：答案（C）A）w.noi / B）C）D） 二、.不定项选择题（共10题，每题1.5分，共计15分，每题正确答案的个数不少于1。多选或少选均不得分）。答案（AB）1、关于CPU下面哪些说法是正确的： A）CPU全称为中央处理器（或中央处理单元）。 B）CPU能直接运行机器语言。 C）CPU最早是由Intel公司发明的。 D）同样主频下，32位的CPU比16位的CPU运行速度快一倍。 Intel最早发明的是微处理器，而CPU之前就由电子管、晶体管实现 位数只能说明处理的字长，所在的系统硬

24、件指令不同，速度很难说谁快。1、64bit CPU拥有更大的寻址能力，最大支持到16GB内存， 32bit支持4G内存，而16bit只支持64K内存（1M）。2、64位CPU一次可提取64位数据，比32位提高了一倍，理论上性能会提升1倍。但这是建立在64bit操作系统，64bit软件的基础上的（30%）。WindowsXP 64位2、关于计算机内存下面的说法哪些是正确的：答案（BD） A）随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。B）一般的个人计算机在同一时刻只能存/取一个特定的内存单元。C）计算机内存严格来说包括主存（memory）、高速缓存（c

25、ache）和寄存器（register）三个部分。D）1MB内存通常是指1024*1024字节大小的内存。 一般是对字节的一个单元串行操作。1MB=1024KB=1024*1024BRAM不是位置随机，而是随时访问，所谓“随机存取”，指的是当存储器中的消息被读取或写入时，所需要的时间与这段信息所在的位置无关。 高速缓存和寄存器的物理实现是集成在CPU中，这两部分不属于冯诺依曼体系中的五大部分的任意一个部分。3、关于操作系统下面说法哪些是正确的：答案（BC）A.多任务操作系统专用于多核心或多个CPU架构的计算机系统的管理。 B.在操作系统的管理下，一个完整的程序在运行过程中可以被部分存放在内存中。

26、 C.分时系统让多个用户可以共享一台主机的运算能力，为保证每个用户都得到及时的响应通常会采用时间片轮转调度的策略。 D.为了方便上层应用程序的开发，操作系统都是免费开源的。 多任务系统可以是单个CPU构架的，普通的PC都是多任务的。 操作系统不是都免费开源4、关于计算机网络，下面的说法哪些是正确的：答案（C）A）网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方案。 B）新一代互联网使用的IPv6标准是IPv5标准的升级与补充。 C）TCP/IP是互联网的基础协议簇，包含有TCP和IP等网络与传输层的通讯协议。 D）互联网上每一台入网主机通常都需要使用一个唯一的IP地址，否则就必须注

27、册一个固定的域名来标明其地址。网络协议分层不是为了兼容，而是根据网络分层模型来的。 新的IPv6是IPv4的升级。 即使注册了域名也要有IP地址的。5、关于HTML下面哪些说法是正确的：答案（BD）A）HTML全称超文本标记语言，实现了文本、图形、声音、乃至视频信息的统一编码。 B）HTML不单包含有网页内容信息的描述，同时也包含对网页格式信息的定义。 C）网页上的超链接只能指向外部的网络资源，本网站网页间的联系通过设置标签来实现。 D）点击网页上的超链接从本质上就是按照该链接所隐含的统一资源定位符（URL）请求网络资源或者网络服务。 没有都统一编码本网站页面也可以用超链接，就是绝对路径。也可

28、以用相对路径。6、若3个顶点的无权图G的邻接矩阵用数组存储为0，1，11，0，10，1，0，假定在具体存储中顶点依次为：v1，v2，v3 关于该图，下面的说法哪些是正确的：答案（ABD）A）该图是有向图。 B）该图是强联通的。 C）该图所有顶点的入度之和减所有顶点的出度之和等于1。 D）从v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。 可以画出这个有向图，矩阵存储的时候，矩阵为非对称，故为有向图。        入度之和等于出度之和。7、在带尾指针（链表指针clist指向尾结点）的非空循环单链表中每个结

29、点都以next字段的指针指向下一个节点。假定其中已经有了2个以上的结点。下面哪些说法是正确的：答案（AC）A）如果p指向一个待插入的新结点，在头部插入一个元素的语句序列为： p.next:=clist.next;clist.next:=p; B）如果p指向一个待插入的新结点，在尾部插入一个元素的语句序列为： p.next:=clist;clist.next:=p; C）在头部删除一个结点的语句序列为： p:=clist.next;clist.next:=clist.next.next;dispose(p); D）在尾部删除一个结点的语句序列为： p:=clist;clist:=clist.ne

30、xt;dispose(p);  B应为p.next:=clist.next;clist.next:=p;  D中要循环找到尾指针的上一个元素才能进行删除8、散列表的地址区间为0-10，散列函数为H(K)=K mod 11。采用开地址法的线性探查法处理冲突，并将关键字序列26，25，72，38，8，18，59存储到散列表中，这些元素存入散列表的顺序并不确定。假 定之前散列表为空，则元素59存放在散列表中的可能地址有：答案（ABC）A）5 B）7 C）9 D）10 选择ABCD   哈希函数的冲突避免  计算各个的散列值26&#

31、160;  25    72    38    8    18    59                  5     4   

32、    6       5    8      7      4 这样就可能5的顺序：25、59          7的顺序：25、26、38、59        

33、60; 9的顺序：25、26、38、18、59 10的顺序：59 上面的顺序不是唯一的。9、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪些排序算法是稳定的：答案（ABCD）A）插入排序 B）基数排序 C）归并排序 D）冒泡排序            在编程实现的时候，只要控制好边界都是可以达到稳定排序的。10、在参加NOI系列竞赛过程中，下面哪些行为是被严格禁止的：答案（BCD）A）携带书写工具，手表和不具有通讯功能的电子词典进入赛场。B）在联机测

34、试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。 C）通过互联网搜索取得解题思路。D）在提交的程序中启动多个进程以提高程序的执行效率。     A有时候是可以的。这里考的是NOI，不是NOIP。三.、问题求解（共2题，每空5分，共计10分） 1.拓扑排序是指将有向无环图G中的所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v>E(G)，则u在线性序列 中出现在v之前，这样的线性序列成为拓扑序列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为_432_。用排列组合，先确定12346的顺序，然后将7

35、插入内部有两个位置可选（可将7放在4钱前或4后），然后将5插入时候（如在123476中插入5，五应在1的后面就可以，则有6种情况，当然在123746中也一样），可以有6个位置选择。最后，放89的时候，考虑两种情况，89在一起，有8个位置选（可放在1前或者1的后面都可以）；89不在一起，8个位置选2个。              C(2,1)×C(6,1)×C(8,1)+C(8,2)=2×6×(8+28)=4322、某个国家的钱

36、币面值有1，7，72，73共计四种，如果要用现金付清10015元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通_35_张钱币。可以判断用29张73的钱，用一张72的钱，此时还剩余19元，可用2张7元的和五张一元的解决，但这时一元用的太多我们可以给对方一张七元的让对方找两张一元的就可以，这样只用到29+1+2（七元）+1（七元）+2（一元）共35张，而第一种方法需要更多一些    10015化成7进制数是41125，正常是4×7+1=29张73面额的，1张72面额，2张7面额的，5张1面额的。     因为可以无限且找零，并要求最少流通数量。这样就把7进制上大于等于4的数a，用找零