NOIP初赛提高组C 语言试题及参考答案.doc

NOIP初赛提高组C++语言试题及参考答案
NOIP初赛提高组C++语言试题及参考答案
NOIP初赛提高组C++语言试题及参考答案
20０9—２013年NＯIP初赛提高组C＋＋语言试题
2０１3第十九届全国青少年信息学奥林匹克联赛初赛
提高组C++语言试题 竞赛时间：2０１3年１0月13日14:３0～16：3０
选手注意:试题纸共有１２页，答题纸共有2页，满分1０0分。请在答题纸上作答，写在试题纸上的一律无效。
不得使用任何电子设备(如计算器、手机、电子词典等）或查阅任何书籍资料.
一、单项选择题(共15题,，；每题有且仅有一个正确选项)
1．一个32位整型变量占用(B)个字节。 A。4 B。8 Ｃ．32　 Ｄ．128
（）. 　 。25 　 　 C．6．2５ 　　 D。
3．下面的故事与（Ｂ）算法有着异曲同工之妙。
从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：？从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事:‘从前有座山，山里有座庙,庙里有个老和尚给小和尚讲故事.。．．'?
　 　 C。贪心　 　Ｄ。分治
，(C)将热力学中的熵引入信息通信领域，标志着信息论研究的开端.
Ａ。冯·诺伊曼(Ｊｏhn von Ｎeumａnｎ) 　　　B。图灵（Ａlan Turing)
C。欧拉（Ｌeonhard Euler)　 　 　 　 　·香农(Ｃｌaude Shannoｎ)
，则其中至多有(A）个节点有２个子节点.
A．１0０6 　 B。1007 　 C。10２３ 　 D。1024
，如果任意两点之间都存在路径相连，则称其为连通图。右图是一个有5个顶点、８条边的连通图。若要使它不再是连通图，至少要删去其中的（B)条边.
A。2 　B。3 　 D．5
7．斐波那契数列的定义如下:F1＝1,Ｆ2=1，Ｆn=Fｎ–１+Fn–２(ｎ≥３）。如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为(Ｄ）。
iｎt　 F(ｉnt　n）
{
iｆ（n〈=2）
ｒｅtｕrn　1;
else
ｒｅｔｕrn　F（n—1）+F(n—２）;
｝
NOIP初赛提高组C++语言试题及参考答案
NOIP初赛提高组C++语言试题及参考答案
NOIP初赛提高组C++语言试题及参考答案
（1)　 B．O(n)　　 (n2） （Ｆｎ）
：每个节点的值都大于其左子树上所有节点的值、，二叉查找树的（B)是一个有序序列。
　 C。后序遍历
9。将(２,6，10,17）分别存储到某个地址区间为０～1０的哈希表中，如果哈希函数ｈ（x)=(），将不会产生冲突，其中a ｍod b表示ａ除以b的余数。
mod 11 　B。x2ｍｏd 1１
C。2x　mod　11 　 　D．
1０。IＰv4协议使用３2位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被使用(D)位地址的IPv６协议所取代。
A．40　　 　 Ｂ。48 　 Ｃ。6４ 　 D。１28
,每一部分内的顶点间没有边相连的简单无向图。那么，１2个顶点的二分图至多有(C)条边。
Ａ．1８　 B。24 　C．3６ 　　Ｄ。６6
12.（A）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制编码,以满足跨语言、跨平台的文本交换。目前它已经收录了超过十万个不同字符。
　 B．Uｎiｃode ２312　 Ｄ。BＩG5
，不可能（B).
B．小于原数 　 　 　
、m条边的带权有向简单图用Ｄｉjkstrａ算法计算单源最短路时，如果不使用堆或其它优先队列进行优化,则其时间复杂度为(）。
(mn+ｎ３) 　 B。O(n2） C．O（（m+n）ｌoｇ n) 　 　((m＋n2）ｌｏg　n）
15。T（ｎ)表示某个算法输入规模为n时的运算次数。如果T(1)为常数，且有递归式T(ｎ)=2*T（n／2）+2ｎ,那么T（n)=()。