2014

1

Let `oplus` 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 `oplus` P) `oplus` (P `oplus` Q)) `oplus` ((P `oplus` Q) `oplus` (Q `oplus` O))

The equivalent expression for F is

A. P + Q

B. `overline(P + Q)`

C. P `oplus` Q

D. `overline(P oplus Q)`

Answer

Report

Discuss

2

Consider the following relational schema:

Employee (`underline(empId)`, empName, empDept)

Customer (`underline(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

Answer

Report

Discuss

3: The CORECT formula for the sentence, "not all rainy days are cold" is

A. `forall`d (Rainy (d) ∧ ~ Cold (d))

B. `forall`d (~ Rainy (d) `rightarrow` Cold (d))

C. `exists`d (~ Rainy (d) `rightarrow` Cold (d))

D. `exists`d (Rainy (d) ∧ ~ Cold (d))

Answer

Report

Discuss

4

Let `delta` denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices

with `delta` `ge` 3, which one of the following is TRUE?

A. In any planar embedding, the number of faces is at least`n/2` + 2

B. In any planar embedding, the number of faces is less than `n/2` + 2

C. There is a planar embedding in which the number of faces is less than `n/2` + 2

D. There is a planar embedding in which the number of faces is at most `n/(delta + 1)`

Answer

Report

Discuss

5: If G is a forest with n vertices and k connected components, how many edges does G have?

A. [n / k]

B. [n / k]

C. n - k

D. n - k + 1

Answer

Report

Discuss