1. 函数a定义如下:

  • 调用函数a(666)返回的结果是: 1023

    int a(int tab){
 int n=tab-1;
 n |= n >> 1;
 n |= n >> 2;
 n |= n >> 4;
 n |= n >> 8;
 n |= n >> 16;
 return n;
}

  • 解析：
    665的二进制数为：1010001111
    512 256 128 64 32 16 8 4 2 1
    1 0 1 0 0 0 1 1 1 1
    或运算 | ：只有同0才为0
    拿 n | (n>>1) 做例子，n>>1位变成了 0101000111，与1010001111 相或得到1111001111
    当 n | (n>>2) 时，结果就已经变成了 1111111111，所以为1023

  • 在HashMap的源码，其中找到大于等于当前值的2的n次幂就是用的这个方法。

2. 已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7计算散列地址，并散列存储在散列表A【0....6】中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 2

  • 解析
    平均查找长度=总的查找次数/元素数
    总的查找次数： 38%7=3 （第1次出现3，无冲突，放在位置3，查找次数为1）
    25%7=4（第1次出现4，无冲突，放在位置4，查找次数为1）
    74%7=4（第2次出现4，有冲突，放在位置5，查找次数为2）
    63%7=0（第1次出现0，无冲突，放在位置0，查找次数为1）
    52%7=3（第2次出现3，有冲突，发现冲突3,4,5，故只能放到6，查找次数为4）
    48%7=6 （第1次出现6，有冲突，发现冲突6,0，故只能放到1，查找次数为3）
    1+1+2+1+4+3=12
    元素数=6
    所以：平均查找长度=12/6=2

3. 给定一个整型数组L，数组长度为n，数组元素取值范围[1,n],（n>2000)，请问最快速找出一个缺失值的时间复杂度是多少？ O(n)

  • 解析
    数组并非排序