1、數組和鏈表的區別

從邏輯結構上來看，數組必須實現定于固定的長度，不能適應數據動態增減的情況，即數組的大小一旦定義就不能改變。當數據增加是，可能超過原先定義的元素的個數;當數據減少時，造成內存浪費;鏈表動態進行存儲分配，可以適應數據動態地增減的情況，且可以方便地插入、刪除數據項。

從內存存儲的角度看;數組從棧中分配空間(用new則在堆上創建)，對程序員方便快速，但是自由度小;鏈表從堆中分配空間，自由度大但是申請管理比較麻煩。

從訪問方式類看，數組在內存中是連續的存儲，因此可以利用下標索引進行訪問;鏈表是鏈式存儲結構，在訪問元素時候只能夠通過線性方式由前到后順序的訪問，所以訪問效率比數組要低。

2、簡述快速排序過程

1)選擇一個基準元素,通常選擇第一個元素或者最后一個元素,

2)通過一趟排序將待排序的記錄分割成獨立的兩部分，其中一部分記錄的元素值均比基準元素值小。另一部分記錄的元素值比基準值大。

3)此時基準元素在其排好序后的正確位置

4)然后分別對這兩部分記錄用同樣的方法繼續進行排序，直到整個序列有序。

3、快速排序的改進

只對長度大于k的子序列遞歸調用快速排序,讓原序列基本有序，然后再對整個基本有序序列用插入排序算法排序。實踐證明，改進后的算法時間復雜度有所降低，且當k取值為 8 左右時,改進算法的性能最佳。

選擇基準元的方式

對于分治算法，當每次劃分時，算法若都能分成兩個等長的子序列時，那么分治算法效率會達到最大。也就是說，基準的選擇是很重要的。選擇基準的方式決定了兩個分割后兩個子序列的長度，進而對整個算法的效率產生決定性影響。最理想的方法是，選擇的基準恰好能把待排序序列分成兩個等長的子序列。

方法1 固定基準元

如果輸入序列是隨機的，處理時間是可以接受的。如果數組已經有序時，此時的分割就是一個非常不好的分割。

方法2 隨機基準元

這是一種相對安全的策略。由于基準元的位置是隨機的，那么產生的分割也不會總是會出現劣質的分割。在整個數組數字全相等時，仍然是最壞情況，時間復雜度是O(n^2)。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對于絕大多數輸入數據達到O(nlogn)的期望時間復雜度。

方法3 三數取中

引入的原因：雖然隨機選取基準時，減少出現不好分割的幾率，但是還是最壞情況下還是O(n^2)，要緩解這種情況，就引入了三數取中選取基準。

分析：最佳的劃分是將待排序的序列分成等長的子序列，最佳的狀態我們可以使用序列的中間的值，也就是第N/2個數。可是，這很難算出來，并且會明顯減慢快速排序的速度。這樣的中值的估計可以通過隨機選取三個元素并用它們的中值作為基準元而得到。事實上，隨機性并沒有多大的幫助，因此一般的做法是使用左端、右端和中心位置上的三個元素的中值作為基準元。

4、冒泡排序算法的改進

1.設置一標志性變量pos,用于記錄每趟排序中最后一次進行交換的位置。由于pos位置之后的記錄均已交換到位,故在進行下一趟排序時只要掃描到pos位置即可。

2.傳統冒泡排序中每一趟排序操作只能找到一個最大值或最小值,我們考慮利用在每趟排序中進行正向和反向兩遍冒泡的方法一次可以得到兩個最終值(最大者和最小者) , 從而使排序趟數幾乎減少了一半。

5、鄰接矩陣與鄰接表

鄰接矩陣表示法：在一個一維數組中存儲所有的點，在一個二維數組中存儲頂點之間的邊的權值

鄰接表表示法：圖中頂點用一個一維數組存儲，圖中每個頂點vi的所有鄰接點構成單鏈表

對比

1)在鄰接矩陣表示中，無向圖的鄰接矩陣是對稱的。矩陣中第 i 行或 第 i 列有效元素個數之和就是頂點的度。

在有向圖中 第 i 行有效元素個數之和是頂點的出度，第 i 列有效元素個數之和是頂點的入度。

2)在鄰接表的表示中，無向圖的同一條邊在鄰接表中存儲的兩次。如果想要知道頂點的度，只需要求出所對應鏈表的結點個數即可。

有向圖中每條邊在鄰接表中只出現一次，求頂點的出度只需要遍歷所對應鏈表即可。求入度則需要遍歷其他頂點的鏈表。

3)鄰接矩陣與鄰接表優缺點：

鄰接矩陣的優點是可以快速判斷兩個頂點之間是否存在邊，可以快速添加邊或者刪除邊。而其缺點是如果頂點之間的邊比較少，會比較浪費空間。因為是一個 n∗n 的矩陣。

而鄰接表的優點是節省空間，只存儲實際存在的邊。其缺點是關注頂點的度時，就可能需要遍歷一個鏈表。

以上就是“關于高頻出現的幾道數據結構面試題”，你能回答上來嗎?如果想要了解更多的Java面試題相關內容，可以關注動力節點Java官網。