Data Structure Question Bank

SET-A

(Prepared by Madhulika Sharma)

Q - 1 List out the areas in which data structures are applied extensively.

Sol. Following are the areas in which data structures are applied extensively.

• Operating system- The data structures like priority queues are used for scheduling the jobs in
the operating system.

• Compiler design- The tree data structure is used in parsing the source program. Stack data
structure is used in handling recursive calls.

• Database management system- The file data structure is used in database management
systems. Sorting and searching techniques can be applied on these data in the file.

• Numerical analysis package- The array is used to perform the numerical analysis on the given
set of data.

• Graphics- The array and the linked list are useful in graphics applications.

• Artificial intelligence- the graph and trees are used for the applications like building expression
trees, game playing.

Q -2 What is the difference between the Breadth First Search (BFS) and Depth First
Search (DFS)?

Sol.

Breadth First Search (BFS) Depth First Search (DFS)

It stands for “Breadth First Search” It stands for “Depth First Search”
BFS (Breadth First Search) finds the
DFS (Depth First Search) finds the shortest path
shortest path using the Queue data
using the Stack data structure.
structure.
We walk through all nodes on the same DFS begins at the root node and proceeds as far as
level before passing to the next level in possible through the nodes until we reach the node
BFS. with no unvisited nearby nodes.
When compared to DFS, BFS is slower. When compared to BFS, DFS is faster.
BFS performs better when the target is DFS performs better when the target is far from the
close to the source. source.
BFS necessitates more memory. DFS necessitates less memory.
Nodes that have been traversed multiple When there are no more nodes to visit, the visited
times are removed from the queue. nodes are added to the stack and then removed.
The DFS algorithm is a recursive algorithm that
Backtracking is not an option in BFS.
employs the concept of backtracking.
It is based on the FIFO principle (First In
It is based on the LIFO principle (Last In First Out).
First Out).
 Q - 3 What is AVL tree data structure, its operations, and its rotations? What are the
applications for AVL trees?

Sol. AVL trees are height balancing binary search trees named after their inventors Adelson,
Velski, and Landis. The AVL tree compares the heights of the left and right subtrees and
ensures that the difference is less than one. This distinction is known as the Balance Factor.

BalanceFactor = height(left-subtree) − height(right-subtree)

We can perform the following two operations on AVL tree:

 Insertion: Insertion in an AVL tree is done in the same way that it is done in a binary search
tree. However, it may cause a violation in the AVL tree property, requiring the tree to be
balanced. Rotations can be used to balance the tree.
 Deletion: Deletion can also be performed in the same manner as in a binary search tree.
Because deletion can disrupt the tree's balance, various types of rotations are used to rebalance
it.

An AVL tree can balance itself by performing the four rotations listed below:

 Left rotation: When a node is inserted into the right subtree of the right subtree and the tree
becomes unbalanced, we perform a single left rotation.
 Right rotation: If a node is inserted in the left subtree of the left subtree, the AVL tree may
become unbalanced. The tree then requires right rotation.
 Left-Right rotation: The RR rotation is performed first on the subtree, followed by the LL
rotation on the entire tree.
 Right-Left rotation: The LL rotation is performed first on the subtree, followed by the RR
rotation on the entire tree.

Following are some real-time applications for AVL tree data structure:

 AVL trees are typically used for in-memory sets and dictionaries.
 AVL trees are also widely used in database applications where there are fewer insertions and
deletions but frequent data lookups are required.
 Apart from database applications, it is used in applications that require improved searching.
Q-4 What are the different types of Data Structures?

Sol. The different types of data structures are:

 Arrays: A collection of data values stored sequentially

 Stacks: Last-in-first-out (LIFO) data structures where the element placed last is
accessed first.
 Queues: A first-in-first-out data structure.
 Linked lists: A collection of data values stored in a linear order and connected to each
other
 Graphs: A data structure in which data values are placed in nodes connected by edges
 Trees: Similar to a linked list, but with data values linked in a hierarchical fashion
 Heaps: A binary tree data structure wherein parent data values can be compared to child
data values
 Hash table: A table where each value is assigned a key and then stored, making
accessing individual values easy. 

Q -5 Give some examples greedy algorithms.

Sol. The below given problems find their solution using greedy algorithm approach –

 Travelling Salesman Problem

 Prim's Minimal Spanning Tree Algorithm
 Kruskal's Minimal Spanning Tree Algorithm
 Dijkstra's Minimal Spanning Tree Algorithm
 Graph - Map Coloring
 Graph - Vertex Cover
 Knapsack Problem
 Job Scheduling Problem

Q – 6 In what ways are the elements of a 2D array stored in a computer’s memory?

Sol. 2D arrays are stored in the following ways:

 Row Major Order: -In row-major order, all the rows of any 2D array are arranged in
the memory in contiguous manners.
 Column Major Order: In a column-major order, all the columns of 2D arrays are stored
in the memory at the same level. Similar to the row order, the first column is also
entirely saved into the computer’s memory, followed by the second and the subsequent
columns until the last column is entirely saved. 

Q – 7 Why do we need to do an algorithm analysis?

Sol. A problem can be solved in more than one way using several solution algorithms. Algorithm
analysis provides an estimation of the required resources of an algorithm to solve a specific
computational problem. The amount of time and space resources required to execute is also
determined.
The time complexity of an algorithm quantifies the amount of time taken for an algorithm to run
as a function of the length of the input. The space complexity quantifies the amount of space or
memory taken by an algorithm, to run as a function of the length of the input.

Q – 8 Differentiate between Linear and Binary Search.

Sol.

Linear Search sequentially checks Binary Search continuously divides the

Definition each element in the list until it finds a sorted list, comparing the middle element
match or exhausts the list. with the target value.
Time The time complexity is O(n), where n The time complexity is O(log n), making it
Complexity is the number of elements in the list. faster for larger datasets.
Less efficient, especially for large More efficient, especially for large
Efficiency
datasets. datasets.
Data
Does not require the list to be sorted. Requires the list to be sorted.
Requirement
Implementation Easier to implement. Requires a more complex implementation.
Eliminates half of the search space with
Search Space Examines each element sequentially.
each comparison.
Suitable for small and unsorted
Use Case Ideal for large and sorted datasets.
datasets.

Q – 9 What is a hash table? What is collision resolution in a hash table?

Sol. A hash table is a data structure that maps keys to values using a hash function. It consists of
an array of buckets and each bucket contains a linked list of key-value pairs. The hash function
determines the index of the bucket where a key-value pair should be stored and retrieved.

Collision resolution is the process of handling collisions that occur when multiple keys are
hashed to the same index in a hash table. There are several methods for collision resolution,
including chaining, where each bucket contains a linked list of key-value pairs, and open
addressing, where the hash table probes different buckets until it finds an empty one.

Q – 10 What are the basic operations performed on a tree?

Sol.

 Insertion: Add a new node to the tree while maintaining its properties (e.g., ordering in
search trees).

 Deletion: Remove a node from the tree while preserving its structure.

 Traversal: Visit each node in the tree exactly once in a specific order (preorder, inorder,
postorder).

 Searching: Find a specific node with a given value based on search criteria. 
Q – 11 Explain algorithm for finding Minimum Spanning Tree?

Sol. There are two widely used algorithms for finding minimum spanning tree:

1. Prim's Algorithm
2. Kruskal Algorithm

Prims Algorithm computes the minimum spanning tree by including appropriate vertex and thus
one edge into existing partially constructed tree in successive stages. The time complexity of the
Prim’s Algorithm is O((V+E)logV).

Kruskal Algorithm computes the minimum spanning tree by adding edges one by one into a
growing spanning tree.

Initially from the graph G, consider a forest of all the vertices without any edge.

1. Sort all the edges in ascending order to their costs.

2. Include the edge with minimum cost into the forest if it does not form a cycle in the
partially constructed tree.
3. Repeat step (2) until no edge can be added to the tree.

Q – 12 Classify the Hashing Functions based on the various methods by which the key
value is found.

Sol.

1. Direct method,
2. Subtraction method,
3. Modulo-Division method,
4. Digit-Extraction method,
5. Mid-Square method,
6. Folding method,
7. Pseudo-random method.

Q - 13 What are the categories of AVL rotations?

Sol. Let A be the nearest ancestor of the newly inserted nod which has the balancing factor ±2.
Then the rotations can be classified into the following four categories:

Left-Left: The newly inserted node is in the left subtree of the left child of A.

Right-Right: The newly inserted node is in the right subtree of the right child of A.

Left-Right: The newly inserted node is in the right subtree of the left child of A.

Right-Left: The newly inserted node is in the left subtree of the right child of A.
 Q – 14 Differentiate between Recursion and Iteration.

Sol.

Recursion Iteration

Recursion is at top-down approach. Iteration is a bottom-up approach.

In Iteration, set of statements is executed

When a function calls itself it is called as Recursion. repeatedly until some specified conditions
are satisfied.

Recursion is based on 'base condition', execution of Iteration is based on initializtion,

statement moving towards base condition. termination, updation and execution.

Recursion runs out of the memory if the base condition Iteration results in infinite loop if the
is not met. termination condition is not met.

Recursion takes more space to store new sets of local Iteration does not take as much space
variables. compared to recursion.

Every recursive algorithm can be converted into its Every iteration cannot be converted to
iterative version. recursive version.

Recursion helps to keep our code short and simple. Iteration approach makes the code longer.

Recursion is slower than iteration due to maintenance

Iteration is faster than recursion.
of stack.

It is complex to implement. It is simple to implement.

Instead of making use of 'for, while, do-while' mostly in The iterative functions are implemented
the code execution we try to call the same function with the help of 'for, while, do-while'
again and again. programming constructs.
Q – 15 What are Infix, Prefix, and Postfix notations?

Sol.

Infix Notation: Operators are written between the operands. This is the standard way of writing
expressions. For example: A * (B + C) / D

Postfix Notation/Reverse Polish Notation: Operators are written after the operands, hence the
name. For example: A B C + * D /

Prefix Notation/Polish Notation: Operators are written before the operands. / * A + B C D is

the prefix notation equivalent of the aforementioned postfix notation example.

Q – 16 What are the various approaches for developing algorithms?

Sol. There are 3 main approaches to developing algorithms:

Divide and Conquer: Involves dividing the entire problem into a number of subproblems and
then solving each of them independently.

Dynamic Programming: Identical to the divide and conquer approach with the exception that
all subproblems are solved together

Greedy Approach: Finds a solution by choosing the next best option.

Q – 17 What Is Merge Sort and How Is It Implemented?

Sol. Merge sort belongs to a class of sorting algorithms known as divide and conquer
approaches. It divides a list of elements into two halves and then recursively applies the merge
sort technique on each half, and then merges the two after sorting them individually.

The following is the algorithm for a merge sort.

Q – 18 How do you differentiate between a Tree and Graph Data Structure?
Sol. The following are the key differences between trees and graphs:

 Trees have a root node from which all other nodes originate. Graphs don’t have root
nodes.
 The vertices in a graph can have bidirectional connections. There is only a single path
between two vertices in a tree.
 The nodes in a graph can connect to themselves, which is not possible in a tree.
 Trees are a hierarchical data structure whereas graphs are flat networks.