GATE CSE 2025 Set 2 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2025 Set 2

MCQ (Single Correct Answer)

-0.67

Consider a binary tree $T$ in which every node has either zero or two children. Let $n>0$ be the number of nodes in $T$. Which ONE of the following is the number of nodes in $T$ that have exactly two children?

$\frac{n-2}{2}$

$\frac{n-1}{2}$

$\frac{n}{2}$

$\frac{n+1}{2}$

GATE CSE 2025 Set 2

MCQ (More than One Correct Answer)

-0

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?

A DFS tree of $G$ is a Shortest Path tree of $G$.

Every non-tree edge of $G$ with respect to a DFS tree is a forward/back edge.

If $(u, v)$ is a non-tree edge of $G$ with respect to a BFS tree, then the distances from the source vertex $s$ to $u$ and $v$ in the BFS tree are within $\pm 1$ of each other.

Both BFS and DFS can be used to find the connected components of $G$.

GATE CSE 2025 Set 2

Numerical

-0

Suppose the values $10,-4,15,30,20,5,60,19$ are inserted in that order into an initially empty binary search tree. Let $T$ be the resulting binary search tree. The number of edges in the path from the node containing 19 to the root node of $T$ is ________ (Answer in integer)

Your input ____

GATE CSE 2025 Set 2

MCQ (Single Correct Answer)

-0.67

A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:

P: Unsorted doubly linked list with pointers to the head node and tail node of the list.

Q: Min-heap implemented using an array.

R: Binary Search Tree.

Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size $n$ of these data structures?

P: $\Theta(1), \mathrm{Q}: \Theta(n), \mathrm{R}: \Theta(n)$

$\mathrm{P}: \Theta(1), \mathrm{Q}: \Theta(n \log n), \mathrm{R}: \Theta(n)$

$\mathrm{P}: \Theta(n), \mathrm{Q}: \Theta(n \log n), \mathrm{R}: \Theta\left(n^2\right)$

$\mathrm{P}: \Theta(1), \mathrm{Q}: \Theta(n), \mathrm{R}: \Theta(n \log n)$

PREVIOUS NEXT

GATE CSE Papers

2025