10/11/2017 Discrete Structure Solved MCQs | Computer Science Solved MCQs

COMPUTER SCIENCE SOLVED MCQS

Solved MCQs For All

Discrete Structure Solved MCQs

Discrete Structure Solved MCQs

1) Let A and B be any two arbitrary events then which one of the following is true ?

1. P( A intersection B) = P(A). P(B)

2. P(A union B) = P(A) + P(B)
3. P(AB) = P(A intersection B). P(B)
4. P(A union B) >= P(A) + P(B)

Collection From: www.cs-mcqs.blogspot.com

Answer = D

2) If X and Y be the sets. Then the set ( X - Y) union (Y- X) union (X intersection Y ) is equal to?

1. X union Y
2. Xc union Yc
3. X intersection Y

4. Xc intersection Yc

Collection From: www.cs-mcqs.blogspot.com

Answer = A

3) If G is an undirected planer graph on n vertices with e edges then ?

1. e<=n
2. e<=2n
3. e<=3n
4. None of these

Collection From: www.cs-mcqs.blogspot.com

Answer = B

4) Which of the following statement is false ?

http://cs-mcqs.blogspot.in/2012/11/discrete-structure-solved-mcqs.html 1/10
10/11/2017 Discrete Structure Solved MCQs | Computer Science Solved MCQs

1. G is connected and is circuitless

2. G is connected and has n edges
3. G is minimally connected graph
4. G is circuitless and has n-1 edges

Collection From: www.cs-mcqs.blogspot.com

Answer = B

5) Probability that two randomly selected cards from a set of two red and two black cards are of same
color is ?

1. 1/2
2. 1 / 3
3. 2 / 3
4. None of these

Collection From: www.cs-mcqs.blogspot.com

Answer = B

6) The number of circuits that can be created by adding an edge between any two vertices in a tree is ?

1. Two
2. Exactly one
3. At least two
4. None

Collection From: www.cs-mcqs.blogspot.com

Answer = B

7) In a tree between every pair of vertices there is ?

1. Exactly one path

2. A self loop
3. Two circuits
4. n number of paths

Collection From: www.cs-mcqs.blogspot.com

Answer = A

8) The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to
guarantee that three cards are from some same suit is ?

1. 8
2. 3
3. 9
4. 12

Collection From: www.cs-mcqs.blogspot.com

Answer = C

http://cs-mcqs.blogspot.in/2012/11/discrete-structure-solved-mcqs.html 2/10
10/11/2017 Discrete Structure Solved MCQs | Computer Science Solved MCQs

9) Context free languages are closed under ?

1. union, intersection
2. Intersection , complement
3. union , kleene star
4. Complement , kleene star

Collection From: www.cs-mcqs.blogspot.com

Answer = C

10) Let R be a symmetric and transitive relation on a set A. Then ?

1. R is reflexive and hence a partial order

2. R is reflexive and hence an equivalence relation
3. R is not reflexive and hence not an equivalence relation
4. None of above

Collection From: www.cs-mcqs.blogspot.com

Answer = D

SET-2

1) A graph is a collection of.... ?

1. Row and columns

2. Vertices and edges
3. Equations
4. None of these

Collection From: www.cs-mcqs.blogspot.com

Answer = B
Explanation: A graph contains the edges and vertices

2) The degree of any vertex of graph is .... ?

1. The number of edges incident with vertex

2. Number of vertex in a graph
3. Number of vertices adjacent to that vertex

4. Number of edges in a graph

Collection From: www.cs-mcqs.blogspot.com

Answer = A
Explanation: The number of edges connected on a vertex v with the self loop counted twice is called
the degree of vertex.

3) If for some positive integer k, degree of vertex d(v)=k for every vertex v of the graph G, then G is
called... ?

1. K graph
http://cs-mcqs.blogspot.in/2012/11/discrete-structure-solved-mcqs.html 3/10
10/11/2017 Discrete Structure Solved MCQs | Computer Science Solved MCQs

2. K-regular graph
3. Empty graph
4. All of above

Collection From: www.cs-mcqs.blogspot.coms

Answer = B
Explanation: A graph in which all vertices are of equal degree is called regular graph.

4) A graph with no edges is known as empty graph. Empty graph is also known as... ?

1. Trivial graph
2. Regular graph
3. Bipartite graph
4. None of these

Collection From: www.cs-mcqs.blogspot.com

Answer = A
Explanation: Trivial graph is the second name for empty graph.

5) Length of the walk of a graph is .... ?

1. The number of vertices in walk W

2. The number of edges in walk W
3. Total number of edges in a graph
4. Total number of vertices in a graph

Collection From: www.cs-mcqs.blogspot.com

Answer = B
Explanation: A walk is defined as finite altering sequence of vertices and edges. No Edges appear
more than once but vertex may appear more than once.

6) If the origin and terminus of a walk are same, the walk is known as... ?

1. Open
2. Closed
3. Path
4. None of these

Collection From: www.cs-mcqs.blogspot.com

Answer = B
Explanation: A walk which begins and ends with same vertex is called closed walk otherwise it is
open.

7) A graph G is called a ..... if it is a connected acyclic graph ?

1. Cyclic graph
2. Regular graph
3. Tree
4. Not a graph
http://cs-mcqs.blogspot.in/2012/11/discrete-structure-solved-mcqs.html 4/10
10/11/2017 Discrete Structure Solved MCQs | Computer Science Solved MCQs

Collection From: www.cs-mcqs.blogspot.com

Answer = C
Explanation: No explanation for this question.

8) Eccentricity of a vertex denoted by e(v) is defined by.... ?

1. max { d(u,v): u belongs to v, u does not equal to v : where d(u,v) is the distance between u&v}
2. min { d(u,v): u belongs to v, u does not equal to v }
3. Both A and B
4. None of these

Collection From: www.cs-mcqs.blogspot.com

Answer = A
Explanation: The eccentricity E(v) of a vertex V in the graph is the distance from v to the vertex
farthest from v in G.

9) Radius of a graph, denoted by rad(G) is defined by.... ?

1. max {e(v): v belongs to V }

2. min { e(v): v belongs to V}
3. max { d(u,v): u belongs to v, u does not equal to v }
4. min { d(u,v): u belongs to v, u does not equal to v }

Collection From: www.cs-mcqs.blogspot.com

Answer = A
Explanation: The diameter or radius of a graph G is largest distance between two vertices in the
graph G.

10) The complete graph K, has... different spanning trees?

1. nn-2
2. n*n
3. nn
4. n2

Collection From: www.cs-mcqs.blogspot.com

Answer = A
Explanation: No explanation for this question.

SET-3

1) A tour of G is a closed walk of graph G which includes every edge G at least once. A ..... tour of G is
a tour which includes every edge of G exactly once ?

1. Hamiltonian
2. Planar
3. Isomorphic
4. Euler

http://cs-mcqs.blogspot.in/2012/11/discrete-structure-solved-mcqs.html 5/10
10/11/2017 Discrete Structure Solved MCQs | Computer Science Solved MCQs

Collection From: www.cs-mcqs.blogspot.com

Answer = D
Explanation: If some closed walk in a graph contains all the edges then the walk is called Euler.
2) Which of the following is not a type of graph ?

1. Euler
2. Hamiltonian
3. Tree
4. Path

Collection From: www.cs-mcqs.blogspot.com

Answer = D
Explanation:Path is a way from one node no another but not a graph.

3) Choose the most appropriate definition of plane graph ?

1. A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices
2. A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non -
empty disjoint subset X and Y in such a way that each edge of G has one end in X and one end in Y.
3. A simple graph which is Isomorphic to Hamiltonian graph
4. None of these

Collection From: www.cs-mcqs.blogspot.com

Answer = A
Explanation: No explanation for this question.
4) A continuous non - intersecting curve in the plane whose origin and terminus coincide ?

1. Planer
2. Jordan

3. Hamiltonian
4. All of these

Collection From: www.cs-mcqs.blogspot.com

Answer = B
Explanation: The jordan graph is the set of all vertices of minimum eccentricity that is the set of all
vertices A where the greatest distance to other vertex B is minimal.
5) Polyhedral is.... ?

1. A simple connected graph

2. A plane graph
3. A graph in which the degree of every vertex and every face is atleast 3
4. All of above

Collection From: www.cs-mcqs.blogspot.com

Answer = D
Explanation: A polyhedral graph is the undirected graph formed from the vertices and edges of a
convex polyhedron

6) A path in graph G, which contains every vertex of G once and only once ?

http://cs-mcqs.blogspot.in/2012/11/discrete-structure-solved-mcqs.html 6/10
10/11/2017 Discrete Structure Solved MCQs | Computer Science Solved MCQs

1. Eulartour
2. Hamiltonian Path
3. Eular trail
4. Hamiltonian tour

Collection From: www.cs-mcqs.blogspot.com

Answer = B
Explanation:A Hamiltonian circuit in a connected graph is defined as a closed walk that traverse
every vertex of G exactly once except the starting vertex.

7) A minimal spanning tree of a graph G is.... ?

1. A spanning sub graph

2. A tree
3. Minimum weights
4. All of above

Collection From: www.cs-mcqs.blogspot.com

Answer = D
Explanation: A tree is said to be spanning tree of connected graph G if it is subgraph of G and
contains all the vertices of G.
8) A tree having a main node, which has no predecessor is.... ?

1. Spanning tree
2. Rooted tree
3. Weighted tree
4. None of these

Collection From: www.cs-mcqs.blogspot.com

Answer = B
Explanation:A tree in which one vertex distinguish from all other is called rooted tree.

9) Diameter of a graph is denoted by diam(G) is defined by.... ?

1. max (e(v) : v belongs to V)

2. max( d(u,v) )
3. Both A and B
4. None of these

Collection From: www.cs-mcqs.blogspot.com

Answer = C
Explanation: The diameter of a graph G is largest distance between two vertices in a graph G.

10) A vertex of a graph is called even or odd depending upon ?

1. Total number of edges in a graph is even or odd

2. Total number of vertices in a graph is even or odd
3. Its degree is even or odd
4. None of these

http://cs-mcqs.blogspot.in/2012/11/discrete-structure-solved-mcqs.html 7/10
10/11/2017 Discrete Structure Solved MCQs | Computer Science Solved MCQs

Collection From: www.cs-mcqs.blogspot.com

Answer = C
Explanation: The vertex of a graph is called even or odd based on its degree.

SET-4

1) Let A and B be any two arbitrary events then which one of the following is true ?

1. P( A intersection B) = P(A). P(B)

2. P(A union B) = P(A) + P(B)
3. P(AB) = P(A intersection B). P(B)
4. P(A union B) >= P(A) + P(B)

Collection From: www.cs-mcqs.blogspot.com

Answer = D

2) If X and Y be the sets. Then the set ( X - Y) union (Y- X) union (X intersection Y ) is equal to?

1. X union Y
2. Xc union Yc
3. X intersection Y
4. Xc intersection Yc

Collection From: www.cs-mcqs.blogspot.com

Answer = A

3) If G is an undirected planer graph on n vertices with e edges then ?

1. e<=n
2. e<=2n
3. e<=3n
4. None of these

Collection From: www.cs-mcqs.blogspot.com

Answer = B

4) Which of the following statement is false ?

1. G is connected and is circuitless

2. G is connected and has n edges
3. G is minimally connected graph
4. G is circuitless and has n-1 edges

Collection From: www.cs-mcqs.blogspot.com

Answer = B

5) Probability that two randomly selected cards from a set of two red and two black cards are of same
color is ?
http://cs-mcqs.blogspot.in/2012/11/discrete-structure-solved-mcqs.html 8/10
10/11/2017 Discrete Structure Solved MCQs | Computer Science Solved MCQs

1. 1/2
2. 1 / 3
3. 2 / 3
4. None of these

Collection From: www.cs-mcqs.blogspot.com

Answer = B

6) The number of circuits that can be created by adding an edge between any two vertices in a tree is ?

1. Two
2. Exactly one
3. At least two
4. None

Collection From: www.cs-mcqs.blogspot.com

Answer = B

7) In a tree between every pair of vertices there is ?

1. Exactly one path

2. A self loop
3. Two circuits
4. n number of paths

Collection From: www.cs-mcqs.blogspot.com

Answer = A

8) The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to
guarantee that three cards are from some same suit is ?

1. 8
2. 3
3. 9
4. 12

Collection From: www.cs-mcqs.blogspot.com

Answer = C

9) Context free languages are closed under ?

1. union, intersection
2. Intersection , complement
3. union , kleene star
4. Complement , kleene star

Collection From: www.cs-mcqs.blogspot.com

Answer = C

10) Let R be a symmetric and transitive relation on a set A. Then ?

http://cs-mcqs.blogspot.in/2012/11/discrete-structure-solved-mcqs.html 9/10
10/11/2017 Discrete Structure Solved MCQs | Computer Science Solved MCQs

1. R is reflexive and hence a partial order

2. R is reflexive and hence an equivalence relation
3. R is not reflexive and hence not an equivalence relation
4. None of above

Collection From: www.cs-mcqs.blogspot.com

Answer = D

http://cs-mcqs.blogspot.in/2012/11/discrete-structure-solved-mcqs.html 10/10