CS GATE 2011 - Online Test
Q1. Let the page fault service time be 10ms in a computer with average memory
access time being 20ns. If one page fault is generated for every 106 memory
accesses, what is the effective access time for the memory?
Answer : Option B
Explaination / Solution:
P = page fault rate 
EA = p × page fault service time
+(1 - p) × Memory access time
Q2. Definition of a language L with alphabet {a} is given as following
L = {ank | k > 0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?
Answer : Option B
Explaination / Solution:
Let n = 3 and k=1
(n + 1) states
Q3. A max-heap is a heap where the value of each parent is greater than or equal to
the value of its children. Which of the following is a max-heap?
Answer : Option B
Explaination / Solution:
Heap is a complete binary tree
Q4. Let the time taken to switch between user and kernel modes of execution be t1 while the time taken to switch between two processes be t2. Which of the
following is TRUE?
Answer : Option C
Explaination / Solution:
Process switching also involves mode changing.
Q5. A deterministic finite automation (DFA)D with alphabet ∑ = {a,b} is given below
Which of the following finite state machines is a valid minimal DFA which accepts
the same language as D?
Answer : Option A
Explaination / Solution:
Options B and C will accept the string b
Option – D will accept the string “bba”
Both are invalid strings.
So the minimized DFA is option A
Q6. A computer handles several interrupt sources of which the following are relevant
for this question.
Interrupt from CPU temperature sensor
Interrupt from Mouse
Interrupt from Keyboard
Interrupt from Hard Disk
Answer : Option D
Explaination / Solution:
No Explaination.
Q7. Which of the given options provides the increasing order of asymptotic
complexityoffunctions f1,f2,f3 and f4?
Answer : Option A
Explaination / Solution:
Q8. Consider the languages L1, L2 and L3 as given below
Which of the following statements is NOT TRUE?
Answer : Option C
Explaination / Solution:
L1: regular language
L2: context free language
L3: context sensitive language
Q9. 
The following is comment written for a C function
/* This function computes the roots of a quadratic equation
a.x^2+b.x+c=0. The function stores two real roots
in *root1 and *root2 and returns the status of validity of
roots. It handles four different kinds of cases.
(i) When coefficient a is zero irrespective of discriminant
(ii) When discriminant is positive
(iii) When discrimanant is zero
(iv) When discrimanant is negative
Only in cases (ii) and (iii), the stored roots are valid.
Otherwise 0 is stored in the roots. the function returns 0 when
the roots are valid and -1 otherwise.
The functin also ensures root1>=root2.
int get_QuadRoots (float a, float b, float c, float *root1, float *root2) ;
*/
A software test engineer is assigned the job of doing black box testing. He comes
up with the following test cases, many of which are redundant.
Which one of the following options provide the set of non-redundant tests using
equivalence class partitioning approach from input perspective for black box
testing?
Answer : Option C
Explaination / Solution:
T1 and T2 checking same condition a = 0 hence, any one of T1 and T2 is
redundant.
T3, T4: in both case discriminant (D)= b2 − 4ac = 0 . Hence any one of it is
redundant.
T5 : D>0
T6 : D<0
Q10. Which one of the following options is CORRECT given three positive integers x, y and z, and a predicate
P (x) = ¬ (x = 1) ∧ ∀y (∃z (x = y * z) ⇒ (y = x) ∨ (y = 1))
Answer : Option A
Explaination / Solution:
No Explaination.
