GATE CSE 1997
View Questions

GATE CSE

1
The concatenation of two lists is to be performed on 0(1) time. Which of the following implementations of a list should be used?
2
The correct matching for the following pairs is
A. All pairs shortest path 1. Greedy
B. Quick Sort 2. Depth-First Search
C. Minimum weight spanning tree 3. Dynamic Programming
D. Connected Components 4. Divide and Conquer
3
Let T(n) be the function defined by $$T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$$
Which of the following statements is true?
4

In the following grammar:

$$\eqalign{ & X:: = X \oplus {Y \over Y} \cr & Y:: = Z*{Y \over Z} \cr & Z:: = id \cr} $$

Which of the following is true?

5
The correct matching for the following pairs is GATE CSE 1997 Computer Organization - IO Interface Question 22 English
6
An $$N$$-bit carry look ahead adder, where $$N$$ is a multiple of $$4,$$ employs $${\rm I}cs$$ $$74181$$ ($$4$$bit $$ALU$$) and $$74182$$ ($$4$$ bit carry look ahead generator). The minimum addition time using the best architecture for this adder is
7
Which of the following is essential for converting an infix expression to the postfix form efficiently?
8
A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented INSERT (Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in
9
A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?
10
For a database relation $$R(a,b,c,d),$$ where the domains of $$a, b, c, d$$ include only atomic values, only the following functional dependencies and those that can be inferred from them hold:
$$a \to c\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,b \to d$$
This relation is
11
Let $$R (a, b, c)$$ and $$S(d, e, f)$$ be two relations in which $$d$$ is the foreign key of $$S$$ that refers to the primary key of $$R.$$ Consider the following four operations $$R$$ and $$S$$
(a) Insert into $$R$$ (b) Insert into $$S$$
(c) Delete from $$R$$ (d) Delete from $$S$

Which of the following statements is true about the referential integrity constraint above?

12
Given $$\sqrt {\left( {224} \right),} = {\left( {13} \right)_r},$$
The value of the radix' $$r$$ is:
13
Let $$^ * $$ be defined as $${x^ * }y = \overline x + y,$$ Let $$z = {x^ * }y.$$ Value of $${z^ * }x$$ is
14
Let $$f\left( {x,y,z} \right) = \overline x + \overline y x + xz$$ be a switching function. Which one of the following is valid?
15
Consider the logic circuit shown in Figure below. The functions $${f_1},$$ $${f_2}$$ and $$f$$ (in canonical sum of products form in decimal notation) are: GATE CSE 1997 Digital Logic - Boolean Algebra Question 39 English

$${f_1}\left( {w,\,x,\,y,\,z} \right) = \sum {8,9,10} $$
$${f_2}\left( {w,\,x,\,y,\,z} \right) = \sum {7,8,12,13,18,15} $$
$$f\left( {w,\,x,\,y,\,z} \right) = \sum {\left( {8,9} \right)} $$

The function $${f_3}$$ is

16
The number of equivalence relations on the set $$\left\{ {1,2,3,4} \right\}$$ is
17
The determination of the matrix $$$\left[ {\matrix{ 6 & { - 8} & 1 & 1 \cr 0 & 2 & 4 & 6 \cr 0 & 0 & 4 & 8 \cr 0 & 0 & 0 & { - 1} \cr } } \right]\,\,is$$$
18
Let $$A = ({a_{ij}})$$ be and n-rowed square matrix and $${I_{12}}$$ be the matrix obtained by interchanging the first and second rows of the n-rowed Identity matrix. Then$${AI_{12}}$$ is such that its first
19
What is the maximum value of the function
$$f\left( x \right) = 2{x^2} - 2x + 6$$ in the interval $$\left[ {0,2} \right]$$?
20
The probability that it will rain today is 0.5. The probability that it will rain tomorrow is 0.6. The probability that it will rain either today or tomorrow is 0.7. That is the probability that it will rain today and tomorrow?
21
Locality of reference implies that the page reference being made by a process
22
Thrashing
23
Dirty bit for a page in a page table
24
$$I/O$$ redirection
25
The correct matching for the following pairs is
$$\,\,\,\,\,$$ List - $${\rm I}$$
(a) $$DMA$$ $$\,\,$$ $${\rm I}/O$$
(b) Cache
(c) Interrupt $${\rm I}/O$$
(d) Condition Code Register

$$\,\,\,\,\,$$ List - $${\rm II}$$
(1) High speed $$RAM$$
(2) Disk
(3) Printer
(4) $$ALU$$

26
When an interrupt occurs, an Operating System
27
The correct matching for the following pairs is

(a) Disk scheduling $$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$(1) Round robin
(b) Batch processing $$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ (2) $$SCAN$$
(c) Time sharing $$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ (3) $$LIFO$$
(d) Interrupt processing $$\,\,\,\,\,\,\,\,\,\,\,$$(4) $$FIFO$$

28
An operating system contains 3 user processes each requiring 2 units of resource R.The minimum number of units of R such that no deadlocks will ever arise is
29
Each process Pi,i=1.....9 is coded as follows

  Repeat
  P(mutex){
  critical section
  }
  V(mutex)
  Forever
The code for P10 is identical except that it uses V(mutex) in place of P(mutex). What is the largest number of processes that can be inside the critical section at any moment?
30
Heap allocation is required for languages.
31

Given the following Pascal like program segment:

Procedure A;

     x,y:intger;
     Procedure B;
            x,z:real;
            S1
     end B;
     Procedure C;
            i:integer;
            S2;
     end C;
end A;

The variables accessible in S1 and S2 are

32
Which one of the following is not decidable?
33
$$\sum { = \left\{ {a,b} \right\},\,\,} $$ which one of the following sets is not countable.
34
Which one of the following regular expressions over $$\left\{ {0,\,\,1} \right\}$$ denotes the set of all strings not containing $$100$$ as substring?
35
Which of the following languages over $$\left\{ {a,b,c} \right\}$$ is accepted by Deterministic push down automata?
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12