携程研发方向秋招专业笔试
答案在問題后
1、對有18個元素的有序表R[1…18]進行二分查找，則查找A[3]的比較序列為：
A、1,2,3
B、9,5,2,3
C、9,5,3
D、9,4,2,3
2、一棵二叉樹的先序遍歷序列為A,B,C,D,E,F,中序遍歷序列為C,B,A,E,D,F，則后序遍歷序列為：?
A、C,B,E,F,D,A
B、F,E,D,C,B,A
C、C,B,E,D,F,A
D、不確定
3、考慮以下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;
?}
A、15,0,6,9,3
B、0,15,6,9,3
C、15,0,6,3,9
D、0,3,6,9,15
4、以下哪項說法正確的是？?
A、垃圾回收線程的優先級很高，以保證不再 使用的內存將被及時回收
B、垃圾收集允許程序開發者明確指定釋放 哪一個對象
C、垃圾回收機制保證了Java程序不會出現內存溢出
D、其他選項都不對
5、給出下列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();???????
??}????
?}
A、blockA,blockB,blockA
B、blockB,blockA,blockA
C、blockA,blockB
D、blockB,blockA
6、給出下列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”);
??????}
A、pingpong
B、pongping
C、pingpong和pongping都有可能
D、都不輸出
7、以下有關?Abstract?Factory（抽象工廠）模式正確的是：?
A、Abstract Factory 的實例化方法就是具體工廠方法
B、Abstract Factory 類和具體工廠方法可以分離,每個具體工廠負責一個抽象工廠方法接口的實現
C、由于 Abstract Factory 類和具體工廠方法可以分離,因此在實現時會產生更多的類
D、當問題存在相同的對象用于解決不同的情形時,應該使用抽象工廠模式
8、軟件開發的螺旋模型綜合了瀑布模型和演化模型的優點，還增加了什么？
A、版本管理
B、風險分析
C、可行性分析
D、系統集成
9、下列選項中，不能構成折半查找中關鍵字比較序列的是？
A、500,200,450,180
B、500,450,200,180
C、180,500,200,450
D、180,200,500,450
10、設計一個數據結構，實現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個操作。
個人想法，僅供參考
1、答案解析：
正確答案: D
題目的意思是：
在[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]中尋找3，利用二分法的查找的過程；
第一次嘗試，[1,18]區間，（1+18）/ 2 = 9, 發現9大于3，所以肯定在左邊；
第二次嘗試，[1,8]區間，因為上一步發現9大了，所以確定上限是8，（1+8）/ 2 = 4，4大于3；
第三次嘗試，[1,3]區間，道理如上，（1+3）/ 2 = 2，2小與2；
第四次嘗試，[3,3]，3==3，找到了；
結束。
2、答案解析：
正確答案: A ?
先知道什么是先序、中序、后序遍歷
先序遍歷：根、左、右???
中序遍歷：左、根、右
后序遍歷：左、右、根
這里先序是A,B,C,D,E,F，所以根是A；中序遍歷序列為C,B,A,E,D,F，所以C,B在根節點A的左側，D,E,F在右側；
然后我們先來確定A左側的結構：
??? A左側只有B和C。根據先序，可以知道B是根；根據中序可以知道C是B的左孩子。
然后是A右側的結構：
??? A右側是D,E,F。根據先序，可以知道D是根；
????那么E是D的左孩子還是右孩子呢？根據中序可知E一定是D的左孩子；
??? 根據中序，F在D的右側，所以它只能是D的右孩子，不可能是E的左/右孩子
樹形結構如圖
3、答案解析
答案是：D
這題本質上就是希爾排序。
具體希爾排序方法，參考：https://blog.csdn.net/gaoruowen1/article/details/81015244
4、答案解析
正確答案: D
A：垃圾回收線程的優先級靠后，原因有：GC占資源，不到萬不得已不啟動GC，而主線程里面的業務邏輯才是核心，只有內存不夠時或者CPU空閑時才會GC。
B：垃圾回收歸GC管。
C：GC只是保證了大部分情況，但是代碼的組合有無限的可能，這是GC無法周全考慮到的，因此需要JVM調優。
5、答案解析：
正確答案: A
創建類的靜態變量和實例變量都會觸發類加載。類加載時靜態代碼塊只加載一次。在運行?Test?t2=new?Test();? 時創建實例變量 觸發類加載，在加載該類時?public?static?Test?t1=new?Test();???創建類靜態變量 觸發類加載。首先執行public?static?Test?t1=new?Test();?打印blockA blockB.后執行?Test?t2=new?Test();??打印blockA。如果public?static?Test?t1=new?Test();放在靜態代碼塊后面則是選B，先打印blockB，在執行public?static?Test?t1=new?Test();?打印blockA。
6、答案解析：
正確答案: B ?
run()方法不會啟動新的線程，這里只有一個主線程，所以順序執行，假如這里用start()方法，就會啟動新的線程，而ping和pong兩個線程并不知道哪個先執行就是答案就是B。
7、答案解析：
正確答案: B?
抽象工廠是對具體工廠的抽象，具體工廠是對實例的抽象
8、答案解析
正確答案: B
螺旋模型?是一種演化?軟件開發過程?模型，它兼顧了?快速原型?的?迭代?的特征以及?瀑布模型?的系統化與嚴格監控。螺旋模型最大的特點在于引入了其他模型不具備的風險分析，使軟件在無法排除重大風險時有機會停止，以減小損失。同時，在每個迭代階段構建原型是螺旋模型用以減小風險的途徑。螺旋模型更適合大型的昂貴的系統級的軟件應用。
9、答案解析
正確答案: A
A:第一次查找為0-500;第二次查找200-500;第三次查找不論是200-450還是450-500都不可能包含180所以錯誤
B:第一次查找為0-500;第二次查找0-450;第三次查找0-200;第四次查找0-180
C:第一次查找為0-180;第二次查找180-500;第三次查找200-500;第四次查找200-450或450-500
D:第一次查找為0-180;第二次查找200-末尾;第三次查找200-500;第四次查找200-450或450-500
10、答案解析
?
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
??
public clas***ain{
????private class Node {
??? ? ??Node next, prev;
??? ? ??int key, value;
??
??? ? ??Node (){}
??? ? ??Node(int key,?int value) {
??? ? ? ? ??this.value = value;
??? ? ? ? ??this.key = key;
??? ? ??}
????}
??
????private Node head, tail;
????private Map<Integer, Node> map;
????private int count, capacity;
??
????private void addNode(Node node) {
??? ? ??Node old = head.next;
??? ? ??head.next = node;
??? ? ??node.prev = head;
??? ? ??node.next = old;
??? ? ??old.prev = node;
????}
??
????private void removeNode(Node node) {
??? ? ??Node previous = node.prev;
??? ? ??previous.next = node.next;
??? ? ??node.next.prev = previous;
????}
??
????private void moveToHead(Node node) {
??? ? ??removeNode(node);
??? ? ??addNode(node);
????}
??
????private Node popTail() {
??? ? ??Node pre = tail.prev;
??? ? ??removeNode(pre);
??? ? ??return pre;
????}
??
????public Main(int capacity) {
??? ? ??this.capacity = capacity;
??? ? ??this.count =?0;
??? ? ??map =?new HashMap<>();
??? ? ??head =?new Node();
??? ? ??tail =?new Node();
??? ? ??head.next = tail;
??? ? ??tail.prev = head;
????}
??
????public int get(int key) {
??? ? ??Node node = map.get(key);
??? ? ??if (node ==?null)?return -1;
??? ? ??moveToHead(node);
??? ? ??return node.value;
????}
??
????public void put(int key,?int value) {
??? ? ??Node node = map.get(key);
??? ? ??if (node ==?null) {
??? ? ? ? ??if (count == capacity) {
??? ? ? ? ? ? ??map.remove(popTail().key);
??? ? ? ? ? ? ??--count;
??? ? ? ? ??}
??? ? ? ? ??Node fresh =?new Node(key, value);
??? ? ? ? ??map.put(key, fresh);
??? ? ? ? ??addNode(fresh);
??? ? ? ? ??count++;
??? ? ??}?else {
??? ? ? ? ??node.value = value;
??? ? ??}
????}
????public static void main(String[] args) {
??? ? ??Scanner scanner =?new Scanner(System.in);
??? ? ??int capacity = Integer.valueOf(scanner.nextLine().trim());
??? ? ??Main instance =?new Main(capacity);
??? ? ??while (scanner.hasNextLine()) {
??? ? ? ? ??String command = scanner.nextLine().trim();
??? ? ? ? ??if (capacity >0 && command.charAt(0) ==?‘p’) {
??? ? ? ? ? ? ??int key = Integer.valueOf(command.substring(2, command.lastIndexOf(" “)));
??? ? ? ? ? ? ??int value = Integer.valueOf(command.substring(command.lastIndexOf(” ")+1));
??? ? ? ? ? ? ??instance.put(key, value);
??? ? ? ? ??}else if(command.charAt(0) ==?‘g’) {
??? ? ? ? ? ? ??if (capacity <=?0) {
??? ? ? ? ? ? ? ? ??System.out.println(-1);
??? ? ? ? ? ? ??}else {
??? ? ? ? ? ? ? ? ??int key = Integer.valueOf(command.substring(2));
??? ? ? ? ? ? ? ? ??System.out.println(instance.get(key));
??? ? ? ? ? ? ??}
??? ? ? ? ??}
??? ? ??}
????}
}
總結
以上是生活随笔為你收集整理的携程研发方向秋招专业笔试的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： vim中的替换
- 下一篇： IPv6格式转换（全写转简写）