## GATE 1989

Question 1 |

A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols S1 to S7 initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is

4 | |

5 | |

6 | |

3 |

→ 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 comparisons = 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 |

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

__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)} |

Transitive closure of R:

(a) It is transitive.

(b) It contains R.

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

Question 5 |

Match the pairs in the following questions:

(A) Cyclic redundancy code (p) Error correction (B) Serial communication (q) Wired-OR (C) Open collector (r) Error detection (D) Hamming code (s) RS-232-C

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

Question 6 |

Match the pairs in the following questions:

(A) Base addressing (p) Reentranecy (B) Indexed addressing (q) Accumulator (C) Stack addressing (r) Array (D) Implied addressing (s) Position independent

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

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 |

Match the pairs in the following questions:

(A) O(log n) (p) Heapsort (B) O(n) (q) Depth-first search (C) O(n log n) (r) Binary search (D) O(n^{2}) (s) Selection of the k^{th}smallest element in a set of n elements.

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

O(n) - Selection of the k

^{th}smallest element in a set of n elements

O(n log n) - Heapsort

O(n

^{2}) - Depth-first search

Question 8 |

Match the pairs in the following questions:

(A) Virtual memory (p) Temporal Locality (B) Shared memory (q) Spatial Locality (C) Look-ahead buffer (r) Address Translation (D) Look-aside buffer (s) Mutual Exclusion

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

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

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

Union | |

Intersection | |

Concatenation | |

Complementation | |

Both A and C |

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

^{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. |

¬Q → ¬P ⇔ Q ∨ ¬P

¬P ∨ Q ⇔ ¬P ∨ Q

¬Q → P ⇔ Q ∨ P

A, B and C are equivalent.

Question 13 |

Which of the following graphs is/are planner?

Theory Explanation is given below. |

_{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 occurrences of every third arrival is also exponential. | |

Both (A) and (C). |

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

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

→ An index for each secondary key.

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

→ Exhibits better enquiry performance.