Algorithms Algorithms 4 ā Questions and Answers
Question 1: What is the time complexity of inserting an element into a balanced BST (e.g., AVL tree)?
- O(1)
- O(log n) (Correct answer)
- O(n)
- O(n log n)
Correct answer: O(log n)
A balanced BST maintains height O(log n), so insertion requires at most O(log n) comparisons.
Question 2: Which algorithm solves the single-source shortest path problem with negative edge weights (but no negative cycles)?
- Dijkstra's
- BFS
- DFS
- Bellman-Ford (Correct answer)
Correct answer: Bellman-Ford
Bellman-Ford handles negative edge weights by relaxing all edges V-1 times, unlike Dijkstra's which requires non-negative weights.
Question 3: What does 'P vs NP' refer to in computational complexity theory?
- Whether polynomial algorithms are faster than non-polynomial ones
- Whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time (Correct answer)
- Whether parallel computing solves NP problems faster
- Whether probabilistic algorithms are more efficient than deterministic ones
Correct answer: Whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time
P vs NP asks whether every problem verifiable in polynomial time (NP) can also be solved in polynomial time (P).
Question 4: Which traversal of a binary search tree produces elements in sorted order?
- Pre-order
- Post-order
- In-order (Correct answer)
- Level-order
Correct answer: In-order
In-order traversal visits left subtree, root, then right subtree, producing a sorted sequence in a BST.
Question 5: What is the key invariant maintained by Quick Sort's partition step?
- All elements to the left of pivot are smaller, all to the right are larger (Correct answer)
- The pivot is always the median element
- Elements are sorted in each half before recursion
- The pivot is placed at the array midpoint
Correct answer: All elements to the left of pivot are smaller, all to the right are larger
After partitioning, all elements less than the pivot are on its left and all greater are on its right.
Question 6: In the context of graph algorithms, what is a topological sort?
- Sorting graph vertices by degree
- A linear ordering of vertices such that for every directed edge (u,v), u comes before v (Correct answer)
- Finding the shortest path in a DAG
- Sorting edges by weight in a directed graph
Correct answer: A linear ordering of vertices such that for every directed edge (u,v), u comes before v
Topological sort produces a linear ordering where every directed edge points from earlier to later in the sequence.
Question 7: What is the time complexity of building a binary heap from an unsorted array of n elements?
- O(n log n)
- O(n) (Correct answer)
- O(log n)
- O(nĀ²)
Correct answer: O(n)
Using the 'heapify' bottom-up approach, a heap can be built in O(n) time due to the mathematical series involved.
Algorithms Algorithms 4
What is the time complexity of inserting an element into a balanced BST (e.g., AVL tree)?