GATE 2007IT
Question 1 
Suppose there are two coins. The first coin gives heads with probability 5/8 when tossed, while the second coin gives heads with probability 1/4. One of the two coins is picked up at random with equal probability and tossed. What is the probability of obtaining heads ?
7/8  
1/2  
7/16  
5/32 
The probability of obtaining heads
= (1/2)(5/8) + (1/2)(1/4)
= (5/16) + (1/8)
= 7/16
Question 2 
Let A be the What is the maximum value of x^{T}Ax where the maximum is taken over all x that are the unit eigenvectors of A?
5  
5+√5/2  
3  
5√5/2 
Question 3 
Consider a weighted undirected graph with positive edge weights and let uv be an edge in the graph. It is known that the shortest path from the source vertex s to u has weight 53 and the shortest path from s to v has weight 65. Which one of the following statements is always true?
weight (u, v) < 12  
weight (u, v) ≤ 12  
weight (u, v) > 12  
weight (u, v) ≥ 12 
weight (u,v) ≥ 12
Lets check other options,
A) If the weight (u,v) < 12
Minimum weight of (s,v)
= weight of (s,v) + weight of (u,v)
= 53 + (<12)
= less than 65, which is not possible because shortest path from s to v has weight 65.
Similarly, we can check for option (B) and (C).
Question 4 
In the Spiral model of software development, the primary determinant in selecting activities in each iteration is
Iteration size  
Cost  
Adopted process such as Rational Unified Process or Extreme Programming  
Risk 
Question 5 
Which of the following systems is a most likely candidate example of a pipe and filter architecture ?
Expert system  
DB repository  
Aircraft flight controller  
Signal processing 
Question 6 
A processor takes 12 cycles to complete an instruction I. The corresponding pipelined processor uses 6 stages with the execution times of 3, 2, 5, 4, 6 and 2 cycles respectively. What is the asymptotic speedup assuming that a very large number of instructions are to be executed?
1.83  
2  
3  
6 
For a nonpipelined processor each instruction takes 12 cycles.
So for n instructions total execution time be 12 × n = 12n
For a pipelined processor each instruction takes
max (3, 2, 5, 4, 6, 2) = 6
So for n instructions total execution time be,
(1×6 + (n1) × 1) × 6
= (6 + n  1) × 6
= (5 + n) × 6
= 30 + 6n
∴ Speedup = time without pipeline/time with pipeline = 12n/30+6n
So, if n is very large,
Question 7 
Which of the following input sequences for a crosscoupled RS flipflop realized with two NAND gates may lead to an oscillation?
11, 00  
01, 10  
10, 01  
00, 11 
So, 00 input cause indeterminate state which may lead to oscillation.
Question 8 
The following circuit implements a twoinput AND gate using two 21 multiplexers. What are the values of X_{1}, X_{2}, X_{3} ?
X1 = b, X2 = 0, X3 = a  
X1 = b, X2 = 1, X3 = b  
X1 = a, X2 = b, X3 = 1  
X1 = a, X2 = 0, X3 = b 
If we put
X1 = b
X2 = 0
X3 = a
Then we get,
F = ab
Question 9 
Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true ?
L (D) ⊂ L (G)  
L (D) ⊃ L (G)  
L (D) = L (G)  
L (D) is empty 
For example, by converting NFA to DFA language will not be changed.
Question 10 
Processes P1 and P2 use critical_flag in the following routine to achieve mutual exclusion. Assume that critical_flag is initialized to FALSE in the main program.
get_exclusive_access ( ) { if (critical _flag == FALSE) { critical_flag = TRUE ; critical_region () ; critical_flag = FALSE; } }
Consider the following statements. i. It is possible for both P1 and P2 to access critical_region concurrently. ii. This may lead to a deadlock.
Which of the following holds?
(i) is false and (ii) is true  
Both (i) and (ii) are false  
(i) is true and (ii) is false  
Both (i) and (ii) are true 
Question 11 
Let a memory have four free blocks of sizes 4k, 8k, 20k, 2k. These blocks are allocated following the bestfit strategy. The allocation requests are stored in a queue as shown below.
The time at which the request for J_{7} will be completed will be
16  
19  
20  
37 
At t = 8
At t = 10
At t = 11
J_{7} can be finished at t = 19.
Question 12 
The address sequence generated by tracing a particular program executing in a pure demand paging system with 100 bytes per page is
0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0410.Suppose that the memory can store only one page and if x is the address which causes a page fault then the bytes from addresses x to x + 99 are loaded on to the memory. How many page faults will occur?
0  
4  
7  
8 
0200  Page fault, address till 299 in memory
0430  Page fault, address till 529 in memory
0499  No page fault
0510  No page fault
0530  Page fault, address till 629 in memory
0560  No page fault.
0120  Page fault, address till 219 in memory
0220  Page fault, address till 319 in memory
0240  No page fault
0260  No page fault
0320  Page fault, address till 419 in memory
0410  No page fault
So, total page faults = 7.
Question 13 
Consider the following statements about the timeout value used in TCP.
(i) The timeout value is set to the RTT (Round Trip Time) measured during TCP connection establishment for the entire duration of the connection.
(ii) Appropriate RTT estimation algorithm is used to set the timeout value of a TCP connection.
(iii) Timeout value is set to twice the propagation delay from the sender to the receiver.
Which of the following choices hold?
(i) is false, but (ii) and (iii) are true  
(i) and (iii) are false, but (ii) is title  
(i) and (ii) are false, but (iii) is true  
(i), (ii) and (iii) are false 
The timeout value cannot be fixed for entire duration as it will turn timer to static timer, we need dynamic timer for timeout.
StatementII: It is True.
Basic algorithm, Jacobson's algorithm, Karl's modification; these three algorithms are to be appropriate to RTT estimation algorithm used to set timeout value dynamically.
StatementIII: It is False.
Because timeout value is set to twice the propagation delay in data link layer where hop to hop distance is known, not in TCP layer.
Question 14 
Consider a TCP connection in a state where there are no outstanding ACKs. The sender sends two segments back to back. The sequence numbers of the first and second segments are 230 and 290 respectively. The first segment was lost, but the second segment was received correctly by the receiver. Let X be the amount of data carried in the first segment (in bytes), and Y be the ACK number sent by the receiver. The values of X and Y (in that order) are
60 and 290  
230 and 291  
60 and 231  
60 and 230 
Question 15 
Consider the following two statements:
(i) A hash function (these are often used for computing digital signatures) is an injective function.
(ii) An encryption technique such as DES performs a permutation on the elements of its input alphabet.
Which one of the following options is valid for the above two statements?
Both are false  
Statement (i) is true and the other is false  
Statement (ii) is true and the other is false  
Both are true 
ii) It uses the PBox permutation.
StatementI is false, II is true.
Question 16 
The minimum positive integer p such that 3^{p} modulo 17 = 1 is
5  
8  
12  
16 
a^{p1 mod p = 1 Here, p = 17 So, p1 = 16 is the answer.}
Question 17 
Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute b^{n} mod m, 0≤b, n≤m?
O(log n)  
O(√n)  
O(n/log n)  
O(n) 
C_{1} = b^{n/2} × b^{n/2}
C_{2} = b^{n/4} × b^{n/4}
C_{3} = b^{n/8} × b^{n/8}
⋮
C_{k} = b^{2} × b^{2}
Recurrence relation T(n) = T(n/2) + O(1)
T(n) = O(log n)
Question 18 
A firewall is to be configured to allow hosts in a private network to freely open TCP connections and send packets on open connections. However, it will only allow external hosts to send packets on existing open TCP connections or connections that are being opened (by internal hosts) but not allow them to open TCP connections to hosts in the private network. To achieve this the minimum capability of the firewall should be that of
A combinational circuit  
A finite automaton  
A pushdown automaton with one stack  
A pushdown automaton with two stacks 
Turing machine can do everything as the normal computer can do, so firewall can be created by the TM.
Question 19 
Given below are HTML lines,
With reference to the HTML lines given above, consider the following statements.
(i) Clicking on the point <80, 75> does not have any effect.
(ii) The web browser can identify the area applicable to the mouseclick within the image and the subsequent action to be taken without additional responses from the web server.
(iii) The dots in the cgibin URL will be resolved by the web browser before it is sent to the web server.
(iv) The "fd.html" request when sent to the web server will result in a GET request.
Exactly how many of the statements given above are correct?
0  
1  
2  
3 
Question 20 
Consider the XML document fragment given below:
Consider the XPath expression: *[not (self)::TOC]
What would be the result of the given XPath expression when the current node is Book?
The Title and Content elements  
The Content and TOC elements  
The Title and TOC elements  
The Title, Content and TOC elements

Question 21 
Which one of these firstorder logic formula is valid?
∀x(P(x) ⇒ Q(x)) ⇒ (∀xP(x) ⇒ ∀xQ(x))  
∃x(P(x) ∨ Q(x)) ⇒ (∃xP(x) ⇒ ∃xQ(x))  
∃x(P(x) ∧ Q(x)) (∃xP(x) ∧ ∃xQ(x))  
∀x∃y P(x, y) ⇒ ∃y∀x P(x, y) 
RHS = if P(x) holds for all x, then Q(x) holds for all x
LHS ⇒ RHS (✔)
RHS ⇒ LHS (️×)
Question 22 
The trapezoidal method is used to evaluate the numerical value of . Consider the following values for the step size h.
 (i) 10^{2}
(ii) 10^{3}
(iii) 10^{4}
(iv) 10^{5}
For which of these values of the step size h, is the computed value guaranteed to be correct to seven decimal places. Assume that there are no roundoff errors in the computation.
(iv) only  
(iii) and (iv) only  
(ii), (iii) and (iv) only  
(i), (ii), (iii) and (iv) 
Question 23 
A partial order P is defined on the set of natural numbers as follows. Here x/y denotes integer division.
(i) (0, 0) ∊ P.
(ii) (a, b) ∊ P if and only if a % 10 ≤ b % 10 and (a/10, b/10) ∊ P.
Consider the following ordered pairs:
(i) (101, 22)
(ii) (22, 101)
(iii) (145, 265)
(iv) (0, 153)
Which of these ordered pairs of natural numbers are contained in P?
(i) and (iii)  
(ii) and (iv)  
(i) and (iv)  
(iii) and (iv) 
The given condition can be satisfied by
(iii) (145, 265) → 5 ≤ 5, 4 < 6 and 1< 2
(iv) (0, 153) → 0 < 3
Question 24 
A depthfirst search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the dfs call to the vertex u terminates. Which of the following statements is always true for all edges (u, v) in the graph?
d[u] < d[v]  
d[u] < f[v]  
f[u] < f[v]  
f[u] > f[v] 
Option A:
d[u]
d[u]
f[u]
Question 25 
What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?
1  
2  
3  
n 
→ If we create a different spanning tree by removing one edge at a time.
→ For cycle required 3 minimum edges. So there is at least 3 spanning trees in such a graph.
Question 26 
Consider n jobs J_{1}, J_{2},......J_{n} such that job J_{i} has execution time t_{i} and a nonnegative integer weight w_{i}. The weighted mean completion time of the jobs is defined to be , where T_{i} is the completion time of job J_{i}. Assuming that there is only one processor available, in what order must the jobs be executed in order to minimize the weighted mean completion time of the jobs?
Nondecreasing order of t_{i}  
Nonincreasing order of w_{i}  
Nonincreasing order of w_{i}t_{i}  
Noneincreasing order of w_{i}/t_{i} 
So answer is the nonincreasing order of w_{i}/t_{i}.
Question 27 
The function f is defined as follows:
int f (int n) { if (n <= 1) return 1; else if (n % 2 == 0) return f(n/2); else return f(3n  1); }Assuming that arbitrarily large integers can be passed as a parameter to the function, consider the following statements.
(i) The function f terminates for finitely many different values of n ≥ 1.
(ii) The function f terminates for infinitely many different values of n ≥ 1.
(iii) The function f does not terminate for finitely many different values of n ≥ 1.
(iv) The function f does not terminate for infinitely many different values of n ≥ 1.
Which one of the following options is true of the above?
(i) and (iii)  
(i) and (iv)  
(ii) and (iii)  
(ii) and (iv) 
→ Let n=3, then it is terminated in 2^{nd} iteration.
→ Let n=5, then sequence is 5→14→7→20→10 and it will repeat.
→ Any number with factor 5 and 2 leads to infinite recursion.
So, (iv) is True and (iii) is False.
Question 28 
Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5.
5  
6  
7  
10 
Probability of collision for each entry = 1/20
After inserting X values then probability becomes 1/2
i.e., (1/20)X = 1/2
X = b
Question 29 
When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?
35  
64  
128  
5040 
Smaller values 90, 80 and 70 are visited in order
i.e., 7!/(4!3!) = 35
Question 30 
Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:
(i) isEmpty (Q) — returns true if the queue is empty, false otherwise.
(ii) delete (Q) — deletes the element at the front of the queue and returns its value.
(iii) insert (Q, i) — inserts the integer i at the rear of the queue.
Consider the following function:
void f (queue Q) { int i ; if (!isEmpty(Q)) { i = delete(Q); f(Q); insert(Q, i); } }What operation is performed by the above function f?
Leaves the queue Q unchanged  
Reverses the order of the elements in the queue Q  
Deletes the element at the front of the queue Q and inserts it at the rear keeping the other elements in the same order  
Empties the queue Q 
Question 31 
Consider the C program given below:
#includeint main () { int sum = 0, maxsum = 0, i, n = 6; int a [] = {2, 2, 1, 3, 4, 2}; for (i = 0; i < n; i++) { if (i == 0  a [i] < 0  a [i] < a [i  1]) { if (sum > maxsum) maxsum = sum; sum = (a [i] > 0) ? a [i] : 0; } else sum += a [i]; } if (sum > maxsum) maxsum = sum ; printf ("%dn", maxsum); }
What is the value printed out when this program is executed?
9  
8  
7  
6 
Question 32 
Consider the following C program:
#include #define EOF 1 void push (int); /* push the argument on the stack */ int pop (void); /* pop the top of the stack */ void flagError (); int main () { int c, m, n, r; while ((c = getchar ()) != EOF) { if (isdigit (c) ) push (c); else if ((c == '+')  (c == '*')) { m = pop (); n = pop (); r = (c == '+') ? n + m : n*m; push (r); } else if (c != ' ') flagError (); } printf("% c", pop ()); }What is the output of the program for the following input?
5 2 * 3 3 2 + * +
15  
25  
30  
150 
push 2
pop 2
pop 5
5 * 2 = 10
push 10
push 3
push 3
push 2
pop 2
pop 3
3 + 2 = 5
push 5
pop 5
pop 3
3 * 5 = 15
push 15
pop 15
pop 10
10 + 15 = 25
push 25
Finally, pop 25 and print it.
Question 33 
Consider the program below in a hypothetical language which allows global variable and a choice of call by reference or call by value methods of parameter passing.
int i ; program main () { int j = 60; i = 50; call f(i,j); print i, j; } procedure f(x,y) { i = 100; x = 10; y = y + i ; }Which one of the following options represents the correct output of the program for the two parameter passing mechanisms?
Call by value : i = 70, j = 10; Call by reference : i = 60, j = 70  
Call by value : i = 50, j = 60; Call by reference : i = 50, j = 70  
Call by value : i = 10, j = 70; Call by reference : i = 100, j = 60  
Call by value : i = 100, j = 60; Call by reference : i = 10, j = 70 
'i' is a global variable. Then in main( ) a local variable 'j' as integer declared, i.e., j=60 and global variable 'i' is initialized to 50 by i=50.
Now procedure f called and values of 'i' and 'j' are passed to it, i.e., in f(i, j)→f(x, y).
Content of memory location of 'i' (here 50) is copied to memory location of x (which is different from i) and content of memory location of 'j' (here 60) is copied to memory location of y. Then in f(x, y) i=100 changes the global i to 100, x=10 changes the local x from 50 to 10 and y=y+i means y=60+100=160. Now, when return back to main, i & j will be 100 & 60 respectively.
Call by reference:
Now procedure f called and passed reference of i and j to it, i.e., in f(i,j)→f(x,y). x and y are pointing to same memory location of i and j respectively. So i=100 changes the global i to 100 and x=10 means as well as global i=10 (as the i being passed is the global variable and x and i share the same address).
y=y+i means y=60+10=70 and this changes the value of j also to as j and y have the same addresses. Now when return to main, i and j will be 10 and 70.
Question 34 
Consider the program below in a hypothetical programming language which allows global variables and a choice of static or dynamic scoping.
int i ; program main () { i = 10; call f(); } procedure f() { int i = 20; call g (); } procedure g () { print i; }Let x be the value printed under static scoping and y be the value printed under dynamic scoping. Then, x and y are
x = 10, y = 10  
x = 20, y = 10  
x = 10, y = 20  
x = 20, y = 20 
Question 35 
Early binding refers to a binding performed at compile time and late binding refers to a binding performed at execution time. Consider the following statements:
i. Static scope facilitates w1 bindings.
ii. Dynamic scope requires w2 bindings.
iii. Early bindings w3 execution efficiency.
iv. Late bindings w4 execution efficiency.
The right choices of wl, w2, w3 and w4 (in that order) are
Early, late, decrease, increase  
Late, early, increase, decrease  
Late, early, decrease, increase  
Early, late, increase, decrease 
Dynamic scoping requires late binding (during execution time).
Late binding decreases efficiency as this binding needs to be done at run time.
Question 36 
The floating point unit of a processor using a design D takes 2t cycles compared to t cycles taken by the fixed point unit. There are two more design suggestions D1 and D2. D1 uses 30% more cycles for fixed point unit but 30% less cycles for floating point unit as compared to design D. D2 uses 40% less cycles for fixed point unit but 10% more cycles for floating point unit as compared to design D. For a given program which has 80% fixed point operations and 20% floating point operations, which of the following ordering reflects the relative performances of three designs? (Di > Dj denotes that Di is faster than Dj)
D1 > D > D2  
D2 > D > D1  
D > D2 > D1  
D > D1 > D2 
D = 0.8 × t + 0.2 × 2t = 1.2t
D1 = 0.8 × 1.3t + 0.2 × 0.7 × 2t = 1.32t
D2 = 0.8 × 0.6t + 0.2 × 1.1 × 2t = 0.92t
⇒ D2 > D > D1
Question 37 
Consider a Direct Mapped Cache with 8 cache blocks (numbered 07). If the memory block requests are in the following order
3, 5, 2, 8, 0, 63, 9,16, 20, 17, 25, 18, 30, 24, 2, 63, 5, 82,17, 24.Which of the following memory blocks will not be in the cache at the end of the sequence?
3  
18  
20  
30 
So memory block 18 is not in the cache.
Question 38 
The following expression was to be realized using 2input AND and OR gates. However, during the fabrication all 2input AND gates were mistakenly substituted by 2input NAND gates.
(a.b).c + (a'.c).d + (b.c).d + a. dWhat is the function finally realized?
1  
a’ + b’ + c’ + d’  
a’ + b + c’ + d’  
a’ + b’ + c + d’ 
= ((ab)'c)' + ((a'c)'d)' + ((bc)'d)' + (ad)'
= ab + c' + a'c + d' + bc + d' + a' + d'
= ab + c' + a'c + bc + a' + d'
= ab + c' + bc + a' + d'
= b + c' + bc + a' + d'
= a' + b + c' + d'
Question 39 
Data forwarding techniques can be used to speed up the operation in presence of data dependencies. Consider the following replacements of LHS with RHS.
(i) R1→Loc, Loc→R2 ≡ R1→R2, R1→Loc (ii) R1→Loc, Loc→R2 ≡ R1→R2 (iii) R1→Loc, R2→Loc ≡ R1→Loc (iv) R1→Loc, R2→Loc ≡ R2→LocIn which of the following options, will the result of executing the RHS be the same as executing the LHS irrespective of the instructions that follow?
(i) and (iii)  
(i) and (iv)  
(ii) and (iii)  
(ii) and (iv)  
Only (i) 
(ii) Is false. Because R2 gets the correct data in both LHS and RHS, but Loc is not updated in RHS.
(iii) Is false. Because R2 is writing last in LHS, but not in RHS.
(iv) Is true. The first write to Loc in LHS is useless as it is overwritten by the next write.
Question 40 
What is the final value stored in the linear feedback shift register if the input is 101101?
0110  
1011  
1101  
1111 
Question 41 
Following table indicates the latencies of operations between the instruction producing the result and instruction using the result.
Consider the following code segment.
Load R1,Loc1; Load R1 from memory location Loc1 Load R2,Loc2; Load R2 from memory location Loc2 Add R1,R2,R1; Add R1 and R2 and save result in R1 Dec R2; Decrement R2 Dec R1; Decrement R1 Mpy R1,R2,R3; Multiply R1 and R2 and save result in R3 Store R3,Loc3; Store R3 in memory location Loc3What is the number of cycles needed to execute the above code segment assuming each instruction takes one cycle to execute?
7  
10  
13  
14 
If an instruction is in execution phase then any other instructions cannot be in the execution phase. So, atleast 7 clock cycles will be taken.
Now, it is given that between two instructions latency or delay should be there based on their operation.
(C012.25)_{H} – (10111001110.101)_{B} =
(135103.412)_{O}  
(564411.412)_{O}  
(564411.205)_{O}  
(135103.205)_{O} 
= 1100000000010010.00100101  0000010111001110.10100000
= 1011101001000011.10000101
= 1011101000011.100001010
= (135103.412)_{O}
Question 43 
An error correcting code has the following code words:
00000000, 00001111, 01010101, 10101010, 11110000.What is the maximum number of bit errors that can be corrected?
0  
1  
2  
3 
The no. of bits that can be corrected is
Question 44 
A hard disk system has the following parameters:
Number of tracks = 500
Number of sectors/track = 100
Number of bytes /sector = 500
Time taken by the head to move from one track to adjacent track = 1 ms
Rotation speed = 600 rpm.
What is the average time taken for transferring 250 bytes from the disk ?
300.5 ms  
255.5 ms  
255.0 ms  
300.0 ms 
For Avg. seek time:
Given that, time to move between successive tracks is 1ms.
Time to move from track1 to track1 = 0ms
Time to move from track1 to track2 = 1ms
Time to move from track1 to track3 = 2ms
⋮ Time to move from track1 to track500 = 499ms
∴ Avg. seek time = 0+1+2+...+499/500 = 249.5ms
Avg. rotational delay:
600 rotations in 60sec.
One rotation takes 60/600 s = 100ms ∴ Avg. rotational delay = 100/2 = 50ms
Data transfer time:
In one rotation, we can read data on one complete track
= 100 × 500 = 50,000B data is read in one complete rotation
One complete rotation takes 100ms.
100ms → 50,000B
250B → 100/50000 × 250 = 0.5ms
∴ Avg. time to transfer = 249.5 × 50 + 0.5 = 300ms
Question 45 
The line T in the following figure is permanently connected to the ground.
Which of the following inputs (X1 X2 X3 X4) will detect the fault?
0000  
0111  
1111  
None of these 
Since the problem is in the link T which is connected as input to NOR gate. So to check link T we have to make the output dependent on T by deactivating link M. So to deactivate link M, the output at M should be 0, as link M is input to NOR gate. So, to output at M as 0,
X1 = 1
X2 = 1
X3 = 1
X4 = 0
∴ None of the given option is correct.
Question 46 
The two grammars given below generate a language over the alphabet {x, y, z}
G1: S → xzxSzSyB B → yzyBzB G2: S → yzySzSxB B → yyS
Which one of the following choices describes the properties satisfied by the strings in these languages?
G1 : No y appears before any x G2 : Every x is followed by at least one y  
G1 : No y appears before any x G2 : No x appears before any y  
G1 : No y appears after any x G2 : Every x is followed by at least one y  
G1 : No y appears after any x G2 : Every y is followed by at least one x 
(x + z)* + (x + z)* y(y + z)*
Regular expression for G2:
(y + z + xy)*
Question 47 
Consider the following DFA in which s_{0} is the start state and s_{1}, s_{3} are the final states.
What language does this DFA recognize ?
All strings of x and y  
All strings of x and y which have either even number of x and even number of y or odd number or x and odd number of y  
All strings of x and y which have equal number of x and y  
All strings of x and y with either even number of x and odd number of y or odd number of x and even number of y 
Question 48 
Consider the grammar given below
S → x B  y A A → x  x S  y A A B → y  y S  y B B
Consider the following strings.
(i) xxyyx (ii) xxyyxy (iii) xyxy (iv) yxxy (v) yxx (vi) xyx
Which of the above strings are generated by the grammar ?
(i), (ii), and (iii)  
(ii), (v), and (vi)  
(ii), (iii), and (iv)  
(i), (iii), and (iv) 
S → xB
S → xxBB
S → xxyB
S → xxyyS
S → xxyyxB
S → xxyyxy
(iii) xyxy
S → xB
S → xyS
S → xyxB
S → xyxy
(iv) yxxy
S → yA
S → yxS
S → yxxB
S → yxxy
Question 49 
Consider the following grammars. Names representing terminals have been specified in capital letters.
G_{1}: stmnt → WHILE (expr) stmnt stmnt → OTHER expr → ID G_{2}: WHILE (expr) stmnt stmnt → OTHER expr → expr + expr expr → expr * expr expr → ID
Which one of the following statements is true?
G_{1} is contextfree but not regular and G_{2} is regular  
G_{2} is contextfree but not regular and G_{1} is regular  
Both G_{1} and G_{2} are regular  
Both G_{1} and G_{2} are contextfree but neither of them is regular 
Similarly, in right linear grammar, nonterminal appears at the right most position.
Here we can write a right linear grammar for G_{1} as
S → w(E
E → id)S
S → o
(wwhile, oother)
So, L(G_{1}) is regular.
Now for G_{2} also we can write a right linear grammar:
S → w(E
E → id)S
E → id+E
E → id*E
S → o
making its language regular.
So, both G_{1} and G_{2} have an equivalent regular grammar. But given in the question both these grammars are neither right linear nor left linear and hence not a regular grammar. So, (D) must be the answer.
Question 50 
Consider the following finite automata P and Q over the alphabet {a, b, c}. The start states are indicated by a double arrow and final states are indicated by a double circle. Let the languages recognized by them be denoted by L(P) and L(Q) respectively.
The automation which recognizes the language L(P) ∩ L(Q) is:
Question 51 
The following table shoes the time between failures for a software system
The reliability of the system for one hour of operation assuming an exponential model is
0.45  
0.63  
0.84  
0.95 
MIBF = (6+4+8+5+6)/5 = 29/5
The probability or reliability that the product will work for a defined period of time without failure is given by
R(T) = exp(T/MTBF); T = 1 hour
R(1) = e^{(1/(29/5))} = e^{(5/29)} = 0.84
Question 52 
Given the following algorithm for sorting an array X of N numbers:
SUBROUTINE SORT(X,N) IF(N < 2) RETURN FOR(i=2 TO N INCREMENT BY 1) FOR(j=1 TO i INCREMENT BY 1) IF (X[i] > X[j]) CONTINUE TEMP X[i] X[i] = X[j] X[j] = TEMP END FOR END FOR END SUBROUTINE
A good approximation of Halstead's estimated program length is
20  
50  
80  
110 
Question 53 
In the simplified flowchart given below, the shaded boxes represent code that is executed during a test case.
The Branch coverage is
3/4  
2/3  
1/2  
3/8 
Question 54 
Consider the CPM activity chart where an arc connecting two milestones is labeled with a task identifier and the time taken in days. For example in order to go from A to B, task T1 takes 180 days. A dashed line depicts an additional dependency that is equivalent to a zero time task.
The set of activities that lie on the critical path are
T1, T2, T8, T10  
T1, T3, T8, T10  
T1, T2, T3, T4, T5, T6, T7, T8, T9, T10  
T1, T4, T5, T7, T8, T10 
Question 55 
Consider the following pseudocode:
IF ((A > B) AND (C > D)) THEN A = A + 1 B = B + 1 ENDIF
The cyclomatic complexity of the pseudocode is
2  
3  
4  
5 
Question 56 
Synchronization in the classical readers and writers problem can be achieved through use of semaphores. In the following incomplete code for readerswriters problem, two binary semaphores mutex and wrt are used to obtain synchronization
wait (wrt) writing is performed signal (wrt) wait (mutex) readcount = readcount + 1 if readcount = 1 then S1 S2 reading is performed S3 readcount = readcount  1 if readcount = 0 then S4 signal (mutex)
The values of S1, S2, S3, S4, (in that order) are
signal (mutex), wait (wrt), signal (wrt), wait (mutex)  
signal (wrt), signal (mutex), wait (mutex), wait (wrt)  
wait (wrt), signal (mutex), wait (mutex), signal (wrt)  
signal (mutex), wait (mutex), signal (mutex), wait (mutex) 
S2: After readcount has been updated, UP on mutex.
S3: DOWN on mutex to update readcount.
S4: If readcount is zero, i.e., no reader is reading, UP on wrt to allow some writer to write.
Question 57 
In a multiuser operating system on an average, 20 requests are made to use a particular resource per hour. The arrival of requests follows a Poisson distribution. The probability that either one, three or five requests are made in 45 minutes is given by :
6.9 × 10^{6} × e^{20}  
1.02 × 10^{6} × e^{20}  
6.9 × 10^{3} × e^{20}  
1.02 × 10^{3} × e^{20} 
So, λ=15
Question 58 
A demand paging system takes 100 time units to service a page fault and 300 time units to replace a dirty page. Memory access time is 1 time unit. The probability of a page fault is p. In case of a page fault, the probability of page being dirty is also p. It is observed that the average access time is 3 time units. Then the value of p is
0.194  
0.233  
0.514  
0.981  
0.0194 
(if the page is not dirty)
Page fault service time = 300
(if there is dirty page)
Probability of page fault = P
Probability pf page being dirty = P
So, total page fault service time
= P(300) + (1  P)100
= 300P + 100  100P
= 300P + 100
Now given,
Effective average memory access time = 3
So,
3 = m + P × total page fault service time
= 1 + P(200P + 100)
= 1+ 200P^{2} + 100P
⇒ 200P^{2} + 100P  2 = 0
⇒ P = 0.0194
Question 59 
The contents of the text file t1.txt containing four lines are as follows:
a1 b1 a2 b2 a3 b2 a4 b1
The contents of the text file t2.txt containing five lines are as follows:
a1 c1 a2 c2 a3 c3 a4 c3 a5 c4
Consider the following Bourne shell script:
awk  F''' {Print S1, S2} ' t1.txt  while read a b ; do awk v aV = Sa  v bV = Sb  F'' 'aV = = S1 (print aV, bV, S2 )'t2.txt done
Which one of the following strings will NOT be present in the output generated when the above script in run? (Note that the given strings may be substrings of a printed line.)
"b1 c1"  
"b2 c3"  
"b1 c2"  
"b1 c3" 
Question 60 
For the network given in the figure below, the routing tables of the four nodes A, E, D and G are shown. Suppose that F has estimated its delay to its neighbors, A, E, D and G as 8, 10, 12 and 6 msecs respectively and updates its routing table using distance vector routing technique.
Using distance vector routing protocol, F→D→B yeilds distance as 20 which eliminates option (B) and (D).
Question 61 
In the waveform (a) given below, a bit stream is encoded by Manchester encoding scheme. The same bit stream is encoded in a different coding scheme in wave form (b). The bit stream and the coding scheme are
1000010111 and Differential Manchester respectively  
0111101000 and Differential Manchester respectively  
1000010111 and Integral Manchester respectively  
0111101000 and Integral Manchester respectively

As per IEEE (B) is correct.
As per GE Thomas (A) is correct.
As we usually follow IEEE thus (B) is correct.
Question 62 
Let us consider a statistical time division multiplexing of packets. The number of sources is 10. In a time unit, a source transmits a packet of 1000 bits. The number of sources sending data for the first 20 time units is 6, 9, 3, 7, 2, 2, 2, 3, 4, 6, 1, 10, 7, 5, 8, 3, 6, 2, 9, 5 respectively. The output capacity of multiplexer is 5000 bits per time unit. Then the average number of backlogged of packets per time unit during the given period is
5  
4.45  
3.45  
0 
If the no. of packets transmitted is larger than 5 then the extra packets are backlogged. This means gets added to the next number and further backlog is calculated.
Average no. of backlogged packets = 89/20 = 4.45
Question 63 
A group of 15 routers are interconnected in a centralized complete binary tree with a router at each tree node. Router j communicates with router j by sending a message to the root of the tree. The root then sends the message back down to router j. The mean number of hops per message, assuming all possible router pairs are equally likely is
3  
4.26  
4.53  
5.26 
= (3×8) + (2×4) + (1×2) + (0×1)/15
= 2.267
So, Total hops = 2×2.267 = 4.53
Question 64 
A broadcast channel has 10 nodes and total capacity of 10 Mbps. It uses polling for medium access. Once a node finishes transmission, there is a polling delay of 80 μs to poll the next node. Whenever a node is polled, it is allowed to transmit a maximum of 1000 bytes. The maximum throughput of the broadcast channel is
1 Mbps  
100/11 Mbps  
10 Mbps  
100 Mbps 
(T_{t}) = 1000bytes/10×10^{6}bits/sec = 800μs
Polling delay = 80 μs
Efficiency = 800/800+80 = 800/880 = 10/11
Maximum throughput is
= 10/11 × 10 Mbps
= 100/11 Mbps
Question 65 
Consider a selection of the form σ_{A≤100}(r), where r is a relation with 1000 tuples. Assume that the attribute values for A among the tuples are uniformly distributed in the interval [0, 500]. Which one of the following options is the best estimate of the number of tuples returned by the given selection query ?
50  
100  
150  
200 
Values for A among the tuples are uniformly distributed in the interval [0, 500]. This can be split to 5 mutually exclusive and exhaustive intervals of same width of 100 ([0100], [101200], [201300], [301400], [401500], 0 makes the first interval larger  this must be type in this question) and we can assume all of them have same number of values due to uniform distribution. So no. of tuples with A value in first interval should be,
Total no. of tuples/5 = 1000/5 = 200
Question 66 
Consider the following two transactions: T_{1} and T_{2}.
T_{1}: read(A); read(B); if A=0 then B ← B+1; write(B); T_{2}: read(B); read(A); if B≠0 then A ← A1; write(A);Which of the following schemes, using shared and exclusive locks, satisfy the requirements for strict two phase locking for the above transactions?
i) Exclusive locks should be released after the commit.
ii) No locking can be done after the first unlock.
(A) Wrong because to write x you need Exclusive Lock.
(B) Wrong because violating the 1^{st} requirement.
(C) Correct.
(D) Wrong because violating the 1^{st} requirement.
Question 67 
Consider the following implications relating to functional and multivalued dependencies given below, which may or may not be correct.
(i) If A ↠ B and A ↠ C then A → BC
(ii) If A → B and A → C then A ↠ BC
(iii) If A ↠ BC and A → B then A → C
(iv) If A → BC and A → B then A ↠ C
Exactly how many of the above implications are valid?
0  
1  
2  
3 
if A→B then A→→B holds but reverse is not true.
So,
(i) False.
(ii) True.
(iii) False.
(iv) True.
Question 68 
Consider the following relation schemas:
bSchema = (bname, bcity, assets)
aSchema = (anum, bname, bal)
dSchema = (cname, anumber)
Let branch, account and depositor be respectively instances of the above schemas. Assume that account and depositor relations are much bigger than the branch relation.
Consider the following query:
П_{cname} (σ_{bcity = "Agra" ⋀ bal < 0} (branch ⋈ (account ⋈ depositor)
Which one of the following queries is the most efficient version of the above query?
П_{cname} (σ_{bal < 0} (σ_{bcity = “Agra”} branch ⋈ account) ⋈ depositor)  
П_{cname} (σ_{bcity = “Agra”}branch ⋈ (σ_{bal < 0} account ⋈ depositor))  
П_{cname} (σ_{bcity = “Agra”} branch ⋈ σ_{bcity = “Agra” ⋀ bal < 0} account) ⋈ depositor)  
П_{cname} (σ_{bcity = “Agra” ⋀ bal < 0} account ⋈ depositor)) 
Options (C) and (D) are invalid as there is no bcity column in aschema.
Question 69 
Consider the following clauses:
(i) Not inherently suitable for client authentication.
(ii) Not a state sensitive protocol.
(iii) Must be operated with more than one server.
(iv) Suitable for structured message organization.
(v) May need two ports on the serve side for proper operation.
The option that has the maximum number of correct matches is
IMAP(i), FTP(ii), HTTP(iii), DNS(iv), POP3(v)  
FTP(i), POP3(ii), SMTP(iii), HTTP(iv), IMAP(v)  
POP3(i), SMTP(ii), DNS(iii), IMAP(iv), HTTP(v)  
SMTP(i), HTTP(ii), IMAP(iii), DNS(iv), FTP(v) 
(v) FTP needs two ports, 20 for data and 21 for control.
Hence, only (D) matches.
Question 70 
Your are given the following four bytes :
10100011 00110111 11101001 10101011Which of the following are substrings of the base 64 encoding of the above four bytes?
zdp  
fpq  
qwA  
oze 
10100011 00110111 11101001 10101011
So, in total we have 32 bits. And for base 64 we need 6 digits of binary no. to represent one digit of base 64 no.
So lets padd 4 bits on RHS, so that total digits will become 36 and we can separate then as group of 6 digits each.
Now, the longest substring will be from checking option is 'fpq'.
Question 71 
Consider the regular expression
R = (a + b)* (aa + bb) (a + b)*Which of the following nondeterministic finite automata recognizes the language defined by the regular expression R? Edges labeled λ denote transitions on the empty string.
But option (B), (C), (D) accepts aba, which do not contain aa or bb as substring.
Hence, (A) is correct.
Question 72 
Consider the regular expression
R = (a + b)* (aa + bb) (a + b)*Which deterministic finite automaton accepts the language represented by the regular expression R ?
(C) It is not accepting 'abb' which is in language.
(D) It is not accepting 'aa' and 'bb' which is in language.
Question 73 
Consider the regular expression
R = (a + b)* (aa + bb) (a + b)*Which one of the regular expressions given below defines the same language as defined by the regular expression R?
(a(ba)* + b(ab)*)(a + b)^{+}  
(a(ba)* + b(ab)*)*(a + b)*  
(a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)*  
(a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)^{+} 
Having NFA:
Equivalent DFA:
Question 74 
Consider a token ring topology with N stations (numbered 1 to N) running token ring protocol where the stations are equally spaced. When a station gets the token it is allowed to send one frame of fixed size. Ring latency is t_{p}, while the transmission time of a frame is t_{t}. All other latencies can be neglected.
The maximum utilization of the token ring when t_{t} = 3 ms, t_{p} = 5 ms, N = 10 is
0.545  
0.6  
0.857  
0.961 
Question 75 
Consider a token ring topology with N stations (numbered 1 to N) running token ring protocol where the stations are equally spaced. When a station gets the token it is allowed to send one frame of fixed size. Ring latency is t_{p}, while the transmission time of a frame is t_{t}. All other latencies can be neglected.
The maximum utilization of the token ring when t_{t} = 5 ms, t_{p} = 3 ms, N = 15 is:
0.545  
0.655  
0.9375  
0.961 
Question 76 
Consider the sequence <x_{n}>, n>= 0 defined by the recurrence relation x_{n + 1} = c . x_{n}^{2} 2, where c > 0.
Suppose there exists a nonempty, open interval (a, b) such that for all x_{0} satisfying a < x_{0} < b, the sequence converges to a limit. The sequence converges to the value?
2  
Then,
x_{1} = c ⋅ (x_{0})^{2}  2 = 1 ⋅ (1)^{2}  2 = 1
x_{2} = c ⋅ (x_{1})^{2}  2 = 1 ⋅ (1)^{2}  2 = 1
So, the value converges to 1, which is equal to
Exactly, only (B) is answer. As all the term of x converges to 1.
Question 77 
Consider the sequence <x_{n}>, n>= 0 defined by the recurrence relation x_{n + 1} = c. x_{n}^{2} 2, where c > 0.
For which of the following values of c, does there exist a nonempty open interval (a,b) such that the sequence x_{n}, converges for all x_{0} satisfying a < x_{0}
 (i) 0.25
(ii) 0.35
(iii) 0.45
(iv) 0.5
(i) Only  
(i) and (ii) only  
(i), (ii) and (iii) only  
(i), (ii), (iii) and (iv) 
From the recurrence we should have c(x_{n})^{2}  x_{n}  2 < 0
For all the above values of c we have above equation as negative.
Question 78 
Consider the following expression
ad' + (ac)' + bc'dWhich of the following Karnaugh Maps correctly represents the expression?
ad' + a'c' + bc'd
Hence, option (A) matches.
Question 79 
Consider the following expression
ad' + (ac)' + bc'dWhich of the following expressions does not correspond to the Karnaugh Map obtained for the above expression?
c’d’+ ad’ + abc’ + (ac)’d  
(ac)’ + c’d’ + ad’ + abc’d  
(ac)’ + ad’ + abc’ + c’d  
b’c’d’ + acd’ + (ac)’ + abc’ 
a'c' + ad' + abc' + c'd
Not equivalent to the Kmap, we get in previous question.
Question 80 
Let P_{1}, P_{2},..... , P_{n} be n points in the xyplane such that no three of them are collinear. For every pair of points P_{i} and P_{j}, let L_{ij} be the line passing through them. Let Lab be the line with the steepest gradient amongst all n(n 1)/2 lines.
Which one of the following properties should necessarily be satisfied?
P_{a} and P_{b} are adjacent to each other with respect to their xcoordinate  
Either P_{a} or P_{b} has the largest or the smallest ycoordinate among all the points  
The difference between xcoordinates P_{a} and P_{b} is minimum  
None of the above 
Question 81 
Let P_{1},P_{2},…,P_{n} be n points in the xyplane such that no three of them are collinear. For every pair of points P_{i} and P_{j}, let L_{ij} be the line passing through them. Let Lab be the line with the steepest gradient among all n(n−1)/2 lines.
The time complexity of the best algorithm for finding P_{a} and P_{b} is
Θ(n)  
Θ(nlogn)  
Θ(nlog^{2}n)  
Θ(n^{2}) 
For gradient to be maximum x_{2}x_{1} should be minimum. So, sort the points (in Θ(n logn) time) according to n coordinate and find the minimum difference between them (in Θ(n) time).
∴ Complexity = Θ(n logn + n) = Θ(n logn)
Question 82 
The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. The head is initially positioned at truck number 180.
Which of the request sets will cause the head to change its direction after servicing every request assuming that the head does not change direction if there is a tie in SSTF and all the requests arrive before the servicing starts?
11, 139, 170, 178, 181, 184, 201, 265  
10, 138, 170, 178, 181, 185, 201, 265  
10, 139, 169, 178, 181, 184, 201, 265  
10, 138, 170, 178, 181, 185, 200, 265 
Hence, correct option is (B).
Question 83 
The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. The head is initially positioned at track number 180.
What is the maximum cardinality of the request set, so that the head changes its direction after servicing every request if the total number of tracks are 2048 and the head can start from any track?
9  
10  
11  
12 
1) The alternating direction with SSTF policy.
2) Maximize the no. of requests.
The first condition can be satisfied by not having two requests in the equal distance from the current location. As shown below, we must not have request located in the circle marked positions.
Now to maximize the no. of request we need the requests to be located as compact as possible, which can be done by just placing the request in the next position after the circle marked position in particular direction (the direction in which the head need to move).
Now to satisfy the 1^{st} criteria:
Seek length sequence for maximum cardinality and alternating head movements:
→ 1, 3, 7, 15, ...
→ or, 2^{1}1, 2^{2}1, 2^{3}1, 2^{4}1, ...
→ We have 2048 tracks so, maximum swing (seek length) can be 2047.
→ Which corresponds to a seek length of 2^{11}1 in the 11^{th} service.
Question 84 
Consider the B^{+} tree in the adjoining figure, where each node has atmost two keys and three links.
Keys K15 and then K25 are inserted into this tree in that order. Exactly how many of the following nodes (disregarding the links) will be present in the tree after the two insertions?
1  
2  
3  
4 
After inserting K15 we get,
Now, we insert K25, which gives
So, we see in the final tree only (K20, K25) is present. Hence, 1 (Answer).
Question 85 
Consider the B^{+} tree in the adjoining figure, where each node has atmost two keys and three links.
Now the key K50 is deleted from the 8 tree resulting after the two insertions made earlier. Consider the following statements about the B tree resulting after this deletion.
(i) The height of the tree remains the same.
(ii) The node (disregarding the links) is present in the tree.
(iii) The root node remains unchanged (disregarding the links).
Which one of the following options is true?
Statements (i) and (ii) are true  
Statements (ii) and (iii) are true  
Statements (iii) and (i) are true  
All the statements are false 
Now after deleting 50 we get B^{+} tree as
Hence, correct statement is only (i) & (ii).