GATE CSE 1996 PYQ

Which of the following is false?

Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot (i). (ii). Let and be the number of comparisons made for the inputs (i) and (ii) respectively. Then

The recurrence relation has the solution equal to

The pass numbers for each of the following activities i. object code generation ii. literals added to literal table iii. listing printed iv. address resolution of local symbols that occur in a two pas

The grammar whose productions are is ambiguous because

The correct matching for the following pairs is

A micro program control unit is required to generate a total of 25 control signals. Assume that during any micro instruction, at most two control signals are active. Minimum number of bits required in

Relative mode of addressing is most relevant to writing:

Number of machine cycles required for RET instruction in 8085 microprocessor is

For the daisy chain scheme of connecting I/O devices, which of the following statements is true?

A ROM is used to store the table for multiplication of two 8-bit unsigned integers. The size of ROM required is

Consider the circuit in below figure which has a four bit binary number as input and a five bit binary number, as output.

What is the equivalent Boolean expression in product-of-sums form for the Karnaugh map given in Fig

Consider the circuit in figure. f implements

Consider the following floating-point number representation. The exponent is in 2's complement representation and the mantissa is in the sign-magnitude representation. The range of the magnitude of th

Booth's algorithm for integer multiplication gives worst performance when the multiplier pattern is

Suppose X and Y are sets and |X| and |Y| are their respective cardinality. It is given that there are exactly 97 functions from X to Y. From this one can conclude that

Which of the following statements is FALSE?

Which of the following is false? Read as AND, as OR, as NOT, as one way implication and as two way implication

Which one of the following is false?

The matrices and commute under multiplication

Let A and B be sets and let and denote the complements of the sets A and B. The set is equal to

The probability that top and bottom cards of a randomly shuffled deck are both aces is

Two dice are thrown simultaneously. The probability that at least one of them will have 6 facing up is

Let , Let be the partial order defined by if x divides y. Number of edges in the Hasse diagram of is

The formula used to compute an approximation for the second derivative of a function at a point is

Let AX = b be a system of linear equations where A is an matrix and b is a column vector and X is an column vector of unknowns. Which of the following is false?

Let R be a non-empty relation on a collection of sets defined by if and only if . Then, (pick the true statement)

Let R denote the set of real numbers. Let be a bijective function defined by . The inverse function of is given by

Newton-Raphson iteration formula for finding , where c > 0 is

A solution to the Dining Philosophers Problem which avoids deadlock is to

Four jobs to be executed on a single processor system arrive at time 0 in the order A, B, C, D. Their burst CPU time requirements are 4, 1, 8, 1 time units respectively. The completion time of A under

The process state transition diagram in the below figure is representative of

A 1000 Kbyte memory is managed using variable partitions but no compaction. It currently has two partitions of sizes 200 Kbyte and 260 Kbyte respectively. The smallest allocation request in Kbyte that

Which of the following macros can put a macro assembler into an infinite loop? I. .MACRO M1, X .IF EQ, X ;if X=0 then M1 X + 1 .ENDC .IF NE, X ;if X [latex] [/latex] O then .WORD X ;address (X) is sto

The minimum number of interchanges needed to convert the array into a max-heap is 89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70

Which of the following sequences denotes the post order traversal sequence of the below tree?

A binary search tree is generated by inserting in order the following integers: 50,15,62,5,20,58,91,3,8,37,60,24 The number of nodes in the left subtree and right subtree of the root respectively is

An advantage of chained hash table (external hashing) over the open addressing scheme is

In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node g?

Consider the following statements: (i). First-in-first out types of computations are efficiently supported by STACKS. (ii). Implementing LISTS on linked lists is more efficient than implementing LISTS

The average number of key comparisons required for a successful search for sequential search on n items is

If and are context free languages and R a regular set, one of the languages below is not necessarily a context free language. Which one?

Which of the following statements is false?

Which two of the following four regular expressions are equivalent? ( is the empty string). (i). (ii). (iii). (iv).

Let where . Which of the following is true?

Consider the following state table shown in figure for a sequential machine. The number of states in the minimized machine will be

Define a context free languages for some v in ( in other words, is the set of prefixes of L) Let 0 1 Then is: