Dynamic Programming in Data Structures MCQ question and answer with solution

Home / Data Structure / Dynamic Programming In Data Structures

51.
What will be the value stored in arr[5] when the following code is executed?
#include<stdio.h>
int cat_number(int n)
{
     int i,j,arr[n],k;
     arr[0] = 1;
     for(i = 1; i < n; i++)
     {
         arr[i] = 0;
         for(j = 0,k = i - 1; j < i; j++,k--)
          arr[i] += arr[j] * arr[k];
     }
     return arr[n-1];
}
int main()
{
     int ans, n = 10;
     ans = cat_number(n);
     printf("%d\n",ans);
     return 0;
}

Answer & Solution Discuss in Board Save for Later

52.
The recursive formula for Catalan number is given by Cn = ∑Ci*C(n-i).
Consider the following dynamic programming implementation for Catalan numbers:
#include<stdio.h>
int cat_number(int n)
{
     int i,j,arr[n],k;
     arr[0] = 1;
     for(i = 1; i < n; i++)
     {
         arr[i] = 0;
         for(j = 0,k = i - 1; j < i; j++,k--)
           ______________________;
     }
     return arr[n-1];
 
}
int main()
{
     int ans, n = 8;
     ans = cat_number(n);
     printf("%d\n",ans);
     return 0;
}
Which of the following lines completes the above code?

Answer & Solution Discuss in Board Save for Later

54.
Consider the following code snippet. Which property is shown by line 4 of the below code snippet?
1. int sum[len], idx;
2. sum[0] = arr[0];
3. for(idx = 1; idx < len; idx++)
4.	  sum[idx] = max(sum[idx - 1] + arr[idx], arr[idx]);
5. int mx = sum[0];
6. for(idx = 0; idx < len; idx++)
7.	 if(sum[idx] > mx)
8.		mx =sum[idx];
9. return mx;

Answer & Solution Discuss in Board Save for Later

55.
What is the output of the following implementation of Kadane's algorithm?
#include<stdio.h>
int max_num(int a, int b)
{  
      if(a > b)
         return a;
      return b;
}
int kadane_algo(int *arr, int len)	
{
      int ans, sum, idx;
      ans =0;
      sum =0;
      for(idx =0; idx < len; idx++)
      {
	  sum = max_num(0,sum + arr[idx]);
	  ans = max_num(sum,ans);
      }
      return ans;
}
int main()
{
      int arr[] = {-2, -3, -3, -1, -2, -1, -5, -3},len = 8;
      int ans = kadane_algo(arr,len);
      printf("%d",ans);
      return 0;
}

Answer & Solution Discuss in Board Save for Later

56.
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?

Answer & Solution Discuss in Board Save for Later

57.
What is the output of the following code?
#include<stdio.h>
#include<limits.h>
int mat_chain_multiplication(int *mat, int n)
{
     int arr[n][n];
     int i,k,row,col,len;
     for(i=1;i<n;i++)
         arr[i][i] = 0;
     for(len = 2; len < n; len++)
     {
          for(row = 1; row <= n - len + 1; row++)
          {
               col = row + len - 1;
               arr[row][col] = INT_MAX;
               for(k = row; k <= col - 1; k++)
               {
                    int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];
                    if(tmp < arr[row][col])
                    arr[row][col] = tmp;
               }
           }
     }
     return arr[1][n - 1];
}
int main()
{
     int mat[6] = {20,30,40,50};
     int ans = mat_chain_multiplication(mat,4);
     printf("%d",ans);
     return 0;
}

Answer & Solution Discuss in Board Save for Later

58.
Consider the following assembly line problem:
time_to_reach[2][3] = {{17, 2, 7}, {19, 4, 9}}
time_spent[2][4] = {{6, 5, 15, 7}, {5, 10, 11, 4}}
entry_time[2] = {8, 10}
exit_time[2] = {10, 7}
num_of_stations = 4
For the optimal solution, which should be the exit assembly line?

Answer & Solution Discuss in Board Save for Later

59.
Which of the following implementations of Catalan numbers has the largest space complexity(Don't consider the stack space)?

Answer & Solution Discuss in Board Save for Later

Read More Section(Dynamic Programming in Data Structures)

Each Section contains maximum 100 MCQs question on Dynamic Programming in Data Structures. To get more questions visit other sections.