## GATE 2015 -(Set-2)

 Question 1

 A Statement I alone is not sufficient B Statement II alone is not sufficient C Either I or II alone is sufficient D Both statements I and II together are not sufficient.
Aptitude       Numerical
Question 1 Explanation:
Statement-I:
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.
Statement-II:
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.
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
 A 0, -1 B -1, 0 C 0, 1 D -1, 2
Aptitude       Numerical
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.
 Question 3
A generic term that include various items of clothing such as a skirt, a pair of trousers and a shirt is
 A fabric B textile C fibre D apparel
Aptitude       Verbal
Question 3 Explanation:
apparel- clothing, especially outerwear; garments; attire; raiment
 Question 4
Choose the statement where underlined word is used correctly.
 A The industrialist load a personnel jet. B I write my experience in my personnel diary. C All personnel are being given the day off. D Being religious is a personnel aspect.
Aptitude       Verbal
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.
 A Completely forgot - - - don’t just know B Forgot completely - - - don’t just know C Completely forgot - - - just don’t know D Forgot completely - - - just don’t know
Aptitude       Verbal
Question 5 Explanation:
We compltetely forgot our friend's birthday and we just don't know how to make it up to him.
 Question 6

 A B C D
Aptitude       Numerical
Question 6 Explanation:
 Question 7
Out of the following four sentences, select the most suitable sentence with respect to grammar and usage.
 A Since the report lacked needed information, it was of no use to them. B The report was useless to them because there were no needed information in it. C Since the report did not contain the needed information, it was not real useful to them D Since the report lacked needed information, it would not have been useful to them.
Aptitude       Verbal
Question 7 Explanation:
(B) there was no needed information
(C) not really useful
(D) would not have been
 Question 8
 A I only B I and II C II and III D I and III
Aptitude       Numerical
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.
 Question 9

 A 8 B 9 C 7 D 6
Aptitude       Numerical
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
 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?
 A 5.34 B 6.74 C 28.5 D 45.49
Aptitude       Numerical
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
 A Θ(nlog n) B Θ(n) C Θ(log n) D Θ(1)
Aptitude       Numerical
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?
 A R is symmetric and reflexive but not transitive B R is reflexive but not symmetric and not transitive C R is transitive but not reflexive and not symmetric D R is symmetric but not reflexive and not transitive
Engineering-Mathematics       Set-Theory
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.
 Question 13
 A Atomicity B Consistency C Isolation D Durability
Database-Management-System       Transactions
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 _________.
 A 19 B 20 C 21 D 22
Data-Structures       Binary-Trees
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- 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 person-months, D is the development time in chronological months, KLOC is the estimated number of delivered lines of code (in thousands) and abbbcbdb have their usual meanings. The basic COCOMO equations are of the form
 A E=a b(KLOC)exp (b b , D=c b(E)exp (d b) B E=a b(KLOC)exp (b b , D=c b(E)exp (d b) C E=a bexp⁡(b b), D=c b(KLOC)exp (d b) D E=a bexp(D b),D=c b(KLOC)exp (b b)
Software-Engineering       COCOMO-Model
Question 15 Explanation:
Basic cocomo model takes the form
Effort applied (E)=ab(KLOC)bb
Development time (D)=cb(E)db
 Question 16

 A If a person is known to corrupt, he is kind B If a person is not known to be corrupt, he is not kind C If a person is kind, he is not known to be corrupt D If a person is not kind, he is not known to be corrupt
Engineering-Mathematics       Prepositional-Logic
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
 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  _______.
 A 14 B 15 C 16 D 17
Computer-Organization       Cache
Question 17 Explanation:
 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?

 A 1 B 2 C 3 D 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 max-heaps. The lower bound for the number of operations to convert the tree to a heap is
 A Ω(logn) B Ω(n) C Ω(nlog n) D Ω(n2)
Data-Structures       Heap-Tree
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 abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?
 A In both AST and CFG, let node, N2 be the successor of node N1. In the input program, the code corresponding to N2 is present after the code corresponding in N1. B For any input program, neither AST nor CFG will contain a cycle C The maximum number of successors of a node in an AST and a CFG depends on the input program D Each node is AST and CFG corresponds to at most one statement in the input program
Compiler-Design       Syntax-tree-and-context-flow-graph
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.
 Question 21
 A 6 B 7 C 5 D 9
Database-Management-System       B+-Trees
Question 21 Explanation:
 Question 22
A software requirements specification (SRS) document should avoid discussing which one of the following?
 A User interface issues B Non-functional requirements C Design specification D Interfaces with third party software
Software-Engineering       SRS
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.
 A listen, accept, bind recv B bind, listen, accept, recv C bind, accept, listen, recv D accept, listen, bind recv
Computer-Networks       Sockets
Question 23 Explanation:
 Question 24
 A 6 B 7 C 8 D 9
Engineering-Mathematics       Linear-Algebra
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
 Question 25
The cardinality of the power set of {0, 1, 2, … 10} is _________
 A 2046 B 2047 C 2048 D 2049
Engineering-Mathematics       Set-Theory
Question 25 Explanation:
Cardinality of the power set of {0, 1, 2, … , 10} is 211 i.e., 2048.
 Question 26
Which one of the following statements is NOT correct about HTTP cookies?
 A A cookie is a piece of code that has the potential to compromise the security of an internet user B A cookie gains entry to the user’s work area through an HTTP header C A cookie has an expiry date and time D 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

 A ABCD EFGH B ABCD C HGFE DCBA D DCBA
Programming       Programming
Question 27 Explanation:

if condition fails
& returns controls
∴ DCBA will be pointed
 Question 28
A link has a transmission speed of 106 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 stop-and-wait protocol in this setup is exactly 25%. The value of the one-way propagation delay (in milliseconds) is ___________.
 A 12 B 13 C 14 D 15
Computer-Networks       Stop-and-Wait-ARQ
Question 28 Explanation:
Given, B=106bps
L=1000
η=25%
Tp=?
In stop-and-wait, η=1/1+2a
⇒1/4=1/1+2a⇒1+2a=4
2a=3;a=32
Tx=L/B=8×103/106=8ms
Tp/Tx=3/2;2Tp=3Tx
2Tp=24ms
Tp=12ms
 Question 29
The minimum number of JK flip-flops required to construct a synchronous counter with the count sequence (0, 0, 1, 1, 2, 2, 3, 3, 0, 0,…….) is ___________.
 A 2 B 3 C 4 D 5
Digital-Logic-Design       Sequential-Circuits
Question 29 Explanation:
Count sequence mentioned is
00
00
01
01
10
10
11
11
In the above sequence two flip-flop'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 3-flip flops is required.
 Question 30

 A P-2,Q-3,R-1,S-4 B P-2,Q-1,R-4,S-3 C P-2,Q-4,R-1,S-3 D P-2,Q-3,R-4,S-1
Compiler-Design       Compilers
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 ).
 Question 31
Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3 -SAT reduces in polynomial time to Q2. Then which one of following is consistent with the above statement?
 A Q1 is in NP, Q2 in NP hard B Q1 is in NP, Q2 is NP hard C Both Q1 and Q2 are in NP D Both Q1 and Q2 are NP hard
Theory-of-Computation       P-NP
Question 31 Explanation:
3-SAT ⇒ NPC problem
Q1≤p 3-SAT≤p Q2 ≤p ≤p hence → Q1 is in NP
but Q2 is not given in NP
Hence Q2 is in NP-Hard.
 Question 32
A computer system implements a 40-bit virtual address, page size of 8 kilobytes, and a 128-entry translation look-aside 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 _________.
 A 22 B 23 C 24 D 25
Operating-Systems       Virtual Memory
Question 32 Explanation:
22 bits
 Question 33

 A 51 B 52 C 53 D 54
Programming       Programming
Question 33 Explanation:
Recurrence Relation is
f(n) = 1; if n = 1
 Question 34

 A Only II B Only III C Only I and II D Only I and III
Theory-of-Computation       Decidability-and-Undecidability
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.
 Question 35
The number of divisors of 2100 is ______.
 A 36 B 37 C 38 D 39
Engineering-Mathematics       Combinatorics
Question 35 Explanation:
Let N = 2100
=22+3×52×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 A tree has no bridges B A bridge cannot be part of a simple cycle C Every edge of a clique with size 3 is a bridge (A clique is any complete sub graph of a graph) D A graph with bridges cannot have a cycle
Engineering-Mathematics       Graph-Theory
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
 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?
 A 200KBand 300 KB B 200KBand 250 KB C 250KBand 300 KB D 300KBand 400 KB
Engineering-Mathematics       Memory-Management
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?
 A Code inspection is carried out once the code has been unit tested B Code inspection and code walkthrough are synonyms C Adherence to coding standards is checked during code inspection D Code walkthrough is usually carried out by an independent test team
Software-Engineering       SE
Question 38 Explanation:
Note: Out of syllabus.
 Question 39
 A 1-i, 2-iii, 3-i, 4-v. B 1-iii, 2-iii, 3-i, 4-v. C 1-iii, 2-ii, 3-i, 4-iv. D 1-iii, 2-ii, 3-i, 4-v.
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(|V|3) and worst case space complexity is O(|V|2).
→ 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 Depth-first search
 Question 40

 A (a, left_end, k) and (a + left_end + 1, n – left_end – 1, k – left_end – 1) B (a, left_end, k) and (a, n – left_end – 1, k – left_end – 1) C (a + left_end + 1, n – left_end – 1, k – left_end – 1) and (a, left_end, k) D (a, n – left_end – 1, k – left_end – 1) and (a, left_end, k)
Algorithms       Partitioning-Algorithm
 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 512-byte sector of the disk is _____________.
 A 6 B 6.1 C 6.2 D 6.3
Algorithms       Secondary-Storage
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 × 106B ------- 1s
512 B ------- 512B/ 50×106B/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

 A 5 and 7 B 6 and 7 C 5 and 5 D 7 and 8
Compiler-Design       Control-Flow-Graph
Question 42 Explanation:
 Question 43

 A 1 B 2 C 3 D 4
Digital-Logic-Design       Boolean-Algebra
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 de-morgan'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 ______.
 A 36 B 37 C 38 D 39
Engineering-Mathematics       Relations-and-Functions
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
 Question 45

 A L1 and L3 only B L2 only C L2 and L3 only D L3 only
Theory-of-Computation       Regular-Language
Question 45 Explanation:
L1: 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.
L2: In this number of a's is dependent on number of b's. So PDA is needed.
L3: Any number of a's followed by any number of b's followed by any number of c's. Hence Regular.
 Question 46

 A (016A)16 B (016C)16 C (0170)16 D (0172)16
Computer-Organization       Machine-Instructions
Question 46 Explanation:
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 __________
 A 3 B 4 C 5 D 6
Theory-of-Computation       DFA
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?
 A 6 and 925 B 6 and 7400 C 7 and 1110 D 7 and 8880
Computer-Networks       IPv4-an-Fragmentation
Question 48 Explanation:
UDP data = 8880 bytes, UDP header = 8 bytes, IP Header = 20 bytes
Total Size excluding IP Header = 8888 bytes.
= ceil(8880+8 /1500-20)
= ceil(8888/1480)
= 7
Offset of last fragment = (MTU-IP header ) *( number of fragments -1) / scaling factor = 1110 (scaling factor of 8 is used in offset field).
=(1500-20)* (7-1)/8
=1110
 Question 49
 A i-a, ii-c, iii-e, iv-d B i-a, ii-d, iii-b, iv-e C i-b, ii-c, iii-d, iv-e D i-b, ii-c, iii-e, iv-d
Computer-Networks       Subnetting
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 R1(A,B) with the tuples (1,5), (3,7) and R2(A,C) = (1,7), (4,9). Assume that R(A,B,C) is the full natural outer join of R1 and R2. 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?
 A R contains a,b,e,f,g but not c, d. B R contains all of a,b,c,d,e,f,g C R contains e,f,g but not a,b D R contains e but not f,g
Database-Management-System       Relational-Algebra
Question 50 Explanation:

⋆ So, from the above resultant table, R contains e, f, g only but not a, b.
 Question 51
 A Undo T3, T1; Redo T2 B Undo T3, T1; Redo T2, T4 C Undo: none; redo: T2, T4, T3, T1 D Undo T3, T1; T4; Redo: T2
Database-Management-System       Transactions
Question 51 Explanation:
As T1 & T3 are not yet committed they must be undone. The transactions which are after the latest checkpoint must be redone. So T2 must be redone. No need to redo the records which are before the last checkpoint, so T4 need not be redone.
 Question 52
A computer system implements 8 kilobyte pages and a 32-bit 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.
 A 36 B 37 C 38 D 39
Operating-Systems       Virtual Memory
Question 52 Explanation:
Given page size = 8KB = 213B
PAS = 32 bit
∴ No. of frames =PA/Page size = 232 / 213 = 219
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 × 220 = No. of entries × 3
No. of entries = 8 × 220 = 2 23
∴ Virtual Address size = No. of entries × Page size = 223 × 213 = 236
∴ 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?
 A h(i) = i2 mod 10 B h(i) = i3 mod 10 C h(i) = (11 *i2) mod 10 D h(i) = (12 * i) mod 10
Data-Structures       Hashing
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
 A 63 milliseconds, 65535×214 B 63 milliseconds, 65535×216 C 500 milliseconds, 65535×214 D 500 milliseconds, 65535×216
Data-Structures       TCP
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
.
 Question 55

 A 4 B 5 C 6 D 7
Data-Structures       Arrays
Question 55 Explanation:
 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 4-bit ripple-carry binary adder is implemented by using four full adders. The total propagation time of this 4-bit binary adder in microseconds is ____________.
 A 19.1 B 19.2 C 18.1 D 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

 A 11 B 12 C 13 D 14
Computer-Organization       Pipelining
Question 57 Explanation:
I ⇒ Instruction Fetch and Decode
O ⇒ Operand Fetch
P ⇒ Perform the operation
W ⇒ write back the result
 Question 58

 A 0 B 1 C 2 D 3
Engineering-Mathematics       Linear-Algebra
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 C1,C3 are proportional i.e., C3=15C1)
 Question 59
Which one of the following well formed formulae is a tautology?
 A ∀x ∃y R(x,y)↔ ∃y ∀x R(x,y) B (∀x [∃y R(x,y)→S(x,y)])→ ∀x∃y S(x,y) C [∀x ∃y (P(x,y)→R(x,y)]↔[∀x ∃y ( ¬ P(x,y)∨R(x,y)] D ∀x ∀y P(x,y)→ ∀x ∀y P(y,x)
Engineering-Mathematics       Propositional-Logic
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.
 Question 60
A graph is self-complementary if it is isomorphic to its complement for all self-complementary graphs on n vertices, n is
 A A multiple of 4 B Even C Odd D Congruent to 0 mod 4, or, 1 mod 4
Engineering-Mathematics       Graph-Theory
Question 60 Explanation:
An n vertex self-complementary graph has exactly half number of edges of the complete graph i.e., n(n-1)/4 edges. Since n(n – 1) must be divisible by 4, n must be congruent to 0 or 1 module 4.
 Question 61

 A xb – (fb–f(xa))fb /(xb–xa) B xa – (fa–f(xa))fa /(xb–xa) C xb – (xb–xa)fb /(fb–f(xa)) D xa – (xb–xa) fa /(fb–f(xa))
Engineering-Mathematics       Secant-Method
Question 61 Explanation:
The solution for this question is direct formula of secant method. In numerical analysis, the secant method is a root-finding 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.
 Question 62
 A -2 B 2 C -1 D 15
Programming       Programming
Question 62 Explanation:
When first time stkFunc (-1,10) will be called then, inside Switch(opcode) the control will go to Case-I, where size=10.
When next time stkFunc (0,5) is called then, inside Switch(opcode), the control will go to Case-0, 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 = 2-1 = 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 = 1-1 = 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
 A II only B III only C II and III only D I, II and III
Engineering-Mathematics       Calculus
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.
 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 one-to-one is ______.
 A 0.95 B 0.96 C 0.97 D 0.98
Engineering-Mathematics       Relations-and-Functions
Question 64 Explanation:
|X| = 2, |Y| = 20
Number of functions from X to Y is 202 i.e., 400 and number of one-one functions from X to Y is 20P2 i.e., 20×19 = 380
∴ Probability of a function f being one-one is 380/400 i.e., 0.95
 Question 65
 A 10(0* + (10*)* 1 B 10(0* + (10)*)* 1 C 1(0 + 10)* 1 D 10(0 + 10)* 1 + 110(0 + 10)* 1
Theory-of-Computation       Regular-Grammar
Question 65 Explanation:
Convert the given transitions to a state diagram.

From the given diagram we can write,
X0 = 1(0+10)* 1
There are 65 questions to complete.