前 30 名數據結構和算法面試問題和答案 [針對應屆生和有經驗者]
已發表: 2021-08-31數據結構和算法是計算機科學與工程領域最重要的學科之一。 如果你參加軟件工程面試，你肯定會面臨一系列專門針對數據結構和算法的問題——這就是它們的重要性！
算法是計算機科學和數據科學中發生的一切的核心。 從機器學習到人工智能再到區塊鏈——所有技術都基於算法運行。 算法需要數據結構才能發揮作用。 因此，數據結構和算法的綜合知識可以幫助你在面試中脫穎而出。
然而，挑戰在於 DSA 是一個廣泛的領域。 在這裡，學習永無止境，總有一些新的發展需要你去了解。 雖然在處理數據結構和算法時必須不斷提高技能，但今天，我們將了解一些 DSA 基礎知識，這些基礎知識將幫助您在技術面試中脫穎而出。
目錄
頂級數據結構和算法面試問答
- 您對“數據結構”了解多少？
數據結構可以定義為用於系統地定義、存儲和訪問數據的技術。 它們構成了任何算法中最重要的組成部分。 根據數據結構的類型，它們存儲不同類型的數據並以不同的方式訪問。 對於返回結果的算法，它需要以有組織且有效的方式對一組數據結構進行操作和操作，以得出最終結果。
- 如何區分文件結構和數據結構？
在文件結構中，數據按照標准文件存儲策略存儲在磁盤上，並且與外部第三方應用程序不兼容。 另一方面，在數據結構中，數據以定制的存儲策略存儲在磁盤和 RAM 上，並且與外部應用程序高度兼容。
- 數據結構的主要類型有哪些？
數據結構大致可以分為兩類：
- 線性：在這種情況下，所有元素都按順序存儲，檢索是線性進行的。 該排列是非分層的，每個元素都有一個後繼和一個前任。 示例——數組、鍊錶、堆棧、隊列等。
- 非線性：這裡的存儲不是以線性順序發生的——也就是說，所有元素不一定只有一個後繼和前驅。 相反，非線性數據結構中的元素以非線性方式連接到兩個或多個項目。 示例——樹、圖、堆。
4. 數據結構的一些關鍵使用領域是什麼？
您能想到的所有計算領域都需要數據結構，尤其是算法和算法優化。 以下是數據結構廣泛使用的其他一些領域：
- 操作系統設計
- 數值分析
- 機器學習和人工智能
- 編譯器設計與開發
- 數據庫管理
- 詞法分析
- 圖形化編程
- 搜索和排序算法等。
- 解釋堆棧數據結構並提及其使用領域。
堆棧只是一個有序列表，它只允許從一端插入和刪除——這就是所謂的“頂部”。 它是一個遞歸數據結構，它有一個指向其“頂部”元素的指針，它讓我們知道堆棧的最頂部元素。 基於元素檢索策略，堆棧也稱為後進先出，因為最後壓入堆棧的元素將在頂部，並且將最先被彈出。 以下是堆棧數據結構的一些用途：
- 回溯
- 內存管理
- 函數返回和調用
- 表達式評估
- 可以在堆棧上執行哪些操作？
堆棧數據結構支持以下三種操作：
- push() — 將一個元素插入到 Stack 的頂部位置。
- pop()——從棧頂取出一個元素。
- peek() — 只檢查堆棧頂部的元素，而不將其從堆棧中取出。
- 你對後綴表達式了解多少？
後綴表達式是運算符跟在操作數後面的表達式。 這在計算術語中非常有益，因為它不需要將任何子表達式分組到括號中，甚至不需要考慮運算符優先級。 表達式 a+b 在後綴中簡單地表示為 ab+。
- 二維數組元素如何存儲在內存中？
二維數組的元素可以通過以下兩種方式之一存儲在內存中：
- Row-Major：在這種方法中，首先將數組的所有行連續存儲在內存中。 首先，第一行完全存儲，然後是第二行，依此類推，直到最後一行。
- Column-Major：在這種情況下，數組的所有列都連續存儲在內存中。 首先，第 1 列完全存儲，然後是第 2 列，依此類推。
- 定義鍊錶數據結構。
鍊錶是節點的集合——它們是隨機存儲的對象。 每個節點都有兩個內部元素——一個數據字段和一個鏈接字段。 Data 字段保存特定節點具有的值，而 Link 字段具有指向該節點鏈接到的下一個節點的指針。 根據情況，鍊錶既可以被認為是線性數據結構，也可以被認為是非線性數據結構。
- 鍊錶在哪些方面比數組更好？
鍊錶在以下方面優於數組：
- 數組大小在運行時是固定的，以後不能修改，但鍊錶可以根據需要實時擴展。
- 鏈接列表不是連續存儲在內存中的，因此，它們比靜態存儲的數組更節省內存。
- 任何鍊錶中可以存儲的元素數量僅限於可用的內存空間，而元素的數量受數組大小的限制。
- 在 C 編程語言中，您將使用哪個指針來實現異構鍊錶？
異構鍊錶，顧名思義，包含不同的數據類型。 因此，這裡不能使用普通的指針。 因此，Void 指針通常用於這種情況，因為它們能夠指向任何類型的值。
- 什麼是雙向鍊錶？
顧名思義，雙向鍊錶是一個鍊錶，它的節點鏈接到後續節點和前面的節點。 結果，雙向鍊錶的節點具有三個而不是兩個字段：
- 數據字段
- 下一個指針（用於指向下一個節點）
- 前一個指針（用於指向前一個節點）
- 解釋隊列數據結構及其一些應用。
隊列是一個有序列表，允許從兩端插入和刪除元素 - 稱為 REAR 和 FRONT。 插入從 FRONT 端進行，而從 REAR 端刪除。 因此，隊列通常被稱為先進先出 (FIFO)。 以下是隊列作為數據結構的一些廣泛應用：
- 用於單個共享資源（如 CPU、打印機、磁盤等）的等待列表。
- 對於數據的異步傳輸，例如文件 IO、套接字、管道。
- 作為大多數媒體播放器應用程序中的緩衝區。
- 在操作系統中用於處理中斷。
- 你能列出使用數組實現隊列的一些缺點嗎？
使用數組實現隊列主要有兩個缺點：
- 內存管理不善，因為數組是靜態數據結構，所以用數組實現隊列會刪除隊列的許多功能。
- 大小問題，因為數組大小是在數組定義期間定義的。 因此，如果我們想向隊列中添加比數組大小更多的元素，這是不可能的。
- 為了將元素插入循環隊列，應滿足哪些條件？
以下是有關插入循環隊列的一些相關條件：
- 如果 (rear + 1)%maxsize == front -> 這意味著隊列已滿 -> 無法再插入。
- 如果rear != max – 1，則rear 的值將增加到maxsize，並且將在後端插入一個新值。
- 如果 front != 0 和 back == max -1 –> 這意味著隊列未滿。 因此，rear 的值被設置為 0，並且一個新元素被插入到循環隊列的後端。
16. 什麼是出隊？
雙端隊列或雙端隊列是一組有序的元素，有助於從兩端（後端和前端）進行插入和刪除。 因此，這甚至比隊列數據結構更靈活。
- 定義樹數據結構並列出一些類型的樹。
樹是包含各種節點的非線性遞歸數據結構。 一個特定節點被指定為所有其他節點出現的樹的根。 除根外，其他所有節點都稱為子節點。 大致有以下類型的樹數據結構：
- 一般樹木
- 二叉樹
- 二叉搜索樹
- 森林
- 表達式樹
- 比賽樹
- 冒泡排序是如何工作的？
冒泡排序是最常用的排序算法之一，通過比較相鄰元素並根據它們的值交換它們的位置與數組一起使用。 之所以稱為冒泡排序，是因為其工作原理的可視化就像從水面上漂浮的氣泡和下沉的更大實體。
閱讀： C 中的數據結構以及如何使用？
- 最快的排序算法是什麼？
有許多不同的排序算法可用，如歸併排序、快速排序、冒泡排序等。 其中，我們無法選擇一種客觀上最快的特定算法，因為它們的性能會根據輸入數據、算法處理數據後的反應以及數據的存儲方式而有很大差異。
- 什麼是二叉樹？
二叉樹是一種特殊類型的樹，其中每個節點最多可以有兩個孩子。 為方便起見，二叉樹通常分為三個不相交的集合——根節點、右子樹和左子樹。
- 與 BST 相比，AVL 樹如何用於各種操作？
AVL 樹是高度平衡的樹，因此它們不允許樹從任何一側傾斜。 對高度為 h 的 BST 執行的所有操作所花費的時間為 O(h)。 然而，在最壞的情況下，這可能會繼續為 O(n) - BST 變得偏斜。 AVL 通過限制樹的高度來幫助消除這種限制。 這樣做時，它對所有操作施加了一個上限，使其最大值為 O(log n)，其中 n = 節點數。
- B樹的屬性是什麼？
m 階 B-Tree 包含以下屬性：
- M-way 樹的所有屬性。
- B_tree 的每個節點最多有 m 個子節點。
- 除根和葉之外的每個節點都至少有 m / 2 個子節點。
- 根節點必須至少有 2 個子節點。
- 所有葉節點必須位於同一水平面上。
- 你對圖數據結構了解多少？
圖 (G) 數據結構可以定義為有序集 G(V,E)，其中 V 表示頂點集，E 是形成連接的邊。 基本上，圖可以被認為是一個循環樹，其中節點可以維護它們之間的複雜關係，而不僅僅是父子關係。
- 參考圖數據結構區分循環、路徑和電路。
循環、路徑、電路的區別如下：
- 補丁是由邊連接的相鄰頂點的順序，沒有任何限制。
- 循環是一條閉合路徑，其中初始頂點與結束頂點相同。 在一個循環中，沒有特定的頂點可以被訪問兩次。
- 迴路就像循環一樣，是一條閉合路徑，其初始頂點與結束頂點相同。 但是，可以多次訪問電路中的任何特定頂點。
- 克魯斯卡爾算法是如何工作的？
Kruskal 算法將圖視為森林，將其每個節點視為一棵單獨的樹。 當且僅當一棵樹在所有選項中成本最低且不違反最小生成樹 (MST) 的性質時，才稱該樹連接到另一棵樹。
相關：數據結構中的二叉樹
- Prim 的算法是如何找到生成樹的？
Prim 的算法通過將節點視為單個樹來工作。 然後，它不斷地從給定的圖中將新節點添加到生成樹中，這些節點必須轉換為所需的生成樹。
- 什麼是最小生成樹 (MST)？
在加權圖中，MST 是具有最小權重的樹，但它們跨越所有頂點。
- 什麼是遞歸函數？
根據定義，遞歸函數回調自身或直接調用調用它的函數。 每個遞歸函數都有一些基本條件，函數停止調用自身。
- 什麼是插值搜索技術？
插值搜索技術是對二分搜索方法的修改。 插值搜索算法作用於期望值的探測位置。
- 什麼是哈希？
散列是一種非常有用的技術，用於將一系列鍵值對轉換為數組的索引。 哈希表在創建關聯數據存儲時派上用場，只需提供其鍵值對即可在其中輕鬆找到數據索引！
綜上所述
數據結構確實是計算機科學中發生的所有其他事情的基礎。 即使是更複雜的計算機科學應用，例如數據科學、機器學習、人工智能、物聯網，也都建立在數據結構和算法之上。
因此，如果您是一名初學者，希望在任何新時代領域有所作為，建議您從掌握數據結構和算法開始。 或者，您還可以查看我們為初學者設計的數據科學執行 PG 計劃課程。 從頭開始學習，成為數據科學專家。 今天就讓自己報名吧！
哪個職位的面試通常會問數據結構和算法問題？
如果您擔任任何軟件開發或工程角色，肯定會檢查您的 DSA 技能。 除此之外，如果您正在申請數據科學工作或想涉足機器學習，您將需要了解 DSA。
我需要了解編程才能理解數據結構和算法嗎？
不，不一定。 DSA 大多是抽象的，它完全是關於任何應用程序或程序幕後發生的數學、表示和流程。 雖然在實現算法時擁有編程經驗會派上用場，但這絕不是學習 DSA 的先決條件。
數據結構總是靜態的嗎？
不，數據結構既可以是動態的也可以是靜態的，這取決於內存分配的方式。 例如，數組是靜態數據結構，因為在定義它們時會為它們分配大量連續的內存。 另一方面，鍊錶是動態數據結構，因為它們沒有任何固定大小，並且節點的數量可以根據程序員的要求增加。