牛客网错题总结
1、二分查找的时间复杂度（）
第一次查找剩余：n/2
第二次查找剩余：n/4
…
第m次查找剩余：n/(2^m)
最坏情况下：n/(2^m)=1
m=log2 n
时间复杂度：log2 n
2、图的BFS生成树的树高比DFS生成树的树高（）
BFS是广度优先遍历，DFS是深度优先遍历。
对于一些特殊的图，比如只有一个顶点的图，其BFS生成树的树高和DFS生成树的树高相等。
一般的图，根据图的BFS生成树和DFS树的算法思想，BFS生成树的树高比DFS生成树的树高小。
3、设顺序表的长度为n，则顺序查找的平均比较次数为（）
第一个元素：1次
第二个元素：2次
第三个元素：3次
…
第n个元素：n次
平均查找次数：(((1+2+···+n)*n)/2)/n=(1+n)/2
4、有个长度为12的无重复有序表，按折半查找法进行查找，在表内各元素等概率情况下，查找成功所需的平均比较（三元比较）的次数为（）
下标范围为1～12。查找1次成功的结点为：6。查找2次成功的结点为：3，9。查找3次成功的结点为：1，4，7，11。查找4次成功的结点为：2，5，8，10，12。成功查找所有结点的总的比较次数为:1×1+2×2+3×4+4×5=37平均比较次数为37／12
5、对于静态表的顺序查找法，若在表头设置监视哨，则正确的查找方式为（）
静态链表和动态链表是线性表链式存储结构的两种不同的表示方式，前者简称静态表，后者简称动态表。
静态链表是用类似于数组方法实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配地址空间大小。
所以静态链表的初始长度一般是固定的，在做插入和删除操作时不需要移动元素，仅需修改指针。
所谓监视哨，就是将空出来的下标为0的这个元素的值设为Key，监视哨的作用是使得我们不用多次判断i是否越界，因为
就算静态表中找不到，也会在0位置上配对成功，返回0。
6、字符串′ababaabab′的nextval为()
next值的计算
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| 字符串 | a | b | a | b | a | a | b | a | b |
| next | -1 | 0 |
前两位为-1，0固定不变
第三位：第三位前的字符串为ab，前缀有a;后缀有b;前后相等的最长字符串为0
第四位：字符串为aba，前缀有a,ab;后缀有ba,a;前后缀相等的最长字符串长度为1
第第五位：字符串为abab，前缀有a,ab,aba;后缀有bab,ab,b;前后缀相等的最长字符串长度为2
nextval值的计算
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| s | a | b | a | b | a | a | b | a | b |
| next[i] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 2 | 3 |
| nextval | -1 |
nextval[0]值固定为-1
naxtval[1]:next[1]=0,s[(next[1])]=s[0]=a,s[(next[1])]!=s[1],nextval[1]=next[1]=0
naxtval[2]:next[2]=0,s[(next[2])]=s[0]=a.s[(next[2])]=s[2],nextval[2]=next[next[2]]=-1
naxtval[3]:next[3]=1,s[(next[3])]=s[1]=b.s[(next[3])]=s[3],nextval[3]=next[next[3]]=0
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| s | a | b | a | b | a | a | b | a | b |
| next[i] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 2 | 3 |
| nextval | -1 | 0 | -1 | 0 | -1 | 3 | 0 | -1 | 0 |
7、二分查找只能使用顺序表存储，不能采用链表
8、关于红黑树和AVL树，以下哪种说法不正确？
红黑树和avl树都属于自平衡二叉树；
两者查找、插入、删除的时间复杂度相同；
包含n个内部结点的红黑树的高度是o(logn);
TreeMap是一个红黑树的实现，能保证插入的值保证排序