## Discrete Mathematics

Welcome to NTA NET ASPIRANT ACADEMY

NTA NET ASPIRANT ACADEMY is a training academy for College Lectures, Assistant Professor, Research Scholar and PG Students to make qualified for Assistant Professor & JRF in UGC NET / TNSET

NTA NET ASPIRANT ACADEMY is a training academy for College Lectures, Assistant Professor, Research Scholar and PG Students to make qualified for Assistant Professor & JRF in UGC NET / TNSET

Start

Congratulations - you have completed

*Discrete Mathematics*. You scored %%SCORE%% out of %%TOTAL%%. Your performance has been rated as %%RATING%%
Your answers are highlighted below.

Question 1 |

A tree has 2n vertices of degree 1, 3n vertices of degree 2, n vertices of degree 3. Determine the number of vertices and edges on tree.

**NTA NET December 2019**A | 12, 11 |

B | 11, 12 |

C | 16, 11 |

D | 9, 10 |

Question 2 |

If a graph (G) has no loops or parallel edges, and if the number of vertices (n) in the graph is n ≥ 3, then graph G is Hamiltonian if

(i) deg(v) ≥ n/3 for each vertex v

(ii) deg(v) + deg(w) ≥ n Whenever v and w are not connected by an edge.

(iii) E(G) ≥ 1/3(n-1) (n-2) + 2

Choose the correct answer from the code given below:

**NTA NET December 2018**(i) deg(v) ≥ n/3 for each vertex v

(ii) deg(v) + deg(w) ≥ n Whenever v and w are not connected by an edge.

(iii) E(G) ≥ 1/3(n-1) (n-2) + 2

Choose the correct answer from the code given below:

A | (i) and (iii) only |

B | (ii) only |

C | (ii) and (iii) only |

D | (iii) only |

Question 3 |

Consider the following properties:

A. Reflexive

B. Antisymmetric

C. Symmetric

Let A = {a,b,c,d,e,f,g} and R={(a,a),(b,b),(c,d),(c,g),(d,g),(e,e),(f,f),(g,g)} be a relation on A. Which of the following property is satisfied by the relation R?

**NTA NET JUNE 2020**A. Reflexive

B. Antisymmetric

C. Symmetric

Let A = {a,b,c,d,e,f,g} and R={(a,a),(b,b),(c,d),(c,g),(d,g),(e,e),(f,f),(g,g)} be a relation on A. Which of the following property is satisfied by the relation R?

A | Only A |

B | Only C |

C | Both A and B |

D | B and not A |

Question 4 |

A complete n - ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n - ary tree. If L = 41 and I = 10. What is the value of n?

**NTA NET JUNE 2020**A | 3 |

B | 4 |

C | 5 |

D | 6 |

Question 4 Explanation:

Question 5 |

E is the number of Edges in the graph and f is maximum flow in the graph. When the capacities are integers, the runtime of Ford - Fulberson algorithm is bounded by:

1. O(E*F)

2. O(E

3. O(E*F

4. O(E

**CBSE NET JULY 2018**1. O(E*F)

2. O(E

^{2}*f)3. O(E*F

^{2})4. O(E

^{2}*F^{2})A | 1 |

B | 2 |

C | 3 |

D | 4 |

Question 6 |

Which of the relations on {0, 1, 2, 3} is an equivalence relation?

**CBSE NET JULY 2018**A | { (0,0), (0,2), (2,0), (2,2), (2,3), (3,2), (3,3)} |

B | { (0,0), (1,1), (2,2), (3,3)} |

C | { (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0)} |

D | { (0,0), (0,2), (2,3), (1,1), (2,2)} |

Question 7 |

Consider the poset ({3,5,9,15,24,45},|).

Which of the following is correct for the given poset?

**NTA NET JUNE 2019**Which of the following is correct for the given poset?

A | There exist a greatest element and a least element |

B | There exists a greatest element but not a least element |

C | There exists a least element but not a greater element |

D | There does not exist a greater element and a least element |

Question 8 |

Match List - I with List - II:

Choose the correct answer from those given below:

**NTA NET JUNE 2019**List - I | List - II |
---|---|

A. p → q | (i) ¬(q → ¬p) |

B. p ⋁ q | (ii) p ⋀ →q |

C. p ⋀ q | (iii) ¬p → q |

D. ¬(p → q) | (iv) ¬p ⋁ q |

A | A - ii, B - iii, C - i, D - iv |

B | A - ii, B - i, C - iii, D - iv |

C | A - iv, B - i, C - iii, D - ii |

D | A - iv, B - iii, C - i, D - ii |

Question 9 |

What are the greatest lower bound (GLB ) and least upper bound (LUB) of the sets A={3,9,12} and B={1,2,4,5,10} if they exist in poset (z

^{+},/)?**NTA NET December 2019**A | A(GLB - 3, LUB - 36); B(GLB - 1, LUB - 20) |

B | A(GLB - 3, LUB - 12); B(GLB - 1, LUB - 10) |

C | A(GLB - 1, LUB - 36); B(GLB - 2, LUB - 20) |

D | A(GLB - 1, LUB - 12); B(GLB - 2, LUB - 10) |

Question 10 |

Let G be a simple undirected graph, TD be a DFS tree on G, and TB be the BFS tree on G. Consider the following statements.

In the light of the above statements, choose the correct answer from the options given below

**NTA NET JUNE 2020****Statement I:**No edge of G is a cross with respect to TD.**Statement II:**For every edge(u,V) of G, if u is at depth i and v is at depth j in TB then | i-j | = 1.In the light of the above statements, choose the correct answer from the options given below

A | Both Statement I and Statement II are true |

B | Both Statement I and Statement II are false |

C | Statement I is correct but Statement II is false. |

D | Statement I is incorrect but statement II is true. |

Question 10 Explanation:

Question 11 |

Match List - I with List - II:

Choose the correct option from those given below:

**NTA NET JUNE 2019**List - I | List - II |
---|---|

A. Prim's Algorithm | (i) O(V^{3}logV) |

B. Dijkstra's Algorithm | (ii) O(VE^{2}) |

C. Fastest all pair shortest path | (iii) O(ElogV) |

D. Edmonds - Karp Algorithm | (iv) O(V^{2}) |

A | A - ii, B - iv, C - i, D - iii |

B | A - iii, B - iv, C - i, D - ii |

C | A - ii, B - i, C - iv, D - iii |

D | A - iii, B - i, C - iv, D - ii |

Question 12 |

The Boolean expression

**A̅.B+A.B̅+A.B**is equivalent to**NTA NET December 2018**A | A̅.B |

B | A+B |

C | A.B |

D | A̅+B |

Question 13 |

Match List I with List II

Let R1 = {(1,1),(2,2),(3,3)} and R2={(1,1),(1,2),(1,3),(1,4)}

Choose the correct answer from the options given below

**NTA NET JUNE 2020**Let R1 = {(1,1),(2,2),(3,3)} and R2={(1,1),(1,2),(1,3),(1,4)}

List I | List II |
---|---|

A. R1 U R2 | (i) {(1,1),(1,2),(1,3),(1,4),(2,2),(3,3)} |

B. R1 - R2 | (ii) {(1,1)} |

C. R1 n R2 | (iii) {(1,2),(1,3),(1,4)} |

D. R2 - R1 | (iv) {(2,2),(3,3)} |

A | A - i, B - ii, C -iv, D=III |

B | A - i, B - iv, C -iii, D=II |

C | A - i, B - iii, C -ii, D -iv |

D | A- i; B-iv; C-ii, d iii |

Question 14 |

Which of the following statements is false about convex minimization problem?

**CBSE NET JULY 2018**A | If a local minimum exists, then it is a global minimum |

B | The set of all global minima is convex set |

C | The set of all global minima is concave set |

D | For each strictly convex function, if the function has a minimum, then the minimum is unique |

Question 15 |

A survey has been conducted on methods of commuter travel. Each respondent was asked to check Bus, Train or Automobile as a major method of travelling to work. More than one answer was permitted. The results reported were as follows:

Bus 30 people; Train 35 people; Automobile 100 people; Bus and Train 15 people; Bus and Automobile 15 people, Train and Automobile 20 people; and all the three methods 5 people. How many people completed the survey form?

Bus 30 people; Train 35 people; Automobile 100 people; Bus and Train 15 people; Bus and Automobile 15 people, Train and Automobile 20 people; and all the three methods 5 people. How many people completed the survey form?

**NTA NET December 2018**A | 120 |

B | 165 |

C | 160 |

D | 115 |

Question 16 |

Consider the following statements:

A. Any tree is 2 - colorable.

B. A graph G has no cycles of even length if it is bipartite.

C. A graph G is 2 - colorable if it is bipartite.

D. A graph G can be colored with d+1 colors if d is the maximum degree of any vertex in the graph G.

E. A graph G can be colored with O(log|v|) colors if it has O(|v|) edges.

Choose the correct answer from the options given below:

**NTA NET JUNE 2020**A. Any tree is 2 - colorable.

B. A graph G has no cycles of even length if it is bipartite.

C. A graph G is 2 - colorable if it is bipartite.

D. A graph G can be colored with d+1 colors if d is the maximum degree of any vertex in the graph G.

E. A graph G can be colored with O(log|v|) colors if it has O(|v|) edges.

Choose the correct answer from the options given below:

A | (C) and (E) are incorrect |

B | (B) and (C) are incorrect |

C | (B) and (E) are incorrect |

D | (A) and (D) are incorrect |

Question 17 |

In mathematical logic, which of the following are statements?

(i) There will be snow in January.

(ii) What is the time now?

(iii) Today is sunday

(iv) You must study Discrete Mathematics

Choose the correct answer from the code given below:

**NTA NET December 2018**(i) There will be snow in January.

(ii) What is the time now?

(iii) Today is sunday

(iv) You must study Discrete Mathematics

Choose the correct answer from the code given below:

A | (i) and (iii) |

B | (i) and (ii) |

C | (ii) and (iv) |

D | (iii) and (iv) |

Question 18 |

Consider the following statements:

Which of the statements is / are correct?

**NTA NET December 2019****S1:**If a group (G,*) is of order n, and aϵG is such that a^{m}= e for some integer m ≤ n, then m must divide n.**S2:**If a group (G,*) is of even order, then there must be an element aϵG such that a≠e and a*a=e.Which of the statements is / are correct?

A | Only S1 |

B | Only S2 |

C | Both S1 and S2 |

D | Neither S1 nor S2 |

Question 19 |

How many reflexive relations are there on a set with 4 elements?

**NTA NET December 2019**A | 2^4 |

B | 2^12 |

C | 4^2 |

D | 2 |

Question 19 Explanation:

Reflexive relations: A reflexive relation R on Set A is said to be Reflexive, if xRx for every element of x. The number of reflexive relation on an n element set is 2^(n^2)-n. 2^(4^2)-4
2^(16-4) = 2^12

Question 20 |

For which values of m and n does the complete bipartite graph K

_{m,n}have a Hmamilton circuit?**NTA NET JUNE 2019**A | m≠n, m,n≥2 |

B | m≠n, m,n≥3 |

C | m=n, m,n≥2 |

D | m=n, m,n≥3 |

Question 21 |

A basic feasible solution of an m x n transportation problem is said to be non - degenerate, if basic feasible solution contains exactly ____________ number of individual allocation in ________ positions.

**NTA NET December 2019**A | m+n+1, independent |

B | m+n-1, independent |

C | m+n-1, appropriate |

D | m-n+1, independent |

Question 22 |

How many ways are there to pack six copies of the same book into four identical boxes. Where a box can contain as many as six books?

**NTA NET JUNE 2020**A | 4 |

B | 6 |

C | 7 |

D | 9 |

Question 23 |

Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j if and only if either j=i+1 or j=3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is __________

**NTA NET JUNE 2020**A | 23 |

B | 99 |

C | 4 |

D | 7 |

Question 24 |

Consider the set of all possible five - card poker hands dealt fairly from a standard deck of fifty - two cards. How many atomic events are there in the joint probability distribution?

**CBSE NET JULY 2018**A | 2,598,960 |

B | 3,468,960 |

C | 3,958,590 |

D | 2,645,590 |

Question 25 |

How many cards must be selected from a standard deck of 52 cards to guarantee that atleast three hearts are present among them?

**NTA NET JUNE 2019**A | 9 |

B | 13 |

C | 17 |

D | 42 |

Question 26 |

In PERT / CPM, the merge event represents __________ of two or more events.

**NTA NET December 2018**A | Completion |

B | Beginning |

C | Splitting |

D | Joining |

Question 27 |

Match List I with List II and choose the correct answer from the code given below.

**NTA NET December 2018**List - I | List - II |
---|---|

A. Equivalence | (i) p ⇒ q |

B. Contrapositive | (ii) p ⇒ q: q ⇒ p |

C. Converse | (iii) p ⇒ q : ~q ⇒ ~p |

D. Implication | (iv) p ⇔ q |

A | A - i, B - ii, C - iii, D - iv |

B | A - ii, B - i, C - iii, D - iv |

C | A - iii, B - iv, C - ii, D - i |

D | A - iv, B - iii, C - ii, D - i |

Question 28 |

Consider a vocabulary with only four propositions A, B, C and D. How many models are there for the following sentence? B ⋁ C

**CBSE NET JULY 2018**A | 10 |

B | 12 |

C | 15 |

D | 10 |

Question 29 |

Consider the following two sentences:

(A) The planning graph data structure can be used to give a better heuristic for a planning problem.

(B) Dropping negative effects from every action schema in a planning problem results in a relaxed problem.

Which of the following is correct with respect to the above sentences?

**CBSE NET JULY 2018**(A) The planning graph data structure can be used to give a better heuristic for a planning problem.

(B) Dropping negative effects from every action schema in a planning problem results in a relaxed problem.

Which of the following is correct with respect to the above sentences?

A | Both sentence (A) and sentence (B) are false. |

B | Both sentence (A) and sentence (B) are true. |

C | sentence (A) is true but sentence (B) is false. |

D | sentence (A) is false but sentence (B) is true. |

Question 30 |

Which of the following statements are true?

(i) Every logic network is equivalent to one using just NAND gates or just NOR gates.

(ii) Boolean expressions and logic networks correspond to labelled acyclic digraphs.

(iii) No two Boolean algebras with n atoms are isomorphic.

(iv) N0n - zero elements of finite Boolean algebras are not uniquely expressible as joins of atoms.

Choose the correct answer from the code given below:

**NTA NET December 2018**(i) Every logic network is equivalent to one using just NAND gates or just NOR gates.

(ii) Boolean expressions and logic networks correspond to labelled acyclic digraphs.

(iii) No two Boolean algebras with n atoms are isomorphic.

(iv) N0n - zero elements of finite Boolean algebras are not uniquely expressible as joins of atoms.

Choose the correct answer from the code given below:

A | (i) and (iv) only |

B | (i), (ii) and (iii) only |

C | (i) and (ii) only |

D | (ii), (iii) and (iv) only |

Question 31 |

Consider the following statements with respect to duality in LPP:

A. The final simplex table giving optimal solution of the primal also contains optimal solution of its dual in itself.

B. If either the primal or the dual problem has a finite optimal solution, then the other problem also has a finite optimal solution

C. If either problem has an unbounded optimum solution, then the other problem has no feasible solution at all.

Which of the statements is / are correct?

**NTA NET December 2019**A. The final simplex table giving optimal solution of the primal also contains optimal solution of its dual in itself.

B. If either the primal or the dual problem has a finite optimal solution, then the other problem also has a finite optimal solution

C. If either problem has an unbounded optimum solution, then the other problem has no feasible solution at all.

Which of the statements is / are correct?

A | (A) and (B) only |

B | (A) and (C) only |

C | (B) and (C) only |

D | (A), (B) and (C) only |

Question 32 |

A clique in an undirected graph G = {V,E}; is a subset V

1. If (u,v) ϵ E then u ϵ V

2. If (u,v) ϵ E then u ϵ V

3. Each pair of vertices in V

4. All pairs of vertices in V

^{'}⊆ V of vertices, such that**NTA NET December 2019**1. If (u,v) ϵ E then u ϵ V

^{'}and v ϵ V^{'}2. If (u,v) ϵ E then u ϵ V

^{'}or v ϵ V^{'}3. Each pair of vertices in V

^{'}is connected by an edge.4. All pairs of vertices in V

^{'}are not connected by an edge.A | 1 |

B | 2 |

C | 3 |

D | 4 |

Question 33 |

Let P be the set of all people. Let R be a binary relation on P such that (a,b) is in R if a is a brother of b. Is R symmetric, transitive, an equivalence relation, a partial order relation?

**NTA NET December 2019**A | NO,NO,NO,NO |

B | NO,NO,YES,NO |

C | NO,YES,NO,NO |

D | NO,YES,YES,NO |

Question 34 |

How many ways are there to place 8 indistinguishable balls into four distinguishable bins?

**NTA NET JUNE 2019**A | 70 |

B | 165 |

C | 8C4 |

D | 8P4 |

Question 35 |

Consider a weighted graph. The current shortest distance from source S to node x is represented by d[x]. Let d[v]=29, d[u]=15, w[u,v]=12. What is the updated value of d[v] based on current information

**NTA NET December 2019**A | 29 |

B | 27 |

C | 23 |

D | 17 |

Question 36 |

A box contains six red balls and four green balls. Four balls are selected at random from the box. What is the probability that two of the selected balls will be red and two will be green?

**NTA NET December 2018**A | 1/14 |

B | 3/7 |

C | 1/35 |

D | 1/9 |

Question 37 |

Which of the following is principal conjunctive normal form for [(p ⋁ q) ⋀ ¬p → ¬q]?

**NTA NET JUNE 2019**A | p ⋁¬q |

B | p ⋁ q |

C | ¬p ⋁ q |

D | ¬p ⋁¬q |

Once you are finished, click the button below. Any items you have not completed will be marked incorrect.
Get Results

There are 37 questions to complete.

You have completed

questions

question

Your score is

Correct

Wrong

Partial-Credit

You have not finished your quiz. If you leave this page, your progress will be lost.

Correct Answer

You Selected

Not Attempted

Final Score on Quiz

Attempted Questions Correct

Attempted Questions Wrong

Questions Not Attempted

Total Questions on Quiz

Question Details

Results

Date

Score

Hint

Time allowed

minutes

seconds

Time used

Answer Choice(s) Selected

Question Text

All done

Need more practice!

Keep trying!

Not bad!

Good work!

Perfect!