GATE 2008IT
Question 1 
A set of Boolean connectives is functionally complete if all Boolean functions can be synthesized using those. Which of the following sets of connectives is NOT functionally complete?
EXNOR  
implication, negation  
OR, negation  
NAND 
→ NOR and NAND are the functionally complete logic gates, OR, AND, NOT only logic gate can be implemented by using them.
→ And (Implication, Negation) is also functionally complete.
Question 2 
A sample space has two events A and B such that probabilities P(A ∩ B) = 1/2, P(A') = 1/3, P(B') = 1/3. What is P(A ∪ B)?
11/12  
10/12  
9/12  
8/12 
P(A') = 1/3; P(A) = 2/3
P(B') = 1/3; P(B) = 2/3
P(A ∪ B) = P(A) +P(B)  P(A ∩ B)
= 2/3 + 2/3  1/2
= 4+43/ 6
= 5/6
= 10/12
Question 3 
What is the chromatic number of the following graph?
2  
3  
4  
5 
→ Chromatic number of a graph is the smallest number of colours needed to colour the vertices so that no two adjacent vertices share the same colour.
Question 4 
What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes?
5  
4  
3  
2 
(2, 5, 8) is the maximal independent set for a chain of 9 nodes. If we add any start node to the set then it will not be MIS.
Independent set:
A set of vertices is called independent set such that no two vertices in the set are adjacent.
Question 5 
Which of the following regular expressions describes the language over {0, 1} consisting of strings that contain exactly two 1’s?
(0 + 1) * 11(0 + 1) *  
0 * 110 *  
0 * 10 * 10 *  
(0 + 1) * 1(0 + 1) * 1 (0 + 1) *

→ 1110 this consists of 3 ones but accepted by given expression. So this is false.
Option B: 0* 110*
→ 0101 this string consists of two is but not accepted by given expression. This is false.
Option C: 0* 10* 10*
→ This is true.
Option D: (0+1)* 1(0+1)* 1(0+1)*
→ 011010  This can have three is but accepted by given expression. So this is also false.
Question 6 
Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?
m ≤ 2^{n}  
n ≤ m  
M has one accept state  
m = 2^{n} 
A state in a DFA is a proper subset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2^{n}
→ m ≤ 2^{n}
Question 7 
The following bit pattern represents a floating point number in IEEE 754 single precision format
110000011101000000000000000000000The value of the number in decimal form is
10  
13  
26  
None of these 
Exponent bits  10000011
Exponent can be added with 127 bias in IEEE single precision format then outval exponent
= 10000011  127
= 131  127
= 4
→ In IEEE format, an implied 1 is before mantissa, and hence the outval number is
→ 1.101 × 2^{4} = (11010)_{2} = 26
Question 8 
Consider the following Boolean function of four variables
f(A,B,C,D) = Σ(2, 3, 6, 7, 8, 9, 10, 11, 12, 13)The function is
independent of one variable  
independent of two variables  
independent of three variable  
dependent on all the variables 
Independent of one variable '0'.
Question 9 
What Boolean function does the circuit below realize ?
xz+x’z’  
xz’+x’z  
x’y’+yz  
xy+y’z’ 
= (x’z’ + xz)’
= x’z + xz’
Question 10 
Arrange the following functions in increasing asymptotic order:
A. n^{1/3} B. e^{n} C. n^{7/4} D. n log^{9}n E. 1.0000001^{n}
A, D, C, E, B  
D, A, C, E, B  
A, C, D, E, B  
A, C, D, B, E 
n^{1/3} < n log^{9} < n^{7/4} < 1.0000001^{n} < e^{n}
Question 11 
For problems X and Y, Y is NPcomplete and X reduces to Y in polynomial time. Which of the following is TRUE?
If X can be solved in polynomial time, then so can Y  
X is NPcomplete  
X is NPhard  
X is in NP, but not necessarily NPcomplete 
Question 12 
Which of the following is TRUE?
The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n)  
The cost of searching an AVL tree is θ (log n) but that of a complete binary tree is θ (n log n)  
The cost of searching a binary search tree is O (log n) but that of an AVL tree is θ(n)  
The cost of searching an AVL tree is θ (n log n) but that of a binary search tree is O(n) 
Question 13 
Match the programming paradigms and languages given in the following table.
Ic, IId, IIIb, IVa  
Ia, IId, IIIc, IVb  
Id, IIc, IIIb, IVa  
Ic, IId, IIIa, IVb 
Question 14 
Consider the execution of the following commands in a shell on a linux operating system.
system bash$cat alpha Mathematics bash$in alpha beta bash$ rm alpha bash$cat >> beta << SAME Information Technology SANE bash$ cat betaThe output of the last command will be:
Mathematics Information Technology SAME.  
Mathematics Information Technology.  
Information Technology.  
Information Technology SAME. 
Question 15 
A processor that has carry, overflow and sign flag bits as part of its program status word (PSW) performs addition of the following two 2's complement numbers 01001101 and 11101001. After the execution of this addition operation, the status of the carry, overflow and sign flags, respectively will be:
1, 1, 0  
1, 0, 0  
0, 1, 0  
1, 0, 1 
Carry flag = 1
Overflow flag = 0
Sign bit = 0 (MSB bit is 0)
Overflow flag:
In computer processors, the overflow flag is usually a single bit in a system status register used to indicate when an arithmetic overflow has occurred in an operation.
Question 16 
A paging scheme uses a Translation Lookaside Buffer (TLB). A TLBaccess takes 10 ns and a main memory access takes 50 ns. What is the effective access time(in ns) if the TLB hit ratio is 90% and there is no pagefault?
54  
60  
65  
75 
= 10 + 0.1 × 50 + 50
= 10 + 5 + 50
= 65
Question 17 
Find if the following statements in the context of software testing are TRUE or FALSE.
(S1) Statement coverage cannot guarantee execution of loops in a program under test.
(S2) Use of independent path testing criterion guarantees execution of each loop in a program under test more than once.
True, True  
True, False  
False, True  
False, False 
Question 18 
How many bytes of data can be sent in 15 seconds over a serial link with baud rate of 9600 in asynchronous mode with odd parity and two stop bits in the frame?
10,000 bytes  
12,000 bytes  
15,000 bytes  
27,000 bytes 
1 bit for start bit, 8 bits for data, 1 bit for parity, 2 bits for stop bits i.e.,
Question 19 
Which of the following is TRUE only of XML but NOT HTML?
It is derived from SGML  
It describes content and layout  
It allows user defined tags  
It is restricted only to be used with web browsers 
Question 20 
Provider the best matching between the entries in the two columns given in the table below:
Ia, IId, IIIc, IVb  
Ib, IId, IIIc, IVa  
Ia, IIc, IIId, IVb  
Ib, IIc, IIId, IVa 
(ii) Kazaa and DC++ are P2P applications.
(iii) P2P slip is a processor of PPP.
(iv) DNS allows caching of entries at local server.
Question 21 
Which of the following first order formula is logically valid? Here α(x) is a first order formula with x as a free variable, and β is a first order formula with no free variable.
[β→(∃x,α(x))]→[∀x,β→α(x)]  
[∃x,β→α(x)]→[β→(∀x,α(x))]  
[(∃x,α(x))→β]→[∀x,α(x)→β]  
[(∀x,α(x))→β]→[∀x,α(x)→β] 
L.H.S. : If there is an x such that α(x) is true, then β is true.
R.H.S. : For all x, if α(x) true, then β is true.
Here, the given LHS and RHS are to be same as β is a formula which can be independent of x (if β is true for one x, it is true for every x, and viceversa).
Here, LHS = RHS
So, Option C is valid.
Question 22 
Which of the following is the negation of [∀x, α →(∃y, β →(∀ u, ∃v, y))]
[∃x, α → (∀y, β → (∃u, ∀v, y))]  
[∃x, α → (∀y, β → (∃u, ∀ v, ¬y))]  
[∀x, ¬α → (∃y, ¬β → (∀u, ∃v, ¬y))]  
[∃x, α ʌ (∀y, β ʌ (∃u, ∀v, ¬y))] 
⇔ [∃x, [α × ~(∃y, β → (∀u, ∃v, y))]
⇔ [∃x, [α × ∀y, ~(β → (∀u, ∃v, y)]
⇔ [∃x, [α × ∀y, ~(β × ~(∀u, ∃v, y)]
⇔ [∃x, [α × ∀y(β × (∃u, ∀v, y)]
Question 23 
What is the probability that in a randomly chosen group of r people at least three people have the same birthday?
Question 24 
The exponent of 11 in the prime factorization of 300! is
27  
28  
29  
30 
Question 25 
In how many ways can b blue balls and r red balls be distributed in n distinct boxes?
C(n+b1, b) = (n+b1)!/ (n1)!b!
No. of red distributed to n boxes is
(n+r1, r) = (n+r1)!/ (n1)!r!
Total no. of ways = (n+b1)!/(n1)!b! * (n+r1)!/(n1)!r!
= (n+b1)!(n+r1)!/(n1)!b!(n1)!r!
Question 26 
Consider the field C of complex numbers with addition and multiplication. Which of the following form(s) a subfield of C with addition and multiplication?
(S1) the set of real numbers (S2) {(a+ib)  a and b are rational numbers} (S3) {a+ib  (a^{2} + b^{2}) ≤ 1} (S4) {ia  a is real}
only S1  
S1 and S3  
S2 and S3  
S1 and S2 
As real + real = real and real * real = real
S2: It is closed as rational + rational = rational and rational * rational = rational
S3: It is not closed.
⇒ (0.3+0.4i) + (0.7+0.6i) = 1+i
Both (0.3+0.4i) & (0.7+0.6i) are complex numbers follows S3 but addition of them doesn't follows.
⇒ 1+i, (a^{2}+b^{2}) <= 1
⇒ 1+1 is not less than or equal to 1.
S4: {ia  a ia real}
In this there is no multiplicative identity exists (i.e., 1).
Question 27 
G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be
Regular  
Complete  
Hamiltonian  
Euler 
→ In Euler graph all degrees must be even for all nodes. And number of odd degree vertices should be even.
→ So, degree of this new node will be even and as a new edge is formed between this new node and all other nodes of odd degree hence here is not a single node exists with degree odd so this is Euler graph.
Question 28 
Consider the following Hasse diagrams.
(i) and (iv) only  
(ii) and (iii) only  
(iii) only  
(i), (ii) and (iv) only 
(ii) and (iii), having more than one lub or glb for some pairs due to which they are not lattice.
Question 29 
If M is a square matrix with a zero determinant, which of the following assertion(s) is(are) correct?

 (S1) Each row of M can be represented as a linear combination of the other rows

 (S2) Each column of M can be represented as a linear combination of the other columns

 (S3) MX = 0 has a nontrivial solution
 (S4) M has an inverse
S3 and S2  
S1 and S4  
S1 and S3  
S1, S2 and S3 
If determinant of some square matrix is zero then matrix do not have any inverse.
Hence, from the above definitions we can conclude that S1, S2, S3 are true and S4 is false.
Question 30 
Consider the function f(x) = x^{2}  2x  1. Suppose an execution of the NewtonRaphson method to find a zero of f(x) starts with an approximation x_{0} = 2 0f x. What is the value of x_{2}, 'the approximation of x' that the algorithm produces after two iterations, rounded to three decimal places?
2.417  
2.419  
2.423  
2.425 
Question 31 
If f(x) is defined as follows, what is the minimum value of f(x) for x∊(0,2] ?
2  
2(1/12)  
2(1/6)  
2(1/2) 
f(x) = 25/8x = 25/8(3/2) = 25/12 = 2(1/12)
Question 32 
If the final states and nonfinal states in the DFA below are interchanged, then which of the following languages over the alphabet {a,b} will be accepted by the new DFA?
Set of all strings that do not end with ab  
Set of all strings that begin with either an a or a b  
Set of all strings that do not contain the substring ab  
The set described by the regular expression b*aa*(ba)*b* 
Option B: abab is not accepted by given RE.
Option C: aba is accepted by given RE.
Option D: ab is not accepted by RE and it belongs to b*aa*(ba)*b*.
Question 33 
Consider the following languages.
L_{1} = {a^{i} b^{j} c^{k}  i = j, k ≥ 1} L_{1} = {a^{i} b^{j}  j = 2i, i ≥ 0}Which of the following is true?
L_{1} is not a CFL but L_{2} is  
L_{1} ∩ L_{2} = ∅ and L_{1} is nonregular  
L_{1} ∪ L_{2} is not a CFL but L_{2} is  
There is a 4state PDA that accepts L_{1}, but there is no DPDA that accepts L_{2} 
→ L_{1} ∩ L_{2} = ∅, True and also L1 is nonregular. Option B is true.
→ L_{1} ∪ L_{2} is not a CFL but L_{2} is CFL is closed under union. So option C is false.
→ Both L_{1} and L_{2} accepted by DPDA.
Question 34 
Consider a CFG with the following productions.
S → AA  B A → 0A  A0  1 B → 0B00  1S is the start symbol, A and B are nonterminals and 0 and 1 are the terminals. The language generated by this grammar is
{0^{n} 10^{2n}  n ≥ 1}  
{0^{i} 10^{j} 10^{k}  i, j, k ≥ 0} ∪ {0^{n} 10^{2n}  n ≥ l}  
{0^{i} 10^{j}  i, j ≥ 0} ∪ {0^{n} 10^{2n}  n ≥ l}  
The set of all strings over {0, 1} containing at least two 0’s  
None of the above 
A → 0A  A0  1
B → 0B00  1
In this B → 0B00  1 which generates {0n 102n  n ≥0}
S → AA  B
A → 0A  A0  1
Which generates 0A0A → 00A0A → 00101.
Which is suitable for B and D option. D is not correct because 00 is not generated by the given grammar. So only option B is left. Nonterminal B i s generating the second part of B choice and AA is generating the first part.
{0^{i} 10^{j} 10^{k}  i, j, k ≥ 0} ∪ {0^{n} 10^{2n}  n ≥ 0}
Question 35 
Which of the following languages is (are) nonregular? L_{1} = {0^{m}1^{n}  0 ≤ m ≤ n ≤ 10000} L_{2} = {w  w reads the same forward and backward} L_{3} = {w ∊ {0, 1} *  w contains an even number of 0's and an even number of 1's}
L_{2} and L_{3} only  
L_{1} and L_{2} only  
L_{3} only  
L_{2} only 
L_{1} is limited to fixed range and L_{3} contains even number of 0's which is regular. No need to use more memory to implement L_{3}.
Question 36 
Consider the following two finite automata. M_{1} accepts L_{1} and M_{2} accepts L_{2}.
Which one of the following is TRUE?L_{1} = L_{2}  
L_{1} ⊂ L_{2}  
L_{1} ∩ L_{2}‘ = ∅  
L_{1} ∪ L_{2} ≠ L_{1}  
A and C 
L_{2} = (0=1)* 11(0+1)*
Both L_{1} and L_{2} are equal.
Option A is correct.
→ L_{1} ∩ L_{2}‘ = L_{1} ∩ L_{1}‘ = ∅ (option C also correct)
Question 37 
Consider the following state diagram and its realization by a JK flip flop The combinational circuit generates J and K in terms of x, y and Q. The Boolean expressions for J and K are:
(x⊕y)’ and x’⊕y’  
(x⊕y)’ and x⊕y  
x⊕y and (x⊕y)’  
x⊕y and x⊕y 
Excitation table of JK:
Question 38 
Assume that EA = (X)+ is the effective address equal to the contents of location X, with X incremented by one word length after the effective address is calculated; EA = −(X) is the effective address equal to the contents of location X, with X decremented by one word length before the effective address is calculated; EA = (X)− is the effective address equal to the contents of location X, with X decremented by one word length after the effective address is calculated. The format of the instruction is (opcode, source, destination), which means (destination ← source op destination). Using X as a stack pointer, which of the following instructions can pop the top two elements from the stack, perform the addition operation and push the result back to the stack.
ADD (X)−, (X)  
ADD (X), (X)−  
ADD −(X), (X)+  
ADD −(X), (X)+ 
Lets say SP is 1000 initially then after it calculates the EA of source (which is 1000 as it decrements after the EA). The destination becomes 998 and this is where we want to store the result as stack is decrementing.
In case of C and D it becomes,
998 ← 998 + 998
Question 39 
Consider a CPU where all the instructions require 7 clock cycles to complete execution. There are 140 instructions in the instruction set. It is found that 125 control signals are needed to be generated by the control unit. While designing the horizontal microprogrammed control unit, single address field format is used for branch control logic. What is the minimum size of the control word and control address register?
125, 7  
125, 10  
135, 7  
135, 10 
i.e., 140 instruction takes = 140 * 7 =980 cycles.
So, size of control address register = ⌈log_{2} 980⌉
= 10 bit
Since horizontal microprogramming is used, so 125 control signals will require 125 bits.
Hence, size of control word = 125 + 10 = 135 bits
Question 40 
A non pipelined single cycle processor operating at 100 MHz is converted into a synchronous pipelined processor with five stages requiring 2.5 nsec, 1.5 nsec, 2 nsec, 1.5 nsec and 2.5 nsec, respectively. The delay of the latches is 0.5 nsec. The speedup of the pipeline processor for a large number of instructions is
4.5  
4.0  
3.33  
3.0 
For pipelined system = Max(stage delay) + Max(latch delay) = 2.5 + 0.5 = 3.0
Speedup = Time in nonpipelined system/Time in pipelined system = 10/3 = 3.33
Question 41 
Assume that EA = (X)+ is the effective address equal to the contents of location X, with X incremented by one word length after the effective address is calculated; EA = −(X) is the effective address equal to the contents of location X, with X decremented by one word length before the effective address is calculated; EA = (X)− is the effective address equal to the contents of location X, with X decremented by one word length after the effective address is calculated. The format of the instruction is (opcode, source, destination), which means (destination ← source op destination). Using X as a stack pointer, which of the following instructions can pop the top two elements from the stack, perform the addition operation and push the result back to the stack.
6 and 1, 2, 3, 4  
7 and 1, 2, 4, 5  
8 and 1, 2, 4, 5  
9 and 1, 2, 3, 5 
(Each page contains 16 bytes, so say for page0, it contains the virtual address 015)
0: page fault1, pages in memory0
4: page fault1, pages in memory0
8: page fault1, pages in memory0
20: page faults2, pages in memory0,1
24: page faults2, pages in memory0,1
36: page faults3, pages in memory0,1,2
44: page faults3, pages in memory0,1,2
12: page faults3, pages in memory1,2,0
68: page faults4, pages in memory1,2,0,4
72: page faults4, pages in memory1,2,0,4
80: page faults5, pages in memory2,0,4,5
84: page faults5, pages in memory2,0,4,5
28: page faults6, pages in memory0,4,5,1
32: page faults7, pages in memory4,5,1,2
88: page faults7, pages in memory4,1,2,5
92: page faults7, pages in memory4,1,2,5
Question 42 
The two numbers given below are multiplied using the Booth's algorithm.
Multiplicand : 0101 1010 1110 1110 Multiplier: 0111 0111 1011 1101How many additions/Subtractions are required for the multiplication of the above two numbers?
6  
8  
10  
12 
Now we have some values defined for pair of bits in Booth’s Algorithm,
00 → 0
11 → 0
01 → 1
10 → 1
Now after adding 0 to the LSB of the multiplier, start traversing from left to right and accordingly put the values defined above.
Hence, total 8 additions / subtractions required.
Question 43 
If we use Radix Sort to sort n integers in the range [n^{k/2}, n^{k}], for some k>0 which is independent of n, the time taken would be?
Θ(n)  
Θ(kn)  
Θ(nlogn)  
Θ(n^{2}) 
where n = keys, w = word size
w = log_{2} (n^{k}) = k × log_{2} (n)
Complexity Θ(wn) = Θ(k × log_{2}(n) × n) = Θ(n log n) = Θ(n log n)
Question 44 
When n = 2^{2k} for some k ≥ 0, the recurrence relation
T(n) = √(2)T(n/2) + √n, T(1) = 1evaluates to :
√n (log n + 1)  
√n log n  
√n log √n  
n log √n 
Question 45 
For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Spanning Tree?
(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)  
(c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)  
(d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i)  
(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)

(A) (d, f) is chosen but neither 'd' nor 'f' vertices are part of previous MST (MST made till previous step).
(B) (g, h) is chosen but neither g or h vertices are part of MST made till previous step.
(C) Correct.
(D) (f, c) is chosen, but at that point (f, d) had less weight. So, (f , d) should have been chosen.
Question 46 
The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which.
MBCAFHPYK KAMCBYPFH MABCKYFPHPick the true statement from the following.
I and II are preorder and inorder sequences, respectively  
I and III are preorder and postorder sequences, respectively  
II is the inorder sequence, but nothing more can be said about the other two sequences  
II and III are the preorder and inorder sequences, respectively

So, out of the given sequence only I & II are having such kind of order, i.e., K at the beginning and at the last.
Therefore, II is the preorder and I is postorder and the sequence III will definitely be inorder.
Question 47 
Consider the following sequence of nodes for the undirected graph given below.
a b e f d g c a b e f c g d a d g e b c f a d b c g e fA Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first visited. Which all of the above is (are) possible output(s)?
I and III only  
II and III only  
II, III and IV only  
I, II and III only 
IV) After visiting 'c', 'e' or 'f' should be visited next. So, the traversal is incorrect.
Question 48 
Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = k mod 11 be the hash function used. A sequence of records with keys
43 36 92 87 11 4 71 13 14is inserted into an initially empty hash table, the bins of which are indexed from zero to ten. What is the index of the bin into which the last record is inserted?
2  
4  
6  
7 
Hence, correct option is (D).
Question 49 
What is the output printed by the following C code?
# include int main () { char a [6] = "world"; int i, j; for (i = 0, j = 5; i < j; a [i++] = a [j]); printf ("%s\n", a); }
dlrow  
Null String  
dlrld  
worow 
Question 50 
Consider the C program below. What does it print?
# include # define swapl (a, b) tmp = a; a = b; b = tmp void swap2 ( int a, int b) { int tmp; tmp = a; a = b; b = tmp; } void swap3 (int*a, int*b) { int tmp; tmp = *a; *a = *b; *b = tmp; } int main () { int num1 = 5, num2 = 4, tmp; if (num1 < num2) {swap1 (num1, num2);} if (num1 < num2) {swap2 (num1 + 1, num2);} if (num1 >= num2) {swap3 (&num1, &num2);} printf ("%d, %d", num1, num2); }
5, 5  
5, 4  
4, 5  
4, 4 
{Swap3 (&num1, &num2) ; }"
Statement is true, so call by reference will be performed and the value of num1 and num2 will get exchanged.
Question 51 
Consider the C program given below. What does it print?
#include int main () { int i, j; int a [8] = {1, 2, 3, 4, 5, 6, 7, 8}; for(i = 0; i < 3; i++) { a[i] = a[i] + 1; i++; } i; for (j = 7; j > 4; j) { int i = j/2; a[i] = a[i]  1; } printf ("%d, %d", i, a[i]); }
2, 3  
2, 4  
3, 2  
3, 3 
First for loop will run for i = 0, 2 and 4 as i is incremented twice and resultant array will be 'a' = 2, 2, 4, 4, 5, 6, 7, 8. Loop will terminate at i = 4.
After that value of 'i' will become '3' as there is a decremented operation after for loop.
Next for loop is running for j = 7, 6, 5 and corresponding 'i' values which is a local variable inside for loop will be
3(7/2), 3(6/2), 2(5/2)
Array after this for loop will be
a = 2, 2, 3, 2, 5, 6, 2, 8.
After the loop, current 'i' value is 3 and elements at a[3] = 2.
Question 52 
C program is given below:
# include int main () { int i, j; char a [2] [3] = {{'a', 'b', 'c'}, {'d', 'e', 'f'}}; char b [3] [2]; char *p = *b; for (i = 0; i < 2; i++) { for (j = 0; j < 3; j++) { *(p + 2*j + i) = a [i] [j]; } } }What should be the contents of the array b at the end of the program?
ab cd ef  
ad be cf  
ac eb df  
ae dc bf 
*(p+2) = a[0][1] = b
*(p+4) = a[0][2] = c
*(p+1) = a[1][0] = d
*(p+3) = a[1][1] = e
*(p+5) = a[1][2] = f
Question 53 
The following is a code with two threads, producer and consumer, that can run in parallel. Further, S and Q are binary semaphores equipped with the standard P and V operations.
semaphore S = 1, Q = 0; integer x; producer: consumer: while(true) do while(true) do P(S); P(Q); x = produce (); consume (x); V(Q); V(S); done doneWhich of the following is TRUE about the program above?
The process can deadlock  
One of the threads can starve  
Some of the items produced by the producer may be lost  
Values generated and stored in ‘x’ by the producer will always be consumed before the producer can generate a new value 
(B) No starvation happen because there is alteration between Producer and Consumer.
(C) No items is lost.
Question 54 
An operating system implements a policy that requires a process to release all resources before making a request for another resource. Select the TRUE statement from the following:
Both starvation and deadlock can occur  
Starvation can occur but deadlock cannot occur  
Starvation cannot occur but deadlock can occur  
Neither starvation nor deadlock can occur 
Now, maybe the process has not used the resources it released yet. This may happen again when the process requests another resource.
So, the process starved for proper utilization of resources.
Deadlock will not occur as it is one of the deadlock prevention scheme.
Question 55 
If the timeslice used in the roundrobin scheduling policy is more than the maximum time required to execute any process, then the policy will
degenerate to shortest job first  
degenerate to priority scheduling  
degenerate to first come first serve  
none of the above 
Question 56 
Match the following flag bits used in the context of virtual memory management on the left side with the different purposes on the right side of the table below.
Id, IIa, IIIb, IVc  
Ib, IIc, IIIa, IVd  
Ic, IId, IIIa, IVb  
Ib, IIc, IIId, IVa 
The bit indicates that its associated block of memory has been modified and has not been saved to storage yet. Dirty bits are used by the CPU cache and in the page replacement algorithms of an operating system.
R/W bit:
If the bit is set, the page is read/ write. Otherwise when it is not set, the page is read only.
Reference bit:
Reference bit is used in a version of FIFO called second chance policy, in order to avoid replacement of heavily used page.
Valid bit:
Valid bit is not used for page replacement. It is not used in any page replacement policy. It tells the page in the memory is valid or not. If it is valid it is directly used and if it is not then a fresh page is loaded. So, basically it is page initialization, because we are not replacing, it is initializing, we not knocking out somebody, we are filling empty space. So initialization and so option (D).
Question 57 
Which of the following are NOT considered when computing function points for a software project?
 (O1) External inputs and outputs
(O2) Programming language to be used for the implementation
(O3) User interactions
(O4) External interfaces
(O5) Number of programmers in the software project
(O6) Files used by the system
02, 03  
01, 05  
04, 06  
02, 05 
Question 58 
A software project plan has identified ten tasks with each having dependencies as given in the following table:
Task Depends On T1  T2 T1 T3 T1 T4 T1 T5 T2 T6 T3 T7 T3, T4 T8 T4 T9 T5, T7, T8 T10 T6, T9
Answer the following questions:
(Q1) What is the maximum number of tasks that can be done concurrently?
(Q2) What is the minimum time required to complete the project, assuming that each task requires one time unit and there is no restriction on the number of tasks that can be done in parallel?
5, 5  
4, 5  
5, 4  
4, 4 
Question 59 
A software engineer is required to implement two sets of algorithms for a single set of matrix operations in an object oriented programming language; the two sets of algorithms are to provide precisions of 10^{3} and 10^{6}, respectively. She decides to implement two classes, Low Precision Matrix and High Precision Matrix, providing precisions 10^{3} and 10^{6} respectively. Which one of the following is the best alternative for the implementation?
 (S1) The two classes should be kept independent.
(S2) Low Precision Matrix should be derived from High Precision Matrix.
(S3) High Precision Matrix should be derived from Low Precision Matrix.
(S4) One class should be derived from the other; the hierarchy is immaterial.
S1  
S2  
S3  
S4 
Question 60 
Which of the following requirement specifications can be validated?
 (S1) If the system fails during any operation, there should not be any loss of data
(S2) The system must provide reasonable performance even under maximum load conditions
(S3) The software executable must be deployable under MS Windows 95, 2000 and XP
(S4) User interface windows must fit on a standard monitor's screen
S4 and S3  
S4 and S2  
S3 and S1  
S2 and S1 
Question 61 
Let R (A, B, C, D) be a relational schema with the following functional dependencies: A → B, B → C, C → D and D → B.
The decomposition of R into (A, B), (B, C), (B, D)
gives a lossless join, and is dependency preserving  
gives a lossless join, but is not dependency preserving  
does not give a lossless join, but is dependency preserving  
does not give a lossless join and is not dependency preserving

(A, B, C) (B, D)  common attributes is B and B→D is a FD (via B→C, C→D), and hence, B is a key for (B, D). So, decomposition of (A, B, C, D) into (A, B, C) (B, D) is lossless.
Thus the given decomposition is lossless.
The given decomposition is also dependency preserving as the dependencies A→B is present in (A, B), B→C is present in (B, C), D→B is present in (B, D) and C→D is indirectly present via C→B in (B, C) and B→D in (B, D).
Question 62 
Let R (A, B, C, D, E, P, G) be a relational schema in which the following functional dependencies are known to hold:
AB → CD, DE → P, C → E, P → C and B → G.The relational schema R is
in BCNF  
in 3NF, but not in BCNF  
in 2NF, but not in 3NF  
not in 2NF 
Since there is a partial dependency B→G.
So the relational schema R is Not in 2NF.
Question 63 
Consider the following three schedules of transactions T1, T2 and T3. [Notation: In the following NYO represents the action Y (R for read, W for write) performed by transaction N on object O.]
(S1) 2RA 2WA 3RC 2WB 3WA 3WC 1RA 1RB 1WA 1WB (S2) 3RC 2RA 2WA 2WB 3WA 1RA 1RB 1WA 1WB 3WC (S3) 2RA 3RC 3WA 2WA 2WB 3WC 1RA 1RB 1WA 1WBWhich of the following statements is TRUE?
S1, S2 and S3 are all conflict equivalent to each other  
No two of S1, S2 and S3 are conflict equivalent to each other  
S2 is conflict equivalent to S3, but not to S1  
S1 is conflict equivalent to S2, but not to S3 
For S1:
For S2:
For S3:
Hence, S1 is conflict equivalent to S2, but not to S3.
Question 64 
A 1Mbps satellite link connects two ground stations. The altitude of the satellite is 36,504 km and speed of the signal is 3 × 10^{8} m/s. What should be the packet size for a channel utilization of 25% for a satellite link using goback127 sliding window protocol? Assume that the acknowledgment packets are negligible in size and that there are no errors during communication.
120 bytes  
60 bytes  
240 bytes  
90 bytes 
RTT = 4×Time to reach satellite (S1→S, S→S2, S2→S, S→S1)
∴ RTT = 0.48
Efficiency = N×T_{t}/T_{t}+2T_{p}
= N×T_{t}/T_{t}+RTT
0.25 = 127×T_{t}/T_{t}+0.48
0.25T_{t} + 0.25 × 0.48 = 127T_{t}
0.25 × 0.48 = 126.5T_{t}
0.25 × 0.48 × 10^{6}/126.5 = L
L = 952 bit ≈ 120 byte
Question 65 
The minimum frame size required for a CSMA/CD based computer network running at 1 Gbps on a 200 m cable with a link speed of 2 × 10^{8 }m/s is
125 bytes  
250 bytes  
500 bytes  
None of these 
So,
T_{t} ≥ 2 × T_{p}
L/B ≥ 2 × T_{p}
L ≥ 2 × T_{p} × B
L ≥ 2 × 200/(2×10^{8}) × 10^{9}
L ≥ 2000 bits
L ≥ 250 Bytes
Question 66 
Data transmitted on a link uses the following 2D parity scheme for error detection: Each sequence of 28 bits is arranged in a 4×7 matrix (rows r_{0} through r_{3}, and columns d_{7} through d_{1}) and is padded with a column d_{0} and row r_{4} of parity bits computed using the Even parity scheme. Each bit of column d_{0} (respectively, row r_{4}) gives the parity of the corresponding row (respectively, column). These 40 bits are transmitted over the data link. The table shows data received by a receiver and has n corrupted bits. What is the minimum possible value of n?
1  
2  
3  
4 
Here, we need to change minimum 3bits, and by doing it we get correct parity column wise and row wise (correction marked by boxed number).
Question 67 
Two popular routing algorithms are Distance Vector(DV) and Link State (LS) routing. Which of the following are true?

 (S1) Count to infinity is a problem only with DV and not LS routing

 (S2) In LS, the shortest path algorithm is run only at one node

 (S3) In DV, the shortest path algorithm is run only at one node
 (S4) DV requires lesser number of network messages than LS
S1, S2 and S4 only  
S1, S3 and S4 only  
S2 and S3 only  
S1 and S4 only 
→ In LSR shortest path is calculated at each every router. (B) is wrong.
→ In DVR also shortest path is calculated at each and every router. (C) is wrong.
→ Since DVR is based upon local knowledge whereas LSR is based upon global knowledge.
Question 68 
Which of the following statements are TRUE?

 (S1) TCP handles both congestion and flow control

 (S2) UDP handles congestion but not flow control

 (S3) Fast retransmit deals with congestion but not flow control
 (S4) Slow start mechanism deals with both congestion and flow control
S1, S2 and S3 only  
S1 and S3 only  
S3 and S4 only  
S1, S3 and S4 only 
TCP handles both congestion and flow control ⇒ True.
S2:
UDP handles congestion but not flow control ⇒ False, because UDP neither handles congestion control nor flow control.
S3:
Fast retransmits deals with congestion but not flow control ⇒ True.
S4:
Slow start mechanism deals with both congestion and flow control ⇒ False, because it has nothing to do with flow control. Flow control is taken care by Advertisement window.
Question 69 
The three way handshake for TCP connection establishment is shown below.
Which of the following statements are TRUE? (S1) Loss of SYN + ACK from the server will not establish a connection (S2) Loss of ACK from the client cannot establish the connection (S3) The server moves LISTEN → SYN_RCVD → SYN_SENT → ESTABLISHED in the state machine on no packet loss (S4) The server moves LISTEN → SYN_RCVD → ESTABLISHED in the state machine on no packet loss.
S2 and S3 only  
S1 and S4  
S1 and S3  
S2 and S4 
S2 → False, because if after ACK client immediately sends data then everything goes on without worry.
S3 → False.
S4 → True.
Question 70 
The total number of keys required for a set of n individuals to be able to communicate with each other using secret key and public key cryptosystems, respectively are:
n(n1) and 2n  
2n and n(n1)/2  
n(n1)/2 and 2n  
n(n1)/2 and n 
^{n}C_{2} = n(n1)/2
In case of public key, each sender has its own public key as well as private key. So, no. of keys are 2n.
Question 71 
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
I. 81, 537, 102, 439, 285, 376, 305 II. 52, 97, 121, 195, 242, 381, 472 III. 142, 248, 520, 386, 345, 270, 307 IV. 550, 149, 507, 395, 463, 402, 270
Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?
II and III only  
I and III only  
III and IV only  
III only 
Question 72 
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
I. 81, 537, 102, 439, 285, 376, 305 II. 52, 97, 121, 195, 242, 381, 472 III. 142, 248, 520, 386, 345, 270, 307 IV. 550, 149, 507, 395, 463, 402, 270
Which of the following statements is TRUE?
I, II and IV are inorder sequences of three different BSTs  
I is a preorder sequence of some BST with 439 as the root  
II is an inorder sequence of some BST where 121 is the root and 52 is a leaf  
IV is a postorder sequence of some BST with 149 as the root 
B) False because if 439 is root then it should be first element in preorder.
C) This is correct.
D) False because if 149 is root, then it should be last element in postorder.
Question 73 
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
I. 81, 537, 102, 439, 285, 376, 305 II. 52, 97, 121, 195, 242, 381, 472 III. 142, 248, 520, 386, 345, 270, 307 IV. 550, 149, 507, 395, 463, 402, 270
How many distinct BSTs can be constructed with 3 distinct keys?
4  
5  
6  
9 
^{2n}C_{n}/n+1 = ^{6}C_{3}/7 = 5
Question 74 
Consider the following relational schema:
Student (schoolid, schrollno, sname, saddress) School (schoolid, schname, schaddress, schphone) Enrolment(schoolid, schrollno, erollno, examname) ExamResult(erollno, examname, marks)
What does the following SQL query output?
SELECT schname, COUNT (*) FROM School C, Enrolment E, ExamResult R WHERE E.schoolid = C.schoolid AND E.examname = R.examname AND E.erollno = R.erollno AND R.marks = 100 AND S.schoolid IN (SELECT schoolid FROM student GROUP BY schoolid HAVING COUNT (*) > 200) GROUP By schoolid
for each school with more than 200 students appearing in exams, the name of the school and the number of 100s scored by its students  
for each school with more than 200 students in it, the name of the school and the number of 100s scored by its students  
for each school with more than 200 students in it, the name of the school and the number of its students scoring 100 in at least one exam  
nothing; the query has a syntax error

Question 75 
Consider the following relational schema:
Student (schoolid, schrollno, sname, saddress) School (schoolid, schname, schaddress, schphone) Enrolment(schoolid, schrollno, erollno, examname) ExamResult(erollno, examname, marks)
Consider the following tuple relational calculus query:
If a student needs to score more than 35 marks to pass an exam, what does the query return?The empty set  
schools with more than 35% of its students enrolled in some exam or the other  
schools with a pass percentage above 35% over all exams taken together  
schools with a pass percentage above 35% over each exam 
{ x  x ∈ Enrollment ∧ x . schoolid = t }  * 100 > 35 }
This is school with enrollment % is 35 or above.
As we are actually taking percentage of
(Total count in which a student has passed from a particular school)/(Total exams taken by all student combined)
Eg: if A passed in 3 and B passed in 4 and they both took 55 exam each. Then it is (7/10)
Question 76 
A binary tree with n > 1 nodes has n_{1}, n_{2} and n_{3} nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. n_{3} can be expressed as
n_{1} + n_{2}  1  
n_{1}  2  
[((n_{1} + n_{2})/2)]  
n_{2}  1 
n_{1} = 3
n_{2} = 1
n_{3} = 1
So, option (B) satisfies.
Question 77 
A binary tree with n > 1 nodes has n_{1}, n_{2} and n_{3} nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two neighbors of v and then remove v from the tree. How many edges will remain at the end of the process?
2 * n_{1} – 3  
n_{2} + 2 * n_{1} – 2  
n_{3} – n_{2}  
n_{2} + n_{1} – 2 
n_{1} = 3
n_{3} = 1
So, option (A) satisfies.
Question 78 
A CFG G is given with the following productions where S is the start symbol, A is a nonterminal and a and b are terminals.
S → aS∣A A → aAb∣bAa∣ϵWhich of the following strings is generated by the grammar above?
aabbaba  
aabaaba  
abababb  
aabbaab 
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
Question 79 
A CFG G is given with the following productions where S is the start symbol, A is a nonterminal and a and b are terminals.
S → aS∣A A → aAb∣bAa∣ϵFor the correct answer in Q75, how many steps are required to derive the string and how many parse trees are there?
6 and 1  
6 and 2  
7 and 2  
4 and 2 
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
⇒ 6 steps are required
Only 1 parse tree is there.
Question 80 
Consider a computer with a 4ways setassociative mapped cache of the following characteristics: a total of 1 MB of main memory, a word size of 1 byte, a block size of 128 words and a cache size of 8 KB. The number of bits in the TAG, SET and WORD fields, respectively are:
7, 6, 7  
8, 5, 7  
8, 6, 6  
9, 4, 7 
No. of sets in cache = 2^{6}/2^{2} = 2^{4}
So no. of set bits = 4
Size of block = 128 words = 128 B = 2^{7}
So no. of word bit = 7
So tag bits = 20  4  7 = 9
Question 81 
Consider a computer with a 4ways setassociative mapped cache of the following characteristics: a total of 1 MB of main memory, a word size of 1 byte, a block size of 128 words and a cache size of 8 KB. While accessing the memory location 0C795H by the CPU, the contents of the TAG field of the corresponding cache line is
000011000  
110001111  
00011000  
110010101 
So lets first convert given Hexadecimal no. into binary number,
Question 82 
Consider the code fragment written in C below :
void f (int n) { if (n <=1) { printf ("%d", n); } else { f (n/2); printf ("%d", n%2); } }
What does f(173) print?
010110101  
010101101  
10110101  
10101101 
So, after traversing the tree we get:
10101101
Question 83 
Consider the code fragment written in C below :
void f (int n) { if (n <= 1) { printf ("%d", n); } else { f (n/2); printf ("%d", n%2); } }
Which of the following implementations will produce the same output for f(173) as the above code?
P1 void f (int n) { if (n/2) { f(n/2); } printf ("%d", n%2); } P2 void f (int n) { if (n <=1) { printf ("%d", n); } else { printf ("%d", n%2); f (n/2); } }
Both P1 and P2  
P2 only  
P1 only  
Neither P1 nor P2 
But P2 prints the reverse of original sequence printed by original program.
Question 84 
Host X has IP address 192.168.1.97 and is connected through two routers R1 and R2 to another host Y with IP address 192.168.1.80. Router R1 has IP addresses 192.168.1.135 and 192.168.1.110. R2 has IP addresses 192.168.1.67 and 192.168.1.155. The netmask used in the network is 255.255.255.224. Given the information above, how many distinct subnets are guaranteed to already exist in the network?
1  
2  
3  
6 
XX.XX.XX.96, XX.XX.XX.64 and XX.XX.XX.128.
Question 85 
Host X has IP address 192.168.1.97 and is connected through two routers R1 and R2 to another host Y with IP address 192.168.1.80. Router R1 has IP addresses 192.168.1.135 and 192.168.1.110. R2 has IP addresses 192.168.1.67 and 192.168.1.155. The netmask used in the network is 255.255.255.224. Which IP address should X configure its gateway as?
192.168.1.67  
192.168.1.110  
192.168.1.135  
192.168.1.155 
Subnet no. of host X is,
Now, the gateway must also have the same subnet number.
Let's take IP 192.168.1.110 of R1,
and hence this can be used by X.