資料結構
1. 陣列和鏈表的區別?
-
從邏輯結構上來看，陣列必須實作定于固定的長度，不能適應資料動態增減的情況，即陣列的大小一旦定義就不能改變，當資料增加是，可能超過原先定義的元素的個數；當資料減少時，造成記憶體浪費；鏈表動態進行存盤分配，可以適應資料動態地增減的情況，且可以方便地插入、洗掉資料項，
-
從記憶體存盤的角度看；陣列從堆疊中分配空間（用new則在堆上創建），對程式員方便快速，但是自由度小；鏈表從堆中分配空間，自由度大但是申請管理比較麻煩，
-
從訪問方式類看，陣列在記憶體中是連續的存盤，因此可以利用下標索引進行訪問；鏈表是鏈式存盤結構，在訪問元素時候只能夠通過線性方式由前到后順序的訪問，所以訪問效率比陣列要低，
2. 簡述快速排序程序
[!NOTE]
掌握所有常見的排序演算法的手寫實作，以及復雜度相關細節知識，
-
選擇一個基準元素,通常選擇第一個元素或者最后一個元素,
-
通過一趟排序將待排序的記錄分割成獨立的兩部分，其中一部分記錄的元素值均比基準元素值小，另一部分記錄的元素值比基準值大，
-
此時基準元素在其排好序后的正確位置
-
然后分別對這兩部分記錄用同樣的方法繼續進行排序，直到整個序列有序，
3. 各類排序演算法對比（熟練掌握）
3.1 時間復雜度來說
-
平方階(O(n2))排序
各類簡單排序:直接插入、直接選擇和冒泡排序； -
線性對數階(O(nlog2n))排序
快速排序、堆排序和歸并排序； -
O(n1+§))排序,§是介于0和1之間的常數，
希爾排序 -
線性階(O(n))排序
基數排序，此外還有桶、箱排序，
說明：
-
當原表有序或基本有序時，直接插入排序和冒泡排序將大大減少比較次數和移動記錄的次數，時間復雜度可降至O（n）；
-
而快速排序則相反，當原表基本有序時，將蛻化為冒泡排序，時間復雜度提高為O（n2）；
-
原表是否有序，對簡單選擇排序、堆排序、歸并排序和基數排序的時間復雜度影響不大，
3.2 穩定性
[!NOTE]
排序演算法的穩定性:若待排序的序列中，存在多個具有相同關鍵字的記錄，經過排序，這些記錄的相對次序保持不變，則稱該演算法是穩定的；若經排序后，記錄的相對次序發生了改變，則稱該演算法是不穩定的，
3.2.1 穩定的排序演算法
冒泡排序、插入排序、歸并排序和基數排序
3.2.2 不是穩定的排序演算法
選擇排序、快速排序、希爾排序、堆排序
3.3 選擇排序演算法準則
一般而言，需要考慮的因素有以下四點：
設待排序元素的個數為n.
-
當n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序，
-
當n較大，記憶體空間允許，且要求穩定性：歸并排序
-
當n較小，可采用直接插入或直接選擇排序，
直接插入排序：當元素分布有序，直接插入排序將大大減少比較次數和移動記錄的次數，
直接選擇排序 ：元素分布有序，如果不要求穩定性，選擇直接選擇排序
-
一般不使用或不直接使用傳統的冒泡排序，
-
基數排序
它是一種穩定的排序演算法，但有一定的局限性：
- 關鍵字可分解，
- 記錄的關鍵字位數較少，如果密集更好
- 如果是數字時，最好是無符號的
4. 解決哈希沖突的方法（面試重點）
[!NOTE]
需要對HashTable的底層實作有深入的理解，知道哈希沖突的產生原因和解決方法，
哈希表（Hash table，也叫散串列），是根據關鍵碼值(Key value)而直接進行訪問的資料結構，
1） 線性探測法
2） 平方探測法
3） 偽隨機序列法
4） 拉鏈法
5. B樹（了解）
[!NOTE]
如果對資料庫有了解的話，該知識點需要深入理解，
根據B類樹的特點，構造一個多階的B類樹，然后在盡量多的在結點上存盤相關的資訊，保證層數盡量的少，以便后面我們可以更快的找到資訊，磁盤的I/O操作也少一些，而且B類樹是平衡樹，每個結點到葉子結點的高度都是相同，這也保證了每個查詢是穩定的，
B樹和B+樹的區別，以一個m階樹為例，
-
關鍵字的數量不同；B+樹中分支結點有m個關鍵字，其葉子結點也有m個，其關鍵字只是起到了一個索引的作用，但是B樹雖然也有m個子結點，但是其只擁有m-1個關鍵字，
-
存盤的位置不同；B+樹中的資料都存盤在葉子結點上，也就是其所有葉子結點的資料組合起來就是完整的資料，但是B樹的資料存盤在每一個結點中，并不僅僅存盤在葉子結點上，
-
分支結點的構造不同；B+樹的分支結點僅僅存盤著關鍵字資訊和兒子的指標（這里的指標指的是磁盤塊的偏移量），也就是說內部結點僅僅包含著索引資訊，
-
查詢不同；B樹在找到具體的數值以后，則結束，而B+樹則需要通過索引找到葉子結點中的資料才結束，也就是說B+樹的搜索程序中走了一條從根結點到葉子結點的路徑，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/6702.html
標籤：其他
上一篇：前端面試題及答案（一）
下一篇：三列浮動中間寬度自適應