- Which of the following is tautology?
a.)x v y
b.)x v (~y)
c.)x v(~x)
d.)(x=<y)^(x<=y)
Ans.: c.)
Explanation:
| X | ~X | X V(~X) | ||
| T | F | T | ||
| F | T | T |
Tip: ‘~’ denotes negation that is ‘1’ means ‘0’ and ‘0’ means ‘1’
‘V’ means ‘OR’ operator.
Side note: Tautolgy means all the results should be True(T) or 1
- Minimum number of individual shoes to be picked up from a dark room (containing 10 pair of shoes) if we have to get atleast one proper pair.
a.)3
b.)11
c.)10
d.)20
Ans.: b.)
Explanation of logic: There are 10 pair of shoes.
A single proper matching pair can be found out only when we pick the 11th shoe because till 10th shoe we cannot be very sure that we will get the right pair. But the 11th shoe that we take will definitely let us match the right pair surely. (LOGICAL REASONING QUESTION)
Note: May be asked in interviews too.
- Circle has how many vertices?
a.) No vetices
b.) 2 vertex
c.) 5 vertex
d.) Infinite vertices
Ans.: d.)
Note: A simple but logic question.
You can mark as much vertices as possible on a circle.
Example:
- The logic of pumping lemma is and example of
a.)Recursion
b.) Divide and conquer rule
c.) Pigeon hole principle
d.) Iteration
Ans.: c.)
- An undirected graph possesses an eulerian circuit only if it is connected and its vertices are
a.) All of even degree
b.) All of odd degree
c.) of any degree
d.) even in number
Ans.: a.)
- The number of edges in a complete graph with N vertices is equal to
a.) N(N-1)
b.) 2N-1
c.) N-1
d.) N(N-1)/2
Ans.: d.)
- The number of edges in a connected graph with ‘n’ vertices is
a.) n-1
b.) n(n-1)/2
c.) n^2
d.) 2n-1
Ans.: a.)
- A graph G has
4,5
a.) 4 edges
b.) 5 edges
c.) 20 edges
d.) 15 edges
Ans.: c.)
Logic: Number of edges in Graph G(m,n)=m*n
- A self complemented,distributed lattice is
a.) Boolean algebra
b.) Modular lattice
c.) Complete lattice
d.) Self dual lattice.
Ans.: a.)
- A graph with all nodes of equal importance is called as
a.) Complete graph
b.) Regular graph
c.) Non regular graph
d.) Multigraph
Ans.: b.)
- A partial ordered relation is transitive, reflexive and
a.) bisymmetric
b.) antisymmetric
c.) antireflexive
d.) asymmetric
Ans.: b.)
- If n is an integer, and n^2 is odd then ‘n’ is
a.) even
b.) odd
c.) even or odd
d.) prime
Ans.: b.)
Reason:
1.) Let n be 7 then,
n^2=49
2.) Let n be 9 then,
n^2=81
In both cases, the result is an odd number
Therefore, answer is odd.
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 ?
Hamiltonian
Planar
Isomorphic
Euler
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 ?
Euler
Hamiltonian
Tree
Path
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 ?
A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices
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.
A simple graph which is Isomorphic to Hamiltonian graph
None of these
Answer = A
Explanation: No explanation for this question.
4) A continuous non – intersecting curve in the plane whose origin and terminus coincide ?
Planer
Jordan
Hamiltonian
All of these
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…. ?
A simple connected graph
A plane graph
A graph in which the degree of every vertex and every face is atleast 3
All of above
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 ?
Eulartour
Hamiltonian Path
Eular trail
Hamiltonian tour
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…. ?
A spanning sub graph
A tree
Minimum weights
All of above
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…. ?
Spanning tree
Rooted tree
Weighted tree
None of these
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…. ?
max (e(v) : v belongs to V)
max( d(u,v) )
Both A and B
None of these
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 ?
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
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 ?
P( A intersection B) = P(A). P(B)
P(A union B) = P(A) + P(B)
P(AB) = P(A intersection B). P(B)
P(A union B) >= P(A) + P(B)
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?
X union Y
Xc union Yc
X intersection Y
Xc intersection Yc
Answer = A
3) If G is an undirected planer graph on n vertices with e edges then ?
e<=n
e<=2n
e<=3n
None of these
Answer = B
4) Which of the following statement is false ?
G is connected and is circuitless
G is connected and has n edges
G is minimally connected graph
G is circuitless and has n-1 edges
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 / 2
1 / 3
2 / 3
None of these
Answer = B
6) The number of circuits that can be created by adding an edge between any two vertices in a tree is ?
Two
Exactly one
At least two
None
Answer = B
7) In a tree between every pair of vertices there is ?
Exactly one path
A self loop
Two circuits
n number of paths
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 ?
8
3
9
12
Answer = C
9) Context free languages are closed under ?
union, intersection
Intersection , complement
union , kleene star
Complement , kleene star
Answer = C
10) Let R be a symmetric and transitive relation on a set A. Then ?
R is reflexive and hence a partial order
R is reflexive and hence an equivalence relation
R is not reflexive and hence not an equivalence relation
None of above
Answer = D