GATE CS question library

State whether the following statements are True or False with reasons for your answer A symbol declared as ‘external’ in an assembly language program is assigned an address outside the program by the assembler itself.

Consider the following recursive function: function fib (n:integer);integer; begin if (n=0) or (n=1) then fib := 1 else fib := fib(n-1) + fib(n-2) end; The above function is run on a computer with a stack of $64$ bytes. Assuming that only return address and parameter are passed on the stack, and that an integer value and an address takes $2$ bytes each, …

State whether the following statements are True or False with reasons for your answer: Coroutine is just another name for a subroutine.

State whether the following statements are True or False with reasons for your answer A subroutine cannot always be used to replace a macro in an assembly language program.

Find the contents of the flip-flop $Q_2, Q_1$ and $Q_0$ in the circuit of figure, after giving four clock pulses to the clock terminal. Assume $Q_2Q_1Q_0=000$ initially.

Let $p$ and $q$ be propositions. Using only the Truth Table, decide whether $p \Longleftrightarrow q$ does not imply $p \to \lnot q$ is True or False.

State True or False with reason Logical data independence is easier to achieve than physical data independence.

Every subset of a countable set is countable. State whether the above statement is true or false with reason.

State True or False with reason There is always a decomposition into Boyce-Codd normal form (BCNF) that is lossless and dependency preserving.

State True or False with one line explanation A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits).

State True or False with one line explanation Expanding opcode instruction formats are commonly employed in RISC. (Reduced Instruction Set Computers) machines.

The Hasse diagrams of all the lattices with up to four elements are ________ (write all the relevant Hasse diagrams)

Let $A, B,$ and $C$ be independent events which occur with probabilities $0.8, 0.5,$ and $0.3$ respectively. The probability of occurrence of at least one of the event is _______

Consider the following heap (figure) in which blank regions are not in use and hatched region are in use. The sequence of requests for blocks of sizes $300, 25, 125, 50$ can be satisfied if we use

Consider the following two functions: $g_1(n) = \begin{cases} n^3 \text{ for } 0 \leq n \leq 10,000 \\ n^2 \text{ for } n > 10,000 \end{cases}$ $g_2(n) = \begin{cases} n \text{ for } 0 \leq n \leq 100 \\ n^3 \text{ for } n > 100 \end{cases}$ Which of the following is true?

Which of the following statements is false?

Which one of the following statements is true?

Algorithm design technique used in quicksort algorithm is?

Which of the following features cannot be captured by context-free grammars?

Which of the following conversions is not possible (algorithmically)?