GATE CSE 1996

## GATE CSE

Which of the following is false?

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

View Question The average number of key comparisons done on a successful sequential search
in list of length n is

View Question Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot
i) 1, 2, 3,.......,

View Question The recurrence relation
T(1) = 2
T(n) = 3T(n/4) + n
has the solution, T(n) equals to

View Question A binary search tree is generated by inserting in order the following integers:
50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60,

View Question The pass numbers for each of the following activities
(i) object code generation
(ii) literals added to literal table

View Question Both’s algorithm for integer multiplication gives worst performance when the multiplier pattern is

View Question Consider the following floating point number representation
The exponent is in $$2’s$$ complement representation and m

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

View Question A computer system has a three level memory hierarchy, with access time and hit ratios as shown below:
(i) What shou

View Question It gives non-uniform priority to various devices.

View Question Consider the following statements:
(i) First-in-first out types of computations are efficiently supported by STACKS.
(

View Question Which of the following sequences denotes the post order traversal sequence of the tree of previous question?

View Question In the balanced binary tree in Fig. given below, how many nodes will become unbalanced when a node is inserted as a chil

View Question A binary search tree is generated by inserting in order the following integers:
50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60

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

View Question A binary search tree is used to locate the number 43. Which of the following
probe sequences are not possible?

View Question A library relational database system uses the following schema
USERS (User #, User Name, Home Town)
BOOKS (Books # Book

View Question A logic network has two data inputs $$A$$ and $$B,$$ and two control inputs $${C_0}$$ and $${C_1}$$. It implements the f

View Question What is the equivalent Boolean expression in product-of-sums form for the Karnaugh map given in fig?

View Question Consider the circuit in Fig. Which has a four bit binary number $${b_3}\,{b_2}\,{b_1}\,{b_0}\,$$ as input and a five bit

View Question Consider the circuit in fig shown $$f$$ implements

View Question Consider the synchronous sequential circuit in fig.
(a) Draw a state diagram which is implemented by the circuit. Use

View Question Which one of the following is false? Read $$ \wedge $$ as AND, $$ \vee $$ as OR, $$ \sim $$ as NOT, $$ \to $$ as one way

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

View Question The probability that the top and bottom cards of a randomly shuffled deck are both access is

View Question Let R be a non-emply relation on a collection of sets defined by $${A^R}\,B $$ if and only if $$A\, \cap \,B\, = \,\phi

View Question Which one of the following is false?

View Question Let R denote the set of real numbers. Let f: $$R\,x\,R \to \,R\,x\,R\,$$ be a bijective function defined by f (x, y ) =

View Question Let $$X$$ $$X = \left\{ {2,3,6,12,24} \right\}$$. Let $$ \le $$ the partial order defined by $$x \le y$$ if $$x$$ divi

View Question Suppose $$X$$ and $$Y$$ are sets and $$\left| X \right|$$ and $$\left| Y \right|$$ are their respective cardinalities. I

View Question Let $$A$$ and $$B$$ be sets and let $${A^c}$$ and $${B^c}$$ denote the complements of the sets $$A$$ and $$B$$. The set

View Question Which of the following statements is false?

View Question Let AX = B be a system of linear equations where A is an m x n matrix and B is a $$m\,\, \times \,\,1$$ column vector an

View Question The recurrence relation $$\,\,\,\,\,$$ $$T\left( 1 \right) = 2$$
$$T\left( n \right) = 3T\left( {{n \over 4}} \right)

View Question The matrices$$\left[ {\matrix{
{\cos \,\theta } & { - \sin \,\theta } \cr
{\sin \,\,\theta } & {\cos \,\

View Question The formula used to compute an approximation for the second derivative of a function $$f$$ at a point $${x_0}$$ is

View Question Let $$A = \left[ {\matrix{
{{a_{11}}} & {{a_{12}}} \cr
{{a_{21}}} & {{a_{22}}} \cr
} } \right]\,\,$$

View Question The process state transition diagram in Figure is representative of

View Question Which of the following is an example of spooled device?

View Question Four jobs to be executed on a single processor system arrive at time $${0^ + }$$ in the order $$A, B, C, D.$$ their bur

View Question A critical section is a program segment

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

View Question The concurrent programming constructs fork and join are as below:
Fork (label) which creates a new process executing fr

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

View Question A $$1000$$ Kbyte memory is managed using variable partitions but to compaction. It currently has two partitions of sizes

View Question A demand paged virtual memory system uses $$16$$ bit virtual address, page size of $$256$$ bytes, and has $$1$$ Kbyte of

View Question A file system with a one-level directory structure is implemented on a disk with disk block size of $$4$$ K bytes. The d

View Question A computer system uses the Banker’s Algorithm to deal with deadlocks. Its current state is shown in the tables below, wh

View Question The correct matching for the following pairs is
List - I
(A) Activation record
(B) Location counter
(C) Reference counts

View Question Which two of the following four regular expressions are equivalent?
(i) $${\left( {00} \right)^ * }\left( {\varepsilon

View Question Let $$L \subseteq \sum {^{^ * }\,} $$ where $$\,\sum { = \,\,\left\{ {a,b} \right\}\,\,} $$ which of the following is tr

View Question If $${L_1}$$ and $${L_2}$$ are context free languages and $$R$$ a regular set, one of the languages below is not necessa

View Question Let $$G$$ be a context free grammar where $$G = \left( {\left\{ {S,A,.B,C} \right\},\left\{ {a,b,d} \right\},P,S} \right

View Question Which of the following statements is false?

View Question