UGC NET CS 2017 Jan paper3
Question 1 
Which of the following is an interrupt according to temporal relationship with system clock?
Maskable interrupt  
Periodic interrupt  
Division by zero  
Synchronous interrupt 
Question 1 Explanation:
Synchronous interrupts are produced by the CPU control unit while executing instructions and are called synchronous because the control unit issues them only after terminating the execution of an instruction.
This interrupt according to temporal relationship with system clock.
Asynchronous interrupts are generated by other hardware devices at arbitrary times with respect to the CPU clock signals..
Maskable Interrupts  Those interrupts whose request can be denied by microprocessor.
eg RST 1, RST2, RST 5, RST 6.5 etc..
Non maskable Interrupts  Interrupts whose request cannot be denied. eg RST 4.5 or TRAP ,RESET IN.
. Periodic interrupts to cause a software task to be executed on a periodic basis.
This interrupt according to temporal relationship with system clock.
Asynchronous interrupts are generated by other hardware devices at arbitrary times with respect to the CPU clock signals..
Maskable Interrupts  Those interrupts whose request can be denied by microprocessor.
eg RST 1, RST2, RST 5, RST 6.5 etc..
Non maskable Interrupts  Interrupts whose request cannot be denied. eg RST 4.5 or TRAP ,RESET IN.
. Periodic interrupts to cause a software task to be executed on a periodic basis.
Question 2 
Which of the following is incorrect for virtual memory?
Large programs can be written  
More I/O is required  
More addressable memory available  
Faster and easy swapping of process 
Question 2 Explanation:
OptionA TRUE: Implementing virtual memory is need to write large program
OptionB TRUE: It require more I/O
OptionC FALSE: Not more addressable memory available.
OptionD TRUE: Virtual memory is faster and easy swapping of process.
OptionB TRUE: It require more I/O
OptionC FALSE: Not more addressable memory available.
OptionD TRUE: Virtual memory is faster and easy swapping of process.
Question 3 
The general configuration of the microprogrammed control unit is given below:
What are blocks B and C in the diagram respectively?
What are blocks B and C in the diagram respectively?
Block address register and cache memory  
Control address register and control memory  
Branch register and cache memory  
Control address register and random access memory 
Question 3 Explanation:
Question 4 
Match the following :
a(iv), b(iii), c(i), d(ii)  
a(iv), b(i), c(iii), d(ii)  
a(iv), b(ii), c(i), d(iii)  
a(iv), b(iii), c(ii), d(i) 
Question 4 Explanation:
Implied → Specified implicitly in the definition of instruction
Immediate→ Registers which are in CPU
Register→ Specified in the register
Register Indirect→ Specified implicitly in the definition of instruction
Immediate→ Registers which are in CPU
Register→ Specified in the register
Register Indirect→ Specified implicitly in the definition of instruction
Question 5 
In 8085 microprocessor, the digit 5 indicates that the microprocessor needs:
–5 volts, +5 volts supply  
+5 volts supply only  
–5 volts supply only  
5 MHz clock 
Question 5 Explanation:
Before 8085 microprocessors require +5V, 5V and 12V. In 8085 microprocessor need +5 volts supply only.
Question 6 
In 8085, which of the following performs : load register pair immediate operation?
LDAX rp  
LHLD addr  
LXI rp, data  
INX rp 
Question 6 Explanation:
LDAX: Load accumulator indirect( This instruction copies the contents of that memory location into the accumulator. )
LHLD: Load H and L register direct ( This instruction loads the contents of the 16 bit memory location into the H and L register pair. )
LXI: Load register pair immediate( The instruction loads 16bit data in the register pair designated in the operand.)
INX: Increment register pair by 1.( It will increment the register value by 1.)
LHLD: Load H and L register direct ( This instruction loads the contents of the 16 bit memory location into the H and L register pair. )
LXI: Load register pair immediate( The instruction loads 16bit data in the register pair designated in the operand.)
INX: Increment register pair by 1.( It will increment the register value by 1.)
Question 7 
Consider following schedules involving two transactions:
S1 : r1(X); r1(Y); r2(X); r2(Y); w2(Y); w1(X)
S2 : r1(X); r2(X); r2(Y); w2(Y); r1(Y); w1(X)
Which of the following statement is true?
Both S1 and S2 are conflict serializable.  
S1 is conflict serializable and S2 is not conflict serializable.  
S1 is not conflict serializable and S2 is conflict serializable.  
Both S1 and S2 are not conflict serializable. 
Question 7 Explanation:
Question 8 
Which one is correct w.r.t. RDBMS ?
primary key ⊆ super key ⊆ candidate key  
primary key ⊆ candidate key ⊆ super key  
super key ⊆ candidate key ⊆ primary key  
super key ⊆ primary key ⊆ candidate key 
Question 8 Explanation:
Question 9 
Let pk(R) denotes primary key of relation R. A manytoone relationship that exists between two relations R_{1} and R_{2} can be expressed as follows :
pk(R_{2}) → pk(R_{1})  
pk(R_{1}) → pk(R_{2})  
pk(R_{2}) → R_{1} ∩ R_{2}  
pk(R_{1}) → R_{1} ∩ R_{2} 
Question 9 Explanation:
Consider an example, where we have two entities Employee(whose primary key is R_{1}) and Department(whose primary key is R_{2}) and a department have many employees and each employee works in one department i.e. many to one relationship.
Question 10 
For a database relation R(A, B, C, D) where the domains of A, B, C and D include only atomic values, only the following functional dependencies and those that can be inferred from them are :
A → C
B → D
The relation R is in _______.
A → C
B → D
The relation R is in _______.
First normal form but not in second normal form.  
Both in first normal form as well as in second normal form.  
Second normal form but not in third normal form.  
Both in second normal form as well as in third normal form. 
Question 10 Explanation:
Candidate key is ab.
Since all a, b, c, d are atomic. So the relation is in 1NF.
Checking the FD's
a → c
b → d
We can see that there is partial dependencies. So it is not 2NF.
So answer is option (A).
Since all a, b, c, d are atomic. So the relation is in 1NF.
Checking the FD's
a → c
b → d
We can see that there is partial dependencies. So it is not 2NF.
So answer is option (A).
Question 11 
Here, emp_name is primary key. Consider the following SQL query
Select emp name
From works T
Where salary > (select avg (salary)
from works S
where T.company _ name = S.company _name)
The above query is for following :
Find the highest paid employee who earns more than the average salary of all employees of his company  
Find the highest paid employee who earns more than the average salary of all the employees of all the companies.  
Find all employees who earn more than the average salary of all employees of all the companies.  
Average salary of all employees of their company. 
Question 11 Explanation:
Question 12 
If following sequence of keys are inserted in a B+ tree with K(=3) pointers:
8, 5, 1, 7, 3, 12, 9, 6
Which of the following shall be correct B+ tree?
Question 12 Explanation:
Question 13 
Which of the following statement(s) is/are correct ?
Persistence is the term used to describe the duration of phosphorescence.  
The control electrode is used to turn the electron beam on and off.  
The electron gun creates a source of electrons which are focused into a narrow beam directed at the face of CRT.  
All of the above 
Question 13 Explanation:
TRUE: Persistence is the term used to describe the duration of phosphorescence. Phosphorescence is a process in which energy absorbed by a substance is released relatively slowly in the form of light.
TRUE: The control electrode is used to turn the electron beam on and off.
TRUE: The electron gun creates a source of electrons which are focused into a narrow beam directed at the face of CRT.
TRUE: The control electrode is used to turn the electron beam on and off.
TRUE: The electron gun creates a source of electrons which are focused into a narrow beam directed at the face of CRT.
Question 14 
A segment is any object described by GKS commands and data that start with CREATE SEGMENT and Terminates with CLOSE SEGMENT command. What functions can be performed on these segments ?
Translation and Rotation  
Panning and Zooming  
Scaling and Shearing  
Translation, Rotation, Panning and Zooming 
Question 15 
Match the following:
ai, bii, ciii, di  
ai, biii, cii, div  
aiv, biii, cii, di  
aiv, bii, ci, diii 
Question 16 
Below are the few steps given for scanconverting a circle using Bresenham’s Algorithm. Which of the given steps is not correct ?
Compute d = 3 – 2r (where r is radius)  
Stop if x > y  
If d < 0, then d = 4x + 6 and x = x + 1  
If d ≥, then d = 4 * (x – y) + 10, x = x + 1 and y = y + 1 
Question 16 Explanation:
Scan converting a circle using Bresenham’s algorithm:
1 Initially X = 0 , Y = R and D = 3 – 2R
2. While (X < Y)
3. Call Draw Circle(X_{c}, Y_{c}, X, Y)
4. Set X = X + 1
5. If (D < 0) Then
6. D = D + 4X + 6
7. Else
8. Set Y = Y – 1
9. D = D + 4(X – Y) + 10
10. End If
11. Draw Circle(X_{c}, Y_{c}, X, Y) /* calling function call */
12. End While
1 Initially X = 0 , Y = R and D = 3 – 2R
2. While (X < Y)
3. Call Draw Circle(X_{c}, Y_{c}, X, Y)
4. Set X = X + 1
5. If (D < 0) Then
6. D = D + 4X + 6
7. Else
8. Set Y = Y – 1
9. D = D + 4(X – Y) + 10
10. End If
11. Draw Circle(X_{c}, Y_{c}, X, Y) /* calling function call */
12. End While
Question 17 
Which of the following is/are side effects of scan conversion ?
a. Aliasing
b. Unequal intensity of diagonal lines
c. Overstriking in photographic applications
d. Local or Global aliasing
a. Aliasing
b. Unequal intensity of diagonal lines
c. Overstriking in photographic applications
d. Local or Global aliasing
a and b  
a, b and c  
a, c and d  
a, b, c and d 
Question 17 Explanation:
Side effects of scan conversions are
1. Aliasing
2. Unequal intensity of diagonal lines
3. Overstriking in photographic applications
4. Local or Global aliasing
2. Unequal intensity of diagonal lines
3. Overstriking in photographic applications
4. Local or Global aliasing
Question 18 
Consider a line AB with A=(0,0) and B=(8,4). Apply a simple DDA algorithm and compute the first four plots on this line.
[(0, 0), (1, 1), (2, 1), (3, 2)]  
[(0, 0), (1, 1.5), (2, 2), (3, 3)]  
[(0, 0), (1, 1), (2. 2.5), (3, 3)]  
[(0, 0), (1, 2), (2, 2), (3, 2)] 
Question 18 Explanation:
Question 19 
Which of the following are not regular?
(A) Strings of even number of a’s.
(B) Strings of a’s, whose length is a prime number.
(C) Set of all palindromes made up of a’s and b’s.
(D) Strings of a’s whose length is a perfect square.
(A) and (B) only  
(A), (B) and (C) only  
(B), (C) and (D) only  
(B) and (D) only 
Question 19 Explanation:
L = { a^{2}, a^{3}, a^{5}, a^{7}, a^{11}, a^{13}, a^{17}...................}
It is not a regular language. A language is regular if the difference between two consecutive strings is the same or we can say the language is in AP(arithmetic progression). But here if you see the difference between two consecutive strings/terms is not the same. Hence it is not regular.
Statement (C):
L = {ab, aabb, ................... abab, baba, ababa, aababa, baabb, ..................}
It is also not regular language because the difference between two consecutive strings/terms is not same.
Statement (D): L = { a^{1}, a^{4}, a^{9}, a^{16}, a^{25}, a^{36}, a^{49}...............}
It is also not a regular language because the difference between two consecutive strings/terms is not the same.
It is not a regular language. A language is regular if the difference between two consecutive strings is the same or we can say the language is in AP(arithmetic progression). But here if you see the difference between two consecutive strings/terms is not the same. Hence it is not regular.
Statement (C):
L = {ab, aabb, ................... abab, baba, ababa, aababa, baabb, ..................}
It is also not regular language because the difference between two consecutive strings/terms is not same.
Statement (D): L = { a^{1}, a^{4}, a^{9}, a^{16}, a^{25}, a^{36}, a^{49}...............}
It is also not a regular language because the difference between two consecutive strings/terms is not the same.
Question 20 
Consider the languages L1 = φ and L2 = {1}. Which one of the following represents L_{1}* ∪ L_{1}*L_{2}* ?
{∈}  
{∈, 1}  
ϕ  
1* 
Question 20 Explanation:
As we know, for any regular expression R,
Rϕ = ϕR=ϕ
So L_{1} L_{2} * = ϕ
and L_{1} * = {ϕ}* = {ϵ}
So L_{1}L_{2}* ∪ L_{1}* = {ϵ}
Rϕ = ϕR=ϕ
So L_{1} L_{2} * = ϕ
and L_{1} * = {ϕ}* = {ϵ}
So L_{1}L_{2}* ∪ L_{1}* = {ϵ}
Question 21 
Given the following statements :
(A) A class of languages that is closed under union and complementation has to be closed under intersection.
(B) A class of languages that is closed under union and intersection has to be closed under complementation.
Which of the following options is correct?
(A) A class of languages that is closed under union and complementation has to be closed under intersection.
(B) A class of languages that is closed under union and intersection has to be closed under complementation.
Which of the following options is correct?
Both (A) and (B) are false.  
Both (A) and (B) are true.  
(A) is true, (B) is false.  
(A) is false, (B) is true. 
Question 21 Explanation:
be closed under intersection but if a language is not closing under either of union or complementation then it can or can not be closed under intersection.
So here, Statement (A) is true because regular language, context sensitive language and recursive language are closed under union and complementation and they are also closing under intersection but recursive enumerable language is closed under union but not under complementation but still it is closed under intersection.
Statement (B): The meaning of given statement is that if a class of languages that is closed under union and intersection then it has to be closed under complementation but if a language is not closing under either of union or intersection then it can or can not be closed under complementation.
So here, Statement (B) is false because regular language, context sensitive language, recursive language and recursively enumerable language are closed under union and intersection but only regular language, context sensitive language and recursive language are closed under complementation , recursively enumerable language is not closing under complementation after being closed under union and intersection.
Hence statement (B) is not true.
So here, Statement (A) is true because regular language, context sensitive language and recursive language are closed under union and complementation and they are also closing under intersection but recursive enumerable language is closed under union but not under complementation but still it is closed under intersection.
Statement (B): The meaning of given statement is that if a class of languages that is closed under union and intersection then it has to be closed under complementation but if a language is not closing under either of union or intersection then it can or can not be closed under complementation.
So here, Statement (B) is false because regular language, context sensitive language, recursive language and recursively enumerable language are closed under union and intersection but only regular language, context sensitive language and recursive language are closed under complementation , recursively enumerable language is not closing under complementation after being closed under union and intersection.
Hence statement (B) is not true.
Question 22 
Let G = (V, T, S, P) be a contextfree grammar such that every one of its productions is of the form A → v, with v = K > 1. The derivation tree for any W ∈ L(G) has a height h such that
log_{K}W ≤ h ≤ log_{K}((W1) / k1)  
log_{K}W ≤ h ≤ log_{K}(KW)  
log_{K}W ≤ h ≤ K log_{K}W  
log_{K}W ≤ h ≤ ((W1) / k1) 
Question 22 Explanation:
Min height of any tree is log_k W
For max height (since k>1, consider k=2) , hence it is CNF form and in CNF height is log_2 (W+1)
so in general it should be log_k ((w1) / (k1))
For max height (since k>1, consider k=2) , hence it is CNF form and in CNF height is log_2 (W+1)
so in general it should be log_k ((w1) / (k1))
Question 23 
Given the following two languages :
L_{1} = {a^{n} b^{n}  n ≥ 0, n ≠ 100}
L_{2 }= {w ∈ {a, b, c}* n_{a}(w) = n_{b}(w) = n_{c}(w)}
Which of the following options is correct ?
Both L_{1} and L_{2} are not context free language  
Both L_{1} and L_{2} are context free language.  
L_{1} is context free language, L_{2} is not context free language.  
L_{1} is not context free language, L_{2} is context free language. 
Question 23 Explanation:
Statement 1: L1 is a context free language because we can easily construct a pushdown automata which can push all a's onto the top of stack and then when b's comes as input for each "b" one "a" will be popped up. If number of a's is equal to number of b's then final stage is reached and string is accepted except the case when 100th "b" came as input we can go to a non final state and if after that any "b" came as input then the transaction can take place to a final state according to the equal number of b's and a's else we remain on that nonfinal state. So in this way a pushdown automata can be constructed for given language.
Hence L1 is a context free language.
Statement 2: L2 is not a context free language because we can push a's on the top of stack and when b's came as input we can pop one "a" for each "b" so in this way stack will get empty before comparing equal number of a, b and c. For comparing number of "c" the will be no "a or b" on the top of stack.
Hence L2 is not a context free language.
Hence L1 is a context free language.
Statement 2: L2 is not a context free language because we can push a's on the top of stack and when b's came as input we can pop one "a" for each "b" so in this way stack will get empty before comparing equal number of a, b and c. For comparing number of "c" the will be no "a or b" on the top of stack.
Hence L2 is not a context free language.
Question 24 
A recursive function h, is defined as follows :
h(m) = k, if m = 0
= 1, if m = 1
= 2 h(m – 1) + 4h(m – 2), if m ≥ 2
If the value of h(4) is 88 then the value of k is :
h(m) = k, if m = 0
= 1, if m = 1
= 2 h(m – 1) + 4h(m – 2), if m ≥ 2
If the value of h(4) is 88 then the value of k is :
0  
1  
2  
1 
Question 24 Explanation:
If k=2, 24 + 32 × 2 = 24 + 64 = 88
Each iteration:
h(2) = 2h(1) + 4h(0) = 2 + 4k
h(3) = 2h(2) + 4h(1) = 4 + 8k + 4 = 8 + 8k
h(4) = 2h(3) + 4h(2) = 16 + 16k + 8 +16k = 32k + 24 = 88 (if k=2)
Each iteration:
h(2) = 2h(1) + 4h(0) = 2 + 4k
h(3) = 2h(2) + 4h(1) = 4 + 8k + 4 = 8 + 8k
h(4) = 2h(3) + 4h(2) = 16 + 16k + 8 +16k = 32k + 24 = 88 (if k=2)
Question 25 
Suppose there are n stations in a slotted LAN. Each station attempts to transmit with a probability P in each time slot. The probability that only one station transmits in a given slot is _______.
nP(1 – P)^{n – 1}  
nP  
P(1 – P)^{n – 1}  
n^{P}(1 – P)^{n – 1} 
Question 25 Explanation:
This question can be solved by binomial distribution,
^{n}C_{1}P^{1}(1p)^{n1}
= nP(1P)^{n1}
Question 26 
Station A uses 32 byte packets to transmit messages to station B using sliding window protocol. The round trip delay between A and B is 40 milliseconds and the bottleneck bandwidth on the path between A and B is 64 kbps. The optimal window size of A is ________.
20  
10  
30  
40 
Question 26 Explanation:
Given data,
L = 32 byte
Bandwidth = 64 kbps,
2Tp = 40 millisec
Tt = L / B = 32 *8 / 64*103 = 4 millisec
a= Tp/Tt
Optimal window size (N) = 1 + 2a
N = 1 + 2a ⇒ 1+ (40/4) ⇒ 11
The correct answer is 11. OptionB is more relevant.
L = 32 byte
Bandwidth = 64 kbps,
2Tp = 40 millisec
Tt = L / B = 32 *8 / 64*103 = 4 millisec
a= Tp/Tt
Optimal window size (N) = 1 + 2a
N = 1 + 2a ⇒ 1+ (40/4) ⇒ 11
The correct answer is 11. OptionB is more relevant.
Question 27 
Let G(x) be generator polynomial used for CRC checking. The condition that should be satisfied by G(x) to correct odd numbered error bits, will be:
(1 + x) is factor of G(x)  
(1 – x) is factor of G(x)  
(1 + x2) is factor of G(x)  
x is factor of G(x) 
Question 27 Explanation:
Odd number of bit errors can be detected if G(x) contains (x+1) as a factor.
Question 28 
In a packet switching network, if the message size is 48 bytes and each packet contains a header of 3 bytes. If 24 packets are required to transmit the message, the packet size is ________.
2 bytes  
1 bytes  
4 bytes  
5 bytes 
Question 28 Explanation:
Given data,
 Message size=48 bytes
 Packet header=3 bytes
 24 packets are carrying 48 bytes of data
 Packet size=?
Step1: One packet carries maximum size is= Message size / Transmission message size
= 48 / 24
= 2 bytes
Step2: Packet size= One packet carries maximum size + new packet header size
= 2 + 3
= 5 byte
 Message size=48 bytes
 Packet header=3 bytes
 24 packets are carrying 48 bytes of data
 Packet size=?
Step1: One packet carries maximum size is= Message size / Transmission message size
= 48 / 24
= 2 bytes
Step2: Packet size= One packet carries maximum size + new packet header size
= 2 + 3
= 5 byte
Question 29 
In RSA public key cryptosystem suppose n = p ∗ q where p and q are primes. (e, n) and (d, n) are public and private keys respectively. Let M be an integer such that o < M < n and φ(n) = (p – 1)(q – 1).
Which of the following equations represent RSA public key cryptosystem ?
I. C ≡ M^{e}(mod n)
M ≡ (C)^{d}(mod n)
II. ed ≡ 1(mod n)
III. ed ≡ 1(mod φ (n))
IV. C ≡ M^{e}(mod φ (n))
M ≡ C^{d}(mod φ (n))
Which of the following equations represent RSA public key cryptosystem ?
I. C ≡ M^{e}(mod n)
M ≡ (C)^{d}(mod n)
II. ed ≡ 1(mod n)
III. ed ≡ 1(mod φ (n))
IV. C ≡ M^{e}(mod φ (n))
M ≡ C^{d}(mod φ (n))
I and II  
I and III  
II and III  
I and IV 
Question 29 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 ∅=(p1)(q1).
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 K_{E}=(n,e) and the decryption private key is K_{D}=(n,d).
The encryption function is
E(M)=M^{e} mod n
The decryption function is
D(M)=M^{d} mod n
1. Generate randomly two “large” primes p and q.
2. Compute n=pq and ∅=(p1)(q1).
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 K_{E}=(n,e) and the decryption private key is K_{D}=(n,d).
The encryption function is
E(M)=M^{e} mod n
The decryption function is
D(M)=M^{d} mod n
Question 30 
A node X on a 10 Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 2 Mbps. Token bucket is initially filled with 16 megabits. The maximum duration taken by X to transmit at full rate of 10 Mbps is _________ secs.
1  
2  
3  
4 
Question 30 Explanation:
Given data,
 A node X on a 10 Mbps network is regulated by a token bucket.
 Filled rate=2 Mbps
 Initially token bucket filled time= 16 Megabits
 Maximum duration time=?
Step1: Maximum duration time= Initially token bucket filled time / (Regulated token timeFilled rate)
= 16 / (102)
= 16 / 8
= 2 seconds
 A node X on a 10 Mbps network is regulated by a token bucket.
 Filled rate=2 Mbps
 Initially token bucket filled time= 16 Megabits
 Maximum duration time=?
Step1: Maximum duration time= Initially token bucket filled time / (Regulated token timeFilled rate)
= 16 / (102)
= 16 / 8
= 2 seconds
Question 31 
The asymptotic upper bound solution of the recurrence T(n)= 2T(n/2)+(n/lg) is relation given by
O(n^{2})  
O(n lg n)  
O(n lg lg n)  
O(lg lg n) 
Question 31 Explanation:
→ The above recurrence is not in the form of Masters theorem. It doesn't apply since f(n)=n/logn is n polynomially smaller than n^{log(base 2) 2e} for any epsilon>0.
We can apply after converting into n/logn as n*log^{1}n
2T(n/2)+n/logn is by taking a=2,b=2 ,k=1 ,p=1
T(n) = Θ(n^{log(base 2)2} log log n)
= O(n lg lg n)
We can apply after converting into n/logn as n*log^{1}n
2T(n/2)+n/logn is by taking a=2,b=2 ,k=1 ,p=1
T(n) = Θ(n^{log(base 2)2} log log n)
= O(n lg lg n)
Question 32 
Any decision tree that sorts n elements has height ________.
Ω(lg n)  
Ω(n)  
Ω(n lg n)  
Ω(n^{2}) 
Question 32 Explanation:
Theorem: Any decision tree that sorts n elements has height Ω(n lg n).
Proof:
→ The number of leaves l ≥ n!
→ Any binary tree of height h has ≤ 2^{h} leaves.
→ Hence, n! ≤ l ≤ 2^{h}
→ Take logs: h ≥ lg(n!)
→ Use Stirling’s approximation: n! > (n/e)^{n}
→ We get:
h ≥ log(n/e)^{n}
= nlg(n/e)
= nlg n  n lg e
= Ω(n lg n)
Proof:
→ The number of leaves l ≥ n!
→ Any binary tree of height h has ≤ 2^{h} leaves.
→ Hence, n! ≤ l ≤ 2^{h}
→ Take logs: h ≥ lg(n!)
→ Use Stirling’s approximation: n! > (n/e)^{n}
→ We get:
h ≥ log(n/e)^{n}
= nlg(n/e)
= nlg n  n lg e
= Ω(n lg n)
Question 33 
Redblack trees are one of many search tree schemes that are “balanced” in order to guarantee that basic dynamicset operations take ________ time in the worst case.
O(1)  
O(lg n)
 
O(n)  
O(n lg n) 
Question 34 
The minimum number of scalar multiplication required, for parenthesization of a matrixchain product whose sequence of dimensions for four matrices is <5, 10, 3, 12, 5> is
630  
580  
480  
405 
Question 34 Explanation:
Question 35 
Dijkstra’s algorithm is based on
Divide and conquer paradigm  
Dynamic programming  
Greedy Approach
 
Backtracking paradigm 
Question 35 Explanation:
Dijkstra’s algorithm is used on greedy approach for single source shortest path problem.
Question 36 
Match the following with respect to algorithm paradigms : 36
aiii, bi, cii, div  
aii, bi, civ, diii  
aii, bi, ciii, div  
biii, bii, ci, div 
Question 36 Explanation:
Merge sort→ Divide and conquer
Huffman coding→ Greedy approach
Optimal polygon triangulation→ Dynamic programming
Subset sum problem → Backtracking
Note: We can also use subset sum problem as well backtracking.
Huffman coding→ Greedy approach
Optimal polygon triangulation→ Dynamic programming
Subset sum problem → Backtracking
Note: We can also use subset sum problem as well backtracking.
Question 37 
Abstraction and encapsulation are fundamental principles that underlie the object oriented approach to software development. What can you say about the following two statements ?
I. Abstraction allows us to focus on what something does without considering the complexities of how it works.
II. Encapsulation allows us to consider complex ideas while ignoring irrelevant detail that would confuse us.
Neither I nor II is correct.  
Both I and II are correct.  
Only II is correct.  
Only I is correct. 
Question 37 Explanation:
StatementI: FALSE
→ Abstraction is a process of hiding the implementation details and showing only functionality to the user.
→ The data type created by the data abstraction process is called abstract data type(ADT).
→ ADT is a class of objects whose logical behavior is defined by a set of values and a set of operations.
StatementII: FALSE
→ Encapsulation is a mechanism to associate the code and data.
→ Encapsulation is wrapping up of data into single unit.
→ Abstraction is a process of hiding the implementation details and showing only functionality to the user.
→ The data type created by the data abstraction process is called abstract data type(ADT).
→ ADT is a class of objects whose logical behavior is defined by a set of values and a set of operations.
StatementII: FALSE
→ Encapsulation is a mechanism to associate the code and data.
→ Encapsulation is wrapping up of data into single unit.
Question 38 
Given the array of integers ‘array’ shown below :
What is the output of the following JAVA statements ?
int [ ] p = new int [10];
int [ ] q = new int [10];
for (int k = 0; k < 10; k ++)
p[k] = array [k];
q = p;
p[4] = 20;
System.out.println (array [4] + “ : ” + q[4]);
What is the output of the following JAVA statements ?
int [ ] p = new int [10];
int [ ] q = new int [10];
for (int k = 0; k < 10; k ++)
p[k] = array [k];
q = p;
p[4] = 20;
System.out.println (array [4] + “ : ” + q[4]);
20 : 20  
18 : 18  
18 : 20  
20 : 18 
Question 38 Explanation:
Question 39 
Consider the following JAVA program :
public class First {
public static int CBSE (int x) {
if (x < 100) x = CBSE (x + 10);
return (x – 1);
}
public static void main (String[] args){
System.out.print(First.CBSE(60));
}
}
What does this program print ?
public class First {
public static int CBSE (int x) {
if (x < 100) x = CBSE (x + 10);
return (x – 1);
}
public static void main (String[] args){
System.out.print(First.CBSE(60));
}
}
What does this program print ?
59  
95  
69  
99 
Question 39 Explanation:
Main program will call the function CBSE(60)
According to the function definition,
Function call CBSE(100) will give the value of 99,
100<100 condition is false and it will return x1 which is 99
x=CBSE(90)
90<100 is true> x=CBSE(100) and it will return x1
CBSE(100) will return 99 to Function CBSE(90) and this function will return to 98(991).
Repeat this procedure,
CBSE(60) will return 95
According to the function definition,
Function call CBSE(100) will give the value of 99,
100<100 condition is false and it will return x1 which is 99
x=CBSE(90)
90<100 is true> x=CBSE(100) and it will return x1
CBSE(100) will return 99 to Function CBSE(90) and this function will return to 98(991).
Repeat this procedure,
CBSE(60) will return 95
Question 40 
Which of the following statement(s) with regard to an abstract class in JAVA is/are TRUE ?
I. An abstract class is one that is not used to create objects.
II. An abstract class is designed only to act as a base class to be inherited by other classes.
I. An abstract class is one that is not used to create objects.
II. An abstract class is designed only to act as a base class to be inherited by other classes.
Only I  
Only II  
Neither I nor II  
Both I and II 
Question 40 Explanation:
StatementI and II are TRUE
A class which is declared as abstract is known as an abstract class. It can have abstract and nonabstract methods. It needs to be extended and its method implemented. It cannot be instantiated.
Rules:
1. An abstract class must be declared with an abstract keyword.
2. It can have abstract and nonabstract methods.
3. It cannot be instantiated.
4. It can have constructors and static methods also.
5. It can have final methods which will force the subclass not to change the body of the method.
A class which is declared as abstract is known as an abstract class. It can have abstract and nonabstract methods. It needs to be extended and its method implemented. It cannot be instantiated.
Rules:
1. An abstract class must be declared with an abstract keyword.
2. It can have abstract and nonabstract methods.
3. It cannot be instantiated.
4. It can have constructors and static methods also.
5. It can have final methods which will force the subclass not to change the body of the method.
Question 41 
Which of the following HTML code will affect the vertical alignment of the table content?
Question 41 Explanation:
Question 42 
What can you say about the following statements ?
I. XML tags are caseinsensitive.
II. In JavaScript, identifier names are casesensitive.
III.Cascading Style Sheets (CSS) cannot be used with XML.
IV. All wellformed XML documents must contain a document type definition.
I. XML tags are caseinsensitive.
II. In JavaScript, identifier names are casesensitive.
III.Cascading Style Sheets (CSS) cannot be used with XML.
IV. All wellformed XML documents must contain a document type definition.
only I and II are false.  
only III and IV are false.  
only I and III are false.  
All are incorrect. 
Question 42 Explanation:
FALSE: XML tags are casesensitive.
FALSE: In JavaScript, identifier names are not casesensitive.
FALSE: Cascading Style Sheets (CSS) can be used with XML.
FALSE: Somel wellformed XML documents must contain a document type definition.
FALSE: In JavaScript, identifier names are not casesensitive.
FALSE: Cascading Style Sheets (CSS) can be used with XML.
FALSE: Somel wellformed XML documents must contain a document type definition.
Question 43 
Which of the following statement(s) is/are TRUE with regard to software testing ?
I. Regression testing technique ensures that the software product runs correctly after the changes during maintenance.
II. Equivalence partitioning is a whitebox testing technique that divides the input domain of a program into classes of data from which test cases can be derived.
I. Regression testing technique ensures that the software product runs correctly after the changes during maintenance.
II. Equivalence partitioning is a whitebox testing technique that divides the input domain of a program into classes of data from which test cases can be derived.
only I  
only II  
both I and II  
neither I nor II 
Question 43 Explanation:
Statement1:
→ Regression testing is rerunning functional and nonfunctional tests to ensure that previously developed and tested software still performs after a change. If not, that would be called a regression.
→ Changes that may require regression testing include bug fixes, software enhancements, configuration changes, and even substitution of electronic components.
→ As regression test suites tend to grow with each found defect, test automation is frequently involved.
Statement2: Black box testing methods are
1. GraphBased Testing Methods
2. Equivalence Partitioning: It is a black box testing technique that divides the input domain of a program into classes of data from which test cases can be derived.
3. Boundary Value Analysis
4. Orthogonal Array Testing
→ Regression testing is rerunning functional and nonfunctional tests to ensure that previously developed and tested software still performs after a change. If not, that would be called a regression.
→ Changes that may require regression testing include bug fixes, software enhancements, configuration changes, and even substitution of electronic components.
→ As regression test suites tend to grow with each found defect, test automation is frequently involved.
Statement2: Black box testing methods are
1. GraphBased Testing Methods
2. Equivalence Partitioning: It is a black box testing technique that divides the input domain of a program into classes of data from which test cases can be derived.
3. Boundary Value Analysis
4. Orthogonal Array Testing
Question 44 
Which of the following are facts about a topdown software testing approach?
I. Topdown testing typically requires the tester to build method stubs.
II. Topdown testing typically requires the tester to build test drivers.
I. Topdown testing typically requires the tester to build method stubs.
II. Topdown testing typically requires the tester to build test drivers.
Only I  
Only II  
Both I and II  
Neither I nor II 
Question 44 Explanation:
Statement1: TRUE: Topdown testing typically requires the tester to build method stubs.
Stub is a dummy subprogram. Stub uses the subordinate module’s interface, may do minimal data manipulation, provides verification of entry, and returns control to the module undergoing testing.
Statement2: FALSE: Bottom up testing typically requires the tester to build test drivers.
Driver is nothing more than a “main program “ that accepts test case data, passes such data to the component(to be tested) and prints relevant results.
Driver is serve to replace modules that are subordinate to (called by) the component to be tested.
Stub is a dummy subprogram. Stub uses the subordinate module’s interface, may do minimal data manipulation, provides verification of entry, and returns control to the module undergoing testing.
Statement2: FALSE: Bottom up testing typically requires the tester to build test drivers.
Driver is nothing more than a “main program “ that accepts test case data, passes such data to the component(to be tested) and prints relevant results.
Driver is serve to replace modules that are subordinate to (called by) the component to be tested.
Question 45 
Match the terms related to Software Configuration Management (SCM) in List – I with the descriptions in List – II.
IB, IIC, IIIA  
IC, IIA, IIIB  
IC, IIB, IIIA  
IB, IIA, IIIC 
Question 45 Explanation:
Version→ An instance of a system that differs, in some way, from other instances.
Release→ An instance of a system that is distributed to customers.
Variant→ An instance of a system which is functionally identical to other instances, but designed for different hardware/software configurations.
Release→ An instance of a system that is distributed to customers.
Variant→ An instance of a system which is functionally identical to other instances, but designed for different hardware/software configurations.
Question 46 
A software project was estimated at 352 Function Points (FP). A four person team will be assigned to this project consisting of an architect, two programmers, and a tester. The salary of the architect is 80,000 per month, the programmer ₹ 60,000 per month and the tester ₹ 50,000 per month. The average productivity for the team is 8 FP per person month. Which of the following represents the projected cost of the project ?
₹ 28,16,000  
₹ 20,90,000  
₹ 26,95,000  
₹ 27,50,000 
Question 46 Explanation:
Given data,
 Functional Point(FP)=352
 Team=4 persons
 Average each person(FP) productivity=8
 Architect month salary=80,000
 Programmers month salary=2*60,000
 Tester month salary=50,000
 projected cost of project=?
Step1: Total number of months=Functional Point(FP) / (Team* Average each person(FP) productivity)
= 352 / (4*8)
= 352 / 32
= 11 months
Step2: Total cost of the project= (one Architect month salary + 2*Programmers month salary + one tester month salary) * Total number of months
= (80000 + 2 * 60000 + 50000) * 11
= ₹ 27,50,000
 Functional Point(FP)=352
 Team=4 persons
 Average each person(FP) productivity=8
 Architect month salary=80,000
 Programmers month salary=2*60,000
 Tester month salary=50,000
 projected cost of project=?
Step1: Total number of months=Functional Point(FP) / (Team* Average each person(FP) productivity)
= 352 / (4*8)
= 352 / 32
= 11 months
Step2: Total cost of the project= (one Architect month salary + 2*Programmers month salary + one tester month salary) * Total number of months
= (80000 + 2 * 60000 + 50000) * 11
= ₹ 27,50,000
Question 47 
Complete each of the following sentences in List – I on the left hand side by filling in the word or phrase from the List – II on the right hand side that best completes the sentence :
IB, IID, IIIA, IVC  
IB, IID, IIIC, IVA  
ID, IIB, IIIC, IVA  
ID, IIB, IIIA, IVC 
Question 47 Explanation:
→ Verification: Are we building the product right?
→ Validation: Are we building the right product?
→ Software debugging is the process of discovering the cause of a defect and fixing it.
→ is the process of demonstrating the existence.
→ Validation: Are we building the right product?
→ Software debugging is the process of discovering the cause of a defect and fixing it.
→ is the process of demonstrating the existence.
Question 48 
A software company needs to develop a project that is estimated as 1000 function points and is planning to use JAVA as the programming language whose approximate lines of code per function point is accepted as 50. Considering a = 1.4 as multiplicative factor, b = 1.0 as exponential factor for the basic COCOMO effort equation and c = 3.0 as multiplicative factor, d = 0.33 as exponential factor for the basic COCOMO duration equation, approximately how long does the project take to complete ?
11.2 months  
12.2 months  
13.2 months  
10.2 months 
Question 48 Explanation:
Given data,
 lines of code(LOC)= 50,000 (or 50K)
 Multiplicative value ‘a’=1.4
 Exponential ‘b’=1.0
 Basic COCOMO formula= a*(LOC in K)^{b}
 Multiplicative value ‘c’=3.0
 Exponential ‘d’=0.33
 Development=c*(basic COCOMO result)^{d}
Step1: Basic COCOMO formula= a*(LOC in K)^{b}
= 1.4*(50)^{1.0}
= 70 Step2: Development= c*(basic COCOMO result)^{d}
= 3(70)^{0.33}
= 12.18 months
 lines of code(LOC)= 50,000 (or 50K)
 Multiplicative value ‘a’=1.4
 Exponential ‘b’=1.0
 Basic COCOMO formula= a*(LOC in K)^{b}
 Multiplicative value ‘c’=3.0
 Exponential ‘d’=0.33
 Development=c*(basic COCOMO result)^{d}
Step1: Basic COCOMO formula= a*(LOC in K)^{b}
= 1.4*(50)^{1.0}
= 70 Step2: Development= c*(basic COCOMO result)^{d}
= 3(70)^{0.33}
= 12.18 months
Question 49 
A memory management system has 64 pages with 512 bytes page size. Physical memory consists of 32 page frames. Number of bits required in logical and physical address are respectively:
14 and 15  
14 and 29  
15 and 14  
16 and 32 
Question 49 Explanation:
Given data,
 Total number of pages=64
 Page size=512
 Page frames=32
 Logical address=?
 physical address=?
Step1: Logical address=Total number of pages*Page size
= 2^{6}*2^{9}
= 2^{15}
Step2: Physical address= Page size*Page frames
= 2^{9}*2^{5}
= 2^{14}
 Total number of pages=64
 Page size=512
 Page frames=32
 Logical address=?
 physical address=?
Step1: Logical address=Total number of pages*Page size
= 2^{6}*2^{9}
= 2^{15}
Step2: Physical address= Page size*Page frames
= 2^{9}*2^{5}
= 2^{14}
Question 50 
Consider a disk queue with I/O requests on the following cylinders in their arriving order:
6, 10, 12, 54, 97, 73, 128, 15, 44, 110, 34, 45
The disk head is assumed to be at cylinder 23 and moving in the direction of decreasing number of cylinders. Total number of cylinders in the disk is 150. The disk head movement using SCANscheduling algorithm is:
6, 10, 12, 54, 97, 73, 128, 15, 44, 110, 34, 45
The disk head is assumed to be at cylinder 23 and moving in the direction of decreasing number of cylinders. Total number of cylinders in the disk is 150. The disk head movement using SCANscheduling algorithm is:
172  
173  
227  
228 
Question 50 Explanation:
Question 51 
Match the following for Unix file system:
aiii, bi, cii, div  
aiii, bi, iv, dii  
aiv, biii, cii, di  
aiv, biii, ci, dii

Question 51 Explanation:
Book block→ Contains boot program and partition table.
Super block→ Information about file system, free block list, free inode list etc.
Inode block→ Contains a table for every file in the file system. Attributes of files are stored here.
Data block→ Contains operating system files as well as program and data files created by users.
Super block→ Information about file system, free block list, free inode list etc.
Inode block→ Contains a table for every file in the file system. Attributes of files are stored here.
Data block→ Contains operating system files as well as program and data files created by users.
Question 52 
Some of the criteria for calculation of priority of a process are:
a. Processor utilization by an individual process.
b. Weight assigned to a user or group of users.
c. Processor utilization by a user or group of processes In fair share scheduler, priority is calculated based on:
a. Processor utilization by an individual process.
b. Weight assigned to a user or group of users.
c. Processor utilization by a user or group of processes In fair share scheduler, priority is calculated based on:
only (a) and (b)  
only (a) and (c)  
(a), (b) and (c)  
only (b) and (C) 
Question 52 Explanation:
Fairshare scheduling is a scheduling algorithm for computer operating systems in which the CPU usage is equally distributed among system users or groups, as opposed to equal distribution among processes.
Question 53 
One of the disadvantages of user level threads compared to Kernel level threads is
If a user level thread of a process executes a system call, all threads in that process are blocked.  
Scheduling is application dependent.  
Thread switching doesn’t require kernel mode privileges.  
The library procedures invoked for thread management in user level threads are local procedures. 
Question 53 Explanation:
TRUE: If a user level thread of a process executes a system call, all threads in that process are blocked.
FALSE: Scheduling is application dependent.
FALSE: Thread switching doesn’t require kernel mode privileges.
FALSE: The library procedures invoked for thread management in user level threads are local procedures.
Advantage:
1. userlevel threads package can be implemented on an Operating System that does not support threads.
2. Userlevel threads does not require modification to operating systems.
3. Simple Representation: Each thread is represented simply by a PC, registers, stack and a small control block, all stored in the user process address space.
4. Simple Management: This simply means that creating a thread, switching between threads and synchronization between threads can all be done without intervention of the kernel.
5. Fast and Efficient: Thread switching is not much more expensive than a procedure call.
Disadvantages:
1. UserLevel threads are not a perfect solution as with everything else, they are a trade off.
2. There is a lack of coordination between threads and operating system kernel.
3. Userlevel threads requires nonblocking systems call i.e., a multithreaded kernel.
FALSE: Scheduling is application dependent.
FALSE: Thread switching doesn’t require kernel mode privileges.
FALSE: The library procedures invoked for thread management in user level threads are local procedures.
Advantage:
1. userlevel threads package can be implemented on an Operating System that does not support threads.
2. Userlevel threads does not require modification to operating systems.
3. Simple Representation: Each thread is represented simply by a PC, registers, stack and a small control block, all stored in the user process address space.
4. Simple Management: This simply means that creating a thread, switching between threads and synchronization between threads can all be done without intervention of the kernel.
5. Fast and Efficient: Thread switching is not much more expensive than a procedure call.
Disadvantages:
1. UserLevel threads are not a perfect solution as with everything else, they are a trade off.
2. There is a lack of coordination between threads and operating system kernel.
3. Userlevel threads requires nonblocking systems call i.e., a multithreaded kernel.
Question 54 
Which statement is not correct about “init” process in Unix?
It is generally the parent of the login shell.  
It has PID 1.  
It is the first process in the system.  
Init forks and execs a ‘getty’ process at every port connected to a terminal. 
Question 54 Explanation:
TRUE: It is generally the parent of the login shell.
TRUE: It has PID 1.
FALSE: It is the second process in the system.
TRUE: Init forks and execs a ‘getty’ process at every port connected to a terminal.
TRUE: It has PID 1.
FALSE: It is the second process in the system.
TRUE: Init forks and execs a ‘getty’ process at every port connected to a terminal.
Question 55 
Consider following two rules R1 and R2 in logical reasoning in Artificial Intelligence (AI) :
R1 : From α ⊃ β
and α

Inter β (is known as Modus Tollens (MT) )

R2 : From α ⊃ β
and ¬β

Inter ¬α ( is known as Modus Ponens (MP))

Only R1 is correct.  
Only R2 is correct.  
Both R1 and R2 are correct.  
Neither R1 nor R2 is correct. 
Question 56 
Consider the following AO graph:
Which is the best node to expand next by AO* algorithm?
Which is the best node to expand next by AO* algorithm?
A  
B  
C  
B and C 
Question 56 Explanation:
f(n)=c(n)+h(n)
where
f(n)= Best path to reach the destination node
c(n)=Cost of path
h(n)= heuristic value of a node
Cost of choosing B or C is
=(22+3)+(24+2)
=51
Note: We add cost of B and C because they belongs to AND graph.
Cost of choosing A =42+4=46
Since cost of choosing node choosing B or C that’s why we will expand ‘A’.
Question 57 
In Artificial Intelligence (AI), what is present in the planning graph?
Sequence of levels  
Literals  
Variables  
Heuristic estimates 
Question 57 Explanation:
In Artificial Intelligence (AI), Sequence of levels is present in the planning graph.
→ A planning graph consists of a sequence of levels that correspond to time steps in the LEVELS plan, where level 0 is the initial state.
→ Each level contains a set of literals and a set of actions.
→ The literals are all those that could be true at that time step, depending on the actions executed at preceding time steps.
→ The actions are all those actions that could have their preconditions satisﬁed at that time step, depending on which of the literals actually hold.
→ The planning graph records only a restricted subset of the possible negative interactions among actions i.e.., it might be optimistic about the minimum number of time steps required for a literal to become true.
→ This number of steps in the planning graph provides a good estimate of how difﬁcult it is to achieve a given literal from the initial state.
→ The planning graph is deﬁned in such a way that it can be constructed very efﬁciently.
→ Planning graphs work only for propositional planning problemsones with no variables.
→ A planning graph consists of a sequence of levels that correspond to time steps in the LEVELS plan, where level 0 is the initial state.
→ Each level contains a set of literals and a set of actions.
→ The literals are all those that could be true at that time step, depending on the actions executed at preceding time steps.
→ The actions are all those actions that could have their preconditions satisﬁed at that time step, depending on which of the literals actually hold.
→ The planning graph records only a restricted subset of the possible negative interactions among actions i.e.., it might be optimistic about the minimum number of time steps required for a literal to become true.
→ This number of steps in the planning graph provides a good estimate of how difﬁcult it is to achieve a given literal from the initial state.
→ The planning graph is deﬁned in such a way that it can be constructed very efﬁciently.
→ Planning graphs work only for propositional planning problemsones with no variables.
Question 58 
What is the best method to go for the game playing problem?
Optimal Search  
Random Search
 
Heuristic Search  
Stratified Search 
Question 58 Explanation:
→ Heuristic search is the best method to go for the game playing problem
→ A heuristic is a method that might not always find the best solution but is guaranteed to find a good solution in reasonable time.
Example: Hill Climbing, Simulated Annealing, Best first search,A* algorithm,etc..,
→ A heuristic is a method that might not always find the best solution but is guaranteed to find a good solution in reasonable time.
Example: Hill Climbing, Simulated Annealing, Best first search,A* algorithm,etc..,
Question 59 
Which of the following statements is true?
The sentence S is a logical consequence of S_{1},.., S_{n} if and only if S_{1} ∧ S_{2} ∧.... ∧ S_{n} → S is satisfiable.  
The sentence S is a logical consequence of S_{1},..., S_{n} if and only if S_{1} ∧ S_{2} ∧........ ∧S_{n} → S is valid.  
The sentence S is a logical consequence of S_{1},..., S_{n} if and only if S_{1} ∧ S_{2} ∧........ ∧ S_{n} ∧ S is consistent.  
The sentence S is a logical consequence of S_{1},..., S_{n} if and only if S_{1} ∧ S_{2} ∧........ ∧ S_{n} ∧ S is inconsistent. 
Question 60 
The first order logic (FOL) statement ((R ∨ Q) ∧ (P ∨ ¬Q)) is equivalent to which of the following ?
((R ∨ ¬Q) ∧ (P ∨ ¬Q) ∧ (R ∨ P))
 
((R ∨ Q) ∧ (P ∨ ¬Q) ∧ (R ∨ P))  
((R ∨ Q) ∧ (P ∨ ¬Q) ∧ (R ∨ ¬P))  
((R ∨ Q) ∧ (P ∨ ¬Q) ∧ ( ¬R ∨ P)) 
Question 60 Explanation:
Method1: Boolean simplification
((R ∨ Q) ∧ (P ∨ Q’))
(R∨Q)∧(P∨Q’)∧(R∨P)
(PR ∨ Q’R ∨ PQ) ∧ (R∨P)
PR ∨ RQ’ ∨ PQR ∨ PR ∨ PRQ’ ∨ PQ
(RQ’∨PQ’R)∨(PQR∨PQ)∨PR
RQ’ ∨ PQ ∨ PR
((R ∨ Q) ∧ (P ∨ Q’) ∧ (R ∨ P))
Method2: Using Truth table
((R ∨ Q) ∧ (P ∨ Q’))
(R∨Q)∧(P∨Q’)∧(R∨P)
(PR ∨ Q’R ∨ PQ) ∧ (R∨P)
PR ∨ RQ’ ∨ PQR ∨ PR ∨ PRQ’ ∨ PQ
(RQ’∨PQ’R)∨(PQR∨PQ)∨PR
RQ’ ∨ PQ ∨ PR
((R ∨ Q) ∧ (P ∨ Q’) ∧ (R ∨ P))
Method2: Using Truth table
Question 61 
Given the following two statements :
A. L = {wn_{a}(w) = n_{b}(w)} is deterministic context free language, but not linear.
B. L = {a^{n} b^{n}} ∪ {a^{n} b^{2n}} is linear, but not deterministic context free language.
Which of the following options is correct ?
A. L = {wn_{a}(w) = n_{b}(w)} is deterministic context free language, but not linear.
B. L = {a^{n} b^{n}} ∪ {a^{n} b^{2n}} is linear, but not deterministic context free language.
Which of the following options is correct ?
Both (A) and (B) are false.  
Both (A) and (B) are true.  
(A) is true, (B) is false.  
(A) is false, (B) is true. 
Question 61 Explanation:
Statement1:
A linear grammar is a context free grammar that has at most one nonterminal in the right hand side of each of its productions and language generated by linear grammar is known as a linear language.
ex1: S→ aSb  ab
ex2: S→ aS  Sb  ϵ
The grammar for (a)> S→ϵ,S→SaSbS,S→SbSaS }
which is not linear. It is DCFL
Statement2:
The example grammar is
S→ aSb  aSbb  ϵ
Hence it is linear language and it is not DCFL.
A linear grammar is a context free grammar that has at most one nonterminal in the right hand side of each of its productions and language generated by linear grammar is known as a linear language.
ex1: S→ aSb  ab
ex2: S→ aS  Sb  ϵ
The grammar for (a)> S→ϵ,S→SaSbS,S→SbSaS }
which is not linear. It is DCFL
Statement2:
The example grammar is
S→ aSb  aSbb  ϵ
Hence it is linear language and it is not DCFL.
Question 62 
Which of the following pairs have different expressive power?
Singletapeturing machine and multidimensional turing machine.  
Multitape turing machine and multidimensional turing machine.  
Deterministic pushdown automata and nondeterministic pushdown automata.  
Deterministic finite automata and Nondeterministic finite automata 
Question 62 Explanation:
Option(A): It is incorrect option because using multidimensional turing machine we can speed up the process of accepting the language but it does not mean that Singletapeturing machine can't accept the string that multidimensional turing machine accepts.
Option(B): is also incorrect because both machines are same so they can accept the same string with same speed.
Option(C) : It is correct option because Non deterministic pushdown automata is more powerful than deterministic pushdown automata because by using nondeterministic pushdown automata L= {ww  w belongs to (a,b)*} can be accepted but the same language can't be accepted using deterministic pushdown automata.
Option(D) : it is incorrect option because DFA and NDFA both are equivalent to each other i.e. we can convert DFA into NFA and NFA into DFA. DFA and NFA are equal in powers and can accept the same strings.
Option(B): is also incorrect because both machines are same so they can accept the same string with same speed.
Option(C) : It is correct option because Non deterministic pushdown automata is more powerful than deterministic pushdown automata because by using nondeterministic pushdown automata L= {ww  w belongs to (a,b)*} can be accepted but the same language can't be accepted using deterministic pushdown automata.
Option(D) : it is incorrect option because DFA and NDFA both are equivalent to each other i.e. we can convert DFA into NFA and NFA into DFA. DFA and NFA are equal in powers and can accept the same strings.
Question 63 
Which of the following statements is false?
Every contextsensitive language is recursive.  
The set of all languages that are not recursively enumerable is countable.  
The family of recursively enumerable languages is closed under union.  
The families of recursively enumerable and recursive languages are closed under reversal. 
Question 63 Explanation:
Option(A) : it is correct option because L= {a^{n} b^{n} c^{n}} is a context sensitive language and it can also be accepted by the turing machine. Hence every CSL also recursive language.
Option(B): It is incorrect option.
Option(C): Yes it is true that recursively enumerable languages are closed under union.
Option(D): It is a correct option because recursively enumerable and recursive languages are closed under reversal.
NOTE: The difference between recursive and recursively enumerable language is that if a language is recursive then there will be definitely a turing machine which will halt and will say whether the string is accepted or not. But if a language is recursively enumerable then the turing machine will halt if the string is accepted but it is not necessary that the turing machine will halt to indicate that the string is not accepted. in this case the user might end up in infinite wait by thinking that turing machine will halt string acceptance process is still in progress.
Option(B): It is incorrect option.
Option(C): Yes it is true that recursively enumerable languages are closed under union.
Option(D): It is a correct option because recursively enumerable and recursive languages are closed under reversal.
NOTE: The difference between recursive and recursively enumerable language is that if a language is recursive then there will be definitely a turing machine which will halt and will say whether the string is accepted or not. But if a language is recursively enumerable then the turing machine will halt if the string is accepted but it is not necessary that the turing machine will halt to indicate that the string is not accepted. in this case the user might end up in infinite wait by thinking that turing machine will halt string acceptance process is still in progress.
Question 64 
Let C be a binary linear code with minimum distance 2t + 1 then it can correct upto _____ bits of error.
t + 1  
t  
t  2  
t / 2 
Question 64 Explanation:
A binary linear code with minimum distance 2t + 1 then it can correct up to ‘T’ bits of error.
Question 65 
A terror correcting qnary linear code must satisfy:
Where M is the number of code words and X is
Where M is the number of code words and X is
q^{n}  
q^{t}  
q^{n}  
q^{t} 
Question 66 
Names of some of the Operating Systems are given below:
(a) MSDOS
(b) XENIX
(c) OS/2
In the above list, following operating systems didn’t provide multi user facility.
(a) MSDOS
(b) XENIX
(c) OS/2
In the above list, following operating systems didn’t provide multi user facility.
(a) only  
(a) and (b) only  
(b) and (c) only  
(a), (b) and (c) 
Question 66 Explanation:
MSDOS→ Single user operating system
XENIX→ Multi user operating system. XENIX is a multiuser solution that allows multiple users to be attached via inexpensive terminals to a single machine, thereby allowing the users to share the resources of the machine.
OS/2→ Multi user operating system.
XENIX→ Multi user operating system. XENIX is a multiuser solution that allows multiple users to be attached via inexpensive terminals to a single machine, thereby allowing the users to share the resources of the machine.
OS/2→ Multi user operating system.
Question 67 
From the given data below :
a b b a a b b a a b
which one of the following is not a word in the dictionary created by LZcoding (the initial words are a, b)?
a b b a a b b a a b
which one of the following is not a word in the dictionary created by LZcoding (the initial words are a, b)?
a b  
b b  
b a  
b a a b  
None of the above 
Question 67 Explanation:
Lempel–Ziv–Welch is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch
abbaabbaab
⇒ Dictionary created by L2  coding will contain words:
a  b  ba  ab  baa  b
b  already present in dictionary
So the words are a, b, ba, ab, baa.
⇒ Hence ‘B’ and ‘D’ both are not present in the dictionary.
Note: (B) and (D) is correct answers
abbaabbaab
⇒ Dictionary created by L2  coding will contain words:
a  b  ba  ab  baa  b
b  already present in dictionary
So the words are a, b, ba, ab, baa.
⇒ Hence ‘B’ and ‘D’ both are not present in the dictionary.
Note: (B) and (D) is correct answers
Question 68 
With respect to a loop in the transportation table, which one of the following is not correct?
Every loop has an odd no. of cells and at least 5.  
Closed loops may or may not be square in shape.  
All the cells in the loop that have a plus or minus sign, except the starting cell, must be occupied cells.  
Every loop has an even no. of cells and at least four. 
Question 69 
At which of the following stage(s), the degeneracy do not occur in transportation problem ? (m, n represents number of sources and destinations respectively)
(a) While the values of dual variables ui and vj cannot be computed.
(b) While obtaining an initial solution, we may have less than m + n – 1 allocations.
(c) At any stage while moving towards optimal solution, when two or more occupied cells with the same minimum allocation become unoccupied simultaneously.
(d) At a stage when the no. of +ve allocation is exactly m + n – 1.
(a) While the values of dual variables ui and vj cannot be computed.
(b) While obtaining an initial solution, we may have less than m + n – 1 allocations.
(c) At any stage while moving towards optimal solution, when two or more occupied cells with the same minimum allocation become unoccupied simultaneously.
(d) At a stage when the no. of +ve allocation is exactly m + n – 1.
(a), (b) and (c)  
(a), (c) and (d)  
(a) and (d)  
(a), (b), (c) and (d) 
Question 70 
Consider the following LPP :
Min. Z = X_{1} + X_{2} + X_{3}
Subject to 3X_{1} + 4X_{3} ≤ 5
5X_{1} + X_{2} + 6X_{3} = 7
8X_{1} + 9X_{3} ≥ 2,
X_{1}, X_{2}, X_{3} ≥ 0
The standard form of this LPP shall be :
Min. Z = X_{1} + X_{2} + X_{3}
Subject to 3X_{1} + 4X_{3} ≤ 5
5X_{1} + X_{2} + 6X_{3} = 7
8X_{1} + 9X_{3} ≥ 2,
X_{1}, X_{2}, X_{3} ≥ 0
The standard form of this LPP shall be :
Question 70 Explanation:
Question 71 
Let R and S be two fuzzy relations defined as :
Then, the resulting relation, T, which relates elements of universe x to the elements of universe z using maxmin composition is given by :
Then, the resulting relation, T, which relates elements of universe x to the elements of universe z using maxmin composition is given by :
Question 71 Explanation:
Question 72 
A neuron with 3 inputs has the weight vector [0.2 –0.1 0.1]^{T} and a bias θ = 0. If the input vector is X = [0.2 0.4 0.2]^{T} then the total input to the neuron is :
0.20  
1.0  
0.02  
–1.0 
Question 72 Explanation:
Total input to neuron f(x)=(W^{T}XX)+Ⲑ
=(0.2*0.2)+(0.1*0.4)+(0.1*0.2)
=0.040.04+0.02
=0.02
=(0.2*0.2)+(0.1*0.4)+(0.1*0.2)
=0.040.04+0.02
=0.02
Question 73 
Which of the following neural networks uses supervised learning ?
(A) Multilayer perceptron
(B) Self organizing feature map
(C) Hopfield network
(A) Multilayer perceptron
(B) Self organizing feature map
(C) Hopfield network
(A) only  
(B) only  
(A) and (B) only  
(A) and (C) only 
Question 73 Explanation:
Question 74 
Unix command to change the case of first three lines of file “shortlist” from lower to upper
$ tr ‘[a – z]’ ‘[A – Z]’ shortlist ¦ head3  
$ head 3 shortlist ¦ tr ‘[a – z]’ ‘[A – Z]’  
$ tr head 3 shortlist ‘[A – Z]’ ‘[a – z]’  
$ tr shortlist head 3 ‘[a – z]’ ‘[A – Z]’ 
Question 74 Explanation:
Head: The head command is a commandline utility for outputting the first part of files given to it via standard input. It writes results to standard output. By default head returns the first ten lines of each file that it is given.
tr: Translates lowercase to uppercase (or) uppercase to lowercase.
OptionB will display first three lines of file “shortlist” from lower to upper
tr: Translates lowercase to uppercase (or) uppercase to lowercase.
OptionB will display first three lines of file “shortlist” from lower to upper
Question 75 
Match the following vi commands in Unix:
aii, biii, ci, div  
aiv, biii, cii, di  
aiii, biv, ci, dii  
aiii, bi, civ, dii 
Question 75 Explanation:
: w → saves file and remains in editing mode
: x → saves the file and quits editingmode
: q → quits editing mode and no changes are saved to the file
: sh→ escapes unix shell
: x → saves the file and quits editingmode
: q → quits editing mode and no changes are saved to the file
: sh→ escapes unix shell
There are 75 questions to complete.