CS and IT Gate 2014 Set-3 Questions with Answer

Ques 27 GATE 2014 SET-3

Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?

Ques 28 GATE 2014 SET-3

Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.
typedef struct treeNode* treeptr;
struct treeNode
{
treeptr leftMostChild, rightSibling;
};
int DoSomething (treeptr tree)
{
int value = 0;
if (tree != NULL) {
if (tree->leftMostChild == NULL)
value = 1;
else
value = DoSomething(tree->leftMostChild) + DoSomething(tree->rightSibling);
}
return (value);
}
When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the number of

Ques 29 GATE 2014 SET-3

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order.
int ProcessArray(int *listA, int x, int n)
{
int i, j, k;
i = 0;
j = n - 1;
do {
k = (i + j)/2;
if (x <= listA[k])
j = k - 1;
if (listA[k] <= x)
i = k + 1;
} while (i <= j);
if (listA[k] == x)
return (k);
else
return -1;
}
Which one of the following statements about the function ProcessArray is CORRECT?

Ques 30 GATE 2014 SET-3

What is the optimized version of the relation algebra expression πA₁ (πA₂ (σF₁ (σF₂ (r)))), where A₁, A₂ are sets of attributes in r with A₁ ⊆ A₂ and F₁, F₂ are Boolean expressions based on the attributes in r?

Ques 31 GATE 2014 SET-3

A prime attribute of a relation scheme R is an attribute that appears

Ques 32 GATE 2014 SET-3

Consider the transactions T₁, T₂, and T₃ and the schedules S₁ and S₂ given below.
T₁: r₁(X); r₁(Z); w₁(X); w₁(Z)
T₂: r₂(Y); r₂(Z); w₂(Z)
T₃: r₃(Y); r₃(X); w₃(Y)
S₁: r₁(X); r₃(Y); r₃(X); r₂(Y); r₂(Z); w₃(Y); w₂(Z); r₁(Z); w₁(X); w₁(Z)
S₂: r₁(X); r₃(Y); r₂(Y); r₃(X); r₁(Z); r₂(Z); w₃(Y); w₁(X); w₂(Z); w₁(Z)
Which one of the following statements about the schedules is TRUE?

Ques 33 GATE 2014 SET-3

Consider the relational schema given below, where empId of the relation dependent is a foreign key referring to empId of the relation employee. Assume that every employee has at least one associated dependent in the dependent relation.
employee (empId, empName, empAge)
dependent (depId, empId, depName, depAge)
Consider the following relational algebra query:
π_empId (employee) – π_empId (employee ⋈_{(empId = eID)∧(empAge ≤ depAge)} dependent)
The above query evaluates to the set of empIds of employees whose age is greater than that of

Ques 34 GATE 2014 SET-3

Consider the following relational schema:
employee (empId, empName, empDept)
customer (custId, custName, salesRepId, rating)
salesRepId is a foreign key referring to empId of the employee relation. Assume that each employee makes a sale to at least one customer. What does the following query return?
SELECT empName
FROM employee E
WHERE NOT EXISTS
(SELECT custId
FROM customer C
WHERE C.salesRepId = E.empId
AND C.rating <> 'GOOD');

Ques 35 GATE 2014 SET-3

The following functional dependencies hold for relations R(A, B, C) and S(B, D, E):
B → A,
A → C
The relation R contains 200 tuples and the relation S contains 100 tuples. What is the maximum number of tuples possible in the natural join R ⋈ S?

Ques 36 GATE 2014 SET-3

Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is conflict serializable?

Ques 37 GATE 2014 SET-3

Consider the following minterm expression for F:
F(P, Q, R, S) = Σ(0, 2, 5, 7, 8, 10, 13, 15)
The minterms 2, 7, 8 and 13 are 'do not care' terms. The minimal sum-of-products form for F is

Ques 38 GATE 2014 SET-3

Consider the following combinational function block involving four Boolean variables x, y, a, b where x, a, b are inputs and y is the output.
f(x, y, a, b)
{
if (x is 1)
y = a;
else
y = b;
}
Which one of the following digital logic blocks is the most suitable for implementing this function?

Ques 39 GATE 2014 SET-3

The above synchronous sequential circuit built using JK flip-flops is initialized with Q2Q1Q0 = 000. The state sequence for this circuit for the next 3 clock cycles is