Q. What is Data Structure
Answer: A data structure is a way of organizing and storing data so that it can be accessed and modified efficiently. Choosing the right data structure improves program performance and scalability. Data structures are broadly classified as linear (arrays, lists, stacks, queues) and non-linear (trees, graphs). They define relationships among data elements and the operations allowed on them.Example: Using a stack for function calls in recursion.
Q. What is Algorithm Analysis
Answer: Algorithm analysis evaluates an algorithm’s efficiency in terms of time and space. Running time calculations estimate how execution time grows with input size using asymptotic notations like O, Θ, and Ω. This helps compare algorithms independent of hardware or language. Best, average, and worst cases are considered to understand behavior under different inputs.Example: Binary search runs in O(log n) time.
Q. Define an Abstract Data Type (ADT).
An Abstract Data Type (ADT) is a mathematical model that defines a data structure purely in terms of its behavior and operations, without specifying implementation details. ADTs separate what operations do from how they are performed. This allows multiple implementations while keeping the interface consistent. For example, a Stack ADT defines operations such as push, pop, peek, and isEmpty. These operations describe behavior, but the stack may be implemented using arrays or linked lists. ADTs help in modular program design because implementation changes do not affect the rest of the program. Real-life example: ATM banking systems use ADTs for account operations while hiding internal data storage.
Q. What are Arrays and Pointers
Answer: Arrays store elements of the same data type in contiguous memory locations, enabling fast random access. Pointers store addresses and allow dynamic access to array elements. Multidimensional arrays represent data in tabular or matrix form. Arrays are efficient but have fixed size.Example: A 2D array used to store marks of students.
Q. What is String Processing
Answer: Strings are sequences of characters stored in arrays and terminated by a null character in C. String processing includes operations like concatenation, comparison, searching, and substring extraction. Efficient string handling is essential in text processing and compilers.Example: Using strcmp() to compare two strings.
strcmp() to compare two strings.Q. What is List and List ADT (Singly, Doubly, Circular)
Answer: A list is a collection of elements arranged sequentially. List ADT defines operations like insert, delete, and traverse. Singly linked lists store one link, doubly linked lists store two links, and circular lists connect last node to first. Lists allow dynamic memory usage.Example: Circular list used in round-robin scheduling.
Q. What is a Stack and Stack ADT
Answer: A stack is a linear data structure that follows LIFO (Last In First Out). Stack ADT supports push, pop, and peek operations. Stacks are used in expression evaluation, recursion, and syntax parsing. They can be implemented using arrays or linked lists.
Example: Stack used for function call management.Q. Difference between array and linked list.
An array is a contiguous block of memory where elements are stored sequentially, allowing constant-time random access using index positions. However, inserting and deleting elements is costly because shifting is required. A linked list uses nodes containing data and pointers; nodes need not be contiguous. This allows efficient insertions and deletions but slower access because traversal is needed.
Example:
Array: Best for applications like storing marks of students where size is fixed.
Linked List: Best for dynamic applications like playlist management, where songs may be frequently added or removed.
Q. Write two applications of a stack.
Stacks follow LIFO (Last In, First Out) order, useful for problems requiring reversal or backtracking.
Applications:
Expression evaluation: Compilers use stacks to convert infix expressions like A+BC* into postfix and to evaluate them.
Function call management: The runtime system stores activation records for each function call on a call stack.
Example: When recursion occurs, each recursive call pushes a new frame on the stack. Once the base case is reached, frames are popped in reverse order, correctly producing results. Web browsers also use stacks for navigation history—Back and Forward operations.
Q. Convert A + B * C to postfix.
Infix notation follows normal algebraic rules, while postfix (Reverse Polish Notation) removes parentheses and operator precedence is handled by order.
Conversion:
Expression: A + B * C
Since multiplication has higher precedence than addition, evaluate BC* first.
Postfix = A B C * +
Explanation:
A is pushed to output
B and C are processed
is applied to B and C
is applied last
Example: Using a stack algorithm, operators are pushed, and when a higher-precedence operator arrives, previous operators are popped. Postfix expressions simplify machine execution and eliminate parentheses for compilers.
Q. What is a circular queue?
A circular queue is a linear data structure where the last position connects back to the first, forming a circle. It overcomes the limitation of a normal queue where space cannot be reused after deletion. Circular queues use two pointers—front and rear—and operate using modulo arithmetic.
Example: In a circular queue of size 5, after inserting 5 elements and deleting 3, new insertions will use the freed spaces at the beginning.
Circular queues are used in CPU scheduling (Round Robin), buffering in printers, and managing traffic lights because they efficiently cycle through fixed-size tasks.
Q. Define a binary tree.
A binary tree is a hierarchical data structure where each node has at most two children: left and right. It is used to represent hierarchical relationships and provides efficient search, insertion, and deletion depending on structure.
Example:
Expression trees: Internal nodes represent operators (+, *, /).
Binary Search Trees (BST): Left child contains smaller values; right child contains larger values.
Binary trees form the foundation for advanced structures like AVL trees, heaps, and Huffman trees. They help optimize operations such as searching from O(n) in lists to O(log n) in balanced trees.
Q. What is a sparse matrix?
A sparse matrix is a matrix in which most of the elements are zero. Storing all elements wastes memory, so compact representations—like 3-tuple format or linked lists—store only non-zero values along with their row and column indices.
Example:
Matrix:
0 0 0 5
0 8 0 0
0 0 0 0
Sparse representation stores only:
(0,3,5), (1,1,8)
Sparse matrices are used in scientific computing, graph adjacency matrices, and machine learning because they efficiently handle huge datasets with few meaningful values.
Q. Difference between BST and AVL tree.
A Binary Search Tree (BST) stores nodes such that the left child is smaller and the right child is larger. However, a BST may become unbalanced (like a linked list), causing operations to degrade to O(n).
An AVL tree is a self-balancing BST where the height difference (balance factor) between left and right subtrees is maintained at −1, 0, or +1. Rotations restore balance automatically.
Example: Inserting sorted data (1,2,3,4,5) creates a skewed BST but an AVL tree automatically rotates to maintain O(log n) height, improving search performance significantly.
Q. What is hashing?
Hashing is a technique that converts keys into array indices using a hash function. It enables constant-time average search, insert, and delete operations. When two keys hash to the same index (collision), techniques like chaining or open addressing are used to resolve it.
Example: A dictionary storing names uses a hash function to compute an index for each name. Instead of searching sequentially, the name “Amit” maps directly to its slot, offering faster lookup. Hashing is used in databases, compilers, password storage, and caching.
Q. Define BFS.
Breadth-First Search (BFS) is a graph traversal algorithm that visits nodes level by level. It uses a queue to explore all neighbors of a node before moving to the next level. BFS ensures the shortest path in unweighted graphs.
Example: In a social network graph, BFS finds the shortest connection path between two users—like “Degrees of Separation.”
Steps:
Start at a source vertex.
Visit all adjacent vertices.
Add them to the queue.
Continue until all reachable vertices are visited.
BFS is widely used in network routing, web crawling, and solving puzzles like the shortest path in a maze.
Q. (a) Explain running time calculation
(b) Algorithm to insert an element in a 1D array
(a) Running Time Calculation
Running time describes how the execution time of an algorithm grows with input size. It is expressed using Big-O notation. For example, a loop that runs n times has O(n) complexity. Nested loops generate O(n²). Constant-time operations like accessing an array element take O(1).
Example:
To find maximum in an array of n elements, the algorithm compares each element once → O(n).
Time complexity helps compare algorithms independent of hardware and programming language.
(b) Array Insertion Algorithm (at Position pos)
Start from the last element and shift elements right until pos.
Insert new value at pos.
Update size.
Example: Inserting 50 at index 2 shifts later elements, making insertion O(n).
Q. (a) Singly, doubly, and circular linked lists
(b) Reverse a singly linked list
a) Types of Linked Lists
Singly Linked List: Each node points to next. Easy insertion/deletion but no backward traversal.
Doubly Linked List: Nodes have next and previous pointers, allowing two-way traversal but requiring more memory.
Circular Linked List: Last node points to first, avoiding NULL pointers and supporting cyclic operations.
Example: Round-robin CPU scheduling uses circular lists.
(b) Algorithm to Reverse a Singly Linked List
Use three pointers: prev, curr, next.
Iterate through the list, reversing each link.
Example: List: 10 → 20 → 30 becomes 30 → 20 → 10.
Q. (a) Stack operations using arrays
(b) Evaluate postfix expression: 25 7 3 * + 9 -**
(a) Stack Using Arrays
Stack is implemented using an array and a top pointer.
Operations:
push(x): increment top, place x.
pop(): return array[top--].
peek(): return array[top].
isEmpty(): top == -1.
Example: Browser navigation or undo features.
(b) Evaluate Postfix Expression
Expression: 25 7 3 * + 9 -
Push 25
Push 7
Push 3
Evaluate 7*3 = 21 → push 21
25 + 21 = 46
46 - 9 = 37
Final answer = 37
Q. (a) Sparse matrix representation
(b) Addition & multiplication algorithms
(a) Representing Sparse Matrix
Sparse matrices contain mostly zero values.
Array Representation: Use triplet format (row, column, value).
Linked List Representation: Nodes store row, column, and value with pointers.
Example: Graph adjacency matrices.
(b) Sparse Matrix Addition & Multiplication
Addition: Traverse both lists in order; add values with the same row & column.
Multiplication: Multiply matching row/column pairs and sum partial products.
Example: In adding two sparse matrices, only non-zero elements are processed, improving efficiency.
15. (a) Binary tree traversals
(b) Insert keys into BST
(a) Tree Traversals
Inorder (LNR): Left → Node → Right
Example: Gives sorted order in BST.
Preorder (NLR): Node → Left → Right
Example: Used to create a copy of a tree.
Postorder (LRN): Left → Right → Node
Example: Deletes tree nodes safely.
(b) BST Construction
Insert: 50, 30, 20, 40, 70, 60, 80
The BST formed is:
50
/ \
30 70
/ \ / \
20 40 60 80
BST supports efficient search O(log n) when balanced.
Q. (a) AVL tree rotations
(b) Heap creation & deletion
(a) AVL Rotations
AVL trees self-balance using rotations:
LL Rotation: Fixes left-heavy imbalance.
RR Rotation: Fixes right-heavy imbalance.
LR & RL Rotations: Double rotations for complex cases.
Example: Inserting 30, 20, 10 causes LL imbalance → rotate right.
(b) Heap Operations
Creation (Heapify): Insert elements, percolate up to maintain max/min heap property.
Deletion: Remove root, replace with last element, percolate down.
Example: Priority queues use heaps for scheduling tasks.
Q. (a) Merge sort
(b) Compare bubble, selection & insertion sort
(a) Merge Sort
Merge sort uses divide-and-conquer.
Steps:
Divide array into halves recursively.
Sort each half.
Merge sorted halves.
Example: Sorting [8,3,5,2] → merge steps produce [2,3,5,8].
Time complexity: O(n log n), stable.
(b) Comparison
Bubble Sort: Repeatedly swaps adjacent elements; O(n²); simple but slow.
Selection Sort: Finds minimum each pass; O(n²); fewer swaps.
Insertion Sort: Inserts into sorted part; O(n²) but best-case O(n) for nearly sorted data.
Q. Short notes (any two)
(a) Hashing Techniques & Collision Resolution
Hashing maps keys to indices.
Collision resolution:
Chaining: Linked lists at each index.
Open Addressing: Linear probing, quadratic probing, double hashing.
Example: Hash tables in dictionaries.
(b) B-Trees & B+ Trees
B-Trees store keys and values in internal nodes; B+ Trees keep data only in leaf nodes with linked leaves.
Example: Databases use B+ Trees for range queries.
(c) Polynomial Representation
Store coefficients and powers using linked lists.
Example: (5x² + 3x + 1) stored as nodes and supports addition/multiplication.
Q. Disjoint Sets
(a) MAKE-SET, FIND, UNION
(b) Union-by-rank & Path compression
(c) Applications
(a) Disjoint Set Operations
Disjoint sets store elements divided into non-overlapping groups.
MAKE-SET(x): Creates a new set with element x as its own parent.
FIND(x): Returns the representative (root) of the set containing x.
UNION(x, y): Merges two sets by linking their roots.
These operations efficiently organize components in dynamic connectivity problems.
(b) Union-by-Rank & Path Compression
Union-by-Rank: Always attaches the shorter tree under the taller one to avoid increasing height.
Path Compression: During FIND, nodes along the path point directly to the root, flattening the structure.
Combined, they make operations almost O(1) amortized.
Example: Sets {1,2}, {3,4} can be merged efficiently while keeping shallow trees.
(c) Applications
Used in network connectivity, clustering, image segmentation, and Kruskal’s MST algorithm to detect cycles.
Q. Graphs and Traversals
(a) Graph Representations
(b) BFS & DFS algorithms
(c) Applications
(a) Graph Representation
Adjacency Matrix: 2D array storing edges; easy to use but space O(n²).
Adjacency List: Stores neighbors using linked lists; efficient for sparse graphs.
Example: Social networks prefer adjacency lists.
(b) BFS & DFS
BFS: Uses a queue, explores level by level.
DFS: Uses stack/recursion, explores deeply before backtracking.
Example Traversal: For graph 1–2–3–4, BFS gives 1,2,3,4; DFS gives 1,2,3,4 but order may vary depending on branching.
(c) Applications
BFS: Shortest path in unweighted graphs, web crawling, friend suggestions.
DFS: Cycle detection, topological sorting, maze solving.
Q. Minimum Spanning Tree & Shortest Path
(a) Prim’s & Kruskal’s
(b) Dijkstra’s Algorithm
(c) MST vs Shortest Path
(a) Prim’s & Kruskal’s Algorithms
Prim’s Algorithm: Grows MST from a starting node by repeatedly choosing the minimum-weight edge connecting visited and unvisited nodes.
Example: Works like expanding a connected region outward.
Kruskal’s Algorithm: Sorts all edges and keeps adding the smallest edge that doesn’t create a cycle, using disjoint sets to check cycles.
Example: Useful for sparse graphs.
(b) Dijkstra’s Shortest Path
Computes shortest path from a source to all vertices in a weighted graph (no negative weights). It selects the nearest unvisited node, updates distances, and repeats.
Example: Finding the fastest route in Google Maps.
(c) MST vs Shortest Path
MST connects all vertices with minimum total weight but does not consider paths between specific nodes.
The shortest path gives minimum distance between two nodes but doesn’t need to include all nodes.
Example:
Array: Best for applications like storing marks of students where size is fixed.
Linked List: Best for dynamic applications like playlist management, where songs may be frequently added or removed.
Applications:
Expression evaluation: Compilers use stacks to convert infix expressions like A+BC* into postfix and to evaluate them.
Function call management: The runtime system stores activation records for each function call on a call stack.
Example: When recursion occurs, each recursive call pushes a new frame on the stack. Once the base case is reached, frames are popped in reverse order, correctly producing results. Web browsers also use stacks for navigation history—Back and Forward operations.
Conversion:
Expression: A + B * C
Since multiplication has higher precedence than addition, evaluate BC* first.
Postfix = A B C * +
Explanation:
A is pushed to output
B and C are processed
is applied to B and C
is applied last
Example: Using a stack algorithm, operators are pushed, and when a higher-precedence operator arrives, previous operators are popped. Postfix expressions simplify machine execution and eliminate parentheses for compilers.
Example: In a circular queue of size 5, after inserting 5 elements and deleting 3, new insertions will use the freed spaces at the beginning.
Circular queues are used in CPU scheduling (Round Robin), buffering in printers, and managing traffic lights because they efficiently cycle through fixed-size tasks.
Example:
Expression trees: Internal nodes represent operators (+, *, /).
Binary Search Trees (BST): Left child contains smaller values; right child contains larger values.
Binary trees form the foundation for advanced structures like AVL trees, heaps, and Huffman trees. They help optimize operations such as searching from O(n) in lists to O(log n) in balanced trees.
Example:
Matrix:
0 0 0 5
0 8 0 0
0 0 0 0
Sparse representation stores only:
(0,3,5), (1,1,8)
Sparse matrices are used in scientific computing, graph adjacency matrices, and machine learning because they efficiently handle huge datasets with few meaningful values.
An AVL tree is a self-balancing BST where the height difference (balance factor) between left and right subtrees is maintained at −1, 0, or +1. Rotations restore balance automatically.
Example: Inserting sorted data (1,2,3,4,5) creates a skewed BST but an AVL tree automatically rotates to maintain O(log n) height, improving search performance significantly.
Example: A dictionary storing names uses a hash function to compute an index for each name. Instead of searching sequentially, the name “Amit” maps directly to its slot, offering faster lookup. Hashing is used in databases, compilers, password storage, and caching.
Example: In a social network graph, BFS finds the shortest connection path between two users—like “Degrees of Separation.”
Steps:
Start at a source vertex.
Visit all adjacent vertices.
Add them to the queue.
Continue until all reachable vertices are visited.
BFS is widely used in network routing, web crawling, and solving puzzles like the shortest path in a maze.
Example:
To find maximum in an array of n elements, the algorithm compares each element once → O(n).
Time complexity helps compare algorithms independent of hardware and programming language.
Start from the last element and shift elements right until pos.
Insert new value at pos.
Update size.
Example: Inserting 50 at index 2 shifts later elements, making insertion O(n).
Singly Linked List: Each node points to next. Easy insertion/deletion but no backward traversal.
Doubly Linked List: Nodes have next and previous pointers, allowing two-way traversal but requiring more memory.
Circular Linked List: Last node points to first, avoiding NULL pointers and supporting cyclic operations.
Example: Round-robin CPU scheduling uses circular lists.
Iterate through the list, reversing each link.
Example: List: 10 → 20 → 30 becomes 30 → 20 → 10.
Operations:
push(x): increment top, place x.
pop(): return array[top--].
peek(): return array[top].
isEmpty(): top == -1.
Example: Browser navigation or undo features.
Push 25
Push 7
Push 3
Evaluate 7*3 = 21 → push 21
25 + 21 = 46
46 - 9 = 37
Final answer = 37
Array Representation: Use triplet format (row, column, value).
Linked List Representation: Nodes store row, column, and value with pointers.
Example: Graph adjacency matrices.
Addition: Traverse both lists in order; add values with the same row & column.
Multiplication: Multiply matching row/column pairs and sum partial products.
Example: In adding two sparse matrices, only non-zero elements are processed, improving efficiency.
Inorder (LNR): Left → Node → Right
Example: Gives sorted order in BST.
Preorder (NLR): Node → Left → Right
Example: Used to create a copy of a tree.
Postorder (LRN): Left → Right → Node
Example: Deletes tree nodes safely.
LL Rotation: Fixes left-heavy imbalance.
RR Rotation: Fixes right-heavy imbalance.
LR & RL Rotations: Double rotations for complex cases.
Example: Inserting 30, 20, 10 causes LL imbalance → rotate right.
Deletion: Remove root, replace with last element, percolate down.
Example: Priority queues use heaps for scheduling tasks.
Steps:
Divide array into halves recursively.
Sort each half.
Merge sorted halves.
Example: Sorting [8,3,5,2] → merge steps produce [2,3,5,8].
Time complexity: O(n log n), stable.
Bubble Sort: Repeatedly swaps adjacent elements; O(n²); simple but slow.
Selection Sort: Finds minimum each pass; O(n²); fewer swaps.
Insertion Sort: Inserts into sorted part; O(n²) but best-case O(n) for nearly sorted data.
Collision resolution:
Chaining: Linked lists at each index.
Open Addressing: Linear probing, quadratic probing, double hashing.
Example: Hash tables in dictionaries.
Example: Databases use B+ Trees for range queries.
Example: (5x² + 3x + 1) stored as nodes and supports addition/multiplication.
(b) Union-by-rank & Path compression
(c) Applications
MAKE-SET(x): Creates a new set with element x as its own parent.
FIND(x): Returns the representative (root) of the set containing x.
UNION(x, y): Merges two sets by linking their roots.
These operations efficiently organize components in dynamic connectivity problems.
Union-by-Rank: Always attaches the shorter tree under the taller one to avoid increasing height.
Path Compression: During FIND, nodes along the path point directly to the root, flattening the structure.
Combined, they make operations almost O(1) amortized.
Example: Sets {1,2}, {3,4} can be merged efficiently while keeping shallow trees.
(b) BFS & DFS algorithms
(c) Applications
Adjacency Matrix: 2D array storing edges; easy to use but space O(n²).
Adjacency List: Stores neighbors using linked lists; efficient for sparse graphs.
Example: Social networks prefer adjacency lists.
DFS: Uses stack/recursion, explores deeply before backtracking.
Example Traversal: For graph 1–2–3–4, BFS gives 1,2,3,4; DFS gives 1,2,3,4 but order may vary depending on branching.
BFS: Shortest path in unweighted graphs, web crawling, friend suggestions.
DFS: Cycle detection, topological sorting, maze solving.
(b) Dijkstra’s Algorithm
(c) MST vs Shortest Path
Example: Works like expanding a connected region outward.
Kruskal’s Algorithm: Sorts all edges and keeps adding the smallest edge that doesn’t create a cycle, using disjoint sets to check cycles.
Example: Useful for sparse graphs.
Example: Finding the fastest route in Google Maps.
MST connects all vertices with minimum total weight but does not consider paths between specific nodes.
The shortest path gives minimum distance between two nodes but doesn’t need to include all nodes.
Q. Explain Expressions and Recursion
Q. What is a Queue and Queue ADT
Q. What is Sparse Matrix Representation and its Arithmetic
Q. What is Polynomial Representation and its Arithmetic
Q. What is a Tree and Binary Tree
Q. What are Binary Tree Traversals and Expression Trees
Q. What is a Binary Search Tree and AVL Tree
Q. What are Heaps, Priority Queues, and B-Trees
Q. Explain Sorting Concepts and Types
Q. Explain Selection, Insertion, and Exchange Sorts
- Selection sort selects minimum element repeatedly.
- Insertion sort inserts elements into correct position.
- Exchange sorts like bubble and quicksort swap elements.
Q. Explain Merge Sort and External Sorting
Q. What are Searching Techniques and Hashing
Q. Disjoint Sets and Union-Find Algorithm
Q. What is a Graph and Graph Representation
Q. Explain Graph Traversals (BFS and DFS)
Answer: BFS explores graph level by level using queue, while DFS explores depth-wise using stack or recursion. Traversals are fundamental for graph algorithms.
Example: BFS used in shortest path finding.
Q. Minimum Spanning Tree and Shortest Path Algorithms
Q. Define an Abstract Data Type (ADT) with an example.
An Abstract Data Type (ADT) is a logical description of how data is organized and what operations can be performed on it, without specifying how it is implemented. It separates what the data structure does from how it is achieved. ADTs define operations, input-output behavior, and constraints. For example, a Stack ADT supports operations like push, pop, peek, and isEmpty. It does not specify whether the stack is implemented using an array or linked list. The user only interacts with the defined operations. Thus, ADTs promote modularity and abstraction in programming by hiding implementation details while providing clear functionality.
Q. What is the difference between an array and a linked list?
An array is a contiguous block of memory where all elements are stored next to each other. It provides constant-time access (O(1)) using indices but has a fixed size, making insertions and deletions expensive. A linked list consists of nodes where each node stores data and a pointer to the next node. Memory is allocated dynamically, allowing flexible size adjustments. However, accessing an element requires traversal from the beginning (O(n)). Arrays are suitable for indexing and static data, while linked lists are preferred for frequent insertions and deletions. For example, adding an element at the beginning is O(1) in a linked list but O(n) in an array.
Q. Explain postfix expression with an example.
A postfix expression, also known as Reverse Polish Notation (RPN), is a mathematical expression where operators appear after their operands. It eliminates the need for parentheses and follows left-to-right evaluation using stacks. In postfix form, an expression like A + B × C is written as A B C × +. During evaluation, operands are pushed onto a stack, and when an operator is encountered, the required number of operands are popped, the operation is performed, and the result is pushed back. For example, evaluating 6 2 3 + ×: first compute (2 + 3 = 5), then (6 × 5 = 30). Postfix expressions are widely used in compilers.
Q. Define recursion. Where is it used?
Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem. Each recursive call reduces the problem size until it reaches a base case, which stops further recursion. Recursion is commonly used in problems that naturally break into subproblems. Examples include tree traversal, factorial calculation, Fibonacci series, Tower of Hanoi, and divide-and-conquer algorithms like merge sort and quicksort. In Data Structures, recursion is especially useful for navigating hierarchical structures like binary trees. For instance, inorder traversal of a binary tree uses recursion to visit left subtree, root, and then right subtree.
Q. What is sparse matrix representation?
A sparse matrix is a matrix in which most elements are zero. Storing all elements wastes memory, so special representations are used. Sparse matrix representation stores only the non-zero elements along with their row and column indices. Two popular methods are:
Triplet array representation, where each entry stores (row, column, value).
Linked-list representation, where nodes store non-zero values with pointers to next elements.
For example, a 5×5 matrix with only 3 non-zero values can be represented efficiently using just three triplets. Sparse matrices are used in graph algorithms, scientific computing, and machine learning where matrices are mostly empty.
Q. Define binary tree traversal. Name the three traversal techniques.
Binary tree traversal is the process of visiting every node in a binary tree in a specific order. Since each node has at most two children, different traversal techniques help process nodes systematically. The three primary depth-first traversal methods are:
Inorder (Left–Root–Right)
Preorder (Root–Left–Right)
Postorder (Left–Right–Root)
For example, in an expression tree, inorder traversal generates the original infix expression, preorder gives prefix notation, and postorder gives postfix notation. Traversals are essential for operations such as searching, expression evaluation, and tree manipulation.
Q. What is the difference between selection sort and insertion sort?
Selection sort repeatedly finds the minimum element from the unsorted portion and places it at the beginning. It makes a constant number of swaps but many comparisons, resulting in O(n²) time. Insertion sort builds the final sorted array one element at a time by shifting elements and inserting items in their proper place. It performs well when the list is already partially sorted. For example, sorting [3,1,2]: insertion sort will shift 3 and 2, but selection sort will find the minimum first. Insertion sort is faster for small or nearly sorted data, while selection sort is simpler but less efficient.
Q. Define hashing. What is collision?
Hashing is a technique used to store and retrieve data efficiently using a hash function that maps a key to an index in a hash table. Ideally, each key maps to a unique index. However, when two different keys generate the same hash value, a collision occurs. For example, if key1 and key2 both map to index 5, it is a collision. Collision resolution strategies such as separate chaining, open addressing, or linear probing are used to handle such situations. Hashing provides average O(1) time for search, insertion, and deletion.
Q. What is a minimum spanning tree?
A Minimum Spanning Tree (MST) of a connected, undirected, weighted graph is a subset of edges that connects all vertices with the minimum possible total edge weight and without forming cycles. MST ensures that the graph remains fully connected but uses the least cost. Popular algorithms to find MST include Kruskal’s algorithm and Prim’s algorithm. For example, in a network of cities connected with costs, MST helps design the lowest-cost network of roads or communication links. MST is widely used in networking, clustering, and circuit design.
Q. Define BFS and DFS in graphs.
Breadth-First Search (BFS) explores a graph level by level using a queue. It visits all neighbors of a node first before moving to deeper levels. BFS is used for shortest path in unweighted graphs and level-order traversal.
Depth-First Search (DFS) explores deeply using a stack or recursion, visiting one branch entirely before backtracking. DFS is used in topological sorting, cycle detection, and connected components.
For example, in a social network graph, BFS helps find the shortest connection between two users, while DFS helps detect communities or cycles.
Q. Explain the concept of Abstract Data Types (ADT). Describe list ADT with examples of operations.
An Abstract Data Type (ADT) defines a mathematical model for a data structure along with the operations that can be performed on it, without specifying how the operations are implemented. ADTs promote modularity and allow programmers to focus on what an operation does instead of how it is done.
The List ADT represents an ordered collection of elements that may be accessed by position. It supports operations like insert(position, element), delete(position), get(position), search(element), and traverse().
For example, inserting 20 at position 3 shifts elements to the right in an array, whereas a linked list adjusts pointers. The operations remain the same even though implementations differ, which is the key advantage of ADTs.
Q. Explain the representation of sparse matrices using arrays. Write an algorithm for sparse matrix addition.
A sparse matrix contains mostly zero values. To save memory, only non-zero elements are stored.
Array (Triplet) Representation: Each non-zero element is stored as a triplet (row, column, value). For example, a 4×4 matrix with 4 non-zero values will be stored in an array of size 5 (including header).
Sparse matrix addition uses two triplet arrays representing matrices A and B.
Algorithm:
Initialize result matrix C.
Compare positions of A[i] and B[j].
If same (same row & column), add values.
If position in A < B, copy A element; else copy B element.
Continue until both lists are complete.
Store header as (rows, columns, non-zero-count).
Q. Explain binary search trees (BST). How are insertion and deletion performed in BST?
A Binary Search Tree (BST) is a binary tree in which the left child of a node contains values less than the node, while the right child contains values greater than it. This ordering allows fast searching, insertion, and deletion.
Insertion:
Start at the root and compare the new value with the current node. If smaller, go to the left subtree; if larger, go to the right. Insert at the first NULL position.
Deletion: Three cases exist:
Node is a leaf: delete directly.
Node has one child: replace node with its child.
Node has two children: replace node with its inorder successor (minimum in right subtree), then delete that successor.
BSTs ensure O(log n) operations on average.
Q. Explain quicksort algorithm. Discuss its worst-case and average-case complexities.
Quicksort is a divide-and-conquer sorting algorithm. It selects a pivot element and partitions the array so elements smaller than pivot go left and larger go right. The subarrays are then recursively sorted.
Process:
Choose pivot (e.g., last element).
Partition array around pivot.
Recursively sort left and right partitions.
Complexity:
Average case: O(n log n), because partitioning usually divides data into balanced halves.
Worst case: O(n²), occurs when array is already sorted or pivot repeatedly becomes smallest/largest.
Despite this, quicksort is preferred due to small constant factors, in-place operation, and excellent practical performance.
Q. Explain the hashing method with separate chaining. Give an example of collision resolution.
Hashing maps keys to indices in a table using a hash function. When two keys map to the same index, a collision occurs.
Separate chaining resolves collisions by storing multiple values at the same index using a linked list.
For example, if table size = 5 and the hash function is h(k) = k % 5, keys 12 and 22 both hash to index 2. Instead of overwriting, the index stores a linked list: → 12 → 22.
Advantages: easy to implement, no need to rehash entire table.
Insertion: compute hash index, append element to linked list.
Search: traverse list at index.
Deletion: remove node from linked list.
Separate chaining effectively handles multiple collisions with minimal structural issues.
Q. Explain circular linked lists and their applications.
A circular linked list is a variation of the linked list in which the last node does not point to NULL but instead points back to the first node, forming a circular structure. In a singly circular linked list, each node has one pointer connecting to the next node, and in a doubly circular linked list, nodes contain both previous and next pointers, still forming a cycle.
The major advantage is that the list can be traversed from any node without explicitly knowing the head, as all nodes are connected circularly. Operations like insertion and deletion become more efficient in certain cases because there is no need to handle NULL references.
Applications: Circular linked lists are commonly used in real-world scenarios requiring continuous looping. Examples include CPU scheduling algorithms like Round Robin, where processes are executed in cycles; implementation of buffer management in operating systems; managing playlist rotations, where songs play repeatedly; and simulation problems dealing with repeating structures, such as the Josephus problem.
Because of their cyclic nature, circular linked lists efficiently support repetitive access patterns and allow fast insertion at both beginning and end compared to linear linked lists.
Q. Write algorithms for insertion at beginning and deletion at end in a circular linked list.
Algorithm: Insert at Beginning (Singly Circular List)
Create a new node N.
Set N->data = value.
If list is empty:
Set N->next = N and update head = N.
Else:
Traverse to last node L (L->next = head).
Set N->next = head.
Set L->next = N.
Update head = N.
Algorithm: Delete Last Node
If list is empty → return.
If only one node: delete and set head = NULL.
Traverse to second-last node (prev) and last node (last).
Set prev->next = head.
Free last.
Q. What is a heap? Explain max heap and min heap with insertion and deletion algorithms.
A heap is a complete binary tree used to implement priority queues. It satisfies the heap property: the value of every node is greater (max heap) or smaller (min heap) than its children. Heaps are commonly represented using arrays for efficient navigation through indices.
Max Heap
Insert new element at the end of the array.
Perform up-heapify (bubble up): compare with parent, swap if greater, continue.
Deletion (Delete Max):Replace root with last element.
Remove last element.
Perform down-heapify: swap root with larger of its children until heap property holds.
Min Heap
Here, the smallest element is at the root.
Insertion and deletion algorithms are identical except comparisons use the smaller value.
Heaps are used in priority queues, Dijkstra’s shortest path, heap sort, and scheduling.
Q. Explain priority queues and their applications.
A priority queue is an abstract data type where each element is assigned a priority, and deletion always removes the element with the highest (or lowest) priority. Unlike normal queues that follow FIFO order, priority queues follow a priority-based removal mechanism.
They are usually implemented using heaps because heap operations provide O(log n) insertion and deletion.
Applications:
Operating systems: CPU process scheduling, interrupt handling.
Networking: Managing packets where high-priority packets are transmitted first.
Artificial intelligence: Algorithms like A* use priority queues for exploring optimal paths.
Simulation systems: Events scheduled by time or importance.
Data compression: Huffman coding uses priority queues to build optimal prefix codes.
Priority queues efficiently manage tasks that must be accessed in an order other than arrival time.
Q. Explain union–find algorithm for disjoint sets. Discuss union by rank and path compression.
The union–find or disjoint-set data structure manages a collection of non-overlapping sets and supports two main operations:
Find(x): Determines the representative (parent) of the set containing x.
Union(x, y): Merges the sets containing x and y.
Disjoint sets are implemented using trees, where each set is a tree with a root as representative.
Union by Rank
To avoid tall trees, each tree is assigned a rank (approximate height). When unioning two sets, the tree with smaller rank is attached under the tree with larger rank. If ranks are equal, one becomes parent and its rank increases by one. This helps keep operations near O(α(n)), almost constant time.
Path Compression
During Find, every node on the path to the root is directly linked to the root, flattening the structure. This drastically speeds up future Find operations.
Union by rank + path compression is one of the most efficient data structures in computer science.
Q. Explain Dijkstra’s shortest path algorithm with an example.
Dijkstra’s algorithm finds the shortest path from a single source to all other vertices in a weighted graph with non-negative weights.
Steps:
Initialize distance of source = 0, others = ∞.
Use a priority queue to select the vertex with the minimum distance.
For each neighbor, update distance if a shorter path is found.
Mark the vertex as processed.
Repeat until all vertices are processed.
Example
Consider source A with edges:
A–B = 2, A–C = 4, B–C = 1, B–D = 7, C–D = 3
The algorithm updates distances as:
From A: B=2, C=4
Pick B: update C=3 (2+1), D=9
Pick C: update D=6 (3+3)
Final distances: A=0, B=2, C=3, D=6.
No comments:
Post a Comment