CSE - PracticePaper

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:

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

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

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.

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

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

Question 1 Explanation:

Question 2

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

Question 2 Explanation:

Question 3

Given below are four statements.

Statement 1: All students are inquisitive.
Statement 2: Some students are inquisitive.
Statement 3: No student is inquisitive.
Statement 4: Some students are not inquisitive.

From the given four statements, find the two statements that CANNOT BE TRUE simultaneously, assuming that there is at least one student in the class.

A	Statement 1 and Statement 3
B	Statement 1 and Statement 2
C	Statement 2 and Statement 4
D	Statement 3 and Statement 4

Question 3 Explanation:

Question 4

The _____ is too high for it to be considered ______

A	fair / fare
B	faer / fair
C	fare / fare
D	fare / fair

Question 4 Explanation:

Question 5

Six students P, Q, R, S, T and U, with distinct heights, compare their heights and make the following observations.

Observation I: S is taller than R.
Observation II: Q is the shortest of all.
Observation III: U is taller than only one student.
Observation IV: T is taller than S but is not the tallest

The number of students that are taller than R is the same as the number of students shorter than ____________.

A	T
B	R
C	S
D	P

Question 5 Explanation:

Question 6

Listening to music during exercise improves performance and reduces discomfort. Scientists researched whether listening to music while studying can help students learn better and the results were inconclusive. Students who needed external stimulation for studying fared worse while students who did not need any external stimulation benefited from music.

Which one of the following statements is the CORRECT inference of the above passage?

A	Listening to music has no effect on learning and a positive effect on physical exercise
B	Listening to music has a clear positive effect both in physical exercise and on learning
C	Listening to music has a clear positive effect on physical exercise. Music has a positive effect on learning only in some students
D	Listening to music has a clear positive effect on learning in all students. Music has a positive effect only in some students who exercise

Question 6 Explanation:

Question 7

Pen : Write :: Knife : _______

Which one of the following options maintains a similar logical relation in the above?

A	Vegetables
B	Sharp
C	Cut
D	Blunt

Question 7 Explanation:

Question 8

Gauri said that she can play the keyboard __________ her sister.

A	as well as
B	as better as
C	as nicest as
D	as worse as

Question 8 Explanation:

Question 9

Some people suggest anti-obesity measures (AOM) such as displaying calorie information in restaurant menus. Such measures sidestep addressing the core problems that cause obesity: poverty and income inequality.

Which one of the following statements summarizes the passage?

A	The proposed AOM addresses the core problems that cause obesity
B	If obesity reduces, poverty will naturally reduce, since obesity causes poverty
C	AOM are addressing the core problems and are likely to succeed
D	AOM are addressing the problem superficially

GATE CSE 2021 SET-1 General Aptitude

Question 9 Explanation:

Question 10

Given below are two statements 1 and 2, and two conclusions I and II

Statement 1: All bacteria are microorganisms.
Statement 2: All pathogens are microorganisms.

Conclusion I: Some pathogens are bacteria.
Conclusion II: All pathogens are not bacteria.

Based on the above statements and conclusions, which one of the following options is logically CORRECT?

A	Only conclusion II is correct
B	Only conclusion IIII is correct
C	Either conclusion II or IIII is correct
D	Neither conclusion II nor IIII is correct

GATE CSE 2021 SET-1 General Aptitude

Question 10 Explanation:

There are 10 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

A plot of land must be divided between four families. They want their individual plots to be similar in shape, not necessarily equal in area. The land has equally spaced poles, marked as dots in the below figure. Two ropes, R1 and R2, are already present and cannot be moved. What is the least number of additional straight ropes needed to create the desired plots? A single rope can pass through three poles that are aligned in a straight line.

A	2
B	4
C	5
D	3

Question 1 Explanation:

Question 2

A box contains five balls of same size and shape. Three of them are green coloured balls and two of them are orange coloured balls. Balls are drawn from the box one at a time. If a green ball is drawn, it is not replaced. If an orange ball is drawn, it is replaced with another orange ball.
First ball is drawn. What is the probability of getting an orange ball in the next draw?

A	$\frac{1}{2}$
B	$\frac{8}{25}$
C	$\frac{19}{50}$
D	$\frac{23}{50}$

Question 2 Explanation:

Question 3

In a recently conducted national entrance test, boys constituted 65% of those who appeared for the test. Girls constituted the remaining candidates and they accounted for 60% of the qualified candidates.
Which one of the following is the correct logical inference based on the information provided in the above passage?

A	Equal number of boys and girls qualified
B	Equal number of boys and girls appeared for the test
C	The number of boys who appeared for the test is less than the number of girls who appeared
D	The number of boys who qualified the test is less than the number of girls who qualified

Question 3 Explanation:

Question 4

A palindrome is a word that reads the same forwards and backwards. In a game of words, a player has the following two plates painted with letters.

From the additional plates given in the options, which one of the combinations of additional plates would allow the player to construct a five-letter palindrome. The player should use all the five plates exactly once. The plates can be rotated in their plane.

A	A
B	B
C	C
D	D

Question 4 Explanation:

Question 5

Let

r

be a root of the equation

x^2+2x+6=0

Then the value of the expression

(r+2)(r+3)(r+4)(r+5)

A	$51$
B	$-51$
C	$126$
D	$-126$

Question 5 Explanation:

Question 6

A function

y(x)

is defined in the interval [0, 1] on the

x-

axis as

y(x)= \left \{ \begin{matrix} 2 &if & 0 \leq x \leq \frac{1}{3} \\ 3& if& \frac{1}{3} \leq x \leq \frac{3}{4} \\ 1& if& \frac{3}{4} \leq x \leq 1 \end{matrix} \right.

Which one of the following is the area under the curve for the interval [0, 1] on the

x-

axis?

A	$\frac{5}{6}$
B	$\frac{6}{5}$
C	$\frac{13}{6}$
D	$\frac{6}{13}$

Question 6 Explanation:

Question 7

The number of units of a product sold in three different years and the respective net profits are presented in the figure above. The cost/unit in Year 3 was Re. 1, which was half the cost/unit in Year 2. The cost/unit in Year 3 was one-third of the cost/unit in Year 1. Taxes were paid on the selling price at 10%, 13%, and 15% respectively for the three years. Net profit is calculated as the difference between the selling price and teh sum of cost and taxes paid in that year.

The ratio of the selling price in Year 2 to the selling price in Year 3 is _________.

A	4:03
B	1:01
C	3:04
D	1:02

Question 7 Explanation:

Question 8

The number of students in three classes is in the ratio 3:13:6. If 18 students are added to each class, the ratio changes to 15:35:21.

The total number of students in all the three classes in the beginning was:

A	22
B	66
C	88
D	110

Question 8 Explanation:

Question 9

A jigsaw puzzle has 2 pieces. One of the pieces is shown above. Which one of the given options for the missing piece when assembled will form a rectangle? The piece can be moved, rotated or flipped to assemble with the above piece.

A	A
B	B
C	C
D	D

Question 9 Explanation:

Question 10

\left( x - \dfrac{1}{2} \right)^2 - \left( x- \dfrac{3}{2} \right) ^2 = x+2

, then the value of

x

is:

A	2
B	4
C	6
D	8

Question 10 Explanation:

There are 10 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

A	2
B	4
C	5
D	3

Question 1 Explanation:

Question 2

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 Verbal Ability

Question 2 Explanation:

Question 3

A	$\frac{1}{2}$
B	$\frac{8}{25}$
C	$\frac{19}{50}$
D	$\frac{23}{50}$

Question 3 Explanation:

Question 4

A	Equal number of boys and girls qualified
B	Equal number of boys and girls appeared for the test
C	The number of boys who appeared for the test is less than the number of girls who appeared
D	The number of boys who qualified the test is less than the number of girls who qualified

Question 4 Explanation:

Question 5

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 Verbal Ability

Question 5 Explanation:

Question 6

A palindrome is a word that reads the same forwards and backwards. In a game of words, a player has the following two plates painted with letters.

A	A
B	B
C	C
D	D

Question 6 Explanation:

Question 7

A	Statement 1 and Statement 3
B	Statement 1 and Statement 2
C	Statement 2 and Statement 4
D	Statement 3 and Statement 4

GATE CSE 2022 Verbal Ability

Question 7 Explanation:

Question 8

Let

r

be a root of the equation

x^2+2x+6=0

Then the value of the expression

(r+2)(r+3)(r+4)(r+5)

A	$51$
B	$-51$
C	$126$
D	$-126$

Question 8 Explanation:

Question 9

A function

y(x)

is defined in the interval [0, 1] on the

x-

axis as

y(x)= \left \{ \begin{matrix} 2 &if & 0 \leq x \leq \frac{1}{3} \\ 3& if& \frac{1}{3} \leq x \leq \frac{3}{4} \\ 1& if& \frac{3}{4} \leq x \leq 1 \end{matrix} \right.

Which one of the following is the area under the curve for the interval [0, 1] on the

x-

axis?

A	$\frac{5}{6}$
B	$\frac{6}{5}$
C	$\frac{13}{6}$
D	$\frac{6}{13}$

Question 9 Explanation:

Question 10

The _____ is too high for it to be considered ______

A	fair / fare
B	faer / fair
C	fare / fare
D	fare / fair

GATE CSE 2022 Verbal Ability

Question 10 Explanation: