Mathematical Foundations of Computer Science Mid - II, November - 2014

1.In how many different ways can the letters of the word ‘MATHEMATICS’ can be arranged in such a way that the vowels always come together?
  • 10080
  • 4989600
  • 120960
  • None
Answer: C
2.The maximum number of edges possible in a planar graph with 8 vertices is,
  • 15
  • 16
  • 17
  • 18
Answer: D
3.The number of spanning trees of the simple graph k4 is
  • 5
  • 8
  • 4
  • 6
Answer: C
4.A tree with n vertices has exactly ……….number of vertices
  • n+1
  • n-1
  • n (n+1)
  • n2
Answer: B
5.The solution of the recurrence relation an = an - 1 + 2an - 2 with a0 = 2 and a1 = 7 is
  • 3.2n – (-1)n
  • 2n – (-1)n
  • 3.2n + 2n
  • None
Answer: A
6.Euler’s formula is
  • V + E + R = 2
  • V − E + R = 2
  • V − R + E = 2
  • R − V + E = 2
Answer: B
7.In a non directed graph, the total number of vertices of odd degree is
  • Odd
  • Even
  • A and B
  • Depends on graph
Answer: B
8.The general solution of the recurrence relation an + 1 = 5 an is _____
  • an = a0.5n
  • an = a0.2n
  • an = a0.3n
  • none
Answer: A
9.A graph which has a Hamiltonian circuit is called ________
  • Eulerian graph
  • Hamiltonian graph
  • Trivial graph
  • None
Answer: B
10.The number of circular permutation of n different objects =______
  • n-1
  • N+!
  • (n-1)!
  • (n+1)!
Answer: C
11.How many 4 digit numbers, not beginning with zero, without repeating any digit, can be formed using 0, 1, 2, 3, and 4 __________________
Answer: 96
12.The solution of the recurrence relation an = an-1 + n3 where a0=5 by method of substitution is __________________
Answer: an = { n2(n + 1)2 / 4 } + 5
13.The chromatic number of tree with n vertices is __________________
Answer: 2
14.The total number of edges of a complete graph with 50 vertices ______________
Answer: 1225
15.Suppose that f(n) = f(n/5) + 3 n2 where n is divisible by 5 and f(1) = 4, then f(125) = ___________
Answer: 48829
16.The solution of the recurrence relation ar = 2 ar-1+1with a1 = 7 is __________
Answer: ar = 7.2r-1 + 2r-1 - 1
17.In how many ways can nine students be partitioned into three teams containing four, three, and two students respectively ______________
Answer: 1260
18.15 males and 10females are _____________ways seated in round table and all females seated together
Answer: 15! X 10!
19.IF planner graph is self dual then _________________________
Answer: |E| = 2|V| - 2
20.A graph G is a tree if and only if ___________________________
Answer: G has no cycles & |E| = |V| - 1