GATE CS 1989 Q3-ixa — Trees

To determine which statements are FALSE, let us analyze each option individually:

• Statement A: "Overlaying is used to run a program, which is longer than the address space of the computer."
  Analysis: Overlaying is a technique used to run programs that are larger than the available physical memory (RAM). However, a program's size cannot exceed the logical address space of the computer. Thus, this statement is FALSE.
• Statement B: "Optimal binary search tree construction can be performed efficiently by using dynamic programming."
  Analysis: Constructing an Optimal Binary Search Tree (OBST) is a classic dynamic programming problem with a time complexity of $O(n^3)$ (which can be optimized to $O(n^2)$ using Knuth's optimization). Thus, this statement is TRUE.
• Statement C: "Depth first search cannot be used to find connected components of a graph."
  Analysis: Depth First Search (DFS) can easily find connected components in an undirected graph by launching a DFS from each unvisited vertex. It can also find strongly connected components in directed graphs (e.g., using Kosaraju's or Tarjan's algorithm). Thus, this statement is FALSE.
• Statement D: "Given the prefix and postfix walls over a binary tree, the binary tree can be uniquely constructed."
  Analysis: "Prefix and postfix" refers to preorder and postorder traversals. A general binary tree cannot be uniquely reconstructed using only its preorder and postorder traversals (an inorder traversal is mandatory alongside either preorder or postorder for unique reconstruction). Thus, this statement is FALSE.

Since the question asks for the FALSE statements, the correct options are A, C, and D.