# CS GATE 2013 (Test 3)

Tag: cs gate 2013
Q.1
Were you a bird, you ___________ in the sky
A. would fly
B. shall fly
C. should fly
D. shall have flown
Explaination / Solution:
No Explaination.

Workspace
Report
Q.2
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
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
Q.3
Consider the following sequence of micro–operations
MBR ← PC
MAR ← X
PC ← Y
Memory ← MBR
Which one of the following is a possible operation performed by this sequence?
A. Instruction fetch
B. Operand fetch
C. Conditional branch
D. Initiation of interrupt service
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

Workspace
Report
Topic: Databases Tag: CS GATE 2013
Q.4
Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values.
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. in INF, but not in 2NF
B. in 2NF, but not in 3NF
C. in 3NF, but not in BCNF
D. in BCNF
Explaination / Solution:

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

Workspace
Report
Q.5
Which of the following statements is/are FALSE?
(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.
A. 1 and 4 only
B. 1 and 3 only
C. 2 only
D. 3 only
Explaination / Solution:

(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
Q.6
Consider the DFA given below. 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
A. 1 and 3 only
B. 2 and 4 only
C. 2 and 3 only
D. 3 and 4 only
Explaination / Solution: (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
Q.7
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
Explaination / Solution:

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

Workspace
Report
Q.8
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?

A. Θ(n)
B. Θ(n + k)
C. Θ(nk)
D. Θ(n2)
Explaination / Solution:
No Explaination.

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

Workspace
Report
Q.10
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 