Multiple Choice Questions
Algorithms and Algorithmic Efficiency
Topic: Algorithms and Algorithmic Efficiency
Grade: 10
Question 1:
What is the time complexity of a linear search algorithm?
a) O(1)
b) O(log n)
c) O(n)
d) O(n^2)
Answer: c) O(n)
Explanation: In a linear search algorithm, the time complexity is directly proportional to the number of elements in the input. This means that as the size of the input increases, the time taken to find the desired element also increases linearly. For example, if we have an array of n elements and we want to search for a specific element, the worst-case scenario is that we have to look through all n elements.
Question 2:
Which of the following sorting algorithms has a worst-case time complexity of O(n^2)?
a) Quick sort
b) Merge sort
c) Bubble sort
d) Insertion sort
Answer: c) Bubble sort
Explanation: Bubble sort compares adjacent elements and swaps them if they are in the wrong order. In the worst-case scenario, where the input is in reverse order, bubble sort would have to perform n-1 comparisons for the first pass, n-2 for the second pass, and so on. This results in a time complexity of O(n^2). For example, if we have an array of 5 elements [5, 4, 3, 2, 1], bubble sort would need to perform 4 + 3 + 2 + 1 = 10 comparisons.
Question 3:
Which data structure is typically used to implement a stack?
a) Array
b) Linked list
c) Tree
d) Hash table
Answer: a) Array
Explanation: A stack is a data structure that follows the Last-In-First-Out (LIFO) principle. An array is commonly used to implement a stack because it provides constant time access to elements and allows for efficient insertion and deletion at the end of the stack. For example, if we have a stack of integers [1, 2, 3], pushing the element 4 onto the stack would involve inserting it at the end of the array.
Question 4:
What is the time complexity of a binary search algorithm?
a) O(1)
b) O(log n)
c) O(n)
d) O(n^2)
Answer: b) O(log n)
Explanation: In a binary search algorithm, the time complexity is logarithmic. This means that as the size of the input increases, the time taken to find the desired element increases at a slower rate. Binary search works by repeatedly dividing the search space in half until the desired element is found or the search space becomes empty. For example, if we have a sorted array of n elements and we want to search for a specific element, binary search would divide the search space in half at each step, resulting in a time complexity of O(log n).
Question 5:
Which of the following is an example of a greedy algorithm?
a) Depth-first search
b) Dijkstra\’s algorithm
c) Kruskal\’s algorithm
d) Bellman-Ford algorithm
Answer: c) Kruskal\’s algorithm
Explanation: Greedy algorithms make locally optimal choices at each step with the hope of finding a globally optimal solution. Kruskal\’s algorithm for finding the minimum spanning tree of a graph is an example of a greedy algorithm. It starts with an empty set of edges and repeatedly adds the edge with the smallest weight that does not create a cycle. For example, in a graph with vertices A, B, C, and edges with weights 2, 3, and 4, Kruskal\’s algorithm would start by selecting the edge with weight 2.
(Note: This is the first set of 5 questions. Please let me know if you would like me to continue with the next set of questions.)