CS GATE 2009 (Test 2)



Tag: cs gate 2009
Q.1
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?
A. 3
B. 8
C. 129
D. 216
Answer : Option D
Explaination / Solution:
No Explaination.


Workspace
Report
Q.2
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?
A. All processes will finish without any deadlock
B. Only P1 and P2 will be in a deadlock
C. Only P1 and P3 will be in deadlock
D. All three processes will be in deadlock
Answer : Option A
Explaination / Solution:
No Explaination.


Workspace
Report
Q.3
In the following process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state:

Now consider the following statements: 
I. If a process makes a transition D, it would result in another process making transition A immediately 
II. A process P2 in blocked state can take transition E while another process P1 is in running state 
III. The OS uses preemptive scheduling 
IV. The OS uses non-preemptive scheduling 
Which of the above statements are TRUE?
A. I and II
B. I and III
C. II and III
D. II and IV
Answer : Option C
Explaination / Solution:
No Explaination.


Workspace
Report
Q.4
The enter_CS( ) and leave_CS( ) functions to implement critical section of a process are realized using test-and-set instruction as follows:
void enter_CS ( X)
{
while (test-and-set (X))
}
void leave_CS (X)
{
X = 0;
}
In the above solution, X is a memory location associated with the CS and is initialized to 0. Now consider the following statements 
I. The above solution to CS problem is deadlock-free 
II. The solution is starvation free 
III. The processes enter CS in FIFO order 
IV. More than one process can enter CS at the same time 
Which of the above statements are TRUE?
A. I only
B. I and II
C. II and III
D. IV only
Answer : Option A
Explaination / Solution:
No Explaination.


Workspace
Report
Q.5
S → a Sa| bSb| a| b The language generated by the above grammar over the alphabet {a, b} is the set of
A. All palindromes
B. All odd length palindromes
C. Strings that begin and end with the same symbol
D. All even length palindromes
Answer : Option B
Explaination / Solution:
No Explaination.


Workspace
Report
Q.6
Which one of the following languages over the alphabet {0, 1} is described by the regular expression: (0 + 1)* 0 (0 + 1)* 0(0 + 1)*?
A. The set of all strings containing the substring 00
B. The set of all strings containing at most two ’s
C. The set of all string containing at least two ’s
D. The set of all strings that begin and end with either 0 or 1
Answer : Option C
Explaination / Solution:
No Explaination.


Workspace
Report
Q.7
Which one of the following is FALSE?
A. There is a unique minimal DFA for every regular language
B. Every NFA can be converted to an equivalent PDA
C. Complement of every context-free language is recursive
D. Every nondeterministic PDA can be converted to an equivalent deterministic PDA
Answer : Option D
Explaination / Solution:
No Explaination.


Workspace
Report
Q.8
Let L = L1 ∩ L2, where L1 and Lare languages as defined below:

Then L is 
A. Not recursive
B. regular
C. context – free but not regular
D. recursively enumerable but not context-free
Answer : Option C
Explaination / Solution:
No Explaination.


Workspace
Report
Q.9
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?
A. S1 and S2
B. S2 and S3
C. S3 only
D. S4 only
Answer : Option B
Explaination / Solution:
No Explaination.


Workspace
Report
Topic: Algorithms Tag: CS GATE 2009
Q.10
Let πbe a problem that belongs to the class NP. Then which one of the following is TRUE?
A. There is no polynomial time algorithm for πA
B. If πcan be solved deterministically in polynomial time, then P = NP
C. If πis NP-hard, then it is NP complete
D. πmay be undecidable
Answer : Option C
Explaination / Solution:
No Explaination.


Workspace
Report