Java面試過程中，經(jīng)常會被問到數(shù)據(jù)結(jié)構(gòu)和算法相關(guān)的知識。對于工作多年的程序員來說，這些理論的知識可能已經(jīng)忘得差不多了吧，所以面試前還是有必要臨時抱抱佛腳的。

　　一、線性表(重點)

　　線性表是由N個元素組成的有序序列，也是最常見的一種數(shù)據(jù)結(jié)構(gòu)。重點有兩個數(shù)組和鏈表。

　　1、數(shù)組

　　數(shù)組是一種存儲單元連續(xù)，用來存儲固定大小元素的線性表。java中對應(yīng)的集合實現(xiàn)，比如ArrayList。

　　2、鏈表

　　鏈表又分單鏈表和雙鏈表，是在物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中指針的鏈接次序?qū)崿F(xiàn)的。java中對應(yīng)的集合實現(xiàn)，比如LinkedList。

　　二、棧與隊列

　　1、棧

　　棧，是一種運算受限的線性表，重點掌握其后進(jìn)先出的特點。表的末端叫棧頂，基本操作有push(進(jìn)棧)和pop(出棧)。java中stack就是簡單的棧實現(xiàn)。

　　2、隊列

　　隊列也是一種操作受限制的線性表，重點掌握其先進(jìn)先出的特點。表的前端只允許進(jìn)行刪除操作，表的后端進(jìn)行插入操作。進(jìn)行插入操作的端稱為隊尾，進(jìn)行刪除操作的端稱為隊頭。java中很多Queue的實現(xiàn)，消息中間件的隊列本質(zhì)也是基于此的。

　　三、樹(重點)

　　在非線性結(jié)構(gòu)里面，樹是非常非常重要的一種數(shù)據(jù)結(jié)構(gòu)。基于其本身的結(jié)構(gòu)優(yōu)勢，尤其在查找領(lǐng)域，應(yīng)用廣泛，其中又以二叉樹最為重要。樹的話我們這里只重點說一下二叉樹。

　　1、二叉搜索樹

　　二叉搜索樹又叫二叉查找樹，又叫二叉排序樹。性質(zhì)如下：(1) 若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值;(2) 若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值;(3) 左、右子樹也分別為二叉排序樹;(4) 沒有鍵值相等的結(jié)點。

　　2、平衡二叉樹

　　平衡二叉樹又叫AVL樹。性質(zhì)如下：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。

　　3、紅黑樹

　　紅黑樹是一種特殊的平衡二叉樹，它保證在最壞情況下基本動態(tài)集合操作的事件復(fù)雜度為O(log n)。

　　紅黑樹放棄了追求完全平衡，追求大致平衡，在與平衡二叉樹的時間復(fù)雜度相差不大的情況下，保證每次插入最多只需要三次旋轉(zhuǎn)就能達(dá)到平衡，實現(xiàn)起來也更為簡單。平衡二叉樹追求絕對平衡，條件比較苛刻，實現(xiàn)起來比較麻煩，每次插入新節(jié)點之后需要旋轉(zhuǎn)的次數(shù)不能預(yù)知。

　　四、圖

　　圖是比線性表和樹更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，面試中基本不太會問到，大家有興建的可以自己去了解下。

　　綜上，說了下常見的幾種數(shù)據(jù)結(jié)構(gòu)，上面的內(nèi)容大家不用死記硬背，重要的是理解，面試過程中能說出大體原理即可。

      以上就是動力節(jié)點Java培訓(xùn)機(jī)構(gòu)小編介紹的“Java數(shù)據(jù)結(jié)構(gòu)面試題及答案”的內(nèi)容，希望對大家有幫助，如有疑問，請在線咨詢，有專業(yè)老師隨時為你服務(wù)。

相關(guān)推薦

最新最全java面試題及答案（初級到高級）

史上最全的中高級JAVA工程師面試題及答案匯總

Java高級開發(fā)工程師面試題

2019史上最全java面試題題庫大全800題

哪有資深java工程師面試題