# Number Theory in Data Structure and Algorithms MCQs

Q1. If 4 is the GCD of 16 and 12, What is the GCD of 12 and 4?.

A. 12.

B. 6.

C. 4.

D. 2.

Q2. Which of the following is not an application of Euclid’s algorithm?.

A.  Simplification of fractions.

B.  Performing divisions in modular arithmetic.

D.  Solving diophantine equations.

Q3. The Euclid’s algorithm runs efficiently if the remainder of two numbers is divided by the minimum of two numbers until the remainder is zero..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q4. According to Gabriel lame, how many steps does Euclid’s algorithm require to solve a problem?.

A.  Less than five times the number of digits.

B.  More than five times the number of digits.

C.  Less than two times the number of digits.

D.  More than two times the number of digits.

Answer=  Less than five times the number of digits

Q5. Which of the following is the correct mathematical application of Euclid’s algorithm?.

A.  Determination of prime numbers.

B.  Lagrange’s four square theorem.

C.  Cauchy-Euler theorem.

D.  Residue theorem.

Q6. If GCD of two numbers is 1, then the two numbers are said to be ________.

A.  Co-prime numbers.

B.  Prime numbers.

C.  Composite numbers.

D.  Rational numbers.

Q7. What is the total running time of Euclid’s algorithm?.

A.  O(N).

B.  O(N log M).

C.  O(N log N).

D.  O(log N +1).

Q8. Euclidean algorithm does not require the calculation of prime factors..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q9. What is the formula for Euclidean algorithm?.

A.  GCD (m,n) = GCD (n, m mod n).

B.  LCM(m,n)=LCM(n, m mod n).

C.  GCD(m,n,o,p) = GCD (m, m mod n, o, p mod o).

D.  LCM (m,n,o,p) = LCM (m, m mod n, o, p mod o).

Answer=  GCD (m,n) = GCD (n, m mod n)

Q10. What is the total running time of the binary GCD algorithm?.

A.  O(N).

B.  O(N^2).

C.  O(log N).

D.  O(N log N).

Q11. What is the GCD of 20 and 12 using Euclid’s algorithm?.

A. 8.

B. 2.

C. 4.

D. 6.

Q12. Strassen’s algorithm is a/an_____________ algorithm..

A.  Non- recursive.

B.  Recursive.

C.  Approximation.

D.  Accurate.

Q13. What is the running time of Strassen’s algorithm for matrix multiplication?.

A.  O(n^2.81).

B.  O(n3).

C.  O(n1.8).

D.  O(n^2).

Q14. What is the running time of naÃ¯ve matrix multiplication algorithm?.

A.  O(n^2.81).

B.  O(n4).

C.  O(n).

D.  O(n3).

Q15. Strassen’s matrix multiplication algorithm follows ___________ technique..

A.  Greedy technique.

B.  Dynamic Programming.

C.  Divide and Conquer.

D.  Backtracking.

Q16. The number of scalar additions and subtractions used in Strassen’s matrix multiplication algorithm is ________.

A.  O(n^2.81).

B.  Theta(n^2).

C.  Theta(n).

D.  O(n3).

Q17. Who demonstrated the difference in numerical stability?.

A.  Strassen.

B.  Bailey.

C.  Lederman.

D.  Higham.

Q18. What is the recurrence relation used in Strassen’s algorithm?.

A.  7T(n/2) + Theta(n^2).

B.  8T(n/2) + Theta(n^2).

C.  7T(n/2) + O(n^2).

D.  8T(n/2) + O(n^2).

Q19. Who discussed techniques for reducing the memory requirements for Strassen’s algorithm?.

A.  Strassen.

B.  Lederman.

C.  Bailey.

D.  Higham.

Q20. What is the formula to calculate the element present in second row, first column of the product matrix?.

A.  M1+M7.

B.  M1+M3.

C.  M2+M4 – M5 + M7.

D.  M2+M4.

Q21. Strassen’s Matrix Algorithm was proposed by _____________.

A.  Volker Strassen.

B.  Andrew Strassen.

C.  Victor Jan.

D.  Virginia Williams.

Q22. How many iterating statements are involved in the naÃ¯ve method of matrix multiplication?.

A. 1.

B. 2.

C. 3.

D. 4.

Q23. Strassen’s algorithm is quite numerically stable as the naÃ¯ve method..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q24. Compute the product matrix using Strassen’s matrix multiplication algorithm.Given a11=1; a12=3;a21=5;a22=7b11=8;b12=4;b21=6;b22=2.

A.  c11=20;c12=12;c21=100;c22=15.

B.  c11=22;c12=8;c21=90;c22=32.

C.  c11=15;c12=7;c21=80;c22=34.

D.  c11=26;c12=10;c21=82;c22=34.

Q25. What is pseudo random number generator?.

A.  an algorithm that generates random numbers with help of mathematical formula.

B.  an algorithm that generates random numbers according to user activity.

C.  an algorithm that generates random numbers according to time.

D.  an algorithm that generates random numbers with help of user input.

Answer=  an algorithm that generates random numbers with help of mathematical formula

Q26. What should be the return type of rand() function?.

A.  int.

B.  float.

C.  long.

D.  double.

Q27. What is the purpose of using function srand()?.

A.  to set the seed of rand() function.

B.  to generate random numbers.

C.  to enable rand() function.

D.  to improve efficiency of rand().

Answer=  to set the seed of rand() function

Q28. What is the range of rand()?.

A.  0 to RAND_MAX.

B.  0 to infinity.

C.  0 to 2147483647.

D.  0 to 32767.

Q29. Which of the following will generate random numbers in the range 1-100 (both inclusive)?.

A.  rand() % 100.

B.  rand() % 101.

C.  (rand() % (101)) + 1.

D.  (rand() % (100)) + 1.

Answer=  (rand() % (100)) + 1

Q30. What is the minimum value of RAND_MAX possible in any implementation?.

A. 0.

B. 32767.

C. 2147483647.

D. 128.

Q31. Function rand() generates unique random numbers every time..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q32. What is the default value of seed if function rand() is called before srand()?.

A.  srand(0).

B.  srand(1).

C.  srand(time(null)).

D.  srand(-1).

Q33. Which header file contains the function rand() in C language?.

A.  stdlib.

B.  iostream.

C.  stdio.

D.  time.

Q34. The dictionary ordering of elements is known as?.

A.  Lexicographical order.

B.  Colexicographical order.

C.  Well order.

D.  Sorting.

Q35. How many permutations will be formed from the array arr={1,2,3}?.

A. 2.

B. 4.

C. 6.

D. 8.

Q36. What will be the lexicographical order of permutations formed from the array arr={1,2,3}?.

A.  {{2,1,3},{3,2,1},{3,1,2},{2,3,1},{1,2,3},{1,3,2}}.

B.  {{1,2,3},{1,3,2},{2,3,1},{2,1,3},{3,2,1},{3,1,2}}.

C.  {{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}.

D.  {{2,1,3},{3,1,2},{3,2,1},{2,3,1},{1,2,3},{1,3,2}}.

Q37. What is the time complexity of Heap’s algorithm?.

A.  O(n log n).

B.  O(n^2).

C.  O(n*n!).

D.  O(n!).

Q38. What is meant by the term lexicographical order?.

A.  dictionary ordering of elements.

B.  reverse dictionary ordering of elements.

C.  to sort according to value of first element.

D.  to sort according to value of last element.

Q39. How many combinations of 2 elements will be formed from the array arr={1,2,3}?.

A. 1.

B. 2.

C. 3.

D. 4.

Q40. What will be the lexicographical order of combinations of 2 elements each formed from the array arr={1,2,3}?.

A.  {{2,1},{3,2},{3,1}}.

B.  {{1,2},{2,3},{1,3}}.

C.  {{1,2},{1,3},{2,3}}.

D.  {{2,1},{3,1},{3,2}}.

Q41. What will be the auxiliary space requirement (excluding call stack) of the program to print combinations of r elements each from array of size n?.

A.  O(n*r).

B.  O(n/r).

C.  O(n).

D.  O(r).

Q42. The code for printing combinations is in-place..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q43. What will be the time complexity of the code to print combinations?.

A.  O(n).

B.  O(n^2).

C.  O(n log n).

D.  O(2n).

Q44. What is meant by integer partition?.

A.  representing an integer as sum of positive and negative real numbers.

B.  representing an integer as sum of positive and negative integers.

C.  representing an integer as sum of positive integers.

D.  representing an integer as sum of positive real numbers.

Answer=  representing an integer as sum of positive integers

Q45. How many partitions will be formed for the integer 3?.

A. 2.

B. 3.

C. 4.

D. 8.

Q46. What is meant by number theory?.

A.  study of integers.

B.  study of complex numbers.

C.  numerology.

D.  theory of origination of mathematics.

Q47. Which of the following is true according to Ramanujan’s congruence?.

A.  No. of partitions are divisible by 5 for a number 3 more than a multiple of 5.

B.  No. of partitions are divisible by 5 for a number 4 more than a multiple of 5.

C.  No. of partitions are divisible by 5 for a number 2 more than a multiple of 5.

D.  No. of partitions are divisible by 5 for a number 1 more than a multiple of 5.

Answer=  No. of partitions are divisible by 5 for a number 4 more than a multiple of 5

Q48. The no. of partitions of which of the following integer will be divisible by 5?.

A. 3.

B. 5.

C. 9.

D. 6.

Q49. What is meant by the power set of a set?.

A.  subset of all sets.

B.  set of all subsets.

C.  set of particular subsets.

D.  empty set.

Q50. Number of elements in the power set of set S={1,2,3} will be?.

A. 2.

B. 4.

C. 6.

D. 8.

Q51. Number of elements in the power set of set S={1,2,2} will be?.

A. 2.

B. 4.

C. 6.

D. 8.

Q52. Which one of the following problem types does inclusion-exclusion principle belong to?.

A.  Numerical problems.

B.  Graph problems.

C.  String processing problems.

D.  Combinatorial problems.

Q53. ____________ is one of the most useful principles of enumeration in combinationatorics and discrete probability..

A.  Inclusion-exclusion principle.

B.  Quick search algorithm.

C.  Euclid’s algorithm.

D.  Set theory.

Q54. Which of the following is not an application of inclusion-exclusion principle?.

A.  Counting intersections.

B.  Graph coloring.

C.  Matching of bipartite graphs.

D.  Maximum flow problem.

Q55. Who invented the concept of inclusion-exclusion principle?.

A.  Abraham de Moivre.

B.  Daniel Silva.

C.  J.J. Sylvester.

D.  Sieve.

Q56. Which of the following statement is incorrect with respect to generalizing the solution using the inclusion-exclusion principle?.

A.  including cardinalities of sets.

B.  excluding cardinalities of pairwise intersections.

C.  excluding cardinalities of triple-wise intersections.

D.  excluding cardinalities of quadraple-wise intersections.

Answer=  excluding cardinalities of triple-wise intersections

Q57. Counting intersections can be done using the inclusion-exclusion principle only if it is combined with De Morgan’s laws of complementing..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q58. Using the inclusion-exclusion principle, find the number of integers from a set of 1-100 that are not divisible by 2, 3 and 5..

A. 22.

B. 25.

C. 26.

D. 33.

Q59. ____________ is an arithmetic function that calculates the total number of positive integers less than or equal to some number n, that are relatively prime to n..

A.  Euler’s phi function.

B.  Euler’s omega function.

C.  Cauchy’s totient function.

D.  Legrange’s function.

Q60. Let A={1,2,3} B={2,3,4} C={1,3,5} D={2,3}. Find the cardinality of sum of all the sets..

A. 6.

B. 5.

C. 4.

D. 7.

Q61. The shortest distance between a line and a point is achieved when?.

A.  a line is drawn at 90 degrees to the given line from the given point.

B.  a line is drawn at 180 degrees to the given line from the given point.

C.  a line is drawn at 60 degrees to the given line from the given point.

D.  a line is drawn at 270 degrees to the given line from the given point.

Answer=  a line is drawn at 90 degrees to the given line from the given point

Q62. What is the distance between the lines 3x-4y+7=0 and 3x-4y+5=0?.

A.  1 unit.

B.  0.5 unit.

C.  0.8 unit.

D.  0.4 unit.