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

A
4
B
5
C
6
D
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 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?

A
Passing an expression as a parameter
B
Passing an array as a parameter
C
Passing a pointer as a parameter
D
Passing as array element as a parameter
E
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 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.

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

A
{(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.
There are 4 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access