## GATE CSE 1996

Exam Held on Thu Jan 01 1970 00:00:00 GMT+0000 (Coordinated Universal Time)
Click View All Questions to see questions one by one or you can choose a single question from below.

## Algorithms

Which of the following is false?
The minimum number of interchanges needed to convert the array <p>89, 19, 40, 17...
The average number of key comparisons done on a successful sequential search in ...
Quicksort is run on two inputs shown below to sort in ascending order taking fir...
The recurrence relation<br/> T(1) = 2<br/> T(n) = 3T(n/4) + n<br/> has the solu...
A binary search tree is generated by inserting in order the following integers:<...

## Compiler Design

The pass numbers for each of the following activities <p>(i) object code generat...

## Computer Organization

Both’s algorithm for integer multiplication gives worst performance when the mul...
Consider the following floating point number representation <img class="question...
A $$ROM$$ is used to store the table for multiplication of two $$8$$ bit unsigne...
A computer system has a three level memory hierarchy, with access time and hit r...
It gives non-uniform priority to various devices.

## Data Structures

Consider the following statements: <br/> (i) First-in-first out types of computa...
Which of the following sequences denotes the post order traversal sequence of th...
In the balanced binary tree in Fig. given below, how many nodes will become unba...
A binary search tree is generated by inserting in order the following integers: ...
An advantage of chained hash table (external hashing) over the open addressing s...
A binary search tree is used to locate the number 43. Which of the following pro...

## Database Management System

<p>A library relational database system uses the following schema</p> <p>USERS (...

## Digital Logic

A logic network has two data inputs $$A$$ and $$B,$$ and two control inputs $${C... What is the equivalent Boolean expression in <b>product-of-sums</b> form for the... Consider the circuit in Fig. Which has a four bit binary number$${b_3}\,{b_2}\,...
Consider the circuit in fig shown $$f$$ implements <img class="question-image" ...
Consider the synchronous sequential circuit in fig. <img class="question-image" ...

## Discrete Mathematics

Which one of the following is false? Read $$\wedge$$ as AND, $$\vee$$ as OR,...
Two dice are thrown simultaneously. The probability that at least one of them wi...
The probability that the top and bottom cards of a randomly shuffled deck are bo...
Let R be a non-emply relation on a collection of sets defined by $${A^R}\,B$$ i...
Which one of the following is false?
Let R denote the set of real numbers. Let f: $$R\,x\,R \to \,R\,x\,R\,$$ be a bi...
Let $$A$$ and $$B$$ be sets and let $${A^c}$$ and $${B^c}$$ denote the complemen...
Let $$X$$ $$X = \left\{ {2,3,6,12,24} \right\}$$. Let $$\le$$ the partial orde...
Suppose $$X$$ and $$Y$$ are sets and $$\left| X \right|$$ and $$\left| Y \right|... Which of the following statements is false? Let AX = B be a system of linear equations where A is an m x n matrix and B is a... The recurrence relation$$\,\,\,\,\,T\left( 1 \right) = 2$$<br>$$T\left...
The matrices$$\left[ {\matrix{ {\cos \,\theta } & { - \sin \,\theta } \cr ... The formula used to compute an approximation for the second derivative of a fun... Let$$A = \left[ {\matrix{ {{a_{11}}} & {{a_{12}}} \cr {{a_{21}}} & {{a_...

## Operating Systems

The process state transition diagram in Figure is representative of <img class=...
Which of the following is an example of spooled device?
Four jobs to be executed on a single processor system arrive at time $${0^ + }$$...
A critical section is a program segment
The concurrent programming constructs fork and join are as below: Fork (label) ...
A solution to the Dining Philosophers Problem which avoids deadlock is
A ROM is sued to store the table for multiplication of two $$8$$-bit unsigned in...
A $$1000$$ Kbyte memory is managed using variable partitions but to compaction. ...
A demand paged virtual memory system uses $$16$$ bit virtual address, page size ...
A file system with a one-level directory structure is implemented on a disk with...
A computer system uses the Banker’s Algorithm to deal with deadlocks. Its curren...

## Programming Languages

The correct matching for the following pairs is <p><b>List - I</b> <br/>(A) Acti...

## Theory of Computation

Which two of the following four regular expressions are equivalent? <br>(i) $$... Let$$L \subseteq \sum {^{^ * }\,} $$where$$\,\sum { = \,\,\left\{ {a,b} \righ...
If $${L_1}$$ and $${L_2}$$ are context free languages and $$R$$ a regular set, o...
Let $$G$$ be a context free grammar where G = \left( {\left\{ {S,A,.B,C} \righ...
Which of the following statements is false?