GATE 2003
Question 1 
Consider the following C function.
float f(float x, int y) { float p, s; int i; for (s=1, p=1, i=1; i < y; i ++) { p*= x/i; s+=p; } return s; }
For large values of y, the return value of the function f best approximates
X^{y}  
e^{x}  
ln(1+x)  
X^{x} 
S = S+P
Iteration 1:
P=1; i=1; S=1
P=x
S = 1+x
Iteration 2:
P=x; S = 1+x; i=2
P = x * x/2 = x^{2}/2
Iteration 3:
P = x^{2}/2; S = 1+x+x^{2}/2; i=3
P = (x^{2}/2)(x/3) = x^{3}/6
S = 1 + x + x^{2}/2 + x^{3}/6
Continue upto n
Then f( ) returns:
S = 1 + x/1 + x^{2}/2⋅1 + x^{3}/3⋅2 + ...
= 1 + x/1! + x^{2}/2! + x^{3}/3! + ... + x^{n}/n!
= e^{x}
Question 2 
Assume the following C variable declaration
int *A [10], B[10][10];
Of the following expressions
I. A[2] II. A[2][3] III. B[1] IV. B[2][3]
which will not give compiletime errors if used as left hand sides of assignment statements in a C program?
I, II, and IV only  
II, III, and IV only  
II and IV only  
IV only 
ii) A[2][3] This results an integer, no error will come.
iii) B[1] is a base address of an array. This will not be changed it will result a compile time error.
iv) B[2][3] This also results an integer. No error will come.
Question 3 
Let P(E) denote the probability of the event E. Given P(A) = 1, P(B) = 1/2, the values of P(AB) and P(BA) respectively are
1/4, 1/2  
1/2, 1/4  
1/2, 1  
1, 1/2 
P(A/B) = P(A∩B)/P(B)
= P(A)⋅P(B)/P(B) (consider P(A), P(B) are two independent events)
= 1
P(B/A) = P(B∩A)/P(A)
= P(B)⋅P(A)/P(A)
= 1/2
Question 4 
Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, B and C are there such that (i) each is sorted in ascending order, (ii) B has 5 and C has 3 elements, and (iii) the result of merging B and C gives A?
2  
30  
56  
256 
→ If we are pick 3 elements from 8 sequence integers then remaining 5 elements are already in ascending order. After merging these elements then it gives A.
→ No. of possibilities of choosing 8 elements from total of 8 = ^{8}C_{3}
= 8!/3!5!
= 8 * 7
= 56
Question 5 
n couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is
i) Both husband and wife comes
ii) Only wife comes
iii) Both are not come
The no. of different gatherings possible at party is
= 3 * 3 * 3 * 3 * ... n times
= 3^{n}
Question 6 
Let T(n) be the number of different binary search trees on n distinct elements. Then , where x is
n – k + 1  
n – k  
n – k – 1  
n – k – 2 
Question 7 
Consider the set ∑* of all strings over the alphabet ∑ = {0, 1}. ∑* with the concatenation operator for strings
does not form a group  
forms a noncommutative group  
does not have a right identity element  
forms a group if the empty string is removed from Σ*

→ To perform concatenation with the given set can result a Monoid and it follows the property of closure, associativity and consists of identity element.
Question 8 
Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between
k and n  
k – 1 and k + 1  
k – 1 and n – 1  
k + 1 and n – k 
If a vertex is removed then it results that all the components are also be disconnected. So removal can create (n1) components.
Question 9 
Assuming all numbers are in 2's complement representation, which of the following numbers is divisible by 11111011?
11100111  
11100100  
11010111  
11011011 
MSB bit is '1' then all numbers are negative
1's complement = 00000100
2's complement = 00000100 + 00000001 = 00000101 = 5
(A) 11100111  (25)_{10}
(B) 11100100  (28)_{10 (C) 11010111  (41)10 (D) 11011011  (37)10 Answer: Option A (25 is divisible by 5)}
Question 10 
For a pipelined CPU with a single ALU, consider the following situations
I. The j + 1st instruction uses the result of the jth instruction as an operand II. The execution of a conditional jump instruction III. The jth and j + 1st instructions require the ALU at the same time
Which of the above can cause a hazard?
I and II only  
II and III only  
III only  
All the three 
II is belongs to the Control hazard.
III is belongs to the Structural hazard.
→ Hazards are the problems with the instruction pipeline in CPU micro architectures.
Question 11 
Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is
Θ (1)  
Θ (log n)  
Θ (n)  
Θ (n^{2}) 
The total time is n+knk = Θ(n)
Question 12 
Ram and Shyam have been asked to show that a certain problem Π is NPcomplete. Ram shows a polynomial time reduction from the 3SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3SAT. Which of the following can be inferred from these reductions?
Π is NPhard but not NPcomplete
 
Π is in NP, but is not NPcomplete
 
Π is NPcomplete  
Π is neither NPhard, nor in NP

Question 13 
Nobody knows yet if P = NP. Consider the language L defined as follows:
Which of the following statements is true?
L is recursive  
L is recursively enumerable but not recursive  
L is not recursively enumerable  
Whether L is recursive or not will be known after we find out if P = NP 
P = NP (or) P != NP
→ If P=NP then L=(0+1)* which is regular, then it is recursive.
→ If P!=NP then L becomes ɸ which is also regular, then it is recursive.
So, finally L is recursive.
Question 14 
The regular expression 0*(10*)* denotes the same set as
(1*0)*1*  
0+(0+10)*  
(0+1)*10(0+1)*  
None of the above 
Option (B) and (C) doesn't generate 11.
Question 15 
If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?
L is necessarily finite
 
L is regular but not necessarily finite  
L is context free but not necessarily regular  
L is recursive but not necessarily context free 
The give 'L' is recursive but not necessarily context free.
Question 16 
Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
Removing left recursion alone  
Factoring the grammar alone  
Removing left recursion and factoring the grammar  
None of the above 
To convert an arbitrary CFG to an LL(1) grammar we need to remove the left recursion and as well as left factoring without that we cannot convert.
Question 17 
Assume that the SLR parser for a grammar G has n_{1} states and the LALR parser for G has n_{2} states. The relationship between n_{1} and n_{2} is:
n_{1} is necessarily less than n_{2}  
n_{1} is necessarily equal to n_{2}
 
n_{1} is necessarily greater than n_{2}
 
None of the above 
Question 18 
In a bottomup evaluation of a syntax directed definition, inherited attributes can
always be evaluated  
be evaluated only if the definition is Lattributed  
be evaluated only if the definition has synthesized attributes  
never be evaluated 
LAttributed definitions are a class of syntax directed definitions whose attributes can be evaluated by a single traversal of the parsetree.
Question 19 
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the inorder traversal sequence of the resultant tree?
7 5 1 0 3 2 4 6 8 9  
0 2 4 3 1 6 5 9 8 7  
0 1 2 3 4 5 6 7 8 9  
9 8 6 4 2 3 0 1 5 7 
Inorder: 0 1 2 3 4 5 6 7 8 9
Question 20 
Consider the following three claims
I. (n + k)^{m} = Θ(n^{m}), where k and m are constants II. 2^{n+1} = O(2^{n}) III. 2^{2n+1} = O(2^{n})
Which of these claims are correct?
I and II
 
I and III  
II and III  
I, II, and III 
Which is true by considering leading ordered term present in polynomial expression.
II) 2^{n+1} = Θ(n^{m}) → True
2^{n}×2^{n} can't be written as Θ(2^{n})
So, this is False.
Question 21 
Consider the following graph
Among the following sequences:
(I) a b e g h f (II) a b f e h g (III) a b f h g e (IV) a f g h b e
Which are depth first traversals of the above graph?
I, II and IV only  
I and IV only  
II, III and IV only  
I, III and IV only 
II) a → b → f → e (✖️)
III) a → b → f → h → g → e (✔️)
IV) a → f → g → h → b → e (✔️)
Question 22 
The usual Θ(n^{2}) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will
remain Θ(n^{2})  
become Θ(n (log n)^{2})  
become Θ(n log n)  
become Θ(n) 
Instead, linear search use binary search then (log n) will be the worst case time complexity of binary search and performing n swaps to place an element in right position for the corresponding n elements
i.e., n×(logn+n)
Θ((n×logn)+n^{2})
Θ(n^{2})
Remains same.
Question 23 
In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time
Θ(n log n)  
Θ(n)  
Θ(log n)  
Θ(1) 
1 + 2 + 4 + 6 + 8 + 16 + 32
Which is constant then we can find the 7^{th} smallest element in Θ(1) time.
Question 24 
Which of the following statements is FALSE?
In statically typed languages, each variable in a program has a fixed type  
In untyped languages, values do not have any types  
In dynamically typed languages, variables have no types  
In all statically typed languages, each variable in a program is associated with values of only a single type during the execution of the program

Question 25 
Using a larger block size in a fixed block size file system leads to:
better disk throughput but poorer disk space utilization  
better disk throughput and better disk space utilization  
poorer disk throughput but better disk space utilization  
poorer disk throughput and poorer disk space utilization

Question 26 
In a system with 32 bit virtual addresses and 1 KB page size, use of onelevel page tables for virtual to physical address translation is not practical because of
the large amount of internal fragmentation  
the large amount of external fragmentation  
the large memory overhead in maintaining page tables  
the large computation overhead in the translation process

Virtual address = 32 bit = 2^{32}
No. of page level entries = 2^{32} / 2^{10}
= 2^{22}
= 4M (Too large size)
Question 27 
Which of the following assertions is FALSE about the Internet Protocol (IP)?
It is possible for a computer to have multiple IP addresses
 
IP packets from the same source to the same destination can take different routes in the network
 
IP ensures that a packet is discarded if it is unable to reach its destination within a given number of hops
 
The packet source cannot set the route of an outgoing packets; the route is determined only by the routing tables in the routers on the way

Question 28 
Which of the following functionalities must be implemented by a transport protocol over and above the network protocol?
Recovery from packet losses  
Detection of duplicate packets  
Packet delivery in the correct order  
End to end connectivity 
Question 29 
Which of the following scenarios may lead to an irrecoverable error in a database system?
A transaction writes a data item after it is read by an uncommitted transaction  
A transaction reads a data item after it is read by an uncommitted transaction  
A transaction reads a data item after it is written by a committed transaction  
A transaction reads a data item after it is written by an uncommitted transaction

Question 30 
Consider the following SQL query
select distinct a_{l}, a_{2},........., a_{n} from r_{l}, r_{2},........, r_{m} where P
For an arbitrary predicate P, this query is equivalent to which of the following relational algebra expressions?
Question 31 
Let (S, ≤) be a partial order with two minimal elements a and b, and a maximum element c. Let P: S → {True, False} be a predicate defined on S. Suppose that P(a) = True, P(b) = False and P(x) ⇒ P(y) for all x, y ∈ S satisfying x ≤ y, where ⇒ stands for logical implication. Which of the following statements CANNOT be true?
P(x) = True for all x ∈ S such that x ≠ b
 
P(x) = False for all x ∈ S such that x ≠ a and x ≠ c  
P(x) = False for all x ∈ S such that b ≤ x and x ≠ c  
P(x) = False for all x ∈ S such that a ≤ x and b ≤ x 
a or b the minimal element in set.
P(a) = True for all x ∈ S such that a ≤ x and b ≤ x.
Option D is False.
Question 32 
Which of the following is a valid first order formula? (Here α and β are first order formulae with x as their only free variable)
((∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α⇒β]
 
(∀x)[α] ⇒ (∃x)[α ∧ β]  
((∀x)[α ∨ β] ⇒ (∃x)[α] ⇒ (∀x)[α]  
(∀x)[α ⇒ β] ⇒ ((∀x)[α] ⇒ (∀x)[β]) 
Here, α, β are holding values of x. Then and RHS saying that α holding the value of x and β is holding value of x.
Then LHS ⇒ RHS.
Question 33 
Consider the following formula a and its two interpretations I_{1} and I_{2}
α: (∀x)[Px ⇔ (∀y)[Qxy ⇔ ¬Qyy]] ⇒ (∀x)[¬Px] I_{1}: Domain: the set of natural numbers Px ≡ 'x is a prime number' Qxy ≡ 'y divides x' I_{2}: same as I_{1} except that Px = 'x is a composite number'.
Which of the following statements is true?
I_{1} satisfies α, I_{2} does not  
I_{2} satisfies α, I_{1} does not
 
Neither I_{2} nor I_{1} satisfies α
 
Both I_{1} and I_{2} satisfy α 
(∀x)[Px ⇔ (∀y)[Qxy ⇔ ¬Q_{yy}]] ⇒(∀x)[¬Px]
Q_{yy} is always true, because y divide y, then ¬Q_{yy} is false.
∀x[(P(x) ⇔ ∀y [Qxy ⇔ False]]
∀y [Qxy ⇔ False] can be written as ∀y[¬axy]
⇒(∀x)[P(x) ⇔ ∀y[¬Qxy]]
Here, ¬Qxy says that y doesnot divides x, which is not always be true.
For example, if x=y then it is false then ∀y[¬Qxy] is not true for all values of y.
⇒(∀x)[P(x) ⇔ False]
⇒(∀x)[¬P(x) = RHS]
LHS = RHS
⇒ Irrespective of x, whether x is prime of composite number I_{1} and I_{2} satisfies α.
Question 34 
m identical balls are to be placed in n distinct bags. You are given that m ≥ kn, where, k is a natural number ≥1. In how many ways can the balls be placed in the bags if each bag must contain at least k balls?
. So option (B) is correct.
Question 35 
Consider the following recurrence relation
T(1) = 1 T(n+1) = T(n) + ⌊√n+1⌋ for all n≥1
The value of T(m^{2}) for m ≥ 1 is
Considering floor value for square root of numbers.
Successive root number of numbers are in the series 3, 5, 7, ... like 3 numbers from 1... 4, 5 numbers 59 and so on.
Question 36 
How many perfect matching are there in a complete graph of 6 vertices ?
15  
24  
30  
60 
(2n)!/n!×2^{n}
Given, 2n = 6 ⇒ n = 3
So, finally, 6!/3!×2^{3} = 15
Question 37 
Let f : A → B be an injective (onetoone) function. Define g: 2^{A}→2^{B} as: g(C) = {f(x)x ∈ C}, for all subsets C of A.
Define h: 2^{B} → 2^{A} as: h(D) = {xx ∈ A, f(x) ∈ D}, for all subsets D of B.
Which of the following statements is always true?
g(h(D)) ⊆ D  
g(h(D)) ⊇ D  
g(h(D)) ∩ D = ɸ  
g(h(D)) ∩ (B—D) ≠ ɸ 
→ g: 2^{A}→2^{B} be also one to one function and g(C) = f(x)x∈C}, for all subsets C of A.
The range of this function is n(2^{A}).
→ h: 2^{B}→2^{A} it is not a one to one function and given h(D) = {xx∈A, f(x)∈D}, for all subsets D of B.
The range of this function is also n(2^{A}).
→ The function g(h(D)) also have the range n(2^{A}) that implies n(A)≤n(B), i.e., n(2^{A}) is less than n(2^{B}).
Then this result is g(h(D)) ⊆ D.
Question 38 
Consider the set {a, b, c} with binary operators + and × defined as follows:
+ a b c × a b c a b a c a a b c b a b c b b c a c a c b c c c b
For example, a + c = c, c + a = a, c × b = c and b × c = a. Given the following set of equations:
(a × x) + (a × y) = c (b × x) + (c × y) = c
The number of solution(s) (i.e., pair(s) (x, y)) that satisfy the equations is:
0  
1  
2  
3 
In those (x, y) = (b,c) & (c,b) are the possible solution for the corresponding equations.
(x, y) = (b,c) ⇒ (a*b)+(a*c) ⇒ (b*b)+(c*c)
⇒ (b) + (c) ⇒ c + b
⇒ c (✔️) ⇒ c (✔️)
(x,y) = (c,b) ⇒ (a*c)+(a*b) ⇒ (b*c)+(c*b)
⇒ c+b ⇒ a+c
⇒ c (✔️) ⇒ c (✔️)
Question 39 
Let ∑ = (a, b, c, d, e) be an alphabet. We define an encoding scheme as follows:
g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11.
Let p_{i} denote the ith prime number (p_{1}=2).
 For a nonempty string s=a_{1} ... a_{n}, where each a_{i}∈Σ, define
For a nonempty sequence 〈s_{j}...s_{n}〉 of strings from ∑^{+}, define
Which of the following numbers is the encoding h of a nonempty sequence of strings?
2^{7}3^{7}5^{7}  
2^{8}3^{8}5^{8}
 
2^{9}3^{9}5^{9}  
2^{10}5^{10}7^{10} 
And f(S) = 2^{3} = 8
So answer is 2^{8}3^{8}5^{8}.
Question 40 
A graph G = (V,E) satisfies E≤ 3V6. The mindegree of G is defined as . Therefore, mindegree of G cannot be
3  
4  
5  
6 
E ≤ 3v  6
Based on handshaking lemma, the minimum degree is (min×v)/2
⇒ (min×v)/2 ≤ 3v  6
Checking the options lets take min=6
(6×v)/2 ≤ 3v  6
0 ≤ 6 (Not satisfied)
And which is inconsistent.
Question 41 
Consider the following system of linear equation
Notice that the second and the third columns of the coefficient matrix are linearly dependent. For how many values of α, does this system of equations have infinitely many solutions?
0  
1  
2  
infinitely many 
This is in the form AX = B
⇒ R(AB) < n [If we want infinitely many solution]
then 1+5α = 0
5α = 1
α = 1/5 There is only one value of α. System can have infinitely many solutions.
Question 42 
A piecewise linear function f(x) is plotted using thick solid lines in the figure below (the plot is drawn to scale).
If we use the NewtonRaphson method to find the roots of f(x) = 0 using x0, x1 and x2 respectively as initial guesses, the roots obtained would be
1.3, 0.6, and 0.6 respectively  
0.6, 0.6, and 1.3 respectively
 
1.3, 1.3, and 0.6 respectively  
1.3, 0.6, and 1.3 respectively 
Question 43 
The following is a scheme for floating point number representation using 16 bits.
Let s, e, and m be the numbers represented in binary in the sign, exponent, and mantissa fields respectively. Then the floating point number represented is:
What is the maximum difference between two successive real numbers representable in this system?
2^{40}  
2^{9}  
2^{22}  
2^{31} 
The largest number is 1.111111111× 2^{6231} = (2−2^{−9})×2^{31}
Second largest number is 1.111111110×2^{6231} = (2−2^{8})×2^{31}
Difference = (2−2^{−9})×2^{31}  (2−2^{8})×2^{31}
= (2^{8}−2^{−9}) ×2^{31}
= 2^{−9}×2^{31}
= 2^{22}
Question 44 
A 1input, 2output synchronous sequential circuit behaves as follows:
Let z_{k}, n_{k} denote the number of 0's and 1's respectively in initial k bits of the input (z_{k} + n_{k} = k). The circuit outputs 00 until one of the following conditions holds.
• z_{k}  n_{k} = 2. In this case, the output at the kth and all subsequent clock ticks is 10. • n_{k}  z_{k} = 2. In this case, the output at the kth and all subsequent clock ticks is 01.
What is the minimum number of states required in the state transition graph of the above circuit?
5  
6  
7  
8 
q_{0} ← Number of zeros is one more than number of ones.
q_{1} ← Number of ones is one more than number of zeros.
q_{00} ← Number of zeros is two more than number of ones.
q_{11} ← Number of ones is two more than number of zeros.
Question 45 
The literal count of a boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of (xy + xz') is 4. What are the minimum possible literal counts of the productofsum and sumofproduct representations respectively of the function given by the following Karnaugh map ? Here, X denotes "don't care"
(11, 9)  
(9, 13)  
(9, 10)  
(11, 11) 
⇒ w'y' + z'wx' + xyz'
Total 8 literals are there.
For POS,
⇒ (z' + w')(z' + y')(w' + x')(x + z + w)
Total 9 literals are there.
Question 46 
Consider the ALU shown below.
If the operands are in 2's complement representation, which of the following operations can be performed by suitably setting the control lines K and C_{0} only (+ and  denote addition and subtraction respectively)?
A + B, and A – B, but not A + 1  
A + B, and A + 1, but not A – B  
A + B, but not A – B or A + 1  
A + B, and A – B, and A + 1

1) A+B when K=0 and C_{0} = 0. It is binary adder which performs addition of two binary numbers.
2) A  B = A+ B' + 1 when K=1 and C_{0} = 1 ;
Here XOR gates produce B' if K=1. Since 1⊕b= b'.
"1" in (A+B+1) is coming from C_{0}.
Note: 2's complement of B is (B'+1). 3) A+1 when B=0, K=0, C_{0}= 1.
Increments A.
Question 47 
Consider the following circuit composed of XOR gates and noninverting buffers.
The noninverting buffers have delays δ_{1} = 2 ns and δ_{2} = 4 ns as shown in the figure. Both XOR gates and all wires have zero delay. Assume that all gate inputs, outputs and wires are stable at logic level 0 at time 0. If the following waveform is applied at input A, how many transition(s) (change of logic levels) occur(s) at B during the interval from 0 to 10 ns?
1  
2  
3  
4 
⇒ a will always be equal to A.
Question 48 
Consider the following assembly language program for a hypothetical processor. A, B, and C are 8 bit registers. The meanings of various instructions are shown as comments.
MOV B, # 0 ; B ← 0 MOV C, # 8 ; C ← 8 Z : CMP C, # 0 ; compare C with 0 JZX ; jump to X if zero flag is set SUB C, # 1 ; C ← C  1 RRC A, # 1 ; right rotate A through carry by one bit. Thus: ; if the initial values of A and the carry flag are a7...a0 and ; c_{0} respectively, their values after the execution of this ; instruction will be c_{0}a_{7}...a_{1} and a_{0} respectively. JC Y ; jump to Y if carry flag is set JMP Z ; jump to Z Y : ADD B, # 1 ; B ← B + 1 JMP Z ; jump to Z X :
If the initial value of register A is A_{0} the value of register B after the program execution will be
the number of 0 bits in A_{0}
 
the number of 1 bits in A_{0}  
A_{0}  
8 
The code is counting the number of 1 bits in A_{0}.
Question 49 
Consider the following assembly language program for a hypothetical processor. A, B, and C are 8 bit registers. The meanings of various instructions are shown as comments.
MOV B, # 0 ; B ← 0 MOV C, # 8 ; C ← 8 Z : CMP C, # 0 ; compare C with 0 JZX ; jump to X if zero flag is set SUB C, # 1 ; C ← C  1 RRC A, # 1 ; right rotate A through carry by one bit. Thus: ; if the initial values of A and the carry flag are a7...a0 and ; c_{0} respectively, their values after the execution of this ; instruction will be c_{0}a_{7}...a_{1} and a_{0} respectively. JC Y ; jump to Y if carry flag is set JMP Z ; jump to Z Y : ADD B, # 1 ; B ← B + 1 JMP Z ; jump to Z X :
Which of the following instructions when inserted at location X will ensure that the value of register A after program execution is the same as its initial value?
RRC A, #1
 
NOP ; no operation  
LRC A, #1 ; left rotate A through carry flag by one bit  
ADD A, #1 
a_{7}, a_{6}, a_{5, a4, a3 , a2, a1, a0 Now right rotate it once, C0, a7, a6, a5, a4, a3 , a2, a1, now a0 is the new carry. Now again right rotate it, a0C0, a7, a6, a5, a4, a3 , a2 ⁞ So after 8 rotations, a6, a5, a4, a3 , a2, a1, a0C0 and carry is a7 Now, one more rotation will restore the original value of A0. Hence, answer is Option (A). }
Question 50 
Consider the following deterministic finite state automaton M.
Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is
1  
5  
7  
8 
There are possible: 7 strings.
Question 51 
Let G = ({S},{a,b},R,S) be a context free grammar where the rule set R is S → aSb  SS  ε Which of the following statements is true?
G is not ambiguous  
There exist x, y ∈ L(G) such that xy ∉ L(G)
 
There is a deterministic pushdown automaton that accepts L(G)  
We can find a deterministic finite state automaton that accepts L(G) 
We can derive ϵ with more than one parse tree,
So ambiguous.
b) False
Let take x=aabb and y=ab then xy=aabbab we can produce it,
c) True
Because the language generated is no. of a's = no' of b's. So DPDA exist for this language.
d) Not possible.
Infinite memory needed to count 'a' for no. of 'b'.
Question 52 
Consider two languages L_{1} and L_{2} each on the alphabet ∑. Let f: ∑ → ∑ be a polynomial time computable bijection such that (∀ x)[x ∈ L_{1} iff f(x) ∈ L_{2}]. Further, let f^{1} be also polynomial time computable.
Which of the following CANNOT be true?
L_{1} ∈ P and L_{2} is finite  
L_{1} ∈ NP and L_{2} ∈ P
 
L_{1} is undecidable and L_{2} is decidable  
L_{1} is recursively enumerable and L_{2} is recursive 
Now if L_{2} is decidable then L_{1} should also be decidable. Hence, option (c) is wrong.
Question 53 
A single tape Turing Machine M has two states q_{0} and q_{1}, of which q_{0} is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table.
The table is interpreted as illustrated below. The entry (q_{1}, 1, R) in row q_{0} and column 1 signifies that if M is in state q_{0} and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q_{1}.
Which of the following statements is true about M?
M does not halt on any string in (0+1)^{+}
 
M does not halt on any string in (00+1)*  
M halts on all strings ending in a 0  
M halts on all strings ending in a 1 
Try for any string, it will not Halt for any string other than ϵ. Hence, option (A) is correct.
Question 54 
Define languages L_{0} and L_{1} as follows:
L_{0} = {〈M, w, 0〉  M halts on w} L_{1} = {〈M, w, 1〉  M does not halts on w}
Here 〈M, w, i〉 is a triplet, whose first component. M, is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit.
Let L = L_{0}∪L_{1}. Which of the following is true?
Question 55 
Consider the NFA M shown below.
Let the language accepted by M be L. Let L_{1} be the language accepted by the NFA M_{1}, obtained by changing the accepting state of M to a nonaccepting state and by changing the nonaccepting state of M to accepting states. Which of the following statements is true?
L_{1} = {0,1}*  L  
L_{1} = {0,1}*  
L_{1} ⊆ L  
L_{1} = L 
As in above NFA language,
L_{1} is {0,1}*.
Question 56 
Consider the grammar shown below
S → i E t S S'  a S' → e S  ε E → b
In the predictive parse table. M, of this grammar, the entries M[S', e] and M[S', $] respectively are
{S'→e S} and {S'→ε}  
{S'→e S} and { }  
{S'→ε} and {S'→ε}  
{S'→e S, S'→ε} and {S'→ε} 
First(S') = {e,ε}
First(E) = {b}
Follow(S') = {e,$}
Only when 'First' contains ε, we need to consider FOLLOW for getting the parse table entry.
Hence, option (D) is correct.
Question 57 
Consider the grammar shown below.
S → C C C → c C  d
The grammar is
LL(1)  
SLR(1) but not LL(1)
 
LALR(1) but not SLR(1)  
LR(1) but not LALR(1)

Hence, it is LL(1).
Question 58 
Consider the translation scheme shown below.
S → T R R → + T {print ('+');} Rε T → num {print(num.val);}
Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string '9 + 5 + 2', this translation scheme will print
9 + 5 + 2  
9 5 + 2 +  
9 5 2 + +  
+ + 9 5 2 
Now traverse the tree and whatever comes first to print, just print it.
Answer will be 9 5 + 2 +.
Question 59 
Consider the syntax directed definition shown below.
S → id := E {gen (id.place = E.place;);} E → E_{1} + E_{2} {t = newtemp ( ); gen(t = E_{1}.place + E_{2}.place;); E.place = t} E → id {E.place = id.place;}
Here, gen is a function that generates the output code, and newtemp is a function that returns the name of a new temporary variable on every call. Assume that ti's are the temporary variable names generated by newtemp. For the statement 'X: = Y + Z', the 3address code sequence generated by this definition is
X = Y + Z  
t_{1} = Y + Z; X = t_{1}  
t_{1}= Y; t_{2} = t_{1} + Z; X = t_{2}  
t_{1} = Y; t_{2} = Z; t_{3} = t_{1} + t_{2}; X = t_{3}

Question 60 
A program consists of two modules executed sequentially. Let f_{1}(t) and f_{2}(t) respectively denote the probability density functions of time taken to execute the two modules. The probability density function of the overall time taken to execute the program is given by:
f_{1}(t) + f_{2}(t)  
max{f_{1}(t), f_{2}(t)} 
→ They representing the probability density functions of time taken to execute.
→ f_{1} can be executed in 'x' time.
f_{2} can be executed in 'tx' time.
→ The probability density function =
Question 61 
In a permutation a_{1}...a_{n} of n distinct integers, an inversion is a pair (a_{i}, a_{j}) such that i < j and a_{i} > a_{j}.
If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1...n ?
n(n1)/2  
n(n1)/4  
n(n+1)/4  
2n[log_{2}n] 
Question 62 
In a permutation a_{1}...a_{n} of n distinct integers, an inversion is a pair (a_{i}, a_{j}) such that i
What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1...n with at most n inversions?
Θ(n^{2})  
Θ(n log n)  
Θ(n^{1.5})  
Θ(n) 
Question 63 
A data structure is required for storing a set of integers such that each of the following operations can be done in O(log n) time, where n is the number of elements in the set.
 I. Deletion of the smallest element
II. Insertion of an element if it is not already present in the set
Which of the following data structures can be used for this purpose?
A heap can be used but not a balanced binary search tree  
A balanced binary search tree can be used but not a heap  
Both balanced binary search tree and heap can be used  
Neither balanced binary search tree nor heap can be used 
Insertion of an element takes O(n).
→ In balanced primary tree deletion takes O(log n).
Insertion also takes O(log n).
Question 64 
Let S be a stack of size n≥1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m≥1, define the stacklife of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stacklife of an element of this stack is
n(X + Y)  
3Y + 2X  
n(X + Y)  X  
Y + 2X 
(After push into stack then immediately popped)
Life time of (n1) element = Y + X + Y + X + Y = 2X + 3Y
Life time of (n2) element = (n1) + 2X + 2Y = 2X + 3Y + 2X + 2Y = 4X + 5Y
Life time of 1's element = 2(n1)X + (2n1)Y
Life time of all elements is ⇒
2X(1+2+3+...+n1)+Y(1+3+5+...+(2n1))
⇒ 2X(n(n1) /2) +Y((n/2)(1+2n1))
⇒ n(n(X+Y)X))
Avg. of n numbers = n(n(X+Y)X)/n = n(X+Y)X
Question 65 
Consider the following 234 tree (i.e., Btree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree.
What is the result of inserting G in the above tree?
None of the above 
Insert G at root level:
Question 66 
The cube root of a natural number n is defined as the largest natural number m such that m^{3}≤n. The complexity of computing the cube root of n (n is represented in binary notation) is:
O(n) but not O(n^{0.5})  
O(n^{0.5} but not O((log n)^{k}) for any constant k>0
 
O((log n)^{k}) for some constant k>0, but not O((log log n)^{m}) for any constant m>0  
O((log log n)^{k}) for some constant k>0.5, but not O((log log n)^{0.5}) 
The time complexity is never less than O(log n) because to represent a binary search will takes O(log n) ... (II)
From (I), option A and B False
From (II), option D False.
Question 67 
Let G = (V, E) be an undirected graph with a subgraph G_{1} = (V_{1}, E_{1}). Weights are assigned to edges of G as follows:
A singlesource shortest path algorithm is executed on the weighted graph (V,E,w) with an arbitrary vertex ν_{1} of V_{1} as the source. Which of the following can always be inferred from the path costs computed?
The number of edges in the shortest paths from v_{1} to all vertices of G  
G_{1} is connected  
V_{1} forms a clique in G  
G_{1} is a tree 
Question 68 
What is the weight of a minimum spanning tree of the following graph ?
29  
31  
38  
41 
1+2+3+2+8+4+4+2+5 =31
Question 69 
The following are the starting and ending times of activities A, B, C, D, E, F, G and H respectively in chronological order: "a_{s}b_{s}c_{s}a_{e}d_{s}c_{e}e_{s}f_{s}b_{e}d_{e}g_{s}e_{e}f_{e}h_{s}g_{e}h_{e}" Here, x_{s} denotes the starting time and x_{e} denotes the ending time of activity X. We need to schedule the activities in a set of rooms available to us. An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required?
3  
4  
5  
6 
Where x_{s}→Starting time, x_{e}→ Ending time.
R_{1}→for a
R_{2}→for b
R_{3}→for c
a_{e}, R_{1} is free
R_{1}→for d
c_{e}, R_{3} is free
R_{3}→for e
R_{4}→for f
b_{e}, R_{2} is free
d_{e}, R_{1} is free
R_{1}→for g
e_{e}, R_{3} is free
f_{e}, R_{4} is free
R_{2}→for h
g_{e}, R_{1} is free
h_{e}, R_{2} is free
Here, total we used is: R_{1}, R_{2}, R_{3}, R_{4}.
Therefore, total no. of rooms we required = 4(minimum).
Question 70 
Let G = (V,E) be a directed graph with n vertices. A path from v_{i} to v_{j} in G is sequence of vertices (v_{i}, v_{i+1}, ......., v_{j}) such that (v_{k}, v_{k+1}) ∈ E for all k in i through j1. A simple path is a path in which no vertex appears more than once. Let A be an nxn array initialized as follow.
Consider the following algorithm.
for i = 1 to n for j = 1 to n for k = 1 to n A [j,k] = max (A[j,k] (A[j,i] + A [i,k]);
Which of the following statements is necessarily true for all j and k after terminal of the above algorithm?
A[j,k] ≤ n  
If A[j,j] ≥ n1, then G has a Hamiltonian cycle
 
If there exists a path from j to k, A[j,k] contains the longest path length from j to k  
If there exists a path from j to k, every simple path from j to k contains at most A[j,k] edges

Here, we have two functionalities i.e., from j to k, there exists a path then it results otherwise 0.
If there exist a path then it results
A[j,k] = max(A[j,k], A[j,i]+A[i,k])
i.e., if there exists a path from j to k, every simple path from j to k contains the atmost A[j,k] edges.
Question 71 
Consider the following logic program P
A(x) < B(x, y), C(y) < B(x,x)
Which of the following first order sentences is equivalent to P?
(∀x) [(∃y) [B(x,y) ∧ C(y)] ⇒ A(x)] ∧ ¬(∃x)[B(x,x)]  
(∀x) [(∀y) [B(x,y) ∧ C(y)] ⇒ A(x)] ∧ ¬(∃x)[B(x,x)]  
(∀x) [(∃y) [B(x,y) ∧ C(y)] ⇒ A(x)] ∨ ¬(∃x)[B(x,x)]  
(∀x) [(∀y) [B(x,y) ∧ C(y)] ⇒ A(x)] ∧ (∃x)[B(x,x)] 
Question 72 
The following resolution rule is used in logic programming.
Derive clause (P ∨ Q) from clauses (P ∨ R), (Q ∨ ¬R)
Which of the following statements related to this rule is FALSE?
((P ∨ R) ∧ (Q ∨ ¬R)) ⇒ (P ∨ Q) is logically valid  
(P ∨ Q) ⇒ ((P ∨ R) ∧ (Q ∨ ¬R)) is logically valid
 
(P ∨ Q) is satisfiable if and only if (P∨R) ∧ (Q∨¬R) is satisfiable  
(P ∨ Q) ⇒ FALSE if and only if both P and Q are unsatisfiable

It is may be True (or) False depending on values. So this is not valid.
Question 73 
The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions.
global int i = 100, j = 5; void P(x) { int i = 10; print(x + 10); i = 200; j = 20; print(x); } main() { P(i + j); }
If the programming language uses static scoping and call by need parameter passing mechanism, the values printed by the above program are
115, 220  
25, 220  
25, 15  
115, 105 
P(100+5) = P(105)
→void P(105)
{
int i=10;
print (x+10); ⇒ 105+10=115 prints
i=200;
j = 20;
print (x); ⇒ x=105 prints
}
115, 105 prints
Question 74 
The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions.
global int i = 100, j = 5; void P(x) { int i = 10; print(x + 10); i = 200; j = 20; print(x); } main() { P(i + j); }
If the programming language uses dynamic scoping and call by name parameter passing mechanism, the values printed by the above program are:
115, 220  
25, 220  
25, 15  
115, 105 
In void P(x)
{ int i = 10;
print(x + 10); ⇒ 105+10 = 115 prints
print (x); ⇒ print x=220;
Question 75 
Consider the following class definitions in a hypothetical Object Oriented language that supports inheritance and uses dynamic binding. The language should not be assumed to be either Java or C++, though the syntax is similar.
Class P { void f(int i) { print(i); } } Class Q subclass of P { void f(int i) { print(2*i); } }
Now consider the following program fragment:
Px = new Q(); Qy = new Q(); Pz = new Q(); x.f(1); ((P)y).f(1); z.f(1);
Here ((P)y) denotes a typecast of y to P. The output produced by executing the above program fragment will be
1 2 1  
2 1 1  
2 1 2  
2 2 2 
Note: The given question is not in the present syllabus
Question 76 
Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?
Smaller sizes of executable files  
Lesser overall page fault rate in the system  
Faster program startup
 
Existing programs need not be relinked to take advantage of newer versions of libraries 
Question 77 
A uniprocessor computer system only has two processes, both of which alternate 10ms CPU bursts with 90ms I/O bursts. Both the processes were created at nearly the same time. The I/O of both processes can proceed in parallel. Which of the following scheduling strategies will result in the least CPU utilization (over a long period of time) for this system?
First come first served scheduling  
Shortest remaining time first scheduling  
Static priority scheduling with different priorities for the two processes  
Round robin scheduling with a time quantum of 5 ms

(i) FCFS:
010: Process 1 can execute
1020: Process 2 can execute
100110: Process 1 Terminate
110120: Process 2 Terminate
CPU utilization = 20/100 [In every 100ms it utilizes]
=20%
(ii) SRTF: can process P and Q same as FCFS
then CPU utilization = 20%
(iii) Round robin: with TQ5
05: Process P_{1}
510: Process P_{2}
1015: Process P_{1}
1520: Process P_{2}
105110: Process P_{1}
110115: Process P_{2}
CPU utilization = 20/105 = 19.5
Question 78 
A processor uses 2level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The memory is byte addressable. For virtual to physical address translation, the 10 most significant bits of the virtual address are used as index into the first level page table while the next 10 bits are used as index into the second level page table. The 12 least significant bits of the virtual address are used as offset within the page. Assume that the page table entries in both levels of page tables are 4 bytes wide. Further, the processor has a translation lookaside buffer (TLB), with a hit rate of 96%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of 90%. Main memory access time is 10 ns, cache access time is 1 ns, and TLB access time is also 1 ns.
Assuming that no page faults occur, the average time taken to access a virtual address is approximately (to the nearest 0.5 ns)
1.5 ns  
2 ns  
3 ns  
4 ns 
(TLB Miss * Cache Hit) + (TLB Miss * Cache Miss)
= (0.96*0.9*2)+(0.96*0.1+12)
(0.04*0.9*2)+(0.04*0.1*32)
= 3.8
= 4 (approximately)
Question 79 
A processor uses 2level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The memory is byte addressable. For virtual to physical address translation, the 10 most significant bits of the virtual address are used as index into the first level page table while the next 10 bits are used as index into the second level page table. The 12 least significant bits of the virtual address are used as offset within the page. Assume that the page table entries in both levels of page tables are 4 bytes wide. Further, the processor has a translation lookaside buffer (TLB), with a hit rate of 96%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of 90%. Main memory access time is 10 ns, cache access time is 1 ns, and TLB access time is also 1 ns.
Suppose a process has only the following pages in its virtual address space: two contiguous code pages starting at virtual address 0x00000000, two contiguous data pages starting at virtual address 0×00400000, and a stack page starting at virtual address 0×FFFFF000. The amount of memory required for storing the page tables of this process is:
8 KB  
12 KB  
16 KB  
20 KB 
32bits are broken up as 10bits (L2)  10bits (L1)  12bits (offset)
First code page:
0x00000000 = 0000 0000 00  00 0000 0000  0000 0000 0000
So next code page will start from
0x00001000 = 0000 0000 00  00 0000 0001  0000 0000 0000
First data page:
0x00400000 = 0000 0000 01  00 0000 0000  0000 0000 0000
So next data page will start from
0x00401000 = 0000 0000 01  00 0000 0001  0000 0000 0000
Only one stack page:
0xFFFFF000 = 1111 1111 11  11 1111 1111  0000 0000 0000
Now, for second level page table, we will just require 1 Page
which will contain following 3 distinct entries i.e. 0000 0000 00, 0000 0000 01, 1111 1111 11.
Now, for each of these distinct entries, we will have 11 page in Level1.
Hence, we will have in total 4 pages and page size = 2^{12} = 4KB.
Therefore, Memory required to store page table = 4*4KB = 16KB.
Question 80 
Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below.
Process P: while (1) { W: print '0'; print '0'; X: } Process Q: while (1) { Y: print '1'; print '1'; Z: }
Synchronization statements can be inserted only at points W, X, Y and Z.
Which of the following will always lead to an output staring with '001100110011'?
P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1  
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T initially 0  
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1  
P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S initially 1, and T initially 0

Process P_{1} will be executed first and then Process P_{2} can be executed next.
At the process P: W=P(S)
X=V(T)
At the process Q: Y=P(T)
Z=V(S)
Here, S=1, T=0 then the process P executes first and then Q, and both can run on process alternate way start with P.
Question 81 
Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below.
Process P: while (1) { W: print '0'; print '0'; X: } Process Q: while (1) { Y: print '1'; print '1'; Z: }
Synchronization statements can be inserted only at points W, X, Y and Z.
Which of the following will ensure that the output string never contains a substring of the form 01^{n}0 or 10^{n}1 where n is odd?
P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1  
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1  
P(S) at W, V(S) at X, P(S) at Y, V(S) at Z, S initially 1  
V(S) at W, V(T) at X, P(S) at Y, P(T) at Z, S and T initially 1 
Question 82 
The subnet mask for a particular network is 255.255.31.0. Which of the following pairs of IP addresses could belong to this network?
172.57.88.62 and 172.56.87.233
 
10.35.28.2 and 10.35.29.4  
191.203.31.87 and 191.234.31.88  
128.8.129.43 and 128.8.161.55 
128.8.129.43 (Bitwise AND) 255.255.31.0 = 128.8.1.0
128.8.161.55 (Bitwise AND) 255.255.31.0 = 128.8.1.0
Question 83 
A 2 km long broadcast LAN has 10^{7} bps bandwidth and uses CSMA/CD. The signal travels along the wire at 2×10^{8} m/s. What is the minimum packet size that can be used on this network?
50 bytes  
100 bytes  
200 bytes  
None of the above 
d= 2 km = 2 x 10^{3} m, v = 2 x 10^{8} m/s, B= 10^{7}
T_{p} = d / v = 2 x 10^{3} /(2 x 10^{8} ) seconds = 10^{5} seconds
Let L bits be minimum size of frame, then T_{t} = t L / B = L / 10^{7} seconds
Now, T_{t} = 2T_{p}
L/10^{7} = 2 x 10^{5} = 200 bits = (200 / 8) bytes = 25 bytes
Question 84 
Host A is sending data to host B over a full duplex link. A and B are using the sliding window protocol for flow control. The send and receive window sizes are 5 packets each. Data packets (sent only from A to B) are all 1000 bytes long and the transmission time for such a packet is 50 µs. Acknowledgement packets (sent only from B to A) are very small and require negligible transmission time. The propagation delay over the link is 200 µs. What is the maximum achievable throughput in this communication?
7.69 × 10^{6} bps
 
11.11 × 10^{6} bps  
12.33 × 10^{6} bps  
15.00 × 10^{6} bps 
Transmission rate , T_{t} = L / B.W
Therefore, B.W. = L / T_{t} = 1000 bytes/ 50 μs = 8000 bits / 50 μs=160 Mbps
Efficiency = N / 1 + 2a, where a = T_{p} / T_{t}
Efficiency = 5 * 50 / (50+400) = 250/450 = 5/9
Maximum achievable throughput = Efficiency * B.W = (5/9)*160 Mbps = 88.88 Mbps = = 11.11 x 10^{6} bytes per second
*Actual option should be in bytes per second.
Question 85 
Consider the following functional dependencies in a database:
Data_of_Birth → Age Age → Eligibility Name → Roll_number Roll_number → Name Course_number → Course_name Course_number → Instructor (Roll_number, Course_number) → Grade
The relation (Roll_number, Name, Date_of_birth, Age) is:
in second normal form but not in third normal form  
in third normal form but not in BCNF  
in BCNF  
in none of the above 
Date_of_Birth → Age
Name → Roll_number
Roll_number → Name
Candidate keys for the above are:
(Date_of_Birth, Name) and (Date_of_Birth, Roll_number)
Clearly, there is a partial dependency,
Date_of_Birth → Age
So, it is only in 1NF.
Question 86 
Consider the set of relations shown below and the SQL query that follows.
Students: (Roll_number, Name, Date_of_birth) Courses: (Course number, Course_name, Instructor) Grades: (Roll_number, Course_number, Grade) select distinct Name from Students, Courses, Grades where Students. Roll_number = Grades.Roll_number and Courses.Instructor = Korth and Courses.Course_number = Grades.Course_number and Grades.grade = A
Which of the following sets is computed by the above query?
Names of students who have got an A grade in all courses taught by Korth
 
Names of students who have got an A grade in all courses  
Names of students who have got an A grade in at least one of the courses taught by Korth
 
in none of the above 
Question 87 
Consider three data items D1, D2 and D3 and the following execution schedule of transactions T1, T2 and T3. In the diagram, R(D) and W(D) denote the actions reading and writing the data item D respectively.
Which of the following statements is correct?
The schedule is serializable as T2; T3; T1
 
The schedule is serializable as T2; T1; T3  
The schedule is serializable as T3; T2; T1  
The schedule is not serializable 
Cycle formed so not serializable.
Question 88 
In the following C program fragment, j, k n and TwoLog_n are interger variables, and A is an array of integers. The variable n is initialized to an integer ≥3, and TwoLog_n is initialized to the value of 2*⌈log_{2}(n)⌉
for (k = 3; k < = n; k++) A[k] = 0; for (k = 2; k < = TwoLog_n; k++) for (j = k + 1; j < = n; j++) A[j] = A[j]  (j%k); for (j = 3; j < = n; j++) if (!A[j]) printf("%d", j);
The set of numbers printed by this program fragment is
{mm ≤ n, (∃i)[m=i!]}  
{mm ≤ n, (∃i)[m=i^{2}]}  
{mm ≤ n, m is prime}
 
{ } 
Now Trace the code,
for (k=3; k<=n; k++)
A[k]=0; // A[3]=0
A[4]=0
for (k=2; k<=Two log_n; k++)
for(j=k+1; j<=n; j++)
A[j] = A[j] // (j%k); // A[3] = 0 // I=1
A[4] = 0 // I=1
for (j=3; j<=n; j++)
if (!A[j]) printf("%d", j);
// if (!1) means if (0), so printf will never execute
Hence, Option (D) is the answer.
Question 89 
Consider the C program shown below.
#include#define print(x) printf("%d", x) int x; void Q(int z) { z += x; print(z); } void P(int *y) { int x = *y + 2; Q(x); *y = x  1; print(x); } main(void) { x = 5; P(&x); print(x); }
The output of this program is
12 7 6
 
22 12 11  
14 6 6  
7 6 6 
p(&x) it goes to P( ) function
y=5
x=5+2=7;
Q(x)
z=7
z=7+5=12(Print+z→I)
comes to P( )
*y=71=6
x=7(Print x→II)
comes to main ( ),
print x=*y=6 (print x→III)
Output: 12 7 6
Question 90 
Consider the function f defined below.
struct item { int data; struct item * next; }; int f(struct item *p) { return ((p == NULL)  (p>next == NULL)  ((P>data <= p>next>data) && f(p>next))); }
For a given linked list p, the function f returns 1 if and only if
the list is empty or has exactly one element  
the elements in the list are sorted in nondecreasing order of data value
 
the elements in the list are sorted in nonincreasing order of data value
 
not all elements in the list have the same data value 