GATE 2015 [Set2]
Question 1 
Based on the given statements, select the most appropriate option to solve the given question, What will be the total weight of 10 poles each of same weight?

Statements:
(I) One fourth of the weight of a pole is 5 kg
(II) The total weight of these poles is 160 kg more than the total weight of two poles.
Statement I alone is not sufficient  
Statement II alone is not sufficient  
Statement II alone is not sufficient  
Both statements I and II together are not sufficient. 
One fourth of the weight of a pole is 5Kg. ⇒ Weight of pole is 4×5 = 20Kg
Weight of 10 poles each of same weight = 10×20 = 200 Kg
∴Statement I alone is sufficient.
StatementII:
Let, Weight of each pole = W Kg
Given,
10W = 2W + 160
⇒ 8W = 160
W = 20Kg
∴ Weight of each pole = 20 Kg
∴ Weight of 10 poles = 10×20 Kg = 200 Kg
∴ Statement II alone is sufficient.
Option (C) is the answer.
Either I or II alone is sufficient.
Question 2 
Consider a function f(x) = 1  x on 1 ≤ x ≤ 1. The value of x at which the function attains a maximum and the maximum value of the function are
0, 1  
1, 0  
0, 1  
1, 2 
In the given function, it is given as
x ⇒ To obtain the maximum of this function we have to minimize the value x and the minimum value is 0.
∴ Maximum value of f(x) is at f(0) and i.e., f(x) = 1
Maximum value is 1 at x=0.
Question 3 
A generic term that include various items of clothing such as a skirt, a pair of trousers and a shirt is
fabric  
textile  
fibre  
apparel 
Question 4 
Choose the statement where underlined word is used correctly.
The industrialist load a personnel jet.
 
I write my experience in my personnel diary.  
All personnel are being given the day off.  
Being religious is a personnel aspect. 
Question 5 
We __________________ our friend’s birthday and we ______________ how to make it up to him.
Completely forgot    don’t just know
 
Forgot completely    don’t just know  
Completely forgot    just don’t know  
Forgot completely    just don’t know 
Question 6 
In a triangle PQR, PS is the angle bisector of ∠QPR and ∠QPS = 60º. What is the length of PS?
(q+r)/qr  
qr/(q+r)  
√(q^{2} + r^{2})  
(q+r)^{2} /qr 
∠QPS = 60º
and PS is angle bisector of ∠QPR
⇒ ∠QPS = ∠SPR = 60º
and ∠QPR = 120º
Let, PS = s
Area of ΔPQR = Area of ΔPQS + Area of ΔSPR
1/2 qr Sin∠QPR = 1/2 rs Sin∠QPS + 1/2 sq∠SPR
1/2 qr Sin 120º = 1/2 rs Sin 60º + 1/2 sq 60º
1/2 qr Sin × √3/2 = 1/2 rs × √3/2 + 1/2 × √3/2
qr = rs + sq
∴ s = qr/q+r
PS = qr/q+r
Question 7 
Out of the following four sentences, select the most suitable sentence with respect to grammar and usage.
Since the report lacked needed information, it was of no use to them.
 
The report was useless to them because there were no needed information in it.
 
Since the report did not contain the needed information, it was not real useful to them  
Since the report lacked needed information, it would not have been useful to them. 
(C) not really useful
(D) would not have been
Question 8 
If the list of letters, P, R, S, T, U is an arithmetic sequence, which of the following are also in arithmetic sequence?

I. 2P, 2R, 2S, 2T, 2U
II. P3, R3, S3, T3, U3
III. P^{2}, R^{2}, S^{2}, T^{2}, U^{2}
I only  
I and II  
II and III  
I and III 
Hence, II is an arithmetic sequence.
If the set of numbers is multiplied by the common number, even then the new set will also be in arithmetic sequence.
Hence, I is an arithmetic sequence.
Question 9 
If p, q, r, s are distinct integers such that:

f(p,q,r,s) = max(p,q,r,s)
g(p,q,r,s) = min(p,q,r,s)
h(p,q,r,s) = remainder of (p×q)(r×s) if (p×q)>(r×s) OR remainder of (r×s)(p×q) if (r×s)>(p×q)
Also a function fgh(p,q,r,s) = f(p,q,r,s) × g(p,q,r,s) ×h(p,q,r,s)
Also the same operations are valid with two variable functions of the form f(p,q).
What is the value of fg(h(2,5,7,3),(4,6,8)?
8  
9  
7  
6 
= remainder of 21/10
= 1
fg(1,4,6,8) = f(1,4,6,8) × g(1,4,6,8)
= max(1,4,6,8) × min(1,4,6,8)
= 8 × 1
= 8
Question 10 
Four branches of a company are located at M, N, O and P. M is north of N at a distance of 4km; P is south of O at a distance of 2 km; N is southeast of O by 1 km. What is the distance between M and P in km?
5.34  
6.74  
28.5  
45.49 
Question 11 
An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is
Θ(nlog n)  
Θ(n)  
Θ(log n)  
Θ(1) 
Question 12 
Let R be the relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is true?
R is symmetric and reflexive but not transitive  
R is reflexive but not symmetric and not transitive  
R is transitive but not reflexive and not symmetric  
R is symmetric but not reflexive and not transitive 
In aRb, 'a' and 'b' are distinct. So it can never be reflexive.
Symmetric:
In aRb, if 'a' and 'b' have common divisor other than 1, then bRa, i.e., 'b' and 'a' also will have common divisor other than 1. So, yes symmetric.
Transitive:
Take (3, 6) and (6, 2) elements of R. For transitivity (3, 2) must be the element of R, but 3 and 2 don't have a common divisor. So not transitive.
Question 13 
Consider the following transaction involving two bank account x and y.
read(x); x:= x50; write(x); read(y); y:= y+50; write(y)The constraint that the sum of the accounts x and y should remain constant is that of
Atomicity  
Consistency  
Isolation  
Durability 
Question 14 
A binary tree T has 20 leaves. The number of nodes in T having two children is _________.
19  
20  
21  
22 
(i) p vertices (i.e., leaves) of degree 1
(ii) one vertex (i.e., root of T) of degree 2
(iii) 'n  p  1' (i.e., interval) vertices of degree 3
(iv) n  1 edges
∴ By Handshaking theorem,
p × 1 + 1 × 2 + (n  p  1) × 3 = 2(n  1)
⇒n = 2p  1
= 39 as p = 20
∴ n  p = 19 vertices have exactly two children
Question 15 
Consider the basic COCOMO model where E is the effort applied in personmonths, D is the development time in chronological months, KLOC is the estimated number of delivered lines of code (in thousands) and a_{b}, b_{b}, c_{b}, d_{b} have their usual meanings. The basic COCOMO equations are of the form
E = a _{b}(KLOC)exp (b _{b}, D = c _{b}(E)exp (d _{b})  
E = a _{b}(KLOC)exp (b _{b}, D = c _{b}(E)exp (d _{b})  
E = a _{b}exp(b _{b}), D = c _{b}(KLOC)exp (d _{b})  
E = a _{b}exp(D _{b}), D = c _{b}(KLOC)exp (b _{b}) 
Effort applied (E) = a_{b}(KLOC)b_{b}
Development time (D) = c_{b}(E)d_{b}
Question 16 
Consider the following statements:

S1: If a candidate is known to be corrupt, then he will not be elected.
S2: If a candidate is kind, he will be elected.
Which one of the following statements follows from S1 and S2 as per sound inference rules of logic?
If a person is known to corrupt, he is kind  
If a person is not known to be corrupt, he is not kind
 
If a person is kind, he is not known to be corrupt
 
If a person is not kind, he is not known to be corrupt 
q: candidate will be elected
r: candidate is kind
then S1 = p→~q
= q→~p (conrapositive rule)
and S2: r→q ⇒ r→~p (transitive rule)
i.e., If a person is kind, he is not known to be corrupt. ∴ Option is C
Question 17 
Assume that for a certain processor, a read request takes 50 nanoseconds on a cache miss and 5 nanoseconds on a cache hit. Suppose while running a program, it was observed that 80% of the processors read requests result in a cache hit. The average and access time in nanoseconds is _______.
14  
15  
16  
17 
Question 18 
A system has 6 identical resources and N processes competing for them. Each process can request atmost 2 resources. Which one of the following values of N could lead to a deadlock?
1  
2  
3  
6 
Question 19 
Consider a complete binary tree where the left and the right subtrees of the root are maxheaps. The lower bound for the number of operations to convert the tree to a heap is
Ω(logn)  
Ω(n)  
Ω(nlog n)  
Ω(n^{2}) 
Question 20 
In the context of abstractsyntaxtree (AST) and controlflowgraph (CFG), which one of the following is TRUE?
In both AST and CFG, let node, N_{2} be the successor of node N_{1}. In the input program, the code corresponding to N_{2} is present after the code corresponding in N_{1}.
 
For any input program, neither AST nor CFG will contain a cycle
 
The maximum number of successors of a node in an AST and a CFG depends on the input program
 
Each node is AST and CFG corresponds to at most one statement in the input program 
Option (B) is false as CFG can contain cycle
Option (D) is false as a single node can contain block of statements.
Question 21 
With reference to the B^{+} tree index of order 1 shown below, the minimum number of nodes (including the Root node) that must be fetched in order to satisfy the following query:"Get all records with a search key grater than or equal to 7 and less than 15" is ___________.
6  
7  
5  
9 
Question 22 
A software requirements specification(SRS) document should avoid discussing which one of the following?
User interface issues  
Nonfunctional requirements  
Design specification  
Interfaces with third party software

Question 23 
Identify the correct order in which a server process must invoke the function calls accept, bind, listen, and recv according to UNIX socket API.
listen, accept, bind recv  
bind, listen, accept, recv  
bind, accept, listen, recv  
accept, listen, bind recv 
Question 24 
The larger of the two eigenvalues of the matrix is _________.
6  
7  
8  
9 
⇒ λ^{2}  5λ  6 = 0 ⇒ (λ  6)(λ + 1) = 0 ⇒ λ = 6, 1
∴ Larger eigen value is 6.
Question 25 
The cardinality of the power set of {0, 1, 2, … 10} is _________.
2046  
2047  
2048  
2049 
Question 26 
Which one of the following statements is NOT correct about HTTP cookies?
A cookie is a piece of code that has the potential to compromise the security of an internet user  
A cookie gains entry to the user’s work area through an HTTP header  
A cookie has an expiry date and time  
Cookies can be used to track the browsing pattern of a user at a particular site

Cookies are not piece of code, they are just strings typically in the form of key value pairs.
Question 27 
Consider the following function written the C programming language.
void foo(char *a) { if(*a && *a != ' ') { foo(a+1); putchar(*a); } }
The output of the above function on input "ABCD EFGH" is
ABCD EFGH  
ABCD  
HGFE DCBA  
DCBA 
if condition fails
& returns controls
∴ DCBA will be pointed
Question 28 
A link has a transmission speed of 10^{6} bits/sec. It uses data packets of size 1000 bytes each. Assume that the acknowledgement has negligible transmission delay, and that its propagation delay is the same as the data propagation delay. Also assume that the processing delays at the nodes are negligible. The efficiency of the stopandwait protocol in this setup is exactly 25%. The value of the oneway propagation delay (in milliseconds) is ___________.
12  
13  
14  
15 
L = 1000
η = 25%
T_{p} = ?
In stopandwait, η = 1/1 + 2a
⇒1/4 = 1/1 + 2a ⇒ 1 + 2a = 4
2a = 3; a = 32
Tx = L/B = 8×10^{3}/10^{6} = 8ms
T_{p}/T_{x} = 3/2; 2T_{p} = 3T_{x}
2T_{p} = 24ms
T_{p} = 12ms
Question 29 
The minimum number of JK flipflops required to construct a synchronous counter with the count sequence (0, 0, 1, 1, 2, 2, 3, 3, 0, 0,……) is ___________.
2  
3  
4  
5 
00
00
01
01
10
10
11
11
In the above sequence two flipflop's will not be sufficient. Since we are confronted with repeated sequence, we may add another bit to the above sequence.
000
100
001
101
010
110
011
111
Now and every count is unique, occurring only once.
So finally 3flip flops is required.
Question 30 
Match the following:
(P) Lexical analysis (1) Graph coloring (Q) Parsing (2) DFA minimization (R) Register allocation (3) Postorder traversal (S) Expression evaluation (4) Production tree
P2, Q3, R1, S4  
P2, Q1, R4, S3  
P2, Q4, R1, S3  
P2, Q3, R4, S1 
Q) Expression can be evaluated with postfix traversals.
R) Register allocation can be done by graph colouring.
S) The parser constructs a production tree.
Hence, answer is ( C ).
Question 31 
Consider two decision problems Q_{1}, Q_{2} such that Q_{1} reduces in polynomial time to 3SAT and 3 SAT reduces in polynomial time to Q_{2}. Then which one of following is consistent with the above statement?
Q_{1} is in NP, Q_{2} in NP hard  
Q_{1} is in NP, Q_{2} is NP hard  
Both Q_{1} and Q_{2} are in NP  
Both Q_{1} and Q_{2} are NP hard 
Q_{1}≤p 3SAT≤p Q_{2} ≤p ≤p hence → Q1 is in NP
but Q_{2} is not given in NP
Hence Q_{2} is in NPHard.
Question 32 
A computer system implements a 40bit virtual address, page size of 8 kilobytes, and a 128entry translation lookaside buffer (TLB organized into 32 sets each having four ways. Assume that the TLB tag does not store any process id. The minimum length of the TLB tag in bits is _________.
22  
23  
24  
25 
Question 33 
Consider the following C functions
int fun(int n) { int x = 1, k; if(n == 1) return x; for(k = 1; k < n; ++k) x = x + fun(k) * fun(n  k); return x; }
The return value of fun(5) is _______.
51  
52  
53  
54 
f(n) = 1; if n = 1
Question 34 
Consider the following statements:

I. The complement of every Turning decidable language is Turning decidable
II. There exists some language which is in NP but is not Turing decidable
III. If L is a language in NP, L is Turing decidable
Which of the above statements is/are True?
Only II  
Only III  
Only I and II  
Only I and III 
Turing decidable language are recursive language which is closed under complementation.
II. False.
All language which is in NP are turing decidable.
III. True.
Question 35 
The number of divisors of 2100 is ______.
36  
37  
38  
39 
= 2^{2}+3×5^{2}×7 (i.e., product of primes)
Then the number of divisions of 2100 is
(2+1)∙(1+1)∙(2+1)∙(1+1) i.e., (3)(2)(3)(2) i.e., 36.
Question 36 
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?
A tree has no bridges  
A bridge cannot be part of a simple cycle  
Every edge of a clique with size 3 is a bridge (A clique is any complete sub graph of a graph)  
A graph with bridges cannot have a cycle 
∴ (A) is false
Since, every edge in a complete graph kn(n≥3) is not a bridge ⇒
(C) is false
Let us consider the following graph G:
This graph has a bridge i.e., edge ‘e’ and a cycle of length ‘3’
∴ (D) is false
Since, in a cycle every edge is not a bridge
∴ (B) is true
Question 37 
Consider six memory partitions of sizes 200 KB, 400 KB, 600 KB, 500 KB, 300 KB and 250 KB, where KB refers to kilobyte. These partitions need to be allotted to four processes of sizes 357 KB, 210KB, 468 KB and 491 KB in that order. If the best fit algorithm is used, which partitions are NOT allotted to any process?
200KBand 300 KB  
200KBand 250 KB  
250KBand 300 KB  
300KBand 400 KB 
Since Best fit algorithm is used. So, process of size,
357KB will occupy 400KB
210KB will occupy 250KB
468KB will occupy 500KB
491KB will occupy 600KB
So, partitions 200KB and 300KB are NOT alloted to any process.
Question 38 
Which one of the following assertions concerning code inspection and code walkthrough is true?
Code inspection is carried out once the code has been unit tested  
Code inspection and code walkthrough are synonyms  
Adherence to coding standards is checked during code inspection
 
Code walkthrough is usually carried out by an independent test team 
Question 39 
Given below are some algorithms, and some algorithm design paradigms
A. Dijkstra’s Shortest Path 1. Divide and Conquer B. FloydWarshall algorithm to 2. Dynamic Programming compute all pairs shortest path C. Binary search on a sorted array 3. Greedy design D. Backtracking search on a graph 4. Depthfirst search 5. Breadthfirst search
Match the above algorithms on the left to the corresponding design paradigm they follow Codes:
1i, 2iii, 3i, 4v.  
1iii, 2iii, 3i, 4v.  
1iii, 2ii, 3i, 4iv.  
1iii, 2ii, 3i, 4v. 
(2) → All Pair shortest path algorithm is using Dynamic Programming technique. It takes worst case time complexity is O(V3) and worst case space complexity is O(V2).
→ The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).
→ A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm.
(3) Binary search on a sorted array:
Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
(4) Backtracking search on a graph uses Depthfirst search
Question 40 
Suppose you are provided with the following function declaration in the C programming language.
int partition (int a[], int n);
The function treats the first element of a[] as a pivot, and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part. The following partially given function in the C programming language is used to find the kth smallest element in an array a[ ] of size n using the partition function. We assume k ≤ n
int kth_smallest (int a[], int n, int k) { int left_end = partition (a, n); if (left_end+1==k) { return a [left_end]; } if (left_end+1 > k) { return kth_smallest (____________________); } else { return kth_smallest (____________________); } }
The missing argument lists are respectively
(a, left_end, k) and (a + left_end + 1, n – left_end – 1, k – left_end – 1)
 
(a, left_end, k) and (a, n – left_end – 1, k – left_end – 1)  
(a + left_end + 1, n – left_end – 1, k – left_end – 1) and (a, left_end, k)  
(a, n – left_end – 1, k – left_end – 1) and (a, left_end, k) 
Question 41 
Consider a typical disk that rotates at 15000 rotations per minute (RPM) and has a transfer rate of 50×106 bytes/sec. If the average seek time of the disk is twice the average rotational delay and the controller’s transfer time is 10 times the disk transfer time, the average time (in milliseconds) to read or write a 512byte sector of the disk is _____________.
6  
6.1  
6.2  
6.3 
1 rotation → 60 /15000 sec = 4 ms
∴ Average rotational delay = 1/2 × 4 ms = 2 ms
Average seek time = 2 × Average rotational delay
= 2 × 2 ms = 4 ms
Time to transfer 512 byte,
50 × 10^{6}B  1s
512 B  512B/ 50×10^{6}B/s = 0.01 ms
∴ Controllers transfer time
= 10 × Disk transfer time
= 10 × 0.01 ms
= 0.01 ms
∴ Avg. time = (4 + 2 + 0.1 + 0.01)ms
= 6.11 ms
Question 42 
Consider the intermediate code given below.

1. i = 1
2. j = 1
3. t1 = 5 * i
4. t2 = t1 + j
5. t3 = 4 * t2
6. t4 = t3
7. a[t4] = –1
8. j = j + 1
9. if j <= 5 goto(3)
10. i = i + 1
11. if i < 5 goto(2)
The number of nodes and edges in the controlflowgraph constructed for the above code, respectively, are
5 and 7  
6 and 7  
5 and 5  
7 and 8 
Question 43 
The number of minterms after minimizing the following Boolean expression is ______.
[D′ + AB′ + A′C + AC′D + A′C′D]′
1  
2  
3  
4 
[D' + AB' + A'C + AC'D + A'C'D]'
[D' + AB' + A'C + C'D (A + A')']' (since A+A' = 1)
[AB' + A'C + (D' + C') (D' + D)]' (since D' + D =1)
[AB' + A'C + D' + C']'
[AB' + (A' + C') (C + C') + D']'
[AB' + A' + C' + D']'
[(A + A') (A' + B') + C' + D']'
[A' + B' + C' + D']'
Apply demorgan's law,
ABCD
Question 44 
The number of onto function (surjective function) from set X = {1, 2, 3, 4} to set Y = {a, b, c} is ______.
36  
37  
38  
39 
m = 4, n = 3 ⇒ number of onto function is
Question 45 
Which of the following language is/are regular ?
 L1: {wxw^{R} ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} w^{R} is the reverse of string w
L2: {a^{n}b^{m} ⎪m ≠ n and m, n≥0}
L3: {a^{p}b^{q}c^{r} ⎪ p, q, r ≥ 0}
L_{1} and L_{3} only  
L_{2} only  
L_{2} and L_{3} only  
L_{3} only 
L_{2}: In this number of a's is dependent on number of b's. So PDA is needed.
L_{3}: Any number of a's followed by any number of b's followed by any number of c's. Hence Regular.
Question 46 
Consider a processor with byteaddressable memory. Assume that all registers, including Program Counter (PC) and Program Status Word (PSW), are of size 2 bytes. A stack in the main memory is implemented from memory location (0100)_{16} and it grows upward. The stack pointer (SP) points to the top element of the stack. The current value of SP is (016E)_{16}. The CALL instruction is of two words, the first word is the opcode and the second word is the starting address of the subroutine (one word = 2 bytes). The CALL instruction is implemented as follows:

• Store the current value of PC in the stack.
• Store the value of PSW register in the stack.
• Load the starting address of the subroutine in PC.
The content of PC just before the fetch of a CALL instruction is (5FA0)_{16}. After execution of the CALL instruction, the value of the stack pointer is
(016A)_{16}  
(016C)_{16}  
(0170)_{16}  
(0172)_{16} 
The CALL instruction is implemented as follows:
Store the current value of PC in the stack
pc is 2 bytes so when we store pc in stack SP is increased by 2 so current value of SP is (016E)_{16}+2 Store the value of PSW register in the stack
psw is 2 bytes, so when we store psw in stack SP is increased by 2
so current value of SP is (016E)_{16}+2+2 = (0172)_{16}
Question 47 
The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1) * (10) is __________.
3  
4  
5  
6 
No. of states in minimal DFA is 3.
Question 48 
Host A sends a UDP datagram containing 8880 bytes of user data to host B over an Ethernet LAN. Ethernet frames may carry data up to 1500 bytes (i.e. MTU = 1500 bytes). Size of UDP header is 8 bytes and size of IP heard is 20 bytes. There is no option field in IP header. How many total number of IP fragments will be transmitted and what will be the contents of offset field in the last fragment?
6 and 925  
6 and 7400  
7 and 1110  
7 and 8880 
Total Size excluding IP Header = 8888 bytes.
Number of fragments = ceil(8880+ UDP or TCP header /1500IP header)
= ceil(8880+8 /150020)
= ceil(8888/1480)
= 7
Offset of last fragment = (MTUIP header ) *( number of fragments 1) / scaling factor = 1110 (scaling factor of 8 is used in offset field).
= (150020)* (71)/8
= 1110
Question 49 
Consider the following routing table at an IP router:
For each IP address in Group I identify the correct choice of the next hop from Group II using the entries from the routing table above.
Group I Group II (i) 128.96.171.92 (a) Interface 0 (ii) 128.96.167.151 (b) Interface 1 (iii) 128.96.163.121 (c) R2 (iv) 128.96.165.121 (d) R3 (e) R4
ia, iic, iiie, ivd  
ia, iid, iiib, ive  
ib, iic, iiid, ive  
ib, iic, iiie, ivd 
Question 50 
Consider two relations R_{1}(A,B) with the tuples (1,5), (3,7) and R_{2}(A,C) = (1,7), (4,9). Assume that R(A,B,C) is the full natural outer join of R_{1} and R_{2}. Consider the following tuples of the form (A,B,C): a = (1.5,null), b = (1,null,7), c = (3,null,9), d = (4,7,null), e = (1,5,7), f = (3,7,null), g = (4,null,9). Which one of the following statements is correct?
R contains a,b,e,f,g but not c, d.
 
R contains all of a,b,c,d,e,f,g  
R contains e,f,g but not a,b  
R contains e but not f,g 
⋆ So, from the above resultant table, R contains e, f, g only but not a, b.
Question 51 
Consider a simple checkpointing protocol and the following set of operations in the log.

(start, T_{4}); (write, T_{4}, y, 2, 3); (start, T_{1}); (commit, T_{4}); (write, T_{1}, z, 5, 7);
(checkpoint);
(start, T_{2}); (write, T_{2}, x, 1, 9); (commit, T_{2}); (start, T_{3}); (write, T_{3}, z, 7, 2);
If a crash happens now and the system tries to recover using both undo and redo operations, what are the contents of the undo list and the redo list
Undo T_{3}, T_{1}; Redo T_{2}  
Undo T_{3}, T_{1}; Redo T_{2}, T_{4}  
Undo: none; redo: T_{2}, T_{4}, T_{3}, T_{1}  
Undo T_{3}, T_{1}; T_{4}; Redo: T_{2}

Question 52 
A computer system implements 8 kilobyte pages and a 32bit physical address space. Each page table entry contains a valid bit, a dirty bit, three permission bits, and the translation. If the maximum size of the page table of a process is 24 megabytes, the length of the virtual address supported by the system is ________ bits.
36  
37  
38  
39 
PAS = 32 bit
∴ No. of frames =PA/Page size = 2^{32} / 2^{13} = 2^{19}
Also, it is given that each page table entry contains a valid bit, a dirty bit, 3 permission bits:
= 5 bits reserved
So one Page table entry size is
= 19+5 = 24 bits = 3 bytes
Now, Page table size = No. of entries × Entry size
24 × 2^{20} = No. of entries × 3
No. of entries = 8 × 2^{20} = 2 ^{23}
∴ Virtual Address size = No. of entries × Page size = 2^{23} × 2^{13} = 2^{36}
∴ Virtual Address Space = 36 bits
Question 53 
Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?
h(i) = i^{2} mod 10  
h(i) = i^{3} mod 10  
h(i) = (11 *i^{2}) mod 10  
h(i) = (12 * i) mod 10 
Question 54 
Assume that the bandwidth for a TCP connection is 1048560 bits/sec. Let α be the value of RTT in milliseconds (rounded off to the nearest integer) after which the TCP window scale option is needed. Let β be the maximum possible window size the window scale option. Then the values of α and β are
63 milliseconds, 65535×2^{14}  
63 milliseconds, 65535×2^{16}  
500 milliseconds, 65535×2^{14}  
500 milliseconds, 65535×2^{16} 
The wrap around time for given link = 1048560 * α. The TCP window scale option is an option to increase the receive window size. TCP allows scaling of windows when wrap around time > 65,535.
==> 1048560 * α > 65,535*8 bits
==> α = 0.5 sec = 500 mss
Scaling is done by specifying a one byte shift count in the header options field. The true receiver window size is left shifted by the value in shift count. A maximum value of 14 may be used for the shift count value. Therefore maximum window size with scaling option is 65535 × 2^{14}.
Question 55 
A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with ∞, and hence there cannot be any entry to the right of, or below a ∞. The following Young tableau consists of unique entries.
1 2 5 14 3 4 6 23 10 12 18 25 31 ∞ ∞ ∞
When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a ∞). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is ____________.
4  
5  
6  
7 
Question 56 
A half adder is implemented with XOR and AND gates. A full adder is implemented with two half adders and one OR gate. The propagation delay of an XOR gate is twice that of an AND/OR gate. The propagation delay of an AND/OR gate is 1.2 microseconds. A 4bit ripplecarry binary adder is implemented by using four full adders. The total propagation time of this 4bit binary adder in microseconds is ____________.
19.1  
19.2  
18.1  
18.2 
Here, each Full Adder is taking 4.8 microseconds. Given adder is a 4 Bit Ripple Carry Adder. So it takes 4*4.8 = 19.2 microseconds.
Question 57 
Consider the sequence of machine instructions given below:
MUL R5, R0, R1 DIV R6, R2, R3 ADD R7, R5, R6 SUB R8, R7, R4
In the above sequence, R0 to R8 are general purpose registers. In the instructions shown, the first register stores the result of the operation performed on the second and the third registers. This sequence of instructions is to be executed in a pipelined instruction processor with the following 4 stages: (1) Instruction Fetch and Decode (IF), (2) Operand Fetch (OF), (3) Perform Operation (PO) and (4) Write back the Result (WB). The IF, OF and WB stages take 1 clock cycle each for any instruction. The PO stage takes 1 clock cycle for ADD or SUB instruction, 3 clock cycles for MUL instruction and 5 clock cycles for DIV instruction. The pipelined processor uses operand forwarding from the PO stage to the OF stage. The number of clock cycles taken for the execution of the above sequence of instructions is
11  
12  
13  
14 
O ⇒ Operand Fetch
P ⇒ Perform the operation
W ⇒ write back the result
Question 58 
Perform the following operations on the matrix
 (i) add the third row to the second row
(ii) Subtract the third column from the first column
The determinant of the resultant matrix is ________.
0  
1  
2  
3 
Method 2: Determinant is unaltered by the operations (i) and (ii)
∴ Determinant of the resultant matrix = Determinant of the given matrix
(Since C_{1}, C_{3} are proportional i.e., C_{3} = 15C_{1})
Question 59 
Which one of the following well formed formulae is a tautology?
∀x ∃y R(x,y) ↔ ∃y ∀x R(x,y)
 
(∀x [∃y R(x,y) → S(x,y)]) → ∀x∃y S(x,y)
 
[∀x ∃y (P(x,y) → R(x,y)] ↔ [∀x ∃y (¬ P(x,y)∨R(x,y)]  
∀x ∀y P(x,y) → ∀x ∀y P(y,x) 
[∀x ∃y (P(x,y) → R(x,y)] ↔ [∀x ∃y (¬ P(x,y)∨R(x,y)] is a tautology.
Question 60 
A graph is selfcomplementary if it is isomorphic to its complement for all selfcomplementary graphs on n vertices, n is
A multiple of 4  
Even  
Odd  
Congruent to 0 mod 4, or, 1 mod 4

Question 61 
The secant method is used to find the root of an equation f(x) = 0. It is started from two distinct estimates x_{a} and x_{b} for the root. It is an iterative procedure involving linear interpolation to a root. The iteration stops if f(x_{b}) is very small and then x_{b} is the solution. The procedure is given below. Observe that there is an expression which is missing and is marked by? Which is the suitable expression that is to be put in place of? So that it follows all steps of the secant method?
Secant
Initialize: x_{a}, x_{b}, ε, N // ε = convergence indicator f_{b} = f(x_{b}) i = 0 while (i < N and f_{b} > ε) do i = i + 1 // update counter x_{t} = ? // missing expression for // intermediate value x_{a} = x_{b} // reset x_{a} x_{b} = x_{t} // reset x_{b} f_{b} = f(x_{b}) // function value at new x_{b} end while if f_{b} > ε then // loop is terminated with i = N write “Nonconvergence” else write “return x_{b}” end if
x_{b} – (f_{b}–f(x_{a}))f_{b} /(x_{b}–x_{a})  
x_{a} – (f_{a}–f(x_{a}))f_{a} /(x_{b}–x_{a})  
x_{b} – (x_{b}–x_{a})f_{b} /(f_{b}–f(x_{a}))  
x_{a} – (x_{b}–x_{a}) f_{a} /(f_{b}–f(x_{a})) 
The first two iterations of the secant method. The red curve shows the function f and the blue lines are the secants. For this particular case, the secant method will not converge.
Question 62 
Consider the C program below.
#includeint *A, stkTop; int stkFunc (int opcode, int val) { static int size=0, stkTop=0; switch (opcode) { case 1: size = val; break; case 0: if (stkTop < size ) A[stkTop++]=val; break; default: if (stkTop) return A[stkTop]; } return 1; } int main() { int B[20]; A=B; stkTop = 1; stkFunc (1, 10); stkFunc (0, 5); stkFunc (0, 10); printf ("%dn", stkFunc(1, 0)+ stkFunc(1, 0)); }
The value printed by the above program is ___________
2  
2  
1  
15 
When next time stkFunc (0,5) is called then, inside Switch(opcode), the control will go to Case0, where A[0] = 5 and stkTop = 0+1 = 1.
When next time stkFunc (0,10) is called then, inside Switch (opcode), the control will go to Case '0', where A[1] = 10 and stkTop = 1+1 = 2.
When next time stkFunc(1,0) is called from inside the printf statement, then inside Switch(opcode), the control will go to default and stkTop = 21 = 1 and value of A[1] will get returned, i.e., 10.
When next time stkFunc(1,0) is called from inside the printf statement, then inside Switch(opcode), the control will go to default and stkTop = 11 = 0 and value of A[0] will get returned, i.e., 5.
Finally the two values 10 & 5 will be added and printed.
Question 63 
Let f(x) = x ^{(1/3)} and A denote the area of the region bounded bu f(x) and the Xaxis, when x varies from 1 to 1. Which of the following statements is/are TRUE?

I) f is continuous in [1,1]
II) f is not bounded in [1,1]
III) A is nonzero and finite
II only  
III only  
II and III only  
I, II and III 
∴ f is not bounced in [1, 1] and hence f is not continuous in [1, 1].
∴ Statement II & III are true.
Question 64 
Let X and Y denote the sets containing 2 and 20 distinct objects respectively and F denote the set of all possible functions defined from X to Y. Let f be randomly chosen from F. The probability of f being onetoone is ______.
0.95  
0.96  
0.97  
0.98 
Number of functions from X to Y is 20^{2} i.e., 400 and number of oneone functions from X to Y is ^{20}P_{2} i.e., 20×19 = 380
∴ Probability of a function f being oneone is 380/400 i.e., 0.95
Question 65 
Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X_{0}, X_{1} and X_{2} generated by the corresponding nonterminals of a regular grammar. X_{0}, X_{1} and X_{2} are related as follows:

X_{0} = 1 X_{1}
X_{1} = 0 X_{1} + 1 X_{2}
X_{2} = 0 X_{1} + {λ}
Which one of the following choices precisely represents the strings in X_{0}?
10(0* + (10*)* 1  
10(0* + (10)*)* 1  
1(0 + 10)* 1  
10(0 + 10)* 1 + 110(0 + 10)* 1 
From the given diagram we can write,
X_{0} = 1(0+10)* 1