2009

Question 1
Which one of the following in NOT necessarily a property of a Group?
A
Commutativity
B
Associativity
C
Existence of inverse for every element
D
Existence of identity
Question 1 Explanation: 
A Group should satisfy Closure, Associative, should have identity element and each element has inverse.
So, commutativity is not required.
Question 2
What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2.
A
2
B
3
C
n-1
D
n
Question 2 Explanation: 
If n≥ 2 and there are no odd length cycles, Then it is bipartite graph. A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Question 3
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
A
No two vertices have the same degree.
B
At least two vertices have the same degree.
C
At least three vertices have the same degree.
D
All vertices have the same degree.
Question 3 Explanation: 
Method 1:
If all vertices have different degrees, then the degree sequence will be {1,2,3,....n-1}, it will not have ‘n’( A simple graph will not have edge to itself, so it can have edges with all other (n-1) vertices). Degree sequence has only (n-1) numbers, but we have ‘n’ vertices. So, by Pigeonhole principle there are two vertices which has same degree.
Method 2:
A) consider a triangle, all vertices has same degree, so it is false
C) consider a square with one diagonal, there are less than three vertices with same degree, so it is false
D) consider a square with one diagonal, vertices have different degrees. So, it is false.
We can conclude that option B is correct.
Question 4
Consider the binary relation R = {(x, y), (x, z), (z, x), (z, y)} on the set {x, y, z}. Which one of the following is TRUE?
A
R is symmetric but NOT antisymmetric
B
R is NOT symmetric but antisymmetric
C
R is both symmetric and antisymmetric
D
R is neither symmetric nor antisymmetric
Question 4 Explanation: 
Symmetric Relation: A relation R on a set A is called symmetric if (b,a) € R holds when (a,b) € R.
Antisymmetric Relation: A relation R on a set A is called antisymmetric if (a,b)€ R and (b,a) € R then a = b is called antisymmetric.
In the given relation R, for (x,y) there is no (y,x). So, this is not Symmetric. (x,z) is in R also (z,x) is in R, but as per antisymmetric relation, x should be equal to z, where this fails.
So, R is neither Symmetric nor Antisymmetric.
Question 5
(1217)8 is equivalent to
A
(1217)16
B
(028F)16
C
(2297)10
D
(0B17)16
Question 5 Explanation: 
(1217)8= (001 010 001 111)2
Divide the bits into groups, each containing 4 bits.
=(0010 1000 1111)2
=(28F)16
Question 6
What is the minimum number of gates required to implement the Boolean function (AB+C) if we have to use only 2-input NOR gates?
A
2
B
3
C
4
D
5
Question 6 Explanation: 
NOR is Complement of OR
AB+C
= (A+C)(B+C) ← Distribution of + over
= ((A+C)’+(B+C)’)’
1st NOR- (A+C)’. Let X = (A+C)’
2nd NOR- (B+C)’. Let Y = (B+C)’
3rd NOR- (X+Y)’
Question 7
How many 32K × 1 RAM chips are needed to provide a memory capacity of 256K-bytes?
A
8
B
32
C
64
D
128
Question 7 Explanation: 
Each chip capacity = 32K×1- bit
Needed memory capacity = 256K-bytes = 256K*8 bits
Number of chips needed = 256K*8 / 32K×1= 64
Question 8
A CPU generally handles an interrupt by executing an interrupt service routine
A
As soon as an interrupt is raised.
B
By checking the interrupt register at the end of fetch cycle.
C
By checking the interrupt register after finishing the execution of the current instruction.
D
By checking the interrupt register at fixed time intervals.
Question 8 Explanation: 
As soon as an interrupt is raised the corresponding register is set. But CPU acts on it only after execution of its current instruction. This is followed to ensure integrity of instructions.
Question 9
In which one of the following page replacement policies, Belady’s anomaly may occur?
A
FIFO
B
Optimal
C
LRU
D
MRU
Question 9 Explanation: 
Bélády's anomaly is the phenomenon in which increasing the number of page frames results in an increase in the number of page faults for certain memory access patterns. This phenomenon is commonly experienced when using the first-in first-out.
Question 10
The essential content(s) in each entry of a page table is / are
A
Virtual page number
B
Page frame number
C
Both virtual page number and page frame number
D
Access right information
Question 10 Explanation: 
For every page table it contains page frame number.
Virtual page number can represents index in the page table to get the page frame number.
Question 11
What is the number of swaps required to sort n elements using selection sort, in the worst case?
A
θ(n)
B
θ(n log n)
C
θ(n2)
D
θ(n2 logn)
Question 11 Explanation: 
Selection sort – There is no Worst case input for selection sort. Since it searches for the index of kth minimum element in kth iteration and then in one swap, it places that element into its correct position. For n-1 iterations of selection sort, it can have O(n) swaps. Selection Sort does a significant number of comparisons before moving each element directly to its final intended position. At most the algorithm requires N swaps. once we swap an element into place, you never go back again.So it is great for writes O(n) but not so great (at all) for reads — O(n2). It isn’t well-suited to generalized sorting, but might work well in specialized situations like EEPROM (where writes are inordinately expensive).
Question 12
S → aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of
A
All palindromes.
B
All odd length palindromes.
C
Strings that begin and end with the same symbol.
D
All even length palindromes.
Question 12 Explanation: 
From the grammar, we can easily infer that it generates all the palindromes of odd length, for ex: strings {aba, bab, aaa, bbb, ….}
Question 13
 
A
P Only
B
Q Only
C
Both P and Q
D
Neither P nor Q
Question 13 Explanation: 
Bellman-Ford shortest path algorithm is a single source shortest path algorithm. So it can only find cycles which are reachable from a given source, not any negative weight cycle. Consider a disconnected where a negative weight cycle is not reachable from the source at all. If there is a negative weight cycle, then it will appear in shortest path as the negative weight cycle will always form a shorter path when iterated through the cycle again and again.
More Info: The Dijkstra'a algorithm:
--A greedy algorithm
--Works when weights are all non-negative
The bellman ford algorithm: If there is a negative cycle, there is no solution, but negative weight edges are allowed.
– Add this cycle again can always produces a less weight path
---If there is no negative cycle, a shortest path has at most |V|-1 edges
---A dynamic programming algorithm
Note: Dijkastra is faster than Bellman-Ford
Question 14
Let πA be a problem that belongs to the class NP. Then which one of the following is TRUE?
A
There is no polynomial time algorithm for πA.
B
If πA can be solved deterministically in polynomial time,then P = NP.
C
If πA is NP-hard, then it is NP-complete.
D
πA may be undecidable.
Question 14 Explanation: 
As per the above question, only option C is correct because it is an standard definition of NP- Complete. Rest of the options are violating their definition and properties.
NP-Complete: In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes. In this context, NP stands for "nondeterministic polynomial time". The set of NP-complete problems is often denoted by NP-C or NPC.
Standard Definition:
A decision problem C is NP-complete if:
1. C is in NP, and
2. Every problem in NP is reducible to C in polynomial time.
C can be shown to be in NP by demonstrating that a candidate solution to C can be verified in polynomial time. Note that a problem satisfying condition 2 is said to be NP-hard, whether or not it satisfies condition 1. A consequence of this definition is that if we had a polynomial time algorithm (on a UTM, or any other Turing-equivalent abstract machine) for C, we could solve all problems in NP in polynomial time.
Note: As per Present GATE syllabus NP- Complete and NP- Hard not required
Question 15
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
A
The set of all strings containing the substring 00.
B
The set of all strings containing at most two 0’s.
C
The set of all strings containing at least two 0’s.
D
The set of all strings that begin and end with either 0 or 1.
Question 15 Explanation: 
Option A is false, as the regular expression generates string “010” which doesn’t have “00” as substring. Option B is false, as we can have the string “000” from the given regular expression, which has more than two 0’s. Option D is false, as we cannot generate the string “01” from the given regular expression and according to option D, string “01” must be generated by regular expression, which clearly shows option D is not correct language as per regular expression.
Question 16
Which one of the following is FALSE?
A
There is unique minimal DFA for every regular language.
B
Every NFA can be converted to an equivalent PDA.
C
Complement of every context-free language is recursive.
D
Every non-deterministic PDA can be converted to an equivalent deterministic PDA.
Question 16 Explanation: 
As we know there are several languages (CFL) for which we only have NPDA, i.e. these languages cannot be recognized by DPDA. For example
L= {wwr | w ϵ {a,b}* } is a CFL but not DCFL, i.e. it can be recognized by NPDA but not by DPDA.
Question 17
     
A
P-4, Q-1, R-2, S-3
B
P-3, Q-1, R-4, S-2
C
P-3, Q-4, R-1, S-2
D
P-2, Q-1, R-4, S-3
Question 17 Explanation: 
Lexical analysis phase uses regular expression to identify the pattern of tokens, PDA is used in CFG and hence syntax analysis phase is related to PDA. Data flow analysis is done in code optimization phase and register allocation is related to code generation phase.
Question 18
A
6
B
8
C
14
D
15
Question 18 Explanation: 
int x=15;
printf(fun(5,&x));
The code is implemented using Tail Recursion.
fun(5,15)

fun(4,15)

fun(3,15)

fun(2,15)

fun(1,15)
→ First we will trace fun(1,15) which returns 1.
→ Then trace fun(2,15) using fun(1,15) value, it returns 2.
→ Then fun(3,15), it returns 3≃(1+2)
→ Then fun(4,15), it returns 5=(2+3)
→ Then fun(5,15), it returns 8=(3+5)
If you call fun(6,15) then it will return 13=(5+8)
Here fun(n,*x)≃fun(n-1,&x)+fun(n-2,&x), where fun(n-1,&x) is storing in variable ‘t’ & fun(n-2,&x) is storing in variable x(*f-p).
∴ The program is nth Fibonacci number.
Question 19
 
A
I-II-III-IV-V
B
V-IV-III-II-I
C
I-III-V-II-IV
D
IV-II-V-III-I
Question 20
 
A
〈2, 2, 3〉 and 〈2, 3, 2〉
B
〈2, 2, 3〉 and 〈2, 2, 3〉
C
〈2, 3, 2〉 and 〈2, 3, 2〉
D
〈2, 3, 2〉 and 〈2, 2, 3〉
Question 21
   
A
0.453
B
0.468
C
0.485
D
0.492
Question 21 Explanation: 
P(0) = Probability of getting odd no. face.
P(e) = Probability of getting even no. face.
It is given that,
P(0) = 0.9 P(e) ----- (I)
Also we know that,
P(0) + P(e) = 1 ----- (II)
Solving equation (I) and (II) we get,
P(e) = 0.52
Also even no. can be 2 or 4 or 6.
And given in question that P(2) = P(4) = P(6).
So, 3 × P(2) = 0.52
P(2) = 0.175
So, P(2) = P(4) = P(6) = 0.175
Also in question it is given that,
P(e/>3) = 0.75
P(even no. greater than 3)/ P(no. greater than 3) = 0.75
P(4,6)/P(>3) = 0.75
(0.175×2)/P(>3) = 0.75
P(>3) = 0.35/0.75 = 0.467
Question 22
A
a, b are generators
B
b, c are generators
C
c, d are generators
D
d, a are generators
Question 22 Explanation: 
Each element of set can be written as a power of g in multiplicative notation, or as a multiple of g in additive notation. This element g is called a generator of the group.
We can observe that, a is an identity element. ( a *x = x ). An identity element cannot be a generator, as it cannot produce any other element ( always a*a*... = a).
Also, b*b =a, so it also cannot produce all other elements ( always b*b*... =a , where a is identify element).
c,d are able to produce other elements like { c*c =b, c*(c*c) = c*b= d, c*(c*(c*c))) = c*(c*b)= c*d=a. }. Similar with d.
Question 23
A
∀x(P(x) → (G(x) ∧ S(x)))
B
∀x((G(x) ∧ S(x)) → P(x))
C
∃x((G(x) ∧ S(x)) → P(x)
D
∀x((G(x) ∨ S(x)) → P(x))
Question 23 Explanation: 
Interpreting the options will lead to
(A) for all ornaments, if it is precious then they should be gold and silver.
But, given statement does not says that, “ only gold and silver are precious “ . So this is wrong.
(B) For all ornaments, which contains gold and silver are precious.

Which is only the shaded region in the venn diagrams. But, it misses p,r regions. So, this is wrong option.
C) Some ornaments, which are gold and silver are precious. It is false, because all gold or silver ornaments are precious.
D) For all ornaments, Any ornament which is gold or silver is precious. Which is true.
Question 24
 
A
¬Q□¬P
B
P□¬Q
C
¬P□Q
D
¬P□¬Q
Question 24 Explanation: 
The options are simple to draw the truth table then go with the corresponding options.

P∨Q=P□️Q
So, option B is correct.
Question 25
 
A
0
B
1
C
ln 2
D
1/2 ln 2
Question 25 Explanation: 

Question 26
A
I and III
B
I and IV
C
II and III
D
II and IV
Question 26 Explanation: 
I) ¬∀x(P(x)) = ∃x(¬P(x)) [De morgan's Law]
II ) ¬∃x(P(x))= ∀x(~P(x))
III) ¬∃x(¬P(x)) = ∀x(P(x))
Question 27
A
3
B
4
C
5
D
6
Question 27 Explanation: 
Consider the below given FSM (represented as graph)

From the given FSM we can clearly see that, if we start from initial state (00) and follow the input “101” {highlighted in RED color},
{state 00, 1} -> state “01” , output 0,
{state 01, 0} -> state “10” , output 0,
{state 10, 1} -> state “01” , output 1,
Hence it require an input string of minimum length 3, which will take the machine to the state A=0, B=1 with Output = 1.
Question 28
A
16
B
23
C
28
D
30
Question 28 Explanation: 
Question 29
 
A
3
B
8
C
129
D
216
Question 29 Explanation: 
It is given that cache contains 16 blocks, it is 4-way set associative cache.
So number of sets = 16 / 4 = 4
Given main memory blocks will be mapped to one of the 4 sets.
The given blocks are 0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155, and they will be mapped to following sets(Since there are 4 sets we get the set number by doing mod 4):
0, 3, 1, 0, 3, 0, 1, 3, 0, 1, 3, 0, 0, 0, 1, 0, 3
The cache mapping and the replacement using LRU can be seen from the below diagram.

We can see that at the end of mapping the given block pattern block number 216 is not in the cache.
Question 30
 
A
All processes will finish without any deadlock.
B
Only P1 and P2 will be in deadlock.
C
Only P1 and P3 will be in a deadlock.
D
All three processes will be in deadlock.
Question 30 Explanation: 
Process P1:

t=0; req R2-2
t=1; req R3-1
t=3; req R1-2
t=5; release R2-1
& R1-1
t=7; release R3-1
t=8; req R4-2
t=10; finish:After completion of P, it releases all the resources.
Process P2:
t=0; req R3-2
t=2; req R4-1
t=4; req R1-1
t=6; releases R3-1
t=8; finishes
It releases all the resources.
Process P3:

t=0; req R4-1
t=2; req R1-2
t=5; releases R1-2
t=7; req R2-1
t=8; req R3-1
t=9; finishes
It releases all the resources.
All processes will finish without any deadlock.
Question 31
 
A
95 ms
B
119 ms
C
233 ms
D
276 ms
Question 31 Explanation: 
The given sequence is
4, 34, 10,7, 19, 73, 2, 15, 6, 20
Arrange the sequence in order
2, 4, 6, 10, 15, 19, 20, 34, 73

⇒ 1 ms to move from one cylinder to adjacent one
⇒ (16*1)+(14*1)+(1*1)+(4*1)+(5*1)+(3*1)+(1*1)+(2*1)+(2*1)+(71*1)
⇒ 16+14+1+4+5+3+1+2+2+71
⇒ 119 ms
Question 32
 
A
I and II
B
I and III
C
II and III
D
II and IV
Question 32 Explanation: 
Statement I is false, if a process makes a transition D, then it result to perform a transition B immediately not A.
Statement II is true, a process can move to ready state when I/O completes irrespective of other process being in running state or not.
Statement III is true, the transition C, represents preemptive scheduling.
Statement IV is false, because it is preemptive scheduling.
Correct Answer is Option-C (II & III are true).
Question 33
 
A
I only
B
I and II
C
II and III
D
IV only
Question 33 Explanation: 
The given solution is the basic test-and-set solution. So there is no possibility of getting deadlock.
It is not using any queue to avoid starvation and there is no use of FIFO.
In CS, only one process can enter.
So, Answer is option A.
Question 34
A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because
A
It reduces the memory access time to read or write a memory location.
B
It helps to reduce the size of page table needed to implement the virtual address space of a process.
C
It is required by the translation lookaside buffer.
D
It helps to reduce the number of page faults in page replacement algorithms.
Question 34 Explanation: 
In multilevel page table size is too big to fit in contiguous space then page tables are to be divided into different levels.
Question 35
 
A
θ(n)
B
θ(n log n)
C
θ(n2)
D
θ(n2log n )
Question 35 Explanation: 
The above recurrence relation is form of master theorem. So, we can apply directly master's theorem T(n) = aT(n/b) + nk logp n)
The recurrence relation is T(n) = T(n/3) + cn
Here a=1 , b=3, k=1, p=0.
So, ak and p>=0. So, it comes under case 3.
Therefore T(n) = θ(nk(logpn)) => θ(n1(log0 n)) => θ(n)
Question 36
The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
A
B
C
D
Question 36 Explanation: 
Given keys: 12, 18, 13, 2, 3, 23, 5 & 15
They are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k)=k mod 10 & linear probing is used.

12 % 10 = 2
18 % 10 = 8
13 % 10 = 3
2 % 10 = 2 (Index 4 is empty)
3 % 10 = 3 (Index 5 is empty)
23 % 10 = 3 (Index 6 is empty)
5 % 10 = 5 (Index 7 is empty)
15 % 10 = 5 (Index 9 is empty)
Hence Option C is correct.
A & B doesn’t include all the keys & option D is similar to chaining. So, will go with C.
Question 37
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
A
2
B
3
C
4
D
5
Question 37 Explanation: 
The maximum height of any AVL tree with 7 nodes is, [where root is considered as height 0]
2h-1=7
∴ h=3
Question 38
 
A
(b,e)(e,f)(a,c)(b,c)(f,g)(c,d)
B
(b,e)(e,f)(a,c)(f,g)(b,c)(c,d)
C
(b,e)(a,c)(e,f)(b,c)(f,g)(c,d)
D
(b,e)(e,f)(b,c)(a,c)(f,g)(c,d)
Question 38 Explanation: 
To find Minimum Spanning Tree(MST) using Kruskal’s algorithm we have to follow standard procedure is
1. It follows like forest structure(Means we are disconnecting all the edges connected to vertices).
2. Sort edge weights in Ascending order.
3. Always select the minimum edge weight first according to Spanning Tree rules.
As per the options below Option A,B,C, are following correct order but Option D is violating Kruskal’s procedure. The edge between a-c of weight 4 comes after b-c of weight 3.
Question 39
In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort? 
A
θ(n)
B
θ(n log n)
C
θ(n2)
D
θ(n2 log n )
Question 39 Explanation: 

n→n/(4/3)→n/(4/3)2→n/(4/3)3-----n/(4/3)k=1
n/(4/3)k=1
⇒n=(4/3)k⇒k=log4/3n [k=no. of levels]
In each level workdone = Cn
So, total workdone = Cn⋅log4/3n=(nlog4/3n)
Question 40
 
A
Not recursive
B
Regular
C
Context free but not regular
D
Recursively enumerable but not context free
Question 40 Explanation: 
The strings in L1 are { c, abc, cab, abcab, aabbcab, abcaabb, aabbcaabb,.....} and the strings in L2 are { ϵ, a, b, c, ab, bc, ac, abc, aabc, abbc, abcc, aabbcc, …..}
Clearly, L1 ∩ L2 is {axbx | x ≥0}, which is CFL but not regular.
Question 41
 
A
begin either with 0 or 1
B
end with 0
C
end with 00
D
contain the substring 00
Question 41 Explanation: 
Option A is false, as the DFA is not accepting the string “10”, option B is false as the DFA is not accepting the string “10” . Option D is false as the DFA doesn’t accept the string “1001” which has “00” as substring. Hence option C , every strings end with “00” is correct.
Question 42
 
A
I and II
B
I and IV
C
III and IV
D
I, III and IV
Question 42 Explanation: 
Statement II is false, as a programming language which allows recursion requires dynamic storage allocation. Statement III is false, as L-attributed definition (assume for instance the L-attributed definition has synthesized attribute only) can be evaluated in bottom up framework.
Statement I is true, as the bottom up and top down parser take O(n) time to parse the string , i.e. only one scan of input is required.
Statement IV is true,Code improving transformations can be performed at both source language and intermediate code level. For example implicit type casting is also a kind of code improvement which is done during semantic analysis phase and intermediate code optimization is a topic itself which uses various techniques to improve the code such as loop unrolling, loop invariant.
Question 43
 
A
S1 and S2
B
S2 and S3
C
S3 only
D
S4 only
Question 43 Explanation: 
S1 has a cycle from T1→T2 and T2→T1 Schedule S2,

Dependency graph is,

So, there is no cycle.
Schedule S3,

Dependency graph is,

S4 also has a cycle T1→T2 and T2→T1.
So, S2 and S3 are conflict serializable.
Question 44
 
A
2
B
3
C
4
D
5
Question 44 Explanation: 
Insert 10:

Insert 3:

Insert 6:

Insert 4:

Insert 2:

Insert 1:

So, total splits are 3.
Question 45
A
I and II
B
I and III
C
II and IV
D
III and IV
Question 45 Explanation: 
R={a,b,c}
S={c}

It looks like Division operator. Since a division operator in E(A,B)/ P(B) will be equal to

Now replacing A=R-S P=r
B=S
E=r
we will get,

equivalent to I
∴ It is equivalent to division operator.
⇒ r(R-S,S)/r(S)

This logical statement means that
① Select t(R-S) from r such that
② for all tuples U in S,
③ there exists a tuple V in r, such that
④ U=V[S] & t=V[R-S]
A(x,y) & B(y)
A/B = {(x) | ∃(x,y)∈A(y)∈B}
which means that A/B contains all x tuples, such that for every tuple in B, there is an xy tuple in A.
So, this is just equivalent to I.

This logical statement means that
① Select t(R-S) from r such that
② for all tuples V in r,
③ there exists a tuple U in r, such that
④ U=V[S] & t=V[R-S]
⇒ Select (R-S) values from r, where the S value is in (r/r), which will be true only if S in r is a foreign key referring to S is r.

This selects (a,b) from all tuples from r which has an equivalent value in S.
Question 46
 
A
I and II
B
I and III
C
II and IV
D
III and IV
Question 46 Explanation: 
To generate the encryption and decryption keys, we can proceed as follows.
1. Generate randomly two “large” primes p and q.
2. Compute n=pq and ∅=(p-1)(q-1).
3. Choose a number e so that
gcd(e,∅)=1
4. Find the multiplicative inverse of e modulo ∅, i.e., find d so that
ed≡1 (mod ∅)
This can be done efficiently using Euclid’s Extended Algorithm.
The encryption public key is KE=(n,e) and the decryption private key is KD=(n,d).
The encryption function is
E(M)=Me mod n
The decryption function is
D(M)=Md mod n
Question 47
A
0.015/s
B
0.064/s
C
0.135/s
D
0.327/s
Question 47 Explanation: 
32 bits are used to represent a sequence number. So we have 232 different sequence number.
The maximum packet lifetime is given is given 64s.
Maximum data rate possible(bandwidth) to avoid the wraparound = 232/64 = 226 Byte/sec.
The clock counter increments once per milliseconds = That means when then counter increments next possible sequence number is generated. The packet lifetime is 64 seconds and after this 64 seconds next sequence number is come. So that means in this 64 seconds only 1 sequence number is generated.
Hence the minimum rate is = 1/64 = 0.015/sec.
Question 48
Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?
A
G(x) contains more than two terms
B
G(x) does not divide 1+xk, for any k not exceeding the frame length
C
1+x is a factor of G(x)
D
G(x) has an odd number of terms
Question 48 Explanation: 
Odd number of bit errors can be detected if G(x) contains (x+1) as a factor.
Question 49
A
II and III
B
II and III
C
I and III
D
I, II and III
Question 50

A
I and II
B
II and III
C
I and III
D
I, II and III
Question 51
     
A
505035
B
505036
C
505037
D
505038
Question 51 Explanation: 
By default the cylinders numbering starts from 0. In the given hard disk there are 1000 cylinders, 1st cylinder is numbered 0, 2nd cylinder is numbered 1 and so on 1000th cylinder is numbered 999.
To reach a cylinder numbered n, we need to cross cylinders numbered from 0 to n-1.
To reach cylinder numbered 400 (401th cylinder) we need to skip cylinders numbered from 0 to 399, (from cylinder number 0 to 399 there are total 400 cylinders).
Each cylinder consists of 10 plates with 2 recording surfaces and 63 sectors per track.
So total number of tracks to be crossed to reach cylinder numbered 400 = 400 * (10*2) * 63 = 504,000 sectors.
Then, to reach the 16th surface of the cylinder numbered 400, we need to skip another 16*63 = 1,008 sectors.
Finally, to find the 29 sector, we need to move another 29 sectors.
In total, we moved 504,000 + 1,008 + 29 = 505,037 sectors.
Hence, option C is the answer.
Question 52
 
A
〈0, 15, 31〉
B
〈0, 16, 30〉
C
〈0, 16, 31〉
D
〈0, 17, 31〉
Question 52 Explanation: 
We know in each track there are 63 sectors. And we know there is one track per surface.
From the given options we can calculate the sector numbers as
Option A - 15*63+31 = 976
Option B - 16*63+30 = 1038
Option C - 16*63+31 = 1039
Option D - 17*63+31 = 1102
Hence Option C is the answer.
Question 53
 
A
expr1 ≡ l(i-1, j) + 1
B
expr1 ≡ l(i, j-1)
C
expr2 ≡ max(l(i-1, j), l(i, j-1))
D
expr2 ≡ max(l(i-1,j-1), l(i,j))
Question 53 Explanation: 
Question 54

A
All elements L should be initialized to 0 for the values of l(i,j) to be properly computed.
B
The values of l(i,j) may be computed in a row major order or column major order of L(M,N).
C
The values of l(i,j) cannot be computed in either row major order or column major order of L(M,N).
D
L[p,q] needs to be computed before L[r,s] if either p
Question 54 Explanation: 
LCS procedure can followed by either row major or column major order. We can get the same solution by any order. The above question looks very big but they are explaining the procedure of LCS.
Question 55
 
A
Find the names of all suppliers who have supplied a non-blue part.
B
Find the names of all suppliers who have not supplied a non-blue part.
C
Find the names of all suppliers who have supplied only blue parts.
D
Find the names of all suppliers who have not supplied only blue parts.
Question 55 Explanation: 



If we execute the given query the output will be S3 and S4 i.e., names of all suppliers who didn’t supply blue parts which is option (A).
Option (D) says names of suppliers who didn’t supply only blue parts that means, supplier should supply all other parts for sure and shouldn’t supply blue part.
Question 56
 
A
The schema is in BCNF
B
The schema is in 3NF but not in BCNF
C
The schema is in 2NF but not in 3NF
D
The schema is not in 2NF
Question 56 Explanation: 
From the given data the FDs will be
(Sid, Street) → Sname
As Sid is a primary key, then
(Sid, Street) will be super key.
Hence, it is in BCNF.
Question 57
 
A
I = 2
B
I = 3
C
I = 4
D
I = 5
Question 57 Explanation: 
Transmission time (Tt)=1000/106 seconds =1 ms
Maximum number of frames that can be transmit to maximally pack them is=(Tt+2Tp)/Tx = (25+1)/1=26 which is window size
Minimum sequence numbers required = 26
Minimum number of bits required for sequence number is 5.
Question 58

A
16ms
B
18ms
C
20ms
D
22ms
Question 58 Explanation: 

From above diagram we can say that Total RTT will be
1ms (transmitting time for first frame)
+ 25ms (propagation delay from S to R)
+ 1ms (transmitting time for piggybacked ACK)
+ 25ms (propagation delay from R to S)
= 52 ms
Also total time for sender needed to transmit 32 frames (22 = 25 = 32) is 32×1ms = 32ms
So sender has to wait for,
(52 - 32)ms
= 20ms
Question 59
A
{25,12,16,13,10,8,14}
B
{25,14,13,16,10,8,12}
C
{25,14,16,13,10,8,12}
D
{25,14,12,13,10,8,16}
Question 59 Explanation: 
Option-A:

Violating a max heap property.
Option-B:

Violating a max heap property.
Option-C:
Question 60
   
A
{14,13,12,10,8}
B
{14,12,13,8,10}
C
{14,13,8,12,10}
D
{14,13,12,8,10}
Question 60 Explanation: 
Actual Graph:

Step 1: Delete 25

Step 2:

Step 3: Delete 16

Step 4:

Step 5:

∴ Finary array elements: 14, 13, 12, 8, 10.
There are 60 questions to complete.