历届奥赛试题解析-初赛讲解(7)

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

18.2 十八届提高组

一、单项选择题（共10题，每题1.5分，共计15分；每题有且仅有一个正确选项） 5．如里不在快速排序中引入随机化，有可能导致的后果是（ D ）。

A．数组访问越界 C．排序结果错误

B．陷入死循环

D．排序时间退化为平方级

9．以下不属于3G（第三代移动通信技术）标准的是（ A ）。

A．GSM

B．TD-SCDMA

C．CDMA2000

D．WCDMA

【分析】（1）1G（first generation）表示第一代移动通讯技术，以模拟技术为基础的蜂窝无线电话系统，如现在已经淘汰。

（2）2G技术基本可被切为两种： TDMA和CDMA规。复用﹙Multiplexing﹚形式的一种。全球移动通信系统GSM（Global System for Mobile communication）是代表

（3）3G（第三代移动通信技术3rd-generation，），是指支持高速数据传输的蜂窝移动通讯技术。3G服务能够同时传送声音及数据信息，速率一般在几百kbps以上。目前3G存在四种标准：CDMA2000，WCDMA，TD-SCDMA(我国)，WiMAX。

(4) 4G：第四代移动电话行动通信标准；该技术包括TD-LTE和FDD-LTE两种制式（3.5G）。升级版的LTE Advanced是标准的4G。4G是集3G与WLAN于一体，并能够快速传输数据、高质量、音频、视频和图像等。4G能够以100Mbps以上的速度下载，比目前的家用宽带ADSL（4兆）快20倍，并能够满足几乎所有用户对于无线服务的要求。此外，4G可以在DSL和有线电视调制解调器没有覆盖的地方部署，然后再扩展到整个地区。很明显，4G有着不可比拟的优越性。有比较形象的说法， 2G时代看txt ； 3G时代看JPG ； 4G时代看AVI。 这都是很形象的解释了4G是什么意思！及对比了前两代移动通信技术的区别！

二、不定项选择题（共10题，每题1.5分，共计15分；每题有一个或多个正确选项，多选或

少选均不得分）

1．如果对于所有规模为n的输入，一个算法均恰好进行（ A ）次运算，我们可以说该算法

的时间复杂度为 O(2) 。

n

A．2

n+1

B．3n C．n*2n D．22n

2． 从顶点A0出发，对有向图（ AD ）进行广度优先搜索（BFS）时，一种可能的遍历顺序

是A0 A1 A2 A3 A4 。

31

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

3. 如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a，b，c

（如右图所示），另有元素d已经出栈，则可能的入栈顺序是（ AD ）。 A．a, b, c, d C．a, c, b, d

B．b, a, c, d D．d, a, b, c

4．在计算机显示器所使用的RGB颜色模型中，（ BD ）属于三原色之一。

A．黄色 B．蓝色 C．紫色 D．绿色

5．一棵二叉树一共有19个节点，其叶子节点可能有（ ABC ）个。

A．1

B．9

C．10

D．15

【分析】如果选D 15叶子要8个父节点，节点数合计已经超过19

6．已知带权有向图G上的所有权值均为正整数，记顶点u到顶点v的最短路径的权值为d(u,v)。

若V1 V2 V3 V4 V5 是图G上的顶点，且它们之间两两都存路径可达，则以下说法正确的有（ CD ）。

A．V1 到V2的最短路径可能包含一个环 B．d（V1 ，V2）=d（V2 ，V,1）

C．d（V1 ，V3）≤d（V1 ，V2）+ d（V2 ，V3）

D．如果V1→V2 →V3 →V4 →V5 是V1到V5的一条最短路径，那么V2 →V3 →V4是V2到V4的一条最短路径

7．逻辑异或（? ）是一种二元运算，其真值表如下所示。

32

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

以下关于逻辑异或的性质，正确的有（ AB ）。 A．交换律：a?b?b?a

B．结合律：(a?b)?c?a?(b?c)

C．关于逻辑与的分配律：a?(b?c)?(a?b)?(a?c) D．关于逻辑或的分配律：a?(b?c)?(a?b)?(a?c)

【分析】（1）a?(b?c)?(a?b)?(a?c)，当a=T时，b=F、c=F时右边才会T，而左

边a=T、b与c只要一个为F时即为T

（2）a?(b?c)?(a?b)?(a?c)，当a=T时，b=F、c=F时左边才会T，而右边b与c

只要一个为F时即为T

8．十进制下的无限循环小数（不包括循环节内的数字均为0成均为9的平凡情况），在二进制

下有可能是（ A ）。

A．无限循环小数(不包括循环节内的数字均为0或均为9的平凡情） B．无限不循环小数

C．有限小数

D．整数

9．（ CD ）是目前互联网上常用的E-mail服务协议。

A．HTTP

B．FTP

C．POP3

D．SMTP

10．以下关于计算复杂度的说法中，正确的有（ BD ）。

A．如果一个问题不存在多项式时间的算法，那它一定是NP类问题 B．如果一个问题不存在多项式时间的算法，那它一定不是P类问题 C．如果一个问题不存在多项式空间的算法，那它一定是NP类问题 D．如果一个问题不存在多项式空间的算法，那它一定不是P类问题

【分析】1.时间复杂度:时间复杂度并不是表示一个算法解决问题需要花多少时间，而是当问

题规模扩大后，算法需要的时间长度增长得有多快。 不管数据有多大，算法处理花的时间始终是那么多的，我们就说这个算法很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个算法的时间复杂度就是O(n)。

多项式级的复杂度：如O(1), O(log(n)),O(n^a)等——因为它的规模n出现在底数的位置！ 非多项式级的复杂度：如：O(a^n)和O(n!)等！

三、问题求解（共2题，每题5分，共计10分）

1． 本题中，我们约定布尔表达式只能包含p，q，r三个布尔变量，以及“与”（∧）、“或”（∨）、

33

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

“非”（￢）三种布尔运算。如果无论p，q，r如何取值，两个布尔表达式的值总是相同，则称它们等价。例如(p∨q)∨r和p∨(q∨r)等价，p∨￢p和q∨￢q也等价；而p∨q和p∧q不等价。那么两两不等价的布尔表达式最多有 256 个。 【分析】

（1）对于p、q、r三个变量，每个变量可取0,1两种取值，共有8种组合。 （2）对于表达式真值表中共8项，

序号 0 1 2 3 4 7 p、q、r取值 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 表达式值 0 0 0 0 0 0 1 1 1 1 1 1 （3）对于某一表达式A，与其它不等价，在真值表中表达式值0——7项中至少有一项不等，

0表示这一项相等，1表示不相等，不相等的情况如下 序号 1 2 3 255

2． 对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图1有5个不同的

独立集（1个双点集合，3个单点集合、1个空集），图2有14个不同的独立集。那么图3有 5536 个不同的独立集。

pqr各种取值使得表达式有8个值 7 0 0 0 1 6 0 0 0 1 5 0 0 0 1 4 0 0 0 1 3 0 0 0 1 2 0 0 0 1 1 0 1 1 1 0 1 0 1 1 含义 两个表达式在pqr=000时值不等 两个表达式在pqr=001时值不等 两个表达式值在真值表中有2 …… 此处隐藏：2508字，全部文档内容请下载后查看。喜欢就下载吧 ……