# 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. What is the search complexity in direct addressing?

a) O(n)

b) O(logn)

c) O(nlogn)

d) O(1)

### View Answer

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

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

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

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

## Set 3

1. Every Directed Acyclic Graph has at least one sink vertex.

a) True

b) False

### View Answer

2. Which of the following is a topological sorting of the given graph?

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

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

4. The topological sorting of any DAG can be done in ________ time.

a) cubic

b) quadratic

c) linear

d) logarithmic

### View Answer

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

6. What sequence would the BFS traversal of the given graph yield?

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

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

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

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

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

## Set 4

1. Dijkstra’s Algorithm will work for both negative and positive weights?

a) True

b) False

### View Answer

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

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

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

5. All Graphs have unique representation on paper.

a) True

b) False

### View Answer

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

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

8. What would be the DFS traversal of the given Graph?

a) ABCED

b) AEDCB

c) EDCBA

d) ADECB

### View Answer

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

`#include <bits/stdc++.h>`

`#define INF 1000000`

int graph[V][V] = { {0, 7, INF, 4},

{INF, 0, 13, INF},

{INF, INF, 0, 12},

{INF, INF, INF, 0}

};

int distance[V][V], i, j, k;

for (i = 0; i < V; i++)

for (j = 0; j < V; j++)

distance[i][j] = graph[i][j];

for (k = 0; k < V; k++)

for (i = 0; i < V; i++)

for (j = 0; j < V; j++)

`{`

if (distance[i][k] + distance[k][j] < distance[i][j])

distance[i][j] = distance[i][k] + distance[k][j];

return 0;

`}`

a)

`{`

{0, 7, INF, 4},

{INF, 0, 13, INF},

{INF, INF, 0, 12},

{INF, INF, INF, 0}

};

b)

`{`

{0, 7, 20, 24},

{INF, 0, 13, 25},

{INF, INF, 0, 12},

{INF, INF, INF, 0}

};

c)

`{`

{0, INF, 20, 24},

{INF, INF, 13, 25},

{INF, INF, 0, 12},

{INF, INF, INF, 0}

{INF, 0, 13, 25},

{INF, INF, 0, 12},

{24, INF, INF, 0}

};

d) None of the mentioned

### View Answer

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

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

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

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

4. How will you implement dynamic arrays in Java?

a) Set

b) Map

c) HashMap

d) List

### View Answer

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

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

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

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)