CSE - PracticePaper

Question 2

Which one of the following sequences when stored in an array at locations A[1], . . . , A[10] forms a max-heap?

A	23, 17, 10, 6, 13, 14, 1, 5, 7, 12
B	23, 17, 14, 7, 13, 10, 1, 5, 6, 12
C	23, 17, 14, 6, 13, 10, 1, 5, 7, 15
D	23, 14, 17, 1, 10, 13, 16, 12, 7, 5

Data Structure Heap Tree

Question 2 Explanation:

Question 3

Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list.
Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?

A	SLLdel is O(1) and DLLdel is O(n)
B	Both SLLdel and DLLdel are O(log(n))
C	Both SLLdel and DLLdel are O(1)
D	SLLdel is O(n) and DLLdel is O(1)

Data Structure Link List

Question 3 Explanation:

Question 4

Consider the Deterministic Finite-state Automaton (DFA)

A

shown below. The DFA runs on the alphabet {0, 1}, and has the set of states {s, p, q, r}, with s being the start state and p being the only final state.

Which one of the following regular expressions correctly describes the language accepted by

A

A	$1(0^11)^$
B	$0(0 + 1)^*$
C	$1(0 + 11)^*$
D	$1(110^)^$

Theory of Computation Regular Expression

Question 4 Explanation:

Question 5

The Lucas sequence

L_n

is defined by the recurrence relation:

L_n=L_{n-1}+L_{n-2}, \; for \; n\geq 3,

with

L_1=1 \; and \; L_2=3

Which one of the options given is TRUE?

A	$L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n+\left ( \frac{1-\sqrt{5}}{2} \right )^n$
B	$L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n - \left ( \frac{1-\sqrt{5}}{3} \right )^n$
C	$L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n+\left ( \frac{1-\sqrt{5}}{3} \right )^n$
D	$L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n- \left ( \frac{1-\sqrt{5}}{2} \right )^n$

Discrete Mathematics Recurrence

Question 5 Explanation:

There are 5 questions to complete.

Gate 2023 CSE question paper and solution. GATE 2023 Answer Key.

Practice Previous year GATE CSE Topicwise questions with detail Solution.

GATE CSE 2022

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

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	abbab + baaba
B	(abb)ab* + (baa)ba*
C	(abb + baa)(a + b*)
D	(baa + abb)(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.

Data Structure Link List

Question 5 Explanation:

There are 5 questions to complete.

Gate 2022 CSE question paper and solution.

Practice Previous year GATE CSE Topicwise questions with detail Solution.

AVLTree Mock Test-1

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

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

T

such that

|k-x|

is minimized?

A	$\Theta ( n)$
B	$\Theta (\log n)$
C	$\Theta (n \log n)$
D	$\Theta (n^2)$

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

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.

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)

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

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

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.

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

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.

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

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

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

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)

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

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)

There are 5 questions to complete.

Suggested Mock Test For You.

GATE CSE Previous Years Questions on AVL Tree

GATE CSE Previous Years Questions on Data Structure

Binary Search Tree Mock Test -1

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

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

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

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.

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

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

Question 2 Explanation:

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)

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

Question 3 Explanation:

The traversal visits and lists each element once, so it is O(n).

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)$

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

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)

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)$

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

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.

There are 5 questions to complete.

Suggested Mock Test For You.

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

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

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

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.

There are 5 questions to complete.

Suggested Mock Test For You.

GATE CSE Previous Years Questions on Graph Traversal

GATE CSE Previous Years Questions on Algorithm

Shortest Path Algorithm Mock Test – 2

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

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

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

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

E

, we have

w_0(e) = w(e)^2

. For any two vertices

u, v

V

, any shortest path between

u

and

v

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.

Shortest Path Algorithm Mock Test – 1

There are 5 questions to complete.

Suggested FREE Mock Test For you.

GATE CSE Previous Years Questions on Shortest Path Algorithm

GATE CSE Previous Years Questions on Algorithm

Graph Traversal (BFS and DFS)

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

Question 1

Let

U = \{1, 2, 3\}

. Let

2^U

denote the powerset of

U

. Consider an undirected graph

G

whose vertex set is

2^U

. For any

A,B \in 2^U, (A,B)

is an edge in

G

if and only if (i)

A \neq B

, and (ii) either

A \subseteq B

B \subseteq A

. For any vertex

A

G

, the set of all possible orderings in which the vertices of

G

can be visited in a Breadth First Search (BFS) starting from

A

is denoted by

B(A)

.
If

\phi

denotes the empty set, then the cardinality of

B(\phi )

is ____.

A	524
B	63218
C	5040
D	2540

GATE CSE 2023 Algorithm

Question 1 Explanation:

Question 2

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 2 Explanation:

Question 3

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 3 Explanation:

Question 4

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 4 Explanation:

Question 5

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 5 Explanation:

There are 5 questions to complete.

Verbal Ability

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

Question 1

Which one of the following sentence sequences creates a coherent narrative?

(i) Once on the terrace, on her way to her small room in the corner, she notices the man right away.
(ii) She begins to pant by the time she has climbed all the stairs.
(iii) Mina has bought vegetables and rice at the market, so her bags are heavy.
(iv) He was leaning against the parapet, watching the traffic below.

A	(i), (ii), (iv), (iii)
B	(ii), (iii), (i), (iv)
C	(iv), (ii), (i), (iii)
D	(iii), (ii), (i), (iv)

Question 1 Explanation:

Question 2

Kind : _______ : : Often : Frequently
(By word meaning)

A	Mean
B	Type
C	Cruel
D	Kindly

Question 2 Explanation:

Question 3

We reached the station late, and _______ missed the train.

A	near
B	nearly
C	utterly
D	mostly

Question 3 Explanation:

Question 4

The corners and mid-points of the sides of a triangle are named using the distinct letters P, Q, R, S, T and U, but not necessarily in the same order. Consider the following statements:

The line joining P and R is parallel to the line joining Q and S.
P is placed on the side opposite to the corner T.
S and U cannot be placed on the same side.

Which one of the following statements is correct based on the above information?

A	P cannot be placed at a corner
B	S cannot be placed at a corner
C	U cannot be placed at a mid-point
D	R cannot be placed at a corner

GATE CSE 2022 General Aptitude

Question 4 Explanation:

Question 5

Some people believe that "what gets measured, improves". Some others believe that "what gets measured, gets gamed". One possible reason for the difference in the beliefs is the work culture in organizations. In organizations with good work culture, metrics help improve outcomes. However, the same metrics are counterproductive in organizations with poor work culture.
Which one of the following is the CORRECT logical inference based on the information in the above passage?

A	Metrics are useful in organizations with poor work culture
B	Metrics are useful in organizations with good work culture
C	Metrics are always counterproductive in organizations with good work culture
D	Metrics are never useful in organizations with good work culture

GATE CSE 2022 General Aptitude

Question 5 Explanation:

There are 5 questions to complete.

Numerical Ability

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

Question 1

Which one of the options best describes the transformation of the 2-dimensional figure P to Q, and then to R, as shown?

A	Operation 1: A clockwise rotation by $90^{\circ}$ about an axis perpendicular to the plane of the figure Operation 2: A reflection along a horizontal line
B	Operation 1: A counter clockwise rotation by $90^{\circ}$ about an axis perpendicular to the plane of the figure Operation 2: A reflection along a horizontal line
C	Operation 1: A clockwise rotation by $90^{\circ}$ about an axis perpendicular to the plane of the figure Operation 2: A reflection along a vertical line
D	Operation 1: A counter clockwise rotation by $180^{\circ}$ about an axis perpendicular to the plane of the figure Operation 2: A reflection along a vertical line

Question 1 Explanation:

Question 2

f(x)

and

g(y)

are functions of

x

and

y

, respectively, and

f(x)=g(y)

for all real values of

x

and

y

. Which one of the following options is necessarily TRUE for all

x

and

y

A	$f(x)=0 \; and \; g(y)=0$
B	$f(x)= g(y)= constant$
C	$f(x)\neq constant \; and \; g(y)\neq constant$
D	$f(x)+ g(y)=f(x)- g(y)$

Question 2 Explanation:

Question 3

Consider two functions of time

(t)

f(t)=0.01t^2

g(t)=4t

where

0 \lt t \lt \infty

Now consider the following two statements:

(i) For some

t \gt 0, g(t) \gt f(t)

.
(ii) There exists a

T

, such that

f(t) \gt g(t)

for all

t \gt T

.

Which one of the following options is TRUE?

A	only (i) is correct
B	only (ii) is correct
C	both (i) and (ii) are correct
D	neither (i) nor (ii) is correct

Question 3 Explanation:

Question 4

The country of Zombieland is in distress since more than 75% of its working population is suffering from serious health issues. Studies conducted by competent health experts concluded that a complete lack of physical exercise among its working population was one of the leading causes of their health issues. As one of the measures to address the problem, the Government of Zombieland has decided to provide monetary incentives to those who ride bicycles to work.
Based only on the information provided above, which one of the following statements can be logically inferred with certainty?

A	All the working population of Zombieland will henceforth ride bicycles to work.
B	Riding bicycles will ensure that all of the working population of Zombieland is free of health issues.
C	The health experts suggested to the Government of Zombieland to declare riding bicycles as mandatory.
D	The Government of Zombieland believes that riding bicycles is a form of physical exercise.

Question 4 Explanation:

Question 5

Looking at the surface of a smooth 3-dimensional object from the outside, which one of the following options is TRUE?

A	The surface of the object must be concave everywhere.
B	The surface of the object must be convex everywhere.
C	The surface of the object may be concave in some places and convex in other places.
D	The object can have edges, but no corners.

Question 5 Explanation:

There are 5 questions to complete.

General Aptitude

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

Question 1

Which one of the options best describes the transformation of the 2-dimensional figure P to Q, and then to R, as shown?

A	Operation 1: A clockwise rotation by $90^{\circ}$ about an axis perpendicular to the plane of the figure Operation 2: A reflection along a horizontal line
B	Operation 1: A counter clockwise rotation by $90^{\circ}$ about an axis perpendicular to the plane of the figure Operation 2: A reflection along a horizontal line
C	Operation 1: A clockwise rotation by $90^{\circ}$ about an axis perpendicular to the plane of the figure Operation 2: A reflection along a vertical line
D	Operation 1: A counter clockwise rotation by $180^{\circ}$ about an axis perpendicular to the plane of the figure Operation 2: A reflection along a vertical line

Question 1 Explanation:

Question 2

f(x)

and

g(y)

are functions of

x

and

y

, respectively, and

f(x)=g(y)

for all real values of

x

and

y

. Which one of the following options is necessarily TRUE for all

x

and

y

A	$f(x)=0 \; and \; g(y)=0$
B	$f(x)= g(y)= constant$
C	$f(x)\neq constant \; and \; g(y)\neq constant$
D	$f(x)+ g(y)=f(x)- g(y)$

Question 2 Explanation:

Question 3

A	(i), (ii), (iv), (iii)
B	(ii), (iii), (i), (iv)
C	(iv), (ii), (i), (iii)
D	(iii), (ii), (i), (iv)

GATE CSE 2023 Verbal Ability

Question 3 Explanation:

Question 4

Consider two functions of time

(t)

f(t)=0.01t^2

g(t)=4t

where

0 \lt t \lt \infty

Now consider the following two statements:

(i) For some

t \gt 0, g(t) \gt f(t)

.
(ii) There exists a

T

, such that

f(t) \gt g(t)

for all

t \gt T

.

Which one of the following options is TRUE?

A	only (i) is correct
B	only (ii) is correct
C	both (i) and (ii) are correct
D	neither (i) nor (ii) is correct

Question 4 Explanation:

Question 5

A	All the working population of Zombieland will henceforth ride bicycles to work.
B	Riding bicycles will ensure that all of the working population of Zombieland is free of health issues.
C	The health experts suggested to the Government of Zombieland to declare riding bicycles as mandatory.
D	The Government of Zombieland believes that riding bicycles is a form of physical exercise.

Question 5 Explanation: