GATE 1996 CSE & IT
45 questions across 1 session
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 $$. Then, (pick the true statement)
Two dice are thrown simultaneously. The probability that at least one of them will have 6 facing up is
Which one of the following is false?
A $$1000$$ Kbyte memory is managed using variable partitions but to compaction. It currently has two partitions of sizes $$200$$ Kbytes and $$260$$ Kbytes respectively. The smalles...
A solution to the Dining Philosophers Problem which avoids deadlock is
A critical section is a program segment
Let $$A = \left[ {\matrix{ {{a_{11}}} & {{a_{12}}} \cr {{a_{21}}} & {{a_{22}}} \cr } } \right]\,\,$$ and $$B = \left[ {\matrix{ {{b_{11}}} & {{b_{12}}} \cr {{b_{21}}} & {{b_{22}}}...
The correct matching for the following pairs is List - I (A) Activation record (B) Location counter (C) Reference counts (D) Address relocation List - II (1) Linking loader (2) Gar...
The probability that the top and bottom cards of a randomly shuffled deck are both access is
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 and X is a n x 1 column vector of unknowns. Which of the follo...
Which one of the following is false? Read $$ \wedge $$ as AND, $$ \vee $$ as OR, $$ \sim $$ as NOT, $$ \to $$ as one way implication and $$ \leftrightarrow $$ two way implication.
The recurrence relation $$\,\,\,\,\,$$ $$T\left( 1 \right) = 2$$ $$T\left( n \right) = 3T\left( {{n \over 4}} \right) + n$$ has the solution $$T(n)$$ equal to
Let $$X$$ $$X = \left\{ {2,3,6,12,24} \right\}$$. Let $$ \le $$ the partial order defined by $$x \le y$$ if $$x$$ divides $$y$$. The number of edges in the Hasse diagram of $$\left...
Suppose $$X$$ and $$Y$$ are sets and $$\left| X \right|$$ and $$\left| Y \right|$$ are their respective cardinalities. It is given that there are exactly 97 functions from $$X$$ to...
A $$ROM$$ is used to store the table for multiplication of two $$8$$ bit unsigned integers. The size of $$ROM$$ required is
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...
A binary search tree is used to locate the number 43. Which of the following probe sequences are not possible?
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 subtre...
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 with the maximum element at the root is
Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot i) 1, 2, 3,......., n ii) n, n-1, n-2,......, 2, 1 Let C 1 and C 2 be the number...
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 subtre...
Let $$A$$ and $$B$$ be sets and let $${A^c}$$ and $${B^c}$$ denote the complements of the sets $$A$$ and $$B$$. The set $$\left( {A - B} \right) \cup \left( {B - A} \right) \cup \l...
The average number of key comparisons done on a successful sequential search in list of length n is
The recurrence relation T(1) = 2 T(n) = 3T(n/4) + n has the solution, T(n) equals to
Which of the following sequences denotes the post order traversal sequence of the tree of previous question?
Both’s algorithm for integer multiplication gives worst performance when the multiplier pattern is
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 re...
It gives non-uniform priority to various devices.
An advantage of chained hash table (external hashing) over the open addressing scheme is
The concurrent programming constructs fork and join are as below: Fork (label) which creates a new process executing from the specified label join (variable) which decrements the s...
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 ) = (x + y, x - y). The inverse function of f is given by
Which of the following is an example of spooled device?
The formula used to compute an approximation for the second derivative of a function $$f$$ at a point $${x_0}$$ is
A file system with a one-level directory structure is implemented on a disk with disk block size of $$4$$ K bytes. The disk is used as follows: Disk-block $$0:$$ File Allocation Ta...
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...
Which of the following statements is false?
A library relational database system uses the following schema USERS (User #, User Name, Home Town) BOOKS (Books # Book Title, Author Name) ISSUED (Book #, User #, Date) Explain in...
A ROM is sued to store the table for multiplication of two $$8$$-bit unsigned integers. The size of ROM required is
The matrices$$\left[ {\matrix{ {\cos \,\theta } & { - \sin \,\theta } \cr {\sin \,\,\theta } & {\cos \,\,\theta } \cr } } \right]\,\,and$$ $$\left[ {\matrix{ a & 0 \cr 0 & b \cr }...
If $${L_1}$$ and $${L_2}$$ 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?
Let $$L \subseteq \sum {^{^ * }\,} $$ where $$\,\sum { = \,\,\left\{ {a,b} \right\}\,\,} $$ which of the following is true?
Let $$G$$ be a context free grammar where $$G = \left( {\left\{ {S,A,.B,C} \right\},\left\{ {a,b,d} \right\},P,S} \right)$$ with productions $$P$$ given below $$\eqalign{ & S \to A...
Which two of the following four regular expressions are equivalent? (i) $${\left( {00} \right)^ * }\left( {\varepsilon + 0} \right)$$ (ii) $${\left( {00} \right)^ * }$$ (iii) $${0^...
Which of the following is false?