Free Printable discrete mathematics

1.

The number of edges in a complete graph

with ‘n’ vertices is equal to:

a)

n(n-1)

b)

n(n-1)/2

c)

n^2

d)

2n-1

2.

A relation R is from set A to B and a relation S from set B to C. Then is from_____

a)

Set C to A

b)

Set A to C

c)

Does not exist

d)

None of these

3.

What is the identity element In the group G = {2, 4, 6, 8) under multiplication modulo 10?

a)

5

b)

6

c)

9

d)

12

4.

The function $f:R^+→R^+$ , $f(x)=x^3,g:R^+→R^+,g(x)=x^{1/3}\ then\ (fog)(x)=$

a)

$x^3$

b)

$1/x$

c)

$∛x$

d)

x

5.

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

a)

(i) and (ii)

b)

(i) and (iii)

c)

(i) and (iv)

d)

(ii) and (iii)

6.

The number of binary operation on set {1,2} is____

a)

8

b)

16

c)

2

d)

4

7.

Which sentence is true?

a)

Set of all matrices forms a group under multiplication

b)

Set of all rational negative numbers forms a group under multiplication

c)

Set of all non-singular matrices forms a group under multiplication

d)

Both (b) and (c)

8.

$The\ function\ f:R→R,\ f(x)=5x+7\ then\$ function f is

a)

One one and onto

b)

One one but not onto

c)

Onto but not one one

d)

Neither one one nor onto

9.

The complete graph with four vertices has k edges where k is:

a)

3

b)

4

c)

5

d)

6

10.

The number of onto function from set $\left\{1,2,3,4\right\}to\left\{3,4,7\right\}$ is

a)

18

b)

36

c)

64

d)

none

11.

What is an inverse of – i in the multiplicative group if {1, – 1, i , – i} is?

a)

1

b)

-1

c)

i

d)

-i

12.

The function $f:R→R,f(x)=(x-1)(x-2)(x-3)$ then f is

a)

One one but not onto

b)

Onto but not one one

c)

One one and onto

d)

Neither one one nor onto

13.

For a complete graph with N vertices, the total number of spanning trees is given by:

a)

2N-1

b)

N^(N-1)

c)

N^(N-2)

d)

2N+1

14.

If set A contain 4 element and

set B contains 5 elements then AxB contains _____ elements.

a)

4⁵

b)

5⁴

c)

20

d)

9

15.

The monoid is a?

a)

a non-abelian group

b)

groupoid

c)

A group

d)

a commutative group

16.

For any non empty sets A and B if $A⊂B\ then\ A∩B=$

a)

A

b)

B

c)

$\phi$

d)

none

17.

Consider the graph given above. The two distinct sets of vertices, which make the graph bipartite are:

a)

(v1, v4, v6);

(v2, v3, v5, v7, v8)

b)

(v1, v7, v8);

(v2, v3, v5, v6)

c)

(v1, v4, v6, v7);

(v2, v3, v5, v8)

d)

(v1, v4, v6, v7, v8);

(v2, v3, v5)

18.

For any non empty sets A and B if $A⊂B\ then\ A∪B=$

a)

A

b)

B

c)

$\phi$

d)

none

19.

A non empty set A is termed as an algebraic structure ________

A with respect to binary operation *

B with respect to ternary operation ?

C with respect to binary operation +

D with respect to unary operation –

a)

option A

b)

option B

c)

option C

d)

option D

20.

$IfA=∅\ and\ B=\left\{1,2,3,4\right\}\ then\ A×B=$

a)

B

b)

$∅$

c)

A U B

d)

$A\cap B$

21.

3 A group (M,*) is said to be abelian if ___________

A) (x+y)=(y+x)

B) (x*y)=(y*x)

C) (x+y)=x

D) (y*x)=(x+y)

a)

OPTION A

b)

OPTION B

c)

OPTION C

d)

OPTION D

22.

Which of the following is a contradiction?

a)

$\left((p⋀q)⋀∼(p⋁q\right)$

b)

$p⋁(∼p⋀q)$

c)

$(p⇒q)⇒p$

d)

$~(p⋀q)⋁q$

23.

In preorder traversal of a binary tree the second step is

a)

traverse the

right subtree

b)

traverse the

left subtree

c)

traverse

right subtree and visit the root

d)

visit the

root

24.

How many relations are there on a set with 5 elements?

a)

2⁵

b)

5²

c)

2²⁵

d)

5

25.

What is the minimum height for a binary search tree with 60 nodes?

a)

1

b)

3

c)

4

d)

2

26.

Let\ R=\left\{(1,2),(3,4)\right\}

be a relation on the set {1,2,3,4} then

a)

R is reflexive

b)

R is symmetric

c)

R is an equivalence relation

d)

R is Transitive

27.

Consider a complete bipartite graph km,n. For which values of m and n does this, complete graph have a Hamilton circuit ?

a)

m=3, n=2

b)

m=2, n=3

c)

m=n≥2

d)

m=n≥3

28.

In the poset $(P(S),⊆)$ The least element is

a)

$\phi$

b)

S

c)

P(S)

d)

not exist

29.

The inorder and preorder traversal of a binary tree are

d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:

a)

d e b f g c a

b)

e d b g f c a

c)

e d b f g c a

d)

d e f g b c a

30.

$In\ the\ poset\ (Z^+,|)$ In the poset which of the following pairs of integers are coparable?

a)

5,7

b)

1,4

c)

2,5

d)

13,5

31.

19 The set of integers Z with the binary operation "*" defined as a*b =a +b+ 1 for a, b ∈ Z, is a group. The identity element of this group is

a)

0

b)

1

c)

-1

d)

12

32.

Consider the relation R of divisibility on the set of Z of integers. Then the relation R is

a)

Reflexive and anti symmetric

b)

Reflexive but not anti symmetric

c)

anti symmetric but not

reflexive

d)

Neither reflexive nor anti symmetric

33.

Data Structure: Preorder and in order of a tree is given by

Preorder ----- A B D H E C F I G J K

Inorder -------- D H B E A I F C J G K

What will be the postorder?

a)

H D E B I F J K G C A

b)

H D E B F I J K G C A

c)

H D E B I F J K C G A

d)

None

34.

$LetX=\left\{2,3,6,12,24,48\right\}$ be ordered by divisibility. Then the number of edges in the Hasse diagram of $(X,|)\ is$

a)

3

b)

4

c)

5

d)

6

35.

A graph G is called a ..... if it is a

connected acyclic graph

a)

Cyclic

graph

b)

Regular

graph

c)

Tree

d)

Not a

graph

36.

Let S = {2,3, 4, 16} be ordered by divisibility. Then the maximal

elements are

a)

3,16

b)

4,16

c)

16,3

d)

4,3

37.

If two cycle graphs Gm and Gn are joined

together with a vertex, the number of spanning trees in the new graph is

______

a)

m+n-1

b)

m-n

c)

m*n

d)

m*n+1

38.

Consider the Poset $(A=1,2,3,4,6,9,12,18,36,|)$ Then the greatest lower bound and the least upper bound of subset {4,6,9} are

a)

18,2

b)

12,3

c)

9,4

d)

1,36

39.

An undirected graph possesses an eulerian

circuit if and only if it is connected and its vertices are An undirected graph possesses an eulerian circuit if and

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

40.

Consider the subset S= {2, 3, 6} of the poset $(1,2,3,4,5,6,|)$ Then the upper bounds and lower bounds of S are respectively

a)

6,2

b)

6,1

c)

6,3

d)

6 and 1,2

41.

How many edges are there in a complete graph

of order 9?

a)

35

b)

36

c)

45

d)

19

42.

Which of the following expression are equal to $p\ ⇒q$ ?

a)

$q⇒p$

b)

$∼p⇒∼q$

c)

$(~p⋀(p⋁q))⇒q$

d)

$~\ q⇒∼p$

43.

The number of edges from the root to the node

is called __________ of the tree

a)

Height

b)

Depth

c)

Length

d)

Width

44.

If A and B are two sets and $A∩B=A∪B$ then

a)

$A=∅$

b)

A=B

c)

$B=∅$

d)

none

45.

Length of the walk of a graph is

a)

The

number of vertices in walk W

b)

The

number of edges in walk W

c)

Total

number of edges in a graph

d)

Total number

of vertices in a graph

46.

If A and B are two sets, then $A∩〖(A∪B)〗^c=$

a)

$\phi$

b)

A`

c)

B

d)

none

47.

What is a full binary tree?

a)

Each node

has exactly zero or two children

b)

Each node

has exactly two children

c)

All the

leaves are at the same level

d)

Each node

has exactly one or two children

48.

A relation R is defined on the set of positive integers as if $2a+b≤7.$ The relation R is

a)

reflexive

b)

transitive

c)

symmetric

d)

None of these.

49.

Kruskal’s algorithm is used to ______

a)

find minimum

spanning tree

b)

find single

source shortest path

c)

find all

pair shortest path algorithm

d)

traverse

the graph

50.

Which of the following is an ordered collection of objects?

a)

Relation

b)

Function

c)

Set

d)

Proposition

51.

A graph with one vertex and no edges is

a)

Multigraph

b)

digraph

c)

Isolated

graph

d)

Trivial

graph

52.

Two sets are called disjoint if there _____is a empty set.

a)

Union

b)

Difference

c)

Intersection

d)

Compliment

53.

Consider the given graph, What is the weight of the minimum spanning tree using the Kruskal’s algorithm?

a)

24

b)

23

c)

15

d)

19

54.

The compliment of the set S is

(Where U is an Universal set and A is any set)

a)

S - A

b)

U - S

c)

S - U

d)

A - S

55.

Which of the following is true?

a)

Prim’s

algorithm can also be used for disconnected graphs

b)

Kruskal’s

algorithm can also run on the disconnected graphs

c)

Prim’s

algorithm is simpler than Kruskal’s algorithm

d)

In Kruskal’s

sort edges are added to MST in decreasing order of their weights

56.

The domain of $1/√(9-x^2)$ is

a)

(-3,3)

b)

(-3,3]

c)

[-3,3]

d)

None of these

57.

In an undirected graph the number of nodes

with odd degree must be

a)

Zero

b)

Odd

c)

Prime

d)

Even

58.

If A = {1, 2, 3, 4, 5} then the relation R={(4, 5)} in A is

a)

Symmetric and transitive only

b)

Symmetric only

c)

Transitive

only

d)

Not transitive

59.

Consider the given graph.

What is the weight of the minimum spanning tree using the Prim’s algorithm,starting from vertex a?

a)

23

b)

28

c)

27

d)

11

60.

$If\ A\ ⊂\ B\ then\ A^c∩\ B=$

a)

A - B

b)

B - A

c)

$\phi$

d)

A U B

discrete mathematics

Total questions: 60

Worksheet time: 2hrs 0mins

Similar Resources on Wayground