Design & Analysis of Algorithm logo

DAA Unit 4 Part 1 MCQs

PREV
NEXT
Menu
Unit 4

Divide & Conquer:- Matrix Multiplication, Strassen’s Multiplication, Convex Hull, Searching- Binary search, linear search

Ques 1 – Linked list are not suitable for
  1. Insertion Sort
  2. Radix Sort
  3. Binary Search
  4. Polynomial multiplication

Ans – (3)

Explanation –

Linked list is a data structure and it can store and retrieve data. But linked list is not suitable for binary search,

because it is not able to skip numbers between inputs.

Arrays are used in binary search.

By using the binary search formula, we get a[50] from an input of 100 numbers ranging from a[0] to a[99]. Basic sense, we point to the array element a[50].

But we can’t do it with a linked list. We must search the linked list’s head in order of 1, 2, 3, … up to 50.

Q2 – The running time of Strassen’s algorithm for matrix multiplication is
  1. θ(n)
  2. θ(1)
  3. θ(n3)
  4. O(n2.81)

Ans – (4)

Explanation –

With just 7 recursive n/2 x n/2 matrix multiplications and additions and subtractions requires running time θ(n2), this method has a running time O(n2.81). The simple matrix multiplication has running time θ(n3). Strassen method is better than simple matrix multiplication but only for computer. In manual way, simple matrix multiplication is better.

Q3 – Binary search uses a feature of the data that linear search neglects is:
  1. maximum value of the list
  2. length of list
  3. Order of list
  4. Mean value of list

Ans – (3)

Explanation – Binary search uses sorted list of data.

Q4 – The time complexity of linear search algorithm over an array of n elements is
  1. O(nlogn)
  2. O(logn)
  3. O(n2)
  4. O(n)

Ans – (4)

Explanation –

The comparisons made by linear search = 1 + 1 + 1 + … + 1 (n times) = O(n)

Q5 – The time complexity of binary search algorithm over an array of n elements given by (Array is sorted)
  1. O(n)
  2. O(logn)
  3. O(nlogn)
  4. O(n2)

Ans – (2)

Q6 – The time required to search an element in a sorted linked list of length n is
  1. O(n)
  2. O(log2n)
  3. O(1)
  4. O(n2)

Ans – (1)

Explanation – In array you can jump on array[5] or array[12] but in linked list you have to go in the sequence.

Q7 – The best, worst, and average time complexity for a linear search in an array of n elements are
  1. O(n), O(1) and O(n/2)
  2. O(1), O(n) and O(n)
  3. O(1), O(n) and O(n/2)
  4. O(1), O(n) and O((n-1)/2)

Ans – (2)

Explanation –

Linear search is a sequential search algorithm that searches for a target value in a list or array by sequentially checking each element from the start until the target is found or the end of the list is reached.

For the best-case scenario, where the target value is found at the very beginning of the list, the algorithm will only need to check the first element once. Therefore, the time complexity for the best case is O(1).

In the average-case scenario, the target value could be located anywhere in the list, and the algorithm will need to check on average (n+1)/2 elements. Therefore, the time complexity for the average case is O(n).

For the worst-case scenario, the target value is located at the very end of the list or not present at all. In this case, the algorithm will need to check every element in the list, resulting in a time complexity of O(n).

Q8 – Breadth first traversal (BFS) is a method to traverse
  1. All successors of a visited node before any successor of any of those successors.
  2. a single path of the graph as far it can go
  3. the graph using shortest path
  4. none of these

Ans – (1)

Explanation –

Breadth-first traversal (BFS) is a graph traversal algorithm that traverses the nodes of a graph in breadth-first order, i.e., it visits all the neighbors of a node before moving on to visit the neighbors of its neighbors.

One of the main characteristics of BFS is that it explores all the nodes at the same depth level before moving on to explore the nodes at the next depth level. This means that all successors of a visited node are explored before any successor of any of those successors.

In other words, BFS visits all the nodes at a given distance from the starting node before moving on to the nodes that are farther away. This makes BFS particularly useful for finding the shortest path between two nodes in an unweighted graph, as it guarantees that the shortest path will be found once the target node is reached.

Q9 – A linear list in which elements can be added or removed at either end but not in the middle is known as
  1. Deque
  2. Stack
  3. Tree
  4. Queue

Ans – (1)

Explanation – A deque (double ended queue) is a data structure that allows for efficient insertion and deletion of elements at both the front and the back of the queue. It can be thought of as a combination of a stack and a queue, where elements can be added and removed from both ends.

Q10 – What is the number of comparison required by an algorithm for finding fourth largest element in the given input list of ‘n’ elements? (RPSC-2022)
  1. 2n-3
  2. 2n-4
  3. 2n-5
  4. 2(2n-5)

Ans – (3)

Explanation – Using a modified version of the quick sort algorithm, we can find the fourth largest element in O(n) time in the worst case, which requires 2n-5 comparisons.

The basic idea is to use quicksort to find the kth largest element in the list, where k=n-3. This can be done in O(n) time on average and O(n^2) in the worst case. After finding the kth largest element, we can return the fourth largest element as the (k-3)th element.

The number of comparisons required by quicksort to find the kth largest element is 2(n-1) in the worst case, because at each step, the algorithm compares the pivot element to all other elements in the list. Since we are looking for the (n-3)th largest element, the number of comparisons required is 2(n-1) – 2(n-3) + 1 = 2n-5.

Therefore, the correct answer is option 3: 2n-5.

Q11 – Which of the following is the correct recurrence relation related to the complexity of binary search? (RPSC-2022)
  1. T(n) = T(n/2) + O(n)
  2. T(n) = T(n/2) + 1
  3. T(n) = 2T(n/2) + O(n)
  4. T(n) = 2T(n/2) + 1

Ans – (2)

Explanation – In binary search, we repeatedly divide the sorted array in half until we find the target element or determine that it is not in the array. At each step, we compare the target element with the middle element of the current subarray.

The recurrence relation for the time complexity of binary search can be expressed as T(n) = T(n/2) + 1, where T(n) represents the time complexity of searching an array of size n. The base case for this recurrence relation is T(1) = 1, since we can find the target element in an array of size 1 in constant time.

Q12 – What is the worst-case time complexity of search operation on unordered and ordered list using linear search algorithm respectively? (RPSC-2022)
  1. O(n) and O(1)
  2. O(n) and O(logn)
  3. O(n) and O(n)
  4. O(logn) and O(logn)

Ans – (1)

Explanation –

The worst-case time complexity of the search operation on an unordered and ordered list using the linear search algorithm is O(n), where n is the number of elements in the list.

In the worst case, the algorithm would have to compare the target element with every element in the list until it finds the target element or determines that it is not present.

Q13 – The time complexity of Strassen’s matrix multiplication problem is:
  1. O(n8.21)
  2. O(2n/2)
  3. O(Sn)
  4. O(n2.81)

Ans – (4)

Explanation –

Matrix multiplication is a very time-consuming process O(n3) for the human and for the computer.

Strassen’s multiplication is the modified version of simple matrix multiplication. It has time complexity O(n2.81). It is less time-consuming only for the computer, because it has multiple computations.

Q14 – Which of the following is an algorithmic design, where the solution to the problem can be viewed as the result of sequence of decisions?
  1. Dynamic Programming
  2. Divide and Conquer
  3. Greedy Method
  4. Branch and Bound

Ans – (1)

Explanation –

Dynamic programming is an algorithm design method that can be used when a solution to the problem is viewed as the result of sequence of decisions. Dynamic programming is a technique for solving problems with overlapping subproblems. These sub-problems are generated by iterating the solution of a given problem only once with the corresponding solution of its smaller sub-problems and entering the results in a table from which the solution of the original problem is obtained. It was invented in the 1950s by Richard Bellman, a prominent American mathematician.

Q15 – Which of the following problems cannot be solved by using divide & conquer algorithm? (DSSSB PGT 2022)
  1. Merge Sort
  2. 0/1 Knapsack
  3. Compute binomial coefficient nCk
  4. Binary Search

Ans – (2)

Explanation – 0/1 knapsack problem can be solved by dynamic programming.

Q16 – The numbers 70, 50, 10, 80, 30, 60, 100, 90, 40 20 are inserted in the given order in to a binary search tree. What is the in-order traversal sequence of the resultant binary search tree? (DSSSB PGT 2021)

 

  1. 70, 50, 10, 80, 30, 60, 100, 90, 40, 20
  2. 100, 90, 80, 70, 60, 50, 40, 30, 20, 10
  3. 10, 30, 50, 70, 90, 20, 40, 60, 80, 100
  4. 10, 20, 30, 40, 50, 60, 70, 80, 90, 100

Ans – (4)

Explanation –

Inorder

Q17 – How many different binary search trees can be constructed with 6 different nodes? (DSSSB PGT 2021)
  1. 32
  2. 128
  3. 132
  4. 64

Ans – (3)

Explanation –

Total number of possible Binary Search Trees with n different keys (countBST(n)) = Catalan number Cn = (2n)! / ((n + 1)! * n!)

For n = 6, The Catalan number is (2*6)!/((6+1)!*6!) = 132

Q18 – What is the average number of comparisons required in sequential search to find an element? (DSSSB PGT 2021)
  1. n2
  2. (n+1)/2
  3. n
  4. n(n+1)/2

Ans – (2)

Explanation – The sum of average number of comparisons is = (1 + 2 + 3 + … + n)/n = n(n+1)/2n = (n+1)/2.

Q19 – What is the maximum running time of binary search algorithm, when n = 12,000? (DSSSB TGT 2021)
  1. 15
  2. 12
  3. 14
  4. 13

Ans – (3)

Explanation – The maximum running time of the binary search algorithm is O(log2n), where n is the size of the sorted array being searched.

In this case, n = 12,000, so the maximum running time of the binary search algorithm is O(log212,000) = 14. [as 214 = 16,384].

Q20 – Which statement is correct regarding binary search tree? (DSSSB TGT 2021)
l. The value at node N is less than every value in the left subtree of node.
ll. The value at node N is greater than or equal to every value in the right subtree of N.
  1. Neither I nor II
  2. Both I and II
  3. Only I
  4. Only II

Ans – (1)

Explanation –

The correct statement is –

  1. The value at node N is greater than or equal to every value in the left subtree of node.
  2. The value at node N is less than every value in the right subtree of N.
PREV
NEXT

BOOKS

Algorithm T H CoremanAlgorithm by Udit AgarwalAlgorithm Ellis HorowitzData Structure & Algorithm Made Easy Narasimha

 

GATE Study Material
Previous Year Paper
Subjective Questions