MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE ONLINE BITS

Code No: 07A3BS04 Set No. 1
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
II B.Tech. I Sem., II Mid-Term Examinations, Oct / Nov. – 2009
MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE
Objective Exam
I. Choose the correct alternative:
1. The recurrence relation representing towers of Hanoi problem is _____ [ ]
A. = +1, n>1, =1 B. = +2, n>0, =1
C. = 2+1, n>1, =1 D. = n, n>1, =1
2. In how many ways 3 letters are posted in 6 letter boxes [ ]
A. B. C. D.
3. The numeric function corresponding to the generating function is ___ [ ]
A. = , n>0, = 1 B. = , n>0, = 0
C. = , n>0, = 1 D. = , n>0, = 0
4. If is an Euler graph then _____ [ ]
A. Both m and n are even B. Both m and n are odd
C. m is even and n is odd D. m is even and n is odd
5. Maximum number of edges possible in a planar graph with 4 vertices is __ [ ]
A. 4 B. 5 C. 6 D. 7
6. The number of edges in graph is ____ [ ]
A. m*n B. m+n C. m+n-1 D. m*n-m-n
7. The maximum number of edges in a complete bipartite graph of n vertices is ____ [ ]
A. B. C. D.
8. A vertex with degree zero is called as ___ [ ]
A. source B. sink C. cut D. isolated
9. If a connected planar graph G has n vertices, e edges, and regions then which of the following formula holds true [ ]
A. n-e-r = 2 B. n+e+r = 2 C. n+e-r = 2 D. n-e+r = 2
10. The recurrence relation with constant coefficients = 2 is _____ [ ]
A. Linear only B. Linear but not homogeneous C. linear and homogeneous D. non-linear
Cont….2

A
Code No: 07A3BS04 :2: Set No. 1
II Fill in the blanks:
11. The coefficient of in is _____
12. The number of binary strings of length 7 is _______
13. The recurrence relation representing Fibonacci sequence is _____
14. Prim’s algorithm is used to find __________ of a graph
15. If the adjacency matrixes of two graphs are same, then the graphs are ______
16. Any planar graph G is _____ colorable
17. The number of spanning trees of a simple graph is ______
18. The chromatic number of a simple graph, i.e. is _____
19. Any connected graph with V vertices and E edges and V + 1 = E is a ______
20. A graph is bipartite iff it is colored with _____ colors
-oOo-
Code No: 07A3BS04 Set No. 2
I. Choose the correct alternative:
1. If is an Euler graph then _____ [ ]
A. Both m and n are even B. Both m and n are odd
C. m is even and n is odd D. m is even and n is odd
2. Maximum number of edges possible in a planar graph with 4 vertices is __ [ ]
A. 4 B. 5 C. 6 D. 7
3. The number of edges in graph is ____ [ ]
A.m*n B.m+n C.m+n-1 D.m*n-m-n
4. The maximum number of edges in a complete bipartite graph of n vertices is ____ [ ]
A. B. C. D.
5. A vertex with degree zero is called as ___ [ ]
A. source B. sink C. cut D. isolated
6. If a connected planar graph G has n vertices, e edges, and regions then which of the following formula holds true [ ]
A. n-e-r = 2 B. n+e+r = 2 C. n+e-r = 2 D. n-e+r = 2
7. The recurrence relation with constant coefficients = 2 is _____ [ ]
A. Linear only B. Linear but not homogeneous C. linear and homogeneous D. non-linear
8. The recurrence relation representing towers of Hanoi problem is _____ [ ]
A. = +1, n>1, =1 B. = +2, n>0, =1
C. = 2+1, n>1, =1 D. = n, n>1, =1
9. In how many ways 3 letters are posted in 6 letter boxes [ ]
A. B. C. D.
10. The numeric function corresponding to the generating function is ___ [ ]
A. = , n>0, = 1 B. = , n>0, = 0
C. = , n>0, = 1 D. = , n>0, = 0
Cont….2

A
Code No: 07A3BS04 :2: Set No. 2
II Fill in the blanks:
11. Prim’s algorithm is used to find __________ of a graph
12. If the adjacency matrixes of two graphs are same, then the graphs are ______
13. Any planar graph G is _____ colorable
14. The number of spanning trees of a simple graph is ______
15. The chromatic number of a simple graph, i.e. is _____
16. Any connected graph with V vertices and E edges and V + 1 = E is a ______
17. A graph is bipartite iff it is colored with _____ colors
18. The coefficient of in is _____
19. The number of binary strings of length 7 is _______
20. The recurrence relation representing Fibonacci sequence is _____
-oOo-
Code No: 07A3BS04 Set No. 3
I. Choose the correct alternative:
1. The number of edges in graph is ____ [ ]
A.m*n B.m+n C.m+n-1 D.m*n-m-n
2. The maximum number of edges in a complete bipartite graph of n vertices is ____ [ ]
A. B. C. D.
3. A vertex with degree zero is called as ___ [ ]
A. source B. sink C. cut D. isolated
4. If a connected planar graph G has n vertices, e edges, and regions then which of the following formula holds true [ ]
A. n-e-r = 2 B. n+e+r = 2 C. n+e-r = 2 D. n-e+r = 2
5. The recurrence relation with constant coefficients = 2 is _____ [ ]
A. Linear only B. Linear but not homogeneous C. linear and homogeneous D. non-linear
6. The recurrence relation representing towers of Hanoi problem is _____ [ ]
A. = +1, n>1, =1 B. = +2, n>0, =1
C. = 2+1, n>1, =1 D. = n, n>1, =1
7. In how many ways 3 letters are posted in 6 letter boxes [ ]
A. B. C. D.
8. The numeric function corresponding to the generating function is ___ [ ]
A. = , n>0, = 1 B. = , n>0, = 0
C. = , n>0, = 1 D. = , n>0, = 0
9. If is an Euler graph then _____ [ ]
A. Both m and n are even B. Both m and n are odd
C. m is even and n is odd D. m is even and n is odd
10. Maximum number of edges possible in a planar graph with 4 vertices is __ [ ]
A. 4 B. 5 C. 6 D. 7
Cont….2

A
Code No: 07A3BS04 :2: Set No. 3
II Fill in the blanks:
11. Any planar graph G is _____ colorable
12. The number of spanning trees of a simple graph is ______
13. The chromatic number of a simple graph, i.e. is _____
14. Any connected graph with V vertices and E edges and V + 1 = E is a ______
15. A graph is bipartite iff it is colored with _____ colors
16. The coefficient of in is _____
17. The number of binary strings of length 7 is _______
18. The recurrence relation representing Fibonacci sequence is _____
19. Prim’s algorithm is used to find __________ of a graph
20. If the adjacency matrixes of two graphs are same, then the graphs are ______
-oOo-
Code No: 07A3BS04 Set No. 4
I. Choose the correct alternative:
1. A vertex with degree zero is called as ___ [ ]
A. source B. sink C. cut D. isolated
2. If a connected planar graph G has n vertices, e edges, and regions then which of the following formula holds true [ ]
A. n-e-r = 2 B. n+e+r = 2 C. n+e-r = 2 D. n-e+r = 2
3. The recurrence relation with constant coefficients = 2 is _____ [ ]
A. Linear only B. Linear but not homogeneous C. linear and homogeneous D. non-linear
4. The recurrence relation representing towers of Hanoi problem is _____ [ ]
A. = +1, n>1, =1 B. = +2, n>0, =1
C. = 2+1, n>1, =1 D. = n, n>1, =1
5. In how many ways 3 letters are posted in 6 letter boxes [ ]
A. B. C. D.
6. The numeric function corresponding to the generating function is ___ [ ]
A. = , n>0, = 1 B. = , n>0, = 0
C. = , n>0, = 1 D. = , n>0, = 0
7. If is an Euler graph then _____ [ ]
A. Both m and n are even B. Both m and n are odd
C. m is even and n is odd D. m is even and n is odd
8. Maximum number of edges possible in a planar graph with 4 vertices is __ [ ]
A. 4 B. 5 C. 6 D. 7
9. The number of edges in graph is ____ [ ]
A.m*n B.m+n C.m+n-1 D.m*n-m-n
10. The maximum number of edges in a complete bipartite graph of n vertices is ____ [ ]
A. B. C. D.
Cont….2

A
Code No: 07A3BS04 :2: Set No. 4
II Fill in the blanks:
11. The chromatic number of a simple graph, i.e. is _____
12. Any connected graph with V vertices and E edges and V + 1 = E is a ______
13. A graph is bipartite iff it is colored with _____ colors
14. The coefficient of in is _____
15. The number of binary strings of length 7 is _______
16. The recurrence relation representing Fibonacci sequence is _____
17. Prim’s algorithm is used to find __________ of a graph
18. If the adjacency matrixes of two graphs are same, then the graphs are ______
19. Any planar graph G is _____ colorable
20. The number of spanning trees of a simple graph is ______
-oOo-