## Match-the-Following

 Question 1

Match the following:

 A P→(ii), Q→(iv), R→(i), S→(iii) B P→(ii), Q→(i), R→(iv), S→(iii) C P→(ii), Q→(iv), R→(iii), S→(i) D P→(iii), Q→(iv), R→(i), S→(ii)
Programming       Match-the-Following       GATE 2017(set-02)
Question 1 Explanation:
Static char var:
⇾ A variable located in Data Section of memory

P→(ii), Q→(iv), R→(i), S→(iii)
 Question 2

Match the algorithms with their time complexities:

```      Algorithm                                     Time complexity
(P) Towers of Hanoi with n disks                       (i) Θ(n2)
(Q) Binary search given n stored numbers              (ii) Θ(n log⁡ n)
(R) Heap sort given n numbers at the worst case      (iii) Θ(2n)
(S) Addition of two n×n matrices                      (iv) Θ(log⁡ n)
```
 A P→(iii), Q→(iv), R→(i), S→(ii) B P→(iv), Q→(iii), R→(i), S→(ii) C P→(iii), Q→(iv), R→(ii), S→(i) D P→(iv), Q→(iii), R→(ii), S→(i)
Algorithms       Match-the-Following       GATE 2017(set-02)
Question 2 Explanation:
In this problem, we have to find Average case of different algorithms
→ Tower of Hanoi with n disks takes θ(2n) time
It is a mathematical game or puzzle.
It consists of three rods and a number of disks of different sizes, which can slide onto any rod.
The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
3. No disk may be placed on top of a smaller disk.
With 3 disks, the puzzle can be solved in 7 moves.
The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n-1, where n is the number of disks.
→ Binary Search given n sorted numbers takes Ɵ(log2 n)
→ Heap sort given n numbers of the worst case takes Ɵ(n log n)
→ Addition of two n×n matrices takes Ɵ(n2)
 Question 3
Match the following:
 A E - P, F - R, G - Q, H - S B E - R, F - P, G - S, H - Q C E - R, F - P, G - Q, H - S D E - P, F - R, G - S, H - Q
Theory-of-Computation       Match-the-Following       Gate-2008
Question 3 Explanation:
The grammar in S {X →bXb | cXc | ϵ} derives all even length Palindromes, So H matches with S.
F matches with P, Number of formal parameters in the declaration…. matches with {L={ an bm c n dm | m,n >=1}
Since, an bm corresponds to formal parameter (if n=2 and m=1, and “a” is int type and “b”is float type, then it means (int,int,float)) and cn dm corresponds to actual parameter used in function.
Similarly other two can also be argued by their reasons, but with F matches with P and H matches with S implies that option C is the only correct option.
 Question 4
Match the programming paradigms and languages given in the following table.
 A I-c, II-d, III-b, IV-a B I-a, II-d, III-c, IV-b C I-d, II-c, III-b, IV-a D I-c, II-d, III-a, IV-b
Programming       Match-the-Following       Gate 2008-IT
Question 4 Explanation:
Note: Out of syllabus.
 Question 5
Provider the best matching between the entries in the two columns given in the table below:
 A I-a, II-d, III-c, IV-b B I-b, II-d, III-c, IV-a C I-a, II-c, III-d, IV-b D I-b, II-c, III-d, IV-a
Computer-Networks       Match-the-Following       Gate 2008-IT
Question 5 Explanation:
(i) Proxy server: Proxy server and firewall are to be combined.
(ii) Kazaa and DC++ are P2P applications.
(iii) P2P slip is a processor of PPP.
(iv) DNS allows caching of entries at local server.
 Question 6
Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match entries in Group 1 to entries in Group 2.
```     Group I                          Group II
(P) Gang Scheduling              (1) Guaranteed Scheduling
(Q) Rate Monotonic Scheduling    (2) Real-time Scheduling
(R) Fair Share Scheduling        (3) Thread Scheduling```
 A P – 3 Q – 2 R – 1 B P – 1 Q – 2 R – 3 C P – 2 Q – 3 R – 1 D P – 1 Q – 3 R – 2
Operating-Systems       Match-the-Following       Gate-2007
Question 6 Explanation:
⇒ Gang scheduling is used for parallel system that schedules the threads.
⇒ Rate monotonic scheduling is used in Real-time operating system.
⇒ Fair share scheduling distributes the CPU equally among users due to which it generates scheduling process.
 Question 7
Match the following:
```(P) SMTP     (1) Application layer
(Q) BGP      (2) Transport layer
(R) TCP      (3) Data link layer
(S) PPP      (4) Network layer
(5) Physical layer```
 A P – 2 Q – 1 R – 3 S – 5 B P – 1 Q – 4 R – 2 S – 3 C P – 1 Q – 4 R – 2 S – 5 D P – 2 Q – 4 R – 1 S – 3
Computer-Networks       Match-the-Following       Gate-2007
Question 7 Explanation:
P) SMTP is used for email transmission.
Q) BGP is network layer protocol that manages low packets are routed across the network.
R) TCP is a transport layer protocol.
S) PPP is a data link layer protocol.
 Question 8
Match the following iterative methods for solving algebraic equations and their orders of convergence.
 A 1-R, 2-S, 3-P, 4-Q B 1-S, 2-R, 3-Q, 4-P C 1-S, 2-Q, 3-R, 4-P D 1-S, 2-P, 3-Q, 4-R
Engineering-Mathematics       Match-the-Following       Gate 2006-IT
Question 8 Explanation:
Note: Out of syllabus.
 Question 9
Match the following concepts and their best possible descriptions. Concepts (i)overloading (ii)friend (iii)constructor (iv)protected (v)this (vi)inheritance Descriptions A. allows to define a class to have a properties of another class B. defining a set of similar functions C.used in dereferncing D.Used to given a non - member function access to the private parts of body E. a function which is automically called when object is created F.allows a derived class to have access to the private parts of the base G. a pointer to the object associated with the current functions H. used to obtain persistence
 A (i) - B, (ii) - D, (iii) - E, (iv) - F, (v) - G, (vi) - A B (i) - C, (ii) - A, (iii) - E, (iv) - D, (v) - H, (vi) - F C (i) - C, (ii) - F, (iii) - H, (iv) - A, (v) - G, (vi) - D D (i) - B, (ii) - E, (iii) - C, (iv) - F, (v) - G, (vi) - H
Programming       Match-the-Following       Gate 2006-IT
Question 9 Explanation:
Note: Out of syllabus.
 Question 10
Match each of the high level language statements given on the left hand side with the most natural addressing mode from those listed on the right hand side.
``` 1 A[1] = B[J];	     a Indirect addressing
2 while [*A++];     b Indexed, addressing
3 int temp = *x;    c Autoincrement```
 A (1, c), (2, b), (3, a) B (1, a), (2, c), (3, b) C (1, b), (2, c), (3, a) D (1, a), (2, b), (3, c)
Computer-Organization       Match-the-Following       Gate-2005
Question 10 Explanation:
(a) A[i] = B[j]; Indexed, Addressing.
Here using the Index.
(b) while [*A++]; Auto increment.
The memory is increments automatically.
(c) int temp = *x; Indirect Addressing.
Here temp is assigned to integer type of Address contained in x.
 Question 11

 A P - 1, Q - 4, R - 3 B P - 2, Q - 4, R - 1 C P - 2, Q - 3, R - 1 D P - 1, Q - 3, R - 2
Computer-Networks       Match-the-Following       Gate-2004
Question 11 Explanation:
Data Link Layer :: Second layer of the OSI Model, Responsible for Hop to Hop connection or point to point connection.
Transport Layer :: Fourth layer of the OSI Model, Responsible for Service point addressing/Socket to socket connection or end to end connection with full reliability.
Network Layer :: Third layer of the OSI Model, Responsible for Host to Host.
 Question 12

 A P - 2, Q - 3, R - 4, S - 1 B P - 4, Q - 3, R - 2, S - 1 C P - 3, Q - 4, R - 1, S - 2 D P - 3, Q - 4, R - 2, S - 1
Programming       Match-the-Following       Gate-2004
Question 12 Explanation:
P) Functional programming is declarative in nature, involves expression evaluation and side effect free.
Q) Logic is also declarative but involves theorem proving.
R) Object oriented is imperative statement based and have abstract data types.
 Question 13

 A X – 3 Y – 2 Z - 1 B X – 1 Y – 3 Z - 2 C X – 2 Y – 3 Z - 1 D X – 3 Y – 1 Z - 2
Computer-Organization       Match-the-Following       Gate-2000
Question 13 Explanation:
Indirect addressing means that the address of the data is held in an intermediate location so that the address is first 'looked up' and then used to locate the data itself.
Immediate Addressing. An immediate operand has a constant value or an expression. When an instruction with two operands uses immediate addressing, the first operand may be a register or memory location, and the second operand is an immediate constant.
Auto increment or decrements can be one by using loops.
 Question 14

 A X – 1 Y – 3 Z – 2 B X – 2 Y – 1 Z – 3 C X – 3 Y – 2 Z – 1 D X – 3 Y – 1 Z – 2
Programming       Match-the-Following       Gate-2000
Question 14 Explanation:
X → m = NULL will results the loss of memory.
Y → n is pointer to invalid memory, a making it as a dangling pointer.
Z → p is not initialized.
p = malloc (size of(char))p = malloc (size of(char)); should have been used before assigning 'aa' to ∗p.
 Question 15

 A X – 1 Y – 2 Z – 3 B X – 3 Y – 1 Z – 2 C X – 3 Y – 2 Z – 1 D X – 2 Y – 3 Z – 1
Data-Structures       Match-the-Following       Gate-2000
Question 15 Explanation:
Stack is used in depth first search.
Queus is used in Queue.
Heap is used in heap.
 Question 16

 A (A) – 2 (B) – 4 (C) – 3 (D) - 1 B (A) – 1 (B) – 2 (C) – 3 (D) – 4 C (A) – 3 (B) – 2 (C) – 4 (D) - 1 D (A) – 4 (B) – 1 (C) – 2 (D) – 3
Operating-Systems       Match-the-Following       Gate-1999
Question 16 Explanation:

⇒ Threads are handled by CPU.
⇒ Virtual address is a memory type.
⇒ File system is used to manage the disk.
⇒ Interrupt is a signal.
 Question 17

 A A – R B – P C – Q D – S B A – R B – P C – S D – Q C A – P B – R C – S D – Q D A – P B – S C – R D – Q
Algorithms        Match-the-Following       Gate-1998
Question 17 Explanation:
Binary search = O(log n)
Selection = O(n)
Merge sort = O(n log n)
Insertion sort = O(n2)
 Question 18

 A A – 2 B – 4 C – 1 D – 3 B A – 3 B – 4 C – 1 D – 2 C A – 3 B – 4 C – 2 D – 1 D A – 4 B – 1 C – 2 D – 3
Algorithms        Match-the-Following       Gate-1997
Question 18 Explanation:
All pairs shortest path - Dynamic Programming
Quick sort - Divide and Conquer
Minimum weight Spanning tree - Greedy
Connected components - Depth-First search
 Question 19

 A A – 4 B – 3 C – 1 D – 2 B A – 2 B – 1 C – 3 D – 4 C A – 4 B – 3 C – 2 D – 1 D A – 2 B – 3 C – 4 D – 1
Computer-Organization       Match-the-Following       Gate-1997
Question 19 Explanation:
DMA I/O → Disk
Cache → High speed RAM
Interrupt I/O → Printer
Condition code register → ALU
 Question 20

 A A – 3 B – 4 C – 2 D – 1 B A – 4 B – 3 C – 2 D – 1 C A – 2 B – 4 C – 1 D – 3 D A – 3 B – 4 C – 3 D – 2
Operating-Systems       Match-the-Following       Gate-1997
Question 20 Explanation:
Disk scheduling - SCAN
Batch processing - FIFO
Time sharing - Round Robin
Interrupt processing - LIFO
 Question 21

 A A – 3 B – 4 C – 1 D – 2 B A – 4 B – 3 C – 1 D – 2 C A – 4 B – 3 C – 2 D – 1 D A – 3 B – 4 C – 2 D – 1
Operating-Systems       Match-the-Following       Gate-1996
Question 21 Explanation:
Each time a subroutine is called its activation record is created.
An assembler uses location counter value to give address to each instruction which is needed for relative addressing as well as for jump labels.
Reference count is used by garbage collector to clear the memory whose reference count be comes 0.
Linker loader is a loader which can load several compiled codes and link them together into a single executable. Thus it needs to do relocation of the object codes.
 Question 22

 A (X, III) (Y, I) (Z, II) B (X, II) (Y, III) (Z, I) C (X, III) (Y, II) (Z, I) D (X, I) (Y, III) (Z, II)
Computer-Organization       Match-the-Following       Gate-2001
Question 22 Explanation:
⇒ Array implementation can be done by Indexed addressing.
⇒ Writing relocatable code can be done by Base Register addressing by changing the value of Base Register.
⇒ While passing an array as parameter we use pointer and hence can use Indirect addressing.
 Question 23

 A (a) - (q), (b) - (p), (c) - (r), (d) - (s)
Operating-Systems       Match-the-Following       Gate-1990
 Question 24

 A (a) - (q), (b) - (r), (c) - (p), (d) - (s)
Database-Management-System       Match-the-Following       Gate-1990
Question 24 Explanation:
Secondary index → B-Tree
Non-procedural query language → Domain calculus
Closure of set of attributes → Function dependency
Natural join → Relational algebraic operations
 Question 25

 A (a) - (q), (b) - (r), (c) - (s), (d) - (p)
Compiler-Design       Match-the-Following       Gate-1990
Question 25 Explanation:
Pointer data type - Dynamic data structure
Activation record - Recursion
Repeat until - Non-deterministic loop
Coercion - Type conversion
 Question 26

 A (a) - (s), (b) - (r), (c) - (p), (d) - (q)
Programming       Match-the-Following       Gate-1990
Question 26 Explanation:
Note: Out of syllabus.
 Question 27

 A (a) - (r), (b) - (p), (c) - (s), (d) - (q)
Algorithms       Match-the-Following       Gate-1990
Question 27 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 28

 A (a) - (q), (b) - (r), (c) - (s), (d) - (p)
Data-Structures       Match-the-Following       Gate-1990
Question 28 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)
 Question 29

 A (a) - (s), (b) - (p), (c) - (q), (d) - (r)
Compiler-Design       Match-the-Following       Gate-1990
Question 29 Explanation:
Lexical analysis - Finite automaton
Code optimization - DAG
Code generation - Syntax tree
Abelian groups - Push down automaton
 Question 30
 A (a) - (s), (b) - (p), (c) - (q), (d) - (r)
Engineering-Mathematics       Match-the-Following       Gate-1990
Question 30 Explanation:
Group - Left inverse
Semigroup - Associative
Monoid - Identity
Abelian group - Commutative
 Question 31

 A (A)-(r), (B)-(s), (C)-(q), (D)-(p)
Computer-Organization       Match-the-Following       Gate-1989
Question 31 Explanation:
 Question 32

 A (A)-(s), (B)-(r), (C)-(p), (D)-(q)
Computer-Organization       Match-the-Following       Gate-1989
Question 32 Explanation:
Base addressing is a position independent. By changing the value in base register, location of address also be changed.
Indexing mode can be used to access an array whose elements are in successive memory locations.
Stack addressing is a Reentranecy whenever code happens to be used again, address is need not be the same.
Implied addressing belongs to accumulator if an address is not specified, It is assumed implied to be accumulator.
 Question 33

 A (A)-(r), (B)-(s), (C)-(p), (D)-(q)
Data-Structures       Match-the-Following       Gate-1989
Question 33 Explanation:
O(log n) - Binary search
O(n) - Selection of the kth smallest element in a set of n elements
O(n log n) - Heapsort
O(n2) - Depth-first search
 Question 34

 A (A)-(r), (B)-(s), (C)-(q), (D)-(p)
Operating-Systems       Match-the-Following       Gate-1989
Question 34 Explanation: