# CS GATE 2014 PAPER 03 (Test 4)

Tag: cs gate 2014 paper 03
Q.1
Consider the C function given below. Assume that the array listA contains n (> 0) elements, sored in ascending order.
int ProcessArray (int * listA, int x, int n)
{
Int 1, 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 (1 < = j);
If (listA [k] = = x)
return (k) ;
else
return -1;
Which one of the following statements about the function ProcessArray is CORRECT?
A. It will run into an infinite loop when x is not in listA.
B. It is an implementation of binary search
C. It will always find the maximum element in listA.
D. It will return – 1 even when x is present in listA.
Explaination / Solution:

By the logic of the algorithm it is clear that it is an attempted implementation of Binary Search. So option C is clearly eliminated. Let us now check for options A and D. A good way to do this is to create small dummy examples (arrays) and implement the algorithm as it is. One may make any array of choice. Running iterations of the algorithm would indicate that the loop exits when the x is not present. So option A is wrong. Also, when x is present, the correct index is indeed returned. D is also wrong. Correct answer is B. It is a correct implementation of Binary Search.

Workspace
Report
Q.2
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’)

A. Names of all the employees with at least one of their customers having a ‘GOOD’ rating.
B. Names of all the employees with at most one of their customers having a ‘GOOD’ rating.
C. Names of all the employees with none of their customers having a ‘GOOD’ rating.
D. Names of all the employees with all their customers having a ‘GOOD’ rating.
Explaination / Solution:

The outer query will return the value (names of employees) for a tuple in relation E, only if inner query for that tuple will return no tuple (usage of NOT EXISTS). The inner query will run for every tuple of outer query. It selects cust-id for an employee e, if rating of customer is NOT good. Such an employee should not be selected in the output of outer query. So the query will return the names of all those employees whose all customers have GOOD rating.

Workspace
Report
Q.3
Consider the following processors (ns stands for nanoseconds). Assume that the pipeline registers have zero latency.
P1: Four-stage pipeline with stage latencies 1 ns, 2 ns, 2 ns, 1 ns.
P2: Four-stage pipeline with stage latencies 1 ns, 1.5 ns, 1.5 ns, 1.5 ns.
P3: Five-stage pipeline with stage latencies 0.5 ns, 1 ns, 1 ns, 0.6 ns, 1 ns.
P4: Five-stage pipeline with stage latencies 0.5 ns, 0.5 ns, 1 ns, 1 ns, 1.1 ns.
Which processor has the highest peak clock frequency?

A. P1
B. P2
C. P3
D. P4
Explaination / Solution:

Clock period (CP) = max stage delay + overhead Workspace
Report
Q.4
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
A. B. C. D. Explaination / Solution: Workspace
Report
Q.5
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?
B. Priority encoder
C. Multiplexor
D. Flip-flop
Explaination / Solution: ‘x’ is working as selection line, where the two input lines are ‘a’ and ‘b’, so the function F (x, y,a,b) can be implemented using (2× 1) multiplexer as follows: Workspace
Report
Q.6 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
A. 001, 010, 011
B. 111, 110, 101
C. 100, 110, 111
D. 100, 011, 001
Explaination / Solution: Workspace
Report
Q.7
Let ⊕ denote the Exclusive OR (XOR) operation. Let ‘1’ and ‘0’ denote the binary constants. Consider the following Boolean expression for F over two variables P and Q.
F(P,Q) = ((1⊕P)⊕(P⊕Q))⊕((P⊕Q)⊕(Q⊕0))
The equivalent expression for F is
A. P + Q
B. C. P ⊕ Q
D. Explaination / Solution: Workspace
Report
Q.8
he ratio of male to female students in a college for five years is plotted in the following line graph. If the number of female students in 2011 and 2012 is equal, what is the ratio of male students in 2012 to male students in 2011? A. 1:1
B. 2:1
C. 1.5:1
D. 2.5:1
Explaination / Solution:

Take number of female students in 2011=100 ∴ Number of male in 2011=100 No. of female in 2012=100 No. of male in 2012=150 Ratio = 150/100 = 1.5:1

Workspace
Report
Q.9
Let X and Y be finite sets and f : X → Y be a function. Which one of the following statements is TRUE?
A. For any subsets A and B of X, |f (A ∪ B)| = |f(A)| + |f(B)|
B. For any subsets A and B of X, f (A ∩ B) = f(A) ∩ f(B)
C. For any subsets A and B of X,|f (A ∩ B)| = min {|f(A)|,|f(B)|}
D. For any subsets S and T of Y, f-1(S ∩ T) = f-1(S) ∩ f-1(T)
Explaination / Solution: Workspace
Report
Q.10
Which one of the following statements is TRUE about every n × n matrix with only real eigenvalues?
A. If the trace of the matrix is positive and the determinant of the matrix is negative, at least one of its eigenvalues is negative.
B. If the trace of the matrix is positive, all its eigenvalues are positive.
C. If the determinant of the matrix is positive, all its eigenvalues are positive.
D. If the product of the trace and determinant of the matrix is positive, all its eigenvalues are positive.