Computer Science Engineering - Online Test
Q1. Consider the following schedule for transactions T1, T2 and T3:
T1 T2 T3
Read(X)
Read(Y)
Read(Y)
Write(Y)
Write(X)
Write(X)
Read(X)
Write(X)
Which one of the schedules below is the correct serialization of the above?
Answer : Option B
Explaination / Solution:
No Explaination.
Q2. A system has n resources R0,…,Rn-1, and k processes P0,…..Pk-1. The
implementation of the resource request logic of each process Pi. is as follows:
if (i% 2==0) {
if (i<n) request Ri;
if (i+2<n)request Ri+2 ;
}
else {
if (i<n) request Rn-i ;
if (i+2<n)request Rn-i-2 ;
}
In which one of the following situations is a deadlock possible?
Answer : Option B
Explaination / Solution:
No Explaination.
Q3. Which of the following languages is generated by the given grammar?
S → aS|bS|ε
Answer : Option D
Explaination / Solution:
Given grammar generates all strings of a’s and b’s including null string
∴ L = (a + b) *
Q4. The statement (¬p) ⇒ (¬q) is logically equivalent to which of the statements below?
I. p ⇒ q
II. q ⇒ p
III. (¬q) ∨ p
IV. (¬p) ∨ q
Answer : Option D
Explaination / Solution:
By rule of contrapositive,
Q5. 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.
Answer : Option C
Explaination / Solution:
Q: Sum of degrees of all vertices = 2 × (number of edges)
Q6. The following program consists of 3 concurrent processes and 3 binary
semaphores. The semaphores are initialized as S0=1, S1=0, S2=0.
How many times will process P0 print ‘0’?
Answer : Option D
Explaination / Solution:
No Explaination.
Q7. Suppose computers A and B have IP addresses 10.105.1.113 and 10.105.1.91
respectively and they both use the same net mask N. Which of the values of N
given below should not be used if A and B should belong to the same network?
Answer : Option C
Explaination / Solution:
No Explaination.
Q8. Which of the following decision problems are undecidable?
I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = Φ?
II. Given a CFG G = (N, Σ, P, S) and a string x ∈ Σ∗, does x ∈ L(G)?
III. Given CFGs G1 and G2, is L(G1) = L(G2)?
IV. Given a TM M, is L(M) = Φ?
Answer : Option C
Explaination / Solution:
There is no known algorithm to check whether the language accepted by TM is empty.
Similarly there is no algorithm to check whether language CFG’s are equivalent.
Q9. The following functional dependencies hold true for the relational schema R{V,W,X,Y,Z}:
V → W
VW → X
Y → VX
Y → Z
Which of the following is irreducible equivalent for this set of functional dependencies ?
Answer : Option A
Explaination / Solution:
Q10.
Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time
algorithm to solve A.
Answer : Option A
Explaination / Solution:
1. Cycle detection using DFS: O(V + E) = O(V2)and it is polynomial problem
2. Every P-problem is NP(since P ⊂ NP)
3. NP-complete ∈ NP
Hence, NP-complete can be solved in non-deterministic polynomial time
