What is the number of swaps required to sort n elements using selection sort, in the worst case?

**A. ** θ(n)

**B. ** θ(n log n)

**C. ** θ(n2)

**D. ** θ(n^{2 }log n)

**Answer : ****Option A**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using
open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash
table?

**A. **

**B. **

**C. **

**D. **

**Answer : ****Option C**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

Consider the following relational schema:

**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 : ****Option D**

**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.

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’)

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

Let R be the relation on the set of positive integers such that a aRb if and only if a and b are
distinct and have a common divisor other than 1. Which one of the following statements
about R is true?

**A. ** R is symmetric and reflexive but not transitive

**B. ** R is reflexive but not symmetric and not transitive

**C. ** R is transitive but not reflexive and not symmetric

**D. ** R is symmetric but not reflexive and not transitive

**Answer : ****Option D**

**Explaination / Solution: **

R is not reflexive as each element can‟t be related to itself.

R is not reflexive as each element can‟t be related to itself.

R is symmetric

Let a = 3, b = 6 and c = 10 then 3 and 6 have a common division other than 1

6 and 10 have a common division other than 1

but 3 &10 have no common division other than 1

3R6 and 6R10 but
3R10

R is not transitive

Workspace

Report

In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of
the following statements is true?

**A. ** A tree has no bridges

**B. ** A bridge cannot be part of a simple cycle

**C. ** Every edge of a clique with size ≥ 3 is a bridge (A clique is any compete sub graph of a graph)

**D. ** A graph with bridges cannot have a cycle

**Answer : ****Option B**

**Explaination / Solution: **

Since, every edge in a tree is bridge

Since, every edge in a tree is bridge

(A) is false

Since, every edge in a complete graph
kn (n ≥ 3) is not a bridge (c) is false

Let us consider the following graph G:

This graph has a bridge i.e., edge „e‟ and a cycle of length „3‟

(D) is false

Since, in a cycle every edge is not a bridge

(B) is true

Workspace

Report

Consider two relations R1(A,B) with the tuples (1.5), (3,7) and R2 (A,C) = (1,7), (4,9).
Assume that R(A,B,C) is the full natural outer join of R_{1} and R_{2} . Consider the following
tuples of the form (A,B,C): a = (1.5,null), b = (1,null,7) c = (3,null,9), d = (4,7,null), e = (1,5,7), f = (3,7,null), g = (4,null,9).
Which one of the following statements is correct?

**A. ** R contains a,b,e,f,g but not c, d.

**B. ** R contains all of a,b,c,d,e,f,g

**C. ** R contains e,f,g but not a,b

**D. ** R contains e but not f,g.

**Answer : ****Option C**

**Explaination / Solution: **

Workspace

Report

Consider two binary operators '↑' and '↓' with the precedence of operator ↓ being lower than that of the operator ↑ . Operator ↑ is right associative while operator ↓, is left associative. Which one of the following represents the parse tree for expression (7 ↓ 3 ↑ 4 ↑ 3 ↓ 2)?

**A. **

**B. **

**C. **

**D. **

**Answer : ****Option B**

**Explaination / Solution: **

7 ↓ 3 ↑ 4 ↑ 3 ↓ 2 7 ↓ 3 ↑ (4 ↑ 3) ↓ 2 as ↑ is right associative 7 ↓ (3 ↑ (4 ↑ 3)) ↓ 2 (7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2 as ↓ is left associative

7 ↓ 3 ↑ 4 ↑ 3 ↓ 2 7 ↓ 3 ↑ (4 ↑ 3) ↓ 2 as ↑ is right associative 7 ↓ (3 ↑ (4 ↑ 3)) ↓ 2 (7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2 as ↓ is left associative

Workspace

Report

Consider evaluating the following expression tree on a machine with load-store
architecture in which memory can be accessed only through load and store
instructions. The variables a, b, c, d and e are initially stored in memory. The
binary operators used in this expression tree can be evaluated by the machine
only when the operands are in registers. The instructions produce result only in a
register. If no intermediate results can be stored in memory, what is the
minimum number of registers needed to evaluate this expression?

**A. ** 2

**B. ** 9

**C. ** 5

**D. ** 3

**Answer : ****Option D**

**Explaination / Solution: **

Total 3 Registers are required minimum

Workspace

Report

Consider a network with five nodes, N1 to N5, as shown below

**A. ** 3

**B. ** 9

**C. ** 10

**D. ** ∞

**Answer : ****Option C**

**Explaination / Solution: **

N3 has neighbors N2 and N4 N2 has made entry ∞ N4 has the distance of 8 to N1 N3 has the distance of 2 to N4 So 2 + 8 = 10

The net work uses a Distance Vector Routing protocol. Once the routes have stabilized, the distance vectors at different nodes are as following

N1 : (0, 1, 7, 8, 4)

N2 : (1, 0, 6, 7, 3)

N3 : (7, 6, 0, 2, 6)

N4 : (8, 7, 2, 0, 4)

N5 : (4, 3, 6, 4, 0)

Each distance vector is the distance of the best known path at that instance to nodes, N1 to N5, where the distance to itself is 0. Also, all links are symmetric and the cost is identical in both directions. In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between two rounds, any change in cost of a link will cause the two incident nodes to change only that entry in their distance vectors

After the update in the previous question, the link N1-N2 goes down. N2 will
reflect this change immediately in its distance vector as cost, ∞ . After the NEXT
ROUND of update, what will be the cost to N1 in the distance vector of N3?

N3 has neighbors N2 and N4 N2 has made entry ∞ N4 has the distance of 8 to N1 N3 has the distance of 2 to N4 So 2 + 8 = 10

Workspace

Report

Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals {S,
A} and terminals {a, b}.

**A. ** 1 3 2

**B. ** 2 2 3

**C. ** 2 3 1

**D. ** syntax error

**Answer : ****Option C**

**Explaination / Solution: **

S → aA {print 1}

S → a {print 2}

A → Sb {print 3}

Using the above SDTS, the output printed by a bottom-up parser, for the input aab is:

Workspace

Report

**Preparation Study Material**- Digital Electronics (Study/Preparation)
- Digital Logic Circuits (Study/Preparation)
- Computer Architecture (Study/Preparation)
- Programming and Data Structures I (Study/Preparation)
- Programming and Data Structure II (Study/Preparation)
- Database Management Systems (Study/Preparation)
- Computer Networks (Study/Preparation)
- Operating Systems (Study/Preparation)
- Software Engineering (Study/Preparation)
- Theory of Computation (Study/Preparation)
- Design and Analysis of Algorithms (Study/Preparation)
- Compiler Design (Study/Preparation)

- Engineering Mathematics (Practise Test)
- Digital Logic (Practise Test)
- Computer Organization and Architecture (Practise Test)
- Programming and Data Structures (Practise Test)
- Algorithms (Practise Test)
- Theory of Computation (Practise Test)
- Compiler Design (Practise Test)
- Operating System (Practise Test)
- Databases (Practise Test)
- Computer Networks (Practise Test)