簡述數(shù)據(jù)結(jié)構(gòu)棧

棧是一種線性表，其限制只能在表尾進行插入或刪除操作。由于該特性又稱為后進先出的線性表。

簡述數(shù)據(jù)結(jié)構(gòu)隊列

隊列是一種先進先出的線性表。其限制只能在線性表的一端進行插入，而在另一端刪除元素。

簡述二叉樹

二叉樹是n個有限元素的集合，該集合或者為空、或者由一個稱為根（root）的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成。

簡述滿二叉樹

一個二叉樹，如果每一個層的結(jié)點數(shù)都達到最大值，則這個二叉樹就是滿二叉樹。

簡述完全二叉樹

一棵深度為k的有n個結(jié)點的二叉樹，對樹中的結(jié)點按從上至下、從左到右的順序進行編號，如果編號為i（1≤i≤n）的結(jié)點與滿二叉樹中編號為i的結(jié)點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。

簡述二叉樹的前中后序遍歷算法

前序遍歷：若二叉樹為空樹，則執(zhí)行空邏輯，否則：

訪問根節(jié)點

遞歸前序遍歷左子樹

遞歸前序遍歷右子樹

中序遍歷：若二叉樹為空樹，則執(zhí)行空邏輯，否則：

遞歸中序遍歷左子樹

訪問根節(jié)點

遞歸中序遍歷右子樹

后序遍歷：若二叉樹為空樹，則執(zhí)行空邏輯，否則：

遞歸后序遍歷左子樹

遞歸后序遍歷右子樹

訪問根節(jié)點

簡述解決Hash沖突的方法

開放定址法：當發(fā)生哈希沖突時，如果哈希表未被裝滿，那么可以把這個值存放到?jīng)_突位置中的下一個空位置中去

鏈地址法：對相同的哈希地址，設(shè)置一個單鏈表，單鏈表內(nèi)放的都是哈希沖突元素。

簡述AVL樹

AVL樹是一種改進版的搜索二叉樹，其引入平衡因子（左子支高度與右子支高度之差的絕對值），通過旋轉(zhuǎn)使其盡量保持平衡。任何一個節(jié)點的左子支高度與右子支高度之差的絕對值不超過1。

簡述紅黑樹

紅黑樹本身是有2-3樹發(fā)展而來，紅黑樹是保持黑平衡的二叉樹，其查找會比AVL樹慢一點，添加和刪除元素會比AVL樹快一點。增刪改查統(tǒng)計性能上講，紅黑樹更優(yōu)。紅黑樹主要特征是在每個節(jié)點上增加一個屬性表示節(jié)點顏色，可以紅色或黑色。紅黑樹和 AVL 樹類似，都是在進行插入和刪除時通過旋轉(zhuǎn)保持自身平衡，從而獲得較高的查找性能。紅黑樹保證從根節(jié)點到葉尾的最長路徑不超過最短路徑的 2 倍，所以最差時間復(fù)雜度是 O(logn)。紅黑樹通過重新著色和左右旋轉(zhuǎn)，更加高效地完成了插入和刪除之后的自平衡調(diào)整。

簡述穩(wěn)定排序和非穩(wěn)定排序的區(qū)別

穩(wěn)定排序：排序前后兩個相等的數(shù)相對位置不變，則算法穩(wěn)定非穩(wěn)定排序：排序前后兩個相等的數(shù)相對位置發(fā)生了變化，則算法不穩(wěn)定

常見的穩(wěn)定排序算法有哪些

插入排序、冒泡排序、歸并排序

常見的不穩(wěn)定排序算法有哪些

希爾排序、直接選擇排序、堆排序、快速排序

簡述插入排序

插入排序：每一趟將一個待排序記錄按其關(guān)鍵字的大小插入到已排好序的一組記錄的適當位置上，直到所有待排序記錄全部插入為止。

排序算法穩(wěn)定。時間復(fù)雜度 O(n2)，空間復(fù)雜度 O(1)。

簡述希爾排序

希爾排序：把記錄按下標的一定增量分組，對每組進行直接插入排序，每次排序后減小增量，當增量減至 1 時排序完畢。

排序算法不穩(wěn)定。時間復(fù)雜度 O(nlogn)，空間復(fù)雜度 O(1)。

簡述直接選擇排序

直接選擇排序：每次在未排序序列中找到最小元素，和未排序序列的第一個元素交換位置，再在剩余未排序序列中重復(fù)該操作直到所有元素排序完畢。

排序算法不穩(wěn)定。時間復(fù)雜度 O(n2)，空間復(fù)雜度 O(1)。

簡述堆排序

堆排序：將待排序數(shù)組看作一個樹狀數(shù)組，建立一個二叉樹堆。通過對這種數(shù)據(jù)結(jié)構(gòu)進行每個元素的插入，完成排序工作。

排序算法不穩(wěn)定，時間復(fù)雜度 O(nlogn)，空間復(fù)雜度 O(1)。

簡述冒泡排序

冒泡排序：比較相鄰的元素，如果第一個比第二個大就進行交換，對每一對相鄰元素做同樣的工作。

排序算法穩(wěn)定，時間復(fù)雜度 O(n2)，空間復(fù)雜度 O(1)。

簡述快速排序

快速排序：隨機選擇一個基準元素，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，一部分全部小于等于基準元素，一部分全部大于等于基準元素，再按此方法遞歸對這兩部分數(shù)據(jù)進行快速排序。

排序算法不穩(wěn)定，時間復(fù)雜度 O(nlogn)，空間復(fù)雜度 O(logn)。

簡述歸并排序

歸并排序：將待排序序列分成兩部分，然后對兩部分分別遞歸排序，最后進行合并。排序算法穩(wěn)定，時間復(fù)雜度都為 O(nlogn)，空間復(fù)雜度為 O(n)。

簡述圖

圖是由頂點集合和頂點之間的邊集合組成的一種數(shù)據(jù)結(jié)構(gòu)，分為有向圖和無向圖。

有向圖：邊具有方向性

無向圖：邊不具有方向性

簡述鄰接矩陣

用一個二維數(shù)組存放圖頂點間關(guān)系的數(shù)據(jù)，這個二維數(shù)組稱為鄰接矩陣。對于無向圖，鄰接矩陣是對稱矩陣

簡述鄰接表

鄰接表是通過鏈表表示圖連接關(guān)系的一種方。對于表頭結(jié)點所對應(yīng)的頂點存在相鄰頂點，則把相鄰頂點依次存放于表頭結(jié)點所指向的單向鏈表中。

簡述圖的深度優(yōu)先搜索DFS

將圖中每個頂點的訪問標志設(shè)為 FALSE, 之后搜索圖中每個頂點，如果未被訪問，則以該頂點V0為起始點出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點都被訪問到。

簡述圖的廣度優(yōu)先搜索

從圖中的某個頂點V0出發(fā)，并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，之后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有和V0有路徑相通的頂點都被訪問到。

簡述最小生成樹和其對應(yīng)的算法

對于有 n 個結(jié)點的原圖，生成原圖的極小連通子圖，其包含原圖中的所有 n 個結(jié)點，并且有保持圖連通的最少的邊。

普里姆算法：取圖中任意一個頂點 v 作為生成樹的根，之后往生成樹上添加新的頂點 w。在添加的頂點 w 和已經(jīng)在生成樹上的頂點v 之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點 v 和 w 之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點，直至生成樹上含有 n-1 個頂點為止。

克魯斯卡爾算法：先構(gòu)造一個只含 n 個頂點的子圖 SG，然后從權(quán)值最小的邊開始，若它的添加不使 SG 中產(chǎn)生回路，則在 SG 上加上這條邊，如此重復(fù)，直至加上 n-1 條邊為止。

簡述最短路徑算法

Dijkstral算法為求解一個點到其余各點最小路徑的方法，其算法為：

假設(shè)我們求解的是頂點v到其余各個點的最短距離。n次循環(huán)至n個頂點全部遍歷：

從權(quán)值數(shù)組中找到權(quán)值最小的，標記該邊端點k

打印該路徑及權(quán)值

如果存在經(jīng)過頂點k到頂點i的邊比v->i的權(quán)值小

更新權(quán)值數(shù)組及對應(yīng)路徑

簡述堆

堆是一種完全二叉樹形式，其可分為最大值堆和最小值堆。

最大值堆：子節(jié)點均小于父節(jié)點，根節(jié)點是樹中最大的節(jié)點。

最小值堆：子節(jié)點均大于父節(jié)點，根節(jié)點是樹中最小的節(jié)點。

簡述set

Set是一種集合。集合中的對象不按特定的方式排序，并且沒有重復(fù)對象。

說一下對于樹的理解

數(shù)據(jù)結(jié)構(gòu)樹是一種由有限節(jié)點組成的層次關(guān)系的集合。其特點如下：

每個節(jié)點有零個或多個子節(jié)點；

只有一個節(jié)點沒有父節(jié)點，該節(jié)點稱為根節(jié)點；

除根節(jié)點外，每個節(jié)點有且只有一個父節(jié)點；

簡述二叉查找樹

二叉查找樹的左子樹若不為空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；

二叉查找樹的右子樹若不為空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；

二叉查找樹的左、右子樹也分別為二叉查找樹；

沒有鍵值相等的結(jié)點。

審核編輯 ：李倩