MAKAUT 3rd Semester (CSE) - Data Structures and Algorithms
Important Questions and Answers
Question: Explain the process of inserting an element into a Binary Search Tree (BST).
Answer:
Algorithm:
1. Start at the root node.
2. Compare the value to be inserted with the value of the current node.
3. If the value is less than the current node's value, move to the left child; if greater, move to the
right child.
4. Repeat step 3 until reaching a null reference, indicating the position for insertion.
5. Insert the new node at the null position.
Code:
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def insert(root, key):
if root is None:
return Node(key)
else:
if key < root.val:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
# Example usage:
r = Node(50)
r = insert(r, 30)
r = insert(r, 20)
r = insert(r, 40)
r = insert(r, 70)
r = insert(r, 60)
r = insert(r, 80)
Question: Describe the Quick Sort algorithm and provide a code implementation.
Answer:
Algorithm:
1. Choose a 'pivot' element from the array.
2. Partition the array into two sub-arrays: elements less than the pivot and elements greater than the
pivot.
3. Recursively apply the above steps to the sub-arrays.
4. Combine the sub-arrays and pivot into a sorted array.
Code:
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# Example usage:
unsorted_array = [3, 6, 8, 10, 1, 2, 1]
sorted_array = quick_sort(unsorted_array)
print(sorted_array)
Question: What is a Hash Table, and how does it handle collisions? Illustrate with an
example.
Answer:
Definition:
A hash table is a data structure that maps keys to values for efficient lookup. It uses a hash function
to compute an index into an array of buckets, from which the desired value can be found.
Collision Handling:
1. Chaining: Each bucket contains a linked list of entries that map to the same index.
2. Open Addressing: All entry records are stored in the array itself. When a collision occurs, the
algorithm probes the array to find the next empty slot.
Code:
class HashTable:
def __init__(self):
self.size = 10
self.table = [[] for _ in range(self.size)]
def _hash(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash(key)
self.table[index].append((key, value))
def search(self, key):
index = self._hash(key)
for pair in self.table[index]:
if pair[0] == key:
return pair[1]
return None
# Example usage:
ht = HashTable()
ht.insert("name", "Alice")
ht.insert("age", 25)
ht.insert("city", "New York")
print(ht.search("name")) # Output: Alice
print(ht.search("age")) # Output: 25
