# Data Structure Interview Questions for Automation Testing

__Data Structure Interview Questions and Answers:__

There is a list of the top frequently asked Data Structure Interview Questions and Answers are given below.

#### 1. What is data structure?

**Ans** – The term ‘**data**‘ means a value or set of values. It specifies either the value of a variable or a constant. The **Data Structure** is the logical or mathematical arrangement of data in memory. It considers not only the physical layout of the data items in the memory but it is the relationships between the data items and the operations. The Data structure uses in almost every program or software system. Such as Array, Stack, Queue, Linked list, Tree, Graph, Sorting, Searching and Hashing.

#### 2. Define LIFO.

**Ans** –It stands for **Last in First out**. The last inserted item will be deleted first that is why stack is also called **LIFO**.

#### 3. What is a linked list?

**Ans** – A linked list is a dynamic linear data structure that contains a collection of data elements that says nodes.

#### 4. What is a stack?

**Ans** – A stack is a linear data structure in which insertion of the new data element and deletion of an existing data element is done from only one end.

#### 5. What is a queue?

**Ans** – A queue is a linear data structure in which deletion can take place only at one end which called the **Front**, and insertions can take place only at the other end which called the **Rear**.

#### 6. Difference between a PUSH and a POP.

1. Data is added to the stack using the PUSH operation.

It is retrieved using the POP operation.

#### 7. Define postfix expression.

**Ans** – In this postfix expression, operators are written after the operands. This expression is also called the **reverse polish notation**. The expression to multiply two X and Y is written in prefix notation as:

`XY*`

#### 8. What is a dequeue?

**Ans** – Deque is a linear list where items can be inserted or deleted at either end but not from the middle. So, we can insert or delete elements from both the rear and from the end.

#### 9. Explain Binary Search Tree.

**Ans** – A binary search tree is a binary tree in which each node has a value greater than every node of its left sub-tree and less than every node of its right sub-tree. This type of tree does not contain a duplicate value.

#### 10. What is an AVL tree?

**Ans** – AVL Tree is a binary search tree in which the balance factor of any node can have only three values -1, 0 or 1. The name AVL comes from the Russian mathematician **G.M Adelson – Velskii – E.M. Landis** developed this tree in 1962.

#### 11. Difference between NULL and VOID?

**Ans** – 1. NULL is a value.

VOID is a data type identifier.

2. A variable assigned with a NULL value represents an empty value.

The VOID is used for identifying pointers having no initial size.

#### 12. Write the syntax in C to create a node in the singly linked list.

**Ans** – newNode = Node(data);

#### 13. Explain tree traversal.

**Ans** – There are three standard ways of traversing a binary tree T with root R.

1. Preorder Traversal

2. In order Traversal

3. Postorder Traversal

#### 14. How does Kruskal’s Algorithm work?

**Ans** – Kruskal’s algorithm treats a graph as a forest and each node in it as an individual tree. A tree connects to another tree only if it:

i. It has the least cost among all the available options.

ii. It does not violate the MST properties.

#### 15. What do you understand by Heap in data structure?

**Ans** – A heap is a complete binary tree and it is implemented in an array as the sequential representation rather than a linked representation. In Data Structure, there are mainly two types of Heap. A heap says **Max Heap** or Descending Heap if every node of the heap has a value greater than or equal to the value of every child of that node. Similarly, a heap says **Min Heap** or Ascending Heap if every node of the heap has a value less than or equal to the value of every child of that node.

#### 16. Explain the Tower of Hanoi problem.

**Ans** – Tower of Hanoi is a famous recursive problem that is based on 3 pegs and a set of discs of different sizes.

#### 17. Define Hashing.

**Ans** – **Hashing** is defined as a function that takes a key (k) as input and provides a bucket index as output.

#### 18. Write the recursive C function to count the number of nodes present in a binary tree.

**Ans** –

static int counter = 0; int countnodes(struct node *root) { if(root != NULL) { countnodes(root->left); counter++; countnodes(root->right); } return counter; }

#### 19. Which sorting algorithm is considered the fastest? Why?

**Ans** – Quick Sort algorithm is generally considered the fastest algorithm because:

i. Quick Sort is a cache-efficient algorithm.

ii. It can skip some swaps.

iii. It is also efficient even in worst-case input sets, as the order is generally random.

iv. Easy adaption to already- or mostly-sorted inputs.

#### 20. Difference between BFS and DFS.

**Ans** – 1. BFS uses a Queue data structure.

DFS uses a Stack data structure.

2. The BFS algorithm traverses a graph in the breadth-wards motion.

DFS algorithm traverses a graph in the depth-ward motion.

3. BFS operates using the FIFO list.

DFS operates using the LIFO list