第十五届(2009年)全国青少年信息学奥赛试题及答案.doc

第十五届(2009年)(共10题,,共计15分,每题有且仅有一个正确答案。)1、关于图灵机下面的说法哪个是正确的:图灵机是世界上最早的电子计算机。由于大量使用磁带操作,图灵机运行速度很慢。图灵机只是一个理论上的计算模型。图灵机是英国人图灵发明的,在二战中为破译德军的密码发挥了重要作用。答案(C)2、关于BIOS下面的说法哪个是正确的:BIOS是计算机基本输入输出系统软件的简称。BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。BIOS一般由操作系统厂商来开发完成。BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。答案(A)3、已知大写字母A的ASCII编码为65(十进制),则大写字母J的十六进制ASCII编码为:A)48B)49C)50D)以上都不是答案(D)4、在字长为16位的系统环境下,一个16位带符号整数的二进制补码为 11111**********。其对应的十进制整数应该是:A)19B)-19C)18D)-18答案(B)5、一个包含n个分支结点(非叶结点)的非空满k叉树,k>=1,它的叶结点数目为:nk+1B)nk-1C)(k+1)n-1D)(k-1)n+1答案(D)6、表达式a*(b+c)-d的后缀表达式是:abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd答案(B)7、最优前缀编码,也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码,以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码:A)(00,01,10,11)B)(0,1,00,11)C)(0,10,110,111)D)(1,01,000,001)答案(B)8、快速排序平均情况和最坏情况下的算法时间复杂度分别为:平均情况O(nlog(2,n)),最坏情况O(n^2)平均情况O(n),最坏情况O(n^2)平均情况O(n),最坏情况O(nlog(2,n))平均情况O(log(2,n)),最坏情况O(n^2)答案(A)9、左图给出了一个加权无向图,从顶点V0开始用prim算法求最小生成树。则依次加入最小生成树的顶点集合的顶点序列为:V0,V1,V2,V3,V5,V4V0,V1,V5,V4,V3,V3V1,V2,V3,V0,V5,V4V1,V2,V3,V0,V4,V5答案(A)10、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源,请问全国信息学奥林匹克官方网站的网址是:p://p://p://(C)