CS GATE 2012 - Online Test
Q1. What is the complement of the language accepted by the NFA show below?
Assume Σ ={a} and ε is the empty string.
Answer : Option B
Explaination / Solution:
Language accepted by NFA is a+ , so complement of this language is {є}
Q2. A file system with 300 GByte disk uses a file descriptor with 8 direct block addresses, 1
indirect block address and 1 doubly indirect block address. The size of each disk block is 128
Bytes and the size of each disk block address is 8 Bytes. The maximum possible file size in
this file system is
Answer : Option B
Explaination / Solution:
Each block size = 128 Bytes
Disk block address = 8 Bytes
∴ Each disk can contain = 128/8 = 16 addresses
Size due to 8 direct block addresses: 8 x 128
Size due to 1 indirect block address: 16 x 128
Size due to 1 doubly indirect block address: 16 x 16 x 128
Size due to 1 doubly indirect block address: 16 x 16 x 128
So, maximum possible file size:
= 8×128 +16×128 +16×16×128=1024 + 2048 + 32768=35840 Bytes= 35KBytes
Q3. Which of the following assertions are CORRECT?
P: Adding 7 to each entry in a list adds 7 to the mean of the list
Q: Adding 7 to each entry in a list adds 7 to the standard deviation of the list
R: Doubling each entry in a list doubles the mean of the list
S: Doubling each entry in a list leaves the standard deviation of the list unchanged
Answer : Option C
Explaination / Solution:
P and R always hold true
Else consider a sample set {1, 2, 3, 4} and check accordingly
Q4. What is the correct translation of the following statement into mathematical logic?
“Some real numbers are rational”
Answer : Option C
Explaination / Solution:
Option A: There exists x which is either real or rational and can be both.
Option B: All real numbers are rational
Option C: There exists a real number which is rational.
Option D: There exists some number which is not rational or which is real.
Q5. Fetch_And_Add (X, i) is an atomic Read-Modify-Write instruction that reads the value of
memory location X, increments it by the value i, and returns the old value of X. It is used in
the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared
variable initialized to 0. The value of 0 corresponds to lock being available, while any nonzero
value corresponds to the lock being not available.
AcquireLock(L){
While (Fetch_And_Add(L,1))
L = 1;
}
Release Lock(L){
L = 0;
}
This implementation
Answer : Option B
Explaination / Solution:
1. Acquire lock (L) {
2. While (Fetch_And_Add(L, 1))
3. L = 1.
}
4. Release Lock (L) {
5. L = 0;
6. }
Let P and Q be two concurrent processes in the system currently executing as follows
P executes 1,2,3 then Q executes 1 and 2 then P executes 4,5,6 then L=0 now Q executes 3 by which L will be set to 1 and thereafter no process can set
L to zero, by which all the processes could starve.
Q6. Given the sequence of terms, AD CG FK JP, the next term is
Answer : Option A
Explaination / Solution:
Q7. Consider the 3 process, P1, P2 and P3 shown in the table
The completion order of the 3 processes under the policies FCFS and RR2 (round robin
scheduling with CPU quantum of 2 time units) are
Answer : Option C
Explaination / Solution:
For FCFS Execution order will be order of Arrival time so it is P1,P2,P3
Next For RR with time quantum=2,the arrangement of Ready Queue will be as follows:
RQ: P1,P2,P1,P3,P2,P1,P3,P2
This RQ itself shows the order of execution on CPU(Using Gantt Chart) and here it gives the
completion order as P1,P3,P2 in Round Robin algorithm.
Q8. For the grammar below, a partial LL(1) parsing table is also presented along with the
grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty
string, $ indicates end of input, and | separates alternate right hand sides of productions.
S → a AbB| bAa B| ε
A → S
B → S
The First and Follow sets for the non-terminals A and B are
Answer : Option A
Explaination / Solution:
Q9. Which one of the following options is the closest in meaning to the word given below?
Mitigate
Answer : Option A
Explaination / Solution:
No Explaination.
Q10. For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, $ indicates end of input, and | separates alternate right hand sides of productions.
S → a AbB| bAa B| ε
A → S
B → S
The appropriate entries for E1, E2, and E3 are
Answer : Option C
Explaination / Solution:
