1、數(shù)組和鏈表的區(qū)別

從邏輯結(jié)構(gòu)上來看，數(shù)組必須實現(xiàn)定于固定的長度，不能適應(yīng)數(shù)據(jù)動態(tài)增減的情況，即數(shù)組的大小一旦定義就不能改變。當(dāng)數(shù)據(jù)增加是，可能超過原先定義的元素的個數(shù);當(dāng)數(shù)據(jù)減少時，造成內(nèi)存浪費;鏈表動態(tài)進行存儲分配，可以適應(yīng)數(shù)據(jù)動態(tài)地增減的情況，且可以方便地插入、刪除數(shù)據(jù)項。

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

從訪問方式類看，數(shù)組在內(nèi)存中是連續(xù)的存儲，因此可以利用下標(biāo)索引進行訪問;鏈表是鏈?zhǔn)酱鎯Y(jié)構(gòu)，在訪問元素時候只能夠通過線性方式由前到后順序的訪問，所以訪問效率比數(shù)組要低。

2、簡述快速排序過程

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

2)通過一趟排序?qū)⒋判虻挠涗浄指畛瑟毩⒌膬刹糠郑渲幸徊糠钟涗浀脑刂稻然鶞?zhǔn)元素值小。另一部分記錄的元素值比基準(zhǔn)值大。

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

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

3、快速排序的改進

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

選擇基準(zhǔn)元的方式

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

方法1 固定基準(zhǔn)元

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

方法2 隨機基準(zhǔn)元

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

方法3 三數(shù)取中

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

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

4、冒泡排序算法的改進

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

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

5、鄰接矩陣與鄰接表

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

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

對比

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

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

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

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

3)鄰接矩陣與鄰接表優(yōu)缺點：

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

而鄰接表的優(yōu)點是節(jié)省空間，只存儲實際存在的邊。其缺點是關(guān)注頂點的度時，就可能需要遍歷一個鏈表。

以上就是“關(guān)于高頻出現(xiàn)的幾道數(shù)據(jù)結(jié)構(gòu)面試題”，你能回答上來嗎?如果想要了解更多的Java面試題相關(guān)內(nèi)容，可以關(guān)注動力節(jié)點Java官網(wǎng)。