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

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

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

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

2、簡(jiǎn)述快速排序過(guò)程

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

2)通過(guò)一趟排序?qū)⒋判虻挠涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的元素值均比基準(zhǔn)元素值小。另一部分記錄的元素值比基準(zhǔn)值大。

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

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

3、快速排序的改進(jìn)

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

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

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

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

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

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

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

方法3 三數(shù)取中

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

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

4、冒泡排序算法的改進(jìn)

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

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

5、鄰接矩陣與鄰接表

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

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

對(duì)比

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

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

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

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

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

鄰接矩陣的優(yōu)點(diǎn)是可以快速判斷兩個(gè)頂點(diǎn)之間是否存在邊，可以快速添加邊或者刪除邊。而其缺點(diǎn)是如果頂點(diǎn)之間的邊比較少，會(huì)比較浪費(fèi)空間。因?yàn)槭且粋€(gè) n∗n 的矩陣。

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

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