Discrete Mathematics Solved M C Q s
A graph G is called a..... If it is a connected cyclic
graph
Cyclic
graph
Regular
graph
Tree
Not a
graph
_____________________________________________________________________________________
What is the probability of choosing correctly an unknown
integer between 0 and 9 with 3 chances?
963/1000
966/1000
968/1000
969/1000
_____________________________________________________________________________________
In an UN directed graph the number of nodes with odd degree
must be
Zero
Odd
Prime
Even
_____________________________________________________________________________________
A graph is a collection of
Row and
columns
Vertices
and edges
Equations
None of
these
_____________________________________________________________________________________
The relation { (1,2), (1,3), (3,1), (1,1), (3,3), (3,2),
(1,4), (4,2), (3,4)} is
Reflexive
Transitive
Symmetric
Asymmetric
_____________________________________________________________________________________
An undirected graph possesses a eulerian circuit if and only
if it is connected and its vertices are
All of
even degree
All of
odd degree
Of any
degree
Even in
number
_____________________________________________________________________________________
How many relations are there on a set with n elements that
are symmetric and a set with n elements that are reflexive and symmetric?
2n (n+1)/2
and 2n.3n(n–1)/2
3n(n–1)/2
and 2n(n–1)
2n(n+1)/2
and 3n(n–1)/2
2n(n+1)/2
and 2n(n–1)/2
_____________________________________________________________________________________
The number of colours required to properly colour the
vertices of every planer graph is
2
3
4
5
_____________________________________________________________________________________
In how many ways can a president and vice president be
chosen from a set of 30 candidates?
820
850
880
870
_____________________________________________________________________________________
Consider an undirected random graph of eight vertices. The
probability that there is an edge between a pair of vertices is ½. What is the
expected number of unordered cycles of length three?
1/8
1
7
8
_____________________________________________________________________________________
In a graph if e=(u, v) means
u is
adjacent to v but v is not adjacent to u
e
begins at u and ends at v
u is
processor and v is successor
both b
and c
_____________________________________________________________________________________
A minimal spanning tree of a graph G is
A
spanning sub graph
A tree
Minimum
weights
All of
above
_____________________________________________________________________________________
The number of leaf nodes in a complete binary tree of depth
d is
2d
2d+1
_____________________________________________________________________________________
A partial ordered relation is transitive, reflexive and
Bi symmetric
Anti
reflexive.
Asymmetric
_____________________________________________________________________________________
In a graph if e=[u, v], Then u and v are called
Endpoints
of e
Adjacent
nodes
Neighbors
All of
above
_____________________________________________________________________________________
In how many ways can a hungry student choose 3 toppings for
his prize from a list of 10 delicious possibilities?
100
120
110
150
_____________________________________________________________________________________
A graph with n vertices will definitely have a parallel edge
or self loop if the total number of edges are
greater
than n–1
less
than n(n–1)
greater
than n(n–1)/2
less
than n2/2
_____________________________________________________________________________________
A vertex of a graph is called even or odd depending upon
Total
number of edges in a graph is even or odd
Total
number of vertices in a graph is even or odd
Its
degree is even or odd
None of
these
_____________________________________________________________________________________
In any undirected graph the sum of degrees of all the nodes
Must be
even
Are
twice the number of edges
Must be
odd
Need
not be even
_____________________________________________________________________________________
The expression a+a c is equivalent to
a
a+c
c
1
_____________________________________________________________________________________
A graph with one vertex and no edges is
multigraph
digraph
isolated
graph
trivial
graph
_____________________________________________________________________________________
Length of the walk of a graph is
The
number of vertices in walk W
The
number of edges in walk W
Total
number of edges in a graph
Total
number of vertices in a graph
_____________________________________________________________________________________
The number of colours required to properly color vertices of
every planar graph is
2
3
4
5
_____________________________________________________________________________________
A
B
C
D
_____________________________________________________________________________________
A graph with no edges is known as empty graph. Empty graph
is also known as
Trivial
graph
Regular
graph
Bipartite
graph
None of
these
_____________________________________________________________________________________
Which two of the following are equivalent for an undirected
graph G?
(i) G is a tree
(ii) There is at least one path between any two distinct
vertices of G
(iii) G contains no cycles and has (n-1) edges
(iv)G has n edges
(i) and
(ii)
(i) and
(iii)
(i) and
(iv)
(ii)
and (iii)
_____________________________________________________________________________________
Choose the most appropriate definition of plane graph
A graph
drawn in a plane in such a way that any pair of edges meet only at their end
vertices
_____________________________________________________________________________________
A continuous non intersecting curve in the plane whose
origin and terminus coincide
Planer
Jordan
Hamiltonian
All of
these
_____________________________________________________________________________________
A graph with n vertices will definitely have a parallel edge
or self loop of the total number of edges are
more
than n
more
than n+1
more
than (n+1)/2
more
than n(n-1)/2
_____________________________________________________________________________________
A debating team consists of 3 boys and 2 girls. Find the
number of ways they can sit in a row?
120
24
720
12
_____________________________________________________________________________________
Which one of the following statements is incorrect ?
The
number of regions corresponds to the cyclomatic complexity.
Cyclometer complexity for a flow graph G is V(G) = N–E+2, where E is the number of edges
and N is the number of nodes in the flow graph.
Which of the following pair is not congruent modulo 7?
10, 24
25, 56
-31, 11
-64,
-15
The maximum degree of any vertex in a simple graph with n
vertices is
n–1
n+1
2n–1
n
_____________________________________________________________________________________
The complete graph with four vertices has k edges where k is
3
4
5
6
_____________________________________________________________________________________
Consider a weighted undirected graph with positive edge
weights and let (u, v) be an edge in the graph. It is known that the shortest
path from source vertex s to u has weight 53 and shortest path from s to v has
weight 65. Which statement is always true ?
Weight
(u, v) <= 12
Weight
(u, v) = 12
Weight
(u, v) >= 12
Weight
(u, v) > 12
_____________________________________________________________________________________
How many onto (or surjective) functions are there from an
n-element (n => 2) set to a 2-element set?
2n
2n - 1
2n - 2
2(2n –
2)
_____________________________________________________________________________________
Suppose v is an isolated vertex in a graph, then the degree
of v is
0
1
2
3
_____________________________________________________________________________________
The number of nodes in a complete binary tree of height h
(with roots at level 0) is equal to
20 + 21
+ ….. 2h
20 + 21
+ ….. 2h-1
20 + 21
+ ….. 2h+1
21 +
….. 2h+1
_____________________________________________________________________________________
Hasse diagram are drawn
Partially
ordered sets
Lattices
Boolean
algebra
None of
these
_____________________________________________________________________________________
In how many ways can 5 balls be chosen so that 2 are red and
3 are black
910
990
970
960
_____________________________________________________________________________________
Circle has ____________
No
vertices
Only 1
vertex
8
vertices
None of
these
_____________________________________________________________________________________
How many different words can be formed out of the letters of
the word VARANASI?
64
120
40320
720
_____________________________________________________________________________________
The proposition ~qvp is equivalent to
p?q
q?p
p?q
p?q
_____________________________________________________________________________________
A graph is tree if and only if
Is
planar
Contains
a circuit
Is
minimally
Is
completely connected
_____________________________________________________________________________________
If B is a Boolean Algebra, then which of the following is
true
B is a
finite but not complemented lattice
B is a
finite, complemented and distributive lattice
B is a
finite, distributive but not complemented lattice
B is
not distributive lattice
_____________________________________________________________________________________
Let G be a simple undirected planar graph on 10 vertices
with 15 edges. If G is a connected graph, then the number of bounded faces in
any embedding of G on the plane is equal to
3
4
5
6
The number of distinguishable permutations of the letters in
the word BANANA are,
60
36
20
10
_____________________________________________________________________________________
If R is a relation “Less Than” from A = {1,2,3,4} to B =
{1,3,5} then RoR-1 is
{(3,3),
(3,4), (3,5)}
{(3,1),
(5,1), (3,2), (5,2), (5,3), (5,4)}
{(3,3),
(3,5), (5,3), (5,5)}
{(1,3),
(1,5), (2,3), (2,5), (3,5), (4,5)}
0 comments: