## GATE CSE 2022

 Question 1
Which one of the following statements is TRUE for all positive functions $f(n)$?
 A $f(n^2)=\theta (f(n)^2)$, where $f(n)$ is a polynomial B $f(n^2)=o (f(n)^2)$ C $f(n^2)=O (f(n)^2)$, where $f(n)$ is an exponential function D $f(n^2)=\Omega (f(n)^2)$
Algorithm   Asymptotic Notation
Question 1 Explanation:
 Question 2
Which one of the following regular expressions correctly represents the language of the finite automaton given below?

 A ab*bab* + ba*aba* B (ab*b)*ab* + (ba*a)*ba* C (ab*b + ba*a)*(a* + b*) D (ba*a + ab*b)*(ab* + ba*)
Theory of Computation   Finite Automata
Question 2 Explanation:
 Question 3
Which one of the following statements is TRUE?
 A The LALR(1) parser for a grammar G cannot have reduce-reduce conflict if the LR(1) parser for G does not have reduce-reduce conflict. B Symbol table is accessed only during the lexical analysis phase. C Data flow analysis is necessary for run-time memory management. D LR(1) parsing is sufficient for deterministic context-free languages.
Compiler Design   Parsing
Question 3 Explanation:
 Question 4
In a relational data model, which one of the following statements is TRUE?
 A A relation with only two attributes is always in BCNF. B If all attributes of a relation are prime attributes, then the relation is in BCNF. C Every relation has at least one non-prime attribute. D BCNF decompositions preserve functional dependencies.
Database Management System   Normal Form
Question 4 Explanation:
 Question 5
Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

the reversed linked list should look like

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?
 A The best algorithm for the problem takes $\theta(n)$ time in the worst case. B The best algorithm for the problem takes $\theta(n \log n)$ time in the worst case. C The best algorithm for the problem takes $\theta(n^2)$ time in the worst case. D It is not possible to reverse a singly linked list in O(1) space.
Question 5 Explanation:
 Question 6
Suppose we are given $n$ keys, $m$ hash table slots, and two simple uniform hash functions $h_1$ and $h_2$. Further suppose our hashing scheme uses $h_1$ for the odd keys and $h_2$ for the even keys. What is the expected number of keys in a slot?
 A $\frac{m}{n}$ B $\frac{n}{m}$ C $\frac{2n}{m}$ D $\frac{n}{2m}$
Data Structure   Hashing
Question 6 Explanation:
 Question 7
Which one of the following facilitates transfer of bulk data from hard disk to main memory with the highest throughput?
 A DMA based I/O transfer B Interrupt driven I/O transfer C Polling based I/O transfer D Programmed I/O transfer
Computer Organization   IO Interface
Question 7 Explanation:
 Question 8
Let R1 and R2 be two 4-bit registers that store numbers in 2's complement form. For the operation R1+R2, which one of the following values of R1 and R2 gives an arithmetic overflow?
 A R1 = 1011 and R2 = 1110 B R1 = 1100 and R2 = 1010 C R1 = 0011 and R2 = 0100 D R1 = 1001 and R2 = 1111
Digital Logic   Number System
Question 8 Explanation:
 Question 9
Consider the following threads, $T_1, T_2, \text{ and }T_3$ executing on a single processor, synchronized using three binary semaphore variables, $S_1, S_2, \text{ and }S_3$, operated upon using standard $wait()$ and $signal()$. The threads can be context switched in any order and at any time.

Which initialization of the semaphores would print the sequence BCABCABCA ...?
 A $S_1 = 1; S_2 = 1; S_3 = 1$ B $S_1 = 1; S_2 = 1; S_3 = 0$ C $S_1 = 1; S_2 = 0; S_3 = 0$ D $S_1 = 0; S_2 = 1; S_3 = 1$
Operating System   Process Synchronization
Question 9 Explanation:
 Question 10
Consider the following two statements with respect to the matrices $A_{m \times n},B_{n \times m},C_{n \times n} \text{ and }D_{n \times n},$

Statement 1: $tr(AB) = tr(BA)$
Statement 2: $tr(CD) = tr(DC)$

where$tr()$ represents the trace of a matrix. Which one of the following holds?
 A Statement 1 is correct and Statement 2 is wrong. B Statement 1 is wrong and Statement 2 is correct. C Both Statement 1 and Statement 2 are correct. D Both Statement 1 and Statement 2 are wrong.
Engineering Mathematics   Linear Algebra
Question 10 Explanation:
There are 10 questions to complete.

Gate 2022 CSE question paper and solution.

Practice Previous year GATE CSE Topicwise questions with detail Solution.

## AVLTree Mock Test-1

 Question 1
An AVL tree $T$ contains $n$ integers, all distinct. For a given integer $k$, what is time comlexity of an algorithm to find the element $x$ in $T$ such that $|k-x|$ is minimized?
 A $\Theta ( n)$ B $\Theta (\log n)$ C $\Theta (n \log n)$ D $\Theta (n^2)$
Data Structure
Question 1 Explanation:
INSERT $k$, then find the PREDECESSOR and SUCCESSOR of $k$. Return the one whose difference with $k$ is smaller. All three methods take $\Theta (\log n)$ time.
Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 2
Given a binary search tree containing N integers, time complexity of creating an AVL tree containing the same values without destroying the original BST in the process is
 A O(N) B O(log N) C O(N log N) D O(N log log N)
Data Structure
Question 2 Explanation:
Traverse the BST (in any order) as you visit a node, insert that value into the AVL Tree. Each AVL Tree insert takes O(log N). You have to perform such N insert. So, total time is O(N log N).
Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 3
We have n distinct values stored in a height balanced (AVL) binary search tree. Which of the following statements is always true?
 A The value at each node is the median of the values in the subtree rooted at that node. B The shortest path between any pair of nodes is at most O(log n). C For any node, the difference between the size of the left subtree and the right subtree is at most 3. D The number of leaf nodes is greater than or equal to the number of internal nodes.
Data Structure
Question 3 Explanation:
A height balanced tree has overall height at most O(log n), so the shortest path between any pair of nodes is always at most O(log n).
The following AVL tree is a counterexample for all other statements.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 4
The number of ways in which the numbers {1,2,3,4,5,6,7} can be inserted in an empty AVL tree, so that we don't have to perform any rotations on it and value of root node as 4, is _____.
 A 64 B 24 C 48 D 128
Data Structure
Question 4 Explanation:
One possible is insert in the order {4, 2, 6, 1, 3, 5, 7} to make an AVL tree.
The ordering of {2, 6} and the ordering of {1, 3, 5, 7} do not matter. One can see the resulting tree is perfectly balance AVL tree.
Therefore, Total possible sequence of elements = 2!*4!=2*24=48
Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 5
What is the running time of an efficient method to merge two balanced binary search trees with n elements each into a balanced BST.
 A O(n log n) B O(n) C O(log n) D O(n log log n)
Data Structure
Question 5 Explanation:
We can start by doing an in-order walk of both trees concurrently. At each step, we compare the two tree elements and add the smaller one into a list, L, before calling that element's successor. When we finish walking both trees, L will contain a sorted list of elements from both trees. This takes O(n + n) = O(n) total time.
Now, from the sorted list, we want to create a balanced binary tree. We can do this by setting the root as the middle element of the list, and letting the first half of the list be its left subtree and the second half be its right subtree (recursively creating the balanced subtrees as well). This also takes O(n + n) = O(n) time.
The total time for this algorithm is therefore O(n)
Click to Join Our Telegram Group for Latest Update of MOCK TEST

There are 5 questions to complete.

Suggested Mock Test For You.

ALL FREE Mock Test of GATE CSE

GATE CSE Previous Years Questions on AVL Tree

GATE CSE Previous Years Questions on Data Structure

## Binary Search Tree Mock Test -1

 Question 1
The postorder traversal of a binary search tree with integer values produces the following sequence: 7, 12, 25, 47, 89, 55, 42, 17. What is the value of the left child of the root of the tree?
 A 42 B 25 C 12 D 7
Data Structure
Question 1 Explanation:
The inorder traversal of a search tree is always the sorted sequence. In this case: 7, 12, 17, 25, 42, 47, 55, 89. From the postorder traversal, we know that 17 is the root of the tree, so the segment 7, 12 corresponds to the left subtree and the segment 25, 42, 47, 55, 89 corresponds to the right subtree. The postorder traversal of the left subtree ends with 12, so this is the left child of the root node.
Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 2
A Binary Search Tree (BST) is made by including each integer in [1,100] exactly once. The depth of a node in the BST is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is_____.
 A 9 B 91 C 99 D 90
Data Structure
 Question 3
Consider the following function to traverse a search tree $t$ with integer values, where $even(m)$ returns True if $m$ is an even number and False otherwise.

function strangeOrder(t) {
if (t != NIL) {
if (even(t.value)){
strangeOrder(t.left);
strangeOrder(t.right);
print(t.value);
}
else{
print(t.value);
strangeOrder(t.right);
strangeOrder(t.left);
}
}
}

What is the complexity of this traversal for a binary search tree with n nodes?
 A O(log n) B O(n) C O(1) D O(n log n)
Data Structure
Question 3 Explanation:
 Question 4
Consider a BST containing $N$ nodes, time complexity of printing out the values stored in all of the leaf nodes in ascending order is
 A $\Theta (N \log N)$ B $\Theta (N^2)$ C $\Theta (N)$ D $\Theta (\log N)$
Data Structure
Question 4 Explanation:
Do an inorder traversal , at each node, if both of its children are NULL, print it out. Checking for NULL is constant timeoperation. Must visit each node once. So $\Theta (N)$ for traversal. Hence, ans is $\Theta (N)$.
Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 5
Two binary search tree $t_1$ and $t_2$ are equivalent if they contain exactly the same elements. That is, for all $x \in t_1,x \in t_2$, and for all $y \in t_1, y \in t_1$. What is the time complexity of an efficient algorithm to determine if BSTs $t_1$ and $t_2$ are equivalent.
Assume $|t_1|=|t_2|=n$.
 A $\Theta (n \log n)$ B $\Theta (n^2)$ C $\Theta (n)$ D $\Theta (\log n)$
Data Structure
Question 5 Explanation:
One solution is to read the elements of each tree into a sorted list using an in-order walk, and compare the resulting lists for equality. This algorithm runs in $\Theta (n)$.
Another $\Theta (n)$ solution is to put all of the elements of each tree into a hash table, and compare the resulting tables.
Click to Join Our Telegram Group for Latest Update of MOCK TEST

There are 5 questions to complete.

Suggested Mock Test For You.

ALL FREE Mock Test of GATE CSE

GATE CSE Previous Years Questions on Binary Search Tree

GATE CSE Previous Years Questions on Data Structure

## Graph Traversal (BFS and DFS) Mock Test-1

 Question 1
Which of the follwing is/are TRUE?

S1: In a weighted undirected graph $G = (V, E, w)$, breadth-first search from a vertex $s$ finds single-source shortest paths from $s$ (via parent pointers) in $O(V + E)$ time.

S2: In a weighted undirected tree $G = (V, E, w)$, breadth-first search from a vertex $s$ finds single-source shortest paths from $s$ (via parent pointers) in $O(V + E)$ time.
 A S1 is TRUE and S2 is FALSE B S1 is FALSE and S2 is TRUE C S1 and S2 are TRUE D S1 and S2 are FALSE
Algorithm
Question 1 Explanation:
S1 is FALSE
Only in unweighted graphs.

S2 is TRUE
True. In a tree, there is only one path between two vertices, and breadth-first search finds it.
Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 2
Which of the follwing is/are TRUE?

S1: The depth of any DFS tree rooted at a vertex is at least as much as the depth of any BFS tree rooted at the same vertex.

S2: In an unweighted graph where the distance between any two vertices is at most T, any BFS tree has depth at most T, but a DFS tree might have larger depth.
 A S1 is TRUE and S2 is FALSE B S1 is FALSE and S2 is TRUE C S1 and S2 are TRUE D S1 and S2 are FALSE
Algorithm
Question 2 Explanation:
S1 is TRUE
Since BFS finds paths using the fewest number of edges, the BFS depth of any vertex is at least as small as the DFS depth of the same vertex. Thus, the DFS tree has a greater or equal depth.

S2 is TRUE
TRUE. Since all vertices are connected by a path with at most T edges, and since BFS always finds the path with the fewest edges, the BFS tree will have depth at most T. A DFS tree may have depth up to V-1 (for example, in a complete graph).
Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 3
Which of the follwing is/are TRUE?

S1: Suppose we do a DFS on a directed graph G. If we remove all of the back edges found, the resulting graph is now acyclic.

S2: For a directed graph, the absence of back edges with respect to a BFS tree implies that the graph is acyclic.
 A S1 is TRUE and S2 is FALSE B S1 is FALSE and S2 is TRUE C S1 and S2 are TRUE D S1 and S2 are FALSE
Algorithm
Question 3 Explanation:
S1 is TRUE
If DFS finds no back edges, then the graph is acyclic. Removing any back edges found doesn't change the traversal order of DFS, so running DFS again on the modified graph would produce no back edges.

S2 is FLASE
It is true that the absence of back edges with respect to a DFS tree implies that the graph is acyclic. However, the same is not true for a BFS tree. There may be cross edges which go from one branch of the BFS tree to a lower level of another branch of the BFS tree. It is possible to construct a cycle using such cross edges (which decrease the level) and using forward edges (which increase the level)
Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 4
Perform a depth-first search on the following graph starting at A. Label every edge in the graph with T if it's a tree edge, B if it's a back edge, F if it's a forward edge, and C if it's a cross edge.
Which of the following is true for B,F and C?

NOTE: Whenever faced with a decision of which node to pick from a set of nodes, pick the node whose label occurs earliest in the alphabet.

 A B : {(E,C)}, C : {(E,C),(C,G)}, F : {(E,G)} B B : {(C,A)}, C : {(F,C)}, F : {(E,G),(F,G)} C B : {(C,A)}, C : {(F,C),(F,G)}, F : {(E,G)} D B : {(C,A)}, C : {}, F : {(E,G),(F,C),(F,G)}
Algorithm
Question 4 Explanation:

Tree Edge: It is an edge which is present in the tree obtained after applying DFS on the graph.
Forward edge: (u, v), where v is a descendant of u, but not a tree edge .It is a non-tree edge that connects a vertex to a descendent in a DFS-tree.
Back edge: (u, v), where v is a ancestor of u, but not a tree edge. It is a non-tree edge that connects a vertex to ancestor in a DFS-tree.
Cross Edge: It is a edge which connects two node such that they do not have any ancestor and a descendant relationship between them in DFS Tree. Reference : https://courses.csail.mit.edu/6.006/fall11/rec/rec14.pdf
MIT faculty Video Reference
Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 5
Which of the following statements is/are correct?

S1 : If a depth-first search on a directed graph $G = (V, E)$ produces exactly one back edge, then it is possible to choose an edge $e \in E$ such that the graph $G'= (V, E - {e})$ is acyclic.
S2 : If a directed graph $G$ is cyclic but can be made acyclic by removing one edge, then a depth-first search in $G$ will encounter exactly one back edge.
 A S1 is True and S2 is False B S1 is False and S2 is True C S1 and S2 are False D S1 and S2 are True
Algorithm
Question 5 Explanation:
S1 is TRUE.
Removing the back edge will result in a graph with no back edges, and thus a graph with no cycles (as every graph with at least one cycle has at least one back edge).
Notice that a graph can have two cycles but a single back edge, thus removing some edge that disrupts that cycle is insufficient, you have to remove specifically the back edge.
For example, in graph $G = (V, E) = ({a, b, c}, {(a, b), (b, c), (a, c), (c, a)})$, there are two cycles $[a, b, c, a]$ and $[a, c, a]$, but only one back edge $(c, a)$. Removing edge $(b, c)$ disrupts one of the cycles that gave rise to the back edge $([a, b, c, a])$, but another cycle remains, $[a, c, a]$

S2 is FALSE
You can have multiple back edges, yet it can be possible to remove one edge that destroys all cycles. For example, in graph $G = (V, E) = ({a, b, c}, {(a, b), (b, c), (b, a), (c, a)})$, there are two cycles $([a, b, a]$ and $[a, b, c, a])$ and a DFS from a in $G$ returns two back edges $((b, a)$ and $(c, a))$, but a single removal of edge $(a, b)$ can disrupt both cycles, making the resulting graph acyclic.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

There are 5 questions to complete.

Suggested Mock Test For You.

ALL FREE Mock Test of GATE CSE

GATE CSE Previous Years Questions on Graph Traversal

GATE CSE Previous Years Questions on Algorithm

## Shortest Path Algorithm Mock Test – 2

 Question 1
Consider the following strategy to solve the single source shortest path problem with edge weights from source $s$.

1. Replace each edge with weight $w$ by $w$ edges of weight $1$ connected by new intermediate nodes
2. Run BFS(s) on the modified graph to find the shortest path to each of the original vertices in the graph.

Which of the following statements is correct?
 A This strategy will not solve the problem correctly. B This strategy will only work if the graph is acyclic. C This strategy will solve the problem correctly and is as efficient as Dijkstra's algorithm. D This strategy will solve the problem correctly but is not as efficient as Dijkstra's algorithm.
Algorithm
Question 1 Explanation:
The strategy is sound, but the size of the graph will be proportional to the edge weights in the original graph, so the complexity will increase.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 2
Consider the following strategy to convert an undirected graph with negative edge weights to one that does not have negative edge weights. Let the maximum magnitude negative edge weight in the graph be $-k$. Then, for each edge in the graph with weight $w$, update the weight to $w+k+1$. Consider the following claim:

To solve the shortest path problem in the original graph, we can run Dijkstra's algorithm on the modified graph and subtract the added weights to get the original distances.

Which of the following is NOT correct?
 A The claim is true for connected acyclic graphs. B The claim is true for all graphs. C The claim is not true in general for graphs with cycles. D The claim is not true in general.
Algorithm
Question 2 Explanation:
Adding a weight to each edge increases the weight of a path proportional to the number of edges, so "long" shortest paths (in terms no of edges) get penalized.
In a tree (connected acyclic graph), there is only one path between any pair of nodes, so the shortest path is invariant.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 3
Suppose you have a directed acyclic graph with $n$ vertices and $O(n)$ edges, all having nonnegative weights. Running time (in form of $n$) of an efficient algorithm for finding the shortest path to each vertex from a single source is
 A $O(n)$ B $O(n \log n)$ C $O(n^2)$ D $O(n^2 \log n)$
Algorithm
Question 3 Explanation:
The given conditions allow us to use either the DAG shortest paths algorithm or Dijkstra's. DAG shortest paths runs in $\Theta (V+E)=\Theta (n)$, and Dijkstra's runs in $O((V + E) \log V )$, or $O(V \log V + E)$ if using a Fibonacci heap. In either case, Dijkstra's runs in $O(n \log n)$. DAG shortest paths is faster in this case
https://www.cs.bgu.ac.il/~ds182/wiki.files/14-shortest_paths.pdf

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 4
Which of the following Statemets is/are TRUE?

S1: Consider two positively weighted graphs $G = (V; E; w)$ and $G_0 = (V; E; w_0)$ with the same vertices $V$ and edges $E$ such that, for any edge $e$ in $E$, we have $w_0(e) = w(e)^2$. For any two vertices $u, v$ in $V$ , any shortest path between $u$ and $v$ in $G_0$ is also a shortest path in $G$.

S2: If the priority queue in Dijkstra's algorithm is implemented using a sorted linked list (where the list is kept sorted after each priority queue operation), then Dijkstra's algorithm would run in $O(ElgV +V lgV)$ time.
 A S1 is True and S2 is False B S1 is False and S2 is True C S1 and S2 are False D S1 and S2 are True
Algorithm
Question 4 Explanation:
S1 is FALSE
Assume we have two paths in $G$ as (1) $path: u-x-v : 4$ with $w(u,x)=2,w(x,v)=2$ (2)path: u-v:3 with $w(u,v)=3$. The first one is shorter in $G_0$ while the second one is shorter in $G$.

S2 is FLASE
The list can take $\Theta (V)$ time to insert a node, and there are $(V)$ nodes to insert, for a running time of $\Omega (V^2)$. In addition, the $\Theta (E)$ calls to decrease-key can each take $\Theta (V)$ time for a total running time of $\Theta ((V + E)V )$.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 5
Which of the following Statemets is/are TRUE?

S1: Given a graph G = (V, E) with positive edge weights, the Bellman-Ford algorithm and Dijkstra's algorithm can produce different shortest-path trees despite always producing the same shortest-path weights.

S2: Dijkstra's algorithm may not terminate if the graph contains negative-weight
 A S1 is True and S2 is False B S1 is False and S2 is True C S1 and S2 are False D S1 and S2 are True
Algorithm
Question 5 Explanation:
S1 is TRUE
Both algorithms are guaranteed to produce the same shortestpath weight, but if there are multiple shortest paths, Dijkstra's will choose the shortest path according to the greedy strategy, and Bellman-Ford will choose the shortest path depending on the order of relaxations, and the two shortest path trees may be different.

S2 is FLASE
It always terminates after |E| relaxations and |V|+|E| priority queue operations, but may produce incorrect results.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

There are 5 questions to complete.

Suggested FREE Mock Test For you.

Shortest Path Algorithm Mock Test – 1

ALL FREE Mock Test of GATE CSE

GATE CSE Previous Years Questions on Shortest Path Algorithm

GATE CSE Previous Years Questions on Algorithm

## Graph Traversal (BFS and DFS)

 Question 1
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.
Let T be a DFS tree obtained by doing DFS in a connected undirected graph G.
Which of the following options is/are correct?
 A Root of T can never be an articulation point in G. B Root of T is an articulation point in G if and only if it has 2 or more children. C A leaf of T can be an articulation point in G. D If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.
GATE CSE 2021 SET-1   Algorithm
Question 1 Explanation:
 Question 2
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4 ,v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7 }. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?
 A v2v4 B v1v4 C v4v5 D v3v4
ISRO CSE 2020   Algorithm
Question 2 Explanation:
 Question 3
Which of the following is application of Breath First Search on the graph?
 A Finding diameter of the graph B Finding bipartite graph C Both (A) and (B) D None of the above
ISRO CSE 2018   Algorithm
Question 3 Explanation:
 Question 4
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements.

(I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)
(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |i-j|=1.

Which of the statements above must necessarily be true?
 A I only B II only C Both I and II D Neither I nor II
GATE CSE 2018   Algorithm
Question 4 Explanation:
 Question 5
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?
 A MNOPQR B NQMPOR C QMNROP D POQNMR
GATE CSE 2017 SET-2   Algorithm
Question 5 Explanation:
 Question 6
Breadth First Search(BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is______ .
 A 16 B 15 C 31 D 32
GATE CSE 2016 SET-2   Algorithm
Question 6 Explanation:
 Question 7
Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is
 A 4 B 5 C 6 D 7
GATE CSE 2016 SET-1   Algorithm
Question 7 Explanation:
 Question 8
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For $x \in V$, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)-d(v)?
 A -1 B 0 C 1 D 2
GATE CSE 2015 SET-1   Algorithm
Question 8 Explanation:
 Question 9
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.
 A 16 B 19 C 17 D 20
GATE CSE 2014 SET-3   Algorithm
Question 9 Explanation:
 Question 10
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
 A $\Theta (n)$ B $\Theta (n+m)$ C $\Theta (n^{2})$ D $\Theta (m^{2})$
GATE CSE 2014 SET-1   Algorithm
Question 10 Explanation:
There are 10 questions to complete.

## General Aptitude

 Question 1
In an equilateral triangle PQR, side PQ is divided into four equal parts, side QR is divided into six equal parts and side PR is divided into eight equals parts. The length of each subdivided part in cm is an integer. The minimum area of the triangle PQR possible, in $cm^2$, is
 A 18 B 24 C $48 \sqrt{3}$ D $144 \sqrt{3}$
GATE CE 2021 SET-2      Numerical Ability
Question 1 Explanation:

For $\left(\frac{a}{4}, \frac{a}{6}, \frac{a}{8}\right)$ to be integer, a must be LCM of 4, 6 and 8. So a = 24
$\text { Area }=\frac{\sqrt{3}}{4} a^{2}=\frac{\sqrt{3}}{4} \times 24^{2}=144 \sqrt{3}$
 Question 2

In the figure shown above, PQRS is a square. The shaded portion is formed by the intersection of sectors of circles with radius equal to the side of the square and centers at S and Q.
The probability that any point picked randomly within the square falls in the shaded area is __________
 A $4-\frac{\pi}{2}$ B $\frac{1}{2}$ C $\frac{\pi}{2}-1$ D $\frac{\pi}{4}$
GATE CE 2021 SET-2      Numerical Ability
Question 2 Explanation:
\begin{aligned} \text { Probability } &=\frac{f A}{T A} \\ f A &=\left(\frac{\pi r^{2}}{4}-\frac{r^{2}}{2}\right) \times 2 \\ \frac{f A}{T A} &=\frac{\left(\frac{\pi r^{2}}{4}-\frac{r^{2}}{2}\right) \times 2}{r^{2}}=\left(\frac{\pi}{2}-1\right) \end{aligned}
 Question 3
1.Some football players play cricket.
2.All cricket players play hockey.
Among the options given below, the statement that logically follows from the two statements 1 and 2 above, is :
 A No football player plays hockey B Some football players play hockey C All football players play hockey D All hockey players play football
GATE CE 2021 SET-2      Verbal Ability
Question 3 Explanation:

 Question 4
The author said, "Musicians rehearse before their concerts. Actors rehearse their roles before the opening of a new play. On the other hand, I find it strange that many public speakers think they can just walk onto the stage and start speaking. In my opinion, it is no less important for public speaker to rehearse their talks."
Based on the above passage., which one of the following is TRUE?
 A The author is of the opinion that rehearsing is important for musicians, actors and public speakers B The author is of the opinion that rehearsing is less important for public speakers than for musicians and actors C The author is of the opinion that rehearsing is more important only for musicians than public speakers D The author is of the opinion that rehearsal is more important for actors than musicians
GATE CE 2021 SET-2      Verbal Ability
Question 4 Explanation:
The last sentence of the passage decides the answer with the key words "No Less Important".
 Question 5
On a planar field, you travelled 3 units East from a point O. Next you travelled 4 units South to arrive at point P. Then you travelled from P in the North-East direction such that you arrive at a point that is 6 units East of point O. Next, you travelled in the North-West direction, so that you arrive at point Q that is 8 units North of point P.
The distance of point Q to point O, in the same units, should be _____________
 A 3 B 4 C 5 D 6
GATE CE 2021 SET-2      Numerical Ability
Question 5 Explanation:

$O Q=\sqrt{3^{2}+4^{2}}=5$
 Question 6
Four persons P, Q, R and S are to be seated in a row. R should not be seated at the second position from the left end of the row. The number of distinct seating arrangements possible is:
 A 6 B 9 C 18 D 24
GATE CE 2021 SET-2      Numerical Ability
Question 6 Explanation:
Number of arrangements $=3 \times 3 !=18$
 Question 7
$\oplus$ and $\odot$ are two operators on numbers p and q such that $p \odot q=p-q$, and $p \oplus q=p \times q$
Then, $(9 \odot(6 \oplus 7)) \odot(7 \oplus(6 \odot 5))=$
 A 40 B -26 C -33 D -40
GATE CE 2021 SET-2      Numerical Ability
Question 7 Explanation:
\begin{aligned} [9-(6 \times 7)]-[7 \times 1] &=-33-7 \\ &=-40 \end{aligned}
 Question 8
Two identical cube shaped dice each with faces numbered 1 to 6 are rolled simultaneously. The probability that an even number is rolled out on each dice is:
 A $\frac{1}{36}$ B $\frac{1}{12}$ C $\frac{1}{8}$ D $\frac{1}{4}$
GATE CE 2021 SET-2      Numerical Ability
Question 8 Explanation:
Probability of getting even number on a dice$=\frac{3}{6}=\frac{1}{2}$
$\therefore$Two dice are rolled simultaneously,
Hence required probability $=\frac{1}{2} \times \frac{1}{2}=\frac{1}{4}$
 Question 9

The mirror image of the above text about X-axis is

 A A B B C C D D
GATE CE 2021 SET-2      Numerical Ability
 Question 10
i. Arun and Aparna are here.
ii. Arun and Aparna is here.
iii. Arun's families is here.
iv. Arun's family is here.

Which of the above sentences are grammatically CORRECT?
 A (i) and (ii) B (i) and (iv) C (ii) and (iv) D (iii) and (iv)
GATE CE 2021 SET-2      Verbal Ability
Question 10 Explanation:
Two subject joined with 'and' become plural and hence plural verb is there in first statement, in fourth sentence the subject is family which is singular and takes singular verb.

There are 10 questions to complete.

## Verbal Ability

 Question 1
The world is going through the worst pandemic in the past hundred years. The air travel industry is facing a crisis, as the resulting quarantine requirement for travelers led to weak demand.
In relation to the first sentence above, what does the second sentence do?
 A Restates an idea from the first sentence. B Second sentence entirely contradicts the first sentence. C The two statements are unrelated. D States an effect of the first sentence.
GATE ME 2021 SET-2   General Aptitude
Question 1 Explanation:
First option is wrong because second sentence does not contradict the first sentence. Third option is wrong because two sentences are related. Fourth option is wrong because the second sentence does not repeat the first one.
Hence second option is correct which shows the result of the cause.
 Question 2
Given below are two statements 1 and 2, and two conclusions I and II.

Statement 1: All entrepreneurs are wealthy.
Statement 2: All wealthy are risk seekers.

Conclusion I: All risk seekers are wealthy.
Conclusion II: Only some entrepreneurs are risk seekers.

Based on the above statements and conclusions, which one of the following options is CORRECT?
 A Only conclusion I is correct B Only conclusion II is correct C Neither conclusion I nor II is correct D Both conclusions I and II are correct
GATE ME 2021 SET-2   General Aptitude
Question 2 Explanation:
Possible cases are:

Conclusion-I is incorrect becaue some risk seeker are wealthy.
Conclusion-II is also incorrect because all the entrepreneurs are risk seeker as well as wealthy
 Question 3
Consider the following sentences:

(i) The number of candidates who appear for the GATE examination is staggering.
(ii) A number of candidates from my class are appearing for the GATE examination.
(iii) The number of candidates who appear for the GATE examination are staggering.
(iv) A number of candidates from my class is appearing for the GATE examination.

Which of the above sentences are grammatically CORRECT?
 A (i) and (ii) B (i) and (iii) C (ii) and (iii) D (ii) and (iv)
GATE ME 2021 SET-2   General Aptitude
Question 3 Explanation:
"The number of" is singular and it takes singular verb. "A number of " is plural and it takes plural verb.
 Question 4
Oxpeckers and rhinos manifest a symbiotic relationship in the wild. The oxpeckers warn the rhinos about approaching poachers, thus possibly saving the lives of the rhinos. Oxpeckers also feed on the parasitic ticks found on rhinos.
In the symbiotic relationship described above, the primary benefits for oxpeckers and rhinos respectively are,
 A Oxpeckers get a food source, rhinos have no benefit. B Oxpeckers save their habitat from poachers while the rhinos have no benefit. C Oxpeckers get a food source, rhinos may be saved from the poachers. D Oxpeckers save the lives of poachers, rhinos save their own lives.
GATE ME 2021 SET-1   General Aptitude
Question 4 Explanation:
Option (A) and (B) are weekend by expression 'rhinos have no benefit'. Oxpeckers do not save life of poachers, so option (D) is incorrect.
Hence, option (C) is correct.
 Question 5
"The increased consumption of leafy vegetables in the recent months is a clear indication that the people in the state have begun to lead a healthy lifestyle"

Which of the following can be logically inferred from the information presented in the above statement?
 A The people in the state did not consume leafy vegetables earlier. B Consumption of leafy vegetables may not be the only indicator of healthy lifestyle. C Leading a healthy lifestyle is related to a diet with leafy vegetables. D The people in the state have increased awareness of health hazards causing by consumption of junk foods.
GATE ME 2021 SET-1   General Aptitude
Question 5 Explanation:
The last sentence of the passage is reflecting in option (c) only.
 Question 6
Ms. X came out of a building through its front door to find her shadow due to the morning sun falling to her right side with the building to her back. From this, it can be inferred that building is facing _____
 A North B East C West D South
GATE ME 2021 SET-1   General Aptitude
Question 6 Explanation:
Morning sun is falling from east then the shadow will fall to the west. So west should be on the right side of Ms. X. So Ms. X came out towards south. Hence, her building is facing south.
 Question 7
Consider the following sentences:

(i) After his surgery, Raja hardly could walk.
(ii) After his surgery, Raja could barely walk.
(iii) After his surgery, Raja barely could walk.
(iv) After his surgery, Raja could hardly walk.

Which of the above sentences are grammatically CORRECT
 A (i) and (ii) B (i) and (iii) C (iii) and (iv) D (ii) and (iv)
GATE ME 2021 SET-1   General Aptitude
Question 7 Explanation:
Hardly/Scarcely/Barely have same sense that is negative and they are used after the verb (could barely and could hardly).
 Question 8
Climate change and resilience deal with two aspects - reduction of sources of non-renewable energy resources and reducing vulnerability of climate change aspects. The terms 'mitigation' and 'adaptation' are used to refer to these aspects, respectively.
Which of the following assertions is best supported by the above information?
 A Mitigation deals with consequences of climate change B Adaptation deals with causes of climate change C Mitigation deals with actions taken to reduce the use of fossil fuels. D Adaptation deals with actions taken to combat green-house gas emissions
GATE ME 2020 SET-2   General Aptitude
Question 8 Explanation:
 Question 9
Select the word that fits the analogy:
White: Whitening : : Light : _____
 A Lightning B Lightening C CLighting D Enlightening
GATE ME 2020 SET-2   General Aptitude
Question 9 Explanation:
 Question 10
The recent measures to improve the output would ______ the level of production to our satisfaction.
 A increase B decrease C Cspeed D equalise
GATE ME 2020 SET-2   General Aptitude
Question 10 Explanation:

There are 10 questions to complete.

## Verbal Ability

 Question 1
1.Some football players play cricket.
2.All cricket players play hockey.
Among the options given below, the statement that logically follows from the two statements 1 and 2 above, is :
 A No football player plays hockey B Some football players play hockey C All football players play hockey D All hockey players play football
GATE CE 2021 SET-2   General Aptitude
Question 1 Explanation:

 Question 2
The author said, "Musicians rehearse before their concerts. Actors rehearse their roles before the opening of a new play. On the other hand, I find it strange that many public speakers think they can just walk onto the stage and start speaking. In my opinion, it is no less important for public speaker to rehearse their talks."
Based on the above passage., which one of the following is TRUE?
 A The author is of the opinion that rehearsing is important for musicians, actors and public speakers B The author is of the opinion that rehearsing is less important for public speakers than for musicians and actors C The author is of the opinion that rehearsing is more important only for musicians than public speakers D The author is of the opinion that rehearsal is more important for actors than musicians
GATE CE 2021 SET-2   General Aptitude
Question 2 Explanation:
The last sentence of the passage decides the answer with the key words "No Less Important".
 Question 3
i. Arun and Aparna are here.
ii. Arun and Aparna is here.
iii. Arun's families is here.
iv. Arun's family is here.

Which of the above sentences are grammatically CORRECT?
 A (i) and (ii) B (i) and (iv) C (ii) and (iv) D (iii) and (iv)
GATE CE 2021 SET-2   General Aptitude
Question 3 Explanation:
Two subject joined with 'and' become plural and hence plural verb is there in first statement, in fourth sentence the subject is family which is singular and takes singular verb.
 Question 4
Humans have the ability to construct worlds entirely in their minds, which don't exist in the physical world. So far as we know, no other species possesses this ability. This skill is so important that we have different words to refer to its different flavors, such as imagination, invention and innovation.
Based on the above passage, which one of the following is TRUE?
 A No species possess the ability to construct worlds in their minds B The terms imagination, invention and innovation refer to unrelated skills C We do not know of any species other than humans who possess the ability to construct mental worlds D Imagination, invention and innovation are unrelated to the ability to construct mental worlds
GATE CE 2021 SET-1   General Aptitude
Question 4 Explanation:
Option (b) and (d) are weekend by the word 'UNRELATED SKILLS'. Option (c) is weekend by the expression, no species posses the ability.
Hence answer is option (a) which reflects the information given in the passage.
 Question 5
Statement: Either P marries Q or X marries Y
Among the options below, the logical NEGATION of the above statement is :
 A P does not marry Q and X marries Y B Neither P marries Q nor X marries Y C X does not marry Y and P marries Q D P marries Q and X marries Y
GATE CE 2021 SET-1   General Aptitude
Question 5 Explanation:
The statement says only one of these two action will happen, it's NEGATION should be a confirmed action, hence option (c) is the answer.
 Question 6
Getting to the top is _____ than staying on top.
 A more easy B much easy C easiest D easier
GATE CE 2021 SET-1   General Aptitude
Question 6 Explanation:
When the comparison is between two things we use the second degree of the adjective.The degree form of easy are: (easy - easier - easiest)
 Question 7
Nominal interest rate is defined as the amount paid by the borrower to the lender for using the borrowed amount for a specific period of time. Real interest rate calculated on the basis of actual value (inflation-adjusted), is approximately equal to the difference between nominal rate and expected rate of inflation in the economy.
Which of the following assertions is best supported by the above information?
 A Under high inflation, real interest rate is low and borrowers get benefited B Under low inflation, real interest rate is high and borrowers get benefited C Under high inflation, real interest rate is low and lenders get benefited D Under low inflation, real interest rate is low and borrowers get benefited
GATE CE 2020 SET-2   General Aptitude
 Question 8
After the inauguration of the new building, the Head of the Department (HoD) collated faculty preferences for office space. P wanted a room adjacent to the lab. Q wanted to be close to the lift. R wanted a view of the playground and S wanted a corner office.
Assuming that everyone was satisfied, which among the following shows a possible allocation?

 A A B B C C D D
GATE CE 2020 SET-2   General Aptitude
 Question 9
Select the word that fits the analogy:
Partial : Impartial :: Popular: _______
 A Impopular B Dispopular C Mispopular D Unpopular
GATE CE 2020 SET-2   General Aptitude
 Question 10
Select the most appropriate word that can replace the underlined word without changing the meaning of the sentence:
Now-a-days, most children have a tendency to belittle the legitimate concerns of their parents.
 A disparage B applaud C reduce D begrudge
GATE CE 2020 SET-2   General Aptitude
There are 10 questions to complete.

## Numerical Ability

 Question 1
Consider a square sheet of side 1 unit. The sheet is first folded along the main diagonal. This is followed by a fold along its line of symmetry. The resulting folded shape is again folded along its line of symmetry. The area of each face of the final folded shape, in square units, equal to _____
 A $\frac{1}{4}$ B $\frac{1}{8}$ C $\frac{1}{16}$ D $\frac{1}{32}$
GATE ME 2021 SET-2   General Aptitude
Question 1 Explanation:

Area$=\frac{1}{2} \times \frac{1}{2} \times \frac{1}{2}=\frac{1}{8}$
 Question 2

The ratio of the area of the inscribed circle to the area of the circumscribed circle of an equilateral triangle is
 A $\frac{1}{8}$ B $\frac{1}{6}$ C $\frac{1}{4}$ D $\frac{1}{2}$
GATE ME 2021 SET-2   General Aptitude
Question 2 Explanation:

\begin{aligned} \sin 30^{\circ} &=\frac{r}{R} \\ \text { Area ratio } &=\frac{\pi r^{2}}{\pi R^{2}}=\sin ^{2} 30=\frac{1}{4} \end{aligned}
 Question 3
A box contains 15 blue balls and 45 black balls. If 2 balls are selected randomly, without replacement, the probability of an outcome in which the first selected is a blue ball and the second selected is a black ball, is ____
 A $\frac{3}{16}$ B $\frac{45}{236}$ C $\frac{1}{4}$ D $\frac{3}{4}$
GATE ME 2021 SET-2   General Aptitude
Question 3 Explanation:
The probability of first ball is blue and second ball is black is given as,
$P=\frac{15}{60} \times \frac{45}{59}=\frac{45}{236}$
 Question 4
The front door of Mr. X's house faces East. Mr. X leaves the house, walking 50 m straight from the back door that is situated directly opposite to the front door. He then turns to his right, walks for another 50 m and stops. The direction of the point Mr. X is now located at with respect to the starting point is ____
 A South-East B North-East C West D North-West
GATE ME 2021 SET-2   General Aptitude
Question 4 Explanation:

 Question 5
If $\oplus \div \odot =2;\;\oplus \div \triangle =3;\;\odot +\triangle =5;\;\triangle \times \otimes =10$,
Then, the value of $( \otimes - \oplus)^2$ is
 A 0 B 1 C 4 D 16
GATE ME 2021 SET-2   General Aptitude
Question 5 Explanation:
\begin{aligned} \frac{\oplus}{\odot}&=2, \frac{\oplus}{\Delta}=3 \\ \therefore \qquad\frac{\Delta}{\odot}&=\frac{2}{3} &\ldots(1)\\ \odot+\Delta&=5 &\ldots(2)\\ \text{From (1) and (2)}\\ \Delta&=2, \odot=3\\ \text{and}\\ \oplus &=6,2 \times \otimes=10 \\ \otimes &=5 \\ \Rightarrow \quad(\otimes-\oplus)^{2}&=(5-6)^{2} =1 \end{aligned}
 Question 6
A digital watch X beeps every 30 seconds while watch Y beeps every 32 seconds. They beeped together at 10 AM. The immediate next time that they will beep together is ____
 A 10.08 AM B 10.42 AM C 11.00 AM D 10.00 PM
GATE ME 2021 SET-2   General Aptitude
Question 6 Explanation:
LCM of (30 and 32) is 480
480 seconds = 8 minutes
Hence, time will be 10.08 pm
 Question 7
Five persons P, Q, R, S and T are to be seated in a row, all facing the same direction, but not necessarily in the same order. P and T cannot be seated at either end of the row. P should not be seated adjacent to S. R is to be seated at the second position from the left end of the row. The number of distinct seating arrangements possible is:
 A 2 B 3 C 4 D 5
GATE ME 2021 SET-2   General Aptitude
Question 7 Explanation:
The possible distinct arrangement are
S R P T A, A R P T S, S R T P A
Hence, number of distinct sitting arrangement. = 3
 Question 8
Five persons P, Q, R, S and T are sitting in a row not necessarily in the same order. Q and R are separated by one person, and S should not be seated adjacent to Q.
The number of distinct seating arrangements possible is:
 A 4 B 8 C 10 D 16
GATE ME 2021 SET-1   General Aptitude
Question 8 Explanation:
The possible seating arrangements are
QPRST, QTRSP
QPRTS, QTRPS
PQTRS, TQPRS
SPQTR, STQPR
RPQTS, RTQPS
SRPQT, SRTQP
SPRTQ, STRPQ
PSRTQ, TSRPQ
Hence, total seating arrangements are 16
 Question 9

The distribution of employees at the rank of executives, across different companies C1, C2,... ,C6 is presented in the chart given above. The ratio of executives with a management degree to those without a management degree in each of these companies is provided in the table above. The total number of executives across all companies is 10,000.

The total number of management degree holders among the executives in companies C2 and C5 together is .
 A 225 B 600 C 1900 D 2500
GATE ME 2021 SET-1   General Aptitude
Question 9 Explanation:
Number of employee in $C2$ company $=\frac{5}{100} \times 10000=500$
Number of management degree holder employee in $\mathrm{C} 2=\frac{1}{5} \times 500=100$
Number of employee in $\mathrm{C} 5$ company $=\frac{20}{100} \times 10000=2000$
Number of management degree holder employee in $\mathrm{C} 5=\frac{9}{10} \times 2000=1800$
Total management degree holder employee $=100+1800=1900$
 Question 10
The number of hens, ducks and goats in farm P are 65, 91 and 169, respectively. The total number of hens, ducks and goats in a nearby farm Q is 416. The ratio of hens:ducks:goats in farm Q is 5:14:13. All the hens, ducks and goats are sent from farm Q to farm P.
The new ratio of hens:ducks:goats in farm P is
 A 5:07:13 B 5:14:13 C 10:21:26 D 21:10:26
GATE ME 2021 SET-1   General Aptitude
Question 10 Explanation:
In farm P,
Hens =65, Ducks =91, Goats =169
In farm Q,
Hens : Ducks : Goats
5: 14: 13
\begin{aligned} \text { Hens } &=\frac{5}{32} \times 416=65 \\ \text { Ducks }&=\frac{14}{32} \times 416=182\\ \text { Goats }&=\frac{13}{32} \times 416=169 \end{aligned}
$\because$From farm d, hens, ducks and goats are sent to farm P.
\begin{aligned} \therefore \text{ Total hens }&=65+65=130\\ \text { Total ducks } &=91+182=273 \\ \text { Total goats } &=169+169=338 \\ \text { New ratio } &=130: 273: 338 \\ &=10: 21: 26 \end{aligned}

There are 10 questions to complete.