Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages
Filter by Categories
nmims post
Objective Type Set
Online MCQ Assignment
Question Solution
Solved Question
Uncategorized

Multiple choice question for engineering

Set 1

1. 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) All of the mentioned

View Answer

Answer: d [Reason:] All of the mentioned methods can be used to solve the dice throw problem.

2. 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

View Answer

Answer: b [Reason:] Each die can take f values and there are n dice. So, the total number of permutations is f*f*f…n times.

3. 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

View Answer

Answer: c [Reason:] The total number of permutations that can be obtained is 6 * 6 * 6 = 216.

4. 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

View Answer

Answer: c [Reason:] The sum of 11 can be achieved when the dice show {6, 5} or {5, 6}.

5. 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) none of the mentioned

View Answer

Answer: c [Reason:] The sum will be minimum when all the faces show a value 1. The sum in this case will be n.

6. 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

View Answer

Answer: d [Reason:] The sum will be maximum when all the faces show a value f. The sum in this case will be n*f.

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

View Answer

Answer: a [Reason:] 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.

8. Consider the following dynamic programming implementation of the dice throw problem:

#include<stdio.h>
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{ 
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return _____________;
}
int main()
{
int num_of_dice = 3, num_of_faces = 4, sum = 6;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}

Which of the following lines should be added to complete the above code?
a) arr[num_of_dice][S].
b) arr[dice][sm].
c) arr[dice][S].
d) none of the mentioned

View Answer

Answer: a [Reason:] The line arr[num_of_dice][S] completes the above code.

9. What is time complexity of the above dynamic programming implementation of the dice throw problem where f is the number of faces, n is the number of dice and s is the sum to be found?
a) O(n*f)
b) O(f*s)
c) O(n*s)
d) O(n*f*s)

View Answer

Answer: d [Reason:] The time complexity of the above dynamic programming implementation is O(n*f*s).

10. What is space complexity of the above dynamic programming implementation of the dice throw problem where f is the number of faces, n is the number of dice and s is the sum to be found?
a) O(n*f)
b) O(f*s)
c) O(n*s)
d) O(n*f*s)

View Answer

Answer: c [Reason:] The space complexity of the above dynamic programming implementation is O(n*s).

11. What is the output of the following code?

#include<stdio.h>
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return arr[num_of_dice][S];
}
int main()
{
int num_of_dice = 3, num_of_faces = 4, sum = 6;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}

a) 10
b) 12
c) 14
d) 16

View Answer

Answer: a [Reason:] The output of the above code is 10.

12. What will be the value stored in arr[2][2] when the following code is executed?

#include<stdio.h>
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return arr[num_of_dice][S];
}
int main()
{
int num_of_dice = 3, num_of_faces = 4, sum = 6;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}

a) 0
b) 1
c) 2
d) 3

View Answer

Answer: b [Reason:] The value stored in arr[2][2] is 1.

13. What is the output of the following code?

#include<stdio.h>
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return arr[num_of_dice][S];
}
int main()
{
int num_of_dice = 4, num_of_faces = 6, sum = 3;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}

a) 0
b) 1
c) 2
d) 3

View Answer

Answer: a [Reason:] The minimum possible sum is 4. So, the output for sum = 3 is 0.

14. What is the output of the following code?

#include<stdio.h>
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return arr[num_of_dice][S];
}
int main()
{
int num_of_dice = 2, num_of_faces = 6, sum = 5;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}

a) 2
b) 3
c) 4
d) 5

View Answer

Answer: c [Reason:] The output of the above code is 4.

Set 2

1. What is direct addressing?
a) Distinct array position for every possible key
b) Fewer array positions than keys
c) Fewer keys than array positions
d) None of the mentioned

View Answer

Answer: a [Reason:] Direct addressing is possible only when we can afford to allocate an array that has one position for every possible key.

2. When is it appropriate to use direct addressing?
a) When the array is comparatively large
b) When the universe U of keys is reasonably small
c) When the universe U of keys is reasonably large
d) When the array is comparatively small

View Answer

Answer: b [Reason:] Since each key is associated with a slot in the array, it is better to use direct addressing when the universe of keys is small as the array size grows with the increase in number of keys.

3. What is the search complexity in direct addressing?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(1)

View Answer

Answer: d [Reason:] Since every key has a unique array position, searching takes a constant time.

4. What is the time complexity to insert an element into the direct address table?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(1)

View Answer

Answer: d [Reason:] As every key has a unique array position, it takes constant time to insert an element.

5. What is the advantage of using a dynamic set in direct addressing?
a) It saves time
b) It saves space
c) It saves both time and space
d) None of the mentioned

View Answer

Answer: b [Reason:] Using a dynamic set, the size of the array is restricted to the number of keys, hence saves space.

6. 4. What is the time complexity to delete an element from the direct address table?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(1)

View Answer

Answer: d [Reason:] As every key has a unique array position, it takes constant time to delete an element, although the deleted position must be specified by nil.

7. How is a bit vector better compared to a normal array for implementing the hash table?
a) It saves time
b) It saves space
c) It saves both time and space
d) None of the mentioned

View Answer

Answer: b [Reason:] A bit vector is an array of bits of only 0s and 1s, a bit vector of length m takes much less space than an array of m pointers.

Set 3

1. Every Directed Acyclic Graph has at least one sink vertex.
a) True
b) False

View Answer

Answer: a [Reason:] A sink vertex is a vertex which has an outgoing degree of zero.

2. Which of the following is a topological sorting of the given graph?
data-structure-questions-answers-directed-acyclic-graph-q2
a) A B C D E F
b) A B F E D C
c) A B E C F D
d) All of the Mentioned

View Answer

Answer: d [Reason:] Topological sorting is a linear arrangement of vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

3. With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?
a) (V*(V-1))/2
b) (V*(V+1))/2
c) (V+1)C2
d) (V-1)C2

View Answer

Answer: a [Reason:] The first edge would have an outgoing degree of atmost V-1, the next edge would have V-2 and so on, hence V-1 + V-2…. +1 equals (V*(V-1))/2.

4. The topological sorting of any DAG can be done in ________ time.
a) cubic
b) quadratic
c) linear
d) logarithmic

View Answer

Answer: c [Reason:] Topological sorting can be done in O(V+E), here V and E represents number of vertices and number of edges respectively.

5. If there are more than 1 topological sorting of a DAG is possible, which of the following is true.
a) Many Hamiltonian paths are possible
b) No Hamiltonian path is possible
c) Exactly 1 Hamiltonian path is possible
d) Given information is insufficient to comment anything

View Answer

Answer: b [Reason:] For a Hamiltonian path to exist all the vertices must be connected with a path, had that happened there would have been a unique topological sort.

6. What sequence would the BFS traversal of the given graph yield?
data-structure-questions-answers-directed-acyclic-graph-q6
a) A F D B C E
b) C B A F D
c) A B D C F
d) F D C B A

View Answer

Answer: c [Reason:] In BFS nodes gets explored and then the neighbors of the current node gets explored, before moving on to the next levels.

7. What would be the output of the following C++ program if the given input is

0 0 0 1 1
0 0 0 0 1
0 0 0 1 0
1 0 1 0 0
1 1 0 0 0
 
#include <bits/stdc++.h>
using namespace std;
bool visited[5];
int G[5][5];
 
void fun(int i)
{
cout<<i<<" ";
visited[i]=true;
for(int j=0;j<5;j++)
if(!visited[j]&&G[i][j]==1)
fun(j);
}
 
int main()
{   
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
cin>>G[i][j];
 
for(int i=0;i<5;i++)
visited[i]=0;
 
fun(0);
return 0;
}

a) 0 2 3 1 4
b) 0 3 2 4 1
c) 0 2 3 4 1
d) 0 3 2 1 4

View Answer

Answer: b [Reason:] Given Input is the adjacency matrix of a graph G, whereas the function ‘fun’ prints the DFS traversal.

8. Which of the given statement is true?
a) All the Cyclic Directed Graphs have topological sortings
b) All the Acyclic Directed Graphs have topological sortings
c) All Directed Graphs have topological sortings
d) None of the given statements is true

View Answer

Answer: a [Reason:] Cyclic Directed Graphs cannot be sorted topologically.

9. For any two different vertices u and v of an Acyclic Directed Graph if v is reachable from u, u is also reachable from v?
a) True
b) False

View Answer

Answer: b [Reason:] If such vertices exists it means that the graph contains a cycle which contradicts the first part of the statement.

10. What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?
a) Depends on a Graph
b) Will always be zero
c) Will always be greater than zero
d) May be zero or greater than zero

View Answer

Answer: b [Reason:] Every Directed Acyclic Graph has a source and a sink vertex.

Set 4

1. Dijkstra’s Algorithm will work for both negative and positive weights?
a) True
b) False

View Answer

Answer: b [Reason:] Dijkstra’s Algorithm assumes all weights to be non-negative.

2. A graph having an edge from each vertex to every other vertex is called a ___________
a) Tightly Connected
b) Strongly Connected
c) Weakly Connected
d) Loosely Connected

View Answer

Answer: a [Reason:] This is a part of the nomenclature followed in Graph Theory.

3. What is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices?
a) 2
b) 4
c) 5
d) 9

View Answer

Answer: b [Reason:] data-structure-questions-answers-directed-graph-q3

4. Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________
a) O(V*V)
b) O(V*V*V)
c) O(E*V)
d) O(E*E)

View Answer

Answer: b [Reason:] The Algorithm uses Dynamic Programming and checks for every possible path.

5. All Graphs have unique representation on paper.
a) True
b) False

View Answer

Answer: False [Reason:] Same Graph may be drawn in different ways on paper.

6. Assuming value of every weight to be greater than 10, in which of the following cases the shortest path of a directed weighted graph from 2 vertices u and v will never change?
a) add all values by 10
b) subtract 10 from all the values
c) multiply all values by 10
d) In both the cases of multiplying and adding by 10

View Answer

Answer: c [Reason:] In case of addition or subtraction the shortest path may change because the number of edges between different paths may be different, while in case of multiplication path wont change.

7. What is the maximum possible number of edges in a directed graph with no self loops having 8 vertices?
a) 28
b) 64
c) 256
d) 56

View Answer

Answer: d [Reason:] If a graph has V vertices than every vertex can be connected to a possible of V-1 vertices.

8. What would be the DFS traversal of the given Graph?
data-structure-questions-answers-directed-graph-q8
a) ABCED
b) AEDCB
c) EDCBA
d) ADECB

View Answer

Answer: a [Reason:] In this case two answers are possible including ADEBC.

9. What would be the value of the distance matrix, after the execution of the given code?

  1. #include <bits/stdc++.h>
  2. #define INF 1000000
  3. int graph[V][V] = {   {0,   7,  INF, 4},
  4.                       {INF, 0,   13, INF},
  5.                       {INF, INF, 0,   12},
  6.                       {INF, INF, INF, 0}
  7.                   };
  8.  
  9. int distance[V][V], i, j, k;
  10.  
  11. for (i = 0; i < V; i++)
  12.         for (j = 0; j < V; j++)
  13.     	distance[i][j] = graph[i][j];
  14.  
  15. for (k = 0; k < V; k++)
  16. 	for (i = 0; i < V; i++)
  17.         	for (j = 0; j < V; j++)
  18.                 {
  19.             		if (distance[i][k] + distance[k][j] < distance[i][j])
  20.                 		distance[i][j] = distance[i][k] + distance[k][j];
  21.  
  22.                            return 0;
  23.                 }

a)

  1.                 {            
  2.                         {0,   7,  INF, 4},
  3.                         {INF, 0,   13, INF},
  4.                         {INF, INF, 0,   12},
  5.                         {INF, INF, INF, 0}
  6.                 };

b)

  1.                 {            
  2.                         {0,   7,  20, 24},
  3.                         {INF, 0,   13, 25},
  4.                         {INF, INF, 0,   12},
  5.                         {INF, INF, INF, 0}
  6.                 };

c)

  1.                   { 
  2.                         {0,   INF,  20, 24},
  3.                         {INF, INF,   13, 25},
  4.                         {INF, INF, 0,   12},
  5.                         {INF, INF, INF, 0}
  6.                         {INF, 0,   13, 25},
  7.                         {INF, INF, 0,   12},
  8.                         {24, INF, INF, 0}
  9.                   };

d) None of the mentioned

View Answer

Answer: b [Reason:] The program computes the shortest sub distances.

10. What is the maximum number of edges present in a simple directed graph with 7 vertices if there exists no cycles in the graph?
a) 21
b) 7
c) 6
d) 49

View Answer

Answer: c [Reason:] If the no cycles exists then the difference between the number of vertices and edges is 1.

Set 5

1. What is a dynamic array?
a) A variable size data structure
b) An array which is created at runtime
c) The memory to the array is allocated at runtime
d) An array which is reallocated everytime whenever new elements have to be added

View Answer

Answer: a [Reason:] It is a varying-size list data structure that allows items to be added or removed, it may use a fixed sized array at the back end.

2. What is meant by physical size in a dynamic array?
a) The size allocated to elements
b) The size extended to add new elements
c) The size of the underlying array at the back-end
d) The size visible to users.

View Answer

Answer: c [Reason:] Physical size, also called array capacity is the size of the underlying array, which is the maximum size without relocation of data.

3. The number of items used by the dynamic array contents is its __________
a) Physical size
b) Capacity
c) Logical size
d) Random size

View Answer

Answer: c [Reason:] By definition.

4. How will you implement dynamic arrays in Java?
a) Set
b) Map
c) HashMap
d) List

View Answer

Answer: d [Reason:] ArrayList is used to implement dynamic arrays in Java.

5. Which of the following is the correct syntax to declare an ArrayList in Java?
a) ArrayList al = new ArrayList();
b) ArrayList al = new ArrayList[];
c) ArrayList al() = new ArrayList();
d) ArrayList al[] = new ArrayList[];

View Answer

Answer: a [Reason:] This is a non-generic way of creating an ArrayList.

6. In what type of dynamic array do you divide the array into two parts?
a) Hashed Array Tree
b) Geometric Array
c) Bounded-size dynamic array
d) None of the mentioned

View Answer

Answer: c [Reason:] The first part stores the items of the dynamic array and the second part is reserved for new allocations.

7. What are the advantages of dynamic arrays?
a) Locality of reference
b) Data cache utilization
c) Random access
d) All of the mentioned

View Answer

Answer: d [Reason:] Dynamic arrays share the advantage of arrays, added to it is the dynamic addition of elements to the array.

8. What is the time complexity for inserting/deleting at the beginning of the array?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)

View Answer

Answer: b [Reason:] All the other elements will have to be moved, hence O(n).