Choose the most appropriate one (10 x 2)
1. Given two sorted lists of size “m” and “n” respectively, the number of comparisons needed in the worst case by the merge sort will be:
(a) m*n
(b) max (m, n)
(c) min (m, n)
(d) m + n - 1
2. Time complexity of insertion sort algorithm in the best case is
(a) O(n)
(a) O(nlog2n)
(c) O(n2)
(d) None of the above
3. Time complexity of quick sort algorithm in the worst case is
(a) O(n)
(b) O(nlog2n)
(c) O(n2)
(d) None of the above
4. Time complexity of heap sort algorithm in the best, average and worst case is
(a) O(n), O(nlog2n) and O(n2)
(b) O(n) O(n2) and O(nlog2n)
(c) O(nlog2n), O(nlog2n) and O(nlog2n)
(d) None of the above
5. Any string of bits of length n represents a unique non-negative integer between
(a) 0 and 2n-1 - 1
(b) 0 and 2n - 1
(c) 1 and 2n - 1
(d) None of the above
6. Which of the following expressions accesses the (i, j)th entry of an m*n matrix stored in a column-major form?
(a) m*(i - l) + j
(b) m*(j - l) + i
(c) m*(n -j) + i
(d) m*(m - i)+j
7. Adjacency matrix for a digraph is
(a) Unit Matrix
(b) Symmetric Matrix
(c) Asymmetric matrix
(d) None of the above
8. Choose the equivalent prefix form of the following expression
(a + (b − c))* ((d − e)/(f + g − h))
(a) * +a − bc /− de − +fgh
(b) * +a −bc − /de − +fgh
(c) * +a − bc /− ed + −fgh
(d) None of the above
9. In linked list representation, a node contains at least
(a) node address field, data field
(b) node number, data field
(c) next address field, information field
(d) None of the above
10. Number of nodes in a complete binary tree of depth k is
(a) 2k
(b) 2k
(c) 2k - l
(d) None of the above
Answer
1. (d) To merge two lists of sizes m and n, we need to do m+n-1 comparisons in the worst case. Since we need to merge 2 at a time, the optimal strategy would be to take the smallest size lists first. The reason for picking the smallest two items is to carry minimum items for repetition in merging.
2. (a) The best-case time complexity of the insertion sort algorithm is O(n) time complexity. Means that the time taken to sort a list is proportional to the number of elements in the list; this is the case when the list is already in the correct order.
3. (c) The worst-case time complexity of a typical implementation of QuickSort is O(n2). The worst-case occurs when the picked pivot is always an extreme (smallest or largest) element. This happens when the input array is sorted or reverse sorted and either the first or last element is picked as a pivot.
4. (c) Heapsort is an efficient, unstable sorting algorithm with an average, best-case, and worst-case time complexity of O(n log n). Heapsort is significantly slower than Quicksort and Merge Sort, so Heapsort is less commonly encountered in practice.
5. (b)
6. (b) (i, j) entries in column-major order of size (m x n). Assume starting address is 1 so, m x (j - 1) + i
7. (c) The adjacency matrix for a digraph is usually not symmetric, since the existence of a directed edge from Pi to Pj does not necessarily imply the existence of a directed edge in the reverse direction.
The adjacency matrix of any graph is symmetric, for the obvious reason that there is an edge between Pi and Pj if and only if there is an edge (the same one) between Pj and Pi.
8. (a) Using the precedence rule of operator and Stack implementation of it
(a + (b − c))* ((d − e)/(f + g − h))
(a + −bc) *((d − e)/(f + g − h))
+a−bc * ((d − e)/(f + g − h))
+a−bc * (−de /(f + g − h))
+a−bc * (−de /(+fg − h))
+a−bc * (−de / −+fgh)
+a−bc * /−de −+fgh
*+a−bc /−de −+fgh
9. (c)
10. (d) The maximum number of nodes in a binary tree of depth K is 2K - 1, k >=1. Here the depth of the tree is 1. A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
---
- The study material for AMIE/B Tech/Junior Engineer exams is available at https://amiestudycircle.com
- If you like the post please share your thoughts in the comment section
Comments