UGC NET · PAPER 2
UGC NET Paper 2 Computer Science – Unit 1: Discrete Structures and Optimization PYQ (December 2022 Shift 2)
Q1. The negation of "Some students like hockey" is:
- Some students dislike hockey
- Every student dislikes hockey
- Every student likes hockey
- All students like hockey
Q2. A relation R is defined on ordered pairs of integers as (x, y) R (u, v) if x < u and y > v. Then R is
- Neither a partial order nor an equivalence relation
- A partial order but not a total order
- A total order
- An equivalence relation
Q3. Suppose you are married and you and your partner attend a party with three other married couples. Several handshakes took place. No one shook hands with himself (or herself) or with their partner, and no one shook hands with the same person more than once. After all handshaking was completed, you asked each person, including your partner, how many hands they had shaken. Each person gave a different answer. How many hands did your spouse shake?
- 1
- 2
- 3
- 4
Q28. Consider the following graph with vertices A, B, C, D and edges:
A – B, B – C, A – D, B – D, C – D
(A, B, C lie in a row; D is below and joined to all three.)
How many spanning trees can be found?
A – B, B – C, A – D, B – D, C – D
(A, B, C lie in a row; D is below and joined to all three.)
How many spanning trees can be found?
- 10
- 5
- 9
- 8
Q41. Consider the following statements:
P: There exists no simple, undirected and connected graph with 80 vertices and 77 edges.
Q: All vertices of an Euler graph are of even degree.
R: Every simple, undirected, connected and acyclic graph with 50 vertices has at least two vertices of degree one.
S: There exists a bipartite graph with more than ten vertices which is 2-colourable.
What is the number of correct statements?
P: There exists no simple, undirected and connected graph with 80 vertices and 77 edges.
Q: All vertices of an Euler graph are of even degree.
R: Every simple, undirected, connected and acyclic graph with 50 vertices has at least two vertices of degree one.
S: There exists a bipartite graph with more than ten vertices which is 2-colourable.
What is the number of correct statements?
- 1
- 2
- 3
- 4
Q42. Consider the following statements:
A. There exists a Boolean algebra with 5 elements.
B. Every element of a Boolean algebra has a unique complement.
C. If a lattice L is a Boolean algebra then L is not relatively complemented.
D. The direct product of two Boolean algebras is also a Boolean algebra.
Choose the correct answer about the four statements.
A. There exists a Boolean algebra with 5 elements.
B. Every element of a Boolean algebra has a unique complement.
C. If a lattice L is a Boolean algebra then L is not relatively complemented.
D. The direct product of two Boolean algebras is also a Boolean algebra.
Choose the correct answer about the four statements.
- Only A and D are correct
- Only B and D are correct
- All statements are NOT correct
- All statements are correct
Q66. Match List I with List II.
Choose the correct answer from the options given below:
Choose the correct answer from the options given below:
| List I | List II |
|---|---|
| a. Planar graph | I. Probabilistic model |
| b. Bipartite graph | II. Deterministic model |
| c. PERT | III. 4-colourable |
| d. CPM | IV. 2-colourable |
- a-IV, b-III, c-I, d-II
- a-III, b-IV, c-II, d-I
- a-II, b-IV, c-I, d-III
- a-III, b-IV, c-I, d-II
Q76. Consider the statements:
I. There does not exist a polynomial-time algorithm to solve integer linear programming problems.
II. The main focus of PERT is 'minimising time'.
Choose the correct option about statements I and II.
I. There does not exist a polynomial-time algorithm to solve integer linear programming problems.
II. The main focus of PERT is 'minimising time'.
Choose the correct option about statements I and II.
- I is true; II is true
- I is true; II is false
- I is false; II is true
- I is false; II is false
Q86. Four persons P, Q, R and S are in custody and one of them has committed a crime. They say:
P: Q did it.
Q: S did it.
R: I did not do it.
S: Q lied.
If exactly one of the statements is false, who is guilty?
P: Q did it.
Q: S did it.
R: I did not do it.
S: Q lied.
If exactly one of the statements is false, who is guilty?
- P
- Q
- R
- S