省淳中信息学奥赛辅导 奥赛试题解析
19.2 十九届提高组
一、单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项） 1．一个32位整型变量占用（ A ）个字节。
A．4
B．8
C．32
D．128
D．11.125
2．二进制数11.01在十进制下是（ A ）。
A．3.25
B．4.125
C．6.25
3．下面的故事与（ B ）算法有着异曲同工之妙。
从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事??????????’”
A．枚举
B．递归
C．贪心
D．分治
4．1948年，（ D ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。
A．冯?诺伊曼(John von Neumann) C．欧拉（Leonhard Euler） 【分析】 香农信息论鼻祖
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
B．图灵（Alan Turing）
D．克劳德?香农（Claude Shannon）
F:=1
F:=F(n-1)+F(n-2);
1
else
省淳中信息学奥赛辅导 奥赛试题解析
end; A．O(1)
B．O(n)
C．O(n2)
D．O(Fn)
【分析】计算F1需要1次，计算F2需要一次，计算Fn需要计算F(n-1)的次数加上F（n-2）的次数，所以其实就是计算Fn次，于是答案选择D，至于这个Fn到底是多大，数学上可以计算，它等于O((（1+sqrt(5)）/2)^n).
8．二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树
上所有节点的值。那么，二叉查找树的（ B ）是一个有序序列。 A．先序遍历
B．中序遍历
C．后序遍历
D．宽度优先遍历
9．将（2，6，10，17）分别存储到某个地址区间为0～10的哈希表中，如果哈希函数h(x)=
（ D ），将不会产生冲突，其中a mod b表示a除以b的余数。 A．x mod 11 C．2x mod 11
D．
B．x2 mod 11
?x?mod 11，其中?x?表示
x下取整
【分析】A项6和17对11取余都是6发生冲突，B项10的平方和17的平方对11取余都是1发生冲突，C项6的两倍和17的两倍对11取余都是1发生冲突，D项分别为1，2，3，4，不冲突
10．IPv4协议使用32位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被使
用（ D ）位地址的IPv6协议所取代。 A．40
B．48
C．64
D．128
11．二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那
么12个顶点的二分图至多有（ C ）条边。 A．18
12．（ B ）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制
编码，以满足跨语言、跨平台的文本交换。目前它已经收录了超过十万个不同字符。 A．ASCII 【分析】
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没有真正标准化这一点，把一个中文字符
2
B．24 C．36 D．66
【分析】二分为6个和6个的顶点，此时边最多，有36条边。
B．Unicode C．GBK2312 D．BIG5
省淳中信息学奥赛辅导 奥赛试题解析
用两个扩展ASCII 字符来表示，以区分ASCII 码部分。
但是这个方法有问题，最大的问题就是中文的文字编码和扩展ASCII 码有重叠。而很
多软件利用扩展ASCII 码的英文制表符来画表格，这样的软件用到中文系统中，这些表格就会被误认作中文字符，出现乱码。另外，由于各国和各地区都有自己的文字编码规则，它们互相冲突，这给各国和各地区交换信息带来了很大的麻烦。 2.UNICODE的产生
（1）要真正解决这个问题，不能从扩展ASCII 的角度入手，UNICODE作为一个全新的编码
系统应运而生，它可以将中文、法文、德文??等等所有的文字统一起来考虑，为每一个文字都分配一个单独的编码。 3.什么是UNICODE
Unicode与ASCII一样也是一种字符编码方法，它占用两个字节（0000H—FFFFH）,容纳65536
个字符，这完全可以容纳全世界所有语言文字的编码。在Unicode 里，所有的字符都按一个字符来处理， 它们都有一个唯一的Unicode 码。
13．把64位非零浮点数强制转换成32位浮点数后，不可能（ D ）。
A．大于原数
B．小于原数 C．等于原数 D．与原数符号相反
【分析】64位非零浮点数强制转换成32位浮点数，两个数会有大小上的细微差别，但不会发生符号变化，因为有专门的符号位
14．对一个n个顶点、m条边的带权有向简单图用Dijkstr算法计算单源最短路时，如果不使
用堆或其它优先队列进行优化，则其时间复杂度为（ B ）。
A．O(mn+n3) B．O(n2) C．O((m+n)log n) D．O((m+n2)log n) 【分析】Dijkstra算法（双重for 循环）计算单源最短路时间复杂度如果不借助堆或优先队列优化，是O（n^2）.
15．T(n)表示某个算法输入规模为n时的运算次数。如果T(1)为常数，且有递归式
T(n)=2*T(n / 2)+2n，那么T(n) = （ B ）。
A．Θ(n) B．Θ(n log n) C．Θ(n2) D．Θ(n2log n) 【分析】Θ的含义和“等于”类似，而大O的含义和“小于等于”类似 设 N×(1 / 2) ^X=1 ,X=log2N
T(n)=2*T(n / 2)+2n=2×(2×（T（n / 4）+2×(n / 2))+2n=22×T（n / 4）+(2n) ×2 =2X×T（1）+(2n) ×X =2 ^ log2N ×T（1）+(2N) ×log2N =N +(2N) ×log2N= O(N ×log2N)
二、不定项选择题（共5题，每题1.5分，共计7.5分；每题有一个或多个正确选项，多选或
3
省淳中信息学奥赛辅导 奥赛试题解析
少选均不得分）
1．下列程序中，正确计算1，2，?，100这100个自然数之和sum（初始值为0）的是（ AC ）。
2．（ AD ）的平均时间复杂度为O(n log n)，其中n是待排序的元素个数。
A．快速排序
B．插入排序
C．冒泡排序
D．归并排序
【分析】只有快速排序和归并排序是n log n的，冒泡和插入都是n^2的时间复杂度。 3．以A0作为起点，对下面的无向图进行深度优先遍历时（遍历的顺
序与顶点字母的下标无关），最后一个遍历到的顶点可能是（ CD ）。
A．A1 B．A2 C．A3 D．A4
4．（ AB ）属于NP类问题。
A．存在一个P类问题 B．任何一个P类问题 C．任何一个不属于P类的问题
D．任何一个在（输入规模的）指数时间内能够解决的问题 【分析】 1. 时间复杂度：
（1）时间复杂度：是指执行算法所需要的计算工作量。 时间复杂度并不是表示一个程序
解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。
（2）多项式时间算法：如果一个算法，它能在以输入规模为参变量的某个多项式的时间
内给出答案，则称它为多项式时间算法。
4
省淳中信息学奥赛辅导 奥赛试题解析
2. P类、NP类问题
（1）P类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，
那么这个问题就属于P问题。
（2）NP类问题：NP（Non-deterministic Polynomial）问题是指可以在多项式的时间里
验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。
（3）所有的P类问题都是NP问题。 NP问题不是非P类问题
3. NPC问题（NP完全问题）：Cook 在1971年给出并证明了有一类问题具有下述性质： （1）这类问题中任何一个问题至今未找到多项式时间算法；
（2）如果这类问题中存在一个问题有多项式时间算法，则这类问题都有多项式时间算法
这类问题就是所谓的NP完全问题。
（3）NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先，它
得是一个NP问题；然后，所有的NP问题都可以约化到它。
5
2013NOIP初赛提高组试题解析
