一位JavaEye的朋友easonfans剛剛進行了某公司游戲部的筆試，并在博客中分享了此次Java工程師筆試題中的一些注意事項。解釋的比較基礎細致，希望對于那些正在準備Java工程師筆試的朋友們有一些幫助。

一、選擇題：

5：既希望較快的查找又便于線性表動態變化的查找方法是【】？

A：順序查找  B：折半查找  C：索引順序查找  D：哈希法查找

ans：C

詳細解釋：

查找是在大量的信息中尋找一個特定的信息元素，在計算機應用中，查找是常用的基本運算，例如編譯程序中符號表的查找。用關鍵字標識一個數據元素，查找時根據給定的某個值，在表中確定一個關鍵字的值等于給定值的記錄或數據元素。在計算機中進行查找的方法是根據表中的記錄的組織結構確定的。

順序查找也稱為線形查找，從數據結構線形表的一端開始，順序掃描，依次將掃描到的結點關鍵字與給定值k相比較，若相等則表示查找成功；若掃描結束仍沒有找到關鍵字等于k的結點，表示查找失敗。

二分查找要求線形表中的結點按關鍵字值升序或降序排列，用給定值k先與中間結點的關鍵字比較，中間結點把線形表分成兩個子表，若相等則查找成功；若不相等，再根據k與該中間結點關鍵字的比較結果確定下一步查找哪個子表，這樣遞歸進行，直到查找到或查找結束發現表中沒有這樣的結點。

【優缺點】折半查找法的優點是比較次數少，查找速度快，平均性能好;其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經常變動而查找頻繁的有序列表。

分塊查找也稱為索引順序查找，把線形分成若干塊，在每一塊中的數據元素的存儲順序是任意的，但要求塊與塊之間須按關鍵字值的大小有序排列，還要建立一個按關鍵字值遞增順序排列的索引表，索引表中的一項對應線形表中的一塊，索引項包括兩個內容：① 鍵域存放相應塊的最大關鍵字；② 鏈域存放指向本塊第一個結點的指針。分塊查找分兩步進行，先確定待查找的結點屬于哪一塊，然后在塊內查找結點。

哈希表查找是通過對記錄的關鍵字值進行運算，直接求出結點的地址，是關鍵字到地址的直接轉換方法，不用反復比較。假設f包含n個結點，Ri為其中某個結點（1≤i≤n），keyi是其關鍵字值，在keyi與Ri的地址之間建立某種函數關系，可以通過這個函數把關鍵字值轉換成相應結點的地址，有：addr(Ri)=H(keyi)，addr(Ri)為哈希函數。

算法詳細比較

查找算法	優點	缺點	運算效率
順序查找	最簡單的，查找表的存儲結構：既適用于順序存儲結構，也適用于鏈式存儲結構。	順序查找效率低，當n過大時，應避免使用。	1若查找成功:(n+1)/2; 2若查找失敗：n+1; 3設查找成功的概率為p,查找不成功的概率為q=(1-p),則平均比較次數為：E(n)=p*(n+1)/2+q*(n+1)=p*(n+1)/2+(1-p)*(n+1)=(n+1)*(1-p/2); 4若成功和失敗的概率各占50%,平均性能:3*(n+1)/4;
二分查找	查找速度快； 但表必須有序。	頻繁插入和刪除不方便，二分法查找適于表中元素很少變化而查找頻繁的情況。	二分法查找的過程可用二叉樹來描述，中間結點是二叉樹的根，左子表相當于左子樹，右子表相當于右子樹，由此得到的二叉樹便為描述二分法查找的判定樹。二分法查找的過程是走了一條從根結點到葉子結點的過程，不論查找成功與失敗，查找長度均不超過樹的高度，h= log2(n+1) ,那個2是log的下綴； 等概率時，折半查找的平均長度為：； 當n很大時，ASL = log2(n+1)-1。
分塊查找（索引順序查找）	分塊查找綜合了順序查找和二分法查找的優點，既有動態結構，又適于快速查找。		設待查找文件有n個記錄，平均分成b塊，每塊有s個記錄。若只考慮查找成功的概率，且在塊內和索引表中均用順序查找，則平均查找長度為： E(n)=Eb+Ew=(b+1)/2 +(s+1)/2 =(s^2+2*s+n)/(2*s)； 若s= √n，則平均查找長度取最小值：√n+1 若對索引表采用二分法查找，則平均查找長度為：        E(n)=Eb+Ew=㏒2(b+1) +(s+1)/2
哈希表查找	不論哈希表中有多少數據，插入和刪除（有時包括側除）只需要接近常量的時間即0(1）的時間級	哈希表也有一些缺點它是基于數組的，數組創建后難于擴展某些哈希表被基本填滿時，性能下降得非常嚴重，所以程序雖必須要清楚表中將要存儲多少數據（或者準備好定期地把數據轉移到更大的哈希表中，這是個費時的過程）。 要面臨沖突處理問題。	基本是：O（1）

6：分別以下列構造二叉排序樹，與用其他三個序列所構造的結果不同的是【】？

A：（100，80，90，60，120，110，130）

B：（100，120，110，130，80，60，90）

C：（100，60，80，90，120，110，130）

D：（100，80，60，90，120，130，110）

ans：C

這道題我答錯了，我選得B，回來一看應該選擇C項，有余長時間沒有看過操作系統了，好多東西我都忘記了，這道題真真的是蒙的。

詳細解釋：

一、二叉排序樹的定義

二叉排序樹或者是空樹，或者是具有如下性質的二叉樹：

１、左子樹上所有結點的數據值均小于根結點的數據值；

２、右子樹上所有結點的數據值均大于或等于根結點的數據值；

３、左子樹、右子樹本身又各是一棵二叉排序樹。

二、叉排序樹的構造

二叉排序樹的構造過程實質上就是排序的過程，它是二叉排序樹作媒介，將一個任意的數據序列變成一個有序序列。二叉排序樹的構造一般是采用陸續插入結點的辦法逐步構成的。具體構造的思路是：

1、以待排序的數據的第一個數據構成根結點；

2、對以后的各個數據，逐個插入結點，而且規定：在插入過程的每一步，原有樹結點位置不再變動，只是將新數據的結點作為一個葉子結點插入到合適的位置，使樹中任何結點的數據與其左、右子樹結點數據之間的關系仍然符合對二叉排序樹的要求。

所以有2可知，明顯我們應該選擇出C，因為只有C項的兩個子樹是以60，120為對應根節點的，其他的三個是以80，120作為子樹根節點的。

#p#

10：實現發送到某個email鏈接的Html代碼是【】?

A:< mail>xxx＠yyy< /mail>

B:< mail href="xxx＠yyy"/>

C:< a href="mailto:xxx＠yyy">

D:< a href="xxx＠yyy">

ans:C

詳細解釋：

^_^，這題我做對了，其實我不懂這個Html代碼,我做到這道題的時候使用Html語言的邏輯猜的，看A和B，我使用排除法，要使A對，那么要是按照Html的邏輯，那么B也對，所以我知道A和B不對，另外對于D，明顯是超鏈接的語句啊，所以我選得C，回來一看果然對了，蒙也要技術的。

或者自己使用dreamweaver的插入－－電子郵件標簽都看的到。

二、填空題：

2.多個線程互斥使用資源，對應的信號量的變化范圍【 】？

ans:[0,1]

詳細解釋：一般信號量為0，1就可以了，若某個資源一次最多可以n個線程可以訪問，那么信號量的范圍就為【0～（n-1）】

3.對于資源靜態分配法來避免死鎖，主要是打破了死鎖四個條件的那個【】？

ans：部分分配條件

詳細解釋：

死鎖的條件

1、互斥條件（Mutual exclusion）：資源不能被共享，只能由一個進程使用。

2、請求與保持條件（Hold and wait）：已經得到資源的進程可以再次申請新的資源。

3、非剝奪條件（也稱為部分分配條件）（No pre-emption）：已經分配的資源不能從相應的進程中被強制地剝奪。

4、循環等待條件（Circular wait）：系統中若干進程組成環路，改環路中每個進程都在等待相鄰進程正占用的資源

死鎖預防的方法：

（1）打破"不剝奪條件：強迫那些請求新資源而沒有立即得到滿足的進程，釋放它已保持的其它資源。即一個進程已占用的資源在運行過程中可能要暫時釋放。

（2）打破"部分分配"條件：對某進程所要求的資源一次性地分配完畢。這樣，進程在運行過程中就不再需要新的資源。這種方法又稱為預先靜態分配法。但在做靜態分配時，只要有一種資源不能滿足，該進程就必需等待．

（3）打破"環路等待"條件：在資源的分配過程中，對資源的請求作出某種限制，使環路不可能出現--有序資源分配法

4.當一個進程獨占處理器順序執行的時候，具有兩個特性【】和可再現性。

ans：封閉性

詳細解釋：

程序順序執行的特征：

a.順序性：每一操作必須在下一操作開始之前結束

b.封閉性：程序運行時獨占全機資源，資源的狀態（除初始狀態外）只有本程序才能改變，程序一旦執行，其結果不受外界影響

c.可再現性：程序執行環境和初始條件相同，重復執行時，結果相同

我開始寫的是可預見性……我也不從哪里看到這個說法的……

9.中級表達式3+x*(2.4/5+6)所對應的后綴表達式為【】？

ans：3x2.45/6-*+

詳細解釋：

表達式表示法

算術表達式中最常見的表示法形式有 中綴、前綴和 后綴表示法。中綴表示法是書寫表達式的常見方式，而前綴和后綴表示法主要用于計算機科學領域。

中綴表示法

中綴表示法是算術表達式的常規表示法。稱它為 中綴表示法是因為每個操作符都位于其操作數的中間，這種表示法只適用于操作符恰好對應兩個操作數的時候（在操作符是二元操作符如加、減、乘、除以及取模的情況下）。對以中綴表示法書寫的表達式進行語法分析時，需要用括號和優先規則排除多義性。

Syntax: operand1 operator operand2 
Example: (A+B)*C-D/(E+F)  

前綴表示法

前綴表示法中，操作符寫在操作數的前面。這種表示法經常用于計算機科學，特別是編譯器設計方面。為紀念其發明家 ― Jan Lukasiewicz，這種表示法也稱 波蘭表示法。

Syntax  : operator operand1 operand2 
Example : -*+ABC/D+EF  

后綴表示法

在后綴表示法中，操作符位于操作數后面。后綴表示法也稱 逆波蘭表示法（reverse Polish notation，RPN），因其使表達式求值變得輕松，所以被普遍使用。

Syntax  : operand1 operand2 operator  
Example : AB+C*DEF+/-  

前綴和后綴表示法有三項公共特征：

◆操作數的順序與等價的中綴表達式中操作數的順序一致

◆不需要括號

◆操作符的優先級不相關

要把表達式從中綴表達式的形式轉換成用后綴表示法表示的等價表達式，必須了解操作符的優先級和結合性。 優先級或者說操作符的強度決定求值順序；優先級高的操作符比優先級低的操作符先求值。 如果所有操作符優先級一樣，那么求值順序就取決于它們的 結合性。操作符的結合性定義了相同優先級操作符組合的順序（從右至左或從左至右）。

Left associativity  : A+B+C = (A+B)+C  
Right associativity : A^B^C = A^(B^C)  

詳細步驟：

設以’＠’字符作為結束符的中綴算術表達式已經保存在s1字符串中，轉換后得到的后綴算術表達式擬存于s2字符串中。由中綴表達式轉換為后綴表達式的規則可知：轉換前后，表達式中的數值項的次序不變，而運算符的次序發生了變化，由處在兩個運算對象的中間變為處在兩個運算對象的后面，同時去掉了所有的括號。為了使轉換正確，必須設定一個運算符棧，并在棧底放入一個特殊算符，假定為‘＠’字符，讓它具有最低的運算符優先級，假定為數值0，此棧用來保存掃描中綴表達式得到的暫不能放入后綴表達式中的運算符，待它的兩個運算對象都放入到后綴表達式以后，再令其出棧并寫入到后綴表達式中。

把中綴表達式轉換為后綴表達式算法的基本思路是從頭到尾地掃描中綴表達式中的每個字符，對于不同類型的字符按不情況進行處理。若遇到的是空格則認為是分隔符，不需要進行處理；若遇到的是數字或小數點，則直接寫入到s2中，并在每個數值的最后寫入一個空格；若遇到的是左括號，則應把它壓入到運算符棧中，待以它開始的括號內的表達式轉換完畢后再出棧；若遇到的是右括號，則表明括號內的中綴表達式已經掃描完畢，把從棧底直到保存著的對應左括號之間的運算符依次退棧并寫入s2串中；若遇到的是運算符，當該運算符的優先級大于棧頂運算符的優先級（加減運算符的優先級設定為1，乘除運算符的優先級設定為2，在棧中保存的特殊運算符‘＠’和’(’的優先級設定為0)時，表明該運算符的后一個運算對象還沒有被掃描并放入到s2串中，應把它暫存于運算符棧中，待它的后一個運算對象從s1串中讀出并寫入到s2串中后，再另其出棧并寫入s2串中；若遇到的運算符的優先級小于等于棧頂運算符的優先級，這表明棧頂運算符的兩個運算對象已經被保存到s2串中，應將棧頂運算符退棧并寫入到s2串中，對于新的棧頂運算符仍繼續進行比較和處理，直到被處理的運算符的優先級大于棧頂運算符的優先級為止，然后另該運算符進棧即可。

按照以上過程掃描到中綴表達式結束符‘＠’時，把棧中剩余的運算符依次退棧并寫入到后綴表達式中，再向s2寫入表達式結束符‘＠’和字符串結束符’{post.content}’，整個轉換過程就處理完畢，在s2中就得到了轉換成的后綴表達式。

或者：

轉換過程包括用下面的算法讀入中綴表達式的操作數、操作符和括號：

初始化一個空堆棧，將結果字符串變量置空。

從左到右讀入中綴表達式，每次一個字符。

如果字符是操作數，將它添加到結果字符串。

如果字符是個操作符，彈出（pop）操作符，直至遇見開括號（opening parenthesis）、優先級較低的操作符或者同一優先級的右結合符號。把這個操作符壓入（push）堆棧。

如果字符是個開括號，把它壓入堆棧。

如果字符是個閉括號（closing parenthesis），在遇見開括號前，彈出所有操作符，然后把它們添加到結果字符串。

如果到達輸入字符串的末尾，彈出所有操作符并添加到結果字符串。

一個例子：

例如，設中綴算術表達式s1為：10+(18+9*3)/15-6＠，使用的運算符棧用R表示，則轉換過程如下：

（1）開始時存放后綴表達式的字符串s2為空，R中壓入有’＠’算符，它具有最低的優先級0：＠

（2）當掃描到s1中的左括號時，s2和R中的數據變化如下：

1 0     
＠ + (   

（3）當掃描到s1中的數值3時，s2和R中的數據變化為：

1 0   1 8  9  3  
＠ + ( + *     

（4）當掃描到s1中的右括號時，s2和R變為：

1 0   1 8  9  3  * +   
＠ +    

（5）當掃描到s1中的數值15時，s2和R又變為：

1 0   1 8  9  3  * + 1 5     
 ＠ + /    

（6）當掃描到s1中的’＠’字符時，s2和R為：

1 0   1 8  9  3  * + 1 5  / + 6     
＠ -     

（7）當整個處理過程結束后，R棧為空，s2為：1 0   1 8  9  3  * + 1 5  / + 6  - ＠ ù

10.在一個帶頭節點的單循環鏈表中，P指向尾結點的直接前驅，則指向頭結點的指針head可用P表示為head＝【 】？

ans：P->next->next

詳細解釋：其實這道題不難，不過我忘記怎么使用鏈表指向下一個node了，我寫的是P.P.P，無語了……

12有序表（12，18，30，43，56，78，82，95）中以此二分查找43和56元素時，其查找長度分別為【  】和【 】？

 ans：1，3

詳細解釋：這題要說難難在那里哪？就是二分法比較的時候，當數列個數是偶數的時候到底是應該去哪個值，也就是說第一次比較的值應該是43，還是56，如果是43，那么這題就是1，3這個結果，那么恭喜你，你答對了，要使56，那么這道題就是3，1.結果正好相反。像本篇日志所涉及的第一道題就講到了查找方法：二分法，其中還提供一個鏈接：http://www.emcad.com/Teaching/DS-DB/Search.htm，其實這個鏈接中舉的例子是錯誤的，因為在算法實現中（1＋n）/2并不會四舍五入，因為c和c＋＋都是取整的，也就是說本題（1＋8）/2=4,也就是43而不是56！！！另外還有一種理解方法，有8個數（偶數），那么8/2＝4，所以比較的是第四個數。這么理解也是對的。

此次Java工程師筆試題就先介紹這么多。原博文中介紹了一些參考閱讀，有興趣的讀者可以去看看。

【編輯推薦】

1. Java筆試題：Java基礎概念（附答案）
2. 自學Javabean迅速成為Java高手
3. Java通過JNI調用C語言的方法
4. 高手Java核心技術學習筆記
5. 成為Java高手需要注意的25個學習目標