GATE 2015 (Set2)
Question 1 
Statement I alone is not sufficient  
Statement II alone is not sufficient  
Either I or II alone is sufficient  
Both statements I and II together are not sufficient. 
Question 1 Explanation:
StatementI:
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.
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

Question 2 Explanation:
f(x) = 1  x on 1 ≤ x ≤ 1
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.
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 3 Explanation:
apparel clothing, especially outerwear; garments; attire; raiment
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 4 Explanation:
personnel people employed in an organization or engaged in an organized undertaking such as military service.
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 5 Explanation:
We compltetely forgot our friend's birthday and we just don't know how to make it up to him.
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.

Question 7 Explanation:
(B) there was no needed information
(C) not really useful
(D) would not have been
(C) not really useful
(D) would not have been
Question 8 
I only  
I and II  
II and III  
I and III 
Question 8 Explanation:
If any set of numbers are in a arithmetic sequence and if a common number if added (or) subtracted from each of these numbers, the new set will also be in arithmetic sequence.
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.
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 
8  
9  
7  
6 
Question 9 Explanation:
h(2,5,7,3) = remainder of (7×3)/(2×5)
= 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
= 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 10 Explanation:
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 11 Explanation:
Consider first three element of the list, atleast one of them will be neither minimum nor maximum.
∴ Θ(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 
Question 12 Explanation:
Reflexive:
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.
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 
Atomicity  
Consistency  
Isolation  
Durability 
Question 13 Explanation:
The consistency property ensures that the database remains in a consistent state before the (start of the transaction and after the transaction is over. Here sum of the accounts x & y should remain same before & after execution of the given transactions which refers to the consistency of the sum.
Question 14 
A binary tree T has 20 leaves. The number of nodes in T having two children is _________.
19  
20  
21  
22 
Question 14 Explanation:
Let the number of vertices of a binary tree with „p‟ leaves be n then the tree has
(i) p vertices (i.e., leaves) of degree 1
(ii) one vertex (i.e.., root of T) of degree 2
(iii) 'n p1' (i.e., interval) vertices of degree 3
(iv) n 1 edges
∴ By Handshaking theorem,
p×1+1×2+(np1)×3=2(n1)
⇒n=2p1
=39 as p=20
∴ np=19 vertices have exactly two children
(i) p vertices (i.e., leaves) of degree 1
(ii) one vertex (i.e.., root of T) of degree 2
(iii) 'n p1' (i.e., interval) vertices of degree 3
(iv) n 1 edges
∴ By Handshaking theorem,
p×1+1×2+(np1)×3=2(n1)
⇒n=2p1
=39 as p=20
∴ np=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}) 
Question 15 Explanation:
Basic cocomo model takes the form
Effort applied (E)=a_{b}(KLOC)b_{b}
Development time (D)=c_{b}(E)d_{b}
Effort applied (E)=a_{b}(KLOC)b_{b}
Development time (D)=c_{b}(E)d_{b}
Question 16 
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

Question 16 Explanation:
Let p: candidate 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
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 17 Explanation:
Average read access time =[(0.8)(5)+(0.2)(50)]ns=4+10=14ns
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 18 Explanation:
Let's assume that each process request 2 resources each. Now there are total 6 identical resources available. Give 1 resource to every processes then there will be deadlock because now each process will wait for another resource which is not available, so there will be deadlock. Since there are total 6 resources so for deadlock to be possible there should be 6 processes available. Hence, the value of N is 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 19 Explanation:
Since left and right subtree is already a heap. So we can apply Heapify (node) which take log n time.
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

Question 20 Explanation:
Optional (A) is not true when CFG contains cycle
Option (B) is false as CFG can contain cycle
Option (D) is false as a single node can contain block of statements.
Option (B) is false as CFG can contain cycle
Option (D) is false as a single node can contain block of statements.
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 22 Explanation:
SRS is a description of a software system to be developed, laying out functional & nonfunctional requirements and may include a set of use cases that describe interactions the user will have with the 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 23 Explanation:
Question 24 
6  
7  
8  
9 
Question 24 Explanation:
Characteristic equation is 4λ 5 2 1λ =0
⇒ λ^{2}5λ6=0⇒(λ6)(λ+1)=0⇒λ=6,1
∴ Larger eigen value is 6
⇒ λ^{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 25 Explanation:
Cardinality of the power set of {0, 1, 2, … , 10} is 2^{11} i.e., 2048.
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

Question 26 Explanation:
An HTTP cookie (also called web cookie, Internet cookie, browser cookie, or simply cookie) is a small piece of data sent from a website and stored on the user's computer by the user's web browser while the user is browsing.
Cookies are not piece of code, they are just strings typically in the form of key value pairs.
Question 27 
ABCD EFGH
 
ABCD  
HGFE DCBA
 
DCBA 
Question 27 Explanation:
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 
Question 28 Explanation:
Given, B=10^{6}bps
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
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 
Question 29 Explanation:
Count sequence mentioned is
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.
Now and every count is unique, occuring only once.
So finally 3flip flops is required.
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.
Now and every count is unique, occuring only once.
So finally 3flip flops is required.
Question 30 
P2,Q3,R1,S4  
P2,Q1,R4,S3  
P2,Q4,R1,S3  
P2,Q3,R4,S1 
Question 30 Explanation:
P) Lexical analysis is related with FA and Regular expressions.
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 ).
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

Question 31 Explanation:
3SAT ⇒ NPC problem
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.
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 32 Explanation:
22 bits
Question 33 
51  
52  
53  
54 
Question 33 Explanation:
Recurrence Relation is
f(n) = 1; if n = 1
f(n) = 1; if n = 1
Question 34 
Only II  
Only III  
Only I and II  
Only I and III 
Question 34 Explanation:
I. True.
Turing decidable language are recursive language which is closed under complementation.
II. False.
All language which is in NP are turing decidable.
III. True.
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 
Question 35 Explanation:
Let N = 2100
=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
=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

Question 36 Explanation:
Since, every edge in a tree is bridge
∴ (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
∴ (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 
Question 37 Explanation:
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 38 Explanation:
Note: Out of syllabus.
Question 39 
1i, 2iii, 3i, 4v.  
1iii, 2iii, 3i, 4v.  
1iii, 2ii, 3i, 4iv.  
1iii, 2ii, 3i, 4v. 
Question 39 Explanation:
(1) Dijkstra’s Shortest Path using to find single source shortest path. It is purely based on Greedy technique because it always selects shortest path among all.
(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
(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 
(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×10^{6} 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 
Question 41 Explanation:
15000 rotations → 60 sec
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
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 
5 and 7  
6 and 7  
5 and 5  
7 and 8 
Question 42 Explanation:
Question 43 
1  
2  
3  
4 
Question 43 Explanation:
Lets simplify it
[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
[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 
Question 44 Explanation:
Number of onto function from set X to set Y with X = m, Y = n is
m = 4, n = 3 ⇒ number of onto function is
m = 4, n = 3 ⇒ number of onto function is
Question 45 
L_{1} and L_{3} only
 
L_{2} only
 
L_{2} and L_{3} only
 
L_{3} only

Question 45 Explanation:
L_{1}: All strings of length 3 or more with same start and end symbol, as everything in middle is consumed by x as per the definition.
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.
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 
(016A)_{16}  
(016C)_{16}  
(0170)_{16}  
(0172)_{16} 
Question 46 Explanation:
Here the memory is byteaddressable.
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}
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 
Question 47 Explanation:
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 
Question 48 Explanation:
UDP data = 8880 bytes, UDP header = 8 bytes, IP Header = 20 bytes
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
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 
ia, iic, iiie, ivd  
ia, iid, iiib, ive  
ib, iic, iiid, ive  
ib, iic, iiie, ivd 
Question 49 Explanation:
Do the AND operation of group I IP address with Netmask and compare the result with network number. if it match with network number, forward packet through that interface.
Ex: 128.96.167.151 AND 255.255.254.0 = 128.96.166.0
Therefore packet will forward through R2
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

Question 50 Explanation:
⋆ So, from the above resultant table, R contains e, f, g only but not a, b.
Question 51 
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 51 Explanation:
As T_{1} & T_{3} are not yet committed they must be undone. The transactions which are after the latest checkpoint must be redone. So T_{2} must be redone. No need to redo the records which are before the last checkpoint, so T_{4} need not be redone.
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 
Question 52 Explanation:
Given page size = 8KB = 2^{13}B
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
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 53 Explanation:
If we take first 10 elements, number of collisions taken by the hash function given by option (B) is less when compared to others.
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}

Question 54 Explanation:
TCP header sequence number field consist 16 bits. The maximum number of sequence numbers possible = 2^16 = 65,535.
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
.
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 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 
Question 56 Explanation:
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 
11  
12  
13  
14 
Question 57 Explanation:
I ⇒ Instruction Fetch and Decode
O ⇒ Operand Fetch
P ⇒ Perform the operation
W ⇒ write back the result
O ⇒ Operand Fetch
P ⇒ Perform the operation
W ⇒ write back the result
Question 58 
0  
1  
2  
3 
Question 58 Explanation:
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)

Question 59 Explanation:
Since P→R=¬P∨R
[∀x ∃y (P(x,y)→R(x,y)]↔[∀x ∃y ( ¬ P(x,y)∨R(x,y)] is a tautology.
[∀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 60 Explanation:
An n vertex selfcomplementary graph has exactly half number of edges of the complete graph i.e., n(n1)/4 edges. Since n(n – 1) must be divisible by 4, n must be congruent to 0 or 1 module 4.
Question 61 
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})) 
Question 61 Explanation:
The solution for this question is direct formula of secant method. In numerical analysis, the secant method is a rootfinding algorithm that uses a succession of roots of secant lines to better approximate a root of a function f. The secant method can be thought of as a finite difference approximation of Newton's method. However, the method was developed independently of Newton's method, and predates it by over 3,000 years.
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.
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 
2  
2  
1  
15 
Question 62 Explanation:
When first time stkFunc (1,10) will be called then, inside Switch(opcode) the control will go to CaseI, where size=10.
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.
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 
II only  
III only  
II and III only  
I, II and III 
Question 63 Explanation:
Since f(0)→∞
∴ f is not bounced in [1, 1] and hence f is not continuous in [1, 1].
∴ Statement II & III are true.
∴ 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 YY. Let f be randomly chosen from F. The probability of f being onetoone is ______.
0.95  
0.96  
0.97  
0.98 
Question 64 Explanation:
X = 2, Y = 20
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
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 
10(0* + (10*)* 1  
10(0* + (10)*)* 1  
1(0 + 10)* 1  
10(0 + 10)* 1 + 110(0 + 10)* 1 
Question 65 Explanation:
Convert the given transitions to a state diagram.
From the given diagram we can write,
X_{0} = 1(0+10)* 1
From the given diagram we can write,
X_{0} = 1(0+10)* 1
There are 65 questions to complete.