Link copied to clipboard. Share away!

Dismiss

Published on 12 Mar 2020

In this article, we will be discussing some of the most asked data structures interview questions by both IT-Service based & Product based companies.

Here are the 30+ most asked data structures interview questions.**Data Structures & Algorithms is one of the most frequently tested subjects** by a lot of companies. So make sure you have a quick look at these questions before the interview.

**1) What do you mean by a Data structure?**

Data structure is a format for storing data in a structured manner.** For example**, data like photos, videos are stored in gallery with the help of a data structure. It is not a separate programming language. It is just an implementation method and can be implemented using any one of the programming language like C, C++, Java, etc.

**2) What** **are some of the** **applications** **of** **DS?**

Some of the real-time applications of Data Structures are:

- For representing a city region telephone network.
- To implement back functionality in the internet web browser.
- To store dynamically growing data which is accessed very frequently, based upon a key value.
- To implement the undo function in a text editor.
- To store information about the directories and files in a system.

For **more applications of each of the data structures**, check out the below links:

- Applications of a Stack
- Applications of Priority Queue
- Applications of Depth First Search
- Applications of Breadth-First Search

**3) What are the advantages of a Linked list over an array?**

**Consider a scenario**, where we need to store large amount of data in an array. But, the memory to store that data is not available contiguously. In this case we cannot use array. Hence, we go for a linked list. Since each node is connected using link, it is not necessary that memory has to be contiguous.

Also, **some of the major differences between a Linked List and an array are given below**. **For more, click here**.

Arrays | Linked List |
---|---|

Array elements can be accessed randomly using the array index. | Random accessing is not possible in linked lists. The elements will have to be accessed sequentially. |

Data elements are stored in contiguous locations in memory. | New elements can be stored anywhere and a reference is created for the new element using pointers. |

**4) Write** **the** **syntax** **in** **C** **to** **create** **a** **node** **in** **the** **singly** **linked** **list**.

```
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node));
```

**5) What is the use of a doubly-linked list when compared to that of a singly linked list?**

In a singly linked list, we have only forward links. Hence, we cannot traverse the linked list in a backward manner. In order to overcome this, we go for a doubly linked list. **In a doubly linked list, each node has three fields such as previous, data and next field and has two links such as a forward and backward link**. The previous field of the first node and the address field of the last node is NULL. The previous field of the second node has the address of the first node and so on.

Also, accessing of elements can be done more efficiently in case of a doubly linked list.

**6) What is the difference between an Array and Stack?**

- Size of the stack keeps on changing as we insert and delete the element
- Stack can store elements of different data type

- Size of the array is fixed at the time of declaration itself
- Array stores elements of similar data type

**7) What are the minimum number of Queues needed to implement the priority queue?**

Two queues are needed. One queue is used to store the data elements, and another is used for storing priorities. **Check out the implementation of a Priority Queue.**

**8) What are the different types of traversal techniques in a tree?**

There are **three main traversals of a tree** such as In-order, Pre-order, Post-order.

**Algorithm of In-order traversal:**

Traverse the left sub-tree Visit the root Traverse the right sub-tree

**Algorithm of Pre-order traversal:**

Visit the root Traverse the left sub-tree Traverse the right sub-tree

**Algorithm of Post-order traversal:**

Traverse the left sub-tree Traverse the right sub-tree Visit the root

**9) Why it is said that searching a node in a binary search tree is efficient than that of a simple binary tree?**

When searching any node in binary search tree, the value of the target node is compared with the parent node and accordingly either left sub tree or right sub tree is searched. So, one has to compare only particular branches. Thus searching becomes efficient.

**10) What are the applications of Graph DS?**

Graphs are **used in circuit networks** where points of connection are drawn as vertices and component wires become the edges of the graph, **in transport networks** where stations are drawn as vertices and routes become the edges of the graph, **in maps** that draw cities/states/regions as vertices and adjacency relations as edges, **in program flow analysis** where procedures or modules are treated as vertices and calls to these procedures are drawn as edges of the graph.

**11) Can we apply Binary search algorithm to a sorted Linked list?**

**No**, we cannot apply the binary search algorithm to a sorted linked list because finding the index of the middle element is difficult.

**12) When can you tell that a Memory Leak will occur?**

A memory leak occurs when a program does not free a block of memory allocated dynamically.

**13) How will you check if a given Binary Tree is a Binary Search Tree or not?**

To know that you need to check the inorder traversal of a binary tree. If it is sorted, then the binary tree is BST. **Click here to know how to perform inorder traversal**.

**14) Which data structure is ideal to perform recursion operation and why?**

Stack is the most ideal for recursion operation. This is mainly because of its LIFO (**Last In First Out**) property, it remembers the elements & their positions, so it exactly knows which one to return when a function is called.

**15) What are some of the most important applications of a Stack?**

Some of the important applications are given below. Check them out to know the detailed code & explanation.

- Balanced parenthesis checker
- Redundant braces
- Infix to postfix using a stack
- Infix to prefix using a stack

**16) Convert the below given expression to its equivalent Prefix And Postfix notations.**

**((A + B) * C - (D - E) ^ (F + G))**

Prefix Notation: ^ * +ABC DE + FG

** postfix Notation: **AB + C * DE FG + ^

Here are **some important programs based on the concepts of data structures** which are important data structures interview questions for freshers.

17)Sorting a stack using a temporary stack

19) Program to reverse first k elements of a queue

20)Program to return the nth node from the end in a linked list

22)Replace each element of the array by its rank in the array

23) Check if a given graph is a tree or not

24) Find out the Kth smallest element in an unsorted array

25) How to find the shortest path between two vertices

Practice more Data Structure questions

If you have any feedback about this
article and want to improve this, please write to **enquiry@faceprep.in**

Explore 'data structures'

×