GATE 2007
Question 1 
Consider the following two statements about the function f(x)=x
P. f(x) is continuous for all real values of x Q. f(x) is differentiable for all real values of x
Which of the following is TRUE?
P is true and Q is false.  
P is false and Q is true.  
Both P and Q are true.  
Both P and Q are false. 
→ f(x) is continuous for all real values of x
For every value of x, there is corresponding value of f(x).
For x is positive, f(x) is also positive
x is negative, f(x) is positive.
So, f(x) is continuous for all real values of x.
→ f(x) is not differentiable for all real values of x. For x<0, derivative is negative
x>0, derivative is positive.
Here, left derivative and right derivatives are not equal.
Question 2 
Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equivalence relations on S are:
n and n  
n^{2} and n  
n^{2} and 0  
n and 1 
→ Reflexive
→ Symmetric
→ Transitive
Let a set S be,
S = {1, 2, 3}
Now, the smallest relation which is equivalence relation is,
S×S = {(1,1), (2,2), (3,3)}
= 3
= n (for set of n elements)
And, the largest relation which is equivalence relation is,
S×S = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}
= 9
= 3^{2}
= n^{2} (for set of n elements)
Question 3 
What is the maximum number of different Boolean functions involving n Boolean variables?
n^{2}  
2^{n}  
2^{2n}  
2^{n2} 
Number of variables= n
Number of input combinations is 2^{n}.
Each “boolean” function has two possible outputs i.e 0 and 1.
Number of boolean functions possible is 2^{2n}.
Formula: The number of mary functions possible with n kary variables is m^{kn}.
Question 4 
Let G be the nonplanar graph with the minimum possible number of edges. Then G has
9 edges and 5 vertices  
9 edges and 6 vertices  
10 edges and 5 vertices  
10 edges and 6 vertices 
if n ≥ 3 then e ≤ 3n6 (for planarity)
where n = no. of vertices
e = no. of edges
Now lets check the options.
A) e=9, n=5
9 ≤ 3(5)  6
9 ≤ 15  6
9 ≤ 9
Yes, it is planar.
B) e=9, n=6
9 ≤ 3(6)  6
9 ≤ 18  6 9 ≤ 12 Yes, it is planar.
iii) e=10, n=5
10 ≤ 3(5)  6
10 ≤ 15  6
10 ≤ 9 No, it is not planar.
So, option C is nonplanar graph.
iv) e=10, n=6
10 ≤ 3(6)  6
10 ≤ 18  6
10 ≤ 12
Yes, it is planar.
Question 5 
Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering?
1 2 3 4 5 6  
1 3 2 4 5 6  
1 3 2 4 6 5  
3 2 4 1 6 5 
(i) Go with vertex with indegree 0.
(ii) Then remove that vertex and also remove the edges going from it.
(iii) Repeat again from (i) till every vertex is completed.
Now we can see that in option (D), '3' is given first which is not possible because indegree of vertex '3' is not zero.
Hence option (D) is not topological ordering.
Question 6 
Which of the following problems is undecidable?
Membership problem for CFGs.  
Ambiguity problem for CFGs.  
Finiteness problem for FSAs.  
Equivalence problem for FSAs. 
Question 7 
Which of the following is TRUE?
Every subset of a regular set is regular.  
Every finite subset of a nonregular set is regular.  
The union of two nonregular sets is not regular.
 
Infinite union of finite sets is regular. 
Every subset of regular set is regular, is false. For example L = {an bn  n ≥ 0} is subset of ∑* and L is CFL, whereas ∑* is regular. Hence, every subset of regular set need not be regular.
The union of two nonregular sets is not regular, is also a false statement.
For example, consider two CFL’s.
L = {a^{n} b^{n}  n ≥ 0} and its complement L^{c} = {a^{m} b^{n}  m ≠ n } U b*a*.
If we take UNION of L and L^{c} , we will get ∑*, which is regular. Hence the UNION of two nonregular set may or may not be regular.
The statement, Infinite union of finite sets is regular is also a false statement.
Question 8 
How many 3to8 line decoders with an enable input are needed to construct a 6to64 line decoder without using any other logic gates?
7  
8  
9  
10 
So, we can say that
8 lines covered by  1 decoder
1 line covered by  1/8 decoder
64 lines covered by  64/8 = 8 decoders
8 lines covered by  8/8 = 1 decoder
Hence total no. of decoder needed is,
8 + 1 = 9 decoders.
Question 9 
Consider the following Boolean function of four variables:
f(w,x,y,z) = ∑(1,3,4,6,9,11,12,14)The function is:
independent of one variable.  
independent of two variables.  
independent of three variables.  
dependent on all the variables. 
w and y are not needed to represent the function f. So f is independent of two variables.
Question 10 
Consider a 4way set associative cache consisting of 128 lines with a line size of 64 words. The CPU generates a 20bit address of a word in main memory. The number of bits in the TAG, LINE and WORD fields are respectively:
9, 6, 5  
7, 7, 6  
7, 5, 8  
9, 5, 6 
Each line size 64 words, so no. of bits for WORD = 6 bits
Because it is 4way set associative cache, no. of sets in the cache = 128/4 = 32 = 2^{5}
No. of bits for the set number = 5
Because the address is 20bits long, no. of TAG bits = 2056 = 9
Question 11 
Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stored in a bit serial manner in a sector. The capacity of the disk pack and the number of bits required to specify a particular sector in the disk are respectively:
256 Mbyte, 19 bits  
256 Mbyte, 28 bits  
512 Mbyte, 20 bits  
64 Gbyte, 28 bit 
So the disk pack capacity = 16 * 128 * 256 * 512 bytes = 256 MB
To specify a sector we need the information about surface number, track number and sector number within a track. Surface number needs 4 bits as there are 16 surfaces(2^{4}), track number needs 7 bits as there are 128 tracks(2^{7}) within a surface, within a track the sector number needs 8 bits as there are 256 sectors (2^{8}). Total number bits needed to specify a particular sector = 4+7+8 = 19 bits. Hence option A is the answer.
Question 12 
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:
2^{h}−1  
2^{h−1} – 1  
2^{h+1}– 1  
2^{h+1}

1, 3, 7, 15, 31, ... = 2^{h+1}  1
Question 13 
The maximum number of binary trees that can be formed with three unlabeled nodes is:
1  
5  
4  
3 
Total no. of possible trees is 5.
Total = 5
Question 14 
Which of the following sorting algorithms has the lowest worstcase complexity?
Merge sort  
Bubble Sort  
Quick Sort  
Selection Sort 
Merge sort→ O(nlogn)
Bubble sort→ O(n^{2})
Quick sort→ O(n^{2})
Selection sort→ O(n^{2})
Question 15 
Consider the following segment of Ccode:
int j, n; j = 1; while (j <= n) j = j*2;
The number of comparisons made in the execution of the loop for any n > 0 is: Base of Log is 2 in all options.
⌈log_{2}n⌉ + 1
 
n  
⌈log_{2}n⌉  
⌊log_{2}n⌋ + 1 
1<=6 (✔️)
2<=6 (✔️)
4<=6 (✔️)
8<=6 (❌)
4 comparisons required
Option A:
[log n]+1
[log 6]+1
3+1 = 4 (✔)
Option B:
n=6 (❌)
Option C:
[log n]
[log 6]=3 (❌)
Option D:
[log_{2}n]+1
[log_{2}6]+1 = 2+1 = 3 (❌)
Question 16 
Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match entries in Group 1 to entries in Group 2.
Group I Group II (P) Gang Scheduling (1) Guaranteed Scheduling (Q) Rate Monotonic Scheduling (2) Realtime Scheduling (R) Fair Share Scheduling (3) Thread Scheduling
P – 3 Q – 2 R – 1  
P – 1 Q – 2 R – 3  
P – 2 Q – 3 R – 1  
P – 1 Q – 3 R – 2 
⇒ Rate monotonic scheduling is used in Realtime operating system.
⇒ Fair share scheduling distributes the CPU equally among users due to which it generates scheduling process.
Question 17 
Consider the following statements about user level threads and kernel level threads. Which one of the following statements is FALSE?
Context switch time is longer for kernel level threads than for user level threads.  
User level threads do not need any hardware support.
 
Related kernel level threads can be scheduled on different processors in a multiprocessor system.  
Blocking one kernel level thread blocks all related threads. 
B) True, because kernel is not involved in it.
C) True
D) Blocking one kernel level thread blocks all related threads is false, because kernel level threads are independent.
Question 18 
Which one of the following is a topdown parser?
Recursive descent parser.  
Operator precedence parser.  
An LR(k) parser.
 
An LALR(k) parser. 
Question 19 
In Ethernet when Manchester encoding is used, the bit rate is:
Half the baud rate.
 
Twice the baud rate.  
Same as the baud rate.  
None of the above. 
Question 20 
Which one of the following uses UDP as the transport protocol?
HTTP  
Telnet  
DNS  
SMTP 
HTTP, Telnet and SMTP uses TCP.
Question 21 
How many different nonisomorphic Abelian groups of order 4 are there?
2  
3  
4  
5 
4 = 2^{2}
So, prime no. is 2 and power of 2 is 2. So exponent value 2 is considered now.
Now the no. of ways we can divide 2 into sets will be the answer.
So division can be done as,
{1,1}, {0,2}
in two ways. Hence, answer is 2.
Question 22 
Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a predicate which denotes that x is connected. Which of the following first order logic sentences DOES NOT represent the statement: “Not every graph is connected”?
¬∀x (Graph (x) ⇒ Connected (x))  
¬∃x (Graph (x) ∧ ¬Connected (x))  
¬∀x (¬Graph (x) ∨ Connected (x))  
∀x (Graph (x) ⇒ ¬Connected (x))

Given expression is
¬∀x(¬Graph(x) ∨ Connected(x)
which can be rewritten as,
¬∀x(Graph(x) ⇒ Connected(x)
which is equivalent to option (A)
(∵ ¬p∨q ≡ p→q)
So, option (A) and (C) cannot be the answer.
Coming to option (B), the given expression is,
∃x (Graph (x) ∧ ¬Connected (x))
"There exist some graph which is not connected", which is equivalent in saying that "Not every graph is connected".
Coming to option (D),
For all x graph is not connected, which is not correct.
Hence, option (D) is the answer.
Question 23 
Which of the following graphs has an Eulerian circuit?
Any kregular graph where k is an even number.  
A complete graph on 90 vertices.  
The complement of a cycle on 25 vertices.
 
None of the above. 
→ all vertices in the graph have an "even degree".
→ And the graph must be corrected.
Now in option (C) it is saying that the complement of a cycle on 25 vertices without complement the degree of each vertex is 2.
Now since there are 25 vertices, so maximum degree of each vertex will be 24 and so in complement of cycle each vertex degree will be 24  2 = 22.
There is a theorem which says "G be a graph with n vertices and if every vertex has a degree of atleast n1/2 then G is connected."
So we can say that complement of cycle with 25 vertices fulfills both the conditions, and hence is Eulerian circuit.
Question 24 
Suppose we uniformly and randomly select a permutation from the 20! Permutations of 1, 2, 3,….., 20. What is the probability that 2 appears at an earlier position than any other even number in the selected permutation?
1/2  
1/10  
9!/20!  
None of these 
→ Total no. of possible even number = 10
→ Here we are not considering odd number.
→ The probability that 2 appears at an earlier position than any other even number is =1/10
Question 25 
Let A be a 4 x 4 matrix with eigenvalues 5, 2, 1, 4. Which of the following is an eigenvalue of
[A I] [I A]
where I is the 4 x 4 identity matrix?
5  
7  
2  
1 
(AλI)^{2}I = 0 [a^{2}b^{2} = (a+b)(ab)]
(AλI+I)(AλII) = 0
(A(λI)I)(A(λ+I)I = 0
Let us assume:
λ1=k & λ +1=k
λ =k+1 λ =k1
⇓ ⇓
for k=5; λ=4 λ =6
k=2; λ=1 λ =3
k=1; λ=2 λ = 0
k=4; λ=5 λ = 3
So, λ = 4,1,2,5,6,3,0,3
Check with the option
Option C = 2
Question 26 
Consider the set S = {a,b,c,d}. Consider the following 4 partitions π_{1}, π_{2}, π_{3}, π_{4} on Let p be the partial order on the set of partitions S' = {π_{1}, π_{2}, π_{3}, π_{4}} defined as follows: π_{i} p π_{j} if and only if π_{i} refines π_{j}. The poset diagram for (S', p) is:
And, neither π_{2} refines π_{3}, nor π_{3} refines π_{2}.
Here, only π_{1} refined by every set, so it has to be at the top.
Finally, option C satisfies all the property.
Question 27 
Consider the set of (column) vectors defined by X = {x ∈ R^{3} x_{1}+x_{2}+x_{3} = 0, where x^{T} = [x_{1},x_{2},x_{3}]^{T}}. Which of the following is TRUE?
{[1,1,0]^{T}, [1,0,1]^{T}} is a basis for the subspace X.  
{[1,1,0]^{T}, [1,0,1]^{T}} is a linearly independent set, but it does not span X and therefore is not a basis of X.  
X is not a subspace of R^{3}  
None of the above

Question 28 
Consider the series obtained from the NewtonRaphson method. The series converges to
1.5  
√2  
1.6  
1.4 
x_{n+1} = x_{n}/2+9/8x_{n} ⟶ (I); x_{0} = 0.5
Equation based on NewtonRaphson is
x_{n+1} = x_{n}f(x_{n})/f'(x_{n}) ⟶ (II)
Equate I and II
x_{n}f(x_{n})/f'(x_{n}) = x_{n}/2+9/8x_{n}
x_{n}f(x_{n})/f'(x_{n}) = x_{n}x_{n}/2+9/8x_{n}
x_{n}f(x_{n})/f'(x_{n}) = x_{n}(4x^{n2}9)/8x_{n}
So, f(x) = 4x^{n2}9
4x^{2}9 = 0
4x^{2} = 9
x^{2} = 9/4
x = ±3/2
x=±1.5
Question 29 
A minimum state deterministic finite automaton accepting the language L = {w  w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has
15 states  
11 states  
10 states  
9 states 
Question 30 
The language L = {0^{i}21^{i}  i≥0} over the alphabet {0, 1, 2} is:
not recursive.  
is recursive and is a deterministic CFL.
 
is a regular language.
 
is not a deterministic CFL but a CFL. 
Question 31 
Which of the following languages is regular?
{ww^{R}w ∈ {0,1}^{+}}  
{ww^{R}xx, w ∈ {0,1}^{+}}  
{wxw^{R}x, w ∈ {0,1}^{+}}  
{xww^{R}x, w ∈ {0,1}^{+}} 
0 (0+1)^{+} 0 + 1 (0+1)^{+} 1
Any string which begins and ends with same symbol, can be written in form of “wxw^{r}”
For example consider a string: 10010111, in this string “w=1” , “x= 001011” and w^{r} = 1.
Hence any string which begins and ends with either “0” or with “1” can be written in form of “wxw^{r}” and L = {wxw^{r}  x,w ϵ {0,1}^{+}} is a regular language.
Question 32 
Let f(w, x, y, z) = ∑(0, 4, 5, 7, 8, 9, 13, 15). Which of the following expressions are NOT equivalent to f?
 (P) x'y'z' + w'xy' + wy'z + xz
(Q) w'y'z' + wx'y' + xz
(R) w'y'z' + wx'y' + xyz + xy'z
(S) x'y'z' + wx'y' + w'y
P only
 
Q and S  
R and S  
S only 
(P), (Q), (R) cover all the minterms and are equivalent to f(w,x,y,z) = Σ(0,4,5,7,8,9,13,15).
(S) covers the minterms m_{0}, m_{8}, m_{9}, m_{2}, m_{3}, m_{6}, m_{7}.
(S) is not covering the minterms m_{4}, m_{5}, m_{13}, m_{15}.
Question 33 
Define the connective * for the Boolean variables X and Y as: X * Y = XY + X'Y'. Let Z = X * Y.
Consider the following expressions P, Q and R.
P: X = Y⋆Z Q: Y = X⋆Z R: X⋆Y⋆Z = 1
Which of the following is TRUE?
Only P and Q are valid.  
Only Q and R are valid.
 
Only P and R are valid.  
All P, Q, R are valid. 
= Y(XY + X’Y’) + Y’(XY+X’Y’)’
= XY+Y’(X ⊕ Y)
= XY+Y’(XY’+X’Y)
= XY+XY’
= X(Y+Y’) = X
Q: X*Z = (XZ + X’Z’)
= X(XY + X’Y’) + X’(XY + X’Y’)’
= XY+X’(X’Y+XY’)
= XY+X’Y
= (X+X’)Y = Y
R: X* Y*Z
= X*X Since P: Y*Z= X
= XX + X’X’
= 1
Question 34 
Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of n variables. What is the minimum size of the multiplexer needed?
2^{n} line to 1 line  
2^{n+1} line to 1 line  
2^{n1} line to 1 line
 
2^{n2} line to 1 line 
A 2^{n} X 1 multiplexer can implement any function of n variables. As n variables are given to select lines, so that true and complement forms of all variables get generated inside the MUX.
As one inverter is available, we can generate complement of one variable outside of the Multiplexer. And remaining (n1) variables are given to select lines. With this we have true and complement form of all n variables.
So, the answer is 2^{n1} X 1 MUX.
Question 35 
In a lookahead carry generator, the carry generate function G_{i} and the carry propagate function P_{i} for inputs A_{i} and B_{i} are given by:
P_{i} = A_{i} ⨁ B_{i} and G_{i} = A_{i}B_{i}
The expressions for the sum bit S_{i} and the carry bit C_{i+1} of the lookahead carry adder are given by:
S_{i} = P_{i} ⨁ C_{i} and C_{i+1} = G_{i} + P_{i}C_{i} , where C_{0} is the input carry.
Consider a twolevel logic implementation of the lookahead carry generator. Assume that all P_{i} and G_{i} are available for the carry generator circuit and that the AND and OR gates can have any number of inputs. The number of AND gates and OR gates needed to implement the lookahead carry generator for a 4bit adder with S3, S2, S1, S0 and C4 as its outputs are respectively:
6, 3  
10, 4  
6, 4  
10, 5 
Question 36 
The control signal functions of a 4bit binary counter are given below (where X is “don’t care”) The counter is connected as follows:
The counter is connected as follows:
Assume that the counter and gate delays are negligible. If the counter starts at 0, then it cycles through the following sequence:
0, 3, 4  
0, 3, 4, 5  
0, 1, 2, 3, 4  
0, 1, 2, 3, 4, 5 
Here, initial state is 0000. It goes through 0001,0010,0011,0100 and 0101. When the state is 5(0101) it immediately resets to initial state 0. Here, state 5 is not considered as valid state.
So valid states are 0,1,2,3, and 4 and hence it is a Mod5 counter.
Question 37 
Consider a pipelined processor with the following four stages:
IF: Instruction Fetch ID: Instruction Decode and Operand Fetch EX: Execute WB: Write Back
The IF, ID and WB stages take one clock cycle each to complete the operation. The number of clock cycles for the EX stage depends on the instruction. The ADD and SUB instructions need 1 clock cycle and the MUL instruction needs 3 clock cycles in the EX stage. Operand forwarding is used in the pipelined processor. What is the number of clock cycles taken to complete the following sequence of instructions?
ADD R2, R1, R0 R2 < R0 + R1 MUL R4, R3, R2 R4 < R3 * R2 SUB R6, R5, R4 R6 < R5  R4
7  
8  
10  
14 
So, total no. of clock cycles needed to execute the given 3 instructions is 8.
Question 38 
The following postfix expression with single digit operands is evaluated using a stack:
8 2 3 ^ / 2 3 * + 5 1 * 
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:
6, 1  
5, 7  
3, 2  
1, 5 
After the * is evaluated at the time elements in the stack is 1, 6.
Question 39 
The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:
d e b f g c a  
e d b g f c a  
e d b f g c a  
d e f g b c a 
Pre order: Root Left Right
Post order: Left Right Root
Inorder: d b e a f c g
Pre order: a b d e c f g
Post order: d e b f g c a
Question 40 
Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.
8, _, _, _, _, _, 10  
1, 8, 10, _, _, _, 3  
1, _, _, _, _, _,3  
1, 10, 8, _, _, _, 3 
Starting index is zero i.e.,
⇾ Given hash function is = (3x+4) mod 3
⇾ Given sequence is = 1, 3, 8, 10
where x = 1 ⟹ (3(1)+4)mod 3 = 0
1 will occupy index 0.
where x = 3 ⟹ (3(3)+4) mod 7 = 6
3 will occupy index 6.
where x = 8 ⟹ (3(8)+4) mod 7 = 0
Index ‘0’ is already occupied then put value(8) at next space (1).
where x = 10 ⟹ (3(10)+4) mod 7 = 6
Index ‘6’ is already occupied then put value(10) at next space (2).
The resultant sequence is (1, 8, 10, __ , __ , __ , 3).
Question 41 
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by
Dijkstra’s algorithm starting from S.  
Warshall’s algorithm.  
Performing a DFS starting from S.  
Performing a BFS starting from S. 
→ Time Complexity of the Warshall’s algorithm: O(n^{3}). Warshall’s algorithm basically we are using to find all pair shortest path.
→ DFS cannot be used for finding shortest paths.
→ Time Complexity for BFS : O(E+V)
Question 42 
Consider the following C function:
#includeint f(int n) { static int r = 0; if (n <= 0) return 1; if (n > 3) { r = n; return f(n2)+2; } return f(n1)+r; } int main() { printf("%d", f(5)); }
What is the value of f(5)?
5  
7  
9  
18 
f(5) = f(3) + 2
f(3) = f(2) + 5 (where r is static and value of r=5)
f(2) = f(1) + 5
f(1) = f(0) + 5
f(0) = 1
⟹ f(5) = 1+5+5+5+2 = 18
Question 43 
A complete nary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete nary tree. If L = 41, and I = 10, what is the value of n?
3  
4  
5  
6 
L = No. of leaves = 41
I = No. of Internal nodes = 10
41 = (n1) * 10 + 1
40 = (n1) * 10
n = 5
Question 44 
In the following C function, let n >= m.
int gcd(n,m) { if (n%m ==0) return m; n = n%m; return gcd(m,n); }
How many recursive calls are made by this function?
θ (log_{2} n)  
Ω (n)  
θ (log_{2}log_{2} n)
 
θ(√n) 
Then, time complexity is = O(log(a∙b) = O(log(a+b)) = O(log n)
Question 45 
What is the time complexity of the following recursive function:
int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor(sqrt(n))) + n); }
Ω (n^{2})  
θ (nlog_{2} n)
 
θ (log_{2} n)  
θ (log_{2}log_{2} n) 
Now apply Master's theorem,
a=1, b=2, k=0, p=0
a = b^{k}, so Case2 will be applied, and p>1, so
Question 46 
Consider the following C program segment where CellNode represents a node in a binary tree:
struct CellNode { struct CellNOde *leftChild; int element; struct CellNode *rightChild; }; int GetValue(struct CellNode *ptr) { int value = 0; if (ptr != NULL) { if ((ptr>leftChild == NULL) && (ptr>rightChild == NULL)) value = 1; else value = value + GetValue(ptr>leftChild) + GetValue(ptr>rightChild); } return(value); }The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:
the number of nodes in the tree
 
the number of internal nodes in the tree  
the number of leaf nodes in the tree  
the height of the tree 
So from applying algorithm to above tree we got the final value v=3 which is nothing but no. of leaf nodes.
Note that height of the tree is also 3 but it is not correct because in algorithm the part
if ((ptr → leafchild = = NULL) && (ptr → rightchild = = NULL)) value = 1;
Says that if there is only one node the value is 1 which cannot be height of the tree because the tree with one node has height '0'.
Question 47 
Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:
θ(log_{2}n)  
θ(log_{2}log_{2}n)  
θ(n)  
θ(nlog_{2}n) 
Question 48 
Which of the following is TRUE about formulae in Conjunctive Normal Form?
For any formula, there is a truth assignment for which at least half the clauses evaluate to true.  
For any formula, there is a truth assignment for which all the clauses evaluate to true.
 
There is a formula such that for each truth assignment, at most onefourth of the clauses evaluate to true.
 
None of the above. 
Formula: a ∧ b
Truth table:
Conjunctive normal form : (a ∨ b) ∧ (a ∨ ~b) ∧ (~a ∨ b)
Similarly,
For n=1TRUE=1, FALSE=1 (1/2 ARE TRUE)
For n=2TRUE=3, FALSE=1 (3/4 ARE TRUE)
For n=3TRUE=7, FALSE=1 (7/8 ARE TRUE)
(12^{n}) are TRUE.
Looking at options,
Question 49 
Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w. Which of the following is FALSE?
There is a minimum spanning tree containing e.  
If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight.
 
Every minimum spanning tree has an edge of weight w.  
e is present in every minimum spanning tree. 
Question 50 
An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?
At least 2n  c comparisons, for some constant c, are needed.  
At most 1.5n  2 comparisons are needed.  
At least nlog_{2}n comparisons are needed.
 
None of the above. 
→ Now take other two element and compare between them and we will get one minimum element which will be compared with min and we will get one maximum element which will be compared with max and accordingly we will mark them. So in total 3 comparisions are required, and we will do this with all (n1)/2 pairs.
So in total, no. of comparisions required,
= 3(n2)/2 + 2
= 3n/2  3 + 2
= 3n/2  1
= 1.5n  1
Question 51 
Consider the following C code segment:
int IsPrime(n) { int i,n; for(i=2;i<=sqrt(n);i++) if(n%i == 0) {printf(“Not Prime\n”); return 0;} return 1; }
Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE?>/p>
T(n) = O(√n) and T(n) = Ω(√n)
 
T(n) = O(√n) and T(n) = Ω(1)
 
T(n) = O(n) and T(n) = Ω(√n)  
None of the above 
Question 52 
Consider the grammar with nonterminals N = {S,C,S_{1}},terminals T = {a,b,i,t,e}, with S as the start symbol, and the following set of rules:
S > iCtSS_{1}a S_{1} > eSϵ C > b
The grammar is NOT LL(1) because:
it is left recursive  
it is right recursive  
it is ambiguous  
it is not contextfree 
This grammar has two parse tree for string “ibt ibt aea”.
Question 53 
Consider the following two statements:
P: Every regular grammar is LL(1) Q: Every regular set has a LR(1) grammar
Which of the following is TRUE?
Both P and Q are true  
P is true and Q is false  
P is false and Q is true  
Both P and Q are false 
For ex: Consider a regular grammar
S > aS  a  ϵ
this grammar is ambiguous as for string "a" two parse tree is possible.
Hence it is regular but not LL(1).
But every regular set has a language accept or as DFA , so every regular set must have atleast one grammar which is unambiguous.
Hence, every regular set has LR(1) grammar.
Question 54 
In a simplified computer the instructions are:
OP R_{j},R_{i}  Performs R_{j} OP R_{i} and stores the result in register R_{i}. OP m,R_{i}  Performs val OP R_{i} and stores the result in R_{i}. val denotes the content of memory location m. MOV m,R_{i}  Moves the content of memory location m to register R_{i}. MOV R_{i},m  Moves the content of register R_{i} to memory location m.
The computer has only to registers, and OP is either ADD or SUB. Consider the following basic block:
t_{1} = a+b t_{2} = c+d t_{3} = et_{2} t_{4} = t_{1}t_{3}
Assume that all operands are initially in memory. The final value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block?
2  
3  
5  
6 
MOV a, R_{1}
ADD b, R_{1}
MOV c, R_{2}
ADD d, R_{2}
SUB e, R_{2}
SUB R_{1}, R_{2}
MOV R_{2}, m
So, from the above total no. of MOV instructions = 3
Question 55 
An operating system uses Shortest Remaining Time first (SRT) process scheduling algorithm. Consider the arrival times and execution times for the following processes:
Process Execution time Arrival time P1 20 0 P2 25 15 P3 10 30 P4 15 45
What is the total waiting time for process P2?
5  
15  
40  
55 
Waiting time for process P2 = TAT  Execution time
= Completion time  AT  ET
= 55  15  25
= 15
Question 56 
A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed number of frames to a process. Consider the following statements:
P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate. Q: Some programs do not exhibit locality of reference.
Which one of the following is TRUE?
Both P and Q are true, and Q is the reason for P
 
Both P and Q are true, but Q is not the reason for P  
P is false, but Q is true  
Both P and Q are false 
FIFO suffers from Belady anomaly. Belady anomaly states that when number of page frames increases no. of page fault increases.
Statement Q,
Locality of reference also known as the principle of locality, is the tendency of a processor to accesses the same set of memory locations respectively over a short period of time.
And yes some programs do not exhibit locality of reference.
Hence, both P and Q are true. But Q is not the reason for P.
Question 57 
A single processor system has three resource types X, Y and Z, which are shared by three processes. There are 5 units of each resource type. Consider the following scenario, where the column alloc denotes the number of units of each resource type allocated to each process, and the column request denotes the number of units of each resource type requested by a process in order to complete execution. Which of these processes will finish LAST?
alloc request X Y Z X Y Z P0 1 2 1 1 0 3 P1 2 0 1 0 1 2 P2 2 2 1 1 2 0
P0  
P1  
P2  
None of the above, since the system is in a deadlock.

543:
System is in safe state
Order of Execution =
P2 will execute last.
Question 58 
Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes:
/* P1 */ while (true) { wants1 = true; while (wants2 == true); /* Critical Section */ wants1=false; } /* Remainder section */ /* P2 */ while (true) { wants2 = true; while (wants1==true); /* Critical Section */ wants2 = false; } /* Remainder section */
Here, wants1 and wants2 are shared variables, which are initialized to false. Which one of the following statements is TRUE about the above construct?
It does not ensure mutual exclusion.  
It does not ensure bounded waiting.
 
It requires that processes enter the critical section in strict alternation.  
It does not prevent deadlocks, but ensures mutual exclusion. 
Now, if in P1
wants1 = true ;
executed and preempted and now if in P2
wants2 = true ;
executed.
Then the deadlock situation will be created because both will fall into infinite loop.
Question 59 
Information about a collection of students is given by the relation studinfo(studId, name, sex). The relation enroll(studId, courseId) gives which student has enrolled for (or taken) that course(s). Assume that every course is taken by at least one male and at least one female student. What does the following relational algebra expression represent?
Π_{courseId}((Π_{studId}(σ_{sex="female"}(studInfo))×Π_{courseId}(enroll))enroll)Courses in which all the female students are enrolled.  
Courses in which a proper subset of female students are enrolled.  
Courses in which only male students are enrolled.
 
None of the above 
Option B: Yes, True. It selects the proper subset of female students which are enrolled because in the expression we are performing the Cartesian product.
Option C: False. It doesn’t shows (or) display the males students who are enrolled.
Question 60 
Consider the relation employee(name, sex, supervisorName) with name as the key. supervisorName gives the name of the supervisor of the employee under consideration. What does the following Tuple Relational Calculus query produce?
{e.nameemployee(e)∧} (∀x)[¬employee(x) ∨ x.supervisorName ≠ e.name ∨ x.sex = "male"]}
Names of employees with a male supervisor.  
Names of employees with no immediate male subordinates.  
Names of employees with no immediate female subordinates.  
Names of employees with a female supervisor. 
Question 61 
Consider the table employee(empId, name, department, salary) and the two queries Q_{1},Q_{2} below. Assuming that department 5 has more than one employee, and we want to find the employees who get higher salary than anyone in the department 5, which one of the statements is TRUE for any arbitrary employee table?
Q_{1} : Select e.empId From employee e Where not exists (Select * From employee s where s.department = “5” and s.salary >= e.salary) Q_{2} : Select e.empId From employee e Where e.salary > Any (Select distinct salary From employee s Where s.department = “5”)
Q_{1} is the correct query  
Q_{2} is the correct query  
Both Q_{1} and Q_{2} produce the same answer  
Neither Q_{1} nor Q_{2} is the correct query 
Query 1: Results the empId's which have higher salary than anyone in the department 5.
Query 2: Results the empId's which have higher salary than atleast one employee of department 5.
Question 62 
Which one of the following statements if FALSE?
Any relation with two attributes is in BCNF  
A relation in which every key has only one attribute is in 2NF  
A prime attribute can be transitively dependent on a key in a 3NF relation  
A prime attribute can be transitively dependent on a key in a BCNF relation 
i) It is in 3NF.
ii) For any dependency X→ Y
where X is a super key.
iii) Functional dependency has been removed.
Option D is false.
→ Because a prime attribute can’t be transitive dependent on a key in a BCNF relation.
Question 63 
The order of a leaf node in a B^{+} tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node?
63  
64  
67  
68 
Data recorder pointer size, r = 7 bytes
Value size, v = 9 bytes
Disk Block pointer, P = 6 bytes
⇒ Order of leaf be m, then
r*m+v*m+p <= 1024
7m+9m+6 <= 1024
16m <= 1024  6
m <= 63
Question 64 
Consider the following schedules involving two transactions. Which one of the following statements is TRUE?
 S_{1}: r_{1}(X); r_{1}(Y); r_{2}(X); r_{2}(Y); w_{2}(Y); w_{1}(X)
S_{2}: r_{1}(X); r_{2}(X); r_{2}(Y); w_{2}(Y); r_{1}(Y); w_{1}(X)
Both S_{1} and S_{2} are conflict serializable.  
S_{1} is conflict serializable and S_{2} is not conflict serializable.  
S_{1} is not conflict serializable and S_{2} is conflict serializable.  
Both S_{1} and S_{2} are not conflict serializable. 
In precedence graph of S_{1} since cycle is formed so not conflict serializable.
But in precedence graph of S_{2} No cycle is formed so it is conflict serializable.
Question 65 
There are n stations in a slotted LAN. Each station attempts to transmit with a probability p in each time slot. What is the probability that ONLY one station transmits in a given time slot?
np(1p)^{n1}  
(1p)^{n1}  
p(1p)^{n1}  
1(1p)^{n1} 
^{n}C_{1}P^{1}(1p)^{n1}
= nP(1P)^{n1}
Question 66 
In a token ring network the transmission speed is 10^{7} bps and the propagation speed is 200 metres/μs. The 1bit delay in this network is equivalent to:
500 metres of cable.  
200 metres of cable.  
20 metres of cable.  
50 metres of cable. 
Given T_{p} = 200 m / microsec
In, 1 microsec it covers 200m
Therefore, in 0.1 microsec it is 200 * 0.1 = 20 meters
Question 67 
The address of a class B host is to be split into subnets with a 6bit subnet number. What is the maximum number of subnets and the maximum number of hosts in each subnet?
62 subnets and 262142 hosts.  
64 subnets and 262142 hosts.
 
62 subnets and 1022 hosts.  
64 subnets and 1024 hosts. 
From HID, we took 6bits for subnetting.
Then total subnets possible = ( 2^{6} )  2 = 64
Total hosts possible for each subnet = (2^{10})  2 = 1022
Question 68 
The message 11001001 is to be transmitted using the CRC polynomial x^{3}+1 to protect it from errors. The message that should be transmitted is:
11001001000  
11001001011  
11001010  
110010010011 
= 1001
∴ Data transmitted is: 11001001011
Question 69 
The distance between two stations M and N is L kilometers. All frames are K bits long. The propagation delay per kilometer is t seconds. Let R bits/second be the channel capacity. Assuming that processing delay is negligible, the minimum number of bits for the sequence number field in a frame for maximum utilization, when the sliding window protocol is used, is:
⌈log_{2}(2LtR+2K/K)⌉  
⌈log_{2}(2LtR/K)⌉  
⌈log_{2}(2LtR+K/K)⌉  
⌈log_{2}(2LtR+K/2K)⌉ 
N = (T_{k} + 2T_{p})/T_{k}
T_{p} = l × l sec
T_{k} = K/R sec
So, N = (K/R+2Lt)/(K/R) = K+2LtR/K
Note that when asked for general sliding window protocol (not GBN nor SR) then we do not care about receiver's window size.
So, no. of bits required,
⌈log_{2} K+2LtR/K⌉
Question 70 
Match the following:
(P) SMTP (1) Application layer (Q) BGP (2) Transport layer (R) TCP (3) Data link layer (S) PPP (4) Network layer (5) Physical layer
P – 2 Q – 1 R – 3 S – 5  
P – 1 Q – 4 R – 2 S – 3  
P – 1 Q – 4 R – 2 S – 5  
P – 2 Q – 4 R – 1 S – 3 
Q) BGP is network layer protocol that manages low packets are routed across the network.
R) TCP is a transport layer protocol.
S) PPP is a data link layer protocol.
Question 71 
Consider the following program segment. Here R1, R2 and R3 are the general purpose registers.
Instruction Operation Instruction size (no. of words) MOV R1,(3000) R1 ← m[3000] 2 LOOP: MOV R2,(R3) R2 ← M[R3] 1 ADD R2,R1 R2 ← R1 + R2 1 MOV (R3),R2 M[R3] ← R2 1 INC R3 R3 ← R3 + 1 1 DEC R1 R1 ← R1  1 1 BNZ LOOP Branch on not zero 2 HALT Stop 1
Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal.
Assume that the memory is word addressable. The number of memory references for accessing the data in executing the program completely is:
10  
11  
20  
21 
R1 ← m[3000]
Now loop will run 10 times because R1 contain value 10, and in each iteration of the loop there are two memory reference,
R2 ← M[R3]
M[R3] ← R2
So, in total, the no. of memory references are,
2(10) + 1 = 21
Question 72 
Consider the following program segment. Here R1, R2 and R3 are the general purpose registers.
Instruction Operation Instruction size (no. of words) MOV R1,(3000) R1 ← m[3000] 2 LOOP: MOV R2,(R3) R2 ← M[R3] 1 ADD R2,R1 R2 ← R1 + R2 1 MOV (R3),R2 M[R3] ← R2 1 INC R3 R3 ← R3 + 1 1 DEC R1 R1 ← R1  1 1 BNZ LOOP Branch on not zero 2 HALT Stop 1
Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal.
Assume that the memory is word addressable. After the execution of this program, the content of memory location 2010 is:
100  
101  
102  
110 
Now since the value will change at memory locations from 2000 to 2009 and will not affect the memory locations 2010.
Hence, the value at memory location 2010 it will be old value, i.e., 100.
Question 73 
Consider the following program segment. Here R1, R2 and R3 are the general purpose registers.
Instruction Operation Instruction size (no. of words) MOV R1,(3000) R1 ← m[3000] 2 LOOP: MOV R2,(R3) R2 ← M[R3] 1 ADD R2,R1 R2 ← R1 + R2 1 MOV (R3),R2 M[R3] ← R2 1 INC R3 R3 ← R3 + 1 1 DEC R1 R1 ← R1  1 1 BNZ LOOP Branch on not zero 2 HALT Stop 1
Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal.
Assume that the memory is byte addressable and the word size is 32 bits. If an interrupt occurs during the execution of the instruction “INC R3”, what return address will be pushed on to the stack?
1005  
1020  
1024  
1040 
→ Starts at memory location 1000.
Interrupt occurs during the execution of information “INC R3”.
Then the value of address i.e., 1024 is pushed into the stack.
Question 74 
Consider the following Finite State Automaton.
The language accepted by this automaton is given by the regular expression
b*ab*ab*ab*  
(a+b)*  
b*a(a+b)*  
b*ab*ab* 
Clearly we can see that the regular expression for DFA is “ b*a (a+b)* ”.
Question 75 
Consider the following Finite State Automaton.
The minimum state automaton equivalent to the above FSA has the following number of states
1  
2  
3  
4 
Question 76 
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively.
Which of the following is the Huffman code for the letter a, b, c, d, e, f?
0, 10, 110, 1110, 11110, 11111  
11, 10, 011, 010, 001, 000  
11, 10, 01, 001, 0001, 0000  
110, 100, 010, 000, 001, 111 
→ 0, 10, 110, 1110, 11110, 11111
Question 77 
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively.
What is the average length of Huffman codes?
3  
2.1875  
2.25  
1.9375 
Question 78 
Consider the CFG with {S,A,B} as the nonterminal alphabet, {a,b} as the terminal alphabet, S as the start symbol and the following set of production rules:
S → aB S → bA B → b A → a B → bS A → aS B → aBB A → bAA
Which of the following strings is generated by the grammar?
aaaabb  
aabbbb  
aabbab  
abbbba 
S > aB [Using S > aB]
> aaBB [Using B > aBB]
> aabB [Using B > b]
> aabbS [Using B > bS]
> aabbaB [Using S > aB]
> aabbab [Using B > b]
Question 79 
Consider the CFG with {S,A,B} as the nonterminal alphabet, {a,b} as the terminal alphabet, S as the start symbol and the following set of production rules:
S → aB S → bA B → b A → a B → bS A → aS B → aBB A → bAA
For the correct answer strings to Q.78, how many derivation trees are there?
1  
2  
3  
4 
Question 80 
Consider a machine with a byte addressable main memory of 2^{16} bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A 50 × 50 twodimensional array of bytes is stored in the main memory starting from memory location 1100H. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses.
How many data cache misses will occur in total?
40  
50  
56  
59 
= log_{2} 2^{16} = 16 bits
Cache line size is 64 bytes means offset bit required is
log_{2} 2^{6} = 6 bits
No. of lines in cache is 32, means lines bits required is
log_{2} 2^{5} = 5 bits.
So, tag bits = 16  6  5 = 5 bits
No. of elements in array is
50 × 50 = 2500
and each element is of 1 byte.
So, total size of array is 2500 bytes.
So, total no. of lines it will require to get into the cache,
⌈2500/64⌉ = 40
Now, given starting address of array,
Now we need 40 cache lines to hold all array elements, but we have only 32 cache lines.
Now lets divide 2500 array elements into 40 array lines, each of which will contain 64 of its elements.
Now,
So, if complete array is accessed twice, total no. of cache misses is,
Question 81 
Consider a machine with a byte addressable main memory of 2^{16} bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A 50 × 50 twodimensional array of bytes is stored in the main memory starting from memory location 1100H. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses.
Which of the following lines of the data cache will be replaced by new blocks in accessing the array for the second time?
line 4 to line 11  
line 4 to line 12  
line 0 to line 7  
line 0 to line 8 
Question 82 
A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): 1, 2, 1, 3, 7, 4, 5, 6, 3, 1
If optimal page replacement policy is used, how many page faults occur for the above reference string?
7  
8  
9  
10 
1, 2, 1, 3, 7, 4, 5, 6, 3, 1
No. of frames = 3
Using Optimal page replacement,
Total 7 page faults.
Question 83 
A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): 1, 2, 1, 3, 7, 4, 5, 6, 3, 1
Least Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement. For the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy?
0  
1  
2  
3 
1, 2, 1, 3, 7, 4, 5, 6, 3, 1 br> No. of frames = 3 (Using LRU)
No. of page faults with LRU = 9
⟶ In the LRU we replace the page with least recently used page.
Using optimal page replacement
⟶ 1,2,1,3,7,4,5,6,3,1
No. of page faults with optimal = 7
Difference between optimal and LRU = 9  7 = 2
In optimal we replace the page which will occur last in the future.
Question 84 
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1).
How many distinct paths are there for the robot to reach the point (10,10) starting from the initial position (0,0)?
2^{20}  
2^{10}  
None of the above 
So now we have 10 u's and 10 r's, i.e.,
uuuuuuuuuurrrrrrrrrr
So, finally the no. of arrangements of above sequences is,
Question 85 
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1).
Suppose that the robot is not allowed to traverse the line segment from (4,4) to (5,4). With this constraint, how many distinct paths are there for the robot to reach (10,10) starting from (0,0)?
2^{9}  
2^{19}  
So, no. of paths possible if line segment from (4,4) to (5,4) is taken is,
= paths possible from (0,0) to (4,4) * paths possible from (5,4) to (10,10)
= {uuuurrrr} * {uuuuuurrrrr}
Hence, the final answer is