GATE CSE 2000 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2000

MCQ (Single Correct Answer)

-0.3

Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

(1 2 (4 5 6 7))

(1 (2 3 4) 5 6) 7)

(1 (2 3 4)(5 6 7))

(1 (2 3 NULL) (4 5))

GATE CSE 2000

MCQ (Single Correct Answer)

-0.6

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always tree?

LASTIN = LASTPOST

LASTIN = LASTPRE

LASTPRE = LASTPOST

None of the above

GATE CSE 2000

MCQ (Single Correct Answer)

-0.6

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

{u, v} must be an edge in G, and u is a descendant of v in T

{u, v} must be an edge in G, and v is a descendant of u in T

If {u, v} is not an edge in G then u is a leaf in T

If {u, v} is not an edge in G then u and v must have the same parent in T

GATE CSE 2000

MCQ (Single Correct Answer)

-0.6

Given the following relation instance
$$\eqalign{ & X\,\,\,\,\,Y\,\,\,\,\,Z \cr & \,\,1\,\,\,\,\,\,4\,\,\,\,\,\,2 \cr & \,\,1\,\,\,\,\,\,5\,\,\,\,\,\,3 \cr & \,\,1\,\,\,\,\,\,6\,\,\,\,\,\,3 \cr & \,\,3\,\,\,\,\,\,2\,\,\,\,\,\,2 \cr} $$

Which of the following functional dependencies are satisfied by the instance?

$$XY \to Z$$ and $$Z \to Y$$

$$YZ \to X$$ and $$Y \to Z$$

$$YZ \to X$$ and $$X \to Z$$

$$XZ \to Y$$ and $$Y \to X$$

PREVIOUS NEXT

GATE CSE Papers

2023