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 $$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
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
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
The concurrent programming constructs fork and join are as below:
Fork (label) which creates a new process executing fr

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

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