McqMate
These multiple-choice questions (MCQs) are designed to enhance your knowledge and understanding in the following areas: Computer Science Engineering (CSE) .
201. |
Which of the following methods can be used to solve the matrix chain multiplication problem? |
A. | dynamic programming |
B. | brute force |
C. | recursion |
D. | dynamic programming, brute force, recursion |
Answer» D. dynamic programming, brute force, recursion | |
Explanation: dynamic programming, brute force, recursion methods can be used to solve the matrix chain multiplication problem. |
202. |
Consider the matrices P, Q and R which are 10 x 20, 20 x 30 and 30 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the three matrices? |
A. | 18000 |
B. | 12000 |
C. | 24000 |
D. | 32000 |
Answer» A. 18000 | |
Explanation: the minimum number of multiplications are 18000. this is the case when the matrices are parenthesized as (p*q)*r. |
203. |
Consider the brute force implementation in which we find all the possible ways of multiplying the given set of n matrices. What is the time complexity of this implementation? |
A. | o(n!) |
B. | o(n3) |
C. | o(n2) |
D. | exponential |
Answer» D. exponential | |
Explanation: the time complexity of finding all the possible ways of multiplying a set of n matrices is given by (n-1)th catalan number which is exponential. |
204. |
Which of the following methods can be used to solve the longest common subsequence problem? |
A. | recursion |
B. | dynamic programming |
C. | both recursion and dynamic programming |
D. | greedy algorithm |
Answer» C. both recursion and dynamic programming | |
Explanation: both recursion and dynamic programming can be used to solve the longest subsequence problem. |
205. |
Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence? |
A. | 9 |
B. | 8 |
C. | 7 |
D. | 6 |
Answer» C. 7 | |
Explanation: the longest common subsequence is “prtpqrs” and its length is 7. |
206. |
Which of the following problems can be solved using the longest subsequence problem? |
A. | longest increasing subsequence |
B. | longest palindromic subsequence |
C. | longest bitonic subsequence |
D. | longest decreasing subsequence |
Answer» B. longest palindromic subsequence | |
Explanation: to find the longest palindromic subsequence in a given string, reverse the given string and then find the longest common subsequence in the given string and the reversed string. |
207. |
Longest common subsequence is an example of |
A. | greedy algorithm |
B. | 2d dynamic programming |
C. | 1d dynamic programming |
D. | divide and conquer |
Answer» B. 2d dynamic programming | |
Explanation: longest common subsequence is an example of 2d dynamic programming. |
208. |
What is the time complexity of the brute force algorithm used to find the longest common subsequence? |
A. | o(n) |
B. | o(n2) |
C. | o(n3) |
D. | o(2n) |
Answer» D. o(2n) | |
Explanation: the time complexity of the brute force algorithm used to find the longest common subsequence is o(2n). |
209. |
Which of the following is the longest common subsequence between the strings “hbcfgmnapq” and “cbhgrsfnmq” ? |
A. | hgmq |
B. | cfnq |
C. | bfmq |
D. | fgmna |
Answer» D. fgmna | |
Explanation: the length of the longest common subsequence is 4. but ‘fgmna’ is not the longest common subsequence as its length is 5. |
210. |
Which of the following methods can be used to solve the longest palindromic subsequence problem? |
A. | dynamic programming |
B. | recursion |
C. | brute force |
D. | dynamic programming, recursion, brute force |
Answer» D. dynamic programming, recursion, brute force | |
Explanation: dynamic programming, recursion, brute force can be used to solve the longest palindromic subsequence problem. |
211. |
Which of the following is not a palindromic subsequence of the string “ababcdabba”? |
A. | abcba |
B. | abba |
C. | abbbba |
D. | adba |
Answer» D. adba | |
Explanation: ‘adba’ is not a palindromic sequence. |
212. |
For which of the following, the length of the string is not equal to the length of the longest palindromic subsequence? |
A. | a string that is a palindrome |
B. | a string of length one |
C. | a string that has all the same letters(e.g. aaaaaa) |
D. | some strings of length two |
Answer» D. some strings of length two | |
Explanation: a string of length 2 for eg: ab is not a palindrome. |
213. |
What is the length of the longest palindromic subsequence for the string “ababcdabba”? |
A. | 6 |
B. | 7 |
C. | 8 |
D. | 9 |
Answer» B. 7 | |
Explanation: the longest palindromic subsequence is “abbabba” and its length is 7. |
214. |
What is the time complexity of the brute force algorithm used to find the length of the longest palindromic subsequence? |
A. | o(1) |
B. | o(2n) |
C. | o(n) |
D. | o(n2) |
Answer» B. o(2n) | |
Explanation: in the brute force algorithm, all the subsequences are found and the length of the longest palindromic subsequence is calculated. this takes exponential time. |
215. |
For every non-empty string, the length of the longest palindromic subsequence is at least one. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: a single character of any string can always be considered as a palindrome and its length is one. |
216. |
Longest palindromic subsequence is an example of |
A. | greedy algorithm |
B. | 2d dynamic programming |
C. | 1d dynamic programming |
D. | divide and conquer |
Answer» B. 2d dynamic programming | |
Explanation: longest palindromic subsequence is an example of 2d dynamic programming. |
217. |
Which of the following methods can be used to solve the edit distance problem? |
A. | recursion |
B. | dynamic programming |
C. | both dynamic programming and recursion |
D. | greedy algorithm |
Answer» C. both dynamic programming and recursion | |
Explanation: both dynamic programming and recursion can be used to solve the edit distance problem. |
218. |
The edit distance satisfies the axioms of a metric when the costs are non-negative. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: d(s,s) = 0, since each string can be transformed into itself without any change. d(s1, s2) > 0 when s1 != s2, since the transformation would require at least one operation. |
219. |
Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: consider the strings “abcd” and “efghi”. the string “efghi” can be converted to “abcd” by deleting “i” and converting “efgh” to “abcd”. the cost of transformation is 5, which is equal to the length of the larger string. |
220. |
Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings? |
A. | 3 |
B. | 4 |
C. | 5 |
D. | 6 |
Answer» B. 4 | |
Explanation: “monday” can be converted to “tuesday” by replacing “m” with “t”, “o” with “u”, “n” with “e” and inserting “s” at the appropriate position. so, the edit distance is 4. |
221. |
Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings? |
A. | 0 |
B. | 4 |
C. | 2 |
D. | 3 |
Answer» B. 4 | |
Explanation: the empty string can be transformed into “abcd” by inserting “a”, “b”, “c” and “d” at appropriate positions. thus, the edit distance is 4. |
222. |
Which of the following is NOT a Catalan number? |
A. | 1 |
B. | 5 |
C. | 14 |
D. | 43 |
Answer» D. 43 | |
Explanation: catalan numbers are given by: (2n!)/((n+1)!n!). |
223. |
Which of the following methods can be used to find the nth Catalan number? |
A. | recursion |
B. | binomial coefficients |
C. | dynamic programming |
D. | recursion, binomial coefficients, dynamic programming |
Answer» D. recursion, binomial coefficients, dynamic programming | |
Explanation: all of the mentioned methods can be used to find the nth catalan number. |
224. |
Which of the following implementations of Catalan numbers has the smallest time complexity? |
A. | dynamic programming |
B. | binomial coefficients |
C. | recursion |
D. | all have equal time complexity |
Answer» B. binomial coefficients | |
Explanation: The time complexities are as follows: Dynamic programming: O(n2) Recursion: Exponential Binomial coefficients: O(n). |
225. |
Which of the following methods can be used to solve the assembly line scheduling problem? |
A. | recursion |
B. | brute force |
C. | dynamic programming |
D. | all of the mentioned |
Answer» D. all of the mentioned | |
Explanation: all of the above mentioned methods can be used to solve the assembly line scheduling problem. |
226. |
What is the time complexity of the brute force algorithm used to solve the assembly line scheduling problem? |
A. | o(1) |
B. | o(n) |
C. | o(n2) |
D. | o(2n) |
Answer» D. o(2n) | |
Explanation: in the brute force algorithm, all the possible ways are calculated which are of the order of 2n. |
227. |
In the dynamic programming implementation of the assembly line scheduling problem, how many lookup tables are required? |
A. | 0 |
B. | 1 |
C. | 2 |
D. | 3 |
Answer» C. 2 | |
Explanation: in the dynamic programming implementation of the assembly line scheduling problem, 2 lookup tables are required one for storing the minimum time and the other for storing the assembly line number. |
228. |
What is the time complexity of the above dynamic programming implementation of the assembly line scheduling problem? |
A. | o(1) |
B. | o(n) |
C. | o(n2) |
D. | o(n3) |
Answer» B. o(n) | |
Explanation: the time complexity of the above dynamic programming implementation of the assembly line scheduling problem is o(n). |
229. |
Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem? |
A. | greedy algorithm |
B. | recursion |
C. | dynamic programming |
D. | both recursion and dynamic programming |
Answer» D. both recursion and dynamic programming | |
Explanation: dynamic programming and recursion can be used to solve the problem. |
230. |
In which of the following cases the minimum no of insertions to form palindrome is maximum? |
A. | string of length one |
B. | string with all same characters |
C. | palindromic string |
D. | non palindromic string |
Answer» D. non palindromic string | |
Explanation: in string of length one, string with all same characters and a palindromic string the no of insertions is zero since the strings are already palindromes. to convert a non-palindromic string to a palindromic string, the minimum length of string to be added is 1 which is greater than all the other above cases. hence the minimum no of insertions to form palindrome is maximum in non-palindromic strings. |
231. |
Consider the string “abbccbba”. What is the minimum number of insertions required to make the string a palindrome? |
A. | 0 |
B. | 1 |
C. | 2 |
D. | 3 |
Answer» A. 0 | |
Explanation: the given string is already a palindrome. so, no insertions are required. |
232. |
Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem? |
A. | minimum number of jumps problem |
B. | longest common subsequence problem |
C. | coin change problem |
D. | knapsack problems |
Answer» B. longest common subsequence problem | |
Explanation: a variation of longest common subsequence can be used to solve the minimum number of insertions to form a palindrome problem. |
233. |
Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem? |
A. | brute force |
B. | recursion |
C. | dynamic programming |
D. | brute force, recursion, dynamic programming |
Answer» D. brute force, recursion, dynamic programming | |
Explanation: brute force, recursion and dynamic programming can be used to find the submatrix that has the maximum sum. |
234. |
In which of the following cases, the maximum sum rectangle is the 2D matrix itself? |
A. | when all the elements are negative |
B. | when all the elements are positive |
C. | when some elements are positive and some negative |
D. | when diagonal elements are positive and rest are negative |
Answer» A. when all the elements are negative | |
Explanation: when all the elements of a matrix are positive, the maximum sum rectangle is the 2d matrix itself. |
235. |
Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle? |
A. | 3 |
B. | 6 |
C. | 12 |
D. | 18 |
Answer» C. 12 | |
Explanation: since all the elements of the 2×3 matrix are positive, the maximum sum rectangle is the matrix itself and the sum of elements is 12. |
236. |
Consider the 2×2 matrix {{-1,-2},{-3,-4}}. What is the sum of elements of the maximum sum rectangle? |
A. | 0 |
B. | -1 |
C. | -7 |
D. | -12 |
Answer» B. -1 | |
Explanation: since all the elements of the 2×2 matrix are negative, the maximum sum rectangle is {-1}, a 1×1 matrix containing the largest element. the sum of elements of the maximum sum rectangle is -1. |
237. |
The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm? |
A. | hirschberg’s algorithm |
B. | needleman-wunsch algorithm |
C. | kadane’s algorithm |
D. | wagner fischer algorithm |
Answer» C. kadane’s algorithm | |
Explanation: the dynamic programming implementation of the maximum sum rectangle problem uses kadane’s algorithm. |
238. |
Given an array, check if the array can be divided into two subsets such that the sum of elements of the two subsets is equal. This is the balanced partition problem. Which of the following methods can be used to solve the balanced partition problem? |
A. | dynamic programming |
B. | recursion |
C. | brute force |
D. | dynamic programming, recursion, brute force |
Answer» D. dynamic programming, recursion, brute force | |
Explanation: all of the mentioned methods can be used to solve the balanced partition |
239. |
In which of the following cases, it is not possible to have two subsets with equal sum? |
A. | when the number of elements is odd |
B. | when the number of elements is even |
C. | when the sum of elements is odd |
D. | when the sum of elements is even |
Answer» C. when the sum of elements is odd | |
Explanation: when the sum of all the elements is odd, it is not possible to have two subsets with equal sum. |
240. |
What is the time complexity of the brute force algorithm used to solve the balanced partition problem? |
A. | o(1) |
B. | o(n) |
C. | o(n2) |
D. | o(2n) |
Answer» D. o(2n) | |
Explanation: in the brute force implementation, all the possible subsets will be formed. this takes exponential time. |
241. |
What is the sum of each of the balanced partitions for the array {5, 6, 7, 10, 3, 1}? |
A. | 16 |
B. | 32 |
C. | 0 |
D. | 64 |
Answer» A. 16 | |
Explanation: the sum of all the elements of the array is 32. so, the sum of all the elements of each partition should be 16. |
242. |
You are given n dice each having f faces. You have to find the number of ways in which a sum of S can be achieved. This is the dice throw problem. Which of the following methods can be used to solve the dice throw problem? |
A. | brute force |
B. | recursion |
C. | dynamic programming |
D. | brute force, recursion and dynamic programming |
Answer» D. brute force, recursion and dynamic programming | |
Explanation: brute force, recursion and dynamic programming can be used to solve the dice throw problem. |
243. |
You have n dice each having f faces. What is the number of permutations that can be obtained when you roll the n dice together? |
A. | n*n*n…f times |
B. | f*f*f…n times |
C. | n*n*n…n times |
D. | f*f*f…f times |
Answer» B. f*f*f…n times | |
Explanation: each die can take f values and there are n dice. so, the total number of permutations is f*f*f…n times. |
244. |
You have 3 dice each having 6 faces. What is the number of permutations that can be obtained when you roll the 3 dice together? |
A. | 27 |
B. | 36 |
C. | 216 |
D. | 81 |
Answer» C. 216 | |
Explanation: the total number of permutations that can be obtained is 6 * 6 * 6 |
245. |
You have 2 dice each of them having 6 faces numbered from 1 to 6. What is the number of ways in which a sum of 11 can be achieved? |
A. | 0 |
B. | 1 |
C. | 2 |
D. | 3 |
Answer» C. 2 | |
Explanation: the sum of 11 can be achieved when the dice show {6, 5} or {5, 6}. |
246. |
There are n dice with f faces. The faces are numbered from 1 to f. What is the minimum possible sum that can be obtained when the n dice are rolled together? |
A. | 1 |
B. | f |
C. | n |
D. | n*f |
Answer» C. n | |
Explanation: the sum will be minimum when all the faces show a value 1. the sum in this case will be n. |
247. |
There are n dice with f faces. The faces are numbered from 1 to f. What is the maximum possible sum that can be obtained when the n dice are rolled together? |
A. | 1 |
B. | f*f |
C. | n*n |
D. | n*f |
Answer» D. n*f | |
Explanation: the sum will be maximum when all the faces show a value f. the sum in this case will be n*f. |
248. |
There are 10 dice having 5 faces. The faces are numbered from 1 to 5. What is the number of ways in which a sum of 4 can be achieved? |
A. | 0 |
B. | 2 |
C. | 4 |
D. | 8 |
Answer» A. 0 | |
Explanation: since there are 10 dice and the minimum value each die can take is 1, the minimum possible sum is 10. hence, a sum of 4 cannot be achieved. |
249. |
Consider the expression T & F ∧ T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)? |
A. | 0 |
B. | 1 |
C. | 2 |
D. | 3 |
Answer» C. 2 | |
Explanation: the expression can be parenthesized as (t & f) ∧ t or t & (f ∧ t), so that the output is t. |
250. |
Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms? |
A. | n factorial |
B. | n square |
C. | n cube |
D. | nth catalan number |
Answer» D. nth catalan number | |
Explanation: the nth catalan number gives |
Done Studing? Take A Test.
Great job completing your study session! Now it's time to put your knowledge to the test. Challenge yourself, see how much you've learned, and identify areas for improvement. Don’t worry, this is all part of the journey to mastery. Ready for the next step? Take a quiz to solidify what you've just studied.