## UGC NET CS 2006 June-Paper-2

Question 1 |

Which of the following strings is in the language defined by grammar

S → 0A

A → 1A/0A/1

S → 0A

A → 1A/0A/1

01100 | |

00101 | |

10011 | |

11111 |

Question 1 Explanation:

Question 2 |

For a complete graph with N vertices, the total number of spanning trees is given by :

2N-1 | |

N ^{N-1} | |

N ^{N-2} | |

2N+1 |

Question 2 Explanation:

If a graph is complete, total number of spanning trees are N

Example:

Formula to find total number of spanning trees are N

=5

=5

=125

^{N-2}Example:

Formula to find total number of spanning trees are N

^{N-2}=5

^{5-2}=5

^{3}=125

Question 3 |

The preposition( p→q) ∧ (~q ∨ p) is equivalent to :

q →p | |

p→ q | |

(q →p)∨(p→ q) | |

(p →q)∨(q→ p) | |

None of the above |

Question 3 Explanation:

Question 4 |

The logic of pumping lemma is a good example of :

pigeon hole principle | |

recursion | |

divide and conquer technique | |

iteration |

Question 4 Explanation:

→ A pumping lemma (or) pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or
sections, that can be removed, or repeated any number of times, with the resulting string remaining in that language.

→ The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.

→ Hence, the logic of pumping lemma is a good example of the pigeonhole principle.

→ The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.

→ Hence, the logic of pumping lemma is a good example of the pigeonhole principle.

Question 5 |

Let A={ x | -1 < x < 1 }=B. The function f(x)=x/2 from A to B is :

injective | |

surjective | |

both injective and surjective | |

neither injective nor surjective |

Question 5 Explanation:

→ A function f : X → Y is defined to be one-one (or injective), if the images of distinct elements of X under f are distinct, i.e., x1 , x2 ∈ X, f(x1) = f(x2) ⇒ x1=x2.

→ The possible value of “x” is 0 then

f(x1)=x1/2=0/2=0

f(x2)=x2/2=0/2=0

for x1 , x2 ∈ X, f(x1) = f(x2) ⇒ x1 = x2.

→ The possible value of “x” is 0 then

f(x1)=x1/2=0/2=0

f(x2)=x2/2=0/2=0

for x1 , x2 ∈ X, f(x1) = f(x2) ⇒ x1 = x2.

Question 6 |

The number of 1 ’s present in the binary representation of (3*512 + 7*64 +5*8 +3)

_{10} is :8 | |

9 | |

10 | |

11 |

Question 6 Explanation:

(3*512 + 7*64 +5*8 +3) =2027

(2027)

Here, total number of 1’s are 9.

(2027)

_{10} = (111 1110 1011)_{ 2}Here, total number of 1’s are 9.

Question 7 |

Which of the following expression removes static hazard from a two level AND - OR gate implementation of xy +zx’

xy +zx’ | |

xy + zx’+ wxy | |

xy +zx’ +yz | |

xy + zx’ +wz |

Question 7 Explanation:

→ A static hazard occurs if a circuit produces incorrect output value momentarily before stabilizing to its correct value.

→ Generally Hazard occurs due to different delays in different paths of the circuit.

→ In the expression xy +zx’ the variable x is in true form in one term(xy) and in complement in other term(zx').

→ Delay occurs due to the presence of NOT gate. If input xyz=111 then output is 1. If input xyz=011 then output stays momentarily in state 0 then settles in state 1.

→ Adding the term yz(select y from xy and z from zx') eliminates the hazard.

→ Generally Hazard occurs due to different delays in different paths of the circuit.

→ In the expression xy +zx’ the variable x is in true form in one term(xy) and in complement in other term(zx').

→ Delay occurs due to the presence of NOT gate. If input xyz=111 then output is 1. If input xyz=011 then output stays momentarily in state 0 then settles in state 1.

→ Adding the term yz(select y from xy and z from zx') eliminates the hazard.

Question 8 |

Which of the following logic has the maximum fan out ?

RTL | |

ECL | |

NMOS | |

CMOS |

Question 8 Explanation:

Emitter Coupled Logic (ECL)

The storage time is eliminated as the transistors are used in difference amplifier mode and are never driven into saturation.

1. Fastest among all logic families

2. Lowest propagation delay.

Complementary metal oxide semiconductor(CMOS)

The power dissipation is usually 10nW per gate depending upon the power supply voltage, output load etc.

1. Lowest power dissipation

2. Excellent noise immunity

3. High packing density

4. Wide range of supply voltage

5. Highest fan out among all logic families

Negative channel metal oxide semiconductor (NMOS)

It is a type of semiconductor that charges negatively. So that transistors are turned ON/OFF by the movement of electrons. In contrast, Positive channel MOS-PMOS works by moving electron vacancies. NMOS is faster than PMOS.

Resistor Transistor Logic (RTL) Sometimes also transistor–resistor logic (TRL) is a class of digital circuits built using resistors as the input network and bipolar junction transistors (BJTs) as switching devices. RTL is the earliest class of transistorized digital logic circuit used; other classes include diode–transistor logic (DTL) and transistor-transistor logic (TTL).

The storage time is eliminated as the transistors are used in difference amplifier mode and are never driven into saturation.

1. Fastest among all logic families

2. Lowest propagation delay.

Complementary metal oxide semiconductor(CMOS)

The power dissipation is usually 10nW per gate depending upon the power supply voltage, output load etc.

1. Lowest power dissipation

2. Excellent noise immunity

3. High packing density

4. Wide range of supply voltage

5. Highest fan out among all logic families

Negative channel metal oxide semiconductor (NMOS)

It is a type of semiconductor that charges negatively. So that transistors are turned ON/OFF by the movement of electrons. In contrast, Positive channel MOS-PMOS works by moving electron vacancies. NMOS is faster than PMOS.

Resistor Transistor Logic (RTL) Sometimes also transistor–resistor logic (TRL) is a class of digital circuits built using resistors as the input network and bipolar junction transistors (BJTs) as switching devices. RTL is the earliest class of transistorized digital logic circuit used; other classes include diode–transistor logic (DTL) and transistor-transistor logic (TTL).

Question 9 |

In a weighted code with weight 6, 4, 2, -3 the decimal 5 is represented by :

0101 | |

0111 | |

1011 | |

1000 |

Question 9 Explanation:

The decimal value 5 is represented by 1011.

= 6*1 + 4*0 + 2*1 + -3*1

= 6+2-3

=5

= 6*1 + 4*0 + 2*1 + -3*1

= 6+2-3

=5

Question 10 |

Upto how many variables, can the Karnaugh map be used ?

3 | |

4 | |

5 | |

6 |

Question 10 Explanation:

The Karnaugh map provides a simple and straightforward method of minimising boolean expressions. With the Karnaugh map Boolean expressions having up to four and even six variables can be simplified.

Question 11 |

What is the output of the following program segment ?

main ( )

{

int count, digit=0;

count=1;

while(digit <=9)

{

printf("%d /n”" , ++count);

++digit;

}

}

main ( )

{

int count, digit=0;

count=1;

while(digit <=9)

{

printf("%d /n”" , ++count);

++digit;

}

}

10 | |

9 | |

12 | |

11 |

Question 11 Explanation:

The digit starts with 0 and will run 9 more times. It means, the loop will run 10 runs. The count variable we are given pre increment. So, it increments before assigning values.

It prints the result is

2 /n 3 /n 4 /n 5 /n 6 /n 7 /n 8 /n 9 /n 10 /n 11

It prints the result is

2 /n 3 /n 4 /n 5 /n 6 /n 7 /n 8 /n 9 /n 10 /n 11

Question 12 |

A static variable is one :

Which cannot be initialized | |

Which is initialized once at the commencement of execution and cannot be changed at runtime | |

Which retains its value throughout the life of the program | |

Which is the same as an automatic variable but is placed at the head of a program |

Question 12 Explanation:

A static variable is one which retains its value throughout the life of the program. The static storage class instructs the compiler to keep a local variable in existence during the life-time of the program instead of creating and destroying it each time it comes into and goes out of scope.