Data Structure II Mock Test 7

10%

Question 1 of 10

1. In dynamic programming, the technique of storing the previously calculated values is called ___________

Memoization

Saving value property

Mapping

Storing value property

Question 1 of 10

Question 2 of 10

2. Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capacity of knapsack=40. Find the maximum value output assuming items to be divisible and nondivisible respectively.

100, 80

130, 110

110, 80

110, 70

Question 2 of 10

Question 3 of 10

3. What will be the recurrence relation of the code of recursive selection sort?

T(n) = 2T(n/2) + c

T(n) = 2T(n/2) + n

T(n) = T(n-1) + c

T(n) = T(n-1) + n

Question 3 of 10

Question 4 of 10

4. Suppose you are given infinite coins of N denominations v1, v2, v3,.....,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the space complexity of a dynamic programming implementation used to solve the coin change problem?

O(N²)

O(S)

O(N)

O(S*N)

Question 4 of 10

Question 5 of 10

5. Which of the following correctly implements iterative code for finding power of a number?

#include <stdio.h> 
int power(int x,  int y) 
{ 
    int res = 1;   
    while (y > 0) 
    { 
        if (y && 1) 
        res = x * x;         
        y = y >> 1; 
        x = x * y;  
    } 
    return res; 
} 
int main() 
{ 
    int x = 3; 
    unsigned int y = 5;   
    printf("%d", power(x, y));   
    return 0; 
}

#include <stdio.h> 
int power(int x,  int y) 
{ 
    int res = 1;   
    while (y > 0) 
    { 
        if (y & 1) 
        res = x * x;         
        y = y >> 1; 
        x = x * y;  
    } 
    return res; 
} 
int main() 
{ 
    int x = 3; 
    unsigned int y = 5;  
    printf("%d", power(x, y));   
    return 0; 
}

#include <stdio.h> 
int power(int x,  int y) 
{ 
    int res = 1;   
    while (y > 0) 
    { 
        
        if (y & 1) 
            res = res * x;         
        y = y >> 1; 
        x = x * x;  
    } 
    return res; 
} 
int main() 
{ 
    int x = 3; 
    unsigned int y = 5;   
    printf("%d", power(x, y));   
    return 0; 
}

#include <stdio.h> 
int power(int x,  int y) 
{ 
    int res = 1;   
    while (y > 0) 
    { 
        
        if (y && 1) 
            res = res * x;         
        y = y >> 1; 
        x = x * x;  
    } 
    return res; 
} 
int main() 
{ 
    int x = 3; 
    unsigned int y = 5;   
    printf("%d", power(x, y));   
    return 0; 
}

Question 5 of 10

Question 6 of 10

6. Consider the following code snippet to find the smallest element in a linked list:

struct Node
{
     int val;
     struct Node* next;
}*head;
int get_min()
{
      struct Node* temp = head->next;
	  int min_num = temp->val;
	  while(temp != 0)
	  {
	       if(_________)
		    min_num = temp->val;
		temp = temp->next;
	  }
	  return min_num;
}

Which of the following lines should be inserted to complete the above code?

temp->val > min_num

val > min_min

temp->val < min_num

temp > min_num

Question 6 of 10

Question 7 of 10

7. Fractional knapsack problem is solved most efficiently by which of the following algorithm?

Dynamic programming

Divide and conquer

Greedy algorithm

Backtracking

Question 7 of 10

Question 8 of 10

8. Consider the following recursive implementation of linear search:

#include<stdio.h>
int recursive_search_num(int *arr, int num, int idx, int len)
{
     if(idx == len)
     return -1;
     if(arr[idx] == num)
       return idx;
     return __________;
}
int main()
{
      int arr[5] ={1,3,3,3,5},num=2,len = 5;
      int indx = recursive_search_num(arr,num,0,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

Which of the following recursive calls should be added to complete the above code?

recursive_search_num(arr, num, idx, len);

recursive_search_num(arr, num+1, idx, len);

recursive_search_num(arr, num, idx+1, len);

recursive_search_num(arr, num+1, idx+1, len);

Question 8 of 10

Question 9 of 10

9. Solve the following recurrence using Master’s theorem.
T(n) = 4T (n/2) + n²

T(n) = O(n)

T(n) = O(n²log n)

T(n) = O(log n)

T(n) = O(n²)

Question 9 of 10

Question 10 of 10

10. What is the objective of the knapsack problem?

To get minimum weight in the knapsack

To get maximum weight in the knapsack

To get minimum total value in the knapsack

To get maximum total value in the knapsack

Question 10 of 10

« Prev - Data Structure II Mock Test 6

» Next - Data Structure II Mock Test 8