# Multiple choice question for engineering

## Set 1

1. Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is ___________

a) O(E)

b) O(V*V)

c) O(E+V)

d) O(V)

### View Answer

2. For some sparse graph an adjacency list is more space efficient against an adjacency matrix.

a) True

b) False

### View Answer

3. Time complexity to find if there is an edge between 2 particular vertices is _________

a) O(V)

b) O(E)

c) O(1)

d) O(V+E)

### View Answer

4. For the given conditions, which of the following is in the correct order of increasing space requirement?

i) Undirected, no weight

ii) Directed, no weight

iii) Directed, weighted

iv) Undirected, weighted

a) ii iii i iv

b) i iii ii iv

c) iv iii i ii

d) i ii iii iv

### View Answer

5. Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is __________

a) O(V)

b) O(E*E)

c) O(E)

d) O(E+V)

### View Answer

6. Complete the given snippet of code for the adjacency list representation of a weighted directed graph.

class neighbor { int vertex, weight; ____ next; } class vertex { string name; _____ adjlist; } vertex adjlists[101];

a) vertex, vertex

b) neighbor, vertex

c) neighbor, neighbor

d) vertex, neighbor

### View Answer

7. In which case adjacency list is preferred in front of an adjacency matrix?

a) Dense graph

b) Sparse graph

c) Adjacency list is always preferred

d) None of the mentioned

### View Answer

8. To create an adjacency list C++’s map container can be used.

a) True

b) False

### View Answer

9. What would be the time complexity of the following function which adds an edge between two vertices i and j, with some weight ‘weigh’ to the graph having V vertices?

vector<int> adjacent[15] ; vector<int> weight[15]; void addEdge(int i,int j,int weigh) { adjacent[a].push_back(i); adjacent[b].push_back(j); weight[a].push_back(weigh); weight[b].push_back(weigh); }

a) O(1)

b) O(V)

c) O(V*V)

d) O(log V)

### View Answer

10. What would be the time complexity of the BFS traversal of a graph with n vertices and n^{1.25} edges?

a) O(n)

b) O(n^{1.25})

c) O(n^{2.25})

d) O(n*n)

### View Answer

^{1.25}) = O(n

^{1.25}).

## Set 2

1. The number of elements in the adjacency matrix of a graph having 7 vertices is __________

a) 7

b) 14

c) 36

d) 49

### View Answer

2. What would be the number of zeros in the adjacency matrix of the given graph ?

a) 10

b) 6

c) 16

d) 0

### View Answer

3. Adjacency matrix of all graphs are symmetric.

a) False

b) True

### View Answer

4. The time complexity to calculate the number of edges in a graph whose information in stored in form of an adjacency matrix is ____________

a) O(V)

b) O(E^{2})

c) O(E)

d) O(V^{2})

### View Answer

5. For the adjacency matrix of a directed graph the row sum is the _________ degree and the column sum is the ________ degree.

a) in, out

b) out, in

c) in, total

d) total, out

### View Answer

6. What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with n vertices?

a) (n*(n-1))/2

b) (n*(n+1))/2

c) n*(n-1)

d) n*(n+1)

### View Answer

7. On which of the following statements does the time complexity of checking if an edge exists between two particular vertices is not, depends?

a) Depends on the number of edges

b) Depends on the number of vertices

c) Is independent of both the number of edges and vertices

d) It depends on both the number of edges and vertices

### View Answer

8. In the given connected graph G, what is the value of rad(G) and diam(G)?

a) 2, 3

b) 3, 2

c) 2, 2

d) 3, 3

### View Answer

9. Which of these adjacency matrices represents a simple graph?

a) [ [1, 0, 0], [0, 1, 0], [0, 1, 1] ].

b) [ [1, 1, 1], [1, 1, 1], [1, 1, 1] ].

c) [ [0, 0, 1], [0, 0, 0], [0, 0, 1] ].

d) [ [0, 0, 1], [1, 0, 1], [1, 0, 0] ].

### View Answer

10. Given an adjacency matrix A = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ], how many ways are there in which a vertex can walk to itself using 2 edges.

a) 2

b) 4

c) 6

d) 8

### View Answer

^{2}= [ [2, 1, 1], [1, 2, 1], [1, 1, 2] ], all the 3 vertices can reach to themselves in 2 ways, hence a total of 3*2, 6 ways.

11. If A[x+3][y+5] represents an adjacency matrix, which of these could be the value of x and y.

a) x=5, y=3

b) x=3, y=5

c) x=3, y=3

d) x=5, y=5

### View Answer

12. Two directed graphs(G and H) are isomorphic if and only if A=PBP-1, where P and A are adjacency matrices of G and H respectively.

a) True

b) False

### View Answer

13. Given the following program, what will be the 3rd number that’d get printed in the output sequence for the given input?

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

using namespace std;

int cur=0;

int G[10][10];

bool visited[10];

deque <int> q;

void fun(int n);

int main()

`{`

int num=0;

int n;

cin>>n;

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

cin>>G[i][j];

for(int i=0;i<n;i++)

visited[i]=false;

fun(n);

return 0;

`}`

void fun(int n)

`{`

cout<<cur<<" ";

visited[cur]=true;

q.push_back(cur);

`do`

`{`

for(int j=0;j<n;j++)

`{`

if(G[cur][j]==1 && !visited[j])

`{`

q.push_back(j);

cout<<j<<" ";

visited[j]=true;

`}`

`}`

q.pop_front();

if(!q.empty())

cur=q.front();

}while(!q.empty());

`}`

Input Sequence:-

9 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0

a) 2

b) 6

c) 8

d) 4

### View Answer

14. For which type of graph, the given program would run infinitely? The Input would be in the form of an adjacency Matrix and n is its dimension (1<n<10).

#include <bits/stdc++.h> using namespace std; int G[10][10]; void fun(int n); int main() { int num=0; int n; cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>G[i][j]; fun(n); return 0; } void fun(int n) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(G[i][j]==1) j--; }

a) All Fully Connected Graphs

b) All Empty Graphs

c) All Bipartite Graphs

d) None of the Mentioned

### View Answer

15. Given the following adjacency matrix of a graph(G) determine the number of components in the G.

[0 1 1 0 0 0], [1 0 1 0 0 0], [1 1 0 0 0 0], [0 0 0 0 1 0], [0 0 0 1 0 0], [0 0 0 0 0 0].

a) 1

b) 2

c) 3

d) 4

### View Answer

## Set 3

1. Which of the following methods can be used to find the sum of first n natural numbers?

a) Iteration

b) Recursion

c) Binomial coefficient

d) All of the mentioned

### View Answer

2. Which of the following gives the sum of the first n natural numbers?

a) nC2

b) (n-1)C2

c) (n+1)C2

d) none of the mentioned

### View Answer

3. Consider the following iterative solution to find the sum of first n natural numbers:

#include<stdio.h> int get_sum(int n) { int sm = 0, i; for(i = 1; i <= n; i++) ________; return sm; } int main() { int n = 10; int ans = get_sum(n); printf("%d",ans); return 0; }

Which of the following lines completes the above code?

a) sm = i

b) sm += i

c) i = sm

d) i += sm

### View Answer

4. What is the output of the following code?

#include<stdio.h> int get_sum(int n) { int sm, i; for(i = 1; i <= n; i++) sm += i; return sm; } int main() { int n = 10; int ans = get_sum(n); printf("%d",ans); return 0; }

a) 55

b) 45

c) 35

d) none of the mentioned

### View Answer

5. What is the time complexity of the above iterative method used to find the sum of the first n natural numbers?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n^{3})

### View Answer

6. Consider the following code:

#include<stdio.h> int recursive_sum(int n) { if(n == 0) return 0; return ________; } int main() { int n = 5; int ans = recursive_sum(n); printf("%d",ans); return 0; }

Which of the following lines is the recurrence relation for the above code?

a) (n – 1) +recursive_sum(n)

b) n + recursive_sum(n)

c) n + recursive_sum(n – 1)

d) (n – 1) + recursive_sum(n – 1)

### View Answer

7. Consider the following code:

#include<stdio.h> int recursive_sum(int n) { if(n == 0) return 0; return n + recursive_sum(n - 1); } int main() { int n = 5; int ans = recursive_sum(n); printf("%d",ans); return 0; }

Which of the following is the base case for the above recursive code?

a) if(n == 0)

b) return 0

c) return n + recursive_sum(n – 1)

d) none of the mentioned

### View Answer

8. What is the time complexity of the above recursive implementation used to find the sum of the first n natural numbers?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n^{3})

### View Answer

9. Which of the following methods used to find the sum of first n natural numbers has the least time complexity?

a) Recursion

b) Iteration

c) Binomial coefficient

d) All of the mentioned

### View Answer

10. What is the output of the following code?

#include<stdio.h> int recursive_sum(int n) { if(n == 0) return 0; return n + recursive_sum(n - 1); } int main() { int n = 5; int ans = recursive_sum(n); printf("%d",ans); return 0; }

a) 10

b) 15

c) 21

d) none of the mentioned

### View Answer

11. How many times is the function recursive_sum() called when the following code is executed?

#include<stdio.h> int recursive_sum(int n) { if(n == 0) return 0; return n + recursive_sum(n - 1); } int main() { int n = 5; int ans = recursive_sum(n); printf("%d",ans); return 0; }

a) 4

b) 5

c) 6

d) 7

### View Answer

12. What is the output of the following code?

#include<stdio.h> int recursive_sum(int n) { if(n == 0) return 0; return n + recursive_sum(n - 1); } int main() { int n = 0; int ans = recursive_sum(n); printf("%d",ans); return 0; }

a) -1

b) 0

c) 1

d) runtime error

### View Answer

13. What is the output of the following code?

#include<stdio.h> int recursive_sum(int n) { if(n == 0) return 0; return n + recursive_sum(n - 1); } int main() { int n = -4; int ans = recursive_sum(n); printf("%d",ans); return 0; }

a) 0

b) -10

c) 1

d) runtime error

### View Answer

## Set 4

1. Which of the following methods can be used to solve the assembly line scheduling problem?

a) Recursion

b) Brute force

c) Dynamic programming

d) All of the mentioned

### View Answer

2. What is the time complexity of the brute force algorithm used to solve the assembly line scheduling problem?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(2^{n})

### View Answer

^{n}.

3. In the dynamic programming implementation of the assembly line scheduling problem, how many lookup tables are required?

a) 0

b) 1

c) 2

d) 3

### View Answer

4. 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 starting assembly line?

a) Line 1

b) Line 2

c) All of the mentioned

d) None of the mentioned

### View Answer

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

a) Line 1

b) Line 2

c) All of the mentioned

d) None of the mentioned

### View Answer

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

What is the minimum time required to build the car chassis?

a) 40

b) 41

c) 42

d) 43

### View Answer

7. Consider the following code:

#include<stdio.h> int get_min(int a, int b) { if(a<b) return a; return b; } int minimum_time_required(int reach[][3],int spent[][4], int *entry, int *exit, int n) { int t1[n], t2[n],i; t1[0] = entry[0] + spent[0][0]; t2[0] = entry[1] + spent[1][0]; for(i = 1; i < n; i++) { t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]); __________; } return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]); }

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

a) t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i])

b) t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+spent[1][i])

c) t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1])

d) none of the mentioned

### View Answer

8. What is the time complexity of the above dynamic programming implementation of the assembly line scheduling problem?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n^{3})

### View Answer

9. What is the space complexity of the above dynamic programming implementation of the assembly line scheduling problem?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n^{3})

### View Answer

10. What is the output of the following code?

#include<stdio.h> int get_min(int a, int b) { if(a<b) return a; return b; } int minimum_time_required(int reach[][3],int spent[][4], int *entry, int *exit, int n) { int t1[n], t2[n], i; t1[0] = entry[0] + spent[0][0]; t2[0] = entry[1] + spent[1][0]; for(i = 1; i < n; i++) { t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]); t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]); } return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]); } int main() { int time_to_reach[][3] = {{6, 1, 5}, {2, 4, 7}}; int time_spent[][4] = {{6, 5, 4, 7}, {5, 10, 2, 6}}; int entry_time[2] = {5, 6}; int exit_time[2] = {8, 9}; int num_of_stations = 4; int ans = minimum_time_required(time_to_reach, time_spent, entry_time, exit_time, num_of_stations); printf("%d",ans); return 0; }

a) 32

b) 33

c) 34

d) 35

### View Answer

11. What is the value stored in t1[2] when the following code is executed?

#include<stdio.h> int get_min(int a, int b) { if(a<b) return a; return b; } int minimum_time_required(int reach[][3],int spent[][4], int *entry, int *exit, int n) { int t1[n], t2[n],i; t1[0] = entry[0] + spent[0][0]; t2[0] = entry[1] + spent[1][0]; for(i = 1; i < n; i++) { t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]); t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]); } return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]); } int main() { int time_to_reach[][3] = {{6, 1, 5}, {2, 4, 7}}; int time_spent[][4] = {{6, 5, 4, 7}, {5, 10, 2, 6}}; int entry_time[2] = {5, 6}; int exit_time[2] = {8, 9}; int num_of_stations = 4; int ans = minimum_time_required(time_to_reach, time_spent, entry_time, exit_time, num_of_stations); printf("%d",ans); return 0; }

a) 16

b) 18

c) 20

d) 22

### View Answer

12. What is the value stored in t2[3] when the following code is executed?

#include<stdio.h> int get_min(int a, int b) { if(a<b) return a; return b; } int minimum_time_required(int reach[][3],int spent[][4], int *entry, int *exit, int n) { int t1[n], t2[n],i; t1[0] = entry[0] + spent[0][0]; t2[0] = entry[1] + spent[1][0]; for(i = 1; i < n; i++) { t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]); t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]); } return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]); } int main() { int time_to_reach[][3] = {{6, 1, 5}, {2, 4, 7}}; int time_spent[][4] = {{6, 5, 4, 7}, {5, 10, 2, 6}}; int entry_time[2] = {5, 6}; int exit_time[2] = {8, 9}; int num_of_stations = 4; int ans = minimum_time_required(time_to_reach, time_spent, entry_time, exit_time, num_of_stations); printf("%d",ans); return 0; }

a) 19

b) 23

c) 25

d) 27

### View Answer

13. What is the output of the following code?

#include<stdio.h> int get_min(int a, int b) { if(a<b) return a; return b; } int minimum_time_required(int reach[][4],int spent[][5], int *entry, int *exit, int n) { int t1[n], t2[n], i; t1[0] = entry[0] + spent[0][0]; t2[0] = entry[1] + spent[1][0]; for(i = 1; i < n; i++) { t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]); t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]); } return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]); } int main() { int time_to_reach[][4] = {{16, 10, 5, 12}, {12, 4, 17, 8}}; int time_spent[][5] = {{13, 5, 20, 19, 9}, {15, 10, 12, 16, 13}}; int entry_time[2] = {12, 9}; int exit_time[2] = {10, 13}; int num_of_stations = 5; int ans = minimum_time_required(time_to_reach, time_spent, entry_time, exit_time, num_of_stations); printf("%d",ans); return 0; }

a) 62

b) 69

c) 75

d) 88

### View Answer

## Set 5

1. What is an AVL tree?

a) a tree which is balanced and is a height balanced tree

b) a tree which is unbalanced and is a height balanced tree

c) a tree with three children

d) a tree with atmost 3 children

### View Answer

2. Why we need to a binary tree which is height balanced?

a) to avoid formation of skew trees

b) to save memory

c) to attain faster memory access

d) to simplify storing

### View Answer

3. Which of the below diagram is following AVL tree property?

i.

ii.

a) only i

b) only i and ii

c) only ii

d) none of the mentioned

### View Answer

4. What is the maximum height of an AVL tree with p nodes?

a) p

b) log(p)

c) log(p)/2

d) ^{p}⁄_{2}

### View Answer

5. To restore the AVL property after inserting a element, we start at the insertion point and move towards root of that tree. is this statement true?

a) true

b) false

### View Answer

6. Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given without performing any rotations?

a) just build the tree with the given input

b) find the median of the set of elements given, make it as root and construct the tree

c) use trial and error

d) use dynamic programming to build the tree

### View Answer

7. What maximum difference in heights between the leafs of a AVL tree is possible?

a) log(n) where n is the number of nodes

b) n where n is the number of nodes

c) 0 or 1

d) atmost 1

### View Answer

8. Consider the pseudo code:

int avl(binarysearchtree root): if(not root) return 0 left_tree_height = avl(left_of_root) if(left_tree_height== -1) return left_tree_height right_tree_height= avl(right_of_root) if(right_tree_height==-1) return right_tree_height

Does the above code can check if a binary search tree is an AVL tree?

a) yes

b) no

### View Answer

9. Consider the below left-left rotation pseudo code where the node contains value pointers to left, right child nodes and a height value and Height() function returns height value stored at a particular node.

avltree leftrotation(avltreenode z): avltreenode w =x-left x-left=w-right w-right=x x-height=max(Height(x-left),Height(x-right))+1 w-height=max(missing)+1 return w

What is missing?

a) Height(w-left), x-height

b) Height(w-right), x-height

c) Height(w-left), x

d) Height(w-left)

### View Answer

10. Why to prefer red-black trees over AVL trees?

a) Because red-black is more rigidly balanced

b) AVL tree store balance factor in every node which costs space

c) AVL tree fails at scale

d) Red black is more efficient