??前幾天更新了計算機網絡面試高頻題面試題，今天開始更新數據結構高頻面試題英文版。點擊此處到公眾號獲取音頻。

What is Data Structure?

• Data structure is a fundamental concept of any programming language, essential for algorithmic design.
• It is used for the efficient organization and modification of data.
• DS is how data and the relationship amongst different data is represented, that aids in how efficiently various functions or operations or algorithms can be applied.

什么是數據結構？

• 數據結構是任何編程語言的基本概念，對算法設計至關重要。
• 它用于有效地組織和修改數據。
• DS 是如何表示數據和不同數據之間的關系的，它有助于提高各種功能或操作或算法的應用效率。

Types

There are two types of data structures:

• Linear data structure: If the elements of a data structure result in a sequence or a linear list then it is called a linear data structure. Example: Arrays, Linked List, Stacks, Queues etc.
• Non-linear data structure: If the elements of data structure results in a way that traversal of nodes is not done in a sequential manner, then it is a non linear data structure. Example: Trees, Graphs etc.

類型

有兩種類型的數據結構：

• 線性數據結構：如果數據結構的元素導致序列或線性列表，則稱為線性數據結構。示例：數組、鏈表、堆棧、隊列等。
• 非線性數據結構：如果數據結構的元素導致節點的遍歷不是按順序進行的，那么它就是非線性數據結構。示例：樹、圖等。

Applications

Data structures form the core foundation of software programming as any efficient algorithm to a given problem is dependent on how effectively a data is structured.

• Identifiers look ups in compiler implementations are built using hash tables.

• The B-trees data structures are suitable for the databases implementation.

• Some of the most important areas where data structures are used are as follows:

• Artificial intelligence
• Compiler design
• Machine learning
• Database design and management
• Blockchain
• Numerical and Statistical analysis
• Operating system development
• Image & Speech Processing
• Cryptography

應用

數據結構構成了軟件編程的核心基礎，因為針對給定問題的任何有效算法都取決于數據結構的有效性。

• 編譯器實現中的標識符查找是使用哈希表構建的。

• B 樹數據結構適用于數據庫實現。

• 使用數據結構的一些最重要的領域如下：

• 人工智能
• 編譯器設計
• 機器學習
• 數據庫設計與管理
• 區塊鏈
• 數值和統計分析
• 操作系統開發
• 圖像和語音處理
• 密碼學

Benefits of Learning Data Structures

Any given problem has constraints on how fast the problem should be solved (time) and how much less resources the problem consumes(space). That is, a problem is constrained by the space and time complexity within which it has to be solved efficiently.

• In order to do this, it is very much essential for the given problem to be represented in a proper structured format upon which efficient algorithms could be applied.

• Selection of proper data structure becomes the most important step before applying algorithm to any problem.

  Having knowledge of different kinds of data structures available helps the programmer in choosing which data structure suits the best for solving a problem efficiently. It is not just important to make a problem work, it is important how efficiently you make it work.

學習數據結構的好處

任何給定的問題都對解決問題的速度（時間）和問題消耗的資源（空間）有所限制。也就是說，一個問題受到空間和時間復雜度的限制，必須在其中有效地解決它。

• 為了做到這一點，以適當的結構化格式表示給定的問題非常重要，在該格式上可以應用有效的算法。

• 在將算法應用于任何問題之前，選擇適當的數據結構成為最重要的一步。

  了解不同類型的可用數據結構有助于程序員選擇最適合有效解決問題的數據結構。讓問題發揮作用不僅重要，更重要的是你讓它發揮作用的效率。

Data structures in C, Java

• The core concepts of data structures remains the same across all the programming languages. Only the implementation differs based on the syntax or the structure of the programming language.
  • The implementation in procedural languages like C is done with the help of structures, pointers, etc.
  • In an objected oriented language like Java, data structures are implemented by using classes and objects.
• Having sound knowledge of the concepts of each and every data structures helps you to stand apart in any interviews as selecting right data structure is the first step towards solving problem efficiently.

C、Java 中的數據結構

• 數據結構的核心概念在所有編程語言中都是相同的。只有實現根據編程語言的語法或結構而有所不同。
  • 像 C 這樣的過程語言的實現是在結構體、指針等的幫助下完成的。
  • 在像 Java 這樣的面向對象語言中，數據結構是通過使用類和對象來實現的。
• 充分了解每種數據結構的概念有助于您在任何面試中脫穎而出，因為選擇正確的數據結構是有效解決問題的第一步。

Interview Questions

1. Can you explain the difference between file structure and storage structure?

• File Structure: Representation of data into secondary or auxiliary memory say any device such as hard disk or pen drives that stores data which remains intact until manually deleted is known as a file structure representation.
• Storage Structure: In this type, data is stored in the main memory i.e RAM, and is deleted once the function that uses this data gets completely executed.
• The difference is that storage structure has data stored in the memory of the computer system, whereas file structure has the data stored in the auxiliary memory.

1. 你能解釋一下文件結構和存儲結構的區別嗎？

• 文件結構：將數據表示到輔助或輔助存儲器中，例如硬盤或筆式驅動器等存儲數據的任何設備，這些數據在手動刪除之前保持不變，稱為文件結構表示。
• 存儲結構：在這種類型中，數據存儲在主存儲器即 RAM 中，一旦使用該數據的功能完全執行，就會被刪除。
• 區別在于存儲結構的數據存儲在計算機系統的內存中，而文件結構的數據存儲在輔助存儲器中。

2. Can you tell how linear data structures differ from non-linear data structures?

• If the elements of a data structure result in a sequence or a linear list then it is called a linear data structure. Whereas, traversal of nodes happens in a non-linear fashion in non-linear data structures.
• Lists, stacks, and queues are examples of linear data structures whereas graphs and trees are the examples of non-linear data structures.

2. 你能說出線性數據結構與非線性數據結構有何不同嗎？

• 如果數據結構的元素產生序列或線性列表，則稱為線性數據結構。然而，節點的遍歷在非線性數據結構中以非線性方式發生。
• 列表、堆棧和隊列是線性數據結構的示例，而圖和樹是非線性數據結構的示例。

3. What is an array?

• Arrays are the collection of similar types of data stored at contiguous memory locations.
• It is the simplest data structure where the data element can be accessed randomly just by using its index number.

3. 什么是數組？

• 數組是存儲在連續內存位置的類似類型數據的集合。
• 它是最簡單的數據結構，只需使用索引號就可以隨機訪問數據元素。

4. What is a multidimensional array?

• Multi-dimensional arrays are those data structures that span across more than one dimension.
• This indicates that there will be more than one index variable for every point of storage. This type of data structure is primarily used in cases where data cannot be represented or stored using only one dimension. Most commonly used multidimensional arrays are 2D arrays.
  • 2D arrays emulates the tabular form structure which provides ease of holding the bulk of data that are accessed using row and column pointers.

4. 什么是多維數組？

• 多維數組是跨越多個維度的數據結構。
• 這表明每個存儲點將有多個索引變量。這種類型的數據結構主要用于無法僅使用一維表示或存儲數據的情況。最常用的多維數組是二維數組。
  • 二維數組模擬表格形式的結構，可以輕松保存使用行和列指針訪問的大量數據。

5. What is a linked list?

A linked list is a data structure that has sequence of nodes where every node is connected to the next node by means of a reference pointer. The elements are not stored in adjacent memory locations. They are linked using pointers to form a chain. This forms a chain-like link for data storage.

• Each node element has two parts:

• • a data field
  • a reference (or pointer) to the next node.

• The first node in a linked list is called the head and the last node in the list has the pointer to NULL. Null in the reference field indicates that the node is the last node. When the list is empty, the head is a null reference.

5. 什么是鏈表？

鏈表是一種具有節點序列的數據結構，其中每個節點都通過引用指針連接到下一個節點。元素不存儲在相鄰的內存位置。它們使用指針鏈接以形成鏈。這形成了用于數據存儲的鏈狀鏈接。

• 每個節點元素有兩部分：

  • 一個數據字段
  • 指向下一個節點的引用（或指針）。

• 鏈表中的第一個節點稱為頭節點，鏈表中的最后一個節點具有指向 NULL 的指針。引用字段中的空值表示該節點是最后一個節點。當列表為空時，頭部為空引用。

6. Are linked lists of linear or non-linear type?

Linked lists can be considered both linear and non-linear data structures. This depends upon the application that they are used for.

• When linked list is used for access strategies, it is considered as a linear data-structure. When they are used for data storage, it can be considered as a non-linear data structure.

6. 鏈表是線性的還是非線性的？

鏈表可以被認為是線性和非線性數據結構。這取決于它們用于的應用程序。

• 當鏈表用于訪問策略時，它被認為是一種線性數據結構。當它們用于數據存儲時，可以認為是一種非線性數據結構。

7. How are linked lists more efficient than arrays?

Insertion and Deletion

• Insertion and deletion process is expensive in an array as the room has to be created for the new elements and existing elements must be shifted.
• But in a linked list, the same operation is an easier process, as we only update the address present in the next pointer of a node.

Dynamic Data Structure

• Linked list is a dynamic data structure that means there is no need to give an initial size at the time of creation as it can grow and shrink at runtime by allocating and deallocating memory.
• Whereas, the size of an array is limited as the number of items is statically stored in the main memory.

No wastage of memory

• As the size of a linked list can grow or shrink based on the needs of the program, there is no memory wasted because it is allocated in runtime.
• In arrays, if we declare an array of size 10 and store only 3 elements in it, then the space for 3 elements is wasted. Hence, chances of memory wastage is more in arrays.

7. 鏈表如何比數組更高效？

插入和刪除

• 數組中的插入和刪除過程是昂貴的，因為必須為新元素創建房間并且必須移動現有元素。
• 但是在鏈表中，相同的操作是一個更簡單的過程，因為我們只更新節點的下一個指針中的地址。

動態數據結構

• 鏈表是一種動態數據結構，這意味著在創建時不需要給出初始大小，因為它可以在運行時通過分配和釋放內存來增長和縮小。
• 然而，數組的大小是有限的，因為項目的數量是靜態存儲在主存儲器中的。

不浪費內存

• 由于鏈表的大小可以根據程序的需要增長或縮小，因此不會浪費內存，因為它是在運行時分配的。
• 在數組中，如果我們聲明一個大小為 10 的數組并且只存儲 3 個元素，那么 3 個元素的空間就被浪費了。因此，數組中內存浪費的可能性更大。

8. Explain the scenarios where you can use linked lists and arrays.

• Following are the scenarios where we use linked list over array:
  • When we do not know the exact number of elements beforehand.
  • When we know that there would be large number of add or remove operations.
  • Less number of random access operations.
  • When we want to insert items anywhere in the middle of the list, such as when implementing a priority queue, linked list is more suitable.
• Below are the cases where we use arrays over the linked list:
  • When we need to index or randomly access elements more frequently.
  • When we know the number of elements in the array beforehand in order to allocate the right amount of memory.
  • When we need speed while iterating over the elements in the sequence.
  • When memory is a concern:
    • Due to the nature of arrays and linked list, it is safe to say that filled arrays use less memory than linked lists.
    • Each element in the array indicates just the data whereas each linked list node represents the data as well as one or more pointers or references to the other elements in the linked list.
• To summarize, requirements of space, time, and ease of implementation are considered while deciding which data structure has to be used over what.

8. 解釋可以使用鏈表和數組的場景。

• 以下是我們在數組上使用鏈表的場景：
  • 當我們事先不知道元素的確切數量時。
  • 當我們知道會有大量的添加或刪除操作時。
  • 更少的隨機訪問操作。
  • 當我們想在鏈表中間的任意位置插入項目時，比如實現優先級隊列時，鏈表更適合。
• 以下是我們在鏈表上使用數組的情況：
  • 當我們需要更頻繁地索引或隨機訪問元素時。
  • 當我們事先知道數組中的元素數量以便分配適量的內存時。
  • 當我們在迭代序列中的元素時需要速度時。
  • 當內存是一個問題時：
    • 由于數組和鏈表的性質，可以肯定地說填充數組比鏈表使用更少的內存。
    • 數組中的每個元素僅表示數據，而每個鏈表節點表示數據以及一個或多個指針或對鏈表中其他元素的引用。
• 總而言之，在決定必須使用哪種數據結構時，需要考慮空間、時間和易于實施的要求。

9. What is a doubly-linked list (DLL)? What are its applications.

• This is a complex type of a linked list wherein a node has two references:
  • One that connects to the next node in the sequence
  • Another that connects to the previous node.
• This structure allows traversal of the data elements in both directions (left to right and vice versa).
• Applications of DLL are:
• A music playlist with next song and previous song navigation options.
• The browser cache with BACK-FORWARD visited pages
• The undo and redo functionality on platforms such as word, paint etc, where you can reverse the node to get to the previous page.

9. 什么是雙向鏈表（DLL）？它的應用是什么。

• 這是一種復雜類型的鏈表，其中一個節點有兩個引用：
  • 一個連接到序列中的下一個節點
  • 另一個連接到前一個節點。
• 這種結構允許在兩個方向（從左到右，反之亦然）遍歷數據元素。
• DLL 的應用有：
• 帶有下一首歌曲和上一首歌曲導航選項的音樂播放列表。
• 具有 BACK-FORWARD 訪問頁面的瀏覽器緩存
• word，paint 等平臺上的撤消和重做功能，您可以在其中反轉節點以到達上一頁。

10. What is a stack? What are the applications of stack?

• Stack is a linear data structure that follows LIFO (Last In First Out) approach for accessing elements.
• Push, pop, and top (or peek) are the basic operations of a stack.
• Following are some of the applications of a stack:
  • Check for balanced parentheses in an expression
  • Evaluation of a postfix expression
  • Problem of Infix to postfix conversion
  • Reverse a string

10. 什么是堆棧？堆棧的應用有哪些？

• 堆棧是一種線性數據結構，遵循 LIFO（后進先出）方法來訪問元素。

• Push、pop 和 top（或 peek）是堆棧的基本操作。

• 以下是堆棧的一些應用：

  • 檢查表達式中的平衡括號
  • 后綴表達式的評估
  • 中綴到后綴轉換的問題
  • 反轉字符串

11. What is a queue? What are the applications of queue?

• A queue is a linear data structure that follows the FIFO (First In First Out) approach for accessing elements.
• Dequeue from the queue, enqueue element to the queue, get front element of queue, and get rear element of queue are basic operations that can be performed.
• Some of the applications of queue are:
  • CPU Task scheduling
  • BFS algorithm to find shortest distance between two nodes in a graph.
  • Website request processing
  • Used as buffers in applications like MP3 media player, CD player, etc.
  • Managing an Input stream

11. 什么是隊列？隊列的應用有哪些？

• 隊列是一種線性數據結構，遵循 FIFO（先進先出）方法來訪問元素。
• 從隊列中出隊、將元素入隊到隊列、獲取隊列的前元素和獲取隊列的后元素是可以執行的基本操作。
• 隊列的一些應用是：
  • CPU 任務調度
  • BFS 算法用于查找圖中兩個節點之間的最短距離。
  • 網站請求處理
  • 在 MP3 媒體播放器、CD 播放器等應用程序中用作緩沖區。
  • 管理輸入流

歡迎關注。

總結

以上是生活随笔為你收集整理的【DS】数据结构八股文英文版(1)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。