WorksheetsMA8351-DM IAT-II
Total questions: 40
Worksheet time: 1hrs 20mins
Name
Class
Date
1.
Determine the solution of the recurrence relation Fn=20Fn-1 − 25Fn-2 where F0=4 and F1=14.
a)
an = 14*5n-1
b)
an = 7/2*2n−1/2*6n
c)
an = 7/2*2n−3/4*6n+1
d)
an = 3*2n−1/2*3n
2.
Find the value of a4 for the recurrence relation an=2an-1+3, with a0=6.
a)
320
b)
221
c)
141
d)
65
3.
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.
a)
39
b)
17
c)
47
d)
53
4.
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?
a)
69
b)
14
c)
32
d)
8
5.
The numbers between 1 and 520, including both, are divisible by 2 or 6 is _______
a)
349
b)
54
c)
213
d)
303
6.
The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is ------
a)
210
b)
200
c)
165
d)
271
7.
In a class of 35 students, 17 have taken mathematics, 10 have taken mathematics but not computers. Find the students who have taken both mathematics and computers.
a)
11
b)
7
c)
9
d)
13
8.
A card is drawn randomly from a standard deck of cards. Determine the probability that the card drawn is a queen or a heart.
a)
14
b)
1356
c)
413
d)
552
9.
There are 9 letters having different colours (red, orange, yellow, green, blue, indigo, violet) and 4 boxes each of different shapes (tetrahedron, cube, polyhedron, dodecahedron). How many ways are there to place these 9 letters into the 4 boxes such that each box contains at least 1 letter?
a)
260100
b)
878760
c)
437102
d)
256850
10.
If X and Y have 3 and 6 elements each, then minimum number of elements in A U B is
a)
3
b)
6
c)
9
d)
18
11.
The maximum number of edges in a bipartite graph on 14 vertices is ___________
a)
56
b)
14
c)
49
d)
87
12.
In a complete bipartite graph, the intersection of two sub graphs is ______
a)
1
b)
null
c)
2 power 10
d)
412
13.
All closed walks are of ______ length in a bipartite graph.
a)
infinite
b)
even
c)
odd
d)
odd prime
14.
The spectrum of a graph is _______ if and only if it is _______ graph.
a)
symmetry, bipartite
b)
transitive, bipartite
c)
cyclic, Euler
d)
reflexive, planar
15.
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).
a)
Subgraph
b)
Hamiltonian graph
c)
Euler graph
d)
Self complementary graph
16.
The number of edges in a regular graph of degree 46 and 8 vertices is ____________
a)
347
b)
230
c)
184
d)
186
17.
A bridge cannot be a part of _______
a)
a simple cycle
b)
a tree
c)
a clique with size ≥ 3 whose every edge is a bridge
d)
a graph which contains cycles
18.
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 ______
a)
Complete bipartite graph
b)
Hamiltonian cycle
c)
Regular graph
d)
Euler graph
19.
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?
a)
11
b)
14
c)
18
d)
19
20.
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 _____
a)
n-1 and n+1
b)
v and k
c)
k+1 and v-k
d)
k-1 and v-1
21.
Every Isomorphic graph must have ________ representation.
a)
cyclic
b)
adjacency list
c)
tree
d)
adjacency matrix
22.
The number of ways to cut a six sided convex polygon whose vertices are labeled into four triangles using diagonal lines that do not cross is
a)
13
b)
14
c)
12
d)
11
23.
How many perfect matchings are there in a complete graph of 6 vertices?
a)
15
b)
24
c)
30
d)
60
24.
Let G1= (V, E1) and G2= (V, E2) be connected graphs on the same vertex set V with more than two vertices. If G1ꓵ G2= (V, E1 ꓵE2) is not a connected graph, then the graph G1U G2= (V, E1 UE2).
a)
Cannot have a cut-vertex
b)
Must have a cycle
c)
Must have a cut-edge(bridge)
d)
Has chromatic number strictly greater than those of G1 and G2
25.
A cycle on n vertices is isomorphic to its complement. What is the value of n?
a)
5
b)
32
c)
17
d)
8
26.
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?
a)
4
b)
0
c)
2
d)
5
27.
In a 7-node directed cyclic graph, the number of Hamiltonian cycle is to be ______
a)
728
b)
450
c)
360
d)
260
28.
Bipartite graphs are used in ________
a)
modern coding theory
b)
colouring graphs
c)
neural networks
d)
chemical bonds
29.
A ______ in a graph G is a circuit which consists of every vertex (except first/last vertex) of G exactly once.
a)
Euler path
b)
Hamiltonian path
c)
Planar graph
d)
Path complement graph
30.
Determine the edge count of a path complement graph with 14 vertices.
a)
502
b)
345
c)
78
d)
69
31.
The maximum number of edges in a bipartite graph on 12 vertices is -----
a)
36
b)
32
c)
24
d)
12
32.
Which one of the following statements is true for every planar graph on n vertices?
a)
The graph is connected
b)
The graph is Eulerian
c)
The graph has a vertex-cover of size at most 3n/4
d)
The graph has an independent set of size at least n/3
33.
Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is -----
a)
18
b)
14
c)
12
d)
15
34.
Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is
a)
6
b)
8
c)
9
d)
13
35.
The sum of an n-node graph and its complement graph produces a graph called _______
a)
complete graph
b)
bipartite graph
c)
star graph
d)
path-complement graph
36.
A walk has Closed property if ____________
a)
v0=vk
b)
v0>=vk
c)
v < 0
d)
vk > 1
37.
The _______ of a graph G consists of all vertices and edges of G.
a)
edge graph
b)
line graph
c)
path complement graph
d)
eulerian circuit
38.
An isomorphism of graphs G and H is a bijection of 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 ____________
a)
f(u) and f(v) are contained in G but not contained in H
b)
f(u) and f(v) are adjacent in H
c)
f(u * v) = f(u) + f(v)
d)
f(u) = f(u)2 + f(v)2
39.
A graph is ______ if and only if it does not contain a subgraph homomorphic to k5 or k3,3.
a)
bipartite graph
b)
planar graph
c)
line graph
d)
euler subgraph
40.
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
100 %
