DATA STRUCTURE AND ALGORITHMS LABORATORY(DSAL)

SAMPLE ORAL QUESTIONS BY SUJAY

Unit-1 (Group-A)
1. Define the Following Terms:
Hashing:
Hashing is a technique used to map data (keys) to a fixed-size table (called a
hash table) using a hash function. It allows fast data access in constant time
O(1) on average.
Hashing Function:
A hash function takes a key and computes an index in the hash table. It should
distribute keys uniformly and minimize collisions.
Example: h(key) = key % table_size
Hash Table:
A data structure that stores key-value pairs. The position of a key is determined
by applying a hash function to it. Used in dictionaries, symbol tables, etc.
Collision:
A collision occurs when two different keys produce the same hash value
(index). This leads to multiple keys trying to occupy the same slot.
Rehashing:
When the hash table becomes full or overloaded, a new larger table is created
and all existing keys are hashed again using a new hash function or table size.
Perfect Hash Function:
A hash function that does not produce any collisions for a given dataset. It
maps all keys uniquely to table indices.
Hash Key:
The key used in the hashing process. It is the actual data item you want to store
or search, like an ID, string, or number.
2. What Are the Issues in Hashing?
• Collisions: Multiple keys hash to the same index.
• Clustering: Collisions can lead to groups of filled slots (primary and
secondary clustering).
• Load Factor: High load factor (number of elements/table size) increases
collisions.
• Poor Hash Function: A non-uniform hash function can lead to uneven
key distribution.
• Limited Table Size: Hash table can become full, requiring rehashing.
• Deletion Issues: Deleting keys without careful handling can break search
chains.

3. Types of Hashing Functions

• Division Method:
h(key) = key % table_size
Simple and widely used. Table size should be prime.
• Multiplication Method:
h(key) = floor(table_size * (key * A % 1))
More consistent distribution. A is a constant (e.g., 0.618033...).
• Mid-square Method:
Square the key and extract the middle portion as the hash.
• Folding Method:
Break the key into parts, add the parts, and take mod.
• Digit Analysis:
Use selected digits from the key (rarely used due to bias).

4. Types of Hashing (Collision Handling Techniques)

Open Hashing (Separate Chaining):
• Store multiple values in a linked list at the same index.
 • No issue with table size overflow.
• Easy to implement but more memory overhead.
Closed Hashing (Open Addressing):
All elements are stored directly in the hash table.
• Linear Probing:
If collision, try next slot sequentially (h(key) + i).
• Quadratic Probing:
Use squared offsets (h(key) + i²).
• Double Hashing:
Use a second hash function to calculate step size.

5. Difference Between Hashing with Replacement and Without

Replacement
Hashing without
Feature Hashing with Replacement
Replacement

Replaces existing value at Does not replace; stores

Definition hashed index if it has lower new key in next available
priority or can be displaced. slot using probing.

Collision May shift existing element to Keeps existing element and

Handling next slot probes forward

Generally faster if replacement May take longer due to

Search Time
leads to better key placement clustering

Implementation Slightly more complex Simpler implementation

If key 5 hashes to a slot with

If key 5 finds key 10 in its
key 10, and 5 has higher
Example slot, it goes to next available
priority, 10 is moved and 5
slot
replaces it
Unit-2 (Group-B)

1. Define Various Terminologies of Trees

• Root: The topmost node of a tree.
• Node: Each data element in a tree.
• Edge: The connection between two nodes.
• Leaf (External Node): A node with no children.
• Internal Node: A node with at least one child.
• Parent: A node that has child nodes.
• Child: A node that descends from another node.
• Siblings: Nodes that share the same parent.
• Level: The depth of a node from the root (root is at level 0).
• Height: Longest path from the root to a leaf node.
• Depth: Number of edges from the root to that node.
• Degree: Number of children a node has.
• Subtree: A portion of a tree structure that forms a tree on its own.

2. What Are the Properties of a Binary Tree?

• Each node has at most two children: left and right.
• The maximum number of nodes at level l is 2^l.
• A binary tree of height h has at most 2^(h+1) - 1 nodes.
• In a binary tree:
o Number of leaf nodes = number of nodes with two children + 1.
o Full Binary Tree: Every node has 0 or 2 children.
o Complete Binary Tree: All levels are completely filled except
possibly the last, and nodes are left-aligned.
3. What Are the Different Tree Traversal Operations?
Tree traversal is the process of visiting each node exactly once in a specific
order. There are two main types:
Depth-First Traversals:
• Inorder (LNR): Left → Node → Right
• Preorder (NLR): Node → Left → Right
• Postorder (LRN): Left → Right → Node
Breadth-First Traversal:
• Level Order: Visit nodes level by level from top to bottom using a queue.

4. Define Binary Search Tree (BST) and Its Operations

A Binary Search Tree (BST) is a special binary tree where:
• All left subtree nodes < root
• All right subtree nodes > root
• This property is true recursively for all subtrees.
Operations on BST:
• Insertion: Recursively place the node in left/right subtree based on
value.
• Deletion: Three cases:
o Node is a leaf
o Node has one child
o Node has two children (replace with inorder successor or
predecessor)
• Search: Compare key with node, go left if smaller, right if larger.
• Traversal: Use inorder to get sorted order of elements.
5. Define Threaded BST and Its Operations
A Threaded Binary Search Tree is a binary tree where NULL pointers are
replaced with "threads" to point to the inorder predecessor or successor to
enable efficient in-order traversal.
Types:
• Single Threaded: Only one of left or right NULLs is replaced with a
thread.
• Double Threaded: Both left and right NULLs are replaced with threads.
Operations:
• Insertion: Similar to BST, while maintaining thread links.
• Deletion: Update threads after removing a node.
• Traversal: Inorder traversal without using recursion or stack.

6. Algorithms for Inorder, Preorder, and Postorder Traversal

Let’s assume Node structure has left, right, and data.
Inorder Traversal (LNR):
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
Preorder Traversal (NLR):
void preorder(Node* root) {
if (root != NULL) {
cout << root->data << " ";
 preorder(root->left);
preorder(root->right);
}
}
Postorder Traversal (LRN):
void postorder(Node* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
}

Unit-3 (Group-C)

1. Define Various Terminology of Graph

• Graph (G): A graph is a collection of vertices (nodes) and edges
(connections). It is represented as G = (V, E).
• Vertex (Node): A fundamental part of a graph representing a point.
• Edge: A connection between two vertices.
• Adjacent Vertices: Two vertices connected directly by an edge.
• Degree: Number of edges incident on a vertex.
o Indegree: Number of edges coming into a vertex.
o Outdegree: Number of edges going out from a vertex.
• Path: A sequence of vertices connected by edges.
• Cycle: A path that starts and ends at the same vertex without repeating
edges or vertices.
 • Connected Graph: A graph in which there is a path between every pair of
vertices.
• Directed Graph (Digraph): A graph in which edges have a direction.
• Undirected Graph: A graph in which edges have no direction.
• Weighted Graph: A graph where edges have weights (cost, distance,
etc.).
• Loop: An edge that connects a vertex to itself.

2. Define Adjacency Matrix and List with Example

Adjacency Matrix:
• A 2D array used to represent a graph.
• If graph[i][j] = 1, there is an edge from vertex i to j; 0 otherwise.
• For weighted graphs, it stores weight instead of 1.
Example (Undirected graph with 3 vertices):
css
CopyEdit
A --- B
\ /
C

Vertices: A=0, B=1, C=2

Adjacency Matrix:
012
0 [0 1 1]
1 [1 0 1]
2 [1 1 0]
Adjacency List:
• Uses an array of lists.
• Each vertex stores a list of adjacent vertices.
Example:
makefile
CopyEdit
0: 1 -> 2
1: 0 -> 2
2: 0 -> 1

3. What is Minimum Spanning Tree and Its Types?

A Minimum Spanning Tree (MST) is a subset of edges from a connected,
undirected, weighted graph that:
• Connects all the vertices
• Has no cycles
• Has the minimum possible total edge weight
Types of MST Algorithms:
• Prim’s Algorithm: Starts from a node and grows the MST by adding the
smallest weight edge.
• Kruskal’s Algorithm: Adds the smallest weight edge that does not form a
cycle, using edge sorting.

4. Algorithms/Steps for Prim’s and Kruskal’s Algorithms

Prim’s Algorithm (Greedy)
• Start with any node (say, node A).
• Initialize key values for all vertices as ∞, and for the start node as 0.
 • Use a priority queue to pick the node with the smallest key value not yet
in the MST.
• Update the key values of its adjacent vertices.
• Repeat until all nodes are included.
Time Complexity:
• O(V²) using simple arrays
• O(E + V log V) using min heap (priority queue)
Kruskal’s Algorithm (Greedy)
• Sort all edges by weight.
• Initialize disjoint sets for all vertices.
• For each edge in sorted order:
o If it connects two different sets (no cycle), add it to MST.
o Merge the sets using Union-Find.
• Repeat until MST has V-1 edges.
Time Complexity:
• O(E log E) due to edge sorting
• O(E α(V)) for Union-Find operations

5. State Concept of Dijkstra’s Single Source Shortest Path

Dijkstra’s Algorithm finds the shortest path from a single source node to all
other nodes in a weighted, directed or undirected graph, assuming non-
negative weights.
Steps:
• Initialize distance to all nodes as ∞, source as 0.
• Use a priority queue to pick the node with the smallest distance.
• For each adjacent node, update its distance if a shorter path is found.
• Repeat until all vertices are processed.
Time Complexity:
• O(V²) with arrays
• O(E + V log V) with min-heap

6. What Are the Ways to Represent a Graph?

• Adjacency Matrix: 2D matrix storing edge presence or weights.
o Good for dense graphs.
o Space complexity: O(V²)
• Adjacency List: Array of lists storing neighbors for each vertex.
o Good for sparse graphs.
o Space complexity: O(V + E)
• Edge List: List of all edges.
o Useful for Kruskal’s algorithm.

7. What Do You Mean by Greedy Approach?

The Greedy Approach is an algorithmic paradigm where the best local optimal
choice is made at each step, hoping it leads to a global optimum.
It does not backtrack and works for problems like:
• Minimum Spanning Tree (Prim’s, Kruskal’s)
• Dijkstra’s Algorithm
• Huffman Encoding
• Fractional Knapsack
Key Feature: Make the best possible choice at each step.

Unit-4 (Group-D)
1. Difference between Static and Dynamic Tree Table
Feature Static Tree Table Dynamic Tree Table

A tree where the structure and

A tree that allows modification
Definition data remain fixed once
like insertion and deletion.
created.

Update Fully supports insertion,

Not allowed or very limited.
Operations deletion, and updates.

Flexibility Low High

Static Decision Trees, Static

Examples AVL Tree, Red-Black Tree
OBST (Optimal BST)

Used in scenarios where data is Used in dynamic applications

Use Case
not expected to change. like databases, file systems.

2. What is Weight Balance Tree and Height Balance Tree with

Example?
Weight Balance Tree
• A tree is weight-balanced when the number of nodes (weight) in the left
and right subtrees are balanced.
• Used in Weight Balanced Binary Search Trees (WBBST).
• Balance is maintained by ensuring the ratio of weights is within a defined
limit.
Example: If left subtree has 3 nodes and right has 4, the tree is considered
balanced.
Height Balance Tree
• A tree is height-balanced if for any node, the height difference between
left and right subtrees is at most 1.
• AVL Tree is a classic example of a height-balanced tree.
Example:
markdown
CopyEdit
30
/ \
20 40
/
10
Height difference at root is 1 → Height balanced.

3. Long Form of OBST, AVL, RBT, KD and AA Tree

Abbreviation Full Form

OBST Optimal Binary Search Tree

AVL Adelson-Velsky and Landis Tree

RBT Red-Black Tree

KD Tree k-Dimensional Tree

AA Tree Arne Andersson Tree

4. What are the Rotations for AVL Tree with Example?

AVL Tree uses rotations to maintain height balance after insertion/deletion.
Types of Rotations:
• LL (Left-Left Rotation): When node is inserted into the left subtree of the
left child.
o Fix with single right rotation.
• RR (Right-Right Rotation): When node is inserted into the right subtree
of the right child.
 o Fix with single left rotation.
• LR (Left-Right Rotation): Node inserted into right subtree of left child.
o Fix with left rotation on left child, then right rotation on root.
• RL (Right-Left Rotation): Node inserted into left subtree of right child.
o Fix with right rotation on right child, then left rotation on root.
Example (RR case):
Insert: 10 → 20 → 30
Initial Tree:
markdown
CopyEdit
10
\
20
\
30
RR Imbalance → Apply Left Rotation →
Final Tree:
markdown
CopyEdit
20
/ \
10 30

5. What Do You Mean by Dynamic Programming Approach?

Dynamic Programming (DP) is a method used for solving complex problems by
breaking them into smaller subproblems, solving each once, and storing their
results to avoid redundant computation.
Characteristics:
• Overlapping subproblems
• Optimal substructure
DP Approaches:
• Top-Down (Memoization): Recursive + caching
• Bottom-Up (Tabulation): Iterative + table
Examples:
• Fibonacci series
• Knapsack problem
• Matrix Chain Multiplication
• Longest Common Subsequence (LCS)

Unit-5 (Group-E)

1. What is a Stack?
A stack is a linear data structure that follows the Last In First Out (LIFO)
principle, meaning the last element inserted is the first to be removed. Think of
it like a stack of plates: you can only take the top plate.

2. What are the Primary Operations on a Stack?

• Push(x): Insert element x at the top of the stack.
• Pop(): Remove the element from the top.
• Peek() / Top(): View the topmost element without removing it.
• isEmpty(): Checks if the stack is empty.
• isFull() (for fixed size stacks): Checks if the stack has reached its capacity.
3. Define Stack Overflow and Underflow
• Stack Overflow: Occurs when trying to push an element onto a full stack.
• Stack Underflow: Occurs when trying to pop an element from an empty
stack.

4. Applications of Stack
• Function call/recursion handling
• Expression evaluation (Postfix, Prefix)
• Expression conversion (Infix to Postfix)
• Undo/Redo operations
• Syntax parsing in compilers
• Backtracking algorithms (like maze or pathfinding)
• Parentheses matching

5. How to Implement a Stack?

• Using Array:
o Use an array and a top variable to track the topmost element.
• Using Linked List:
o Use nodes where insertion and deletion occur at the head.

6. What is the Time Complexity of Push/Pop?

Both Push and Pop operations take O(1) time (constant time), whether using
array or linked list implementation.

7. Difference Between Array and Linked List Stack

Feature Array Stack Linked List Stack

Size Fixed (unless resized) Dynamic (grows as needed)

Overflow Possible No overflow

Underflow Possible Possible

Memory May waste memory Efficient use of memory

8. How Does Stack Help in Recursion?

Stacks store function call frames during recursive calls. Each recursive call
pushes its state onto the stack. When a function finishes, it pops off, resuming
the previous state—thus enabling backtracking and call tracing.

9. What is the Role of Stack in Expression Conversion?

Stack is used to:
• Convert infix expressions to postfix or prefix.
• Maintain operator precedence and associativity.
• Store operators until they're needed based on the precedence rules.

10. What is Postfix Evaluation Using Stack?

In postfix (e.g., 23+), operands come first, then the operator. Stack is used to:
• Push operands onto the stack.
• On encountering an operator, pop two operands, apply the operation,
and push the result back.
Example: Postfix: 23+
Steps: Push 2 → Push 3 → Encounter + → Pop 2 and 3 → Compute 2+3=5 →
Push 5

11. How to Check for Balanced Parentheses?

Use a stack to:
• Push opening brackets: (, [, {
• On closing bracket: check if it matches the top of the stack.
• If mismatched or stack not empty at end → Not balanced.

12. What is Dynamic Stack?

A dynamic stack is a stack whose size grows automatically when needed (e.g.,
using dynamic memory or a resizable array like std::vector in C++).

13. Can You Implement a Stack Using Queues?

Yes, you can implement a stack using two queues:
• Push Efficient Method: Push into queue, rearrange elements to make
front the top.
• Pop Efficient Method: Push normally, and use two queues to pop last
inserted.

14. What is Multiple Stack Implementation?

It refers to managing more than one stack in a single array. Used to optimize
memory:
• Fixed division: Divide array equally for each stack.
• Dynamic division: Adjust boundaries as stacks grow/shrink.

15. Explain Peek Operation

Peek() (also called Top()) returns the element at the top of the stack without
removing it. Used to inspect the last inserted item.
Unit-6 (Group-F)

Q1. What is a Queue?

A queue is a linear data structure that follows the First In First Out (FIFO)
principle. The first element added is the first to be removed. It’s like a line of
people: the one who comes first is served first.

Q2. List Main Queue Operations

• Enqueue(x): Add element x at the rear.
• Dequeue(): Remove element from the front.
• Front(): Access the front element.
• Rear(): Access the rear element.
• isEmpty(): Check if queue is empty.
• isFull(): (for static queues) Check if queue is full.

Q3. What is a Circular Queue?

A circular queue connects the last position back to the first position to make a
circle. It helps in utilizing space efficiently in a fixed-size array queue.

Q4. What are Front and Rear Pointers?

• Front pointer: Points to the element to be dequeued next.
• Rear pointer: Points to the last inserted element (where the next
enqueue will occur).

Q5. Explain Queue Overflow and Underflow

• Overflow: Trying to enqueue into a full queue.
• Underflow: Trying to dequeue from an empty queue.
Q6. What is Dequeue (Double-Ended Queue)?
A deque allows insertion and deletion from both ends (front and rear). Types:
• Input-restricted deque: Deletion from both ends, insertion only at one.
• Output-restricted deque: Insertion from both ends, deletion only from
one.

Q7. What is Priority Queue?

A priority queue is a queue where each element has a priority. The element
with the highest priority is dequeued first. If priorities are equal, FIFO order is
used.

Q8. Applications of Queues

• Job scheduling
• CPU scheduling (Round Robin)
• Print spooling
• Call center systems
• BFS traversal in graphs
• Caching and memory management

Q9. Difference Between Linear and Circular Queue

Feature Linear Queue Circular Queue

Memory Use Wastes space Efficient memory usage

Wrap Around Not possible Rear connects to front

Full Condition Rear == size - 1 (rear + 1) % size == front

Implementation Simple Slightly complex

Q10. How to Avoid Space Wastage in Linear Queue?
Use a circular queue, or shift elements forward after every dequeue
(inefficient). Circular queues reuse the space automatically.

Q11. Can Queue Be Implemented Using Stacks?

Yes. Using two stacks:
• Enqueue Efficient Method: Push to one stack, and reverse when
dequeuing.
• Dequeue Efficient Method: Reverse when enqueuing, and pop directly
for dequeuing.

Q12. What is the Time Complexity of Enqueue/Dequeue?

• Both Enqueue and Dequeue are typically O(1) operations for linked list
and array implementations.

Q13. What is a Real-World Example of Queue?

• Queue at a ticket counter
• Task scheduling in CPU
• Call waiting system

Q14. What is the Difference Between Queue and Stack?

Feature Stack (LIFO) Queue (FIFO)

Order Last in, first out First in, first out

Access Ends One end (top) Both ends (front, rear)

Operations Push, Pop Enqueue, Dequeue

Feature Stack (LIFO) Queue (FIFO)

Example Function call stack CPU job queue

Q15. What is Circular Queue’s Advantage?

Efficiently utilizes all available space in a fixed-size array. No need to shift
elements, unlike in a linear queue.

Q16. What is Static vs Dynamic Queue?

Type Static Queue Dynamic Queue

Size Fixed (array) Grows/shrinks (linked list)

Memory May waste unused space Memory efficient

Q17. Explain Insertion and Deletion in Queue Using Linked List

• Insertion (Enqueue): Add node at the end (rear).
• Deletion (Dequeue): Remove node from the front. Both are O(1)
operations when rear and front pointers are maintained.

Q18. What are Limitations of Queue Using Array?

• Fixed size: Cannot grow.
• Wasted space: After several dequeues, unused space at the front unless
circular queue is used.

Q19. What is Rear and Front Condition for Full Circular Queue?
A circular queue is full when:
(rear + 1) % size == front
Q20. What are Types of Queues?
• Simple (Linear) Queue
• Circular Queue
• Double-Ended Queue (Deque)
• Priority Queue