Class 9 The World of Algorithms Mock Test (CBSE)

Topics in The World of Algorithms

• What an algorithm is
• Adding numbers by counting
• Adding numbers digit by digit
• Computing the divisors of a number
• Greatest common divisor
• A first algorithm for gcd
• Data structures: lists
• Improving the gcd algorithm
• Analysing the efficiency of algorithms
• Euclid's algorithm for gcd
• Euclid's algorithm using remainders

The World of Algorithms practice questions with answers

1. Q1Multiple choice·1 mark
   In the first algorithm for finding the GCD of two numbers $a$ and $b$ by checking all numbers from $1$ up to the smaller number, the worst-case number of steps is proportional to:

   1. (a)$a + b$
   2. (b)$\min(a, b)$
   3. (c)$\max(a, b)$
   4. (d)$a \times b$
   Show answer and step marks

   1. Correct option: (b) $\min(a, b)$+1

   Answer: (b)
2. Q2Multiple choice·1 mark
   What is the greatest common divisor (GCD) of $36$ and $48$?

   1. (a)12
   2. (b)18
   3. (c)24
   4. (d)6
   Show answer and step marks

   1. Correct option: (a) $12$+1

   Answer: (a)
3. Q3Multiple choice·1 mark
   In applying Euclid's algorithm to find the GCD of two positive integers $a$ and $b$ where $a > b$, if $a = bq + r$, the next step in the algorithm is applied to which pair of numbers?

   1. (a)$a$ and $q$
   2. (b)$b$ and $r$
   3. (c)$q$ and $r$
   4. (d)$a$ and $r$
   Show answer and step marks

   1. Correct option: (b) $b$ and $r$+1

   Answer: (b)
4. Q4Assertion and reason·1 mark
   Assertion (A): When adding two large numbers digit by digit using an algorithm, a carry generated at any position must be added to the sum of the digits in the next position to the left. Reason (R): The digit-by-digit addition algorithm processes numbers starting from the most significant digit to the least significant digit.

   1. (a)Both Assertion (A) and Reason (R) are true and Reason (R) is the correct explanation of Assertion (A).
   2. (b)Both Assertion (A) and Reason (R) are true but Reason (R) is not the correct explanation of Assertion (A).
   3. (c)Assertion (A) is true but Reason (R) is false.
   4. (d)Assertion (A) is false but Reason (R) is true.
   Show answer and step marks

   1. Correct option: (c) Assertion (A) is true but Reason (R) is false.+1

   Answer: (c)
5. Q5Short answer·2 marks
   Find the greatest common divisor (GCD) of $105$ and $252$ using an efficient remainder-based approach. Briefly state why this method is more efficient than listing all divisors.
   Show answer and step marks

   1. Apply the division steps: $252 = 105 \times 2 + 42$, then $105 = 42 \times 2 + 21$, and $42 = 21 \times 2 + 0$, giving GCD = $21$.+1
   2. State the reason for efficiency: It replaces large search spaces of divisors with rapid reductions using quotients and remainders.+1

   Answer: GCD $= 21$ ($252 = 105 \times 2 + 42$, $105 = 42 \times 2 + 21$, $42 = 21 \times 2 + 0$). It is more efficient because each division replaces the numbers by smaller ones, so only a few steps are needed instead of testing every possible divisor.
6. Q6Short answer·3 marks
   List all the divisors of $72$ and all the divisors of $108$. Hence, find the greatest common divisor (GCD) of $72$ and $108$ using these lists.
   Show answer and step marks

   1. List the divisors of $72$: $1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72$.+1
   2. List the divisors of $108$: $1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108$.+1
   3. Identify the common divisors ($1, 2, 3, 4, 6, 9, 12, 18, 36$) and state the greatest common divisor as $36$.+1

   Answer: Divisors of $72$: $1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72$. Divisors of $108$: $1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108$. Common divisors: $1, 2, 3, 4, 6, 9, 12, 18, 36$, so GCD $= 36$.

More Class 9 Maths mock tests