CS GATE 2009 - Online Test
Q1. Match all items in Group I with correct options from those given in Group 2
Group 1 Group 2
P. Regular expression 1. Syntax analysis
Q. Pushdown automata 2. Code generation
R. Dataflow analysis 3. Lexical analysis
S. Register allocation 4. Code Optimization
Codes:
Answer : Option B
Explaination / Solution:
No Explaination.
Q2. Consider the following graph:
Which of the following is NOT the sequence of edges added to the minimum spanning tree using
Kruskal’s algorithm?
Answer : Option D
Explaination / Solution:
No Explaination.
Q3. In quick sort, for sorting n elements, the (n/4)th the smallest element is selected as pivot using an O(n)
time algorithm. What is the worst case time complexity of the quick sort?
Answer : Option B
Explaination / Solution:
No Explaination.
Q4. Let L = L1 ∩ L2, where L1 and L2 are languages as defined below:
Then L is
Answer : Option C
Explaination / Solution:
No Explaination.
Q5. Consider the following relational schema: Suppliers (sid:integer, sname: string, city:string, street:
string)
Parts (pid:integer, pname: string, color:string)
Catalog (sid:integer, pid:integer,
cost: real)
Consider the following relational query on the above database:
SELECT S.sname
FROM Suppliers S
WHERE S.sid NOT IN (SELECT C. sid
FROM Catalog C
WHERE C.pid NOT IN (SELECT P.pid
FROM Parts P
WHERE P.color<> ‘blue’))
Assume that relations corresponding to the above schema are not empty. Which one of the following is
the correct interpretation of the above query?
Answer : Option A
Explaination / Solution:
No Explaination.
Q6. Consider a 4-way set associative cache (initially empty) with total 16 cache blocks. The main memory
consists of 256 blocks and the request for memory blocks is in the following order:
0,255,1,4,3,8,133,159,216,129,63,8,48,32, 73, 92,155
Which one of the following memory block will not be in cache if LRU replacement policy is used?
Answer : Option D
Explaination / Solution:
No Explaination.
Q7. Consider two transactions T1 and T2, and four schedules S1, S2, S3, S4 of T1 and T2 as given below:
Which of the above sche dules are conflict-serializable?
Answer : Option B
Explaination / Solution:
No Explaination.
Q8. The following key values are inserted into a B+-tree in which order of the internal nodes is 3, and that
of the leaf nodes is 2, in the sequence given below. The order of internal nodes is the maximum number
of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that
can be stored in it. The B+-tree is initially empty. 10, 3, 6, 8, 4, 2, 1. The maximum number of times leaf
nodes would get split up as a result of these insertions is
Answer : Option C
Explaination / Solution:
No Explaination.
Q9. Consider the following relational schema: Suppliers (sid:integer, sname: string, city:string, street: string)
Parts (pid:integer, pname: string, color:string)
Catalog (sid:integer, pid:integer, cost: real)
Assume that, in the suppliers relation above, each supplier and each street within a city has a unique
name, and (sname, city) forms a candidate key. No other functional dependencies are implied other
than those implied by primary and candidate keys. Which one of the following is TRUE about the above
schema?
Answer : Option B
Explaination / Solution:
No Explaination.
Q10. Consider a system with 4 types of resources R1 (3 units), R2 (2 units),
R3 (3 units), R4 (2 units).
A non-preemptive resource allocation policy is used. At any given instance, a request is not entertained
if it cannot be completely satisfied. Three processes P1,P2,P3 request the resources as follows if executed independently.
Which one of the following statements is TRUE if all three processes run concurrently starting at time t
= 0?
Answer : Option A
Explaination / Solution:
No Explaination.
