## GATE 1990

 Question 1

Match the pairs:

```(a) Critical region     (p) Hoare's monitor
(b) Wait/Signal         (q) Mutual exclusion
(c) Working Set         (r) Principle of locality
 A (a) - (q), (b) - (p), (c) - (r), (d) - (s)
 Question 2

Match the pairs in the following questions:

```(a) Secondary index                  (p) Function dependency
(b) Non-procedural query language    (q) B-tree
(c) Closure of a set of attributes   (r) Domain calculus
(d) Natural join                     (s) Relational algebraic operations
```
 A (a) - (q), (b) - (r), (c) - (p), (d) - (s)
Question 2 Explanation:
Secondary index → B-Tree
Non-procedural query language → Domain calculus
Closure of set of attributes → Function dependency
Natural join → Relational algebraic operations
 Question 3

Match the pairs in the following questions:

```(a) Pointer data type       (p) Type conversion
(b) Activation record       (q) Dynamic data structure
(c) Repeat-until            (r) Recursion
(d) Coercion                (s) Non-deterministic loop```
 A (a) - (q), (b) - (r), (c) - (s), (d) - (p)
Question 3 Explanation:
Pointer data type - Dynamic data structure
Activation record - Recursion
Repeat until - Non-deterministic loop
Coercion - Type conversion
 Question 4

Match the pairs in the following questions:

```(a) Small talk      (p) Logic programming
(b) LISP            (q) Data flow programming
(c) Prolog          (r) Functional programming
(d) VAL             (s) Object-oriented programming```
 A (a) - (s), (b) - (r), (c) - (p), (d) - (q)
Question 4 Explanation:
Note: Out of syllabus.
 Question 5

Match the pairs in the following questions:

```(a) Strassen's matrix multiplication algorithm     (p) Greedy method
(b) Kruskal's minimum spanning tree algorithm      (q) Dynamic programming
(c) Biconnected components algorithm               (r) Divide and Conquer
(d) Floyd's shortest path algorithm                (s) Depth first search```
 A (a) - (r), (b) - (p), (c) - (s), (d) - (q)
Question 5 Explanation:
Strassen's matrix multiplication algorithm - Divide and Conquer
Kruskal's minimum spanning tree algorithm - Greedy method
Biconnected components algorithm - Depth first search
Floyd's shortest path algorithm - Dynamic programming
 Question 6

Match the pairs in the following questions:

```(a) A heap construction                            (p) Ω(n log10 n)
(b) Constructing Hash table with linear probing    (q) O(n)
(c) AVL Tree construction                          (r) O(n2)
(d) Digital trie construction                      (s) O(n log10 n)```
 A (a) - (q), (b) - (r), (c) - (s), (d) - (p)
Question 6 Explanation:
Heap construction - O(n)
Constructing Hash table with linear probing - O(n2
AVL tree construction - O(n log10 n)
Digital trie construction - Ω(n log10 n)
There are 6 questions to complete.

Register Now