{"id":812,"date":"2024-08-23T06:28:50","date_gmt":"2024-08-23T05:28:50","guid":{"rendered":"https:\/\/cyberenlightener.com\/?page_id=812"},"modified":"2024-08-23T08:28:35","modified_gmt":"2024-08-23T07:28:35","slug":"dsa-mcqs","status":"publish","type":"page","link":"https:\/\/cyberenlightener.com\/?page_id=812","title":{"rendered":"DSA MCQs*"},"content":{"rendered":"\n<p><strong>*<em>Some answers may be wrong. This is just for practice purpose only.<\/em><\/strong><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em><strong>Topics : Space and time complexity of an algorithm, Types of asymptotic notations and orders of growth &#8211;<br>Algorithm efficiency \u2013 best case, worst case, average case &#8211;<\/strong><\/em><\/p>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>What is the time complexity of the following function?<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int fun(int n) {\n  int count = 0;\n  for (int i = n; i &gt; 0; i \/= 2)\n     for (int j = 0; j &lt; i; j++)\n        count += 1;\n  return count;\n}<\/code><\/pre>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) O(n^2)<\/li>\n\n\n\n<li><strong>B) O(nLogn)<\/strong><\/li>\n\n\n\n<li>C) O(n)<\/li>\n\n\n\n<li>D) O(nLognLogn)<\/li>\n\n\n\n<li><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>What is the time complexity of the following function?<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int fun(int n) {\n  int count = 0;\n  for (int i = 0; i &lt; n; i++)\n     for (int j = i; j &gt; 0; j--)\n        count = count + 1;\n  return count;\n}<\/code><\/pre>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) Theta(n)<\/li>\n\n\n\n<li><strong>B) Theta(n^2)<\/strong><\/li>\n\n\n\n<li>C) Theta(n*Logn)<\/li>\n\n\n\n<li>D) Theta(nLognLogn)<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) T(n) = 2T(n \u2013 2) + 2<\/li>\n\n\n\n<li>B) T(n) = 2T(n \u2013 1) + n<\/li>\n\n\n\n<li>C) T(n) = 2T(n\/2) + 1<\/li>\n\n\n\n<li><strong>D) T(n) = 2T(n \u2013 1) + 1<\/strong><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>Let w(n) and A(n) denote the worst-case and average-case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) A(n) = \u03a9(W(n))<\/li>\n\n\n\n<li>B) A(n) = \u0398(W(n))<\/li>\n\n\n\n<li><strong>C) A(n) = O(W(n))<\/strong><\/li>\n\n\n\n<li>D) A(n) = o(W(n))<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>Which of the following is not O(n^2)?<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) (15^10) * n + 12099<\/li>\n\n\n\n<li>B) n^1.98<\/li>\n\n\n\n<li><strong>C) n^3 \/ (sqrt(n))<\/strong><\/li>\n\n\n\n<li>D) (2^20) * n<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3, and f4?<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>f1(n) = 2^n\nf2(n) = n^(3\/2)\nf3(n) = nLogn\nf4(n) = n^(Logn)<\/code><\/pre>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>A) f3, f2, f4, f1<\/strong><\/li>\n\n\n\n<li>B) f3, f2, f1, f4<\/li>\n\n\n\n<li>C) f2, f3, f1, f4<\/li>\n\n\n\n<li>D) f2, f3, f4, f1<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = D1D2\u2026Dm<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int n, rev; \nrev = 0; \nwhile (n &gt; 0) {\n   rev = rev * 10 + n % 10; \n   n = n \/ 10; \n}<\/code><\/pre>\n\n\n\n<p>The loop invariant condition at the end of the ith iteration is:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>A) n = D1D2\u2026.Dm-i and rev = DmDm-1\u2026Dm-i+1<\/strong><\/li>\n\n\n\n<li>B) n = Dm-i+1\u2026Dm-1Dm and rev = Dm-1\u2026.D2D1<\/li>\n\n\n\n<li>C) n != rev<\/li>\n\n\n\n<li>D) n = D1D2\u2026.Dm and rev = DmDm-1\u2026D2D1<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>What is the time complexity of the following function?<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>void fun(int n, int arr&#91;]) {\n    int i = 0, j = 0;\n    for(; i &lt; n; ++i)\n        while(j &lt; n &amp;&amp; arr&#91;i] &lt; arr&#91;j])\n            j++;\n}<\/code><\/pre>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) O(n)<\/li>\n\n\n\n<li><strong>B) O(n^2)<\/strong><\/li>\n\n\n\n<li>C) O(nlogn)<\/li>\n\n\n\n<li>D) O(n(logn)^2)<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>In a competition, four different functions are observed. All the functions use a single for loop, and within the for loop, the same set of statements are executed. Consider the following for loops:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) for(i = 0; i &lt; n; i++)<\/li>\n\n\n\n<li>B) for(i = 0; i &lt; n; i += 2)<\/li>\n\n\n\n<li><strong>C) for(i = 1; i &lt; n; i *= 2)<\/strong><\/li>\n\n\n\n<li>D) for(i = n; i &gt; -1; i \/= 2)<\/li>\n<\/ul>\n\n\n\n<p>If n is the size of input (positive), which function is most efficient (if the task to be performed is not an issue)?<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) A<\/li>\n\n\n\n<li>B) B<\/li>\n\n\n\n<li>C) C<\/li>\n\n\n\n<li>D) D<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>The following statement is valid: <code>log(n!) = \u03b8(n log n)<\/code>.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>A) True<\/strong><\/li>\n\n\n\n<li>B) False<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>What does it mean when we say that an algorithm X is asymptotically more efficient than Y?<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) X will be a better choice for all inputs<\/li>\n\n\n\n<li><strong>B) X will be a better choice for all inputs except small inputs<\/strong><\/li>\n\n\n\n<li>C) X will be a better choice for all inputs except large inputs<\/li>\n\n\n\n<li>D) Y will be a better choice for small inputs<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>What is the time complexity of Floyd\u2013Warshall algorithm to calculate all pairs&#8217; shortest path in a graph with n vertices?<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) O(n^2logn)<\/li>\n\n\n\n<li>B) Theta(n^2logn)<\/li>\n\n\n\n<li>C) Theta(n^4)<\/li>\n\n\n\n<li><strong>D) Theta(n^3)<\/strong><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>Consider the following functions:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>f(n) = 2^n\ng(n) = n!\nh(n) = n^logn <\/code><\/pre>\n\n\n\n<p>Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true?<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) f(n) = O(g(n)); g(n) = O(h(n))<\/li>\n\n\n\n<li>B) f(n) = \u03a9(g(n)); g(n) = O(h(n))<\/li>\n\n\n\n<li><strong>C) g(n) = O(f(n)); h(n) = O(f(n))<\/strong><\/li>\n\n\n\n<li>D) h(n) = O(f(n)); g(n) = \u03a9(f(n))<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>In the following C function, let n &gt;= m.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int gcd(n,m) {\n  if (n % m == 0) return m;  \n  n = n % m;\n  return gcd(m, n);\n}<\/code><\/pre>\n\n\n\n<p>How many recursive calls are made by this function?<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>A) \u03b8(logn)<\/strong><\/li>\n\n\n\n<li>B) \u03a9(n)<\/li>\n\n\n\n<li>C) \u03b8(loglogn)<\/li>\n\n\n\n<li>D) \u03b8(sqrt(n))<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>Consider the following C-program fragment in which i, j, and n are integer variables.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>for (i = n, j = 0; i &gt; 0; i \/= 2, j += i);<\/code><\/pre>\n\n\n\n<p>Let val(j) denote the value stored in the variable j after the termination of the for loop. Which one of the following is true?<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) val(j) = \u03b8(logn)<\/li>\n\n\n\n<li>B) val(j) = \u03b8(sqrt(n))<\/li>\n\n\n\n<li>C) val(j) = \u03b8(n)<\/li>\n\n\n\n<li><strong>D) val(j) = \u03b8(nlogn)<\/strong><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) 147.1 to 148.1<\/li>\n\n\n\n<li>B) 145.1 to 146.1<\/li>\n\n\n\n<li><strong>C) 140 to 146<\/strong><\/li>\n\n\n\n<li>D) 140 to 148<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>Consider the following pseudo-code. What is the total number of multiplications to be performed?<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>D = 2\nfor (i = 1 to n)\n   for (j = i to n)\n      for (k = j + 1 to n)\n           D = D * 3 <\/code><\/pre>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) Half of the product of the 3 consecutive integers.<\/li>\n\n\n\n<li>B) One-third of the product of the 3 consecutive integers.<\/li>\n\n\n\n<li><strong>C) One-sixth of the product of the 3 consecutive integers.<\/strong><\/li>\n\n\n\n<li>D) None of the above.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>Consider the following C-function:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>double foo(int n) {\n    int i;\n    double sum;\n    if (n == 0) return 1.0;\n    else {\n        sum = 0.0;\n        for (i = 0; i &lt; n; i++)\n            sum += foo(i);\n        return sum;\n    }\n}<\/code><\/pre>\n\n\n\n<p>The space complexity of the above function is:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) O(1)<\/li>\n\n\n\n<li>B) O(n)<\/li>\n\n\n\n<li>C) O(n!)<\/li>\n\n\n\n<li><strong>D) O(nn)<\/strong><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><\/p>\n\n\n\n<p>Consider the following C-function:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>double foo(int n) {\n    int i;\n    double sum;\n    if (n == 0) return 1.0;\n    else {\n        sum = 0.0;\n        for (i = 0; i &lt; n; i++)\n            sum += foo(i);\n        return sum;\n    }\n}<\/code><\/pre>\n\n\n\n<p>Suppose we modify the above function <code>foo()<\/code> and store the values of <code>foo(i)<\/code>, 0 &lt;= i &lt; n, as and when they are computed. With this modification, the time complexity for function <code>foo()<\/code> is significantly reduced. The space complexity of the modified function would be:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A) O(1)<\/li>\n\n\n\n<li><strong>B) O(n)<\/strong><\/li>\n\n\n\n<li>C) O(n!)<\/li>\n\n\n\n<li>D) O(n^2)<\/li>\n<\/ul>\n\n\n\n<p><strong><em>Topics: Asymptotic analysis for recurrence relation: Iteration Method,Substitution Method, Master Method and Recursive Tree Method.<\/em><\/strong><\/p>\n\n\n\n<p><strong>Question:<\/strong><br>Which of the following methods is most suitable for solving simple divide-and-conquer recurrences?<br>A) Iteration Method<br>B) Substitution Method<br>C) Master Method<br>D) Recursive Tree Method<br><strong>Answer:<\/strong> C) Master Method<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>The recurrence ( T(n) = 2T(n\/2) + n ) can be solved using the Master Theorem. What is the time complexity of this recurrence?<br>A) O(n)<br>B) O(n log n)<br>C) O(n^2)<br>D) O(log n)<br><strong>Answer:<\/strong> B) O(n log n)<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>Which method involves guessing the solution and then proving it by mathematical induction?<br>A) Iteration Method<br>B) Substitution Method<br>C) Master Method<br>D) Recursive Tree Method<br><strong>Answer:<\/strong> B) Substitution Method<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>For the recurrence ( T(n) = 3T(n\/4) + n ), which case of the Master Theorem applies?<br>A) Case 1<br>B) Case 2<br>C) Case 3<br>D) None of the above<br><strong>Answer:<\/strong> C) Case 3<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>In the Iteration Method, after expanding the recurrence, what is the next step to find the time complexity?<br>A) Solve the base case<br>B) Use the Master Theorem<br>C) Express the expanded terms as a summation<br>D) Substitute the guessed solution<br><strong>Answer:<\/strong> C) Express the expanded terms as a summation<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>Which of the following recurrence relations can be solved using the Iteration Method?<br>A) ( T(n) = 2T(n\/2) + n )<br>B) ( T(n) = T(n-1) + 1 )<br>C) ( T(n) = 3T(n\/4) + n )<br>D) All of the above<br><strong>Answer:<\/strong> D) All of the above<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>The Recursive Tree Method is particularly useful for:<br>A) Estimating the growth of a recursive algorithm<br>B) Finding an exact solution to a recurrence<br>C) Solving linear recurrences<br>D) Proving the correctness of an algorithm<br><strong>Answer:<\/strong> A) Estimating the growth of a recursive algorithm<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>Which of the following is NOT a valid approach for solving recurrences?<br>A) Guess-and-check Method<br>B) Substitution Method<br>C) Iteration Method<br>D) Substitution Master Method<br><strong>Answer:<\/strong> D) Substitution Master Method<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>The recurrence ( T(n) = T(n\/2) + T(n\/4) + n ) is best solved using:<br>A) Iteration Method<br>B) Substitution Method<br>C) Master Method<br>D) Recursive Tree Method<br><strong>Answer:<\/strong> D) Recursive Tree Method<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>When solving a recurrence relation using the Substitution Method, what is the most important step?<br>A) Expanding the recurrence<br>B) Making a good guess<br>C) Summing the series<br>D) Applying the Master Theorem<br><strong>Answer:<\/strong> B) Making a good guess<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>What is the correct asymptotic complexity for the recurrence ( T(n) = 4T(n\/2) + n )?<br>A) O(n^2)<br>B) O(n log n)<br>C) O(n^3)<br>D) O(log n)<br><strong>Answer:<\/strong> A) O(n^2)<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>The recurrence ( T(n) = T(n\/2) + n^2 ) falls under which case of the Master Theorem?<br>A) Case 1<br>B) Case 2<br>C) Case 3<br>D) Case 4<br><strong>Answer:<\/strong> C) Case 3<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>In the Iteration Method, if a recurrence has ( T(n) = 2T(n\/2) + 1 ), what is the total number of levels in the expansion tree?<br>A) log n<br>B) n<br>C) n\/2<br>D) 2n<br><strong>Answer:<\/strong> A) log n<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>Which of the following recurrences is most likely to result in a logarithmic time complexity?<br>A) ( T(n) = 2T(n\/2) + n )<br>B) ( T(n) = T(n\/2) + 1 )<br>C) ( T(n) = 3T(n\/4) + n^2 )<br>D) ( T(n) = 2T(n\/2) + n^2 )<br><strong>Answer:<\/strong> B) ( T(n) = T(n\/2) + 1 )<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>The Master Method is applicable when the recurrence has the form:<br>A) ( T(n) = aT(n\/b) + f(n) )<br>B) ( T(n) = T(n-1) + T(n-2) )<br>C) ( T(n) = T(n\/2) + n )<br>D) ( T(n) = T(n-1) + 1 )<br><strong>Answer:<\/strong> A) ( T(n) = aT(n\/b) + f(n) )<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>For the recurrence ( T(n) = 2T(n\/2) + n ), using the Master Theorem, what is the value of the critical exponent ( \\log_b a )?<br>A) 1<br>B) 2<br>C) 0.5<br>D) log n<br><strong>Answer:<\/strong> A) 1<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>The Substitution Method typically involves which of the following steps?<br>A) Expanding the recurrence into a tree<br>B) Expressing the solution as a summation<br>C) Guessing the form of the solution and using induction to verify<br>D) Applying the Master Theorem<br><strong>Answer:<\/strong> C) Guessing the form of the solution and using induction to verify<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>The Recursive Tree Method visualizes the recurrence by representing it as:<br>A) A series of nested recurrences<br>B) A tree where nodes represent subproblems<br>C) A sequence of iterations<br>D) A single linear equation<br><strong>Answer:<\/strong> B) A tree where nodes represent subproblems<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>The recurrence ( T(n) = 2T(n\/2) + n ) is classified under which case of the Master Theorem?<br>A) Case 1<br>B) Case 2<br>C) Case 3<br>D) Case 4<br><strong>Answer:<\/strong> B) Case 2<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>For the recurrence ( T(n) = T(n-1) + n ), the Iteration Method would typically involve:<br>A) Expanding each term iteratively until the base case<br>B) Using the Master Theorem to find the solution<br>C) Guessing the solution and using induction<br>D) Drawing a recursive tree<br><strong>Answer:<\/strong> A) Expanding each term iteratively until the base case<\/p>\n\n\n\n<p><strong><em>Topics : Arrays: 1D and 2D array- Stack &#8211; Applications of stack: Expression Evaluation, Conversion, of Infix to postfix and prefix expression, Tower of Hanoi<\/em><\/strong><\/p>\n\n\n\n<p><strong>Question:<\/strong><br>Which of the following operations is not possible on a static array once it is declared?<br>A) Accessing an element using its index<br>B) Inserting an element at a specific position<br>C) Deleting an element from a specific position<br>D) Resizing the array<br><strong>Answer:<\/strong> D) Resizing the array<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>If an array <code>A<\/code> is defined as <code>int A[10] = {0};<\/code>, what will be the value of <code>A[5]<\/code>?<br>A) 0<br>B) 5<br>C) Undefined<br>D) Compilation error<br><strong>Answer:<\/strong> A) 0<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>What is the time complexity of searching for an element in a sorted 1D array using binary search?<br>A) O(n)<br>B) O(n^2)<br>C) O(log n)<br>D) O(1)<br><strong>Answer:<\/strong> C) O(log n)<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>Which of the following is true about a stack?<br>A) It follows FIFO (First-In-First-Out) order<br>B) It allows insertion and deletion from both ends<br>C) It follows LIFO (Last-In-First-Out) order<br>D) It allows random access to elements<br><strong>Answer:<\/strong> C) It follows LIFO (Last-In-First-Out) order<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>In which of the following scenarios would you prefer to use a stack over other data structures?<br>A) Implementing a queue<br>B) Performing level-order traversal of a tree<br>C) Evaluating arithmetic expressions<br>D) Storing records in a database<br><strong>Answer:<\/strong> C) Evaluating arithmetic expressions<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>Which of the following is the correct postfix expression for the infix expression <code>A + B * C<\/code>?<br>A) <code>ABC*+<\/code><br>B) <code>AB+C*<\/code><br>C) <code>A*BC+<\/code><br>D) <code>AB*C+<\/code><br><strong>Answer:<\/strong> A) <code>ABC*+<\/code><\/p>\n\n\n\n<p><strong>Question:<\/strong><br>Given a stack with an initial state of empty, what will be the stack after the following operations: <code>push(1)<\/code>, <code>push(2)<\/code>, <code>pop()<\/code>, <code>push(3)<\/code>?<br>A) 3, 2, 1<br>B) 1, 2, 3<br>C) 1, 3<br>D) 3, 1<br><strong>Answer:<\/strong> C) 1, 3<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>Which of the following is NOT an application of a stack?<br>A) Parsing expressions<br>B) Function call management in recursion<br>C) Breadth-first search in a graph<br>D) Balancing parentheses in an expression<br><strong>Answer:<\/strong> C) Breadth-first search in a graph<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>In the Tower of Hanoi problem with 3 disks, what is the minimum number of moves required to solve the problem?<br>A) 3<br>B) 5<br>C) 7<br>D) 9<br><strong>Answer:<\/strong> C) 7<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>What is the time complexity for the conversion of an infix expression to a postfix expression using a stack?<br>A) O(n)<br>B) O(n log n)<br>C) O(n^2)<br>D) O(1)<br><strong>Answer:<\/strong> A) O(n)<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>Consider an array <code>arr<\/code> of size <code>n<\/code>. What is the best-case time complexity for finding the maximum element in this array?<br>A) O(n^2)<br>B) O(n log n)<br>C) O(n)<br>D) O(1)<br><strong>Answer:<\/strong> C) O(n)<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>What is the postfix form of the infix expression <code>(A + B) * (C + D)<\/code>?<br>A) <code>AB+CD+*<\/code><br>B) <code>ABCD+*+<\/code><br>C) <code>A+B*C+D+<\/code><br>D) <code>AB+*CD+<\/code><br><strong>Answer:<\/strong> A) <code>AB+CD+*<\/code><\/p>\n\n\n\n<p><strong>Question:<\/strong><br>In an array of size <code>n<\/code>, if elements are inserted one after another, what is the worst-case time complexity for inserting an element at the beginning of the array?<br>A) O(1)<br>B) O(log n)<br>C) O(n)<br>D) O(n log n)<br><strong>Answer:<\/strong> C) O(n)<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>How many stacks are required to evaluate a postfix expression?<br>A) One<br>B) Two<br>C) Three<br>D) None<br><strong>Answer:<\/strong> A) One<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>What will be the content of the stack after converting the infix expression <code>A * (B + C) \/ D<\/code> to postfix?<br>A) <code>AB+C*D\/<\/code><br>B) <code>ABC+*D\/<\/code><br>C) <code>AB+C*D\/<\/code><br>D) <code>ABC*D+\/<\/code><br><strong>Answer:<\/strong> B) <code>ABC+*D\/<\/code><\/p>\n\n\n\n<p><strong>Question:<\/strong><br>In a stack, which operation removes the top element of the stack?<br>A) Push<br>B) Pop<br>C) Peek<br>D) Insert<br><strong>Answer:<\/strong> B) Pop<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>What is the time complexity of finding the middle element in a stack implemented using a linked list?<br>A) O(1)<br>B) O(log n)<br>C) O(n)<br>D) O(n log n)<br><strong>Answer:<\/strong> C) O(n)<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>In a 2D array, how do you calculate the address of an element at row <code>i<\/code> and column <code>j<\/code> given that the array is stored in row-major order?<br>A) Base address + <code>(i * number of columns + j)<\/code> * size of element<br>B) Base address + <code>(j * number of rows + i)<\/code> * size of element<br>C) Base address + <code>(i + j)<\/code> * size of element<br>D) Base address + <code>(i * j)<\/code> * size of element<br><strong>Answer:<\/strong> A) Base address + <code>(i * number of columns + j)<\/code> * size of element<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>For the infix expression <code>A + B * (C - D)<\/code>, what is the equivalent prefix expression?<br>A) <code>+A*B-CD<\/code><br>B) <code>*AB-CD+<\/code><br>C) <code>*+AB-CD<\/code><br>D) <code>+A*B-CD<\/code><br><strong>Answer:<\/strong> D) <code>+A*B-CD<\/code><\/p>\n\n\n\n<p><strong>Question:<\/strong><br>What is the maximum number of elements that can be present in a stack of size <code>n<\/code>?<br>A) n+1<br>B) n<br>C) n-1<br>D) n^2<br><strong>Answer:<\/strong> B) n<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>In the Tower of Hanoi problem with <code>n<\/code> disks, how does the time complexity of the solution change with respect to <code>n<\/code>?<br>A) O(2^n)<br>B) O(n^2)<br>C) O(n log n)<br>D) O(n)<br><strong>Answer:<\/strong> A) O(2^n)<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>What is the minimum number of moves required to solve the Tower of Hanoi problem for <code>n<\/code> disks?<br>A) 2n &#8211; 1<br>B) 2^n &#8211; 1<br>C) 2n^2 &#8211; 1<br>D) 2^n + 1<br><strong>Answer:<\/strong> B) 2^n &#8211; 1<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>In which of the following scenarios is a circular queue more advantageous than a regular queue?<br>A) When the queue is full<br>B) When implementing a stack<br>C) When dealing with fixed-size arrays<br>D) When reusing space that is freed after dequeuing<br><strong>Answer:<\/strong> D) When reusing space that is freed after dequeuing<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>What will be the stack content after evaluating the postfix expression <code>3 4 + 2 * 7 \/<\/code>?<br>A) 14<br>B) 2<br>C) 7<br>D) 4<br><strong>Answer:<\/strong> B) 2<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>Which of the following expressions correctly converts the infix expression <code>A \/ B + C * D - E<\/code> to postfix?<br>A) <code>AB\/CD*+E-<\/code><br>B) <code>AB\/CD*E+-<\/code><br>C) <code>AB\/C*DE+-<\/code><br>D) <code>AB\/C+D*E-<\/code><br><strong>Answer:<\/strong> D) <code>AB\/C+D*E-<\/code><\/p>\n\n\n\n<p><strong>Question:<\/strong><br>Consider the operator precedence and associativity rules for the integer arithmetic operators given in the table below:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Operator<\/th><th>Precedence<\/th><th>Associativity<\/th><\/tr><\/thead><tbody><tr><td>+<\/td><td>Highest<\/td><td>Left<\/td><\/tr><tr><td>\u2212<\/td><td>High<\/td><td>Right<\/td><\/tr><tr><td>*<\/td><td>Medium<\/td><td>Right<\/td><\/tr><tr><td>\/<\/td><td>Low<\/td><td>Right<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Given these rules, what is the value of the expression <code>3 + 5 * 2 - 4 \/ 2<\/code>?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br>The value of the expression is <strong>12<\/strong>.<\/p>\n\n\n\n<p><strong>Explanation:<\/strong><br>According to the precedence and associativity:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Multiplication (*) is performed first: <code>5 * 2 = 10<\/code>.<\/li>\n\n\n\n<li>Division (\/) is next: <code>4 \/ 2 = 2<\/code>.<\/li>\n\n\n\n<li>Addition (+) and subtraction (\u2212) are then evaluated from left to right:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>3 + 10 = 13<\/code><\/li>\n\n\n\n<li><code>13 - 2 = 11<\/code><\/li>\n<\/ul>\n\n\n\n<p><strong>Final Result:<\/strong> 11<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is correct (n refers to the number of items in the queue)?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br>In an array-based queue, both ENQUEUE and DEQUEUE operations can be performed in <strong>O(1)<\/strong> time, provided the array is used in a circular manner.<\/p>\n\n\n\n<p><strong>Explanation:<\/strong><br>If the queue is implemented in a circular fashion using an array, ENQUEUE (adding an element to the end) and DEQUEUE (removing an element from the front) can be efficiently handled without shifting elements, thus operating in constant time.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>The result of evaluating the postfix expression <code>6 2 3 * - 4 2 \/ +<\/code> is:<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br>The result is <strong>4<\/strong>.<\/p>\n\n\n\n<p><strong>Explanation:<\/strong><br>To evaluate the postfix expression:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Multiply 2 and 3: <code>6<\/code>.<\/li>\n\n\n\n<li>Subtract this result from 6: <code>6 - 6 = 0<\/code>.<\/li>\n\n\n\n<li>Divide 4 by 2: <code>2<\/code>.<\/li>\n\n\n\n<li>Add the results from steps 2 and 3: <code>0 + 2 = 2<\/code>.<\/li>\n<\/ol>\n\n\n\n<p><strong>Final Result:<\/strong> 2<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>A function <code>f<\/code> defined on stacks of integers satisfies the following properties: <code>f(\u2205) = 0<\/code> and <code>f(push(S, i)) = max(f(S), 0) + i<\/code> for all stacks <code>S<\/code> and integers <code>i<\/code>. If a stack <code>S<\/code> contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is <code>f(S)<\/code>?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br>The value of <code>f(S)<\/code> is <strong>5<\/strong>.<\/p>\n\n\n\n<p><strong>Explanation:<\/strong><br>Evaluating <code>f(S)<\/code> step by step:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Start with an empty stack: <code>f(\u2205) = 0<\/code>.<\/li>\n\n\n\n<li>Push 2: <code>f(push(\u2205, 2)) = max(0, 0) + 2 = 2<\/code>.<\/li>\n\n\n\n<li>Push -3: <code>f(push(S, -3)) = max(2, 0) - 3 = 2 - 3 = -1<\/code>.<\/li>\n\n\n\n<li>Push 2: <code>f(push(S, 2)) = max(-1, 0) + 2 = 0 + 2 = 2<\/code>.<\/li>\n\n\n\n<li>Push -1: <code>f(push(S, -1)) = max(2, 0) - 1 = 2 - 1 = 1<\/code>.<\/li>\n\n\n\n<li>Push 2: <code>f(push(S, 2)) = max(1, 0) + 2 = 1 + 2 = 3<\/code>.<\/li>\n<\/ol>\n\n\n\n<p><strong>Final Result:<\/strong> 3<\/p>\n\n\n\n<p><strong>Question:<\/strong><br>Which of the following is the correct way to access the third element of a one-dimensional array <code>arr<\/code>?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br><code>arr[2]<\/code><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>In a 2D array <code>matrix[4][5]<\/code>, how do you access the element in the first row and fourth column?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br><code>matrix[0][3]<\/code><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>What data structure is typically used to evaluate postfix expressions?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br>Stack<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>What is the postfix notation for the infix expression <code>A - B + C<\/code>?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br><code>A B - C +<\/code><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>Which of the following correctly represents the infix expression <code>(A + B) * (C - D)<\/code> in prefix notation?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br><code>* + A B - C D<\/code><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>What is the correct postfix notation for the expression <code>(A + B) * (C - D) \/ E<\/code>?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br><code>A B + C D - * E \/<\/code><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>In the Tower of Hanoi problem, how many moves are needed to solve the puzzle for 3 disks?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br>7<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>Given the postfix expression <code>5 1 2 + 4 * + 3 -<\/code>, what is the result of the expression?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br>14<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>Which operation in a stack removes the top element?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br>POP<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>In the context of stack operations, what does the PUSH operation do?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br>Adds an element to the top of the stack<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>What is the result of the infix expression <code>A + B * C<\/code> when converted to postfix notation?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br><code>A B C * +<\/code><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>Which operation is used to add an element to the stack?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br>PUSH<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>When converting the infix expression <code>A + (B - C) * D<\/code> to prefix notation, what is the result?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br><code>+ A * - B C D<\/code><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>How do you represent the infix expression <code>A \/ (B + C)<\/code> in postfix notation?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br><code>A B C + \/<\/code><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>What is the correct prefix notation for the expression <code>A * (B + C) - D<\/code>?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br><code>- * A + B C D<\/code><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>What is the result of the postfix expression <code>8 2 \/ 4 5 * +<\/code>?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br>14<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>In a stack, which operation retrieves the top element without removing it?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br>PEEK<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>What is the minimum number of moves required to solve the Tower of Hanoi problem with 4 disks?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br>15<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>In the conversion of an infix expression to postfix notation, when should operators be popped from the stack?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br>When encountering an operator with lower or equal precedence than the one on the stack<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>Which of the following is the result of converting the infix expression <code>A - B \/ C * D<\/code> to postfix notation?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br><code>A B C D * \/ -<\/code><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>In prefix notation, what is the equivalent of the infix expression <code>A - (B \/ C * D)<\/code>?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br><code>- A \/ B * C D<\/code><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Question:<\/strong><br>In a 2D array, how is the element in the second row and fifth column accessed?<\/p>\n\n\n\n<p><strong>Answer:<\/strong><br><code>array[1][4]<\/code><\/p>\n\n\n\n<p><strong><em>Topics : Searching and Sorting<\/em><\/strong><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Which of the following is true about linear search?<\/strong><\/p>\n\n\n\n<p>a) It requires the list to be sorted.<\/p>\n\n\n\n<p>b) It has a time complexity of O(log n).<\/p>\n\n\n\n<p>c) It can be used on both sorted and unsorted lists.<\/p>\n\n\n\n<p>d) It performs better than binary search for large datasets.<\/p>\n\n\n\n<p><strong>Answer:<\/strong> c) It can be used on both sorted and unsorted lists.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Consider a sorted array of 1000 elements. What is the worst-case time complexity of binary search?<\/strong><\/p>\n\n\n\n<p>a) O(1)<\/p>\n\n\n\n<p>b) O(n)<\/p>\n\n\n\n<p>c) O(log n)<\/p>\n\n\n\n<p>d) O(n log n)<\/p>\n\n\n\n<p><strong>Answer:<\/strong> c) O(log n)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Given a list of 100 elements, what is the maximum number of comparisons required by a binary search?<\/strong><\/p>\n\n\n\n<p>a) 7<\/p>\n\n\n\n<p>b) 10<\/p>\n\n\n\n<p>c) 20<\/p>\n\n\n\n<p>d) 100<\/p>\n\n\n\n<p><strong>Answer:<\/strong> b) 10<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>In the context of linear search, if an element is present in the middle of a list of size <code>n<\/code>, how many comparisons are required on average?<\/strong><\/p>\n\n\n\n<p>a) n\/2<\/p>\n\n\n\n<p>b) n<\/p>\n\n\n\n<p>c) log(n)<\/p>\n\n\n\n<p>d) (n+1)\/2<\/p>\n\n\n\n<p><strong>Answer:<\/strong> d) (n+1)\/2<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Which of the following searching algorithms would be the most efficient for an unsorted list of size 1,000,000?<\/strong><\/p>\n\n\n\n<p>a) Linear search<\/p>\n\n\n\n<p>b) Binary search<\/p>\n\n\n\n<p>c) Hashing<\/p>\n\n\n\n<p>d) Interpolation search<\/p>\n\n\n\n<p><strong>Answer:<\/strong> c) Hashing<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Which of the following sorting algorithms has the worst-case time complexity of O(n^2) and is stable?<\/strong><\/p>\n\n\n\n<p>a) Insertion sort<\/p>\n\n\n\n<p>b) Selection sort<\/p>\n\n\n\n<p>c) Bubble sort<\/p>\n\n\n\n<p>d) Merge sort<\/p>\n\n\n\n<p><strong>Answer:<\/strong> a) Insertion sort<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>In which sorting algorithm does the worst-case performance occur when the list is already sorted or nearly sorted?<\/strong><\/p>\n\n\n\n<p>a) Selection sort<\/p>\n\n\n\n<p>b) Insertion sort<\/p>\n\n\n\n<p>c) Bubble sort<\/p>\n\n\n\n<p>d) Quick sort<\/p>\n\n\n\n<p><strong>Answer:<\/strong> b) Insertion sort<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>What is the average-case time complexity of Bubble Sort?<\/strong><\/p>\n\n\n\n<p>a) O(n)<\/p>\n\n\n\n<p>b) O(n log n)<\/p>\n\n\n\n<p>c) O(n^2)<\/p>\n\n\n\n<p>d) O(log n)<\/p>\n\n\n\n<p><strong>Answer:<\/strong> c) O(n^2)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Which sorting algorithm repeatedly selects the minimum element from the unsorted part and moves it to the end of the sorted part?<\/strong><\/p>\n\n\n\n<p>a) Bubble sort<\/p>\n\n\n\n<p>b) Selection sort<\/p>\n\n\n\n<p>c) Insertion sort<\/p>\n\n\n\n<p>d) Merge sort<\/p>\n\n\n\n<p><strong>Answer:<\/strong> b) Selection sort<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Which of the following sorting algorithms performs the minimum number of swaps in the worst case?<\/strong><\/p>\n\n\n\n<p>a) Bubble sort<\/p>\n\n\n\n<p>b) Selection sort<\/p>\n\n\n\n<p>c) Insertion sort<\/p>\n\n\n\n<p>d) Quick sort<\/p>\n\n\n\n<p><strong>Answer:<\/strong> b) Selection sort<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>For which of the following scenarios is binary search most efficient?<\/strong><\/p>\n\n\n\n<p>a) Searching in a linked list.<\/p>\n\n\n\n<p>b) Searching in a small, unsorted array.<\/p>\n\n\n\n<p>c) Searching in a large, sorted array.<\/p>\n\n\n\n<p>d) Searching in a large, unsorted array.<\/p>\n\n\n\n<p><strong>Answer:<\/strong> c) Searching in a large, sorted array.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>In a binary search tree (BST), which of the following traversal methods would yield the elements in ascending order?<\/strong><\/p>\n\n\n\n<p>a) Pre-order traversal<\/p>\n\n\n\n<p>b) In-order traversal<\/p>\n\n\n\n<p>c) Post-order traversal<\/p>\n\n\n\n<p>d) Level-order traversal<\/p>\n\n\n\n<p><strong>Answer:<\/strong> b) In-order traversal<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>What is the best-case time complexity of bubble sort when the input list is already sorted?<\/strong><\/p>\n\n\n\n<p>a) O(n)<\/p>\n\n\n\n<p>b) O(n log n)<\/p>\n\n\n\n<p>c) O(n^2)<\/p>\n\n\n\n<p>d) O(log n)<\/p>\n\n\n\n<p><strong>Answer:<\/strong> a) O(n)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>In a worst-case scenario, how many comparisons are needed to sort a list of <code>n<\/code> elements using insertion sort?<\/strong><\/p>\n\n\n\n<p>a) n<\/p>\n\n\n\n<p>b) n log n<\/p>\n\n\n\n<p>c) n^2<\/p>\n\n\n\n<p>d) n^2\/2<\/p>\n\n\n\n<p><strong>Answer:<\/strong> c) n^2<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>For a list of size <code>n<\/code>, what is the maximum number of swaps performed by selection sort?<\/strong><\/p>\n\n\n\n<p>a) n<\/p>\n\n\n\n<p>b) n-1<\/p>\n\n\n\n<p>c) n^2<\/p>\n\n\n\n<p>d) (n-1)^2<\/p>\n\n\n\n<p><strong>Answer:<\/strong> b) n-1<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Which sorting algorithm uses a divide-and-conquer strategy and is known for its O(n log n) average and worst-case time complexity?<\/strong><\/p>\n\n\n\n<p>a) Merge sort<\/p>\n\n\n\n<p>b) Bubble sort<\/p>\n\n\n\n<p>c) Insertion sort<\/p>\n\n\n\n<p>d) Selection sort<\/p>\n\n\n\n<p><strong>Answer:<\/strong> a) Merge sort<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>What is the space complexity of the in-place version of the quick sort algorithm?<\/strong><\/p>\n\n\n\n<p>a) O(n)<\/p>\n\n\n\n<p>b) O(log n)<\/p>\n\n\n\n<p>c) O(n log n)<\/p>\n\n\n\n<p>d) O(1)<\/p>\n\n\n\n<p><strong>Answer:<\/strong> b) O(log n)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>If a list is sorted using quick sort with a poorly chosen pivot each time, what is the worst-case time complexity?<\/strong><\/p>\n\n\n\n<p>a) O(n log n)<\/p>\n\n\n\n<p>b) O(n)<\/p>\n\n\n\n<p>c) O(n^2)<\/p>\n\n\n\n<p>d) O(n^3)<\/p>\n\n\n\n<p><strong>Answer:<\/strong> c) O(n^2)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>In a list sorted by insertion sort, how many elements need to be compared in the worst case when inserting a new element?<\/strong><\/p>\n\n\n\n<p>a) 1<\/p>\n\n\n\n<p>b) n\/2<\/p>\n\n\n\n<p>c) n<\/p>\n\n\n\n<p>d) log(n)<\/p>\n\n\n\n<p><strong>Answer:<\/strong> c) n<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Which of the following is NOT a stable sorting algorithm?<\/strong><\/p>\n\n\n\n<p>a) Merge sort<\/p>\n\n\n\n<p>b) Bubble sort<\/p>\n\n\n\n<p>c) Insertion sort<\/p>\n\n\n\n<p>d) Selection sort<\/p>\n\n\n\n<p><strong>Answer:<\/strong> d) Selection sort<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>*Some answers may be wrong. This is just for practice purpose only. Topics : Space and time complexity of an algorithm, Types of asymptotic notations and orders of growth &#8211;Algorithm efficiency \u2013 best case, worst case, average case &#8211; Question: What is the time complexity of the following function? Question: What is the time complexity [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"class_list":["post-812","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/812","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=812"}],"version-history":[{"count":9,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/812\/revisions"}],"predecessor-version":[{"id":832,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/812\/revisions\/832"}],"wp:attachment":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=812"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}