单项选择题

1. 下列四个不同进制的数中，与其它三项数值上不相等的是（ ）。
   A. (269)16
   B. (617)10
   C. (1151)8
   D. (1001101011)2
   正解:D 简单的二进制 每年都有一道
   其他都是617，D是619

1. 下列属于解释执行的程序设计语言是（ ）。
   A. C
   B. C++
   C. Pascal
   D. Python

正解:D
目前 csp-s可以选择前三语言 懂我意思了8

1. 中国计算机学会于（ ）年创办全国青少年计算机程序设计竞赛。
   A. 1983
   B. 1984
   C. 1985
   D. 1986

正解:B
tg2010年考过相关知识点
NOI，1984年邓小平指出：“计算机的普及要从娃娃做起。于是就有了NOI

IOI:1987年，保加利亚的Sendov教授在联合国教科文组织第24届全体会议上，倡议举行国际信息学奥林匹克，定名为International Olympiad in Informatics，简称IOI。开始于1989

APIO：:IOI2006期间，部分亚洲与太平洋地区参赛团领队在多次领队会协商的基础上，经IOI主席、IOI国际委员会与科学委员会批准决定从2007年开始举办该项赛事。

1. 设根节点深度为0，一棵深度为h 的满k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k 个子结点的树，共有（ ）个结点。
   A. (k h+1 - 1) / (k - 1)
   B. k h-1
   C. k h
   D. (k h-1) / (k - 1)
   正解:A
   等比数列求和，以1为首项，k为公比的前（h+1）项和

2. 设某算法的时间复杂度函数的递推方程是T(n) = T(n - 1) + n（n 为正整数）及T(0) = 1，则该算法的时间复杂度为（ ）。
   A. O(log n) B. O(n log n) C. O(n) D. O(n2)
   正解:D

noip2015提高组初赛原题
6. 表达式a * d - b * c 的前缀形式是（ ）。
A. a d * b c * -
B. - * a d * b c
C. a * d - b * c
D. - * * a d b c

正解:B
不会的可以看下前面的题解
7. 在一条长度为1 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（ ）。
A. 1 / 2
B. 1 / 3
C. 2 / 3
D. 3 / 5
正解:B
画三维例题图形

1. 关于Catalan 数Cn = (2n)! / (n + 1)! / n！，下列说法中错误的是（ ）。
   A. Cn 表示有n + 1 个结点的不同形态的二叉树的个数。
   B. Cn 表示含n 对括号的合法括号序列的个数。
   C. Cn 表示长度为n 的入栈序列对应的合法出栈序列个数。
   D. Cn 表示通过连接顶点而将n + 2 边的凸多边形分成三角形的方法个数。
   正解:A
   是n个节点
   前几年考过n个节点能有几个不同形态的二叉树，今年反着考了…

1. 假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于
   （ ）。
   A. 1 : 2
   B. 2 : 1
   C. 1 : 3
   D. 1 : 1
   正解:D

手动模拟

1. 为了统计一个非负整数的二进制形式中1 的个数，代码如下：
   int CountBit(int x)
   {
   int ret = 0;
   while (x)
   {
   ret++;
   __;
   }
   return ret;
   }
   则空格内要填入的语句是（ ）。
   A. x >>= 1
   B. x &= x - 1
   C. x |= x >> 1
   D. x <<= 1
   正解:B
   lowbit操作

二、不定项选择题（共5 题，每题2 分，共计10 分；每题有一个或多个正确选项，多选或少选均不得分）

1. NOIP 初赛中，选手可以带入考场的有（ ）。
   A. 笔
   B. 橡皮
   C. 手机（关机）
   D. 草稿纸
   正解:AB
   详情请看须知

1. 2-3 树是一种特殊的树，它满足两个条件：
   （1）每个内部结点有两个或三个子结点；
   （2）所有的叶结点到根的路径长度相同。
   如果一棵2-3 树有10 个叶结点，那么它可能有（ ）个非叶结点。
   A. 5
   B. 6
   C. 7
   D. 8
   正解:CD
   到根路径长度相同说明这十个叶子节点在同一层，那么就有（25）和（32+2*2）两种分法，即1->2->5->10 和 1->2->4->10

1. 下列关于最短路算法的说法正确的有（ ）。
   A. 当图中不存在负权回路但是存在负权边时，Dijkstra 算法不一定能求出源点到所有点的最短路。
   B. 当图中不存在负权边时，调用多次Dijkstra 算法能求出每对顶点间最短路径。
   C. 图中存在负权回路时，调用一次Dijkstra 算法也一定能求出源点到所有点的最短路。
   D. 当图中不存在负权边时，调用一次Dijkstra 算法不能用于每对顶点间最短路计算。
   正解:ABD
   Dijkstra 单源最短路，不支持负权边和负环

1. 下列说法中，是树的性质的有（ ）。
   A. 无环
   B. 任意两个结点之间有且只有一条简单路径
   C. 有且只有一个简单环
   D. 边的数目恰是顶点数目减1
   正解:ABD

2. 下列关于图灵奖的说法中，正确的有（ ）。
   A. 图灵奖是由电气和电子工程师协会（IEEE）设立的。
   B. 目前获得该奖项的华人学者只有姚期智教授一人。
   C. 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。
   D. 它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。

正解:BCD
图灵奖是ACM创办的

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

1. 去了，没去，没去，没下雨
   （根据3，丙去了，所以丁没去
   根据2，丁没去，所以乙没去
   根据4，丙去了，丁没去，所以甲去了
   根据1，乙没去，甲去了，所以不下雨）
   2.454
   （..并不是很会，详见http://www.cnblogs.com/oier/p/9783787.html）

四、阅读程序写结果

1、4 （0~14中，满足完全平方数除以15余数为1的数个数）
2、6（找环的个数）
3、16（找字符串中独一无二的子串的个数）
4、（1）2 1 3 5 6 4(手动模拟即可）
（2）3 2 5 6 1 4（实际上是在找字典序大于输入的第t个排序，康托展开或者是跳阶乘次步）

参考