DSA面試題

資料結構是以結構化和系統化的方式定義、儲存和檢索資料的方法。資料結構可能包含不同型別的資料項。

可用的資料結構可能因程式語言而異。常用的資料結構包括列表、陣列、棧、佇列、圖、樹等。

演算法是一個逐步的過程，它定義了一組指令，這些指令按一定順序執行以獲得所需的輸出。

一個問題可以用多種方法解決。因此，對於給定的問題，可以推匯出許多解決方案演算法。我們分析可用的演算法以找到並實現最合適的演算法。

演算法通常根據兩個因素進行分析：時間和空間。也就是說，演算法需要多少執行時間和多少額外空間。

演算法的漸進分析是指定義其執行時效能的數學界限/框架。使用漸進分析，我們可以很好地得出演算法的最佳情況、平均情況和最壞情況。

漸進分析可以提供演算法執行時間的三個級別的數學約束：

• 最佳情況由Ω(n)表示。
• 最壞情況由Ο(n)表示。
• 平均情況由Θ(n)表示。

線性資料結構具有順序排列的資料項。下一個資料項可以在下一個記憶體地址中找到。它以順序方式儲存和訪問。陣列和列表是線性資料結構的示例。

以下操作通常在任何資料結構上執行：

• 插入 - 新增資料項

• 刪除 - 刪除資料項

• 遍歷 - 訪問和/或列印所有資料項

• 搜尋 - 查詢特定資料項

• 排序 - 按預定義順序排列資料項

開發演算法有三種常用方法：

• 貪心演算法 - 透過選擇下一個最佳選項來尋找解決方案

• 分治法 - 將問題分解為儘可能小的子問題，並獨立地解決這些子問題

• 動態規劃 - 將問題分解為儘可能小的子問題，並組合地解決這些子問題

以下問題使用貪心演算法方法找到它們的解決方案：

• 旅行商問題
• Prim最小生成樹演算法
• Kruskal最小生成樹演算法
• Dijkstra最小生成樹演算法
• 圖 - 地圖著色
• 圖 - 頂點覆蓋
• 揹包問題
• 作業排程問題

以下問題使用分治演算法方法找到它們的解決方案：

• 歸併排序
• 快速排序
• 二分查詢
• Strassen矩陣乘法
• 最近對（點）

以下問題使用分治演算法方法找到它們的解決方案：

• 斐波那契數列
• 揹包問題
• 漢諾塔
• Floyd-Warshall演算法求所有對最短路徑
• Dijkstra演算法求最短路徑
• 專案排程

連結串列是由連結（即指標或引用）連線的資料項列表。大多數現代高階程式語言不提供直接訪問記憶體位置的功能，因此它們不支援連結串列或以內建函式的形式提供。

在資料結構中，棧是一種抽象資料型別 (ADT)，用於以後進先出 (LIFO) 的方式儲存和檢索值。

棧遵循 LIFO 方法，新增和檢索資料項只需要 O(n) 時間。在我們需要以與它們到達的相反順序訪問資料時使用棧。棧通常用於遞迴函式呼叫、表示式解析、圖的深度優先遍歷等。

以下操作可以在棧上執行：

• push() - 向棧中新增專案

• pop() - 刪除棧頂專案

• peek() - 獲取棧頂專案的 value，但不刪除它

• isempty() - 檢查棧是否為空

• isfull() - 檢查棧是否已滿

佇列是一種抽象資料結構，有點類似於棧。與棧相反，佇列的兩端都是開放的。一端始終用於插入資料（入隊），另一端用於刪除資料（出隊）。佇列遵循先進先出 (FIFO) 方法，即首先儲存的資料項將首先被訪問。

由於佇列遵循 FIFO 方法，因此當我們需要按資料項到達的確切順序處理它們時，我們使用佇列。每個作業系統都維護著各種程序的佇列。優先順序佇列和圖的廣度優先遍歷是一些佇列的例子。

以下操作可以在棧上執行：

• enqueue() - 將專案新增到佇列的尾部

• dequeue() - 從佇列的頭部刪除專案

• peek() - 獲取頭部專案的 value，但不刪除它

• isempty() - 檢查棧是否為空

• isfull() - 檢查棧是否已滿

線性搜尋試圖在一個順序排列的資料型別中找到一個專案。這些順序排列的資料項（稱為陣列或列表）可以在遞增的記憶體位置訪問。線性搜尋將預期資料項與列表或陣列中的每個資料項進行比較。線性搜尋的平均情況時間複雜度為 O(n)，最壞情況複雜度為 O(n²)。目標陣列/列表中的資料不需要排序。

二分查詢僅適用於已排序的列表或陣列。此搜尋選擇中間值，將整個列表分成兩部分。首先比較中間值。

此搜尋首先將目標值與列表的中間值進行比較。如果找不到，則決定是否。

氣泡排序是一種基於比較的演算法，其中比較每一對相鄰元素，如果元素未按順序排列則交換元素。由於時間複雜度為 O(n²)，因此它不適用於大型資料集。

插入排序將列表分成兩個子列表，已排序和未排序。它一次取一個元素，並在已排序的子列表中找到它適當的位置並插入到那裡。插入後的輸出是一個已排序的子列表。它迭代地處理未排序子列表的所有元素，並按順序將它們插入到已排序的子列表中。

選擇排序是一種原地排序技術。它將資料集分成兩個子列表：已排序和未排序。然後，它從未排序的子列表中選擇最小元素，並將其放入已排序的列表中。這個過程會一直迭代，直到未排序子列表中的所有元素都被放入已排序的子列表中。

兩種排序技術都維護兩個子列表，已排序和未排序，並且都一次取一個元素並將其放入已排序的子列表中。插入排序對當前手頭的元素進行操作，並將其放置在已排序陣列中的適當位置，同時保持插入排序的特性。而選擇排序則從未排序的子列表中搜索最小值，並將其與當前手頭的元素替換。

歸併排序是一種基於分治程式設計方法的排序演算法。它不斷將列表分成更小的子列表，直到所有子列表都只有一個元素。然後，它以排序的方式合併它們，直到所有子列表都被合併。它的執行時間複雜度為Ο(n log n)，需要Ο(n)的輔助空間。

希爾排序可以說是插入排序的一種變體。希爾排序根據某個間隔變數將列表分成更小的子列表，然後使用插入排序對每個子列表進行排序。在最佳情況下，它的效能可以達到Ο(n log n)。

快速排序使用分治法。它使用“樞軸”將列表分成更小的“分割槽”。小於樞軸的值排列在左分割槽中，大於樞軸的值排列在右分割槽中。每個分割槽都使用快速排序遞迴排序。

圖是一組物件的圖形表示，其中某些物件對透過連結連線。相互連線的物件由稱為頂點的點表示，連線頂點的連結稱為邊。

深度優先搜尋演算法 (DFS) 以深度優先的方式遍歷圖，並使用堆疊來記住在任何迭代中遇到死鎖時要開始搜尋的下一個頂點。

廣度優先搜尋演算法 (BFS) 以廣度優先的方式遍歷圖，並使用佇列來記住在任何迭代中遇到死鎖時要開始搜尋的下一個頂點。

樹是一個最小連線圖，沒有迴圈和迴路。

二叉樹有一個特殊條件，即每個節點最多可以有兩個子節點。

二叉搜尋樹是一種二叉樹，它有一個特殊的規定：節點的左子節點的值必須小於其父節點的值，而節點的右子節點的值必須大於其父節點的值。

樹的遍歷是訪問樹中所有節點的過程。因為所有節點都透過邊（連結）連線，所以我們總是從根（頭部）節點開始。我們使用三種方法來遍歷樹：

• 中序遍歷
• 前序遍歷
• 後序遍歷

• 中序遍歷：10 14 19 27 31 35 42
• 前序遍歷：27 14 10 19 35 31 42
• 後序遍歷：10 19 14 31 42 35 27

AVL樹是高度平衡的二叉搜尋樹。AVL樹檢查左右子樹的高度，並確保高度差不大於1。這個差值稱為平衡因子。

BalanceFactor = height(left-sutree) − height(right-sutree)

生成樹是圖G的一個子集，它包含所有頂點，並具有儘可能少的邊數。生成樹沒有環，也不能斷開連線。

這取決於圖的連線方式。一個完全無向圖最多可以有n^n-1個生成樹，其中n是節點數。

該演算法將圖視為森林，並將每個節點視為單個樹。只有當樹的成本在所有可用選項中最小且不違反MST屬性時，樹才會連線到另一個樹。

普里姆演算法將節點視為一棵樹，並不斷地從給定圖中向生成樹新增新節點。

在加權圖中，最小生成樹是指權重小於相同圖的所有其他生成樹的生成樹。

堆是一種特殊的平衡二叉樹資料結構，其中根節點鍵與其子節點進行比較並相應地排列。在最小堆中，父節點的鍵值小於其子節點，而在最大堆中，父節點的值大於其子節點。

遞迴函式是指直接或間接呼叫自身的函式。每個遞迴函式都遵循遞迴特性：基本情況，函式停止呼叫自身；遞推關係，函式在每次迭代中試圖滿足基本情況。

漢諾塔是一個數學遊戲，它由三個塔（樁）和多個環組成。所有環的大小都不同，並彼此堆疊，其中大圓盤總是在小圓盤的下方。目標是從一個樁將圓盤塔移動到另一個樁，而不破壞其特性。

斐波那契數列透過將前兩個數字相加來生成後續數字。例如：0 1 1 2 3 5 8 13。

雜湊是一種將一系列鍵值轉換為陣列索引範圍的技術。透過使用雜湊表，我們可以建立一個關聯資料儲存，其中可以透過提供其鍵值來查詢資料索引。

插值查詢是二分查詢的改進變體。該搜尋演算法基於所需值的探測位置。

字首表示法：* + a b + c d

字尾表示法：a b + c d + *