GATE CSE 1989 | Question: 3-ixa

Question

Which one of the following statements (s) is/are FALSE?

• A. Overlaying is used to run a program, which is longer than the address space of the computer.
• B. Optimal binary search tree construction can be performed efficiently by using dynamic programming.
• C. Depth first search cannot be used to find connected components of a graph.
• D. Given the prefix and postfix walls over a binary tree, the binary tree can be uniquely constructed.

Answer 1

• A. FALSE according to definition of address space given in the link. whatever memory used by the overlay comes under the address space of computer "https://en.wikipedia.org/wiki/Address_space".
• B. TRUE Optimal binary search tree construction can be performed efficiently by using dynamic programming.
  ref: http://www.geeksforgeeks.org/dynamic-programming-set-24-optimal-binary-search-tree/
• C. FALSE Depth first search can be used to find connected components of a graph.
• D. FALSE Infix + (postfix or prefix) is req. to construct the binary tree uniquely.

Comments

In short we can say Address space by default means Logical address space..and Overlay is a technique to run a program that is bigger than the size of the Physical memory by keeping only those instructions and data that are needed at any given time.So statement A is false.

---

B,C : True                        A,D: False

---

Address space is nothing but physics memory of computer  (ROM) but in case of overlays we run the program which is bigger than logical memory (RAM) not bigger than physical memory

Answer 2

A. TRUE  Overlaying is a programming method that allows programs to be larger than the computer's main memory. (check wiki)

B TRUE

C FALSE

D FALSE

Answer 3

Answer = A,C,D

A,C,D options are false.

While option B is true

as Optimal binary search tree construction can be performed efficiently using dynamic programming.