携程2019届秋招专业笔试-研发方向

有一组数据{46,79,56,38,40,84}利用快速排序，以第一个元素为基准得到的一次划分结果为：

排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时至少能确定一个元素最终位置的方法是：
1. 简单选择排序     2. 希尔排序        3.快速排序        4. 堆排序        5. 二路归并排序

对有18个元素的有序表R[1...18]进行二分查找，则查找A[3]的比较序列为：

一棵二叉树的先序遍历序列为A,B,C,D,E,F,中序遍历序列为C,B,A,E,D,F，则后序遍历序列为：

考虑以下JAVA排序代码，对于array为{15,0,6,9,3}时，运行sort方法，则最终排序结果为：
 public void sort(Comparable[] a) {
  int N = a.length
  int h = 1
  while (h < N / 3) {
   h = 3 * h + 1// 1, 4, 13, 40, ...
  }
  while (h >= 1) {
   for (int i = h i < N i++) {
     for (int j = i  j >= h && compareElement(a[j],  a[j - h]) j -= h) {
      exch(a, j, j - h)
    }
   }
   h = h / 3
  }
 }
 
 public boolean compareElement(Comparable v, Comparable w) {
  return v.compareTo(w) < 0
 }

 public static void exch(Comparable[] a, int i, int j) {
  Comparable t = a[i]
  a[i] = a[j]
  a[j] = t
 }

给出下列JAVA程序执行结果：       
public class Test {

 public static Test t1=new Test()  

  {  
   System.out.println("blockA")  
  }  
  
  static {  
   System.out.println("blockB")  
  } 
  
  public static void main(String[] args){  
   Test t2=new Test()       
  }    
 }

给出下列JAVA程序执行结果：    
public class A {    
  public int a = 0
  public void fun(){
   System.out.println("A")
  }
 }

 public class B extends A{
  public int a = 1
  public void fun(){
   System.out.println("B")
  }

 public static void main(String[] args){
  A classA = new B()     
  System.out.println(classA.a)
  classA.fun()
 }

给出下列JAVA程序执行结果：                         
public static void main(String args[]) {
        Thread t = new Thread() {
            public void run() {
                pong()
            }
        }
        t.run()
     System.out.print("ping")
    }
    static void pong() {
        System.out.print("pong")
      }

以下有关 Abstract Factory（抽象工厂）模式正确的是：

软件生存周期的瀑布模型一般包括计划、（   ）、设计、编码、测试、维护等阶段

设某棵二叉树的中序遍历序列为BADC，前序遍历序列为ABCD，则后序遍历该二叉树得到序列为：

有一批订单记录，数据有订单号，入店时间，离店时间；
输入一个时间值A，需要在这批记录中找到符合入离店时间范围（A大于等于入店时间，并且A小于等于离店时间）内的所有记录。 单次查询时间复杂度控制在O(logN)
※注意：订单号升序输出 
输入描述： 记录数：10
时间值A：20180602
订单号 入店时间 离店时间
1001 20180103 20180105
1002 20180202 20180203
1003 20180304 20180306
1004 20180401 20180408
1005 20180501 20180504
1006 20180601 20180604
1007 20180705 20180706
1008 20180801 20180804
1009 20180903 20180903
1010 20181003 20181003
以上输入都为整型输入样例： 10 20180602 1001 20180103 20180105 1002 20180202 20180203 1003 20180304 20180306 1004 20180401 20180408 1005 20180501 20180504 1006 20180601 20180604 1007 20180705 20180706 1008 20180801 20180804 1009 20180903 20180903 1010 20181003 20181003 输出描述： 1006输出样例 1006

	设计一个数据结构，实现LRU Cache的功能(Least Recently Used – 最近最少使用缓存)。它支持如下2个操作： get 和 put。

int get(int key) – 如果key已存在，则返回key对应的值value（始终大于0）；如果key不存在，则返回-1。
void put(int key, int value) – 如果key不存在，将value插入；如果key已存在，则使用value替换原先已经存在的值。如果容量达到了限制，LRU Cache需要在插入新元素之前，将最近最少使用的元素删除。

请特别注意“使用”的定义：新插入或获取key视为被使用一次；而将已经存在的值替换更新，不算被使用。

限制：请在O(1)的时间复杂度内完成上述2个操作。

输入描述： 第一行读入一个整数n，表示LRU Cache的容量限制。 从第二行开始一直到文件末尾，每1行代表1个操作。

如果每行的第1个字符是p，则该字符后面会跟随2个整数，表示put操作的key和value。

如果每行的第1个字符是g，则该字符后面会跟随1个整数，表示get操作的key。输入样例： 2 p 1 1 p 2 2 g 1 p 2 102 p 3 3 g 1 g 2 g 3 输出描述： 按照输入中get操作出现的顺序，按行输出get操作的返回结果。输出样例 1 1 -1 3

输入描述： long 类型的数值输入样例： 3 输出描述： 该数值二进制表示中1的个数输出样例 2