Top GATE, UGC NET, NIELIT, and ISRO Practice Questions with Solutions

Prepare effectively for competitive exams like GATE, UGC NET, NIELIT, and ISRO with our carefully curated practice questions. Each question is provided with a detailed solution, step-by-step analysis, and examples for better understanding. These topics are designed for Computer Science aspirants and align with exam patterns.

---

Why These Questions Are Important?

These questions are designed to test critical concepts for competitive exams like GATE, UGC NET, and ISRO. They focus on logic, set theory, graph theory, and combinatorics, which are crucial topics for Computer Science aspirants.

Explore more questions and solutions on Digiimento.com. Prepare smarter, not harder!

Q.1 Number of Hamiltonian cycles in a complete graph with ‘n’ vertices

Question:
Number of Hamiltonian cycles in a complete graph with n vertices is: [MCQ – 2 Marks]

• a) n!
• b) (n-1)!
• c) (n-1)! / 2
• d) (n+1)! / 2

Answer: c) (n-1)! / 2

Solution:

A Hamiltonian cycle is a closed loop on a graph where every vertex is visited exactly once, and the cycle ends at the starting vertex.

1. Total vertices in the complete graph: n.
2. Fix one vertex as the starting point (to avoid duplicate counting of cycles).
3. Remaining n-1 vertices can be arranged in (n-1)! ways.
4. Since the cycle can be traversed in two directions (clockwise and anti-clockwise), we divide by 2 to eliminate duplicates.

Formula:
Number of Hamiltonian Cycles = (n-1)! / 2

Example:
If n = 4:

• Fix one vertex. Remaining n-1 = 3 vertices can be arranged in 3! = 6 ways.
• Divide by 2 for two directions: 6 / 2 = 3.

The Hamiltonian cycles are:

• 1 → 2 → 3 → 4 → 1,
• 1 → 3 → 2 → 4 → 1,
• 1 → 4 → 3 → 2 → 1.

---

Q.2 Total number of 4-letter words formed using “ALLAHABAD”

Question:
Total number of 4-letter words which can be formed by using the word ALLAHABAD, such that there are exactly two letters that are the same and the rest are different. [NAT – 2 Marks]

Answer: 144

Solution:

1. Word Composition:
   • 4 A’s, 2 L’s, and 1 each of H, B, D.
2. Choose 2 identical letters:
   Choose two A’s from the 4 A’s.
3. Choose 2 different letters:
   Remaining letters to choose from: L, H, B, D.
   Total ways to choose 2 letters = C(4, 2) = 6.
4. Arrangement of letters:
   Total letters = 4. Since 2 are identical, the arrangements = 4! / 2! = 12.
5. Final Calculation:
   Total combinations = 6 × 12 = 144.

Example:
Letters chosen: A, A, L, H.
Arrangements: AALH, AAHB, ALHA, etc.
Thus, the total number of combinations = 144.

Q.3 Consider the following statements

Question:
Consider the following statements: [MCQ – 1 Mark]

S1: ((a ∨ b) → c) → ((a ∧ b) → c)
S2: ((a ∧ b) → c) → ((a ∨ b) → c)

Which of the following is true?

• a) Only S1 is valid
• b) Only S2 is valid
• c) Both S1 and S2 are valid
• d) Both S1 and S2 are invalid

Answer: a) Only S1 is valid

Solution:

1. Logical Analysis of S1:S1 states that if ((a ∨ b) → c), then ((a ∧ b) → c). This means:
   • If c is true for at least one of a or b, then c will also be true when both a and b are true.

   This is logically valid.

2. Logical Analysis of S2:S2 states that if ((a ∧ b) → c), then ((a ∨ b) → c). This means:
   • If c is true when both a and b are true, then c must also be true when at least one of a or b is true.

   Counterexample:

   • Let a = T, b = F, and c = F.
   • In this case, (a ∧ b) = F, so ((a ∧ b) → c) is T.
   • However, ((a ∨ b) → c) is F.

   Hence, S2 is invalid.

Conclusion: S1 is valid, and S2 is invalid.

---

Q.4 How many simple graphs are possible on 4 vertices (labeled) with an odd number of edges?

Question:
How many simple graphs are possible on 4 vertices (labeled) in which the number of edges is odd? [NAT – 1 Mark]

Answer: 32

Solution:

1. Calculate Total Edges:A simple graph with 4 vertices can have edges between any pair of vertices. Total possible edges = C(4,2) = 6.
2. Total Simple Graphs:Each edge can either be present or absent. Total number of simple graphs = 2^6 = 64.
3. Graphs with Odd Number of Edges:Out of these 64 graphs, exactly half will have an odd number of edges. Total graphs with an odd number of edges = 64 / 2 = 32.

Example Calculation:

• Graph with 1 edge: C(6,1) = 6.
• Graph with 3 edges: C(6,3) = 20.
• Graph with 5 edges: C(6,5) = 6.
• Total = 6 + 20 + 6 = 32.

Q.5 Which of the following statements are not equivalent for a graph with at least 1 edge?

Question:
Which of the following statements are not equivalent for a graph with at least 1 edge? [MSQ – 1 Mark]

• a. G is bipartite
• b. A graph is 2-colourable
• c. Graph G has a Hamiltonian circuit
• d. Every cycle of G is of even length

Answer: a, b, c, d

Solution:

1. a. G is bipartite: A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent.
2. b. A graph is 2-colourable: A graph is 2-colourable if its vertices can be coloured using only two colours such that no two adjacent vertices have the same colour.
3. c. Graph G has a Hamiltonian circuit: A Hamiltonian circuit is a cycle that visits each vertex exactly once and returns to the starting vertex. This property is unrelated to the above properties.
4. d. Every cycle of G is of even length: This is a necessary condition for G to be bipartite, but it is not equivalent to the other properties.

Conclusion: None of the statements are equivalent as they describe different graph properties.

---

Q.6 Find the value of f-1(g(3))

Question:
Let f and g : ℝ → ℝ be defined as follows:
f(x) = x + 2, g(x) = (1 + x2)-1.
Find the value of f-1(g(3)). [NAT – 1 Mark]

Answer: -1.9

Solution:

1. Evaluate g(3):Substitute x = 3 into g(x):
   g(3) = 1 / (1 + 32) = 1 / (1 + 9) = 1 / 10 = 0.1
2. Find f-1(x):From f(x) = x + 2, solve for x in terms of y:
   f(x) = y ⇒ x = y - 2 ⇒ f-1(x) = x - 2
3. Substitute g(3) into f-1(x):f-1(g(3)) = f-1(0.1) = 0.1 - 2 = -1.9

Q.7 Which of the following is true?

Question:
Which of the following is true? [MCQ – 1 Mark]

• a) Empty set ϕ is an equivalence relation.
• b) A relation can never be both symmetric and anti-symmetric.
• c) “Divides” relation on the set of positive integers is symmetric.
• d) The union of two equivalence relations need not be an equivalence relation.

Answer: d) The union of two equivalence relations need not be an equivalence relation.

Solution:

1. Option a:The empty set ϕ is vacuously reflexive, symmetric, and transitive. Thus, ϕ can be an equivalence relation. This statement is true for equivalence relations, but not relevant to all relations.
2. Option b:A relation can be both symmetric and anti-symmetric if it is trivial, such as the identity relation where (a, a) is the only relation. Therefore, this statement is false.
3. Option c:The “divides” relation a | b on positive integers is not symmetric, as 2 | 4 but 4 |̸ 2. Hence, this statement is false.
4. Option d:The union of two equivalence relations need not be an equivalence relation because the union may not satisfy transitivity. For example, consider equivalence relations on disjoint subsets—transitivity will fail.

Conclusion: The correct answer is d.

---

Q.8 Which of the following is not necessarily a property of the group?

Question:
Which of the following is not necessarily a property of the group? [MCQ – 1 Mark]

• a) Commutativity
• b) Associativity
• c) Existence of inverse for every element
• d) Closure property

Answer: a) Commutativity

Solution:

1. Group Definition:A group is a set G with a binary operation * such that:
   • Closure: For all a, b ∈ G, a * b ∈ G.
   • Associativity: For all a, b, c ∈ G, (a * b) * c = a * (b * c).
   • Identity Element: There exists e ∈ G such that a * e = a for all a ∈ G.
   • Inverse: For every a ∈ G, there exists b ∈ G such that a * b = e.
2. Option a – Commutativity:Commutativity (a * b = b * a) is not required for a group. It is only required for an abelian group. Hence, this property is not necessary.
3. Option b – Associativity:Associativity is a fundamental property of a group and is always required.
4. Option c – Existence of Inverse:The existence of an inverse for every element is a necessary property of a group.
5. Option d – Closure Property:Closure under the group operation is a necessary property of a group.

Conclusion: The correct answer is a.

Q.9 The cardinality of the symmetric closure of the given relation

Question:
The cardinality of the symmetric closure of the following relation is _____. [NAT – 2 Marks]

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

Answer: 8

Solution:

1. Given Relation:The relation includes the pairs:
   { (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0) }.
2. Symmetric Closure Definition:A relation is symmetric if for every pair (a, b) ∈ R, the pair (b, a) is also in R.
3. Identify Missing Symmetric Pair:The given relation is missing (2, 1).
4. Add Missing Pair:Add (2, 1) to the relation.
5. Final Relation:The symmetric closure is:
   { (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1) }.
6. Cardinality:The total number of pairs = 8.

---

Q.10 Functions f : Z × Z → Z that are onto

Question:
Which of the following functions f : Z × Z → Z is/are onto? [MSQ – 2 Marks]

• a) f(a, b) = a + b
• b) f(a, b) = a
• c) f(a, b) = |b|
• d) f(a, b) = a - b

Answer: a, b, d

Solution:

1. Option a – f(a, b) = a + b:For any c ∈ Z, choose a = c and b = 0. Then, f(a, b) = c. Hence, f(a, b) = a + b is onto.
2. Option b – f(a, b) = a:For any c ∈ Z, choose a = c and b arbitrary. Then, f(a, b) = c. Hence, f(a, b) = a is onto.
3. Option c – f(a, b) = |b|:The absolute value function |b| only produces non-negative integers. Therefore, it is not onto.
4. Option d – f(a, b) = a - b:For any c ∈ Z, choose a = c and b = 0. Then, f(a, b) = c. Hence, f(a, b) = a - b is onto.

---

Q.11 Negation of the given expression

Question:
What is the negation of the following expression? [MCQ – 2 Marks]

(p → q) ∨ (¬q → ¬r)

• a) (¬p ∧ q) ∧ (¬q ∨ r)
• b) (p ∧ ¬q) ∧ (¬q ∧ r)
• c) (¬p ∧ q) ∧ (¬q ∧ r)
• d) (p ∧ q) ∧ (¬q ∧ ¬r)

Answer: b) (p ∧ ¬q) ∧ (¬q ∧ r)

Solution:

1. Expression Analysis:Rewrite using implications:
   (p → q) ∨ (¬q → ¬r) = (¬p ∨ q) ∨ (q ∨ r).
2. Negation:Negating the expression:
   ¬[(¬p ∨ q) ∨ (q ∨ r)] = (¬(¬p ∨ q)) ∧ (¬(q ∨ r)).Simplify further:
   (p ∧ ¬q) ∧ (¬q ∧ r).

Q.12 How many integers in the set {1, 2, 3, ..., 121} are not divisible by 2, 3, or 5?

Question:
How many integers in the set {1, 2, 3, ..., 121} are not divisible by 2, 3, or 5? [MCQ – 2 Marks]

• a) 120
• b) 84
• c) 124
• d) None of these

Answer: b) 84

Solution:

1. Total Numbers in the Set:Total integers in {1, 2, 3, ..., 121} = 121.
2. Numbers Divisible by Each of 2, 3, and 5:
   • Divisible by 2: ⎣121 / 2⎦ = 60.
   • Divisible by 3: ⎣121 / 3⎦ = 40.
   • Divisible by 5: ⎣121 / 5⎦ = 24.
3. Numbers Divisible by Two or More (Inclusion-Exclusion Principle):
   • Divisible by 2 and 3: ⎣121 / 6⎦ = 20.
   • Divisible by 3 and 5: ⎣121 / 15⎦ = 8.
   • Divisible by 2 and 5: ⎣121 / 10⎦ = 12.
   • Divisible by 2, 3, and 5: ⎣121 / 30⎦ = 4.

   Total divisible by 2, 3, or 5:
   60 + 40 + 24 - 20 - 12 - 8 + 4 = 88.

4. Numbers Not Divisible by 2, 3, or 5:Total not divisible: 121 - 88 = 33.

---

Q.13 Simplify (A - B) - C

Question:
Let A, B, and C be three sets. Then (A - B) - C = _____. [MSQ – 2 Marks]

• a) (A - B) - (B - C)
• b) (B - C) - (A - C)
• c) (A - B) - (A - C)
• d) (A - C) - (B - C)

Answer: d) (A - C) - (B - C)

Solution:

1. Simplify (A - B) - C:Definition of set difference:
   (A - B) = {x | x ∈ A and x ∉ B}.
   Further:
   (A - B) - C = {x | x ∈ (A - B) and x ∉ C}.
2. Rewriting Using Set Difference Properties:Simplify (A - B) - C:
   (A - B) - C = (A - C) - (B - C).

Conclusion: The correct answer is d.