## Gate 2008-IT

 Question 1
A set of Boolean connectives is functionally complete if all Boolean functions can be synthesized using those. Which of the following sets of connectives is NOT functionally complete?
 A EX-NOR B implication, negation C OR, negation D NAND
Digital-Logic-Design       Boolean-Functions
Question 1 Explanation:
→ EX-NOR is not functionally complete.
→ NOR and NAND are the functionally complete logic gates, OR, AND, NOT only logic gate can be implemented by using them.
→ And (Implication, Negation) is also functionally complete.
 Question 2
A sample space has two events A and B such that probabilities P(A ∩ B) = 1/2, P(A') = 1/3, P(B') = 1/3. What is P(A ∪ B)?
 A 11/12 B 10/12 C 9/12 D 8/12
Engineering-Mathematics       Probability
Question 2 Explanation:
P(A ∩ B) = 1/2
P(A') = 1/3; P(A) = 2/3
P(B') = 1/3; P(B) = 2/3
P(A ∪ B) = P(A) +P(B) - P(A ∩ B)
= 2/3 + 2/3 - 1/2
= 4+4-3/ 6
= 5/6
= 10/12
 Question 3

 A 2 B 3 C 4 D 5
Engineering-Mathematics       Graph-Theory
Question 3 Explanation:
Chromatic number = 3
→ Chromatic number of a graph is the smallest number of colours needed to colour the vertices so that no two adjacent vertices share the same colour.
 Question 4
What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes?
 A 5 B 4 C 3 D 2
Engineering-Mathematics       Graph-Theory
Question 4 Explanation:
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9
(2, 5, 8) is the maximal independent set for a chain of 9 nodes. If we add any start node to the set then it will not be MIS.
Independent set:
A set of vertices is called independent set such that no two vertices in the set are adjacent.
 Question 5
Which of the following regular expressions describes the language over {0, 1} consisting of strings that contain exactly two 1’s?
 A (0 + 1) * 11(0 + 1) * B 0 * 110 * C 0 * 10 * 10 * D (0 + 1) * 1(0 + 1) * 1 (0 + 1) *
Theory-of-Computation        Regular-Expressions
Question 5 Explanation:
Option A: (0+1)* 11(0+1)*
→ 1110 this consists of 3 ones but accepted by given expression. So this is false.
Option B: 0* 110*
→ 0101 this string consists of two is but not accepted by given expression. This is false.
Option C: 0* 10* 10*
→ This is true.
Option D: (0+1)* 1(0+1)* 1(0+1)*
→ 011010 - This can have three is but accepted by given expression. So this is also false.
 Question 6
Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?
 A m ≤ 2n B n ≤ m C M has one accept state D m = 2n
Theory-of-Computation       Finite-Automata
Question 6 Explanation:
Set of states of NFA = n
A state in a DFA is a proper suset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2n
→ m ≤ 2n
 Question 7

 A -10 B -13 C -26 D None of these
Digital-Logic-Design       Number-Systems
Question 7 Explanation:
Sign bit is 1 then given number is negative.
Exponent bits - 10000011
Exponent can be added with 127 bias in IEEE single precision format then outval exponent
= 10000011 - 127
= 131 - 127
= 4
→ In IEEE format, an implied 1 is before mantissa, and hence the outval number is
→ 1.101 × 24 = -(11010)2 = -26
 Question 8

 A independent of one variable B independent of two variables C independent of three variable D dependent on all the variables
Digital-Logic-Design       Boolean-Functions
Question 8 Explanation:
f(A, B, C, D) = Σ(2, 3, 6, 7, 8, 9, 10, 11, 12, 13)

Independent of one variable '0'.
 Question 9

 A xz+x’z’ B xz’+x’z C x’y’+yz D xy+y’z’
Digital-Logic-Design       Decoder
Question 9 Explanation:
 Question 10

 A A, D, C, E, B B D, A, C, E, B C A, C, D, E, B D A, C, D, B, E
Algorithms        Time-Complexity
Question 10 Explanation:
A < D < C < E < B
n1/3 < n log9 < n7/4 < 1.0000001n < en
 Question 11
For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?
 A If X can be solved in polynomial time, then so can Y B X is NP-complete C X is NP-hard D X is in NP, but not necessarily NP-complete
Algorithms        P-NP
Question 11 Explanation:
We can't be able to say X is NP-hard unless and untill X is also NP-complete (or) below it.
That means to be it belongs to NP class, in that class it may be NP-complete. So, X is NP for sure but may be NP-complete.
 Question 12
Which of the following is TRUE?
 A The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n) B The cost of searching an AVL tree is θ (log n) but that of a complete binary tree is θ (n log n) C The cost of searching a binary search tree is O (log n ) but that of an AVL tree is θ(n) D The cost of searching an AVL tree is θ (n log n) but that of a binary search tree is O(n)
Data-Structures       AVL-Trees
Question 12 Explanation:
Complexity of AVL tree is O(logn) because it is a balanced tree, in Worst case binary search tree complexity is O(n).
 Question 13

 A I-c, II-d, III-b, IV-a B I-a, II-d, III-c, IV-b C I-d, II-c, III-b, IV-a D I-c, II-d, III-a, IV-b
Programming       Match-the-Following
Question 13 Explanation:
Note: Out of syllabus.
 Question 14
 A Mathematics Information Technology SAME. B Mathematics Information Technology. C Information Technology. D Information Technology SAME.
Operating-Systems       LINUX
Question 14 Explanation:
Note: Out of syllabus.
 Question 15
A processor that has carry, overflow and sign flag bits as part of its program status word (PSW) performs addition of the following two 2's complement numbers 01001101 and 11101001. After the execution of this addition operation, the status of the carry, overflow and sign flags, respectively will be:
 A 1, 1, 0 B 1, 0, 0 C 0, 1, 0 D 1, 0, 1
Digital-Logic-Design       Number-Systems
Question 15 Explanation:

Carry flag = 1
Overflow flag = 0
Sign bit = 0 (MSB bit is 0)
Overflow flag:
In computer processors, the overflow flag is usually a single bit in a system status register used to indicate when an arithmetic overflow has occurred in an operation.
 Question 16
A paging scheme uses a Translation Look-aside Buffer (TLB). A TLB-access takes 10 ns and a main memory access takes 50 ns. What is the effective access time(in ns) if the TLB hit ratio is 90% and there is no page-fault?
 A 54 B 60 C 65 D 75
Operating-Systems        Virtual Memory
Question 16 Explanation:
EMAT = [(Hit ratio) * (Time during Hit)] + [(Miss ratio) * (Time during Miss TLB time)
= [(0.9) * 60] + [0.1 * 110]
= 65
 Question 17

 A True, True B True, False C False, True D False, False
Question 17 Explanation:
Note: Out of syllabus.
 Question 18
How many bytes of data can be sent in 15 seconds over a serial link with baud rate of 9600 in asynchronous mode with odd parity and two stop bits in the frame?
 A 10,000 bytes B 12,000 bytes C 15,000 bytes D 27,000 bytes
Computer-Organization       Serial-Communication
Question 18 Explanation:
In the Asynchronous mode of transmission along with per byte, we need to send some extra bit like start, stop bit and parity bit, etc.
1 bit for start bit, 8 bits for data, 1 bit for parity, 2 bits for stop bits i.e.,
 Question 19
Which of the following is TRUE only of XML but NOT HTML?
 A It is derived from SGML B It describes content and layout C It allows user defined tags D It is restricted only to be used with web browsers
Question 19 Explanation:
Note: Out of syllabus.
 Question 20

 A I-a, II-d, III-c, IV-b B I-b, II-d, III-c, IV-a C I-a, II-c, III-d, IV-b D I-b, II-c, III-d, IV-a
Computer-Networks       Match-the-Following
Question 20 Explanation:
(i) Proxy server: Proxy server and firewall are to be combined.
(ii) Kazaa and DC++ are P2P applications.
(iii) P2P slip is a processor of PPP.
(iv) DNS allows caching of entries at local server.
 Question 21
Which of the following first order formula is logically valid? Here α(x) is a first order formula with x as a free variable, and β is a first order formula with no free variable.
 A [β→(∃x,α(x))]→[∀x,β→α(x)] B [∃x,β→α(x)]→[β→(∀x,α(x))] C [(∃x,α(x))→β]→[∀x,α(x)→β] D [(∀x,α(x))→β]→[∀x,α(x)→β]
Engineering-Mathematics       Propositional-Logic
Question 21 Explanation:
[(∃x,α(x))→β]→[∀x,α(x)→β]
L.H.S. : If there is an x such that α(x) is true, then β is true.
R.H.S. : For all x, if α(x) true, then β is true.
Here, the given LHS and RHS are to be same as β is a formula which can be independent of x (if β is true for one x, it is true for every x, and vice-versa).
Here, LHS = RHS
So, Option C is valid.
 Question 22
Which of the following is the negation of [∀ x, α → (∃y, β → (∀ u, ∃v, y))]
 A [∃ x, α → (∀y, β → (∃u, ∀ v, y))] B [∃ x, α → (∀y, β → (∃u, ∀ v, ¬y))] C [∀ x, ¬α → (∃y, ¬β → (∀u, ∃ v, ¬y))] D [∃ x, α ʌ (∀y, β ʌ (∃u, ∀ v, ¬y))]
Engineering-Mathematics       Propositional-Logic
Question 22 Explanation:
 Question 23
What is the probability that in a randomly chosen group of r people at least three people have the same birthday?
 A B C D
Engineering-Mathematics       Probability
Question 23 Explanation:
 Question 24
The exponent of 11 in the prime factorization of 300! is
 A 27 B 28 C 29 D 30
Engineering-Mathematics       Combinatorics
Question 24 Explanation:
300/11 = 27
27/11 = 2
2/11 = 0
-------------------
29
-------------------
The exponent of 11 in the prime factorization of 300! = 29
 Question 25
In how many ways can b blue balls and r red balls be distributed in n distinct boxes?
 A B C D
Engineering-Mathematics       Combinatorics
Question 25 Explanation:
 Question 26

 A only S1 B S1 and S3 C S2 and S3 D S1 and S2
Engineering-Mathematics       Sets and Relations
Question 26 Explanation:
S1: It is closed under both * and +.
As real + real = real and real * real = real
S2: It is closed as rational + rational = rational and rational * rational = rational
S3: It is not closed.
⇒ (0.3+0.4i) + (0.7+0.6i) = 1+i
Both (0.3+0.4i) & (0.7+0.6i) are complex numbers follows S3 but addition of them doesn't follows.
⇒ 1+i, (a2+b2) <= 1
⇒ 1+1 is not less than or equal to 1.
S4: {ia | a ia real}
In this there is no multiplicative identity exists (i.e., 1).
 Question 27
G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be
 A Regular B Complete C Hamiltonian D Euler
Engineering-Mathematics       Graph-Theory
Question 27 Explanation:
Euler graph theory is a trail in a finite graph which visits every edge exactly once and which is a undirected graph.
→ In Euler graph all degrees must be even for all nodes. And number of odd degree vertices should be even.
→ So, degree of this new node will be even and as a new edge is formed between this new node and all other nodes of odd degree hence here is not a single node exists with degree odd so this is Euler graph.
 Question 28

 A (i) and (iv) only B (ii) and (iii) only C (iii) only D (i), (ii) and (iv) only
Engineering-Mathematics       Sets-And-Relation
Question 28 Explanation:
If a hasse diagram is a lattice then every pair of element have atleast one lub and one gub.
(ii) and (iii), not having a least upper bound and greatest upper bound.
 Question 29

 A S3 and S2 B S1 and S4 C S1 and S3 D S1, S2 and S3
Engineering-Mathematics       Linear-Algebra
Question 29 Explanation:
As per given information, M has zero determinant. So, it's rank is not full i.e., if the M is of size 3×3 then the rank is not 3. So, there is a linear combinationof rows which evaluates to '0' i.e.,
→ K1R1 + K2R2 + ... + KnRn = 0
and there is also a linear combination of columns which evaluates to '0' i.e.,
→ K1C1 + K2C2 + ... + KCRn = 0
Now, any row Ri can be written as linear combination of other rows as:

Similar case to columns,
Hence, MX=0, always has one solution i.e., X=0 (which is called trivial solution)
Now if |M| = 0, then MX = 0 has non-trivial solutions also.
So, S1, S2, S3 are to be true.
 Question 30
Consider the function f(x) = x2 - 2x - 1. Suppose an execution of the Newton- Raphson method to find a zero of f(x) starts with an approximation x0 = 2 0f x. What is the value of x2, 'the approximation of x' that the algorithm produces after two iterations, rounded to three decimal places?
 A 2.417 B 2.419 C 2.423 D 2.425
Engineering-Mathematics       Newton-Raphson-Method
Question 30 Explanation:
Note: Out of syllabus.
 Question 31

 A B C D
Engineering-Mathematics       Calculus
Question 31 Explanation:
 Question 32

 A Set of all strings that do not end with ab B Set of all strings that begin with either an a or a b C Set of all strings that do not contain the substring ab D The set described by the regular expression b*aa*(ba)*b*
Theory-of-Computation       Finite-Automata
Question 32 Explanation:

Option B: abab is not accepted by given RE.
Option C: aba is accepted by given RE.
Option D: ab is not accepetd by RE and it belongs to b*aa*(ba)*b*.
 Question 33

 A L1 is not a CFL but L2 is B L1 ∩ L2 = ∅ and L1 is non-regular C L1 ∪ L2 is not a CFL but L2 is D There is a 4-state PDA that accepts L1, but there is no DPDA that accepts L2
Theory-of-Computation       Identify-Class-Language
Question 33 Explanation:
→ Both L1 and L2 are CFL. So option A is false.
→ L1 ∩ L2 = ∅, True and also L1 is non-regular. Option B is true.
→ L1 ∪ L2 is not a CFL but L2 is CFL is closed under union. So option C is false.
→ Both L1 and L2 accepted by DPDA.
 Question 34

 A {0n 102n | n ≥ 1} B {0i 10j 10k | i, j, k ≥ 0} ∪ {0n 102n | n ≥ l} C {0i 10j | i, j ≥ 0} ∪ {0n 102n | n ≥ l} D The set of all strings over {0, 1} containing at least two 0’s E None of the above
Theory-of-Computation       Contest-Free-Grammar
Question 34 Explanation:
S → AA | B
A → 0A | A0 | 1
B → 0B00 | 1
In this B → 0B00 | 1 which generates {0n 102n | n ≥0}
S → AA | B
A → 0A | A0 | 1
Which generates 0A0A → 00A0A → 00101.
Which is suitable for B and D option. D is not correct because 00 is not generated by the given grammar. So only option B is left. Non-terminal B i s generating the second part of B choice and AA is generating the first part.
{0i 10j 10k | i, j, k ≥ 0} ∪ {0n 102n | n ≥ 0}
 Question 35

 A L2 and L3 only B L1 and L2 only C L3 only D L2 only
Theory-of-Computation       Identify-Class-Language
Question 35 Explanation:
L1 and L3 are regular.
L1 is limited to fixed range and L3 contains even number of 0's which is regular. No need to use more memory to implement L3.
 Question 36

 A L1 = L2 B L1 ⊂ L2 C L1 ∩ L2‘ = ∅ D L1 ∪ L2 ≠ L1 E A and C
Theory-of-Computation       Finite-Automata
Question 36 Explanation:
In this L1 = (0+10)* 11(0+1)*
L2 = (0=1)* 11(0+1)*
Both L1 and L2 are equal.
Option A is correct.
→ L1 ∩ L2‘ = L1 ∩ L1‘ = ∅ (option C also correct)
 Question 37

 A (x⊕y)’ and x’⊕y’ B (x⊕y)’ and x⊕y C x⊕y and (x⊕y)’ D x⊕y and x⊕y
Digital-Logic-Design       Sequential-Circuits
Question 37 Explanation:
From the given statement:

Excitation table of JK:
 Question 38

Assume that EA = (X)+ is the effective address equal to the contents of location X, with X incremented by one word length after the effective address is calculated; EA = −(X) is the effective address equal to the contents of location X, with X decremented by one word length before the effective address is calculated; EA = (X)− is the effective address equal to the contents of location X, with X decremented by one word length after the effective address is calculated. The format of the instruction is (opcode, source, destination), which means (destination ← source op destination). Using X as a stack pointer, which of the following instructions can pop the top two elements from the stack, perform the addition operation and push the result back to the stack.

Computer-Organization       Machine-Instructions
Question 38 Explanation:
Answer is A as 998 ← 1000 + 998(These are the memory locations).
Lets say SP is 1000 initially then after it calculates the EA of source (which is 1000 as it decrements after the EA). The destination becomes 998 and this is where we want to store the result as stack is decrementing.
In case of C and D it becomes,
998 ← 998 + 998
 Question 39

Consider a CPU where all the instructions require 7 clock cycles to complete execution. There are 140 instructions in the instruction set. It is found that 125 control signals are needed to be generated by the control unit. While designing the horizontal microprogrammed control unit, single address field format is used for branch control logic. What is the minimum size of the control word and control address register?

 A 125, 7 B 125, 10 C 135, 7 D 135, 10
Computer-Organization       Micro-Programmed-Control-Unit
Question 39 Explanation:
Each instruction takes 7 cycles i.e., 140 instructions takes = 140 * 7 = 980 cycles
⇒ 2m ≥ 980
⇒ m ≥ 10
⇒ 10+125 bits and 10 bits
⇒ 135, 10 bits
 Question 40

A non pipelined single cycle processor operating at 100 MHz is converted into a synchro­nous pipelined processor with five stages requiring 2.5 nsec, 1.5 nsec, 2 nsec, 1.5 nsec and 2.5 nsec, respectively. The delay of the latches is 0.5 nsec. The speedup of the pipeline processor for a large number of instructions is

 A 4.5 B 4 C 3.33 D 3
Computer-Organization       Pipelining
Question 40 Explanation:
For non-pipelined system time required = 2.5 + 1.5 + 2.0 + 1.5 + 2.5 = 10
For pipelined system = Max(stage delay) + Max(latch delay) = 2.5 + 0.5 = 3.0
Speedup = Time in non-pipelined system/Time in pipelined system = 10/3 = 3.33
 Question 41

 A 6 and 1, 2, 3, 4 B 7 and 1, 2, 4, 5 C 8 and 1, 2, 4, 5 D 9 and 1, 2, 3, 5
Operating-Systems       Page-Replacement
Question 41 Explanation:
In this, we can have 4 spaces for a page and there is a replacement whether the 5th page comes.
(Each page contains 16 bytes, so say for page0, it contains the virtual address 0-15)
0: page fault-1, pages in memory-0
4: page fault-1, pages in memory-0
8: page fault-1, pages in memory-0
20: page faults-2, pages in memory-0,1
24: page faults-2, pages in memory-0,1
36: page faults-3, pages in memory-0,1,2
44: page faults-3, pages in memory-0,1,2
12: page faults-3, pages in memory-1,2,0
68: page faults-4, pages in memory-1,2,0,4
72: page faults-4, pages in memory-1,2,0,4
80: page faults-5, pages in memory-2,0,4,5
84: page faults-5, pages in memory-2,0,4,5
28: page faults-6, pages in memory-0,4,5,1
32: page faults-7, pages in memory-4,5,1,2
88: page faults-7, pages in memory-4,1,2,5
92: page faults-7, pages in memory-4,1,2,5
 Question 42

 A 6 B 8 C 10 D 12
Digital-Logic-Design       Number-Systems
Question 42 Explanation:
Booth's Algorithm:
First evaluate 2's complement of given numbers, if numberis negative then append 0 into LSB.
Then each pair from LSB to MSB (add 1 bit at a time):
00 = 0, 01 = +1, 10 = -1, 11 = 0
Booth's algorithm based on multiplier which is already given in binary representation:
0111 0111 1011 1101
= Now, append 0 into LSB of
(0111 0111 1011 1101) = 0111 0111 1011 1101 0
Now, Booth's code (add 1 bit at a time, from LSB to MSB):
= 01, 11, 11, 10, 01, 11, 11, 11, 10, 01, 11, 11, 11, 10, 01, 10
= +1 0 0 -1 +1 0 0 0 -1 +1 0 0 0 -1 +1 -1
Here, 4 substractions and 4 additions required,
Total = 8
 Question 43
If we use Radix Sort to sort n integers in the range [nk/2, nk], for some k>0 which is independent of n, the time taken would be?
 A Θ(n) B Θ(kn) C Θ(nlogn) D Θ(n2)
Algorithms        Sorting
Question 43 Explanation:
 Question 44

 A B C D
Algorithms        Time-Complexity
Question 44 Explanation:
 Question 45

 A (a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h) B (c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i) C (d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i) D (h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)
Algorithms        Minimum-Spanning-Tree
Question 45 Explanation:
Prims algorithm starts from any vertex and expands MST by adding one vertex in each step which is close to the intermediate MST (made till previous step).
(A) (d, f) is chosen but neither 'd' nor 'f' vertices are part of previous MST (MST made till previous step).
(B) (g, h) is chosen but neither g or h vertices are part of MST made till previous step.
(C) Correct.
(D) (f, c) is chosen, but at that point (f, d) had less weight. So, (f , d) should have been chosen.
 Question 46

 A I and II are preorder and inorder sequences, respectively B I and III are preorder and postorder sequences, respectively C II is the inorder sequence, but nothing more can be said about the other two sequences D II and III are the preorder and inorder sequences, respectively
Data-Structures       Binary-Trees
Question 46 Explanation:
In preorder, root comes at the beginning of the traversal sequence and in post order, root comes at last of the traversal sequence.
So, out of the given sequence only I & II are having such kind of order, i.e., K at the beginning and at the last.
Therefore, II is the preorder and I is postorder and the sequence III will definitely be inorder.
 Question 47

 A I and III only B II and III only C II, III and IV only D I, II and III only
Data-Structures       Graphs
Question 47 Explanation:
I) After visiting 'f', 'c' or 'g' should be visited next. So, the traversal is incorrect.
IV) After visiting 'c', 'e' or 'f' should be visited next. So, the traversal is incorrect.
 Question 48

 A 2 B 4 C 6 D 7
Data-Structures       Hashing
Question 48 Explanation:

Hence, correct option is (D).
 Question 49
 A dlrow B Null String C dlrld D worow
Programming       C-Programming
Question 49 Explanation:
As the base address or starting of the string "Null" is placed. So while reading array if Null comes it assumes that this is the end of array. So, it terminates here only.
 Question 50
 A 5, 5 B 5, 4 C 4, 5 D 4, 4
Programming       C-Programming
Question 50 Explanation:
"If (num1 ≥ num2)
{Swap3 (&num1, &num2) ; }"
Statement is true, so call by reference will be performed and the value of num1 and num2 will get exchanged.
 Question 51

 A 2, 3 B 2, 4 C 3, 2 D 3, 3
Programming       C-Programming
Question 51 Explanation:
Note that there are two variables named 'i', with different scope.
First for loop will run for i = 0, 2 and 4 as i is incremented twice and resultant array will be 'a' = 2, 2, 4, 4, 5, 6, 7, 8. Loop will terminate at i = 4.
After that value of 'i' will become '3' as there is a decrement operation after for loop.
Next for loop is running for j = 7, 6, 5 and corresponding 'i' values which is a local variable inside for loop will be
3(7/2), 3(6/2), 2(5/2)
Array after this for loop will be
a = 2, 2, 3, 2, 5, 6, 2, 8.
After the loop, current 'i' value is 3 and elements at a[3] = 2.
 Question 52

 A B C D
Programming       C-Programming
Question 52 Explanation:
*p = a[0][0] = a
*(p+2) = a[0][1] = b
*(p+4) = a[0][2] = c
*(p+1) = a[1][0] = d
*(p+3) = a[1][1] = e
*(p+5) = a[1][2] = f
 Question 53

 A The process can deadlock B One of the threads can starve C Some of the items produced by the producer may be lost D Values generated and stored in ‘x’ by the producer will always be consumed before the producer can generate a new value
Operating-Systems       Process-Synchronization
Question 53 Explanation:
(A) Deadlock cannot happen as both producer and consumer are operating on different semaphores (No hold and wait).
(B) No starvation happen because there is alteration between Producer and Consumer.
(C) No items is lost.
 Question 54
An operating system implements a policy that requires a process to release all resources before making a request for another resource. Select the TRUE statement from the following:
 A Both starvation and deadlock can occur B Starvation can occur but deadlock cannot occur C Starvation cannot occur but deadlock can occur D Neither starvation nor deadlock can occur
Question 54 Explanation:
Starvation can occur as each time a process requests a resource it has to release all its resources.
Now, maybe the process has not used the resources it released yet. This may happen again when the process requests another resource.
So, the process starved for proper utilization of resources.
Deadlock will not occur as it is one of the deadlock prevention scheme.
 Question 55
If the time-slice used in the round-robin scheduling policy is more than the maximum time required to execute any process, then the policy will
 A degenerate to shortest job first B degenerate to priority scheduling C degenerate to first come first serve D none of the above
Operating-Systems       Round-Robin
Question 55 Explanation:
Round robin executes processes in FCFS manner with a time slice. In this time slice becomes long enough, so that a process finishes within it, it becomes FCFS.
 Question 56

 A I-d, II-a, III-b, IV-c B I-b, II-c, III-a, IV-d C I-c, II-d, III-a, IV-b D I-b, II-c, III-d, IV-a
Operating-Systems       Virtual Memory
Question 56 Explanation:
Dirty bit:
The bit indicates that its associated block of memory has been modified and has not been saved to storage yet. Dirty bits are used by the CPU cache and in the page replacement algorithms of an operating system.
R/W bit:
If the bit is set, the page is read/ write. Otherwise when it is not set, the page is read only.
Reference bit:
Reference bit is used in a version of FIFO called second chance policy, in order to avoid replacement of heavily used page.
Valid bit:
Valid bit is not used for page replacement. It is not used in any page replacement policy. It tells the page in the memory is valid or not. If it is valid it is directly used and if it is not then a fresh page is loaded. So, basically it is page initialization, because we are not replacing, it is initializing, we not knocking out somebody, we are filling empty space. So initialization and so option (D).
 Question 57

 A 02, 03 B 01, 05 C 04, 06 D 02, 05
Question 57 Explanation:
Note: Out of syllabus.
 Question 58
 A 5, 5 B 4, 5 C 5, 4 D 4, 4
Question 58 Explanation:
Note: Out of syllabus.
 Question 59
 A S1 B S2 C S3 D S4
Question 59 Explanation:
Note: Out of syllabus.
 Question 60

 A S4 and S3 B S4 and S2 C S3 and S1 D S2 and S1
Question 60 Explanation:
Note: Out of syllabus.
 Question 61

 A gives a lossless join, and is dependency preserving B gives a lossless join, but is not dependency preserving C does not give a lossless join, but is dependency preserving D does not give a lossless join and is not dependency preserving
Database-Management-System       Functional-Dependency
Question 61 Explanation:
(A, B) (B, C) - common attribute is (B) and due to B→C, B is a key for (B, C) and hence ABC can be losslessly decomposedinto (A, B)and (B, C).
(A, B, C) (B, D) - common attributes is B and B→D is a FD (via B→C, C→D), and hence, B is a key for (B, D). So, decomposition of (A, B, C, D) into (A, B, C) (B, D) is lossless.
Thus the given decomposition is lossless.
The given decomposition is also dependency preserving as the dependencies A→B is present in (A, B), B→C is present in (B, C), D→B is present in (B, D) and C→D is indirectly present via C→B in (B, C) and B→D in (B, D).
 Question 62

 A in BCNF B in 3NF, but not in BCNF C in 2NF, but not in 3NF D not in 2NF
Database-Management-System       Normalization
Question 62 Explanation:
Candidate key is AB.
Since there is a partial dependency B→G.
So the relational schema R is Not in 2NF.
 Question 63

 A S1, S2 and S3 are all conflict equivalent to each other B No two of S1, S2 and S3 are conflict equivalent to each other C S2 is conflict equivalent to S3, but not to S1 D S1 is conflict equivalent to S2, but not to S3
Database-Management-System       Transactions
Question 63 Explanation:
Two schedules are conflict equivalent when the precedence graph are isomorphic.
For S1:

For S2:

For S3:

Hence, S1 is conflict equivalent to S2, but not to S3.
 Question 64

A 1Mbps satellite link connects two ground stations. The altitude of the satellite is 36,504 km and speed of the signal is 3 × 108 m/s. What should be the packet size for a channel utilization of 25% for a satellite link using go-back-127 sliding window protocol? Assume that the acknowledgment packets are negligible in size and that there are no errors during communication.

 A 120 bytes B 60 bytes C 240 bytes D 90 bytes
Computer-Networks       Sliding-Window-Protocol
Question 64 Explanation:
Time to reach satellite = 36504000/3×108 = 0.121685
RTT = 4×Time to reach satellite (S1→S, S→S2, S2→S, S→S1)

∴ RTT = 0.48
 Question 65
The minimum frame size required for a CSMA/CD based computer network running at 1 Gbps on a 200 m cable with a link speed of 2 × 10m/s is
 A 125 bytes B 250 bytes C 500 bytes D None of these
Computer-Networks       Ethernet
Question 65 Explanation:
For CSMA/CD protocol to work, the transmission time of the frame must be more than minimum value. This minimum value is the RTT.
So,

 Question 66

 A 1 B 2 C 3 D 4
Computer-Networks       Error-Detection
Question 66 Explanation:

Here, we need to change minimum 3-bits, and by doing it we get correct parity column wise and row wise (correction marked by boxed number).
 Question 67

 A S1, S2 and S4 only B S1, S3 and S4 only C S2 and S3 only D S1 and S4 only
Computer-Networks       Routing
Question 67 Explanation:
→ Count to infinity problem only exist into the DVR.
→ In LSR shortest path is calculated at each every router. (B) is wrong.
→ In DVR also shortest path is calculated at each and every router. (C) is wrong.
→ Since DVR is based upon local knowledge whereas LSR is based upon global knowledge.
 Question 68

 A S1, S2 and S3 only B S1 and S3 only C S3 and S4 only D S1, S3 and S4 only
Computer-Networks       Congestion-Control
Question 68 Explanation:
S1:
TCP handles both congestion and flow control ⇒ True.
S2:
UDP handles congestion but not flow control ⇒ False, because UDP neither handles congestion control nor flow control.
S3:
Fast retransmits deals with congestion but not flow control ⇒ True.
S4:
Slow start mechanism deals with both congestion and flow control ⇒ False, because it has nothing to do with flow control. Flow control is taken care by Advertisement window.
 Question 69

 A S2 and S3 only B S1 and S4 C S1 and S3 D S2 and S4
Computer-Networks       TCP
Question 69 Explanation:
S1 → True.
S2 → False, because if after ACK client immediately sends data then everything goes on without worry.
S3 → False.
S4 → True.
 Question 70
The total number of keys required for a set of n individuals to be able to communicate with each other using secret key and public key crypto-systems, respectively are:
 A B C D
Computer-Networks       Network-Security
Question 70 Explanation:
For private key crypto, a key used for encryption as well as decryption. So, no. of keys required for n individuals is same as no. of communication link between any two individuals which is
nC2 = n(n-1)/2
In case of public key, each sender has its own public key as well as private key. So, no. of keys are 2n.
 Question 71

 A II and III only B I and III only C III and IV only D III only
Data-Structures       Binary-Trees
Question 71 Explanation:
 Question 72

 A I, II and IV are inorder sequences of three different BSTs B I is a preorder sequence of some BST with 439 as the root C II is an inorder sequence of some BST where 121 is the root and 52 is a leaf D IV is a postorder sequence of some BST with 149 as the root
Data-Structures       Binary-Trees
Question 72 Explanation:
A) Incorrect because I & IV are not in ascending order. (Inorder sequence of BST is in increasing order).
B) False because if 439 is root then it should be first element in preorder.
C) This is correct.
D) False because if 149 is root, then it should be last element in postorder.
 Question 73

 A 4 B 5 C 6 D 9
Data-Structures       Binary-Trees
Question 73 Explanation:
Formula:
 Question 74
 A for each school with more than 200 students appearing in exams, the name of the school and the number of 100s scored by its students B for each school with more than 200 students in it, the name of the school and the number of 100s scored by its students C for each school with more than 200 students in it, the name of the school and the number of its students scoring 100 in at least one exam D nothing; the query has a syntax error
Database-Management-System       SQL
Question 74 Explanation:
If select clause consist of aggregate and non-aggregate columns, all non-aggregate columns in the select clause must appear in Group By clause. But in this Group By clause consists school-id instaed of school-name.
 Question 75
 A The empty set B schools with more than 35% of its students enrolled in some exam or the other C schools with a pass percentage above 35% over all exams taken together D schools with a pass percentage above 35% over each exam
Database-Management-System       Relational-Calculus
Question 75 Explanation:
Query having the division with
{ x | x ∈ Enrolment ∧ x . school-id = t } | * 100 > 35 }
This is school with enrollment % is 35 or above.
 Question 76

 A B C D
Data-Structures       Binary-Trees
Question 76 Explanation:

n1 = 3
n2 = 1
n3 = 1
So, option (B) satisfies.
 Question 77

 A 2 * n1 – 3 B n2 + 2 * n1 – 2 C n3 – n2 D n2 + n1 – 2
Data-Structures       Binary-Trees
Question 77 Explanation:

n1 = 3
n3 = 1
So, option (A) satisfies.
 Question 78

 A aabbaba B aabaaba C abababb D aabbaab
Theory-of-Computation       Contest-Free-Grammar
Question 78 Explanation:
S→aS
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
 Question 79

 A 6 and 1 B 6 and 2 C 7 and 2 D 4 and 2
Theory-of-Computation       Contest-Free-Grammar
Question 79 Explanation:
S→aS
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
⇒ 6 steps are required

Only 1 parse tree is there.
 Question 80

 A 7, 6, 7 B 8, 5, 7 C 8, 6, 6 D 9, 4, 7
Computer-Organization       Cache
Question 80 Explanation:
 Question 81

 A 000011000 B 110001111 C 00011000 D 110010101
Computer-Organization       Cache
Question 81 Explanation:
As we have found in earlier question that first 9 bits is tag bits.
So lets first convert given Hexadecimal no. into binary number,
 Question 82

 A 010110101 B 010101101 C 10110101 D 10101101
Programming       C-Programming
Question 82 Explanation:

So, after traversing the tree we get:
10101101
 Question 83
 A Both P1 and P2 B P2 only C P1 only D Neither P1 nor P2
Programming       C-Programming
Question 83 Explanation:
P1 prints same as the original program.
But P2 prints the reverse of original sequence printed by original program.
 Question 84

 A 1 B 2 C 3 D 6
Question 84 Explanation:
Simply, Bitwise AND the bits of fourth octet for each of the following IP address with fourth octet of subnet mask. You will get only
XX.XX.XX.96, XX.XX.XX.64 and XX.XX.XX.128.
 Question 85

 A 192.168.1.67 B 192.168.1.110 C 192.168.1.135 D 192.168.1.155