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

Answer: c [Reason:] In an adjacency list for every vertex there is a linked list which have the values of the edges to which it is connected.

2. For some sparse graph an adjacency list is more space efficient against an adjacency matrix.
a) True
b) False

View Answer

Answer: a [Reason:] Space complexity for adjacency matrix is always O(V*V) while space complexity for adjacency list in this case would be O(V).

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

Answer: a [Reason:] The maximum edges a vertex can have is V-1.

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

Answer: a [Reason:] i) takes v+4e, ii) takes v+2e, iii) takes v+3e, iv) takes v +6e space.

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

Answer: c [Reason:] In an adjacency list for every vertex there is a linked list which have the values of the edges to which it is connected.

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

Answer: c [Reason:] Vertex would have a name and a linked list attached to it.

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

Answer: b [Reason:] In case of sparse graph most of the entries in the adjacency matrix would be 0, hence adjacency list would be preferred.

8. To create an adjacency list C++’s map container can be used.
a) True
b) False

View Answer

Answer: True [Reason:] We can create a mapping from string to a vector, where string would be the name of the vertex and vector would contains the name of the vertices to which it is connected.

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

Answer: a [Reason:] The function win in the constant time as all the four step takes constant time.

10. What would be the time complexity of the BFS traversal of a graph with n vertices and n1.25 edges?
a) O(n)
b) O(n1.25)
c) O(n2.25)
d) O(n*n)

View Answer

Answer: b [Reason:] The time complexity for BFS is O(|V| + |E|) = O(n + n1.25) = O(n1.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

Answer: d [Reason:] There are n*n elements in the adjacency matrix of a graph with n vertices.

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

Answer: b [Reason:] Total number of values in the matrix is 4*4=16, out of which 6 entries are non zero.

3. Adjacency matrix of all graphs are symmetric.
a) False
b) True

View Answer

Answer: a [Reason:] Only undirected graphs produce symmetric adjacency matrices.

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(E2)
c) O(E)
d) O(V2)

View Answer

Answer: d [Reason:] As V entries are 0, a total of V^2-V entries are to be examined.

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

Answer: b [Reason:] Row number of the matrix represents the tail, while Column number represents the head of the edge.

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

Answer: c [Reason:] Out of n*n possible values for a simple graph the diagonal values will always be zero.

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

Answer: c [Reason:] To check if there is an edge between to vertices i and j, it is enough to see if the value of A[i][j] is 1 or 0, here A is the adjacency matrix.

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

Answer: a [Reason:] Value of eccentricity for vertices A, C is 2 whereas for F, B, D, E it is 3.

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

Answer: d [Reason:] A simple graph must have no-self loops, should be undirected.

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

Answer: c [Reason:] A2 = [ [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

Answer: a [Reason:] All adjacency matrices are square matrices.

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

Answer: a [Reason:] This is a property of isomorphic graphs.

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

  1. #include <bits/stdc++.h> 
  2. using namespace std; 
  3. int cur=0; 
  4. int G[10][10]; 
  5. bool visited[10]; 
  6. deque <int> q; 
  7.  
  8. void fun(int n); 
  9.  
  10. int main()
  11. {   
  12. 	int num=0; 
  13. 	int n; 
  14. 	cin>>n; 
  15.  
  16. 	for(int i=0;i<n;i++) 
  17.       	for(int j=0;j<n;j++) 
  18.         	cin>>G[i][j]; 
  19.  
  20. 	for(int i=0;i<n;i++) 
  21.         visited[i]=false; 
  22.  
  23.         fun(n); 
  24. 	return 0; 
  25. } 
  26.  
  27. void fun(int n)
  28. { 
  29. 	cout<<cur<<" "; 
  30. 	visited[cur]=true; 
  31. 	q.push_back(cur); 
  32.  
  33. 	do
  34.         { 
  35. 		for(int j=0;j<n;j++)
  36.                 { 
  37. 		    if(G[cur][j]==1 && !visited[j])
  38.                     { 
  39. 		        q.push_back(j); 
  40. 		        cout<<j<<" "; 
  41. 		        visited[j]=true; 
  42. 	            } 
  43.  
  44.                  } 
  45.  
  46. 		q.pop_front(); 
  47. 		if(!q.empty()) 
  48. 		cur=q.front(); 
  49. 	 }while(!q.empty()); 
  50. }

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

Answer: c [Reason:] The given code performs the breadth first search routine on the Graph. The sequence obtained would be 0 1 8 2 6 3 4 5 7.

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

Answer: b [Reason:] For any graph having edges, the condition G[i][j]==1 would hold true, which would result in an infinite loop.

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

Answer: c [Reason:] 0th 1st and 2nd vertices form a component, 3rd and 4th forms another and 5th vertex forms a component of a single vertex.

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

Answer: d [Reason:] All of the above mentioned methods can be used to find the sum of first n natural numbers.

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

Answer: c [Reason:] The sum of first n natural numbers is given by n*(n+1)/2, which is equal to (n+1)C2.

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

Answer: b [Reason:] The line “sm += i” completes the above code.

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

Answer: d [Reason:] Since the variable “sm” is not initialized to 0, it will produce a garbage value.

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(n2)
d) O(n3)

View Answer

Answer: b [Reason:] The time complexity of the above iterative method used to find the sum of first n natural numbers is O(n).

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

Answer: c [Reason:] The recurrence relation for the above code is: n + recursive_sum(n – 1).

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

Answer: a [Reason:] “if(n == 0)” is the base case for the above recursive code.

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(n2)
d) O(n3)

View Answer

Answer: b [Reason:] The time complexity of the above recursive implementation used to find the sum of first n natural numbers is O(n).

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

Answer: c [Reason:] Recursion and iteration take O(n) time to find the sum of first n natural numbers while binomial coefficient takes O(1) time.

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

Answer: b [Reason:] The above code prints the sum of first 5 natural numbers, which is 15.

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

Answer: c [Reason:] The function recursive_sum is called 6 times when the following code is executed.

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

Answer: b [Reason:] The program prints the sum of first 0 natural numbers, which is 0.

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

Answer: d [Reason:] The above code doesn’t handle the case of negative numbers and so the function recursive_sum() will be called again and again till the stack overflows and the program produces a runtime error.

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

Answer: d [Reason:] All of the above mentioned methods can be used to solve the assembly line scheduling problem.

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(n2)
d) O(2n)

View Answer

Answer: d [Reason:] In the brute force algorithm, all the possible ways are calculated which are of the order of 2n.

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

Answer: c [Reason:] In the dynamic programming implementation of the assembly line scheduling problem, 2 lookup tables are required one for storing the minimum time and the other for storing the assembly line number.

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

Answer: b [Reason:] For the optimal solution, the starting assembly line is line 2.

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

Answer: b [Reason:] For the optimal solution, the exit assembly line is line 2.

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

Answer: d [Reason:] The minimum time required is 43. The path is S2,1 -> S1,2 -> S2,3 -> S2,4, where Si,j : i = line number, j = station number

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

Answer: a [Reason:] The line t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]) should be added to complete the above code.

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(n2)
d) O(n3)

View Answer

Answer: b [Reason:] The time complexity of the above dynamic programming implementation of the assembly line scheduling problem is O(n).

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(n2)
d) O(n3)

View Answer

Answer: b [Reason:] The space complexity of the above dynamic programming implementation of the assembly line scheduling problem is O(n).

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

Answer: c [Reason:] The program prints the optimal time required to build the car chassis, which is 34.

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

Answer: c [Reason:] The value stored in t1[2] when the above code is executed is 20.

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

Answer: c [Reason:] The value stored in t2[3] when the above code is executed is 25.

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

Answer: d [Reason:] The program prints the optimal time required to build the car chassis, which is 88.

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

Answer: a [Reason:] It is a self balancing tree with height difference atmost 1.

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

Answer: a [Reason:] In real world dealing with random values is often not possible, the probability that u are dealing with non random values(like sequential) leads to mostly skew trees, which leads to worst case. hence we make height balance by rotations.

3. Which of the below diagram is following AVL tree property?
i.data-structure-questions-answers-avl-tree-q3
ii.data-structure-questions-answers-avl-tree-q3a
a) only i
b) only i and ii
c) only ii
d) none of the mentioned

View Answer

Answer: b [Reason:] The property of AVL tree is it is height balanced tree with difference of atmost 1 between left and right subtrees.

4. What is the maximum height of an AVL tree with p nodes?
a) p
b) log(p)
c) log(p)/2
d) p2

View Answer

Answer: b [Reason:] Consider height of tree to be ‘he’, then number of nodes which totals to p can be written in terms of height as N(he)=N(he-1)+1+N(he-2). since N(he) which is p can be written in terms of height as the beside recurrence relation which on solving gives N(he)= O(logp) as worst case height.

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

Answer: a [Reason:] It is interesting to note that after insertion, only the path from that point to node or only that subtrees are imbalanced interms of height.

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

Answer: b [Reason:] Sort the given input, find the median element among them, make it as root and construct left and right subtrees with elements lesser and greater than the median element recursively. this ensures the subtrees differ only by height 1.

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

Answer: a [Reason:] At every level we can form a tree with difference in height between subtrees to be atmost 1 and so there can be log(n) such levels since height of AVL tree is log(n).

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

Answer: a [Reason:] The condition to check the height difference between left and right subtrees is missing. if (absolute(left_tree_height – right_tree_height)>1) must be added.

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

Answer: a [Reason:] In the code we are trying to make the left rotation and so we need to find maximum of those two values.

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

View Answer

Answer: b [Reason:] Every node in an AVL tree need to store the balance factor (-1, 0, 1) hence space costs to O(n), n being number of nodes. but in red-black we can use the sign of number (if numbers being stored are only positive) and hence save space for storing balancing information. there are even other reasons where redblack is mostly prefered.