2013noip初赛提高组试题解析.doc

19.2 十九届提高组 一、单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项） 1．一个32位整型变量占用（ A ）个字节。 A．4 B．8 C．32 D．128 2．二进制数11.01在十进制下是（ A ）。 A．3.25 B．4.125 C．6.25 D．11.125 3．下面的故事与（ B ）算法有着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事…………………………’” A．枚举 B．递归 C．贪心 D．分治 4．1948年，（ D ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。 A．冯?诺伊曼(John von Neumann) B．图灵（Alan Turing） C．欧拉（Leonhard Euler） D．克劳德?香农（Claude Shannon） 【分析】 香农信息论鼻祖 5．已知一棵二叉树有2013个节点，则其中至多有（ A ）个节点有2个子节点。 A．1006 B．1007 C．1023 D．1024 【分析】（1）树根深度为0，深度为10的满二叉树节点总数2047； （2）本题树深为10的完全二叉树，与满二叉树相比少了34个节点， （3）深度为9的满二叉树节点总数量为1023； （4）1023-（34/2）=1006 6．在一个有向图中，如果任意两点之间都存在路径相连，则称其为连通图。右图是一个有5个顶点、8条边的连通图。若要使它不再是连通图，至少要删去其中的（ B ）条边。 A．2 B．3 C．4 D．5 【分析】要使图不联通，只要其中某一个节点不连通即可，所有顶点度最少是3，所以最少需要删除3条边 7．斐波那契数列的定义如下：F1=1，F2=1，Fn=Fn-1+Fn-2（n≥3）。如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为（ D ）。 function F(n:longint):longint; begin if n=2 then F:=1 else F:=F(n-1)+F(n-2); end; A．O(1) B．O(n) C．O(n2) D．O(Fn) D ），将不会产生冲突，其中a mod b表示a除以b的余数。 A．x mod 11 B．x2 mod 11 C．2x mod 11 D．mod 11，其中表示下取整 D ）位地址的IPv6协议所取代。 A．40 B．48 C．64 D．128 11．二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么12个顶点的二分图至多有（ C ）条边。 A．18 B．24 C．36 D．66 【分析】二分为6个和6个的顶点，此时边最多，有36条边。 12．（ B ）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制编码，以满足跨语言、跨平台的文本交换。目前它已经收录了超过十万个不同字符。 A．ASCII B．Unicode C．GBK2312 D．BIG5 【分析】 UNICODE与ASCII的区别 . 1.ASCII的特点 （1）ASCII 是用来表示英文字符的一种编码规范。每个ASCII字符占用1 个字节，因此，ASCII 编码可以表示的最大字符数是255（00H—FFH）。这对于英文而言，是没有问题的，一般只什么用到前128个(00H--7FH,最高位为0)。而最高位为1 的另128 个字符（80H—FFH）被称为“扩展ASCII”，一般用来存放英文的制表符、部分音标字符等等的一些其它符号。 （2）但是对于中文等比较复杂的语言，255个字符显然不够用。于是，各个国家纷纷制定了自己的文字编码规范，其中中文的文字编码规范叫做“GB2312—80”， 它是和ASCII 兼容的一种编码规范， 其实就是利用扩展ASCII没有真正标准化这一点，把一个中文字符用两个扩展ASCII 字符来表示，以区分ASCII 码部分。 但是这个方法有问题，最大的问题就是中文的文字编码和扩展ASCII 码有重叠。而很多软件利用扩展ASCII 码的英文制表符来画表格，这样的软件用到中文系统中，这些表格就会被误认作中文字符，出现乱码。另外，由于各国和各地区都有自己的文字编码规则，它们互相冲突，这给各国和各地区交换信息带来了很大的麻烦。 2.UNICODE的产生 （1）要真正解决这个问题，不能从扩展ASCII 的角度入手，UNICODE