Discrete Mathematical Structures Solved MCQs- Part2

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)       _____________________________________________________________________________________

A partial ordered relation is transitive, reflexive and Antisymmetric Bisymmetric Anti reflexive. Asymmetric       _____________________________________________________________________________________

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       _____________________________________________________________________________________

Which of the following statements are TRUE? (1) The problem of determining whether there exists a cycle in an undirected graph is in P. (2) The problem of determining whether there exists a cycle in an undirected graph is in NP. (3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A. 1,2 and 3 1 and 2 only 1 and 3 only 2 and 3 only       _____________________________________________________________________________________

If n is an integer and n2 is odd ,then n is even odd even or odd prime       _____________________________________________________________________________________

How many different words can be formed out of the letters of the word VARANASI? 64 120 40320 720       _____________________________________________________________________________________

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)       _____________________________________________________________________________________

The complete graph with four vertices has k edges where k is 3 4 5 6       _____________________________________________________________________________________

Which of the following shall be a compound proposition involving the propositions p, q and r, that is true when exactly two of the p, q and r are true and is false otherwise ? A B C D       _____________________________________________________________________________________

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       _____________________________________________________________________________________

In any undirected graph,the sum of degrees of all nodes Must be even Is twice the number of edges Must be odd Must be even       _____________________________________________________________________________________

The number of colours required to properly color vertices of every planar graph is 2 3 4 5       _____________________________________________________________________________________

The trapzoidal rule for integration gives exact result when integrated is polynomial of degree 0 but not 1 1 but not 0 0 or 1 2       _____________________________________________________________________________________

Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of distinct cycles of length 4 in G is equal to 15 45 90 360       _____________________________________________________________________________________

Consider an undirected graph G with 100 nodes. The maximum number of edges to be included in G so that the graph is not connected is 2451 4950 4851 9900       _____________________________________________________________________________________

If two fair coins are flipped and at least one of the outcomes is known to be a head, what is the probability that both outcomes are heads? 1/3 1/4 1/2 2/3       _____________________________________________________________________________________

A graph G is called a ..... if it is a connected acyclic graph Cyclic graph Regular graph Tree Not a graph       _____________________________________________________________________________________

In how many ways can a president and vice president be chosen from a set of 30 candidates? 820 850 880 870       _____________________________________________________________________________________

Let G be a simple undirected planar graph on 10 vertices with 15edges. 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       _____________________________________________________________________________________

Which of the following pair is not congruent modulo 7? 10, 24 25, 56 -31, 11 -64, -15       _____________________________________________________________________________________

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       _____________________________________________________________________________________

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       _____________________________________________________________________________________

The length of Hamiltonian Path in a connected graph of n vertices is n–1 n n+1 n/2       _____________________________________________________________________________________

The number of leaf nodes in a complete binary tree of depth d is 2d 2d–1+1 2d+1+1 2d+1       _____________________________________________________________________________________

Four fair coins are tossed simultaneously. The probability that latest one head  and tail turn up is 1/16 1/8 7/8 15/16       _____________________________________________________________________________________

Find the number of relations from A = {cat, dog, rat} to B = {male , female} 64 6 32 15       _____________________________________________________________________________________

Find the number of ways to paint 12 offices so that 3 of them will be green, 2 of them pink, 2 of them yellow and the rest ones white. 55,440 1,66,320 4.790E+08 39,91,680       _____________________________________________________________________________________

The number of functions from an m element set to an n element set is: mn m + n nm m * n       _____________________________________________________________________________________

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       _____________________________________________________________________________________

Rank of the matrix Row1 [1,1 ] and Row2[0,0]  is  4 2 1 0       _____________________________________________________________________________________

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       _____________________________________________________________________________________

Let N = {1, 2, 3, ….} be ordered by divisibility, which of the following subset is totally ordered, (2, 6, 24) (3, 5, 15) (2, 9, 16) (4, 15, 30)       _____________________________________________________________________________________

Two dice are thrown simultaneously. The probability that the product of the two numbers  on the two disc is an even number, is 1/2 3/4 5/16 3/8       _____________________________________________________________________________________

McCabe’s cyclomatic metric V(G) of a graph G with n vertices, e edges and p connected component is e n e – n + 2p e – n + p       _____________________________________________________________________________________

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       _____________________________________________________________________________________

An undirected graph possesses an 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       _____________________________________________________________________________________

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       _____________________________________________________________________________________

A B C D       _____________________________________________________________________________________

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       _____________________________________________________________________________________

Number of elements in the power set P(S) of the set S={(Q),1(2,3)} 2 4 8 10       _____________________________________________________________________________________

A graph is a collection of  Row and columns Vertices and edges Equations None of these       _____________________________________________________________________________________

Hasse diagram are drawn Partially ordered sets Lattices Boolean algebra None of these       _____________________________________________________________________________________

Number of vertices of odd degree in a graph is Always even Always odd Either even or odd Always zero       _____________________________________________________________________________________

Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even. P only Q only Both P and Q Neither P nor Q       _____________________________________________________________________________________

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       _____________________________________________________________________________________

Cyclometric complexity of a flow graph G with n vertices and e edges is V(G) = e+n–2 V(G) = e–n+2 V(G) = e+n+2 V(G) = e–n–2       _____________________________________________________________________________________

The statement ( p^q) _ p is a Contingency Absurdity Tautology None of the above       _____________________________________________________________________________________

Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of distinct cycles of length 4 in G is equal to 15 30 90 360       _____________________________________________________________________________________

Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even. P only Q only Both P and Q Neither P nor Q       _____________________________________________________________________________________

Bag A contains 5 white and 2 black balls .Bag B contains 2 white and 3 black balls .if any one bag is chosen and a ball is taken out of it at random ,what is the probability the ball is black? 31/70 1/2 5/12 3/5