Divide and Conquer - Merge Sort
1. What is the time complexity of Merge Sort in the worst case?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)
2. The recurrence relation for Merge Sort is:
a) T(n) = T(n-1) + n
b) T(n) = 2T(n/2) + n
c) T(n) = T(n/2) + 1
d) T(n) = nT(n/2) + 1
3. Merge Sort follows which strategy?
a) Top-down divide and conquer
b) Bottom-up divide and conquer
c) Greedy approach
d) Dynamic programming
4. What is the space complexity of Merge Sort?
a) O(1)
b) O(log n)
c) O(n)
d) O(n²)
5. Which of the following is TRUE about Merge Sort?
a) It is an in-place sorting algorithm
b) It has different complexities for best and worst cases
c) It is a stable sorting algorithm
d) It uses less memory than Quick Sort
6. The time complexity of merging two sorted arrays of size n/2 each is:
a) O(log n)
b) O(n)
c) O(n log n)
d) O(n²)
7. In the merge operation, what happens when one array is exhausted?
a) The algorithm stops
b) Copy remaining elements from the other array
c) Start merging from the beginning
d) Reverse the arrays
8. How many levels are there in the recursion tree of Merge Sort for input size n?
a) n
b) log n
c) n log n
d) n²
9. Merge Sort is preferred when:
a) Memory is limited
b) Stable sorting is required
c) Input is nearly sorted
d) In-place sorting is needed
10. The divide and conquer approach in Merge Sort involves:
a) Dividing array into unequal parts
b) Sorting each element individually
c) Dividing into two equal halves recursively
d) Finding the minimum element first
Quick Sort Algorithm
1. What is the worst-case time complexity of Quick Sort?
a) O(n log n)
b) O(n)
c) O(n²)
d) O(log n)
2. Quick Sort uses which divide and conquer strategy?
a) Bottom-up
b) Top-down
c) Both top-down and bottom-up
d) Neither
3. When does Quick Sort perform worst?
a) Random data
b) Nearly sorted data
c) Reverse sorted data
d) Both b and c
4. The partitioning step in Quick Sort has time complexity:
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
5. In the best case, Quick Sort's recurrence relation is:
a) T(n) = T(n-1) + n
b) T(n) = 2T(n/2) + n
c) T(n) = T(n/2) + 1
d) T(n) = 2T(n/2) + 1
6. Quick Sort is:
a) Stable and in-place
b) Stable but not in-place
c) Not stable but in-place
d) Neither stable nor in-place
7. After partitioning, the pivot element is:
a) At the beginning of array
b) At the end of array
c) In its final sorted position
d) At a random position
8. The space complexity of Quick Sort is:
a) O(1)
b) O(log n)
c) O(n)
d) O(n²)
9. Quick Sort is preferred for:
a) Nearly sorted data
b) Data that needs stable sorting
c) Random data in main memory
d) Data with many duplicates
10. What happens after the partitioning step in Quick Sort?
a) Elements are merged
b) Subarrays are recursively sorted
c) Array is completely sorted
d) Pivot is removed
11. The worst-case recurrence relation for Quick Sort is:
a) T(n) = 2T(n/2) + n
b) T(n) = T(n-1) + n
c) T(n) = T(n/2) + n
d) T(n) = nT(n/2) + 1
12. Quick Sort differs from Merge Sort in that:
a) It requires extra space for merging
b) It doesn't require a merging step
c) It has better worst-case performance
d) It is always stable
Introduction to Graphs
1. A graph is defined as:
a) A set of nodes only
b) A set of edges only
c) A set of nodes and edges connecting them
d) A tree with cycles
2. In an undirected graph, if node A is adjacent to node B, then:
a) B is not adjacent to A
b) B is adjacent to A
c) A and B are the same node
d) There must be a weight on the edge
3. The space complexity of adjacency matrix representation is:
a) O(n)
b) O(n log n)
c) O(n²)
d) O(n³)
4. Which representation is better for sparse graphs?
a) Adjacency matrix
b) Adjacency list
c) Incidence matrix
d) Both a and c
5. The time complexity to check if an edge exists in adjacency matrix is:
a) O(1)
b) O(n)
c) O(log n)
d) O(n²)
6. In adjacency list representation, the space complexity for a dense graph is:
a) O(n)
b) O(n log n)
c) O(n²)
d) O(1)
7. A weighted graph has:
a) Directed edges only
b) Undirected edges only
c) Values associated with edges
d) No cycles
8. Which is NOT a main graph type?
a) Weighted directed
b) Unweighted undirected
c) Weighted undirected
d) Cyclic directed
9. For checking edge existence, adjacency matrix provides:
a) O(n) time
b) O(log n) time
c) O(1) time
d) O(n²) time
10. Adjacency list is preferred when:
a) Graph is dense
b) Graph is sparse
c) Frequent edge checking is needed
d) Memory is unlimited
11. In a directed graph, an edge from A to B means:
a) B is adjacent to A
b) A is adjacent to B
c) Both A and B are adjacent to each other
d) A and B are the same node
12. The adjacency matrix for an undirected graph is:
a) Always diagonal
b) Always symmetric
c) Always upper triangular
d) Always sparse
13. Graph representation examples include:
a) Facebook friendships (logical)
b) City road networks (physical)
c) Both a and b
d) Neither a nor b
14. Dense graphs are characterized by:
a) Few edges relative to possible edges
b) Many edges relative to possible edges
c) No edges
d) Only self-loops
Greedy Algorithms - Minimum Spanning Tree (MST)
1. The MST problem aims to find:
a) The shortest path between two nodes
b) A tree that spans all nodes with minimum total weight
c) The maximum spanning tree
d) A tree with maximum number of edges
2. A spanning tree of a graph with n vertices has exactly:
a) n edges
b) n-1 edges
c) n+1 edges
d) 2n edges
3. Which property is NOT required for MST?
a) Connected
b) Spans all vertices
c) No cycles
d) Maximum weight
4. Greedy design strategy:
a) Always finds global optimum
b) Makes locally optimal choices
c) Requires dynamic programming
d) Never works for MST
5. A graph can have:
a) Only one MST
b) At most two MSTs
c) Multiple MSTs with same weight
d) No MST if it has cycles
6. MST algorithms include:
a) Kruskal's and Prim's
b) Dijkstra's only
c) DFS and BFS
d) Quick Sort and Merge Sort
7. In an unweighted graph, the MST:
a) Does not exist
b) Is unique
c) Can be any spanning tree
d) Must use BFS
8. The MST problem is solved using:
a) Divide and conquer
b) Greedy approach
c) Backtracking
d) Branch and bound
9. For a connected graph with n vertices and m edges, MST will have:
a) m edges
b) n edges
c) n-1 edges
d) m-1 edges
10. Which statement about MST is TRUE?
a) It always contains the shortest edge in the graph
b) It may contain the shortest edge in the graph
c) It never contains the longest edge in the graph
d) It must contain all edges of the graph
11. The main difference between MST and shortest path is:
a) MST finds path between two specific nodes
b) MST minimizes total tree weight, not individual path lengths
c) MST only works on directed graphs
d) MST requires negative weights
12. If all edges in a graph have the same weight, then:
a) No MST exists
b) Exactly one MST exists
c) Any spanning tree is an MST
d) MST problem becomes NP-hard
13. MST is applicable to:
a) Directed graphs only
b) Undirected graphs only
c) Both directed and undirected graphs
d) Trees only
14. The greedy choice in MST algorithms typically involves:
a) Selecting the longest edge
b) Selecting edges that don't form cycles
c) Selecting the shortest safe edge
d) Selecting random edges
15. When might a graph have multiple MSTs?
a) When it has negative weights
b) When it has edges with equal weights
c) When it's disconnected
d) When it has more than n-1 edges
Kruskal's Algorithm
1. Kruskal's algorithm is best suited for:
a) Dense graphs
b) Sparse graphs
c) Directed graphs
d) Disconnected graphs
2. The first step in Kruskal's algorithm is:
a) Select a starting vertex
b) Sort all edges by weight
c) Find the minimum edge
d) Check for cycles
3. Kruskal's algorithm stops when:
a) All edges are processed
b) A cycle is detected
c) n-1 edges are selected
d) All vertices are visited
4. The time complexity of Kruskal's algorithm is:
a) O(n)
b) O(n log n)
c) O(m log m)
d) O(n²)
5. In Kruskal's algorithm, an edge is rejected if:
a) It has maximum weight
b) It creates a cycle
c) It's already in the MST
d) It connects two visited vertices
6. Kruskal's algorithm uses which strategy?
a) Dynamic programming
b) Divide and conquer
c) Greedy approach
d) Backtracking
7. For cycle detection, Kruskal's algorithm can efficiently use:
a) DFS
b) BFS
c) Union-Find data structure
d) Adjacency matrix
8. The greedy choice in Kruskal's algorithm is:
a) Select vertex with minimum degree
b) Select minimum weight edge that doesn't create cycle
c) Select maximum weight edge
d) Select edge connecting to unvisited vertex
9. For dense graphs, Kruskal's time complexity becomes:
a) O(n log n)
b) O(n²)
c) O(n² log n)
d) O(n³)
10. Kruskal's algorithm is:
a) Vertex-based
b) Edge-based
c) Path-based
d) Level-based
11. In the edge list {A,B}:3, {B,C}:1, {A,C}:2, Kruskal's algorithm will select edges in order:
a) {A,B}, {B,C}, {A,C}
b) {B,C}, {A,C}, {A,B}
c) {B,C}, {A,C}
d) {A,C}, {A,B}, {B,C}
12. The space complexity of Kruskal's algorithm is:
a) O(1)
b) O(n)
c) O(m)
d) O(n²)
13. Kruskal's algorithm guarantees:
a) Shortest path between all pairs
b) Minimum spanning tree
c) Maximum spanning tree
d) Eulerian path
14. If two edges have the same weight in Kruskal's algorithm:
a) The algorithm fails
b) Either can be chosen first
c) Both must be included
d) Both must be excluded
15. Kruskal's algorithm processes edges in:
a) Random order
b) Decreasing weight order
c) Increasing weight order
d) Alphabetical order
Prim's Algorithm
1. Prim's algorithm is best suited for:
a) Sparse graphs
b) Dense graphs
c) Directed graphs
d) Disconnected graphs
2. Prim's algorithm starts with:
a) All vertices
b) All edges
c) A single arbitrary vertex
d) The minimum weight edge
3. The time complexity of Prim's algorithm is:
a) O(n)
b) O(n log n)
c) O(n²)
d) O(m log m)
4. In each step, Prim's algorithm adds:
a) The minimum weight edge in the graph
b) The minimum weight edge connecting tree to non-tree vertex
c) Any edge that doesn't create a cycle
d) The maximum weight edge
5. Prim's algorithm never creates:
a) Multiple components
b) Cycles
c) Weighted edges
d) Spanning trees
6. Prim's algorithm is:
a) Edge-based
b) Vertex-based
c) Path-based
d) Level-based
7. During execution, Prim's algorithm maintains:
a) Multiple disconnected components
b) A single growing tree
c) All possible paths
d) Sorted edge list
8. The space complexity of Prim's algorithm is:
a) O(1)
b) O(n)
c) O(m)
d) O(n²)
9. Prim's algorithm can start from:
a) Only the first vertex
b) Only the vertex with minimum degree
c) Any vertex
d) Only vertices with odd degree
10. Compared to Kruskal's, Prim's algorithm:
a) Always produces different MST
b) Is better for sparse graphs
c) Doesn't require sorting all edges
d) Has higher time complexity
11. The greedy choice in Prim's algorithm is:
a) Select minimum weight edge globally
b) Select minimum weight edge from current tree to outside
c) Select maximum weight edge
d) Select random edge
12. Prim's algorithm terminates when:
a) All edges are processed
b) n-1 edges are selected
c) All vertices are in the tree
d) Both b and c
13. The cut property used in Prim's algorithm states:
a) Any edge can be selected
b) Minimum edge crossing a cut is safe for MST
c) Maximum edge should be avoided
d) Cycles must be prevented
14. For a complete graph with n vertices, Prim's algorithm examines:
a) n edges
b) n-1 edges
c) O(n²) edges
d) All possible edges
15. Prim's algorithm differs from Kruskal's in that it:
a) Produces different MST weight
b) Grows tree from single vertex
c) Requires cycle detection
d) Cannot handle weighted graphs
Dijkstra's Algorithm
1. Dijkstra's algorithm finds:
a) Minimum spanning tree
b) Shortest paths from single source to all vertices
c) Maximum flow in network
d) Strongly connected components
2. Dijkstra's algorithm does NOT work with:
a) Weighted graphs
b) Directed graphs
c) Negative edge weights
d) Dense graphs
3. The time complexity of Dijkstra's algorithm is:
a) O(n)
b) O(n log n)
c) O(n²)
d) O(n³)
4. In each iteration, Dijkstra's algorithm selects:
a) Maximum weight edge
b) Unvisited vertex with minimum distance
c) Random unvisited vertex
d) Vertex with maximum degree
5. The distance relaxation step checks if:
a) Current path is shorter than known path
b) Path through current vertex gives shorter distance
c) All paths have been found
d) Graph contains cycles
6. Dijkstra's algorithm uses which approach?
a) Dynamic programming
b) Divide and conquer
c) Greedy strategy
d) Backtracking
7. The space complexity of Dijkstra's algorithm is:
a) O(1)
b) O(n)
c) O(m)
d) O(n²)
8. Initially, the distance of the source vertex is set to:
9. Dijkstra's algorithm terminates when:
a) All edges are relaxed
b) All vertices are visited
c) Shortest path is found
d) Target vertex is reached
10. The distance array in Dijkstra's algorithm:
a) Increases monotonically
b) Decreases monotonically
c) Never increases once set
d) Can increase and decrease
11. Dijkstra's algorithm is optimal because:
a) It checks all possible paths
b) Greedy choice is always correct with non-negative weights
c) It uses dynamic programming
d) It finds maximum spanning tree
12. For finding shortest path between two specific vertices, Dijkstra's algorithm:
a) Can terminate early when target is reached
b) Must complete full algorithm
c) Cannot be used
d) Requires modification
13. The relaxation operation updates distance if:
a) New path is longer
b) New path is shorter
c) Vertex is unvisited
d) Edge weight is positive
14. Dijkstra's algorithm produces:
a) Single shortest path
b) All shortest paths from source
c) Shortest path tree from source
d) Minimum spanning tree
15. If all edge weights are equal in Dijkstra's algorithm:
a) Algorithm fails
b) Reduces to BFS
c) Becomes slower
d) Finds MST instead
16. The key insight in Dijkstra's algorithm is:
a) All paths must be checked
b) Shortest distance vertex can finalize its distance
c) Longest paths are easier to find
d) Cycles must be avoided
Additional Topics Summary
1. The merge operation in merge sort has complexity:
a) O(log n)
b) O(n)
c) O(n log n)
d) O(n²)
2. When merging two sorted arrays, if one array is exhausted:
a) Algorithm terminates
b) Remaining elements from other array are copied
c) Process restarts
d) Arrays are swapped
3. In array representation of binary trees, parent of node at index 7 is at:
a) Index 2
b) Index 3
c) Index 14
d) Index 15
4. Which sorting algorithm is stable?
a) Quick Sort
b) Heap Sort
c) Merge Sort
d) Selection Sort
5. For a complete binary tree with 7 nodes, array representation uses:
a) 7 positions
b) 8 positions
c) 15 positions
d) 16 positions
6. The worst-case space complexity for array representation of binary tree occurs when:
a) Tree is complete
b) Tree is perfect
c) Tree has only right children
d) Tree is balanced
7. Quick Sort performs best when:
a) Data is sorted
b) Data is reverse sorted
c) Data is random
d) Data has duplicates
8. In Quick Sort, the partitioning step:
a) Sorts the entire array
b) Places pivot in correct position
c) Merges two subarrays
d) Finds the minimum element
9. Adjacency matrix is preferred over adjacency list when:
a) Graph is sparse
b) Memory is limited
c) Frequent edge lookups are needed
d) Graph is unweighted
10. The height of a complete binary tree with n nodes is:
a) n
b) log n
c) ⌊log n⌋
d) n/2
11. For graphs, density refers to:
a) Number of vertices
b) Number of edges
c) Ratio of actual edges to possible edges
d) Maximum vertex degree
12. Which algorithm guarantees O(n log n) in all cases?
a) Quick Sort
b) Merge Sort
c) Bubble Sort
d) Insertion Sort
13. In binary tree array representation, left child of root is at index:
14. The main advantage of Quick Sort over Merge Sort is:
a) Better worst-case complexity
b) Stability
c) In-place sorting capability
d) Consistent performance
15. For MST algorithms, which statement is TRUE?
a) Kruskal's is always faster than Prim's
b) Both always produce the same MST structure
c) Both guarantee minimum total weight
d) Prim's requires edge sorting