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 
 f (x, y) = x + y  3
 f (x, y) = max(x, y)
 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 
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 
aaaa  
baba  
abba  
babaaabab 
Given string accepts all palindromes.
Option B → baba is not palindrome.
So, this is not accpeted by S.
Question 5 
(a + b)* a(a + b)b  
(abb)*  
(a + b)* a(a + b)* b(a + b)*  
(a + b)* 
Question 6 
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 
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 
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 
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 
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 
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 
 It initiates another process if there are enough extra frames.
 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 
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 
 Relational algebra
 Tuple relational calculus restricted to safe expressions
 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 
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 
 E  N + P
 E  N + 2
 P + 2
 P + 1
1 or 3  
2 or 3  
2 or 4  
1 or 4 
Question 18 
FTP and HTTP  
TELNET and POP3  
HTTP and TELNET  
SMTP and FTP 
Question 19 
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 
 A hash function takes a message of arbitrary length and generates a fixed length code.
 A hash function takes a message of fixed length and generates a code of variable length.
 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 
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 
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 
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 arbitary points. So the ratio is (2/n).
Question 27 
1R, 2S, 3P, 4Q  
1S, 2R, 3Q, 4P  
1S, 2Q, 3R, 4P  
1S, 2P, 3Q, 4R 
Question 29 
{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 
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 
{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 
always regular  
never regular  
always a deterministic contextfree language  
always a contextfree language

Question 33 
{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 
((a + b)* b)*  
{a^{m}b^{n}  m ≤ n}  
{a^{m}b^{n}  m = n}  
a* b* 
Option C&D:
→ abb accepted by given grammar but option C & D are not accepting.
Question 35 
QRS  
PQS  
PQ'S'  
Q'S' 
Question 36 
XOR, AND  
XOR, XOR  
OR, OR  
OR, AND 
Majority means at least two inputs should be 1.
Whenever the majority of the variables have value 1, the output is 1.
The following combinations produce output 1.
110, 101, 111, and 011
The circuit has 3 inputs namely x, y and z with x as the selection line to MUX.
Consider Majority cases.
Case 1: x=1
x y z
1 1 0 When x is 1 then at least one of y and z should be 1. Then P is OR gate.
1 0 1
1 1 1
Case 2: x=0
0 1 1
When x is 0 both y and z should be 1. So Q is AND gate
Question 37 
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 
2Y and Y  
2Y and 2Y  
2Y and 0  
0 and Y 
⇒ 2Y and 0
Question 39 
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 
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 
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 
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 
{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 
{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 
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 
fdheg  
ecgdf  
dchfg  
fehdg 
∴ 110111100111010 = fdheg
Question 49 
#include <stdio.h> struct 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 
#include void 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 = %dn", 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 
#include int 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("%dn", 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 
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 
(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 
 Interchanging Wait (F) and Wait (S) in the Producer process
 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 
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 

 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);  E1; x_count = x_count  1;

 Each occurrence of x.signal is replaced with the following:
if (x_count > 0) { next_count = next_count + 1;  E2; P(next), next_count = next_count  1; }
 For correct implementation of the monitor, statements E1 and E2 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 
III and IV  
I and IV  
II and IV  
I, II and IV 
Question 60 
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 
<!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 
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 
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 
⌊i/2⌋  
⌈(i1)/2⌉  
⌈i/2⌉  
⌈i/2⌉  1 
Question 72 
O(n)  
O(log n)  
O(n log n)  
O(n log log n) 
Question 73 
⌊log_{2} i⌋  
⌈log_{2} (i + 1)⌉  
⌊log_{2} (i + 1)⌋  
⌈log_{2} i⌉ 
Question 74 
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 
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 
0.5  
0.75  
1.5  
2.0 
Question 77 
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 
10  
12  
14  
16 
Question 80 
Both I and IV  
Only I  
Only IV  
Both II and III 
Half (L), Suffix (L) and Prefix (L) are regular languages.
Question 81 
(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 
P1P2P4, 1 day  
P1P3P4, 1 day  
P1P3P4, 2 days  
P1P2P4, 2 days 
Question 83 
100 and 1000  
100 and 1200  
150 and 1200  
200 and 2000 
Question 84 
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 
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