Were you a bird, you ___________ in the sky

**A. ** would fly

**B. ** shall fly

**C. ** should fly

**D. ** shall have flown

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

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

Assume that source S and destination D are connected through two intermediate routers
labeled R. Determine how many times each packet has to visit the network layer and the data
link layer during a transmission from S to D.

**A. ** Network layer – 4 times and Data link layer-4 times

**B. ** Network layer – 4 times and Data link layer-3 times

**C. ** Network layer – 4 times and Data link layer-6 times

**D. ** Network layer – 2 times and Data link layer-6 times

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

**Explaination / Solution: **

From above given diagram, its early visible that packet will visit network layer 4 times, once
at each node [S, R, R, D] and packet will visit Data Link layer 6 times. One time at S and one
time at D, then two times for each intermediate router R as data link layer is used for link to
link communication.

Once at packet reaches R and goes up from physical –DL-Network and second time when
packet coming out of router in order Network – DL- Physical

Workspace

Report

Consider the following sequence of micro–operations

**A. ** Instruction fetch

**B. ** Operand fetch

**C. ** Conditional branch

**D. ** Initiation of interrupt service

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

**Explaination / Solution: **

PC content is stored in memory via MBR and PC gets new address from Y. It represents a function call (routine), which is matching with interrupt service initiation

MBR ← PC

MAR ← X

PC ← Y

Memory ← MBR

Which one of the following is a possible operation performed by this sequence?

PC content is stored in memory via MBR and PC gets new address from Y. It represents a function call (routine), which is matching with interrupt service initiation

Workspace

Report

Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values.

**A. ** in INF, but not in 2NF

**B. ** in 2NF, but not in 3NF

**C. ** in 3NF, but not in BCNF

**D. ** in BCNF

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

**Explaination / Solution: **

A → BC,B → CFH and F → EG are partial dependencies. Hence it is in 1NF but not in 2NF

F = {CH → G, A → BC, B → CFH, E → A, F → EG} is a set of functional dependencies (FDs) so that F+ is exactly the set of FDs that hold for R

The relation R is

A → BC,B → CFH and F → EG are partial dependencies. Hence it is in 1NF but not in 2NF

Workspace

Report

Which of the following statements is/are FALSE?

**A. ** 1 and 4 only

**B. ** 1 and 3 only

**C. ** 2 only

**D. ** 3 only

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

**Explaination / Solution: **

(1) NTM ≅ DTM

(1) For every non-deterministic Turing machine, there exists an equivalent deterministic
Turing machine.

(2) Turing recognizable languages are closed under union and complementation.

(3) Turing decidable languages are closed under intersection and complementation

(4) Turing recognizable languages are closed under union and intersection.

(1) NTM ≅ DTM

(2) RELs are closed under union & but not complementation

(3) Turing decidable languages are recursive and recursive languages are closed under
intersection and complementation

(4) RELs are closed under union & intersection but not under complementation

Workspace

Report

Consider the DFA given below.

**A. ** 1 and 3 only

**B. ** 2 and 4 only

**C. ** 2 and 3 only

**D. ** 3 and 4 only

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

**Explaination / Solution: **

Which of the following are FALSE?

1. Complement of L(A) is context–free

2. L(A) = L ((11*0+0)(0+1)*0*1*)

3. For the language accepted by A, A is the minimal DFA

4. A accepts all strings over {0, 1} of length at least 2

(1) L(A) is regular, its complement is also regular and if it is regular it is also context free.

(2) L(A) = (11*0+0)(0+1)*0*1* = 1*0(0+1)* Language has all strings where each string contains ‘0’.

(3) A is not minimal, it can be constructed with 2 states

(4) Language has all strings, where each string contains ‘0’. (atleast length one)

Workspace

Report

Which of the following statements is/are TRUE for undirected graphs?
P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.

**A. ** P only

**B. ** Q only

**C. ** Both P and Q

**D. ** Neither P nor Q

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

**Explaination / Solution: **

Q: Sum of degrees of all vertices = 2 × (number of edges)

Q: Sum of degrees of all vertices = 2 × (number of edges)

Workspace

Report

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter

MultiDequeue (Q) {

m = k

while (Q is not empty) and (m > 0) {

Dequeue (Q)

m = m - 1

}

}

What is the worst case time complexity of a sequence of n queue operations on an initially
empty queue?

No Explaination.

Workspace

Report

The number of elements that can be sorted in Θ(logn) time using heap sort is

**A. ** Θ(1)

**B. ** Θ( √log n)

**C. ** Θ(log n/log log n)

**D. ** Θ(log n)

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

**Explaination / Solution: **

After constructing a max-heap in the heap sort , the time to extract maximum element and then heapifying the heap takes Θ(log n) time by which we could say that Θ(log n) time is required to correctly place an element in sorted array. If Θ(logn) time is taken to sort using heap sort, then number of elements that can be sorted is constant which is Θ(1)

After constructing a max-heap in the heap sort , the time to extract maximum element and then heapifying the heap takes Θ(log n) time by which we could say that Θ(log n) time is required to correctly place an element in sorted array. If Θ(logn) time is taken to sort using heap sort, then number of elements that can be sorted is constant which is Θ(1)

Workspace

Report

The smallest integer than can be represented by an 8-bit number in 2’s complement form is

**A. ** -256

**B. ** -128

**C. ** -127

**D. ** 0

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

**Explaination / Solution: **

Workspace

Report