常用的數(shù)據(jù)結構

數(shù)組、鏈表、棧、隊列、樹、圖、散列表、堆
樹：僅有一個根節(jié)點，該節(jié)點沒有前驅節(jié)點，其他節(jié)點僅有一個前驅節(jié)點且可以有兩個后繼節(jié)點
圖：頂點和邊，有向圖和無向圖
散列表：使用散列函數(shù)進行存儲和查找
堆：一種特殊的樹形結構，一般討論的都是二叉堆。堆的特點是根節(jié)點的值是所有節(jié)點中最小的或最大的。并且根節(jié)點的兩個子樹也是一個堆結構。

說幾種排序算法（快排、堆排、歸并）

十大經(jīng)典排序算法（Python實現(xiàn)）

直接插入 尋找插入
折半插入 折半尋找插入
希爾排序 縮小增量直接插入
簡單選擇 選最小的
堆排序 大/小頂堆
冒泡 最大后移
快排 選第一個為基準，大移右小移左
歸并 倒完全二叉樹形狀，最后合并時左右兩邊有序，用一個空數(shù)按序（左右兩邊比較）組裝起來
基數(shù) 10個桶，若干趟分配+收集

BFS和DFS，二者區(qū)別

• 深度優(yōu)先搜索DFS：1.從頂點v出發(fā)，訪問v，2.依次從頂點v未被訪問的鄰接點出發(fā)進行深度遍歷
• 廣度優(yōu)先搜索BFS：1.從頂點v出發(fā)，訪問v，2.假設v最近一層的頂點依次是vi1,vi2,..vik，依次訪問vi1,vi2,..vik的未訪問的鄰接點，3.重復步驟2直到?jīng)]有未被訪問的鄰接點為止
• 區(qū)別：DFS常用于所有解或連通性問題，如馬走日、是否有解；BFS常用于最優(yōu)解問題，如最短路徑問題，BFS運行過程中需要存儲每層的信息，運行時存儲量較大。