GATE CSE 2026 Set 1 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2026 Set 1

MCQ (More than One Correct Answer)

-0

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G(V, E)$ as input, where $d[v]$ and $f[v]$ are the discovery time and finishing time, respectively, of the vertex $v \in V$.

DFS(G):
unmark all v ∈ V
t ← 0
for each v ∈ V
    if v is unmarked
        t ← Explore(G, v, t)
    end if
end for

Explore(G, v, t):
    mark v
    t ← t + 1
    d[v] ← t
    for each (v, w) ∈ E
        if w is unmarked
            t ← Explore(G, w, t)
        end if
    end for
    t ← t + 1
    f[v] ← t
    return t

Suppose that the input directed graph $G(V, E)$ is a directed acyclic graph (DAG). For an edge $(u, v) \in E$, which of the following options will NEVER be correct?

$d[u] < d[v] < f[v] < f[u]$

$d[v] < d[u] < f[u] < f[v]$

$d[v] < f[v] < d[u] < f[u]$

$d[u] < d[v] < f[u] < f[v]$

GATE CSE 2026 Set 1

MCQ (More than One Correct Answer)

-0

An undirected, unweighted, simple graph $G(V, E)$ is said to be 2 -colorable if there exists a function $c: V \rightarrow\{0,1\}$ such that for every $(u, v) \in E, c(u) \neq c(v)$.

Which of the following statements about 2-colorable graphs is/are true?

If $G$ is 2-colorable, then $G$ may contain cycles of odd length

If $G$ is 2 -colorable, then $G$ may contain cycles of even length

An optimal algorithm for testing whether $G$ is 2-colorable runs in time $\theta(|V|+|E|)$, if $G$ is represented as an adjacency list

An optimal algorithm for testing whether $G$ is 2-colorable runs in time $\theta(|E| \log |V|)$, if $G$ is represented as an adjacency list

GATE CSE 2026 Set 1

Numerical

-0

The following sequence corresponds to the preorder traversal of a binary search tree:

$$ 50,25,13,40,30,47,75,60,70,80,77 $$

The position of the element 60 in the postorder traversal of $T$ is $\_\_\_\_$ . (answer in integer)

Note: The position begins with 1.

Your input ____

GATE CSE 2026 Set 1

MCQ (More than One Correct Answer)

-0

Let $P, Q, R$ and $S$ be the attributes of a relation in a relational schema. Let $X \rightarrow Y$ indicate functional dependency in the context of a relational database, where $X, Y \subseteq\{P, Q, R, S\}$ Which of the following options is/are always true?

If $(\{P, Q\} \rightarrow\{R\}$ and $\{P\} \rightarrow\{R\})$, then $\{Q\} \rightarrow\{R\}$

If $\{P, Q\} \rightarrow\{R\}$, then $(\{P\} \rightarrow\{R\}$ or $\{Q\} \rightarrow\{R\})$

If $(\{P\} \rightarrow\{R\}$ and $\{Q\} \rightarrow\{S\})$, then $\{P, Q\} \rightarrow\{R, S\}$

If $\{P\} \rightarrow\{R\}$, then $\{P, Q\} \rightarrow\{R\}$

PREVIOUS NEXT

GATE CSE Papers

All year-wise previous year question papers

2026