历届奥赛试题解析-初赛讲解

省淳中信息学奥赛辅导 奥赛试题解析

目录

19. 十九届（2013）试题 .................................................................................................................... 2

19.1 十九届普及组 ...................................................................................................................... 2 19.2 十九届提高组 ...................................................................................................................... 2 18. 十八届（2012）试题 .................................................................................................................. 20

18.1 十八届普及组 .................................................................................................................... 20 18.2 十八届提高组 .................................................................................................................... 31 17. 十七届（2011）试题................................................................................................................... 49

17.1 十七届普及组 .................................................................................................................... 49 17.2 十七届提高组 .................................................................................................................... 62 01 模拟测试 ....................................................................................................................................... 71

01.1 2014模拟测试一 ................................................................................................................ 71 01.2 2014模拟测试二 ................................................................................................................ 86 01.3 2014模拟测试三 ................................................................................................................ 99

1

省淳中信息学奥赛辅导 奥赛试题解析

19. 十九届（2013）试题

19.1 十九届普及组

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）。如果用下面的函数计算斐波

2

B．图灵（Alan Turing）

D．克劳德?香农（Claude Shannon）

省淳中信息学奥赛辅导 奥赛试题解析

那契数列的第n项，则其时间复杂度为（ D ）。 function F(n:longint):longint; begin

if n<=2 then end; A．O(1)

B．O(n)

C．O(n2)

D．O(Fn)

F:=1

F:=F(n-1)+F(n-2);

else

【分析】计算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 个字节，因此，

3

B．24 C．36 D．66

【分析】二分为6个和6个的顶点，此时边最多，有36条边。

B．Unicode C．GBK2312 D．BIG5

省淳中信息学奥赛辅导 奥赛试题解析

ASCII 编码可以表示的最大字符数是255（00H—FFH）。这对于英文而言，是没有问题的，一般只什么用到前128个(00H--7FH,最高位为0) …… 此处隐藏：4030字，全部文档内容请下载后查看。喜欢就下载吧 ……