13-07-2012

Daily 10 questions(13-07-2012)




1. Which one of the following is a top-down parser?
(A) Recursive descent parser. (B) Operator precedence parser.
(C) An LR(k) parser. (D) An LALR(k) parser.



2. Which of the following graphs has an Eulerian circuit?
(A) Any k-regular graph where k is an even number.
(B) A complete graph on 90 vertices.
(C) The complement of a cycle on 25 vertices.
(D) None of the above


3. A minimum state deterministic finite automaton accepting the language
{ { }* }
L = w w Î 0,1 , number of 0s and 1s in w are divisible by 3 and 5, respectively
has
(A) 15 states (B) 11 states (C) 10 states (D) 9 states


4. The language {0 21 0} i i L = i ³ over the alphabet {0,1,2} is:
(A) not recursive
(B) is recursive and is a deterministic CFL.
(C) is a regular language.
(D) is not a deterministic CFL but a CFL.

7. The following postfix expression with single digit operands is evaluated using a
stack:
8 2 3 Ù / 2 3 * + 5 1 * -
Note that Ù is the exponentiation operator. The top two elements of the stack
after the first * is evaluated are:
(A) 6, 1 (B) 5, 7 (C) 3, 2 (D) 1, 5


8. Which one of the following statements if FALSE?
(A) Any relation with two attributes is in BCNF
(B) A relation in which every key has only one attribute is in 2NF
(C) A prime attribute can be transitively dependent on a key in a 3 NF relation.
(D) A prime attribute can be transitively dependent on a key in a BCNF relation.


9. Match the following:
(P) SMTP             (1) Application layer
(Q) BGP               (2) Transport layer
(R) TCP                (3) Data link layer
(S) PPP                 (4) Network layer
                              (5) Physical layer
(A) P - 2 Q - 1 R - 3 S - 5
(B) P - 1 Q - 4 R - 2 S - 3
(C) P - 1 Q - 4 R - 2 S - 5
(D) P - 2 Q - 4 R - 1 S - 3




10.

12-07-2012

Daily 10 Questions(12-07-2012)






1. Let S be a set of n elements. The number of ordered pairs in the largest and the
smallest equivalence relations on S are:

2. What is the maximum number of different Boolean functions involving n Boolean
variables?

3. Let G be the non-planar graph with the minimum possible number of edges. Then
G has
(A) 9 edges and 5 vertices (B) 9 edges and 6 vertices
(C) 10 edges and 5 vertices (D) 10 edges and 6 vertices




4. Consider the DAG with V = {1,2,3,4,5,6}, shown below.
Which of the following is NOT a topological ordering?

(A) 1 2 3 4 5 6 (B) 1 3 2 4 5 6 (C) 1 3 2 4 6 5 (D) 3 2 4 1 6 5


5. Which of the following problems is undecidable?
(A) Membership problem for CFGs. (B) Ambiguity problem for CFGs.
(C) Finiteness problem for FSAs. (D) Equivalence problem for FSAs.






6. Which of the following is TRUE?
(A) Every subset of a regular set is regular.
(B) Every finite subset of a non-regular set is regular.
(C) The union of two non-regular sets is not regular.
(D) Infinite union of finite sets is regular.




7. Consider the following Boolean function of four variables:
f (w,x,y ,z ) =
(1,3,4,6,9,11,12,14)
The function is:
(A) independent of one variables. (B) independent of two variables.
(C) independent of three variables. (D) dependent on all the variables.




8. The height of a binary tree is the maximum number of edges in any root to leaf
path. The maximum number of nodes in a binary tree of height h is:

9. The maximum number of binary trees that can be formed with three unlabeled
nodes is:
(A) 1 (B) 5 (C) 4 (D) 3


10. Which of the following sorting algorithms has the lowest worst-case complexity?
(A) Merge sort (B) Bubble sort (C) Quick sort (D) Selection sort

11-07-2012

1. Consider a relation scheme R = (A,B,C,D,E,H) on which the following functional dependencies hold: 
{A - B, BC - D, E C, D - A}. What are the candidate keys of R?
(a) AE, BE
(b) AE, BE, DE
(c) AEH, BEH, BCH
(d) AEH, BEH, DEH


2. The set {1,2,3,5,7,8,91 under multiplication modulo 10 is not a group. Given
below are four plausible reasons. Which one of them is false?
(A) It is not closed
(B) 2 does not have an inverse
(C) 3 does not have an inverse
(D) 8 does not have an inverse


3. In a binary max heap containing n numbers, the smallest element can be found in time
(A) 0(n)
(B) O(logn)
(C) 0(loglogn)
(D) 0(1)


4.

5.

6. Which of the following logic families is the fastest?


(a) TTL   (b) DTL  (c) ECL  (d) MOS

7. 

8. 

9. DELETE statement in SQL is used to:


(A) Remove a database
(B) Remove a table from a database
(C) Remove a record from table
(D) Remove a field from a table


10. A B-tree of minimum degree t can have maximum ---- pointers in a node


(A) t-1
(B) 2t-1
(C) 2t
(D) t




Will publish answers soon

10-07-2012

Daily 10 questions(10-07-2012)

1. An Abstract Data Type (ADT) is:

(a) same as an abstract class

(b) a data type that cannot be instantiated

(c) a data type type for which only the operations defined on it can be used, but none else

(d) all ofthe above

2. A common property of logic programming languages and functional languages is:

(a) both are procedural languages

(b) both are based on 2k-calculus

(c) both are declarative

(d) both use Horn-clauses

3. An undirected graph G has n nodes. Its adjacency matrix is given by an n x n square

matr4ix whose (i) diagonal elements are 0’s and (ii) non-diagonal elements are l’s. which one

of the following is TRUE?

(a) Graph G has no minimum spanning tree (MST)

(b) Graph G has a unique MST of cost n-i

(c) Graph G has multiple distinct MSTs, each of cost n-i

(d) Graph G has multiple spanning trees of different costs

4. Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex

cover of G is 8. then, the size of the maximum independent set of G is:

(a) 12

(b) 8

(c) Less than 8

(d) More than 12

5. The hexadecimal representation of 6578 is:

(a) 1AF

(b) D78

(c) D71

(d) 32F

6. The switching expression corresponding to f(A,B,C,D)= (1,4,5,9,11,12) is:

(a) BC’D’ + A’C’D + AB’D

(c) ACD’ + A’BC’ + AC’D’

(b) ABC’+ACD+B’C’D

(d) A’BD + ACD’ + BCD’

7. The address resolution protocol (ARP) is used for:

(a) Finding the IP address from the DNS

(b) Finding the IP address of the default gateway

(c) Finding the IP address that corresponds to a MAC address

(d) Finding the MAC address that corresponds to an IP address

8. Consider the regular language L =(111+11111)*. The minimum number of

states in any DFA accepting this languages is:

(A) 3

(B) 5

(C) 8

(D) 9

9. L={aa,ab,ba,bb} minimum number of states required to implement using DFA are

(A) 2

(B) 3

(C) 4

(D) 5

10. Which one of the following graphs is NOT planar?

Key
1.
2.C
3.
4.
5.
6.A
7.
8.D
9.C
10. Looks like something wrong with the question

05-07-2012

Daily 10 questions(05-07-2012)


(1)What is the complement of the language accepted by the NFA shown below

Answer: (B)


Given NFA does not accept epsilon, so complement should accept epsilon. We left out with two options (B) and (D). But NFA accepts 'a' so complement should not accept 'a'. that means (B) is the answer.



(2) The Truth table

X	Y	f(X,Y)
0	0	0
0	1	0
1	0	1
1	1	1

Represents the boolean function

(A) X        (B)  X+Y   (C)   X EX-OR Y   (D) Y

Answer(A)


f(x,y) and X are same

(3) What will be the output of the following C program segment?

char inChar='A';

switch( inChar ) {

case 'A' : printf ( "Choice A\n");

case 'B' :

case 'C' : printf (" Choice B");

case 'D' : 

case 'E' : 

default : printf (" No choice ");

}

(A) No choice

(B) Choice A

(C) Choice A

       Choice B  No Choice

(D) Program gives no output as it errorneous

Answer(C)


No break statement after case statements so it is nothing but sequential statement execution.

(4) Which of the following is TRUE

(A) Every relation in 3NF is also in BCNF

(B) A relation R is in 3NF  if every non-prime attribute of R is fully functionally dependent on every key of R

(C) Every Relation in BCNF is also in 3NF

(D) No Relation can be in both BCNF and 3NF

Answer: (C)

(5) Given the language L= {ab, aa, baa} which of the following strings are in L*?

1) abaabaaabaa     2) aaaabaaaa 

3) baaaaabaaaab   4) baaaaabaa

(A) 1,2 and 3  (B) 2,3 and 4

(C) 1,2 and 4  (D) 1,3 and 4

Answer(C)

(6)  What is the minimal form of the Karnaugh map shown below? Assume that X denotes a don't care term

Answer: (B)

(7) Which of the following graphs is isomorphic to 

Answer(B)


Compare degree sequences with the given graph

(8) Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros for example, 001110 and 011001 are in the language, but 100010 is not. All strings of less than three are also in the language. A partially  completed DFA that accepts this language is shown below.

Answer(D)

(9) How many onto(or surjective) functions are there from an n-element (n>=2) set to a 2-element set?

Answer(C)

(10) K4 and Q3 are graphs with the following structures

Which one of the following statements is TRUE in relation to these graphs?

(A) K4 is planar while Q3 is not (B) Both K4 and Q3 are planar

(C) Q3 is planar while K4 is not (D) Neither K4 not Q3 is planar

Answer(B)


*******************************************
Key will be published on 06-07-2012 ( Friday ) at 8:00 PM (IST)
*******************************************

Answer Key



1. B 
2. A
3. C
4. C
5. C
6. B
7. B
8. D
9. C
10.B


Let me know if anybody needs explanation.

December 2011 Question paper with answer key

Download Question Paper Here


Will update Answer Key by end of day

1	D	11	A	21	C	31	D	41	B
2	D	12	C	22	C	32	B	42	D
3	B	13	C	23		33	B	43	B
4	D	14	A	24		34	D	44	D
5	D	15	D	25	A	35	C	45	C
6	B	16	C	26	A	36	D	46	D
7	B	17	A	27	D	37	A	47
8	A	18	C	28	B	38	C	48	B
9	B	19	C	29		39	B	49
10	C	20	B	30	D	40	A	50	A

Explanation:

Net Qualifying Criteria

Dear All,


I have seen many people discussing about Qualifying criteria for NET. So thought of writing a post on Qualifying criteria. 


The candidates are required to obtain minimum marks separately in Paper-I, Paper-II and Paper-III as given below:

As per my observation, UGC changes the cutoff marks depends on the number of candidates qualified the mimimum eligibility crieteria

According to me, eligibility criteria for Lecturership for june 2012 may be like this

Category	Expected Qualifying Cut-off Marks for Lectureship Eligibility in UGC-NET held on 24.06.2012
	Paper-I	Paper-II	Paper-I + Paper-II	Paper-III	Paper-I + Paper-II + Paper-III
GEN	40 (40%)	40 (40%)	100 (50%)	75 (50%)	210(60%)
OBC(NCL)	35 (35%)	35 (35%)	90 (45%)	68 (45%)	193(55%)
SC/ST/PH/VH	35 (35%)	35 (35%)	80 (40%)	70 (40%)	175(50%)

Category	Expected Qualifying Cut-off Marks for Junior Research Fellowship in UGC-NET held on 24.06.2012
	Paper-I	Paper-II	Paper-I + Paper-II	Paper-III	Paper-I + Paper-II + Paper-III
GEN	40 (40%)	40 (40%)	100 (50%)	83 (55%)	228(65%)
OBC(NCL)	35 (35%)	35 (35%)	90 (45%)	68 (45%)	210(60%)
SC/ST/PH/VH	35 (35%)	35 (35%)	80 (40%)	70 (40%)	193(55%)

Ugc followed the qualifying criteria for previous years 

I Hope above analysis will give some idea about NET cut-off marks and minimum eligibility criteria for June-2012. Any comments please....