NOIP2018初赛总结(提高组)
先放这么多
T1.下列四个不同进制的数中，与其它三项数值上不相等的是
A.\((269)_{16}\)
B.\((617)_{10}\)
C.\((1151)_8\)
D.\((1001101011)_2\)
答案：D
D比ABC要多2
这种题我一般先算2,8,16进制的，十进制难算，那三个很好互相转。
T2.下列属于解释执行的程序设计语言是
A.C
B.C++
C.Pascal
D.Python
答案：D
常识题
T3.中国计算机学会于?年创办全国青少年计算机程序设计竞赛。
A.1983
B.1984
C.1985
D.1986
答案：B
CCF颂歌题qtmd
T4.设根节点深度为0，一棵深度为h的满k(k>1)叉树，即除最后一层无任何叶子节点外，每一层上的所有节点都有k个子节点的树，共有?个节点
A.\(\displaystyle\frac{k^{h+1}-1}{k-1}\)
B.\(k^{h-1}\)
C.\(k^h\)
D.\(\displaystyle\frac{k^{h-1}}{k-1}\)
答案：A
可以打表可以记结论，甚至你还可以现场推结论！
T5.设某算法的时间复杂度函数的递推方程是T(n)=T(n-1)+n（n为正整数）及T(0)=1，则该算法的时间复杂度为
A.O(log n)
B.O(n log n)
C.O(n)
D.O(n^2)
答案：D
NOIP2015初赛第?题
T6.表达式\(a*d-b*c\)的前缀形式是
A.\(ad*bc*-\)
B.\(-*ad*bc\)
C.\(a*d-b*c\)
D.\(-**adbc\)
答案：B
卧槽慌得一批差点看成后缀表达式
T7.在一条长度为1的线段上随机取两个点，则以这两个点为端点的线段的期望长度是
A.1/2
B.1/3
C.2/3
D.3/5
答案：B
可以通过几何概型+体积什么什么的求，反正挺麻烦的
T8.关于Catalan数Cn=(2n)!/(n+1)!/n!，下列说法错误的是
A.Cn表示有n+1个节点的不同形态的二叉树的个数。
B.Cn表示含n对括号的合法括号序列的个数。
C.Cn表示长度为n的入栈序列对应的合法的出栈序列个数。
D.Cn表示通过连接顶点而将n+2边的凸多边形分成三角形的方法个数。
答案：A
应该是n而不是n+1
T9.假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于
A.1:2
B.2:1
C.1:3
D.1:1
答案：D
考虑如果每个人抽中蓝球都让他们的儿子抽球，则每个人抽中红球蓝球的概率相等，那么答案为D
T10.为了统计一个非负整数的二进制中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
假设二进制末尾是100000的形式，-1之后就是011111，与之后就是000000，最后一个1就没了。
T1.NOIP初赛中，选手可以带入考场的有
A.笔
B.橡皮
C.手机（关机）
D.草稿纸
答案：AB
详见CCF官方
T2.2-3树是一种特殊的数，它满足两个条件：
如果一棵2-3树有10个叶节点，那么它可能有?个非叶节点。
A.5
B.6
C.7
D.8
答案：CD
考虑1->2->5->10和1->2->4->10的形式（表示每一层节点个数）
T3.下列关于最短路算法的说法正确的有
A.当图中不存在负权回路但是存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。
B.当图中不存在负权边时，调动多次Dijkstra算法能求出每对顶点间最短路径。
C.图中存在负权回路时，调用一次Dijkstra算法也一定能求出源点到所有点的最短路。
D.当图中不存在负权边时，调用一次Dijkstra算法不能用于每对顶点间的最短路计算。
答案：ABD
Dijkstra：单源最短路，不支持负权边。
T4.下列说法中，是树的性质的有
A.无环
B.任意两个节点之间有且只有一条简单路径
C.有且只有一个简单环
D.边的数目恰好是顶点数目-1
答案：ABD
沙比题
T5.下列关于图灵奖的说法中，正确的有
A.图灵奖是由电气和电子工程师协会（IEEE）设立的。
B.目前获得该奖项的华人学者只有姚期智教授衽。
C.其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。
D.它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。
答案：BCD
图灵奖是ACM设立的
T1.甲乙丙丁四人在考虑周末要不要外出郊游。
已知
如果周末丙去了，则甲（去了/没去），乙（去了/没去），丁（去了/没去），周末（下雨、没下雨）。
答案：去了，没去，没去，没下雨
根据3，丙去了，那么丁没去
根据2的逆否，丁没去，乙一定没去
根据4，并没去，丁没去，那么甲一定去了
根据1，乙没去，甲去了，周末不下雨
T2.方程\(a*b=(a\ \mathrm{or}\ b)*(a\ \mathrm{and}\ b)\)，在a和b都取[0,31]中的整数时，共有?组解。（*表示乘法；or表示按位或运算；and表示按位与运算）
答案：454
介绍一个结论：\(a\ \mathrm{and}\ b\le\min(a,b)\le\max(a,b)\le a\ \mathrm{or}\ b<2*\max(a,b)\)
最后一个小于号可能不太理解，因为乘以一个2一定要进位，a or b一定是不会进位的。前面的不等号很好理解
那么对答案的贡献形式一定是\(\left\{\begin{aligned}a\ \mathrm{and}\ b=\min(a,b)\\a\ \mathrm{or}\ b=\max(a,b)\end{aligned}\right.\)。那么最小值的二进制一定是最大值的子集。枚举所有二进制可能的位数，那么答案为\(\displaystyle\left(\sum_{i=0}^5\mathrm{C}_{5}^i\times2^i\right)-32=454\)
原文：https://www.cnblogs.com/oier/p/9783787.html