Computer Science Engineering - Online Test
Q1. Consider the transition diagram of a PDA given below with input alphabet Σ = {a, b} and
stack alphabet Γ = {X , Z}. Z is the initial stack symbol. Let L denote the language accepted
by the PDA.
Which one of the following is TRUE?
Answer : Option D
Explaination / Solution:
No Explaination.
Q2. A relational schema for a train reservation database is given below 
Passenger (pid, pname, age)
Reservation (pid, cass, tid)
What pids are returned by the following SQL query for the above instance of the
tables?
SELECT pid
FROM Reservation
WHERE class ' AC ' AND
EXISTS (SELECT *
FROM Passenger
WHERE age> 65 AND
Passenger.pid = Reservation.pid)
Answer : Option D
Explaination / Solution:
No Explaination.
Q3. In the following truth table, V = 1 if and only if the input is valid
What function does the truth table represent?
Answer : Option A
Explaination / Solution:
4 to 2 priority encoder.
Q4. Consider the following grammar.
What is FOLLOW (Q) ?
Answer : Option C
Explaination / Solution:
FOLLOW(Q) is FIRST(R) hence
FIRST(R) = {w, ϵ}
We add ‘w’ in FOLLOW(Q) and for ϵ we calculate FIRST(S)
FIRST(S) ={y}
FOLLOW(Q) is {w ,y}
Q5. Suppose the predicate F(x, y, t) is used to represent the statement that person x
can fool person y at time t. which one of the statements below expresses best
the meaning of the formula ∀x ∃y ∃t (¬F (x, y, t))?
Answer : Option D
Explaination / Solution:
No Explaination.
Q6.
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?
Answer : Option A
Explaination / Solution:
No Explaination.
Q7. Consider the following context-free grammar over the alphabet ∑ = {a,b,c} with S as the start
symbol.
S → abScT|abcT
T → bT|b
Which one of the following represents the language generated by the above grammar ?
Answer : Option B
Explaination / Solution:
The given Grammar over Σ = {a, b, c} with S as the start symbol is
S → abScT | abcT
T→ bT | b
The minimum length string generated by the grammar is 1:
S→abcT→abcb ; hence all variable greater than 1.
Other cases
S → abScT→ ab abScT cT → ab ab abScT cT cT →........→ (ab)n (cT)n
Here T can generate any number of b’s starting with single b.
Q8. The following functional dependencies hold for relations R(A, B, C) and S(B, D, E) B → A,
A → C The relation R contains 200tuples and the relation S contains 100tuples. What is
the maximum number of tuples possible in the natural join R 
S?
S?
Answer : Option A
Explaination / Solution:
No Explaination.
Q9. The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42.
Which one of the following is the postorder traversal sequence of the same tree?
Answer : Option D
Explaination / Solution:
Pr eorder :30,20,10,15,25,23,39,35,42 
Inorder :10,15,20,23,25,30,35,39,42
Q10. If G is grammar with productions S → SaS|aSb|bSa|SS|∈ where S is the start variable, then which one of the following is not generated by G?
Answer : Option D
Explaination / Solution:
No Explaination.
