【DS】数据结构八股文英文版(1)

  前几天更新了计算机网络面试高频题面试题，今天开始更新数据结构高频面试题英文版。点击此处到公众号获取音频。

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:

• 1. Artificial intelligence
  2. Compiler design
  3. Machine learning
  4. Database design and management
  5. Blockchain
  6. Numerical and Statistical analysis
  7. Operating system development
  8. Image & Speech Processing
  9. Cryptography

应用

数据结构构成了软件编程的核心基础，因为针对给定问题的任何有效算法都取决于数据结构的有效性。

• 编译器实现中的标识符查找是使用哈希表构建的。

• B 树数据结构适用于数据库实现。

• 使用数据结构的一些最重要的领域如下：

• 1. 人工智能
  2. 编译器设计
  3. 机器学习
  4. 数据库设计与管理
  5. 区块链
  6. 数值和统计分析
  7. 操作系统开发
  8. 图像和语音处理
  9. 密码学

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?

1. 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.
2. 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.
3. 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. 链表如何比数组更高效？

1. 插入和删除
   • 数组中的插入和删除过程是昂贵的，因为必须为新元素创建房间并且必须移动现有元素。
   • 但是在链表中，相同的操作是一个更简单的过程，因为我们只更新节点的下一个指针中的地址。
2. 动态数据结构
   • 链表是一种动态数据结构，这意味着在创建时不需要给出初始大小，因为它可以在运行时通过分配和释放内存来增长和缩小。
   • 然而，数组的大小是有限的，因为项目的数量是静态存储在主存储器中的。
3. 不浪费内存
   • 由于链表的大小可以根据程序的需要增长或缩小，因此不会浪费内存，因为它是在运行时分配的。
   • 在数组中，如果我们声明一个大小为 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:
  1. A music playlist with next song and previous song navigation options.
  2. The browser cache with BACK-FORWARD visited pages
  3. 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 的应用有：
  1. 带有下一首歌曲和上一首歌曲导航选项的音乐播放列表。
  2. 具有 BACK-FORWARD 访问页面的浏览器缓存
  3. 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 播放器等应用程序中用作缓冲区。
  • 管理输入流

欢迎关注。