GATE 2006IT
Question 1 
In a certain town, the probability that it will rain in the afternoon is known to be 0.6. Moreover, meteorological data indicates that if the temperature at noon is less than or equal to 25°C, the probability that it will rain in the afternoon is 0.4. The temperature at noon is equally likely to be above 25°C, or at/below 25°C. What is the probability that it will rain in the afternoon on a day when the temperature at noon is above 25°C?
0.4  
0.6  
0.8  
0.9 
0.6 = (0.5×0.4) + (0.5×P(rain at temp>25)
0.6 = (2) + (0.5×P(rain at temp>25)
P(rain at temp>25) = 0.8
Question 2 
For the set N of natural numbers and a binary operation f : N x N → N, an element z ∊ N is called an identity for f, if f (a, z) = a = f(z, a), for all a ∊ N. Which of the following binary operations have an identity?
 1. f(x,y) = x + y  3
2. f(x,y) = max(x, y)
3. f(x,y) = x^{y}
1 and 2 only  
2 and 3 only  
1 and 3 only  
None of these 
y = 3
Here, identity element is 3.
(2) f(x, y) = max(x, y) = x = max(y, x)
⇒ y = 1
Here, identity element = 1
(3) f(x, y) = x^{n}y is not equal to f(y, x) = y^{n}x
So, no identity element.
Question 3 
In the automaton below, s is the start state and t is the only final state.
Consider the strings u = abbaba, v = bab, and w = aabb. Which of the following statements is true?
The automaton accepts u and v but not w  
The automaton accepts each of u, v, and w  
The automaton rejects each of u, v, and w  
The automaton accepts u but rejects v and w 
where t is final state
(ii) v = bab
s is not final state
(iii) w = aabb
s is not final state
Question 4 
In the contextfree grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string
S → aSa  bSb  a  b  ϵWhich of the following strings is NOT generated by the grammar?
aaaa  
baba  
abba  
babaaabab 
Given string accepts all palindromes.
Option B → baba is not palindrome.
So, this is not accepted by S.
Question 5 
Which regular expression best describes the language accepted by the nondeterministic automaton below?
(a + b)* a(a + b)b  
(abb)*  
(a + b)* a(a + b)* b(a + b)*  
(a + b)* 
Question 6 
Given a Boolean function f (x_{1}, x_{2}, …, x_{n}), which of the following equations is NOT true.
f (x_{1}, x_{2}, …, x_{n}) = x_{1}’f(x_{1}, x_{2}, …, x_{n}) + x_{1}f(x_{1}, x_{2}, …, x_{n})  
f (x_{1}, x_{2}, …, x_{n}) = x_{2}f(x_{1}, x_{2}, …, x_{n}) + x_{2}’f(x_{1}, x_{2}, …, x_{n})  
f (x_{1}, x_{2}, …, x_{n}) = x_{n}’f(x_{1}, x_{2}, …, 0) + x_{n}f(x_{1}, x_{2}, …,1)  
f (x_{1}, x_{2}, …, x_{n}) = f(0, x_{2}, …, x_{n}) + f(1, x_{2}, .., x_{n}) 
LHS: f(x_{1}) = 0 where x_{1} = 0
LHS: f(x_{1}) = 1 when x1 = 1
RHS: f(0) + f(1) = 0 + 1 = always 1
Question 7 
The addition of 4bit, two’s complement, binary numbers 1101 and 0100 results in
0001 and an overflow  
1001 and no overflow  
0001 and no overflow  
1001 and an overflow 
2's complement of 1100 = 1100
Add = 1111
Now convert 1111 to normal form.
⇒ 0000 (1's complement)
⇒ 0001 (2's complement) No carry bit.
Question 8 
Which of the following DMA transfer modes and interrupt handling mechanisms will enable the highest I/O bandwidth?
Transparent DMA and Polling interrupts  
Cyclestealing and Vectored interrupts  
Block transfer and Vectored interrupts  
Block transfer and Polling interrupts 
→ In case of cycle stealing in each cycle time derive send data then wait again few CPU cycle it sends to memory. So, option B is wrong.
→ In case of polling CPU takes the initiative. So I/O bandwidth cannot be high. So, option D is wrong.
→ Consider block transfer in each single block device. Send data so bandwidth must be high. This makes option (C) correct.
Question 9 
In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is
10  
11  
12  
15 
No. of 1 degree nodes = 5
No. of 2 degree nodes = 10
Total no. of edges = (1*5) + (2*10) = 5 + 20 = 25
So, Total no. of edges = 25 + 1 = 26 (No. of nodes in a tree is 1 more than no. of edges)
Total no. of leaf nodes (node with 0 degree) = 26  5  10 = 11
Question 10 
A problem in NP is NPcomplete if
It can be reduced to the 3SAT problem in polynomial time  
The 3SAT problem can be reduced to it in polynomial time  
It can be reduced to any other problem in NP in polynomial time  
Some problem in NP can be reduced to it in polynomial time

Question 11 
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a
Hamiltonian cycle  
grid  
hypercube  
tree 
If all edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is minimum spanning tree.
Question 12 
In the workingset strategy, which of the following is done by the operating system to prevent thrashing?
1. It initiates another process if there are enough extra frames.
2. It selects a process to suspend if the sum of the sizes of the workingsets exceeds the total number of available frames.
1 only  
2 only  
Neither 1 nor 2  
Both 1 and 2 
Question 13 
The process state transition diagram of an operating system is as given below.
Which of the following must be FALSE about the above operating system?
It is a multiprogrammed operating system  
It uses preemptive scheduling  
It uses nonpreemptive scheduling  
It is a multiuser operating system 
Question 14 
Consider the relations r_{1}(P, Q, R) and r_{2}(R, S, T) with primary keys P and R respectively. The relation r_{1} contains 2000 tuples and r_{2} contains 2500 tuples. The maximum size of the join r_{1}⋈ r_{2} is :
2000  
2500  
4500  
5000 
Question 15 
Which of the following relational query languages have the same expressive power?
1. Relational algebra
2. Tuple relational calculus restricted to safe expressions
3. Domain relational calculus restricted to safe expressions
2 and 3 only  
1 and 2 only  
1 and 3 only  
1, 2 and 3 
Question 16 
The cyclomatic complexity of the flow graph of a program provides
an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at most once  
a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at most once  
an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once  
a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at least once 
Question 17 
With respect to software testing, consider a flow graph G with one connected component. Let E be the number of edges, N be the number of nodes, and P be the number of predicate nodes of G. Consider the following four expressions:
1. E  N + P
2. E  N + 2
3. P + 2
4. P + 1
The cyclomatic complexity of G is given by
1 or 3  
2 or 3  
2 or 4  
1 or 4 
Question 18 
HELO and PORT, respectively, are commands from the protocols
FTP and HTTP  
TELNET and POP3  
HTTP and TELNET  
SMTP and FTP 
Question 19 
Which of the following statements is TRUE?
Both Ethernet frame and IP packet include checksum fields  
Ethernet frame includes a checksum field and IP packet includes a CRC field  
Ethernet frame includes a CRC field and IP packet includes a checksum field  
Both Ethernet frame and IP packet include CRC fields 
IP packet:
IP Datagram:
Question 20 
Which of the following statement(s) is TRUE?
1. A hash function takes a message of arbitrary length and generates a fixed length code.
2. A hash function takes a message of fixed length and generates a code of variable length.
3. A hash function may give the same hash value for distinct messages.
1 only  
2 and 3 only  
1 and 3 only  
2 only 
(2) Statement2 is wrong, refer statement1.
(3) Statement3 is correct, for example hash function N%10, this will generate same values for 1 as well as 2!
Question 21 
Consider the following first order logic formula in which R is a binary relation symbol.
∀x∀y (R(x, y) => R(y, x))The formula is
satisfiable and valid  
satisfiable and so is its negation  
unsatisfiable but its negation is valid  
satisfiable but its negation is unsatisfiable 
Question 22 
When a coin is tossed, the probability of getting a Head is p, 0 < p < 1. Let N be the random variable denoting the number of tosses till the first Head appears, including the toss where the Head appears. Assuming that successive tosses are independent, the expected value of N is
1/p  
1/(1p)  
1/p^{2}  
1/(1p^{2}) 
Multiply both sides with (1  p) and subtract,
E  (1  p) E = 1 × p + (1  p) p + (1  p) (1  p) p + ......
E  (1  p) E = p/(1  (1  p))
(1  1 + p) E = 1
pE = 1
E = 1/p
Question 23 
Let P, Q and R be sets let Δ denote the symmetric difference operator defined as PΔQ = (P U Q)  (P ∩ Q). Using Venn diagrams, determine which of the following is/are TRUE?
1. PΔ (Q ∩ R) = (P Δ Q) ∩ (P Δ R)
2. P ∩ (Q ∩ R) = (P ∩ Q) Δ (P Δ R)
1 only  
2 only  
Neither 1 nor 2  
Both 1 and 2 
P = {1, 2, 4, 5}
Q = {2, 3, 5, 6}
R = {4, 5, 6, 7}
(1) P Δ (Q ∩ R) = (P Δ Q) ∩ (P Δ R)
P Δ ({2,3,5,6} ∩ {4,5,6,7}) = ({1,2,4,5} Δ {2,3,5,6} ∩ {1,2,4,5} Δ {4,5,6,7})
P Δ {5,6} = ({1,2,3,4,5,6}  {2,5}) ∩ ({1,2,4,5,6,7}  {4,5})
({1,2,4,5} Δ {5,6}) = {1,3,4,6} ∩ {1,2,6,7}
{1,2,4,5,6}  {5} = {1,6}
{1,2,4,6} ≠ {1,6}
Statement1 is False.
(2) P ∩ (Q ∩ R) = (P ∩ Q) Δ (P Δ R)
LHS:
{1,2,4,5} ∩ {5,6} = {5}
RHS:
({1,2,4,5} ∩ {2,3,5,6}) Δ ({1,2,4,5} Δ {4,5,6,7})
{2,5} Δ ({1,2,4,5,6,7}  {4,5})
{2,5} Δ {1,2,6,7}
{1,2,5,6,7}  {2}
{1,5,6,7}
LHS ≠ RHS
Statement  2 is also wrong.
Question 24 
What is the cardinality of the set of integers X defined below?
X = {n  1 ≤ n ≤ 123, n is not divisible by either 2, 3 or 5}
28  
33  
37  
44 
A = set of numbers divisible by 2
B = set of numbers divisible by 3
C = set of numbers divisible by 5
n(A∪B∪C) = n(A) + n(B) + n(C)  n(A∩B)  n(B∩C)  n(C∩A) + n(A∩B∩C)
= ⌊123/2⌋ + ⌊123/3⌋ + ⌊123/5⌋  ⌊123/6⌋  ⌊123/15⌋  ⌊123/10⌋ + ⌊123/30⌋
= 61 + 41 + 24  20 12  8 + 4
= 90
Total no. that are not divisible
= n  n(A∪B∪C)
= 123  90
= 33
Question 25 
Consider the undirected graph G defined as follows. The vertices of G are bit strings of length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position (in other words, v can be obtained from u by flipping a single bit). The ratio of the chromatic number of G to the diameter of G is
1/(2^{n1})  
1/n  
2/n  
3/n 
That will give us a bipartite graph, with chromatic number = 2
Also from the same we can conclude that we need for a 'n' bit string, to traverse no more than (n1) edges or 'n' vertices to get a path between two arbitrary points. So the ratio is (2/n).
Question 26 
What are the eigenvalues of the matrix P given below
a, a, a  
0, a, 2a  
a, 2a, 2a 
Question 27 
Match the following iterative methods for solving algebraic equations and their orders of convergence.
1R, 2S, 3P, 4Q  
1S, 2R, 3Q, 4P  
1S, 2Q, 3R, 4P  
1S, 2P, 3Q, 4R 
Question 28 
The following definite integral evaluates to
1/2  
π √10  
√10  
π  
None of the above 
Question 29 
Consider the regular grammar below
S → bS  aA  ϵ A → aS  bA
The MyhillNerode equivalence classes for the language generated by the grammar are
{w ∈ (a + b)*  #a(w) is even) and {w ∈ (a + b)*  #a(w) is odd}  
{w ∈ (a + b)*  #a(w) is even) and {w ∈ (a + b)*  #b(w) is odd}  
{w ∈ (a + b)*  #a(w) = #b(w) and {w ∈ (a + b)*  #a(w) ≠ #b(w)}  
{ϵ}, {wa  w ∈ (a + b)* and {wb  w ∈ (a + b)*} 
⇒ This results even number, no. of a's.
Question 30 
Which of the following statements about regular languages is NOT true?
Every language has a regular superset  
Every language has a regular subset  
Every subset of a regular language is regular  
Every subset of a finite language is regular 
Question 31 
Which of the following languages is accepted by a nondeterministic pushdown automaton (PDA) but NOT by a deterministic PDA?
{a^{n}b^{n}c^{n} ∣ n≥0}  
{a^{l}b^{m}c^{n} ∣ l≠m or m≠n}  
{a^{n}b^{n} ∣ n≥0}  
{a^{m}b^{n}∣ m,n≥0} 
To compare both conditions at the same time, we need a NPDA.
Question 32 
Let L be a contextfree language and M a regular language. Then the language L ∩ M is
always regular  
never regular  
always a deterministic contextfree language  
always a contextfree language 
Question 33 
Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z_{0}, X} where Z_{0} is the bottomofstack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) → (t, XZ_{0}) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z_{0} and X (in that order) on the stack.
(s, a, Z_{0}) → (s, XXZ_{0}) (s, ϵ, Z_{0}) → (f, ϵ) (s, a, X) → (s, XXX) (s, b, X) → (t, ϵ) (t, b, X) → (t,.ϵ) (t, c, X) → (u, ϵ) (u, c, X) → (u, ϵ) (u, ϵ, Z_{0}) → (f, ϵ)
The language accepted by the PDA is
{a^{l}b^{m}c^{n}  l = m = n}  
{a^{l}b^{m}c^{n}  l = m}  
{a^{l}b^{m}c^{n}  2l = m+n}  
{a^{l}b^{m}c^{n}  m=n} 
For every 'a' we put two X in stacks [at state S].
After that for every 'b' we pop out one X [reach to state t].
After that for every 'c' we pop out one X [reach to state u].
If all X are popped out then reached to final state f, means for every 'b' and 'c' there is 'a'. 'a' is followed by 'b' and 'b' is followed by 'c'.
Means,
Sum of no. of b's and no. of c's = twice of no. of a's
i.e., {a^{l}b^{m}c^{n}  2l = m+n}
Question 34 
In the contextfree grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string.
S → aSAb  ϵ A → bA  ϵ
The grammar generates the language
((a + b)* b)*  
{a^{m}b^{n}  m ≤ n}  
{a^{m}b^{n}  m = n}  
a* b* 
((a + b)* b)* → It accepts string aa but given grammar does not accepts.
Option C&D:
→ abb accepted by given grammar but option C & D are not accepting.
Question 35 
The boolean function for a combinational circuit with four inputs is represented by the following Karnaugh map.
Which of the product terms given below is an essential prime implicant of the function?
QRS  
PQS  
PQ'S'  
Q'S' 
Question 36 
The majority function is a Boolean function f(x, y, z) that takes the value 1 whenever a majority of the variables x, y, z and 1. In the circuit diagram for the majority function shown below, the logic gates for the boxes labeled P and Q are, respectively,
XOR, AND  
XOR, XOR  
OR, OR  
OR, AND 
Thus we have OR and AND which gives different outputs on (0,0) and (1,1).
The encodes can be hence select from the two and decide output of the function according to x.
Question 37 
For a state machine with the following state diagram the expression for the next state S^{+} in terms of the current state S and the input variables x and y is
S^{+} = S’ . y’ + S . x  
S^{+} = S. x . y’ + S’ . y . x’  
S^{+} = x . y’  
S^{+} = S’ . y + S . x’col 
From the table:
S' = S'y' + Sx
Question 38 
When multiplicand Y is multiplied by multiplier X = x_{n1}x_{n2} ...x_{0} using bitpair recoding in Booth's algorithm, partial products are generated according to the following table.
The partial products for rows 5 and 8 are
2Y and Y  
2Y and 2Y  
2Y and 0  
0 and Y 
⇒ 2Y and 0
Question 39 
Which of the following statements about relative addressing mode is FALSE?
It enables reduced instruction size  
It allows indexing of array elements with same instruction  
It enables easy relocation of data  
It enables faster address calculations than absolute addressing 
Question 40 
The memory locations 1000, 1001 and 1020 have data values 18, 1 and 16 respectively before the following program is executed.
MOVI Rs, 1 ; Move immediate LOAD Rd, 1000(Rs) ; Load from memory ADDI Rd, 1000 ; Add immediate STOREI 0(Rd), 20 ; Store immediate
Which of the statements below is TRUE after the program is executed?
Memory location 1000 has value 20  
Memory location 1020 has value 20  
Memory location 1021 has value 20  
Memory location 1001 has value 20 
Rd ← 1
Rd ← 1001
Store in address 1001 ← 20.
Question 41 
The data path shown in the figure computes the number of 1s in the 32bit input word corresponding to an unsigned even integer stored in the shift register. The unsigned counter, initially zero, is incremented if the most significant bit of the shift register is
The microprogram for the control is shown in the table below with missing control words for microinstructions I_{1}, I_{2}, ..... I_{n}.
The counter width (k), the number of missing microinstructions (n), and the control word for microinstructions I_{2}, ..... I_{n} are, respectively,
32, 5, 010  
5, 32, 010  
5, 31, 011  
5, 31, 010 
→ So, there may be only 31, is for an unsigned even integer.
→ And 31 left shifts are needed to determine the number of 1's.
Question 42 
A cache line is 64 bytes. The main memory has latency 32 ns and bandwidth 1 GBytes/s. The time required to fetch the entire cache line from the main memory is
32 ns  
64 ns  
96 ns  
128 ns 
→ So, for 64 bytes it will take 64*1/10^{9} = 64ns.
Main memory latency = 32
Total time required to place cache line is
64+32 = 96 ns
Question 43 
A computer system has a level1 instruction cache (1cache), a level1 data cache (Dcache) and a level2 cache (L2cache) with the following specifications:
The length of the physical address of a word in the main memory is 30 bits. The capacity of the tag memory in the Icache, Dcache and L2cache is, respectively,
1K × 18bit, 1K × 19bit, 4K × 16bit  
1K × 16bit, 1K × 19bit, 4K × 18bit  
1K × 16bit, 512 × 18bit, 1K × 16bit  
1K × 18bit, 512 × 18bit, 1K × 18bit 
Bits to represent blocks = m
No. of words in a block = 2^{n}
Bits to represent a word = n
Tag bits = (length of physical address of a word)  (bits to represent blocks)  (bits to represent a word)
⇒ Each block will have its own tag bits.
So, total tag bits = no. of blocks × tag bits.
Question 44 
Which of the following sequences of array elements forms a heap?
{23, 17, 14, 6, 13, 10, 1, 12, 7, 5}  
{23, 17, 14, 6, 13, 10, 1, 5, 7, 12}  
{23, 17, 14, 7, 13, 10, 1, 5, 6, 12}  
{23, 17, 14, 7, 13, 10, 1, 12, 5, 7} 
In this every children and parent satisfies Max heap properties.
Question 45 
Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examined?
{10, 75, 64, 43, 60, 57, 55}  
{90, 12, 68, 34, 62, 45, 55}  
{9, 85, 47, 68, 43, 57, 55}  
{79, 14, 72, 56, 16, 53, 55} 
Question 46 
Which of the following is the correct decomposition of the directed graph given below into its strongly connected components?
{P, Q, R, S}, {T}, {U}, {V}  
{P, Q, R, S, T, V}, {U}  
{P, Q, S, T, V}, {R}, {U}  
{P, Q, R, S, T, U, V} 
From given graph {P, Q, R, S, T, V} and {U} are strongly connected components.
Question 47 
Consider the depthfirstsearch of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that
d(P) = 5 units f(P) = 12 units d(Q) = 6 units f(Q) = 10 units d(R) = 14 unit f(R) = 18 units
Which one of the following statements is TRUE about the graph?
There is only one connected component  
There are two connected components, and P and R are connected  
There are two connected components, and Q and R are connected  
There are two connected components, and P and Q are connected 
Question 48 
The characters a to h have the set of frequencies based on the first 8 Fibonacci numbers as follows
a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21
A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the following code?
110111100111010
fdheg  
ecgdf  
dchfg  
fehdg 
∴ 110111100111010 = fdheg
Question 49 
Which one of the choices given below would be printed when the following program is executed?
#includestruct test { int i; char *c; }st[] = {5, "become", 4, "better", 6, "jungle", 8, "ancestor", 7, "brother"}; main () { struct test *p = st; p += 1; ++p > c; printf("%s,", p++ > c); printf("%c,", *++p > c); printf("%d,", p[0].i); printf("%s n", p > c); }
jungle, n, 8, ncestor  
etter, u, 6, ungle  
cetter, k, 6, jungle  
etter, u, 8, ncestor 
Line 1  main ( )
Line 2  {
Line 3  struct test *p = st;
Line 4  p += 1;
Line 5  ++p → c;
Line 6  printf("%s", p++→ c);
Line 7  printf("%c", +++p → c);
Line 8  printf("%d", p[0].i);
Line 9  printf("%s\n", p → c);
Line 10  }
Now,
Line 3: Initially p is pointing to st, i.e., first element of st which is {5, "become"}
Line 4: Now p is pointing to {4, "better"}
Line 5: ++(p → c), since → has higher precedence, so p → c points to 'e' of "better".
Line 6: prints 'enter' and p now points to {6, "jungle"}
Line 7: ***(p → c), since → has higher precedence. So, prints 'u'.
Line 8: p → i, which is 6 so prints '6'.
Line 9: prints 'ungle' since p is pointing to 'u'.
So, output is "enter, u, 6, ungle".
Question 50 
#includevoid swap (int *x, int *y) { static int *temp; temp = x; x = y; y = temp; } void printab () { static int i, a = 3, b = 6; i = 0; while (i <= 4) { if ((i++)%2 == 1) continue; a = a + i; b = b + i; } swap (&a, &b); printf("a = %d, b = %d\n", a, b); } main() { printab(); printab(); }
a = 0, b = 3 a = 0, b = 3  
a = 3, b = 0 a = 12, b = 9  
a = 3, b = 6 a = 3, b = 6  
a = 6, b = 3 a = 15, b = 12 
Inside print 'a' and 'b' are added to odd integers from 1 to 5, i.e., 1+3+5=9. So, in first call to print ab,
a = 3+9 = 6
b = 6+9 = 3
Static variable have one memory throughout the program run (initialized during program start) and they keep their values across function calls. So during second call to print ab,
a = 6+9 = 15
b = 3+9 = 12
Question 51 
Which one of the choices given below would be printed when the following program is executed?
#includeint a1[] = {6, 7, 8, 18, 34, 67}; int a2[] = {23, 56, 28, 29}; int a3[] = {12, 27, 31}; int *x[] = {a1, a2, a3}; void print(int *a[]) { printf("%d,", a[0][2]); printf("%d,", *a[2]); printf("%d,", *++a[0]); printf("%d,", *(++a)[0]); printf("%d/n", a[1][+1]); } main() { print(x); }
8, 12, 7, 23, 8  
8, 8, 7, 23, 7  
12, 12, 27, 31, 23  
12, 12, 27, 31, 56 
It returns the value of 3^{rd} element in a1.
First printf print 8.
2) *a[2] = *(*(a+2))
It returns the value of 1^{st} element in a3.
Second printf print 12.
3) *++a[0] = *(++(*(a+0)))
a[0] is pointing to 1^{st} element in a1.
++a[0]  after preincrement performed, now a[0] is pointing to 2^{nd} element in a1.
*++a[0] return the value of 2^{nd} element in a1.
Third printf print 7.
4) *(++a)[0]
++a  after preincrement is performed 'a' is pointing to a2.
(++a)[0] is pointing to 1^{st} element in a2.
*(++a)[0] returns the value of 1^{st} element in a2.
Fourth printf print 23.
5) a[1][+1] = *(*(a1)+1)
(a1) is pointing to a1.
*(a1) is pointing to the 2^{nd} element in a1, because in 3^{rd} printf already a1 was incremented by 1.
*(a1)+1 is pointing 3^{rd} element in a1.
*(*(a1)+1) returns the value of 3^{rd} element in a1, i.e., 8.
Question 52 
The following function computes the value of ^{m}C_{n} correctly for all legal values m and n (m≥1,n≥0 and m>n)
int func(int m, int n) { if (E) return 1; else return(func(m  1, n) + func(m  1, n  1)); }
In the above function, which of the following is the correct expression for E?
(n == 0)  (m == 1)  
(n == 0) && (m == 1)  
(n == 0)  (m == n)  
(n == 0) && (m == n) 
^{m}C_{0} = 1
^{n}C_{n} = 1
Question 53 
Match the following concepts and their best possible descriptions.
 Concept:
(i) overloading
(ii) friend
(iii) constructor
(iv) protected
(v) this
(vi) inheritance
Descriptions:
A. allows to define a class to have a properties of another class
B. defining a set of similar functions
C. used in dereferncing
D. used to given a non  member function access to the private parts of body
E. a function which is automatically called when object is created
F. allows a derived class to have access to the private parts of the base
G. a pointer to the object associated with the current functions
H. used to obtain persistence
(i)  B, (ii)  D, (iii)  E, (iv)  F, (v)  G, (vi)  A  
(i)  C, (ii)  A, (iii)  E, (iv)  D, (v)  H, (vi)  F  
(i)  C, (ii)  F, (iii)  H, (iv)  A, (v)  G, (vi)  D  
(i)  B, (ii)  E, (iii)  C, (iv)  F, (v)  G, (vi)  H 
Question 54 
The arrival time, priority, and duration of the CPU and I/O bursts for each of three processes P_{1}, P_{2} and P_{3} are given in the table below. Each process has a CPU burst followed by an I/O burst followed by another CPU burst. Assume that each process has its own I/O resource.
The multiprogrammed operating system uses preemptive priority scheduling. What are the finish times of the processes P_{1}, P_{2} and P_{3} ?
11, 15, 9  
10, 15, 9  
11, 16, 10  
12, 17, 11 
Hence, finish times of process.
P_{1}  10
P_{2}  11
P_{3}  9
Question 55 
Consider the solution to the bounded buffer producer/consumer problem by using general semaphores S, F, and E. The semaphore S is the mutual exclusion semaphore initialized to 1. The semaphore F corresponds to the number of free slots in the buffer and is initialized to N. The semaphore E corresponds to the number of elements in the buffer and is initialized to 0.
Producer Process Consumer Process Produce an item; Wait(E); Wait(F); Wait(S); Wait(S); Append the items to the buffer; Signal(S); Signal(S); Signal(F); Signal(E); Consume the item;
Which of the following interchange operations may result in a deadlock?
1. Interchanging Wait (F) and Wait (S) in the Producer process
2. Interchanging Signal (S) and Signal (F) in the Consumer process
1 only  
2 only  
Neither 1 nor 2  
Both 1 and 2 
Now if Wait(S) in producer succeeds, then producer will wait for Wait(F) which is never going to succeed as consumer would be waiting for Wait(S). So deadlock, can happen.
If Signal(S) and Signal(F) are interchanged in consumer, deadlock won't happen. It will just give priority to a producer compared to the next consumer waiting.
Question 56 
For each of the four processes P_{1}, P_{2}, P_{3} and P_{4}. The total size in kilobytes (KB) and the number of segments are given below.
The page size is 1 KB. The size of an entry in the page table is 4 bytes. The size of an entry in the segment table is 8 bytes. The maximum size of a segment is 256 KB. The paging method for memory management uses twolevel paging, and its storage overhead is P. The storage overhead for the segmentation method is S. The storage overhead for the segmentation and paging method is T. What is the relation among the overheads for the different methods of memory management in the concurrent execution of the above four processes?
P < S < T  
S < P < T  
S < T < P  
T < S < P 
For P_{1},
Page size is 1KB. So, no. of pages required for P_{1}=195. An entry in page table is of size 4 bytes and assuming an inner level page table takes the size of a page, we can have upto 256 entries in second level page table and we require only 195 for P_{1}. Thus only 1 second level page table is enough. So, memory overhead = 1KB (for first level) + 1KB for second level = 2KB.
For P_{2} and P_{3} also, we get 2KB each and for P_{4} we get 1+2 = 3KB as it requires 1 first level page table and 2 second level page tables (364 > 256). So, total overhead for their concurrent execution = 2×3+3 = 9KB. Thus P = 9KB.
Case2 (For segmentation method):
P_{1} uses 4 segments → 4 entries in segment table = 4×8 = 32Bytes
Similarly, for P_{2}, P_{3} and P_{4} we get 5×8, 3×8 and 8×8 Bytes respectively and the total overhead will be
32+40+24+64 = 160 Bytes
So, S = 160 Bytes
Case3 (For segmentation with paging):
Here, we segment first and then page. So, we need the page table size. We are given maximum size of a segment is 256KB and page size is 1KB and thus we require 256 entries in the page table. So, total size of page table = 256 × 4 = 1024 Bytes (exactly one page size).
So, now for P_{1} we require 1 segment table of size 32 Bytes plus 1 page table of size 1KB.
Similarly,
P_{2}  40 Bytes and 1 KB
P_{3}  24 Bytes and 1 KB
P_{4}  64 Bytes and 1KB
Thus, total overhead = 160 Bytes + 4KB = 4256 Bytes
So, T = 4256 Bytes
So, answer should be S < T < P.
Question 57 
The wait and signal operations of a monitor are implemented using semaphores as follows. In the following,
x is a condition variable,
mutex is a semaphore initialized to 1,
x_sem is a semaphore initialized to 0,
x_count is the number of processes waiting on semaphore x_sem, initially 0, next is a semaphore initialized to 0,
next_count is the number of processes waiting on semaphore next, initially 0.
The body of each procedure that is visible outside the monitor is replaced with the following:
P(mutex); ⋮ body of procedure ⋮ if (next_count > 0) V(next); else V(mutex);Each occurrence of x.wait is replaced with the following:
x_count = x_count + 1; if (next_count > 0) V(next) else V(mutex);  E_{1}; x_count = x_count  1;Each occurrence of x.signal is replaced with the following:
if (x_count > 0) { next_count = next_count + 1;  E_{2}; P(next), next_count = next_count  1; }For correct implementation of the monitor, statements E_{1} and E_{2} are, respectively,
P(x_sem), V(next)  
V(next), P(x_sem)  
P(next), V(x_sem)  
P(x_sem), V(x_sem) 
x_count is incremented and decremented in x_wait, which shows that in between them wait(x_sem) must happen which is P(x_sem). Correspondingly V(x_sem) must happen in x_signal. So, D choice.
Question 58 
A software program consists of two modules M_{1} and M_{2} that can fail independently, but never simultaneously. The program is considered to have failed if any of these modules fails. Both the modules are ‘repairable’ and so the program starts working again as soon as the repair is done. Assume that the mean time to failure (MTTF) of M_{1}is T_{1} with a mean time to repair (MTTR) of R_{1}. The MTTF of M_{2} is T_{2} with an MTTR of R_{2}. What is the availability of the overall program given that the failure and repair times are all exponentially distributed random variables?
Question 59 
Consider the following structure chart diagram. The boxes have function names embedded in them, while the variables are indicated along the arcs.
Given below are a set of statements relevant to the above diagram.
I. F3 and F6 can be in the same module.
II. F4 and F6 can be in the same module.
III. A4 is both an output and a control variable.
IV. It is incorrect to pass A1 as data and use it as a control variable.
Which combination of these statements is TRUE?
III and IV  
I and IV  
II and IV  
I, II and IV 
Question 60 
Consider a relation R with five attributes V, W, X, Y, and Z. The following functional dependencies hold: VY → W, WX → Z, and ZY → V.
Which of the following is a candidate key for R?
VXZ  
VXY  
VWXY  
VWXYZ 
Candidate keys are
VXY, WXY, ZXY
Question 61 
In a database file structure, the search key field is 9 bytes long, the block size is 512 bytes, a record pointer is 7 bytes and a block pointer is 6 bytes. The largest possible order of a nonleaf node in a B^{+} tree implementing this file structure is
23  
24  
34  
44 
n × p + (n  1) × k ≤ B (for nonleaf node)
Here, n = order, p = tree/block/index pointer, B = size of block
So,
n × p + (n  1) × k ≤ B
n × 6 + (n  1) × 9 ≤ 512
n ≤ 34.77
∴ n = 34
Question 62 
Consider the following XML DTD describing course information in a university:
<!ELEMENT Univ (Course+, Prof+)> <!ELEMENT Course (Title, Eval*)> <!ATTLIST Course Number ID #REQUIRED Instructor IDREF #IMPLIED> <!ELEMENT Title (#PCDATA)> <!ELEMENT Eval (#PCDATA)> <!ATTLIST Eval Score CDATA #REQUIRED> <!ELEMENT Prof EMPTY> <!ATTLIST Prof Name ID #REQUIRED Teaches IDREF #IMPLIED>
What is returned by the following XQuery?
let $as := //@Score for $c in /Univ/Course[Eval] let $cs := $c/Eval?@Score where min($cs) > avg($as) return $c
The professor with the lowest course evaluation  
Professors who have all their course evaluations above the university average  
The course with the lowest evaluation  
Courses with all evaluations above the university average 
Question 63 
A router uses the following routing table:
A packet bearing a destination address 144.16.68.117 arrives at the router. On which interface will it be forwarded?
eth0  
eth1  
eth2  
eth3 
144.16.68.117 = 144.16.68.01110101 AND 255.255.255.224 = 255.255.255.11100000
= 144.16.68.96(Not matching with destination)
Now, take 255.255.255.0
144.16.68.117 AND 255.255.255.0
= 144.16.68.0 (matched)
Hence, option (C) is correct.
Question 64 
Suppose that it takes 1 unit of time to transmit a packet (of fixed size) on a communication link. The link layer uses a window flow control protocol with a window size of N packets. Each packet causes an ack or a nak to be generated by the receiver, and ack/nak transmission times are negligible. Further, the round trip time on the link is equal to N units. Consider time i > N. If only acks have been received till time i(no naks), then the goodput evaluated at the transmitter at time i(in packets per unit time) is
1 – N/i  
i/(N + i)  
1  
1 – e^{(i/N)} 
So, successful delivery of packet can be assured if ack has been received for it.
So till time 'i' we would have transmitted 'i' packets but only (i  N) can be acknowledged as minimum time for a packet to get acknowledged is N (since RTT is N which is equal to the window size, there is no waiting for the sender).
So, successfully delivered packets = (i  N)
Time for transmission = i
Goodput = Successfully delivered data/Time
= (i  N)/i
= 1  N/i
Question 65 
In the 4B/5B encoding scheme, every 4 bits of data are encoded in a 5bit codeword. It is required that the codewords have at most 1 leading and at most 1 trailing zero. How many such codewords are possible?
14  
16  
18  
20 
Codeword with first two bits '0'
= 0 0 x x x
= 2^{3}
= 8
Codeword with last two bits '0'
= x x x 0 0
= 2^{3} = 8
Codeword with first two and last two bits '0'
= 0 0 x 0 0
= 2
Codeword with first or last two bits '0'
= 8 + 8  2
= 14
Therefore possible codewords
= 32  14
= 18
Question 66 
A router has two fullduplex Ethernet interfaces each operating at 100 Mb/s. Ethernet frames are at least 84 bytes long (including the Preamble and the InterPacketGap). The maximum packet processing time at the router for wirespeed forwarding to be possible is (in microseconds)
0.01  
3.36  
6.72  
8 
T_{t} = 84×8/10×10^{6} = 6.72μs
But since a router has two fullduplex ethernet interfaces, so the maximum processing time should be,
6.72/2 μs = 3.36μs
Question 67 
A link of capacity 100 Mbps is carrying traffic from a number of sources. Each source generates an onoff traffic stream; when the source is on, the rate of traffic is 10 Mbps, and when the source is off, the rate of traffic is zero. The duty cycle, which is the ratio of ontime to offtime, is 1:2. When there is no buffer at the link, the minimum number of sources that can be multiplexed on the link so that link capacity is not wasted and no data loss occurs is S_{1}. Assuming that all sources are synchronized and that the link is provided with a large buffer, the maximum number of sources that can be multiplexed so that no data loss occurs is S_{2}. The values of S_{1} and S_{2} are, respectively,
10 and 30  
12 and 25  
5 and 33  
15 and 22 
Since there is no buffer and constraint given is there should not be any data lost, and no wastage of capacity as well.
Since data should not be lost, we calculate for the extreme case when all sources are ontime (that is transmitting).
10Mbps × nstation ≤ 100Mbps
n = 10 = S_{1}
In the next part of question, it is given that the link is provided with large buffer and we are asked to find out large no. of stations.
For that we calculate expected value of bandwidth usage,
E = 1/3 × 10 + 1/3 × 10 + .......+ ....... nstation times ≤ 100Mbps
⇒ 1/3 × 10 × nstation ≤ 100Mbps ⇒ nstation = 30 = S_{2}
So option (A) is answer.
Question 68 
On a wireless link, the probability of packet error is 0.2. A stopandwait protocol is used to transfer data across the link. The channel condition is assumed to be independent from transmission to transmission. What is the average number of transmission attempts required to transfer 100 packets?
100  
125  
150  
200 
So here it would be for one frame = 1/(10.2) = 1/0.8
So for 100 frames = 100/0.8 = 125
Question 69 
A program on machine X attempts to open a UDP connection to port 5376 on a machine Y, and a TCP connection to port 8632 on machine Z. However, there are no applications listening at the corresponding ports on Y and Z. An ICMP Port Unreachable error will be generated by
Y but not Z  
Z but not Y  
Neither Y nor Z  
Both Y and Z 
Question 70 
A subnetted Class B network has the following broadcast address: 144.16.95.255. Its subnet mask
is necessarily 255.255.224.0  
is necessarily 255.255.240.0  
is necessarily 255.255.248.0  
could be any one of 255.255.224.0, 255.255.240.0, 255.255.248.0 
Broadcast address for subnet is
.95.255 or .01011111.11111111
(as in class B, 16 bits each are used for network and host)
So, we can take minimum 3 bits (from left) as subnet and make rest as host bits (as they are 1)
.224.0 → 11100000.00000000 (leftmost 3 bits for subnet)
.240.0 → 11110000.00000000 (leftmost 4 bits for subnet)
.248.0 → 11111000.00000000 (leftmost 5 bits for subnet)
Question 71 
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. The index of the parent of element X[i],i≠0 is?
⌊i/2⌋  
⌈(i1)/2⌉  
⌈i/2⌉  
⌈i/2⌉  1 
Question 72 
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of
O(n)  
O(log n)  
O(n log n)  
O(n log log n) 
Question 73 
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If the root node is at level 0, the level of element X[i], i ≠ 0, is
⌊log_{2} i⌋  
⌈log_{2} (i + 1)⌉  
⌊log_{2} (i + 1)⌋  
⌈log_{2} i⌉ 
Question 74 
Consider the following program module:
void swap(float* A1, float* A2) { float temp; if (*A1 = = *A2) return; temp = *A1; *A1 = *A2; *A2 = temp; return; }
The program volume for the above module using Halstead's method is
60  
63  
66  
69 
Question 75 
Consider the following program module:
void swap(float* A1, float* A2) { float temp; if (*A1 = = *A2) return; temp = *A1; *A1 = *A2; *A2 = temp; return; }
The program effort for the above module using Halstead's method is
315  
330  
393  
403 
Question 76 
Consider the following set of linear operations:
x + y/2 = 9
3x + y = 10
The value of the Frobenius norm for the above system of equations is:
0.5  
0.75  
1.5  
2.0 
Question 77 
Consider the following set of linear operations:
x + y/2 = 9
3x + y = 10
What can be said about the GaussSiedel iterative method for solving the above set of linear equations?
it will converge  
it will diverse  
it will neither converge nor diverse  
It is not applicable 
1 + 1/2 <= 9
and 3 + 1 <= 10
Question 78 
A pipelined processor uses a 4stage instruction pipeline with the following stages: Instruction fetch (IF), Instruction decode (ID), Execute (EX) and Writeback (WB). The arithmetic operations as well as the load and store operations are carried out in the EX stage. The sequence of instructions corresponding to the statement X = (S  R * (P + Q))/T is given below. The values of variables P, Q, R, S and T are available in the registers R_{0}, R_{1}, R_{2}, R_{3} and R_{4} respectively, before the execution of the instruction sequence.
The number of ReadAfterWrite (RAW) dependencies, WriteAfterRead( WAR) dependencies, and WriteAfterWrite (WAW) dependencies in the sequence of instructions are, respectively,
2, 2, 4  
3, 2, 3  
4, 2, 2  
3, 3, 2 
I_{1}  I_{2} (R_{5})
I_{2}  I_{3} (R_{6})
I_{3}  I_{4} (R_{5})
I_{4}  I_{5} (R_{6})
WAR:
I_{2}  I_{3} (R_{5})
I_{3}  I_{4} (R_{6})
WAW:
I_{1}  I_{3} (R_{5})
I_{3}  I_{4} (R_{6})
Question 79 
A pipelined processor uses a 4stage instruction pipeline with the following stages: Instruction fetch (IF), Instruction decode (ID), Execute (EX) and Writeback (WB). The arithmetic operations as well as the load and store operations are carried out in the EX stage. The sequence of instructions corresponding to the statement X = (S  R * (P + Q))/T is given below. The values of variables P, Q, R, S and T are available in the registers R_{0}, R_{1}, R_{2}, R_{3} and R_{4} respectively, before the execution of the instruction
The IF, ID and WB stages take 1 clock cycle each. The EX stage takes 1 clock cycle each for the ADD, SUB and STORE operations, and 3 clock cycles each for MUL and DIV operations. Operand forwarding from the EX stage to the ID stage is used. The number of clock cycles required to complete the sequence of instructions is
10  
12  
14  
16 
Question 80 
Let L be a regular language. Consider the constructions on L below:
I. repeat (L) = {ww  w ∊ L}
II. prefix (L) = {u  ∃v : uv ∊ L}
III. suffix (L) = {v  ∃u : uv ∊ L}
IV. half (L) = {u  ∃v :  v  =  u  and uv ∊ L}
Which of the constructions could lead to a nonregular language?
Both I and IV  
Only I  
Only IV  
Both II and III 
Half (L), Suffix (L) and Prefix (L) are regular languages.
Question 81 
Let L be a regular language. Consider the constructions on L below:
(I) repeat (L) = {ww  w ∊ L}
(II) prefix (L) = {u  ∃v : uv ∊ L}
(III) suffix (L) = {v  ∃u uv ∊ L}
(IV) half (L) = {u  ∃v :  v  =  u  and uv ∊ L}
Which choice of L is best suited to support your answer above?
(a + b)*  
{ϵ, a, ab, bab}  
(ab)*  
{a^{n}b^{n}  n ≥ 0} 
1) L should be regular due to demand of question.
2) L should be an infinite set of strings.
3) L should have more than one alphabet in its grammar, otherwise repeat(L) would be regular.
∴ (a + b)* is the perfect example to support the conclusions of last questions.
Question 82 
A software project has four phases P1, P2, P3 and P4. Of these phases, P1 Is the first one and needs to be completed before any other phase can commence. Phases P2 and P3 can be executed in parallel. Phase P4 cannot commence until both P2 and P3 are completed. The optimistic, most likely, and pessimistic estimates of the phase completion times in days, for Pl, P2, P3 and P4 are, respectively, (11, 15, 25), (7, 8, 15), (8, 9, 22), and (3, 8, 19).
The critical path for the above project and the slack of P2 are, respectively,
P1P2P4, 1 day  
P1P3P4, 1 day  
P1P3P4, 2 days  
P1P2P4, 2 days 
Question 83 
A software project has four phases P1, P2, P3 and P4. Of these phases, P1 Is the first one and needs to be completed before any other phase can commence. Phases P2 and P3 can be executed in parallel. Phase P4 cannot commence until both P2 and P3 are completed. The optimistic, most likely, and pessimistic estimates of the phase completion times in days, for Pl, P2, P3 and P4 are, respectively, (11, 15, 25), (7, 8, 15), (8, 9, 22), and (3, 8, 19).
The costs (in Rupees per day) of crashing the expected phase completion times for the four phases, respectively, are 100, 2000, 50, and 1000. Assume that the expected phase completion times of the phases cannot be crashed below their respective most likely completion times. The minimum and the maximum amounts (in Rupees) that can be spent on crashing so that ALL paths are critical are, respectively.
100 and 1000  
100 and 1200  
150 and 1200  
200 and 2000 
Question 84 
Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are did and cid respectively and the records are stored in ascending order of these primary keys as given in the tables. No indexing is available
What is the output of the following SQL query?
select D.dname from Drivers D where D.did in ( select R.did from Cars C, Reserves R where R.cid = C.cid and C.colour = 'red' intersect select R.did from Cars C, Reserves R where R.cid = C.cid and C.colour = 'green' )
Karthikeyan, Boris  
Sachin, Salman  
Karthikeyan, Boris, Sachin  
Schumacher, Senna

did = {22, 22, 31, 31, 64}
For colour = "Green"
did = {22, 31, 74}
Intersection of Red and Green will be = {22, 31}, which is Karthikeyan and Boris.
Question 85 
Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are did and cid respectively and the records are stored in ascending order of these primary keys as given in the tables. No indexing is available
Let n be the number of comparisons performed when the above SQL query is optimally executed. If linear search is used to locate a tuple in a relation using primary key, then n lies in the range
36  40  
44  48  
60  64  
100  104 
red did : 22, 31, 64
green did : 22, 31, 74
(6) for intersection
(1) for searching 22 in driver relation, and (3) for searching 31.
Total: 38 + 6 + 4 = 48