第十九届全国奥林匹克信息学联赛初赛.docVIP

第十九届全国青少年信息学奥林匹克联赛初赛 提高组C语言试题 竞赛时间：2013年10月13日 14:30~16:30 选手注意： ●试题纸共有12页，满分100分。请在答题纸上做答，写在试题纸上的一律无效。 ●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。 单项选择题（共15题，每题1.5分，共计22.5分：每题仅有一个正确选项） 一个32位整型变量占用（ ）个字节。 A. 4 B. 8 C. 32 D. 128 2. 二进制数11.01在十进制下是（ ）。 A. 3.25 B. 4.125 C. 6.25 D. 11.125 3. 下面的故事与（ ）算法有异曲同工之妙。 从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事……’” A. 枚举 B. 递归 C. 贪心 D. 分治 4. 1948年，（ ）将热力学的熵引入信息通信领域，标志着信息理论的开端。 A. 冯·诺依曼(John von Neumann) B. 图灵 (Alan Turing) C. 欧拉 (Leohard Euler) D. 克劳德·香农(Claude Shannon) 5. 已知一棵二叉树有2013个节点，则其中至多有（ ）个节点有两个子节点。 A. 1006 B. 1007 C. 1023 D.1024 6. 在一个无向图中，如果任意两点之间都存在路径相连，则称之为连通图。 右图是一个右五个顶点、八条边的连通图。若要使它不再是连通图，至少 要删去其中（ ）条边。 2 3 4 5 7. 斐波那契数列定义如下：F1=1,F2=1,Fn=(n-1)+f(n-2)。如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为（ ）。 int F(int n) { if(n=2) return 1; else return F(n-1)+F(n-2) } A. O(1) B. O(n) C. O(n2) D. O(Fn) 8. 二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。那么，二叉查找树的（ ）是一个有序序列。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 宽度优先遍历 9. 将(2,6,10,17)分别存储到某个地址区间为0~10的哈希表中，如果哈希函数h(x)=（ ），将不会发生冲突，其中a mod b 表示a除以b的余数。 A. x mod 11 B. x2 mod 11 C. 2x mod 11 D. [√x] mod 11，其中[√x]表示向下取整 10.IPv4协议使用32位地址，随着其不断变化，地址资源日趋枯竭。因此，它正逐渐被使用（ ）位地址的IPv6协议所取代。 A．40 B. 48 C. 64 D. 128 11.二分图是指能将顶点划分成两个部分，每一部分顶点间没有边相连的简单无向图。那么，12个顶点的二分图至多有（ ）条边。 A. 18 B. 24 C. 36 D. 66 12.（ ）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制编码，以满足跨语言、跨平台的文本交换。目前它已经收录了超过十万个不同字符。 A. ASCII B. Unicpde C. GBK 2312 D.BIG5 13.把64位非零浮点数强制转换成32位浮点数后，不可能（ ） A. 大于原数 B. 小于原数 C. 等于原数 D. 与原数符号相反 14.对于一个n个顶点，m条边的带权有向图用Dijkstra算法计算单源最短路时，如果不使用堆或其他优先队列进行优化，则其时间复杂度位（ ） A.O(mn+n3) B.O(n2) C.O((m+n)㏒n) D.O((m+n2) ㏒n) 15.T(n)表示某个算法输入规模位n时的运算次数。如果T(1)位常数，且有递归式T(n)