6、百度

试题来源：牛客网（https://www.nowcoder.com/test/30544930/summary）

1、对于数列4、5、6、7、9、12、18、23，如果采用折半查找元素9，请问需要查找几次？（）
A. 2
B. 3
C.4
D.5
答案：B
答案解析：
第1次查找的位置： mid = (low + high)/2 = (0+7)/2=3, 查找到了7.
第2次查找的位置： mid = (mid+1 + 原来的high)/2 = (4+7)/2 = 5, 查找了12.
第3次查找的位置： mid = (原来的low + mid-1) /2= (4+4)/2 = 4,查找了9

public class Test {
    public static void main(String[] args) {
        int[] arr = {4,5,6,7,9,12,18,23};
        System.out.println(binarySearch(arr, 0, arr.length-1,9));
    }
    public static int binarySearch(int[] arr, int low, int high,int target){
        if(low<=high)
        {
            int mid = (low + high)/2;
            System.out.println(arr[mid]);//依次打印7，12，9
            if(target >arr[mid])
            {
                return binarySearch(arr, mid+1,high,target);
            }
            else if(target <arr[mid])
            {
                return binarySearch(arr, low,mid-1, target);
            }
            else
            {
                return mid;
            }
        }
        else
        {
            return -1;
        }                
    }
}

2、假设有一张表test，表中存放着全国的城市信息以及其所在的省份，现在要以每个省份包含名称以’州’为结尾的城市数量降序排序，包含相同数量的省份以省份名称降序排序，最终输出第二多以及第三多的省份以及数量，那么下面正确的sql语句是
create table test(
id int(11) not null auto_increment,
province char(50) not null comment ‘省份名称’,
city char(50) not null comment ‘城市名称’,
primary key(id),
unique key idx(province, city)
)engine = innodb;
A.select province, count() c from test where city like ‘%州’ group by province order by c desc, province desc limit 2,1
B.select province, count() c from test where city like ‘%州’ group by province order by c desc, province desc limit 1,2
C.select province, count() c from test where city like ‘州%’ group by province order by c desc, province desc limit 2,1
D.select province, count() c from test where city like ‘州%’ group by province order by c desc, province desc limit 1,2
答案：B

3、序列{20, 23, 28, 41, 61, 31, 71, 76, 15, 30}构造为完全二叉树，完全二叉树再变为最小堆后，堆所对应的的中序遍历序列可能为（）
A.76, 23, 41, 61, 20, 30, 31, 15, 28, 71
B.76, 23, 41, 20, 61, 30, 15, 31, 28, 71
C.76, 20, 41, 23, 30, 61, 15, 31, 28, 71
D.76, 23, 20, 41, 61, 15, 31, 20, 28, 71
答案：B
答案解析：
构建完全二叉树：

从最后一个非叶子结点开始，从右至左，从下至上进行调整，将它调整成小顶堆，调整过程如下：

中序遍历结果：
76，23，41，20，61，30，15，31，28，71

4、有如下递归函数 test(n)，其时间复杂度为多少？
int test(int n) {
if(n <= 1) return1;
return(2 test(n - 1) + 3 test(n - 2));
}
A.O(logn)
B.O(nlogn)
C.O(n^2)
D.O(n^3)
E:O(2^n)
答案：E
答案解析：
常见的时间复杂度量级有：
常数阶O(1)
对数阶O(logN)
线性阶O(n)
线性对数阶O(nlogN)
平方阶O(n²)
立方阶O(n³)
K次方阶O(n^k)
指数阶(2^n)
上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。
在这个例子中，求第n个数的值，需要求n-1和n-2两个值，求n-1的值，需要依次求前2个值，画个树形结构，就可以看到求解过程是个完全二叉树的过程，每层的数据量：2º ，2¹ , 2² ……， 可以看出时间复杂度指数级的，即是2n

5、假设磁头当前位于116道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为48, 59, 37, 81, 125, 195, 185, 205采用电梯调度SCAN算法得到的磁道访问序列是：
A.125, 185, 195, 205, 81, 59, 48, 37
B.125, 185, 195, 205, 37, 48, 59, 81
C.37, 48, 59, 81, 125, 185, 195, 205
D.125, 195, 185, 205, 48, 59, 37, 81
答案：A
答案解析：
电梯算法的核心就是尽可能的不让磁头的方向发生翻转。当前处于116道且磁头朝增加的方向，那么根据电梯扫描算法，磁头会一直朝着增加方向走，直到到达磁盘的一端。在到达磁盘的一端后，磁头掉头，再朝着磁盘另一端去扫描。这个过程就跟电梯一样所以叫电梯扫描算法。
因此，磁道访问序列为：116->125->185->195->205->81->59->48->37

6、nginx.log是一个日志文件，现在想将日志的最新输出实时打印在屏幕上，用哪个命令可以实现：
A.cat -f nginx.log
B.tee -f nginx.log
C.head -f nginx.log
D.tail -f nginx.log
答案：D

7、度度熊请你找出两个数，满足且尽量大。输出最大的.
其中表示和的最小公倍数，表示和的最大公约数。

public class Main {

    //由于n和n-1一定互质，所以直接返回 n*(n-1) -1
    //注意用long保存答案，使用int，乘法运算会溢出
    public static void main(String[] args) {

         Scanner sc =new Scanner(System.in);
         long n =sc.nextLong();
         System.out.println(n*(n-1)-1);

    }

}

8、老板给度度熊个数， 每一次从中取出一个最大的减去， 其他的个数加上， 一直重复直到最大的， 执行次数记为。
老板想知道最少执行多少次操作使得个数都小于呢？

import java.util.*;

public class Main{
    public static void main(String[] args){

        Scanner sc =new Scanner(System.in);
        int n =sc.nextInt();
        long [] arr =new long [n];
        for(int i =0;i<n;i++){
            arr[i]=sc.nextLong();
        }
        long count=0;
        while(!isFinish(arr)){
            long max=0;
            int index=0;
            for(int i =0;i<arr.length;i++){
                if(arr[i]>max){
                    max=arr[i];
                    index=i;
                }
            }
            arr[index]=max%n;
            count+=max/n;
            for(int i=0;i<n;i++){
                if(i!=index)
                {
                      arr[i]+=max/n;
                }        
            }

        }
        System.out.println(count);

    }
    public static boolean isFinish(long [] arr){
        for(long item:arr){
            if(item>=arr.length) return false;
        }
        return true;
    }
}