Quiznetik

Discrete Mathematics | Set 2

1. Which of the arguments is not valid in proving sum of two odd number is not odd.

Correct : A. 3 + 3 = 6, hence true for all

2. A proof broken into distinct cases, where these cases cover all prospects, such proofs are known as

Correct : C. vacuous proof

3. A proof that p → q is true based on the fact that q is true, such proofs are known as

Correct : C. trivial proof

4. In the principle of mathematical induction, which of the following steps is mandatory?

Correct : A. induction hypothesis

5. For m = 1, 2, …, 4m+2 is a multiple of is known as

Correct : A. lemma

6. For any integer m>=3, the series 2+4+6+… +(4m) can be equivalent to

Correct : A. m2+3

7. For every natural number k, which of the following is true?

Correct : A. (mn)k = mknk

8. For any positive integer m              is divisible by 4.

Correct : D. m3 + 3m

9. What is the induction hypothesis assumption for the inequality m ! > 2m where m>=4?

Correct : B. for m=k, k!>2k holds

10. A polygon with 7 sides can be triangulated into

Correct : C. 5

11. A polygon with 12 sides can be triangulated into

Correct : B. 10

12. Which amount of postage can be formed using just 4-cent and 11-cent stamps?

Correct : D. 10

13. Suppose that P(n) is a propositional function. Determine for which positive integers n the statement P(n) must be true if: P(1) is true; for all positive integers n, if P(n) is true then P(n+2) is true.

Correct : A. p(3)

14. Suppose that P(n) is a propositional function. Determine for which positive integers n the statement P(n) must be true if: P(1) and P(2) is true; for all positive integers n, if P(n) and P(n+1) is true then P(n+2) is true.

Correct : D. p(n)

15. A polygon with 25 sides can be triangulated into

Correct : A. 23

16. How many even 4 digit whole numbers are there?

Correct : C. 4500

17. In a multiple-choice question paper of 15 questions, the answers can be A, B, C or D. The number of different ways of answering the question paper are

Correct : A. 65536 x 47

18. Neela has twelve different skirts, ten different tops, eight different pairs of shoes, three different necklaces and five different bracelets. In how many ways can Neela dress up?

Correct : B. 14400

19. For her English literature course, Ruchika has to choose one novel to study from a list of ten, one poem from a list of fifteen and one short story from a list of seven. How many different choices does Rachel have?

Correct : D. 10500

20. The code for a safe is of the form PPPQQQQ where P is any number from 0 to 9 and Q represents the letters of the alphabet. How many codes are possible for each of the following cases? Note that the digits and letters of the alphabet can be repeated.

Correct : D. 456976000

21. Amit must choose a seven-digit PIN number and each digit can be chosen from 0 to 9. How many different possible PIN numbers can Amit choose?

Correct : A. 10000000

22. A head boy, two deputy head boys, a head girl and 3 deputy head girls must be chosen out of a student council consisting of 14 girls and 16 boys. In how many ways can they are chosen?

Correct : B. 27384

23. A drawer contains 12 red and 12 blue socks, all unmatched. A person takes socks out at random in the dark. How many socks must he take out to be sure that he has at least two blue socks?

Correct : D. 14

24. When four coins are tossed simultaneously, in                number of the outcomes at most two of the coins will turn up as heads.

Correct : C. 11

25. How many numbers must be selected from the set {1, 2, 3, 4} to guarantee that at least one pair of these numbers add up to 7?

Correct : B. 5

26. During a month with 30 days, a cricket team plays at least one game a day, but no more than 45 games. There must be a period of some number of consecutive days during which the team must play exactly               number of games.

Correct : D. 24

27. In how many ways can 8 different dolls be packed in 5 identical gift boxes such that no box is empty if any of the boxes hold all of the toys?

Correct : D. 1260

28. A group of 20 girls plucked a total of 200 oranges. How many oranges can be plucked one of them?

Correct : A. 24

29. In a get-together party, every person present shakes the hand of every other person. If there were 90 handshakes in all, how many persons were present at the party?

Correct : B. 14

30. A bag contains 25 balls such as 10 balls are red, 7 are white and 8 are blue. What is the minimum number of balls that must be picked up from the bag blindfolded (without replacing any of it) to be assured of picking at least one ball of each colour?

Correct : B. 18

31. The number of diagonals can be drawn in a hexagon is

Correct : A. 9

32. A number lock contains 6 digits. How many different zip codes can be made with the digits 0–9 if repetition of the digits is allowed upto 3 digits from the beginning and the first digit is not 0?

Correct : B. 453600

33. In how many ways can 10 boys be seated in a row having 28 seats such that no two friends occupy adjacent seats?

Correct : C. 19p10

34. How many ways can 8 prizes be given away to 7 students, if each student is eligible for all the prizes?

Correct : B. 40320

35. There are 6 equally spaced points A, B, C, D, E and F marked on a circle with radius R. How many convex heptagons of distinctly different areas can be drawn using these points as vertices?

Correct : D. same area

36. How many ways are there to arrange 7 chocolate biscuits and 12 cheesecake biscuits into a row of 19 biscuits?

Correct : B. 50388

37. If a, b, c, d and e are five natural numbers, then find the number of ordered sets(a, b, c, d, e) possible such that a+b+c+d+e=75.

Correct : D. 74c4

38. There are 15 people in a committee. How many ways are there to group these 15 people into 3, 5, and 4?

Correct : D. 1317

39. There are six movie parts numbered from 1 to 6. Find the number of ways in which they be arranged so that part-1 and part-3 are never together.

Correct : B. 480

40. How many ways are there to divide 4 Indian countries and 4 China countries into 4 groups of 2 each such that at least one group must have only Indian countries?

Correct : A. 6

41. Find the number of factors of the product 58 * 75 * 23 which are perfect squares.

Correct : B. 30

42. From a group of 8 men and 6 women, five persons are to be selected to form a committee so that at least 3 women are there on the committee. In how many ways can it be done?

Correct : A. 686

43. What is the recurrence relation for 1, 7, 31, 127, 499?

Correct : C. bn=4bn-1+3

44. Find the value of a4 for the recurrence relation an=2an-1+3, with a0=6.

Correct : C. 141

45. What is the solution to the recurrence relation an=5an-1+6an-2?

Correct : B. 6n

46. Determine the value of a2 for the recurrence relation an = 17an-1 + 30n with a0=3.

Correct : D. 1437

47. Determine the solution for the recurrence relation an = 6an-1−8an-2 provided initial conditions a0=3 and a1=5.

Correct : B. an = 3 * 7n – 5*3n

48. What is the sequence depicted by the generating series 4 + 15x2 + 10x3 + 25x5 + 16x6+⋯?

Correct : C. 4, 0, 15, 10, 25, 16,…

49. What is multiplication of the sequence 1, 2, 3, 4,… by the sequence 1, 3, 5, 7, 11,….?

Correct : A. 1, 5, 14, 30,…

50. What will be the sequence generated by the generating function 4x/(1-x)2?

Correct : C. 0, 4, 8, 12, 16, 20,…

51. Find the sequence generated by 1/1−x2−x4.,assume that 1, 1, 2, 3, 5, 8,… has generating function 1/1−x−x2.

Correct : A. 0, 0, 1, 1, 2, 3, 5, 8,…

52. There are 70 patients admitted in a hospital in which 29 are diagnosed with typhoid, 32 with malaria, and 14 with both typhoid and malaria. Find the number of patients diagnosed with typhoid or malaria or both.

Correct : C. 47

53. At a software company, skilled workers have been hired for a project. Out of 75 candidates, 48 of them were software engineer; 35 of them were hardware engineer; 42 of them were network engineer; 18 of them had skills in all three jobs and all of them had skills in at least one of these jobs. How many candidates were hired who were skilled in exactly 2 jobs?

Correct : B. 14

54. In a renowned software development company of 240 computer programmers 102 employees are proficient in Java, 86 in C#, 126 in Python, 41 in C# and Java, 37 in Java and Python, 23 in C# and Python, and just 10 programmers are proficient in all three languages. How many computer programmers are there those are not proficient in any of these three languages?

Correct : B. 17

55. In class, students want to join sports. 15 people will join football, 24 people will join basketball, and 7 people will join both. How many people are there in the class?

Correct : D. 30

56. From 1, 2, 3, …, 320 one number is selected at random. Find the probability that it is either a multiple of 7 or a multiple of 3.

Correct : B. 42.5%

57. If each and every vertex in G has degree at most 23 then G can have a vertex colouring of

Correct : D. 54

58. Berge graph is similar to              due to strong perfect graph theorem.

Correct : B. perfect graph

59. A              is a graph which has the same number of edges as its complement must have number of vertices congruent to 4m or 4m modulo 4(for integral values of number of edges).

Correct : D. self complementary graph

60. In a              the vertex set and the edge set are finite sets.

Correct : B. bipartite graph

61. If G is the forest with 54 vertices and 17 connected components, G has                total number of edges.

Correct : B. 37

62. An undirected graph G has bit strings of length 100 in its vertices and there is an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position. Determine the ratio of the chromatic number of G to the diameter of G?

Correct : B. 1/50 c) 1/100

63. If each and every vertex in G has degree at most 23 then G can have a vertex colouring of

Correct : A. 24

64. Triangle free graphs have the property of clique number is

Correct : D. more than 10

65. Let D be a simple graph on 10 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6, a vertex of degree 7, a vertex of degree 8 and a vertex of degree 9. What can be the degree of the last vertex?

Correct : C. 2

66. A bridge can not be a part of

Correct : A. a simple cycle

67. Any subset of edges that connects all the vertices and has minimum total weight, if all the edge weights of an undirected graph are positive is called

Correct : B. tree

68. G is a simple undirected graph and some vertices of G are of odd degree. Add a node n to G and make it adjacent to each odd degree vertex of G. The resultant graph is

Correct : D. euler graph

69. Let G be a directed graph whose vertex set is the set of numbers from 1 to 50. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. Calculate the minimum number of edges in a path in G from vertex 1 to vertex 50.

Correct : C. 6

70. What is the number of vertices in an undirected connected graph with 39 edges, 7 vertices of degree 2, 2 vertices of degree 5 and remaining of degree 6?

Correct : C. 18

71. is the maximum number of edges in an acyclic undirected graph with k vertices.

Correct : A. k-1

72. The minimum number of edges in a connected cyclic graph on n vertices is

Correct : B. n

73. The maximum number of edges in a 8- node undirected graph without self loops is

Correct : C. 28

74. Let G be an arbitrary graph with v nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie down between            and

Correct : D. k-1 and v-1

75. The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n>=4. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in G can be

Correct : B. 3n/2

76. Every Isomorphic graph must have                  representation.

Correct : D. adjacency matrix

77. A cycle on n vertices is isomorphic to its complement. What is the value of n?

Correct : A. 5

78. A complete n-node graph Kn is planar if and only if

Correct : C. n ≤ 4

79. A graph is              if and only if it does not contain a subgraph homeomorphic to k5 or k3,3.

Correct : B. planar graph

80. An isomorphism of graphs G and H is a bijection f the vertex sets of G and H. Such that any two vertices u and v of G are adjacent in G if and only if

Correct : B. f(u) and f(v) are adjacent in h

81. What is the grade of a planar graph consisting of 8 vertices and 15 edges?

Correct : A. 30

82. A                is a graph with no homomorphism to any proper subgraph.

Correct : B. core

83. Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?

Correct : A. branch and bound

84. The problem of finding a path in a graph that visits every vertex exactly once is called?

Correct : A. hamiltonian path problem

85. Hamiltonian path problem is

Correct : D. np complete problem

86. Which of the following problems is similar to that of a Hamiltonian path problem?

Correct : C. travelling salesman problem

87. Who formulated the first ever algorithm for solving the Hamiltonian path problem?

Correct : A. martello

88. In what time can the Hamiltonian path problem can be solved using dynamic programming?

Correct : D. o(n2 2n)

89. Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem?

Correct : C. andreas bjorklund

90. For a graph of degree three, in what time can a Hamiltonian path be found?

Correct : A. o(0.251n)

91. What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?

Correct : B. o(n! * n)

92. How many Hamiltonian paths does the following graph have?

Correct : A. 1

93. How many Hamiltonian paths does the following graph have?

Correct : C. 0

94. If set C is {1, 2, 3, 4} and C – D = Φ then set D can be

Correct : C. {1, 2, 3, 4, 5}

95. Let C and D be two sets then C – D is equivalent to

Correct : C. c ∩ d’

96. For two sets C and D the set (C – D) ∩ D will be

Correct : C. Φ

97. Which of the following statement regarding sets is false?

Correct : D. (a u b)’ = a’ u b’

98. Let C = {1,2,3,4} and D = {1, 2, 3, 4} then which of the following hold not true in this case?

Correct : C. c ∩ d = c – d

99. Let Universal set U is {1, 2, 3, 4, 5, 6, 7, 8}, (Complement of A) A’ is {2, 5, 6, 7}, A ∩ B is {1, 3, 4} then the set B’ will surely have of which of the element?

Correct : A. 8

100. Let a set be A then A ∩ φ and A U φ are

Correct : B. φ, a