GATE CSE 2001 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2001

MCQ (Single Correct Answer)

-0.6

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?

d(r, u) < d(r, v)

d(r, u) > d(r, v)

d(r, u)$$ \le $$d(r, v)

None of the above

GATE CSE 2001

MCQ (Single Correct Answer)

-0.6

How many undirected graphs (not necessarily connected) can be constructed out of a given set V = { v₁,v₂,........,v_n } of n vertices?

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

2ⁿ

$$2^\frac{n(n-1)} {2}$$

GATE CSE 2001

MCQ (Single Correct Answer)

-0.6

Which of the following relational calculus expressions is not safe?

$$\left\{t \mid \exists u \in R_1\left(t[A] = u[A]\right) \land \neg \exists s \in R_2 \left(t[A] = s[A]\right)\right\}$$

$$\left\{ t \mid \forall u \in R_1\left(u[A]="x"\Rightarrow \exists s \in R_2\left(t[A] = s[A] \land s[A] = u[A]\right)\right) \right\}$$

$$\left\{t \mid \neg (t \in R_1)\right\}$$

$$\left\{t \mid \exists u \in R_1\left(t[A]=u[A]\right) \land \exists s \in R_2 \left(t[A] = s[A]\right)\right\}$$

GATE CSE 2001

MCQ (Single Correct Answer)

-0.6

$$R(A,B,C,D)$$ is a relation. Which of the following does not have a lossless-join, dependency preserving $$BCNF$$ decomposition?

$$A \to B,\,B \to CD$$

$$A \to B,\,B \to C.\,C \to D$$

$$AB \to C,\,C \to AD$$

$$A \to BCD$$

PREVIOUS NEXT

GATE CSE Papers

All year-wise previous year question papers

2026