## 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
(d) Deadlock            (s) Circular Wait```
 A (a) - (q), (b) - (p), (c) - (r), (d) - (s)
Operating-Systems       Match-the-Following       Video-Explanation
 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)
Database-Management-System       Match-the-Following       Video-Explanation
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)
Compiler-Design       Match-the-Following       Video-Explanation
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)
Programming       Match-the-Following       Video-Explanation
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)
Algorithms       Match-the-Following       Video-Explanation
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)
Data-Structures       Match-the-Following       Video-Explanation
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