## Gate-1989

Question 1 |

4 | |

5 | |

6 | |

3 |

Question 1 Explanation:

In this, maximum size of cluster = 4 (S6, S3, S7, S1)

→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)

→ Maximum no. of comparisions = 4 + 1 = 5

→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)

→ Maximum no. of comparisions = 4 + 1 = 5

Question 2 |

In which of the following case(s) is it possible to obtain different results for call-by-reference and call-by-name parameter passing?

Passing an expression as a parameter | |

Passing an array as a parameter | |

Passing a pointer as a parameter | |

Passing as array element as a parameter | |

Both A and D |

Question 2 Explanation:

__Option D__:

Passing array element as a parameter.

Consider an example:

{

.......

a[ ] = {1, 2, 3, 4, 5}

fun (a[i]);

print a[0];

}

fun (int x)

{

int i=1;

}

O/P:

Call-by-reference: 6

Call-by-name: 1

Result is different.

__Option A__:

While we passing an expression as a parameter due to precedence (higher (or) lower), the output may changes.

If we pass 1+2 to the below function

int foo (int x)

{

return x*x;

}

O/P:

Call by reference = 3*3 = 9

Call by name = 1+2*1+2 (* has higher precedenc e)

= 1+2+2

= 5

Output differs.

Answer: A, D

Question 3 |

Merging states with a common core may produce __________ conflicts and does not produce ___________ conflicts in an LALR purser.

Reduce-Reduce, Shift-Reduce |

Question 3 Explanation:

Merge states with a common core may produce

__Reduce-Reduce__conflicts and does not produce__Shift-Reduce__conflicts in an LALR parser.Question 4 |

The transitive closure of the relation {(1, 2), (2, 3), (3, 4), (5, 4)} on the set {1, 2, 3, 4, 5} is ___________.

{(1,2), (2,3), (1,3), (3,4), (2,4), (1,4), (5,4)} |

Question 4 Explanation:

Transitive closure of the relation {(1,2), (2,3), (3,4), (5,4)} ={(1,2), (2,3), (1,3), (3,4), (2,4), (1,4), (5,4)}

Transitive closure of R:

(a) It is transitive.

(b) It contains R.

(c) It is minimal, satisfies a & b.

Transitive closure of R:

(a) It is transitive.

(b) It contains R.

(c) It is minimal, satisfies a & b.

Question 5 |

(A)-(r), (B)-(s), (C)-(q), (D)-(p) |

Question 5 Explanation:

Question 6 |

(A)-(s), (B)-(r), (C)-(p), (D)-(q) |

Question 6 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.

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 7 |

(A)-(r), (B)-(s), (C)-(p), (D)-(q) |

Question 7 Explanation:

O(log n) - Binary search

O(n) - Selection of the k

O(n log n) - Heapsort

O(n

O(n) - Selection of the k

^{th}smallest element in a set of n elementsO(n log n) - Heapsort

O(n

^{2}) - Depth-first searchQuestion 8 |

(A)-(r), (B)-(s), (C)-(q), (D)-(p) |

Question 8 Explanation:

Virtual Memory - Address Translation

Shared Memory - Mutual Exclusion

Look-ahead buffer - Spatial Locality

Look-aside buffer - Temporal Locality

Shared Memory - Mutual Exclusion

Look-ahead buffer - Spatial Locality

Look-aside buffer - Temporal Locality

Question 9 |

An unrestricted use of the "go to" statement is harmful because of which of the following reason (s):

It makes it more difficult to verify programs. | |

It makes programs more inefficient. | |

It makes it more difficult to modify existing programs. | |

It results in the compiler generating longer machine code. |

Question 9 Explanation:

Dijkstra's argued that unrestricted goto statements should abolished from the higher-level languages because they complicated the task of analyzing and verifying the correctness of programs.

Question 10 |

Context-free languages and regular languages are both closed under the operation(s) of :

Union | |

Intersection | |

Concatenation | |

Complementation | |

Both A and C |

Question 10 Explanation:

Regular languages closed under Union, Intersection, Concatenation and Complementation but CFC is only closed under Union and Concatenation.

Question 11 |

Which of the following problems are undecidable?

Membership problem in context-free languages. | |

Whether a given context-free language is regular. | |

Whether a finite state automation halts on all inputs. | |

Membership problem for type 0 languages. | |

Both (A) and (C). |

Question 11 Explanation:

→ Option A is decidable as we have various membership algorithms for CFL languages such as CYK algo, LL(K) and LC(K) parsing algorithms etc. In fact the upper bound to determine if a string belongs to CFL is given by O(n

→ Option C is also decidable because this is a trivial problem as finite state automaton is a specific case of halting turing machine with limited power.

^{3}) in worst case scenario by CYK algo and in some cases we have best case as O(n) as this is the case of S-grammar.→ Option C is also decidable because this is a trivial problem as finite state automaton is a specific case of halting turing machine with limited power.

Question 12 |

Which of the following well-formed formulas are equivalent?

P → Q | |

¬Q → ¬P | |

¬P ∨ Q | |

¬Q → P | |

A, B and C. |

Question 12 Explanation:

P → Q ⇔ ¬P ∨ Q

¬Q → ¬P ⇔ Q ∨ ¬P

¬P ∨ Q ⇔ ¬P ∨ Q

¬Q → P ⇔ Q ∨ P

A, B and C are equivalent.

¬Q → ¬P ⇔ Q ∨ ¬P

¬P ∨ Q ⇔ ¬P ∨ Q

¬Q → P ⇔ Q ∨ P

A, B and C are equivalent.

Question 13 |

Theory Explanation is given below. |

Question 13 Explanation:

(i) G

→ Let us assume K

Let G be a connected planar graph with n vertices and m edges, and no triangles. Then m≤2n-4.

Where m=9, n=6

⇒ 9 ≤ 12 - 4

⇒ 9 ≤ 8, which is to be false, then K

(ii) G

(iii) Let us assume G

Where m=9, n=6

then 9 ≤ 12-4

9 ≤ 8 is False

So, G

Answer: Only G

_{1}is K_{33}which is planar graph with the minimum number of edges.→ Let us assume K

_{33}is a planar graph. Then it satisfy the useful corollary. As there is no triangle in K_{33}.Let G be a connected planar graph with n vertices and m edges, and no triangles. Then m≤2n-4.

Where m=9, n=6

⇒ 9 ≤ 12 - 4

⇒ 9 ≤ 8, which is to be false, then K

_{33}is non-planar graph.(ii) G

_{2}is a planar graph. Because it can be redrawn like as below.(iii) Let us assume G

_{3}be a planar graph then it also be satisfy useful corollary.Where m=9, n=6

then 9 ≤ 12-4

9 ≤ 8 is False

So, G

_{3}is non-planar graph.Answer: Only G

_{2}is planar graph.Question 14 |

Which of the following statements are FALSE?

For poisson distribution, the mean is twice the variance. | |

In queuing theory, if arrivals occur according to poisson distribution, then the inter-arrival time is exponentially distributed. | |

The distribution of waiting time is independent of the service discipline used in selecting the waiting customers for service. | |

If the time between successive arrivals is exponential, then the time between the occurences of every third arrival is also exponential. | |

Both (A) and (C). |

Question 14 Explanation:

In Poisson distribution, the mean is not equal to the twice the variance.

Option C is also False, because waiting time is dependent on the service discipline.

Option C is also False, because waiting time is dependent on the service discipline.

Question 15 |

Which one of the following statements (s) is/are FALSE?

Overlaying is used to run a program, which is longer than the address space of the computer. | |

Optimal binary search tree construction can be performed efficiently by using dynamic programming. | |

Depth first search cannot be used to find connected components of a graph. | |

Given the prefix and postfix walls over a binary tree, the binary tree can be uniquely constructed. | |

A, C and D. |

Question 15 Explanation:

Option A - False

As per the definition of address space memory used by the overlay comes under the address space of computer.

Option B: True

By using dynamic programming we can construct optimal binary search tree efficiently.

Option C: False

DFS can be used to find connected components of a graph.

Option D: False

Infix + C postfix or prefix is required to construct the binary tree uniquely.

As per the definition of address space memory used by the overlay comes under the address space of computer.

Option B: True

By using dynamic programming we can construct optimal binary search tree efficiently.

Option C: False

DFS can be used to find connected components of a graph.

Option D: False

Infix + C postfix or prefix is required to construct the binary tree uniquely.

Question 16 |

For secondary key processing which of the following file organizations is preferred? Give a one line justification:

Indexed sequential file organization. | |

Two-way linked list. | |

Inverted file organization. | |

Sequential file organization. |

Question 16 Explanation:

Inverted file organization, because of reasons are as follows:

→ An index for each secondary key.

→ An index entry for each distinct value of the secondary key.

→ Exhibits better enquiry performance.

→ An index for each secondary key.

→ An index entry for each distinct value of the secondary key.

→ Exhibits better enquiry performance.

There are 16 questions to complete.