Questions and answers for exam Preparation

MCQs

Total Questions : 5

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

P + Q
`overline(P + Q)`
P `oplus` Q
`overline(P oplus Q)`

Discuss Question

Answer: Option D. -> `overline(P oplus Q)`

F (P, Q) = ((1 `oplus` P) `oplus` (P `oplus` Q)) `oplus` ((P `oplus` Q) `oplus` (Q `oplus` O))

= (`overline(P)` `oplus` (P`overline(Q)` + `overline(P)`Q)) `oplus` ((P`overline(Q)` + `overline(P)`Q) `oplus` Q)

=[`overline(P)`(PQ + `overline(P)` `overline(Q)`) + P(P`overline(Q)` + `overline(P)`Q)] `oplus` [(PQ + `overline(P)` `overline(Q)`) Q + (P`overline(Q)` + `overline(P)`Q)`overline(Q)`]

=(`overline(P)` `overline(Q)` + P`overline(Q)`) `oplus` (PQ + P`overline(Q)`) = `overline(Q)` `oplus` P = PQ + `overline(P)` `overline(Q)` = `overline(P oplus Q)`

Question 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')

Names of all the employees with at least one of their customers having a 'GOOD' rating.
Names of all the employees with at most one of their customers having a 'GOOD' rating
Names of all the employees with none of their customers having a 'GOOD' rating.
Names of all the employees with all their customers having a 'GOOD' rating

Discuss Question

Answer: Option D. -> Names of all the employees with all their customers having a 'GOOD' rating

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.

Question 3.

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

`forall`d (Rainy (d) ∧ ~ Cold (d))
`forall`d (~ Rainy (d) `rightarrow` Cold (d))
`exists`d (~ Rainy (d) `rightarrow` Cold (d))
`exists`d (Rainy (d) ∧ ~ Cold (d))

Discuss Question

Answer: Option D. -> `exists`d (Rainy (d) ∧ ~ Cold (d))

Given statement is ~ `forall` d [r (d) `rightarrow` c (d)]

`equiv` ~ `forall` d[ ~ r(d) `or` c (d)]

`equiv` `exists` d[ r (d) `and` ~ c(d)]

(Since p `rightarrow` q `equiv` ~ p `or` q and let r(d) be rainy day, c(d) be cold day)

Question 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?

In any planar embedding, the number of faces is at least`n/2` + 2
In any planar embedding, the number of faces is less than `n/2` + 2
There is a planar embedding in which the number of faces is less than `n/2` + 2
There is a planar embedding in which the number of faces is at most `n/(delta + 1)`

Discuss Question

Answer: Option A. -> In any planar embedding, the number of faces is at least`n/2` + 2

We know that v + r = e + 2 `rArr` e = n + r - 2 ... (1)

Where V = n(number of vertices) ;r number of faces and

e = number of edges

Given, `delta` `ge` 3 then 3n `ge` 2e

`rArr` e `ge` `(3n)/2`

`rArr` n + r - 2 `ge` `(3n)/2` (u sin g (1))

`rArr` r `ge` `(3n)/2` - n + 2 `rArr` r `ge` `n/2` + 2

`:.` Number of faces is atleast `n/2` + 2

Question 5.

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