NOIP2015提高组初赛
11.具有 n 个节点，e 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度为（ ）。
因为有了st数组，所以每个边也会只遍历一遍
13双向链表中有两个指针域，llink 和 rlink，分别指回前驱及后继，设 p 指向链表中的一个结点，q 指向一待插入结点，现要求在 p 前插入 q，则正确的插入为（ ）。
e[idx]=x;
l[idx]=k;
r[idx]=r[k];
l[r[idx]]=idx;
r[k]=idx++;
14对图 G 中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图 G 的一个正常着色。正常着色图 G 所必需的最少颜色数，称为 G 的色数。那么下图的色数是（ ）。
并不是用四色定理，这是最少用多少种颜色
16下了属于才做系统的是：
MAC OS Linux UNIX WindownsXP
17下列属于视频文件格式的有（ ）。
MPEG AVI WMV
18IP地址
一共四位每位是一个八位的二进制数，所以单个数字不能超过255
这四位二进制数用.连接
19.正确的选项
A.因为哈夫曼树是一个完全二叉树所以他符合二叉树的性质：
叶子节点总数=非叶子节点总数多一个
n0=n2+1
B.完全二叉树只是跟满二叉树的编号一样
C.如下图，他的拓补排序序列也可以是1243，3点的入度是
D.这是树
21.在 1 和 2015之间（包括 1 和 2015 在内）不能被 4、5、6 三个数任意一个数整除的数有_____个。
$\frac{2015}{4}+\frac{2015}{5}+\frac{2015}{6}-\frac{2015}{gcd(4,5)=4\times5}-\frac{2015}{gcd(5,6)=5\times6}-\frac{2015}{gcd(4,6)=12}+\frac{2015}{gcd(4,5,6)=60+1}$
这个题用了容斥原理
22.结点数为 55 的不同形态的二叉树一共有_____种。（结点数为 22 的二叉树一共有 22 种：一种是根结点和左儿子，另一种是根结点和右儿子。）
这是一个卡特兰数列
$Catalan(N)=\frac{C_{2N}^N}{N+1}$
Catalan(1)=1
Catalan(2)=1
Catalan(3)=2
Catalan(4)=5
Catalan(5)=14
Catalan(6)=42
