## UGC NET CS 2007 June-Paper-2

 Question 1
The following deterministic finite automata recognizes : A Set of all strings containing ‘ab’ B Set of all strings containing ‘aab’ C Set of all strings ending in ‘abab’ D None of the above
Theory-of-Computation       Finite-Automata
Question 1 Explanation:
There is no final state in the given deterministic finite automata so it can't accept any string. Hence the answer is option(D)
 Question 2
Depth ion travels of the following directed graph is : A A B C D E F B A B D E F C C A C E B D F D None of the above
Data-Structures       Graphs-and-Tree
Question 2 Explanation:
To find depth ion traverse using DFS.
Option-A: It is ruled out because we can’t move after C to D. It is violating DFS property.
Option-B: It is following actual DFS structure. Option-C: It is ruled out because after visiting E we can’t visit B again. It is violating DFS properties.
 Question 3
The maximum number of nodes in a binary tree of depth 10 :
 A 1024 B 210 - 1 C 1000 D None of the above
Data-Structures       Binary-Trees
Question 3 Explanation:
→ The depth of binary tree starts from 0 but not 1.
→ To find maximum number of nodes in a binary tree of depth using formula is
= 2h+1 -1
= 211 -1
= 2048-1
= 2047 Question 4
The regular expression given below describes : r=(1+01)* (0+λ)
 A Set of all string not containing ‘11’ B Set of all string not containing ‘00’ C Set of all string containing ‘01’ D Set of all string ending in ‘0’
Theory-of-Computation       Regular-Expression
Question 4 Explanation:
L= { λ, 0, 1λ, 01λ, 10, 010, 110, .............}
According to the language L generated by given regular expression
Option(A) is incorrect because L contains 110.
Option(B) is correct because no string is containing 00
Option(C) is incorrect because not all strings in L are containing 01 example 0 in L does not contain 01.
Option(D) is incorrect because L contains 1λ is there in L which is not ending with 0.
Hence correct answer is option (B)
 Question 5
Which of the following language is regular :
 A L = { an bn| n ≥ 1 } B L = { an bm cn dm|n, m ≥ 1 } C L = { an bm|n, m ≥ 1 } D L = { an bm cn|n, m ≥ 1 }
Theory-of-Computation       Regular-Language
Question 5 Explanation:
Language generated in Option (A) requires a memory element to count an equal number of b's after a. And since regular languages are accepted by finite automata which do not have a memory element. Hence Option (A) language is not Regular.
Language generated in Option (B) requires a memory element and a read-write head which can move in both directions to count equal numbers of a's and c's , and b's and d's. And since regular languages are accepted by finite automata which do not have a memory element and a read-write head which can move in both directions. Hence Option (A) language is not Regular.
Language generated in Option (C) is regular because the number of a's and b's does not necessarily need to be the same which means no memory element is required. Hence it is a regular language.
Language generated in Option (D) requires a memory element to count an equal number of c's after a. And since regular languages are accepted by finite automata which do not have a memory element. Hence Option (A) language is not Regular. The language generated here is context free language which can be accepted by pushdown automata.
 Question 6
2’s complement of -100 is :
 A 00011100 B 10011101 C 10011100 D 11100100
Digital-Logic-Design       Number-Systems
Question 6 Explanation: Question 7
Which of the following expression remove hazard form : xy+zx’ ?
 A xy+zx’ B xy+zx’ C xy+zx’+yz D xy+zx’+wz
Digital-Logic-Design       Circuits-Output
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.
 Question 8
How many 1’s are present in the binary representation of 15*256 + 5*16 + 3 :
 A 8 B 9 C 10 D 11
Digital-Logic-Design       Number-Systems
Question 8 Explanation:
Step-1: The precedence to given decimal number is (15*256) + (5*16) + 3
Step-2: 3840+80+3=(3923)10
Step-3: Convert decimal number into binary
(3923)10 = (‭111101010011‬ )2
Step-4: Total number of 1’s are 8.
 Question 9
If A⊕B=C , then :
 A A ⊕ C = B B B ⊕ C = A C A ⊕ B ⊕ C = 1 D A ⊕ B ⊕ C = 0 E None of the above
Digital-Logic-Design       Boolean-Expression
Question 9 Explanation:
Given that A⊕B=C
1) A⊕B⊕ C = C⊕C
A⊕B⊕ C = 0 (Since C⊕C =0)
option D is correct.
So option C is not correct.
2) From step 1, we know that A⊕B⊕ C = 0
A⊕B⊕ C ⊕ B= 0 ⊕ B
A ⊕ C = B (Since B ⊕ B= 0)
So option A is correct.
3) From step 1, we know that A⊕B⊕ C = 0
A⊕B⊕ C ⊕ A= 0 ⊕ A
B ⊕ C = A (Since A ⊕ A =0)
So option B is also correct.
 Question 10
What is the maximum counting speed of a 4-bit binary counter which is composed of Flip-Flop with a propagation delay of 25ns ?
 A 1MHz B 10MHz C 100MHz D 4MHz
Digital-Logic-Design       Sequential-Circuits
Question 10 Explanation:
Question is about frequency of the counter.
Frequency = 1/ Time
Binary counter is ripple counter where the output one flip flop is clock input to next flip flop.
So, maximum delay(time)= 4*25ns = 100 ns.
frequency= 1/100 ns
= 10 MHz.
 Question 11
The following loop in ‘C’ :
int i=0;
while (i++ < 0)
i-- ;
 A will terminate B will go into an infinite loop C will give compilation error D will never be executed
Programming       Control-Statement
Question 11 Explanation:
#include
void main()
{
int i=0;
while(i++ < 0)
{
i--;
printf("%d",i);
}
}
/* It will terminate null value */
 Question 12
In case of right shift bitwise operator in ‘C’ language, after shifting n bits, the leftmost n bits :
 A are always filled with zeros B are always filled with ones C are filled with zeros or ones and is machine dependent D none of the above
Programming       Operator
Question 12 Explanation:
In case of right shift bitwise operator in ‘C’ language, after shifting n bits, the leftmost n bits are filled with zeros or ones and is machine dependent.
Example:
Input: positive number→ It will filled with zeros
Input: Negative number → it will filled with ones