Page 1 Discrete Structures Set1 Q1. Which of the following refers to Idempotent law? a) a b = b a b) a b = b a c) a ( b c ) = ( a b ) c d) a a = a Q2. Which of the following distributive laws should hold true for a distributive lattice? (i) p ( q r ) = ( p q ) ( p r ). (ii) p ( q r ) = ( p q ) r. (iii) p ( q r ) = ( p q ) ( p r ). (iv) p ( q r ) = ( p q ) r a) (i) and (ii) b) (i) and (iii) c) (ii) and (iii) d) (ii) and (iv) Q3. The Dual of any theorem in a lattice is : a) a law b) an order c) a theorem d) None of these Q4. Simplify the Boolean expression : (A + B)'(C + D + E)' + (A + B)' a) A'B' b) C'D'E' c) C+D+E d) A'B'C'D'E' Page 2 Discrete Structures Set1 Q1. Which of the following refers to Idempotent law? a) a b = b a b) a b = b a c) a ( b c ) = ( a b ) c d) a a = a Q2. Which of the following distributive laws should hold true for a distributive lattice? (i) p ( q r ) = ( p q ) ( p r ). (ii) p ( q r ) = ( p q ) r. (iii) p ( q r ) = ( p q ) ( p r ). (iv) p ( q r ) = ( p q ) r a) (i) and (ii) b) (i) and (iii) c) (ii) and (iii) d) (ii) and (iv) Q3. The Dual of any theorem in a lattice is : a) a law b) an order c) a theorem d) None of these Q4. Simplify the Boolean expression : (A + B)'(C + D + E)' + (A + B)' a) A'B' b) C'D'E' c) C+D+E d) A'B'C'D'E' Q5. Which of the following statement(s) is true regarding ISOMORPHIC BOOLEAN ALGEBRA? a) Every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra. b) Boolean algebra may not be a Boolean sub algebra of B. c) Both every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra & Boolean algebra may not be a Boolean sub algebra of B. d) None of these Q6. If a finite lattice L does not contain _____ elements for some positive integer n, then L cannot be a Boolean algebra. a) 2 n b) 2 n + 1 c) 2 n + 1 d) 2 n – 1 Q7. What is the complement of 6 in the lattice D = { 1, 2, 3, 4, 6, 12} ? a) 2 b) 4 c) 12 d) No complement Q8. A lattice L is called ________ if every non empty sub-set of L has a least upper bound and a greatest lower bound. a) Distributive lattice b) Complete lattice c) Modular lattice d) Complemented lattice Page 3 Discrete Structures Set1 Q1. Which of the following refers to Idempotent law? a) a b = b a b) a b = b a c) a ( b c ) = ( a b ) c d) a a = a Q2. Which of the following distributive laws should hold true for a distributive lattice? (i) p ( q r ) = ( p q ) ( p r ). (ii) p ( q r ) = ( p q ) r. (iii) p ( q r ) = ( p q ) ( p r ). (iv) p ( q r ) = ( p q ) r a) (i) and (ii) b) (i) and (iii) c) (ii) and (iii) d) (ii) and (iv) Q3. The Dual of any theorem in a lattice is : a) a law b) an order c) a theorem d) None of these Q4. Simplify the Boolean expression : (A + B)'(C + D + E)' + (A + B)' a) A'B' b) C'D'E' c) C+D+E d) A'B'C'D'E' Q5. Which of the following statement(s) is true regarding ISOMORPHIC BOOLEAN ALGEBRA? a) Every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra. b) Boolean algebra may not be a Boolean sub algebra of B. c) Both every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra & Boolean algebra may not be a Boolean sub algebra of B. d) None of these Q6. If a finite lattice L does not contain _____ elements for some positive integer n, then L cannot be a Boolean algebra. a) 2 n b) 2 n + 1 c) 2 n + 1 d) 2 n – 1 Q7. What is the complement of 6 in the lattice D = { 1, 2, 3, 4, 6, 12} ? a) 2 b) 4 c) 12 d) No complement Q8. A lattice L is called ________ if every non empty sub-set of L has a least upper bound and a greatest lower bound. a) Distributive lattice b) Complete lattice c) Modular lattice d) Complemented lattice Q9. Convert the below logical circuit into Boolean expression : a) ( A + B )'BC' b) ( A + B' )BC' c) ( A'B' )BC' d) ( AB)'BC' Q10. A lattice L is said to be complemented if every element of L has at least __________ complement(s). a) 4 b) 3 c) 2 d) 1 Q11. Find the in-degrees and out-degrees of vertices a, b, c and d in the same order for the following graph? a) 2 & 4, 2 & 1, 2 & 2 and 3 & 2 respectively b) 2 & 1, 3 & 2, 2 & 4 and 2 & 2 respectively c) 2 & 4, 2 & 1, 3 & 2, 2 & 2 respectively d) 2 & 1, 3 & 2, 2 & 2 and 2 & 4 respectively Page 4 Discrete Structures Set1 Q1. Which of the following refers to Idempotent law? a) a b = b a b) a b = b a c) a ( b c ) = ( a b ) c d) a a = a Q2. Which of the following distributive laws should hold true for a distributive lattice? (i) p ( q r ) = ( p q ) ( p r ). (ii) p ( q r ) = ( p q ) r. (iii) p ( q r ) = ( p q ) ( p r ). (iv) p ( q r ) = ( p q ) r a) (i) and (ii) b) (i) and (iii) c) (ii) and (iii) d) (ii) and (iv) Q3. The Dual of any theorem in a lattice is : a) a law b) an order c) a theorem d) None of these Q4. Simplify the Boolean expression : (A + B)'(C + D + E)' + (A + B)' a) A'B' b) C'D'E' c) C+D+E d) A'B'C'D'E' Q5. Which of the following statement(s) is true regarding ISOMORPHIC BOOLEAN ALGEBRA? a) Every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra. b) Boolean algebra may not be a Boolean sub algebra of B. c) Both every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra & Boolean algebra may not be a Boolean sub algebra of B. d) None of these Q6. If a finite lattice L does not contain _____ elements for some positive integer n, then L cannot be a Boolean algebra. a) 2 n b) 2 n + 1 c) 2 n + 1 d) 2 n – 1 Q7. What is the complement of 6 in the lattice D = { 1, 2, 3, 4, 6, 12} ? a) 2 b) 4 c) 12 d) No complement Q8. A lattice L is called ________ if every non empty sub-set of L has a least upper bound and a greatest lower bound. a) Distributive lattice b) Complete lattice c) Modular lattice d) Complemented lattice Q9. Convert the below logical circuit into Boolean expression : a) ( A + B )'BC' b) ( A + B' )BC' c) ( A'B' )BC' d) ( AB)'BC' Q10. A lattice L is said to be complemented if every element of L has at least __________ complement(s). a) 4 b) 3 c) 2 d) 1 Q11. Find the in-degrees and out-degrees of vertices a, b, c and d in the same order for the following graph? a) 2 & 4, 2 & 1, 2 & 2 and 3 & 2 respectively b) 2 & 1, 3 & 2, 2 & 4 and 2 & 2 respectively c) 2 & 4, 2 & 1, 3 & 2, 2 & 2 respectively d) 2 & 1, 3 & 2, 2 & 2 and 2 & 4 respectively Q12 . Which of the following graphs are connected? a) Only 1 b) 1 and 3 c) 1,3 and 4 d) 1, 2 and 3 Q13. Which of the following is a POS form for E = ( P + Q + R ) ( P + Q + R' ) ( P' + Q + R) ? a) PQR + PQR' + P'QR + PQ'R + PQ'R' b) PQ'R +PQR + PQR' + P'QR + P'Q'R c) PQR + PQR' + P'QR + PQ'R + P'QR' d) PQ'R +PQR + PQR' + P'QR + P'Q'R' Q14. Determine the number of edges in a graph with 7 nodes, 1 of degree 0, 1 of degree 1, 1 of degree 2, 1 of degree 3 and 3 of degree 4. a) 9 b) 10 c) 12 d) 18 Q15. The space required for an adjacency matrix is : a) O(V + E) b) O(V 2 ) c) O(E + E) d) O(E 2 ) Page 5 Discrete Structures Set1 Q1. Which of the following refers to Idempotent law? a) a b = b a b) a b = b a c) a ( b c ) = ( a b ) c d) a a = a Q2. Which of the following distributive laws should hold true for a distributive lattice? (i) p ( q r ) = ( p q ) ( p r ). (ii) p ( q r ) = ( p q ) r. (iii) p ( q r ) = ( p q ) ( p r ). (iv) p ( q r ) = ( p q ) r a) (i) and (ii) b) (i) and (iii) c) (ii) and (iii) d) (ii) and (iv) Q3. The Dual of any theorem in a lattice is : a) a law b) an order c) a theorem d) None of these Q4. Simplify the Boolean expression : (A + B)'(C + D + E)' + (A + B)' a) A'B' b) C'D'E' c) C+D+E d) A'B'C'D'E' Q5. Which of the following statement(s) is true regarding ISOMORPHIC BOOLEAN ALGEBRA? a) Every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra. b) Boolean algebra may not be a Boolean sub algebra of B. c) Both every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra & Boolean algebra may not be a Boolean sub algebra of B. d) None of these Q6. If a finite lattice L does not contain _____ elements for some positive integer n, then L cannot be a Boolean algebra. a) 2 n b) 2 n + 1 c) 2 n + 1 d) 2 n – 1 Q7. What is the complement of 6 in the lattice D = { 1, 2, 3, 4, 6, 12} ? a) 2 b) 4 c) 12 d) No complement Q8. A lattice L is called ________ if every non empty sub-set of L has a least upper bound and a greatest lower bound. a) Distributive lattice b) Complete lattice c) Modular lattice d) Complemented lattice Q9. Convert the below logical circuit into Boolean expression : a) ( A + B )'BC' b) ( A + B' )BC' c) ( A'B' )BC' d) ( AB)'BC' Q10. A lattice L is said to be complemented if every element of L has at least __________ complement(s). a) 4 b) 3 c) 2 d) 1 Q11. Find the in-degrees and out-degrees of vertices a, b, c and d in the same order for the following graph? a) 2 & 4, 2 & 1, 2 & 2 and 3 & 2 respectively b) 2 & 1, 3 & 2, 2 & 4 and 2 & 2 respectively c) 2 & 4, 2 & 1, 3 & 2, 2 & 2 respectively d) 2 & 1, 3 & 2, 2 & 2 and 2 & 4 respectively Q12 . Which of the following graphs are connected? a) Only 1 b) 1 and 3 c) 1,3 and 4 d) 1, 2 and 3 Q13. Which of the following is a POS form for E = ( P + Q + R ) ( P + Q + R' ) ( P' + Q + R) ? a) PQR + PQR' + P'QR + PQ'R + PQ'R' b) PQ'R +PQR + PQR' + P'QR + P'Q'R c) PQR + PQR' + P'QR + PQ'R + P'QR' d) PQ'R +PQR + PQR' + P'QR + P'Q'R' Q14. Determine the number of edges in a graph with 7 nodes, 1 of degree 0, 1 of degree 1, 1 of degree 2, 1 of degree 3 and 3 of degree 4. a) 9 b) 10 c) 12 d) 18 Q15. The space required for an adjacency matrix is : a) O(V + E) b) O(V 2 ) c) O(E + E) d) O(E 2 ) Q16. Find the path weight using nearest neighbor algorithm for the below graph starting from vertex A? a) 20 or 21 b) 21 or 22 c) 20 or 22 d) 21 or 19 Q17. Every regular graph with n vertices and degree r has ____________ edges. a) r/2 b) r n/2 c) r + n d) (r + n)/2 Q18. Which of the following is an adjacency matrix for the below given graph? a) b)Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!