Go back to UGC NET COMUPTER SCIENCE

Expected Questions with Solutions

Unit – 1 : Discrete Structures and Optimization

---

A. Mathematical Logic (Propositional & Predicate Logic, Inference)

1. ¬∃x Q(x) is equivalent to:
   (1) ∃x ¬Q(x)
   (2) ∀x ¬Q(x)
   (3) ¬∀x ¬Q(x)
   (4) ∀x Q(x)
   Answer: (2)
   Explanation: Negation of an existential becomes universal negation: ¬∃x Q(x) ≡ ∀x ¬Q(x).

2. From (P → Q) ∧ (R → S) and P ∨ R, what follows (Y)?
   (1) P ∨ R
   (2) P ∨ S
   (3) Q ∨ R
   (4) Q ∨ S
   Answer: (4)
   Explanation: If P then Q; if R then S. From P∨R we derive Q∨S.

3. “Agra and Gwalior are both in India.” Student wrote: In(Agra,India) ∨ In(Gwalior,India). This is:
   (1) Syntactically valid but wrong meaning
   (2) Syntactically valid and correct meaning
   (3) Syntactically invalid but correct meaning
   (4) Invalid and wrong meaning
   Answer: (1)
   Explanation: Sentence requires AND; OR changes meaning. Syntax is valid but semantics wrong.

4. Knowledge base: ∃x AsHighAs(x, Everest). After existential instantiation we get
   (a) AsHighAs(Everest, Everest)
   (b) AsHighAs(Kilimanjaro, Everest)
   Options:
   (1) Both (a) and (b) are sound conclusions.
   (2) Both (a) and (b) are unsound conclusions.
   (3) (a) is sound but (b) is unsound.
   (4) (a) is unsound but (b) is sound.
   Answer: (2) — (In some papers the key differs; see explanation below.)
   Short explanation: Existential instantiation must introduce a new arbitrary constant; substituting existing named constants (Everest, Kilimanjaro) is unsound.

5. Given FOL: ((R ∨ Q) ∧ (P ∨ Q)). Which is equivalent?
   Options show same expression repeated in the paper; all choices are identical.
   Answer: Any option (they are identical)
   Explanation: The options are identical textually; the expression stands as given.

---

B. Sets & Relations (Set operations, Equivalence, Partial Orders)

6. If Aᵢ = {−i, …, −1, 0, 1, …, i} for i ≥ 1, then ⋃_{i=1}^{∞} Aᵢ =
   (1) Z
   (2) Q
   (3) R
   (4) C
   Answer: (1) Z
   Explanation: As i → ∞ the union includes all integers.

7. Which of the following relations on {0,1,2,3} is an equivalence relation?
   (1) {(0,0),(0,2),(2,0),(2,2),(2,3),(3,2),(3,3)}
   (2) {(0,0),(1,1),(2,2),(3,3)}
   (3) {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0)}
   (4) {(0,0),(0,2),(2,3),(1,1),(2,2)}
   Answer: (2)
   Explanation: Identity relation has reflexivity, symmetry, transitivity.

8. Which relation on functions f,g: Z→Z is an equivalence relation?
   (1) f(x) − g(x) = 1
   (2) f(0)=g(0) OR f(1)=g(1)
   (3) f(0)=g(1) AND f(1)=g(0)
   (4) f(x) − g(x) = k (for some integer k)
   Answer: (4)
   Explanation: Difference-by-constant is reflexive (k=0), symmetric (negate), transitive (sum).

9. Which is true?
   (1) (Z, ≤) is not totally ordered
   (2) ⊆ is a partial order on P(S)
   (3) (Z, ≠) is a poset
   (4) Directed graph is not a partial order
   Answer: (2)
   Explanation: Subset relation is reflexive, antisymmetric and transitive.

10. Match:
    (a) ∀x∀y (f(x)=f(y) → x=y)
    (b) ∀y ∃x (f(x)=y)
    (c) ∀x f(x)=k
    (i) Constant (ii) Injective (iii) Surjective
    Codes: (1) (i)(ii)(iii) (2) (iii)(ii)(i) (3) (ii)(i)(iii) (4) (ii)(iii)(i)
    Answer: (4)
    Explanation: (a) injective, (b) surjective, (c) constant.

---

C. Counting, Pigeonhole, Permutations & Combinations, Induction

11. Consider A = {1,2,…,1000}. How many members are divisible by 3 or 5 or both?
    (A) 533 (B) 599 (C) 467 (D) 66
    Answer: (paper keys vary — mathematically = C) (C) 467; several uploaded keys show (A) 533 (answer-key discrepancy).
    Explanation: Using inclusion–exclusion: ⌊1000/3⌋+⌊1000/5⌋−⌊1000/15⌋ = 333+200−66 = 467.

12. How many multiples of 6 between 0 and 100, and between −6 and 34?
    (1) 16 and 6
    (2) 17 and 6
    (3) 17 and 7
    (4) 16 and 7
    Answer: (3)
    Explanation: Multiples of 6 from 0 to 100: 0,6,…,96 → 17 numbers (including 0). From −6 to 34: −6,0,6,…,30 → 7 numbers.

13. Number of atomic events (five-card poker hands)?
    (1) 2,598,960 (2) 3,468,960 (3) 3,958,590 (4) 2,645,590
    Answer: (1)
    Explanation: C(52,5) = 2,598,960.

14. Number of ways to arrange letters of “DISCRETE”:
    (1) 8! (2) 8!/2! (3) 8!/3! (4) 7!
    Answer: (2)
    Explanation: 8 letters with E repeated twice → 8!/2!.

15. Number of permutations of 5 distinct objects taken 3 at a time:
    (A) 60 (B) 10 (C) 125 (D) 5
    Answer: (A) 60
    Explanation: P(5,3)=5×4×3=60.

16. Pigeonhole: 13 pigeons into 12 holes ⇒ some hole has at least how many pigeons?
    (A)1 (B)2 (C)13 (D)12
    Answer: (B) 2
    Explanation: Ceiling(13/12)=2.

17. Probability: rolling two dice, P(sum=7):
    (1) 1/6 (2) 1/9 (3) 1/12 (4) 1/36
    Answer: (1) 1/6
    Explanation: 6 favourable / 36 total.

18. Flipping coin 10 times: number of atomic events:
    (1) 2⁵ (2) 2¹⁰ (3) 10! (4) 100
    Answer: (2) 2¹⁰
    Explanation: 2 outcomes per flip → 2¹⁰ sequences.

---

D. Probability & Bayes

19. Selecting k uniformly from {1..1,000,000} a million times: P(k=1 appears at least once):
    (A) 0.5 (B) 0.704 (C) 0.632121 (D) 0.68
    Answer: (C) ≈ 0.632121
    Explanation: P(not 1 each trial) = 1 − 1/1e6; (1 − 1/1e6)^{1e6} ≈ e^{−1}; 1 − e^{−1} ≈ 0.632121.

20. If A and B independent with P(A)=0.3, P(B)=0.4, then P(A∪B)=
    (A) 0.12 (B) 0.58 (C) 0.7 (D) 0.3
    Answer: (B) 0.58
    Explanation: P(A)+P(B)−P(A)P(B)=0.3+0.4−0.12=0.58.

21. Bayes formula: P(H|E)= ?
    (A) P(E|H)P(E)/P(H)
    (B) P(E|H)P(H)/P(E)
    (C) P(H)P(E)
    (D) P(E)/P(H)
    Answer: (B)
    Explanation: Standard Bayes’ rule.

22. If A,B,C are events, which is true?
    (1) P(A∪B) = P(A)+P(B)−P(AB)
    (2) P(A∪B∪C) = P(A)+P(B)+P(C)
    (3) P(A∪B) ≥ P(A)
    (4) P(A∪B) ≤ P(A)
    Answer: (3)
    Explanation: Union never decreases probability.

---

E. Graph Theory & Trees

23. A tree with two vertices degree 4, one vertex degree 3, one vertex degree 2, rest degree 1 → total vertices?
    (A)5 (B)n−3 (C)20 (D)11
    Answer: (D) 11
    Explanation: Let number of leaves = x, n = x+4; sum degrees = 13 + x = 2(n−1)=2x+6 → x=7 → n=11.

24. This graph is a:
    (A) Complete Graph (B) Bipartite Graph (C) Hamiltonian Graph (D) All of the above
    Answer: (D)
    Explanation: Given graph (in paper) satisfies all three properties.

25. Hamiltonian graph G (|V|=n≥3). Which is true?
    (1) deg(v) ≥ n/2 for each v
    (2) |E| ≥ ½ (n−1)(n−2) + 2
    (3) deg(v)+deg(w) ≥ n whenever v and w not adjacent
    (4) All of the above
    Answer: (4)
    Explanation: These are sufficient conditions referenced in the paper.

26. Strict (full) binary tree with 19 leaves has how many nodes?
    (1) cannot have more than 37 nodes
    (2) has exactly 37 nodes
    (3) has exactly 35 nodes
    (4) cannot have more than 35 nodes
    Answer: (2) 37
    Explanation: In full binary tree: number nodes = 2L − 1.

27. Shortest path algorithm allowing negative edges (no negative cycles):
    (1) Dijkstra (2) Bellman–Ford (3) Prim (4) Floyd only
    Answer: (2) Bellman–Ford
    Explanation: Bellman–Ford handles negative edge weights.

28. Chromatic number of a cycle C_n is:
    (1) 2 (if n even), 3 (if n odd)
    (2) 3 (if n even), 2 (if n odd)
    (3) Always 2
    (4) Always 3
    Answer: (1)
    Explanation: Even cycles are 2-colorable, odd cycles need 3 colors.

---

F. Boolean Algebra & Automata

29. Consensus theorem identity:
    (A) XY + X′Z + YZ = XY + X′Z
    (B) X + X′Y = X + Y
    (C) XX′ = 0
    (D) X + X′ = 1
    Answer: (A)
    Explanation: Consensus term YZ redundant and can be removed.

30. Simplify (A + B)(A + B′):
    (1) A (2) B (3) AB (4) A′
    Answer: (1) A
    Explanation: Use absorption law: (A+B)(A+B′)=A.

31. Order of algorithm determining whether a Boolean function of n variables outputs 1 (brute force):
    (1) Logarithmic (2) Linear (3) Quadratic (4) Exponential
    Answer: (4) Exponential
    Explanation: Exhaustive checking needs O(2^n) evaluations.

---

G. Group Theory & Coding (selected Unit-1 items present)

32. Which structure is always commutative?
    (A) Any group (B) Abelian group (C) Semigroup (D) Non-abelian group
    Answer: (B) Abelian group
    Explanation: Abelian = group where operation commutes.

33. Order of a permutation expressed as disjoint cycles equals:
    (A) sum of cycle lengths (B) product of cycle lengths (C) LCM of cycle lengths (D) minimum cycle length
    Answer: (C) LCM
    Explanation: The permutation repeats after LCM of cycle lengths.

34. Hamming bound uses which RHS term for q-ary n-length code:
    Options: (1) q^n (2) q^t (3) q^{−n} (4) q^{−t}
    Answer: (1) q^n
    Explanation: Sphere-packing bound compares sum of spheres to q^n.

---

H. Optimization (LPP, Transportation, Assignment, PERT/CPM)

35. Given LPP with constraints (in paper) — which is true?
    (1) Solution x₁=100, x₂=0, x₃=0
    (2) Unbounded solution
    (3) No solution
    (4) Solution x₁=50, x₂=70, x₃=60
    Answer: (3) No solution (as per paper key)
    Explanation: The constraints as given are inconsistent → infeasible.

36. Transportation degeneracy occurs when number of basic variables <
    (A) m + n (B) m + n − 1 (C) mn (D) m − n
    Answer: (B) m + n − 1
    Explanation: Basic feasible solution should have m+n−1 basics; fewer indicates degeneracy.

37. A basic feasible solution of LP corresponds to:
    (A) any interior point (B) a vertex of polytope (C) centroid (D) none
    Answer: (B) a vertex (extreme point)
    Explanation: Basic feasible solutions map to vertices of feasible region.

38. PERT uses which distribution for activity times?
    (1) Exponential (2) Normal (3) Beta (4) Poisson
    Answer: (3) Beta
    Explanation: PERT models activity time with Beta distribution (approx. using optimistic, pessimistic, most likely).

39. In PERT/CPM the critical path is:
    (1) minimum duration path (2) maximum duration path (3) any path with slack (4) both (2) and (3)
    Answer: (2) maximum duration path (equivalently zero slack)
    Explanation: Critical path has longest duration; activities on it have zero total float.

40. Which of the following is FALSE about convex minimization?
    (1) Local minimum ⇒ global minimum
    (2) Global minima set is convex
    (3) Global minima set is concave
    (4) Strictly convex function has unique minimum
    Answer: (3) (false)
    Explanation: Global minima set of convex functions is convex (not concave).

MORE PRACTICE CUM EXPECTED QUESTIONS

Q41.

If $A,B,C$ are events in a probability space, then which of the following is TRUE?
(1) $P(A\cup B)=P(A)+P(B)-P(AB)$
(2) $P(A\cup B\cup C)=P(A)+P(B)+P(C)$
(3) $P(A\cup B)\ge P(A)$
(4) $P(A\cup B)\le P(A)$

Answer: (3)
Explanation: A union can never reduce probability: $P(A\cup B)\ge P(A)$

---

Q42.

The number of atomic events in the sample space when a fair coin is flipped 10 times is:
(1) $2^5$
(2) $2^{10}$
(3) $10!$
(4) 100

Answer: (2)
Explanation: Each flip has 2 outcomes → $2^{10}$ sequences.

---

Q43.

A strictly binary tree with L leaves has
(1) $2L+1$ nodes
(2) $2L-1$ nodes
(3) $L-1$ nodes
(4) $2L$ nodes

Answer: (2)
Explanation: Full binary tree nodes = $2L-1$.

---

Q44.

If a function $f$ is injective, then
(1) $f(x)=f(y)\Rightarrow x=y$
(2) $f(x)=k$ for all $x$
(3) $f$ is onto
(4) $f(x)$ never repeats

Answer: (1)
Explanation: Injective means one-to-one.

---

Q45.

If a relation R is reflexive and symmetric but not transitive, then R is
(1) Equivalence relation
(2) Partial order
(3) Not an equivalence relation
(4) Total order

Answer: (3)
Explanation: Equivalence requires all 3; missing transitivity → not equivalence.

---

Q46.

For a universal set $U$ and subset $A\subseteq U$:
(1) $A^{\mathrm{\prime }}\cup A=U$
(2) $A^{\mathrm{\prime }}\cap A=U$
(3) $(A^{\mathrm{\prime }}{)}^{\mathrm{\prime }}=\mathrm{\varnothing }$
(4) $A^{\mathrm{\prime }}\subseteq A$

Answer: (1)
Explanation: A set union its complement gives the universal set.

---

Q47.

Number of arrangements of the letters of “DISCRETE”:
(1) 8!
(2) 8!/2!
(3) 8!/3!
(4) 7!

Answer: (2)
Explanation: “E” is repeated twice → divide by 2!.

---

Q48.

If a fair die is rolled twice, the probability that the sum is 7 is
(1) 1/6
(2) 1/9
(3) 1/12
(4) 1/36

Answer: (1)
Explanation: 6 favourable outcomes → 6/36 = 1/6.

---

Q49.

The chromatic number of the cycle graph $C_n$ is:
(1) 2 if n even; 3 if n odd
(2) 3 if n even; 2 if n odd
(3) Always 2
(4) Always 3

Answer: (1)
Explanation: Even cycle: bipartite (2 colors). Odd cycle: needs 3.

---

Q50.

A relation R on A is antisymmetric if
(1) $aRb\text{ and }bRa\Rightarrow a=b$
(2) $aRb\Rightarrow bRa$
(3) R is neither symmetric nor reflexive
(4) $aRb\text{ and }bRa\Rightarrow a\mathrm{\ne }b$

Answer: (1)
Explanation: This is the definition of antisymmetry.

---

Q51.

Simplify the Boolean expression:
$(A+B)(A+B^{\mathrm{\prime }})$
(1) A
(2) B
(3) AB
(4) A’

Answer: (1)
Explanation: Use absorption: (A + B)(A + B′) = A.

---

Q52.

Shortest-path algorithm that works with negative edge weights (but no negative cycles):
(1) Dijkstra
(2) Bellman–Ford
(3) Prim
(4) Floyd–Warshall only

Answer: (2)
Explanation: Bellman–Ford is designed for graphs with negative edges.

---

Q53.

PERT uses which probability distribution for activity times?
(1) Exponential
(2) Normal
(3) Beta
(4) Poisson

Answer: (3)
Explanation: PERT uses 3-point Beta distribution.

---

Q54.

The number of atomic events when flipping a fair coin n times is
(1) n
(2) n!
(3) $2^n$
(4) $n^2$

Answer: (3)
Explanation: Each flip has 2 outcomes → $2^n$.

---

Q55.

In a graph, the degree sum formula says:
(1) Sum of degrees = E
(2) Sum of degrees = 2E
(3) Sum of degrees = V
(4) Sum of degrees = V + E

Answer: (2)
Explanation: Handshaking lemma: ∑deg(v) = 2|E|.

---

Q56.

If a full binary tree has 15 internal nodes, the number of leaves is:
(1) 14
(2) 15
(3) 16
(4) 30

Answer: (3)
Explanation: In full binary tree: L = I + 1 = 16.

---

Q57.

A relation R on A is transitive if
(1) $aRb\text{ and }bRc\Rightarrow aRc$
(2) $aRb=bRa$
(3) $aRa$ for all a
(4) None

Answer: (1)
Explanation: Direct definition of transitivity.

---

Q58.

Probability of getting exactly 2 heads in 4 fair coin tosses:
(1) 1/4
(2) 3/8
(3) 6/16
(4) 1/2

Answer: (3)
Explanation: C(4,2)=6; total outcomes=16 → 6/16.

---

Q59.

A graph is bipartite if and only if
(1) It has no odd cycle
(2) It is planar
(3) It is complete
(4) It has Euler path

Answer: (1)
Explanation: Characterization of bipartite graphs: no odd-length cycle.

---

Q60.

The value of C(10, 3) is
(1) 120
(2) 720
(3) 10
(4) 3

Answer: (1)
Explanation: 10C3 = 120.

---

Q61.

If events A and B are independent, then
(1) $P(A\mathrm{\mid }B)=P(A)$
(2) $P(A\mathrm{\mid }B)=0$
(3) $P(A\mathrm{\mid }B)>P(A)$
(4) None of these

Answer: (1)
Explanation: Independence implies P(A|B)=P(A).

---

Q62.

The number of spanning trees in a tree with 10 vertices is
(1) 1
(2) 9
(3) 10
(4) 0

Answer: (1)
Explanation: A tree already IS a spanning tree → exactly one.

---

Q63.

In Boolean algebra, the identity element for AND is
(1) 0
(2) 1
(3) X
(4) X’

Answer: (2)
Explanation: A·1 = A.

---

Q64.

The number of subsets of a 5-element set is
(1) 10
(2) 25
(3) 32
(4) 64

Answer: (3)
Explanation: 2⁵ = 32.

---

Q65.

For a simple graph with 7 vertices, maximum possible number of edges is
(1) 21
(2) 7
(3) 14
(4) 35

Answer: (1)
Explanation: Maximum edges = n(n−1)/2 = 7×6/2 = 21.

---

Q66.

Which is a valid probability value?
(1) −0.2
(2) 1.4
(3) 0.5
(4) 2

Answer: (3)
Explanation: Probability must be in [0,1].

---

Q67.

A function f: A → B is surjective if
(1) every element of A is mapped
(2) f repeats values
(3) every element of B has a pre-image
(4) f is injective

Answer: (3)
Explanation: Surjection means onto.

---

Q68.

The chromatic number of a tree is
(1) 1
(2) 2
(3) 3
(4) n

Answer: (2)
Explanation: Any tree is bipartite.

---

Q69.

The probability of an impossible event is
(1) 1
(2) 1/2
(3) 0
(4) Undefined

Answer: (3)
Explanation: Impossible event = probability 0.

---

Q70.

In LP, the optimal solution always occurs at
(1) any point
(2) interior point
(3) a corner point
(4) outside feasible region

Answer: (3)
Explanation: Fundamental theorem of linear programming.

---

Q71.

In adjacency-matrix representation of a graph with n vertices, the matrix size is
(1) n
(2) n²
(3) n×n
(4) n−1

Answer: (3)
Explanation: Adjacency matrix is n×n.

---

Q72.

If P(A)=0.4, P(B)=0.5, and A,B mutually exclusive, then P(A∪B)=
(1) 0.9
(2) 0.2
(3) 1
(4) 0.1

Answer: (1)
Explanation: No overlap → sum of probabilities.

---

Q73.

If a∈A, then in set-builder form A =
(1) {x : x ≠ a}
(2) {x : x = a}
(3) {x : x has property of A}
(4) All

Answer: (3)
Explanation: Set-builder describes all elements satisfying the defining property.

---

Q74.

A graph with all even degrees is
(1) Hamiltonian
(2) Eulerian
(3) Tree
(4) Complete

Answer: (2)
Explanation: Eulerian graph ↔ connected + all vertices have even degree.

---

Q75.

If P(A)=0.6 and P(A′)=0.4, then
(1) Correct
(2) Incorrect
(3) Cannot say
(4) None

Answer: (1)
Explanation: A + A′ = 1.

---

Q76.

Number of edges in a tree with 30 vertices:
(1) 29
(2) 30
(3) 28
(4) None

Answer: (1)
Explanation: Tree with n vertices has n−1 edges.

---

Q77.

If a graph has an odd cycle, it is
(1) Bipartite
(2) Not bipartite
(3) Complete
(4) Tree

Answer: (2)
Explanation: Odd cycle → not bipartite.

---

Q78.

For a set of size n, number of proper subsets is
(1) $2^n$
(2) $2^n-1$
(3) n
(4) n!

Answer: (2)
Explanation: Exclude the set itself.

---

Q79.

Which operation is associative?
(1) Union
(2) Intersection
(3) Both
(4) None

Answer: (3)
Explanation: Both ∪ and ∩ are associative.

---

Q80.

In a simple graph, maximum degree of any vertex is
(1) n
(2) n−1
(3) n²
(4) n/2

Answer: (2)
Explanation: A vertex can be connected to at most n−1 others.