數(shù)據(jù)結(jié)構(gòu)與算法簡(jiǎn)述

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

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

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

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

簡(jiǎn)述二叉樹

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

簡(jiǎn)述滿二叉樹

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

簡(jiǎn)述完全二叉樹

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

簡(jiǎn)述二叉樹的前中后序遍歷算法

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

訪問根節(jié)點(diǎn)

遞歸前序遍歷左子樹

遞歸前序遍歷右子樹

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

遞歸中序遍歷左子樹

訪問根節(jié)點(diǎn)

遞歸中序遍歷右子樹

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

遞歸后序遍歷左子樹

遞歸后序遍歷右子樹

訪問根節(jié)點(diǎn)

簡(jiǎn)述解決Hash沖突的方法

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

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

簡(jiǎn)述AVL樹

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

簡(jiǎn)述紅黑樹

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

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

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

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

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

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

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

簡(jiǎn)述插入排序

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

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

簡(jiǎn)述希爾排序

希爾排序：把記錄按下標(biāo)的一定增量分組，對(duì)每組進(jìn)行直接插入排序，每次排序后減小增量，當(dāng)增量減至 1 時(shí)排序完畢。

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

簡(jiǎn)述直接選擇排序

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

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

簡(jiǎn)述堆排序

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

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

簡(jiǎn)述冒泡排序

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

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

簡(jiǎn)述快速排序

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

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

簡(jiǎn)述歸并排序

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

簡(jiǎn)述圖

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

有向圖：邊具有方向性

無(wú)向圖：邊不具有方向性

簡(jiǎn)述鄰接矩陣

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

簡(jiǎn)述鄰接表

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

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

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

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

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

簡(jiǎn)述最小生成樹和其對(duì)應(yīng)的算法

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

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

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

簡(jiǎn)述最短路徑算法

Dijkstral算法為求解一個(gè)點(diǎn)到其余各點(diǎn)最小路徑的方法，其算法為：

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

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

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

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

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

簡(jiǎn)述堆

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

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

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

簡(jiǎn)述set

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

說一下對(duì)于樹的理解

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

每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；

只有一個(gè)節(jié)點(diǎn)沒有父節(jié)點(diǎn)，該節(jié)點(diǎn)稱為根節(jié)點(diǎn)；

除根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；

簡(jiǎn)述二叉查找樹

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

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

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

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

審核編輯 ：李倩