Number Theory in Data Structure and Algorithms MCQs

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. 

Answer= 4


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

A.  Simplification of fractions. 

B.  Performing divisions in modular arithmetic. 

C.  Solving quadratic equations. 

D.  Solving diophantine equations. 

Answer=  Solving quadratic 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. 

Answer= TRUE


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. 

Answer=  Lagrange’s four square 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. 

Answer=  Co-prime 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). 

Answer=  O(N)


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. 

Answer= TRUE


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). 

Answer=  O(N^2)


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

A. 8. 

B. 2. 

C. 4. 

D. 6. 

Answer= 4


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

A.  Non- recursive. 

B.  Recursive. 

C.  Approximation. 

D.  Accurate. 

Answer=  Recursive


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). 

Answer=  O(n^2.81)


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). 

Answer=  O(n3)


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

A.  Greedy technique. 

B.  Dynamic Programming. 

C.  Divide and Conquer. 

D.  Backtracking. 

Answer=  Divide and Conquer


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). 

Answer=  Theta(n^2)


Q17. Who demonstrated the difference in numerical stability?. 

A.  Strassen. 

B.  Bailey. 

C.  Lederman. 

D.  Higham. 

Answer=  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). 

Answer=  7T(n/2) + Theta(n^2)


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

A.  Strassen. 

B.  Lederman. 

C.  Bailey. 

D.  Higham. 

Answer=  Bailey


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. 

Answer=  M2+M4


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

A.  Volker Strassen. 

B.  Andrew Strassen. 

C.  Victor Jan. 

D.  Virginia Williams. 

Answer=  Volker Strassen


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

A. 1. 

B. 2. 

C. 3. 

D. 4. 

Answer= 3


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. 

Answer= FALSE


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. 

Answer=  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. 

Answer=  int


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. 

Answer=  0 to RAND_MAX


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. 

Answer= 32767


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

A.  true. 

B.  false. 

C. Nothing Can be Said. 

D. None of the mentioned. 

Answer=  false


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). 

Answer=  srand(1)


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

A.  stdlib. 

B.  iostream. 

C.  stdio. 

D.  time. 

Answer=  stdlib


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

A.  Lexicographical order. 

B.  Colexicographical order. 

C.  Well order. 

D.  Sorting. 

Answer=  Lexicographical order


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

A. 2. 

B. 4. 

C. 6. 

D. 8. 

Answer= 6


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}}. 

Answer=  {{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}


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!). 

Answer=  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. 

Answer=  dictionary ordering of elements


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. 

Answer= 3


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}}. 

Answer=  {{1,2},{1,3},{2,3}}


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). 

Answer=  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. 

Answer=  false


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). 

Answer=  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. 

Answer= 3


Q46. What is meant by number theory?. 

A.  study of integers. 

B.  study of complex numbers. 

C.  numerology. 

D.  theory of origination of mathematics. 

Answer=  study of integers


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. 

Answer= 9


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. 

Answer=  set of all subsets


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

A. 2. 

B. 4. 

C. 6. 

D. 8. 

Answer= 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. 

Answer= 6


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. 

Answer=  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. 

Answer=  Inclusion-exclusion principle


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. 

Answer=  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. 

Answer=  Abraham de Moivre


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. 

Answer=  true


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. 

Answer= 26


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. 

Answer=  Euler’s phi 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. 

Answer= 5


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. 

Answer=  0.4 unit

Previous Post Next Post