GATE CSE 1999 PYQ

The minimum number of record movements required to merge five files A (with 10 records), B (with 20 records), C (with 15 records), D (with 5 records) and E (with 25 records) is:

A sorting technique is called stable if

If , give the correct matching for the following pairs: T_n = T_{n-1} + n T_n = O(n) T_n = T_{n/2} + n T_n = O(n n) T_n = T_{n/2} + n n T_n = O(n^2) T_n = T_{n-1} + n T_n = O( ^2 n)

If n is a power of 2, then the minimum number of multiplications needed to compute is

The number of tokens in the FORTRAN statement DO 10 I = 1.25 is

Which of the following is the most powerful parsing method?

A grammar that is both left and right recursive for a non-terminal, is

The main difference(s) between a CISC and a RISC processor is/are that a RISC processor typically: a) has fewer instructions b) has fewer addressing modes c) has more registers d) is easier to impleme

Arrange the following configuration for CPU in decreasing order of operating speeds: Hard wired control, Vertical microprogramming, Horizontal microprogramming.

The main memory of a computer has 2 cm blocks while the cache has 2c blocks. If the cache uses the set associative mapping scheme with 2 blocks per set, then block k of the main memory maps to the set

A certain processor supports only the immediate and the direct addressing modes. Which of the following programming language features cannot be implemented on this processor? a) Pointers b) Arrays c)

Raid configurations of the disks are used to provide

Let R = (A, B, C, D, E, F) be a relation scheme with the following dependencies . Which one of the following is a key for R?

The relational algebra expression equivalent to the following tuple calculus expression: is

Which of the following is/are correct?

For the schedule given below, which of the following is correct:

Consider the schema and the dependencies and . Let be a decomposition such that . The decomposition is

Which of the following sets of component(s) is/are sufficient to implement any arbitrary Boolean function?

Which of the following functions implements the Karnaugh map shown below?

Consider the circuit shown below. In a certain steady state, the line Y is at '1'. What are the possible values of A, B and C in this state?

Zero has two representations in:

Booth's coding in 8 bits for the decimal number -57 is:

Which of the following expressions is not equivalent to ?

The number of full and half-adders required to add 16-bit numbers is

The number of binary relations on a set with n elements is:

The number of articulation points of the following graph is

The Newton-Raphson method is to be used to find the root of the equation where is the initial approximation and is the derivative of . The method converges

The number of binary strings of n zeros and k ones in which no two ones are adjacent is

Two girls have picked 10 roses, 15 sunflowers and 15 daffodils. What is the number of ways they can divide the flowers among themselves?

Let L be a set with a relation R which is transitive, anti-symmetric and reflexive and for any two elements , let the least upper bound and the greatest lower bound exist. Which of the following is/ar

Suppose that the expectation of a random variable X is 5. Which of the following statements is true?

Consider two events and such that probability of , probability of , and probability of , and . Which of the following statements is/are true?

Listed below are some operating system abstractions (in the left column) and the hardware components (in the right column)

A multi-user, multi-processing operating system cannot be implemented on hardware that does not support

System calls are usually invoked by using

Which of the following disk scheduling strategies is likely to give the best throughput?

Which of the following is/are advantage(s) of virtual memory?

Which of the following actions is/are typically not performed by the operating system when switching context from process A to process B?

Consider the following program in a language that has dynamic scooping: var x: real; procedure show: begin print(x);end; procedure small; var x: real; begin x: = 0.125; show; end; begin x:=0.25 show;

Which of the following is correct?

Consider the following C function definition int Trial (int a, int b, int c) { if ((a>=b) && (c = b) return Trial(a, c, b); else return Trial(b, a, c); } The functional Trial:

Suppose we want to arrange the n numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is

Given the programming constructs I. assignment II. for loops where the loop parameter cannot be changed within the loop III. if-then-else IV. forward go to V. arbitrary go to VI. non-recursive procedu

Context-free languages are closed under:

If L1 is context free language and L2 is a regular language which of the following is/are false?

Consider the regular expression (0 + 1) (0+1) ... n times. The minimum state finite automaton that recognizes the language represented by this regular expression contains

Let be the set of all languages accepted by a PDA by final state and the set of all languages accepted by empty stack. Which of the following is true?