Category: Data Structures & Algorithms Objective Questions

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Interpolation Searching Algorithm”.

1. Which of the following is the most desirable condition for interpolation search?
a) array should be sorted
b) array should not be sorted but the values should be uniformly distributed
c) array should have a less than 64 elements
d) array should be sorted and the values should be uniformly distributed
Answer: d
Clarification: Desirable condition for interpolation search is that the array should be sorted and the values should be uniformly distributed. The algorithm would fail to give the correct result if array is not sorted.

2. Interpolation search is a variation of?
a) Linear search
b) Binary search
c) Jump search
d) Exponential search

Answer: b
Clarification: Interpolation search is a variation of binary search which gives the best result when the array has uniformly distributed values. Interpolation search goes to different positions depending on the value being searched whereas binary search always goes to the middle element.

3. Interpolation search performs better than binary search when?
a) array has uniformly distributed values but is not sorted
b) array is sorted and has uniform distribution of values
c) array is sorted but the values are not uniformly distributed
d) array is not sorted

Answer: b
Clarification: Interpolation search is an improvement over a binary search for the case when array is sorted and has uniformly distributed values. Binary search performs better when the values are not distributed uniformly.

4. In which of the following case jump search performs better than interpolation search?
a) When array has uniformly distributed values but is not sorted
b) when array is sorted and has uniform distribution of values
c) when array is sorted but the values increases exponentially
d) when array is not sorted

Answer: c
Clarification: In case of non uniform distribution of values the time complexity of interpolation search is O(n) whereas the average time complexity of jump search is O(n^1/2). So in such a case jump search has a better performance.

5. What is the time complexity of interpolation search when the input array has uniformly distributed values and is sorted?
a) O(n)
b) O(log log n)
c) O(n log n)
d) O(log n)
View Answer

Answer: b
Clarification: Interpolation search goes to different positions in the array depending on the value being searched. It is an improvement over binary search and has a time complexity of O(log log n).

6. What is the auxiliary space requirement of interpolation search?
a) O(n)
b) O(2ⁿ)
c) O(1)
d) O(log n)
Answer: c
Clarification: Interpolation search does not require any auxiliary space for finding the element being searched. So it has a constant auxiliary space O(1).

7. What is the time complexity of exponential search when the input array is sorted but the values are not uniformly distributed?
a) O(n^1/2)
b) O(log log n)
c) O(n)
d) O(log n)

Answer: c
Clarification: When an array has non uniformly distributed values then in that case the algorithm of interpolation search fails to work efficiently. As a result, it has a time complexity of O(n) in such a case.

8. Which of the following searching algorithm is fastest when the input array is sorted and has uniformly distributed values?
a) jump search
b) exponential search
c) binary search
d) interpolation search
Answer: d
Clarification: Interpolation search has a time complexity of O( log log n) when the array is sorted and has uniformly distributed values. It has the least time complexity out of the given options for such a case.

9. Which of the following searching algorithm is fastest when the input array is sorted but has non uniformly distributed values?
a) jump search
b) linear search
c) binary search
d) interpolation search

Answer: c
Clarification: Interpolation search has a time complexity of O(n) when the array does not have uniformly distributed values. So in such a case binary search has the least time complexity out of the given options.

10. Which of the following searching algorithm is fastest when the input array is not sorted but has uniformly distributed values?
a) jump search
b) linear search
c) binary search
d) interpolation search
Answer: b
Clarification: Out of the given options linear search is the only searching algorithm which can be applied to arrays which are not sorted. It has a time complexity of O(n) in the worst case.

11. Interpolation search is an in place algorithm.
a) true
b) false
Answer: a
Clarification: Interpolation search has an auxiliary space complexity of O(1). So it qualifies as an in place algorithm.

12. Interpolation search has a better time complexity than exponential search for any given array.
a) True
b) False

Answer: b
Clarification: The worst case time complexity of interpolation search and exponential search are O(n) and O(log n) respectively. So exponential search is better when the worst case scenario is considered.

13. What is the formula used for calculating the position in interpolation search?
(x = element being searched, A[] = input array, low and high are the leftmost and rightmost index of A[] respectively)
a) ((x – A[low]) * (high – low)) / (A[high] – A[low])
b) high + ((x – A[low]) * (high – low)) / (A[high] – A[low])
c) low + ((x – A[low]) * (high – low)) / (A[high] – A[low])
d) x + ((x – A[low]) * (high – low)) / (A[high] – A[low])

Answer: c
Clarification: For calculating the position after each iteration in interpolation search we use the formula low + ((x – A[low]) * (high – low)) / (A[high] – A[low]). Then the value at the calculated position is compared with the element being searched.

14. What are the updated values of high and low in the array if the element being searched is greater than the value at calculated index in interpolation search? (pos = current position)
a) low = pos + 1, high remains unchanged
b) high = pos – 1, low remains unchanged
c) low = low +1, high = high – 1
d) low = pos +1, high = pos – 1

Answer: a
Clarification: When the element being searched is greater than the value at the calculated position then in that case we update low and high remains unaltered. Updated value of low is low = pos + 1.

15. What are the updated values of high and low in the array if the element being searched is lower than the value at calculated index in interpolation search? (pos = current position)
a) low = pos + 1, high remains unchanged
b) high = pos – 1, low remains unchanged
c) low = low +1, high = high – 1
d) low = pos +1, high = pos – 1

Answer: b
Clarification: When the element being searched is lower than the value at the calculated position then in that case we update high and low remains unaltered. Updated value of high is high = pos – 1.

and Answers.

contest

Data Structures & Algorithms Multiple Choice Questions on “Heapsort – 1”.

1. On which algorithm is heap sort based on?
a) Fibonacci heap
b) Binary tree
c) Priority queue
d) FIFO
Answer: c
Clarification: Heap sort is based on the algorithm of priority queue and it gives the best sorting time.

2. In what time can a binary heap be built?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N²)

Answer: a
Clarification: The basic strategy is to build a binary heap of N elements which takes O(N) time.

3. Heap sort is faster than Shell sort.
a) true
b) false
Answer: b
Clarification: Heap sort is slower than Shell sort because Shell sort uses Sedgewick’s increment sequence.

4. Consider the following heap after buildheap phase. What will be its corresponding array?

a) 26,53,41,97,58,59,31
b) 26,31,41,53,58,59,97
c) 26,41,53,97,31,58,59
d) 97,53,59,26,41,58,31
Answer: d
Clarification: Constructing a max heap using the elements 97,53,59,26,41,58,31 will cause the heap to look like that.

5. In what position does the array for heap sort contains data?
a) 0
b) 1
c) -1
d) anywhere in the array

Answer: a
Clarification: The array for heap sort contains data at position 0 whereas for a binary heap, array begins at 1. This is the reason for its complexity.

6. In heap sort, after deleting the last minimum element, the array will contain elements in?
a) increasing sorting order
b) decreasing sorting order
c) tree inorder
d) tree preorder
Answer: b
Clarification: By logic, after deleting minimum element, the heap will contain elements in decreasing sorting order. We can change this by altering the ordering property.

7. What is the typical running time of a heap sort algorithm?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N²)
Answer: b
Clarification: The total running time of a heap sort algorithm is mathematically found to be O(N log N).

8. How many arrays are required to perform deletion operation in a heap?
a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: To perform deletion operation in a heap, we require 2 arrays and that occupies extra memory space and hence increase in running time.

9. What is the time taken to perform a delete min operation?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N²)

Answer: c
Clarification: The time taken to perform a deletion of a minimum element is mathematically found to be O( log N).

10. Heap sort is an extremely stable algorithm.
a) true
b) false
View Answer

Answer: a
Clarification: Heap sort uses fewer comparisons than other sorting algorithms and hence it is an extremely stable algorithm.

11. What is the average number of comparisons used in a heap sort algorithm?
a) N log N-O(N)
b) O(N log N)-O(N)
c) O(N log N)-1
d) 2N log N + O(N)
View Answer

Answer: d
Clarification: The average number of comparisons in a heapsort algorithm is mathematically found to be 2N log N + O(N).

12. What is the time taken to copy elements to and from two arrays created for deletion?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N²)

Answer: a
Clarification: The time taken to copy elements to and from the main array and extra array is found to be O(N).

13. What is the average number of comparisons used to heap sort a random permutation of N distinct items?
a) 2N log N-O(N)
b) 2N log N-O(N log N)
c) 2N log N-O(N log log N)
d) 2N log N-O(log N)
Answer: c
Clarification: According to a theorem, the average number of comparisons used to heap sort a random permutation of N distinct items is found to be 2N log N-O(N log log N).

contest

Data Structures & Algorithms Multiple Choice Questions on “MSD Radix Sort”.

1. How many comparisons will be made to sort the array arr = {1, 5, 3, 8, 2} using MSD radix sort?
a) 5
b) 7
c) 9
d) 0
Answer: d
Clarification: As MSD radix sort is an example of non comparison sort so it is able to sort an array without making any comparison. So the answer should be 0.

2. What is the full form of MSD in MSD radix sort?
a) most significant digit
b) many significant digit
c) more significant digit
d) must significant digit
Answer: a
Clarification: MSD stands for Most Significant Digit. It is named so because in this algorithm the processing begins from the most significant digit.

3. Which of the following combines qualities of MSD radix sort and LSD radix sort?
a) in-place MSD radix sort
b) stable MSD radix sot
c) 3 way radix quick sort
d) forward radix sort

Answer: d
Clarification: Forward radix sort combines the qualities of MSD and LSD radix sort. The sorting is done by separating the strings into groups.

4. Which of the following is the most suitable definition of radix sort?
a) It is a non comparison based integer sort
b) It is a comparison based integer sort
c) It is a non comparison based non integer sort
d) It is a comparison based non integer sort

Answer: a
Clarification: Radix sort is a non-comparison based integer sort. It sorts the given data by grouping keys which share the same significant position value.

5. Which of the following is an alternate name of MSD radix sort?
a) bottom up radix sort
b) top down radix sort
c) forward radix sort
d) backward radix sort

Answer: b
Clarification: Top down radix sort is an alternate name of MSD radix sort. It is because in this algorithm the processing starts from the most significant digit and end at least significant digit.

6. Which of the following is not true about MSD radix sort?
a) its processing starts from the most significant digit
b) it is not a stable sort
c) it is an in place sorting algorithm
d) it is non comparison based sort

Answer: c
Clarification: MSD radix sort takes non constant time for sorting the input data. So it is not an in place sorting algorithm.

7. MSD radix sort should be preferred over LSD radix sort when we have to maintain the original relative order.
a) True
b) False

Answer: b
Clarification: MSD radix sort is not a stable sort whereas LSD radix sort is stable. So when we require to preserve the original order then in that case we should prefer LSD radix sort.

8. What is the average time complexity of MSD radix sort (w= bits required to store each key)?
a) O(n + w)
b) O(n.w)
c) O(n²)
d) O(n log n)

Answer: b
Clarification: Time complexity of radix sort is O(n.w). It performs better than quick sort when we have log n bits for every digit.

9. MSD radix sort is an in place sorting algorithm.
a) True
b) False
View Answer

Answer: b
Clarification: MSD radix sort takes non constant time for sorting the input data. So it is not an in place sorting algorithm.

10. Which of the following statement is not a stable sorting algorithm?
a) LSD radix sort
b) MSD radix sort
c) Counting sort
d) Pigeonhole sort
View Answer

Answer: b
Clarification: MSD radix sort is not a stable sort. It is because the elements with identical values do not appear in the same order in the output array as they were in the input array.

11. Which of the following is not true about radix sort?
a) Radix sort performs better than quick sort when we have log n bits for every digit
b) Radix sort has better cache performance than quick sort
c) Radix sort has higher values of constant factor in asymptotic notation
d) Radix sort takes more space than quick sort

Answer: b
Clarification: Quick sort has a better cache performance than radix sort. Radix sort also takes more space as compared to quick sort.

12. What is the advantage of radix sort over quick sort?
a) radix sort performs better than quick sort when we have log n bits for every digit
b) radix sort has lesser space complexity
c) radix sort is not a comparison based sorting technique
d) radix sort has better cache performance than quick sort

Answer: a
Clarification: Radix sort performs better than quick sort when we have log n bits for every digit. But radix sort takes more space as compared to quick sort.

13. What will be the order of elements of the array arr = {23, 67, 143, 654, 43} after first iteration of MSD sort is complete?
a) 23, 43, 67, 143, 654
b) 23, 67, 43, 143, 654
c) 23, 67, 143, 654, 43
d) 23, 143, 43, 654, 67

Answer: b
Clarification: In the first iteration the array is sorted according to the most significant digit I.e. hundreds place value. So the order of elements will be 23, 67, 43, 143, 654.

contest

Data Structures & Algorithms Multiple Choice Questions on “Pseudorandom Number Generators”.

1. 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: a
Clarification: A pseudo random number generator generates random numbers with the help of a mathematical formula. We can seed the random number generator with a different value everytime if we want unique random numbers to be generated.

2. What should be the return type of rand() function?
a) int
b) float
c) long
d) double

Answer: a
Clarification: The return type of rand () is int. It can generate random numbers from 0 to RAND_MAX.

3. 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: a
Clarification: The function srand() sets the seed of rand(). It can be used to generate a unique set of random numbers every time.

4. What is the range of rand()?
a) 0 to RAND_MAX
b) 0 to infinity
c) 0 to 2147483647
d) 0 to 32767
View Answer

Answer: a
Clarification: The function rand() generates random numbers in the range 0 to RAND_MAX. The value of RAND_MAX is minimum 32,767.

5.What is the correct formula for generating random numbers in the range (lower,upper) using rand()?
a) rand() % (upper – lower)
b) rand() + lower
c) (rand()%(upper-lower)) + lower
d) (rand()%(upper-lower+1)) + lower

Answer: d
Clarification: The correct formula for generating random numbers in the range (lower,upper) using rand() is (rand()%(upper-lower+1)) + lower. The function rand() generates random numbers in the range 0 to RAND_MAX.

6. 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: d
Clarification: Formula for generating random numbers in the range (lower,upper) using rand() is (rand()%(upper-lower+1)) + lower. So the correct answer will be (rand() % (100)) + 1.

7. What is the minimum value of RAND_MAX possible in any implementation?
a) 0
b) 32767
c) 2147483647
d) 128

Answer: b
Clarification: The value of RAND_MAX varies according to implementation. But it is guaranteed to be at least 32767.

8. Function rand() generates unique random numbers every time.
a) true
b) false

Answer: b
Clarification: Function rand() does not generate unique random numbers every time. For achieving this we have to use srand() along with rand().

9. 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: b
Clarification: If srand() is not called before the call to the function rand() then the value of seed is taken as srand(1) by default. We should use srand() before rand() in order to use our own seed.

10. Pseudo random number generators can be used for data encryption.
a) true
b) false

Answer: b
Clarification: Pseudo random number generators cannot be used for data encryption as the random numbers generated by them are predictable. For data encryption the numbers should be absolutely unpredictable.

11. Predict the output of the following code.

#include  
int main() 
{ 
     srand(0); 
     printf("%dn", rand()); 
     return 0; 
}

a) compilation error
b) random number between 0 to RAND_MAX
c) cannot be predicted
d) 0

Answer: b
Clarification: The function rand() generates random numbers in the range 0 to RAND_MAX. The function srand() seeds rand(). We get unique set of random numbers if rand() is seeded with a different value every time.

12. Which header file contains the function rand() in C language?
a) stdlib
b) iostream
c) stdio
d) time
Answer: a
Clarification: In C language the header file stdlib contains the function rand(). It generates pseudo random numbers.

13. Predict the output of the following code.

#include  
int main() 
{ 
     srand(0); 
     printf("%dn", rand()%50); 
     return 0; 
}

a) compilation error
b) random number between 0 to 50 (both inclusive)
c) random number between 0 to 51 (both inclusive)
d) random number between 0 to 49 (both inclusive)

Answer: d
Clarification: Formula for generating random numbers in the range (lower,upper) using rand() is (rand()%(upper-lower+1)) + lower. So the given code will generate random numbers between 0 to 49.

14. Which of the following code will generate unique random numbers every time?
a)

#include  
int main() 
{ 
     srand(0); 
     printf("%dn", rand()%50); 
     return 0; 
}

b)

#include  
int main() 
{ 
     srand(time(0)); 
     printf("%dn", rand()%50); 
     return 0; 
}

c)

#include  
int main() 
{ 
    srand(1); 
    printf("%dn", rand()%50); 
    return 0; 
}

d)

#include  
int main() 
{
     printf("%dn", rand()%50); 
     return 0; 
}

Answer: b
Clarification: The function rand() generates random numbers in the range 0 to RAND_MAX. The function srand() seeds rand(). We get a unique set of random numbers if rand() is seeded with a different value every time. This can be achieved by using srand(time(0)).

15. Which of the following code will give an error?
a)

#include  
int main() 
{ 
     printf("%dn", srand()); 
     return 0; 
}

b)

#include  
int main() 
{ 
     srand(time(0)); 
     printf("%dn", rand()%50); 
     return 0; 
}

c)

#include  
int main() 
{ 
     srand(1); 
     return 0; 
}

d)

#include  
int main() 
{
     printf("%dn", rand()%50); 
     return 0; 
}

Answer: a
Clarification: The function rand() generates random numbers in the range 0 to RAND_MAX. The function srand() seeds rand(). So we get an error if we try to print srand().

Data Structure Multiple Choice Questions on “Recursion”.

1. Recursion is a method in which the solution of a problem depends on ____________
a) Larger instances of different problems
b) Larger instances of the same problem
c) Smaller instances of the same problem
d) Smaller instances of different problems

Answer: c
Clarification: In recursion, the solution of a problem depends on the solution of smaller instances of the same problem.

2. Which of the following problems can’t be solved using recursion?
a) Factorial of a number
b) Nth fibonacci number
c) Length of a string
d) Problems without base case

Answer: d
Clarification: Problems without base case leads to infinite recursion call. In general, we will assume a base case to avoid infinite recursion call. Problems like finding Factorial of a number, Nth Fibonacci number and Length of a string can be solved using recursion.

3. Recursion is similar to which of the following?
a) Switch Case
b) Loop
c) If-else
d) if elif else

Answer: b
Clarification: Recursion is similar to a loop.

4. In recursion, the condition for which the function will stop calling itself is ____________
a) Best case
b) Worst case
c) Base case
d) There is no such condition

Answer: c
Clarification: For recursion to end at some point, there always has to be a condition for which the function will not call itself. This condition is known as base case.

5. What will happen when the below code snippet is executed?

void my_recursive_function()
{
   my_recursive_function();
}
int main()
{
   my_recursive_function();
   return 0;
}

a) The code will be executed successfully and no output will be generated
b) The code will be executed successfully and random output will be generated
c) The code will show a compile time error
d) The code will run for some time and stop when the stack overflows

Answer: d
Clarification: Every function call is stored in the stack memory. In this case, there is no terminating condition(base case). So, my_recursive_function() will be called continuously till the stack overflows and there is no more space to store the function calls. At this point of time, the program will stop abruptly.

6. What is the output of the following code?

void my_recursive_function(int n)
{
    if(n == 0)
    return;
    printf("%d ",n);
    my_recursive_function(n-1);
}
int main()
{
    my_recursive_function(10);
    return 0;
}

a) 10
b) 1
c) 10 9 8 … 1 0
d) 10 9 8 … 1

Answer: d
Clarification: The program prints the numbers from 10 to 1.

7. What is the base case for the following code?

void my_recursive_function(int n)
{
     if(n == 0)
     return;
     printf("%d ",n);
     my_recursive_function(n-1);
}
int main()
{
     my_recursive_function(10);
     return 0;
}

a) return
b) printf(“%d “, n)
c) if(n == 0)
d) my_recursive_function(n-1)
Answer: c
Clarification: For the base case, the recursive function is not called. So, “if(n == 0)” is the base case.

8. How many times is the recursive function called, when the following code is executed?

void my_recursive_function(int n)
{
     if(n == 0)
     return;
     printf("%d ",n);
     my_recursive_function(n-1);
}
int main()
{
     my_recursive_function(10);
     return 0;
}

a) 9
b) 10
c) 11
d) 12

Answer: c
Clarification: The recursive function is called 11 times.

9. What does the following recursive code do?

void my_recursive_function(int n)
{
     if(n == 0)
     return;
     my_recursive_function(n-1);
     printf("%d ",n);
}
int main()
{
     my_recursive_function(10);
     return 0;
}

a) Prints the numbers from 10 to 1
b) Prints the numbers from 10 to 0
c) Prints the numbers from 1 to 10
d) Prints the numbers from 0 to 10

Answer: c
Clarification: The above code prints the numbers from 1 to 10.

10. Which of the following statements is true?
a) Recursion is always better than iteration
b) Recursion uses more memory compared to iteration
c) Recursion uses less memory compared to iteration
d) Iteration is always better and simpler than recursion

Answer: b
Clarification: Recursion uses more memory compared to iteration because every time the recursive function is called, the function call is stored in stack.

11. What will be the output of the following code?

int cnt=0;
void my_recursive_function(int n)
{
     if(n == 0)
     return;
     cnt++;
     my_recursive_function(n/10);
}
int main()
{
     my_recursive_function(123456789);
     printf("%d",cnt);
     return 0;
}

a) 123456789
b) 10
c) 0
d) 9

Answer: d
Clarification: The program prints the number of digits in the number 123456789, which is 9.

12. What will be the output of the following code?

void my_recursive_function(int n)
{
    if(n == 0)
    {
         printf("False");
	   return;
    }
    if(n == 1)
    {
         printf("True");
         return;
    }
    if(n%2==0)
    my_recursive_function(n/2);
    else
    {
         printf("False");
         return;
    }
 
}
int main()
{
     my_recursive_function(100);
     return 0;
}

a) True
b) False

Answer: b
Clarification: The function checks if a number is a power of 2. Since 100 is not a power of 2, it prints false.

13. What is the output of the following code?

int cnt = 0;
void my_recursive_function(char *s, int i)
{
     if(s[i] == ' ')
        return;
     if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
     cnt++;
     my_recursive_function(s,i+1);
}
int main()
{
     my_recursive_function("thisisrecursion",0);
     printf("%d",cnt);
     return 0;
}

a) 6
b) 9
c) 5
d) 10

Answer: a
Clarification: The function counts the number of vowels in a string. In this case the number is vowels is 6.

14. What is the output of the following code?

void my_recursive_function(int *arr, int val, int idx, int len)
{
    if(idx == len)
    {
         printf("-1");
         return ;
    }
    if(arr[idx] == val)
    {
         printf("%d",idx);
         return;
    }
    my_recursive_function(arr,val,idx+1,len);
}
int main()
{
     int array[10] = {7, 6, 4, 3, 2, 1, 9, 5, 0, 8};
     int value = 2;
     int len = 10;
     my_recursive_function(array, value, 0, len);
     return 0;
}

a) 3
b) 4
c) 5
d) 6
Answer: b
Clarification: The program searches for a value in the given array and prints the index at which the value is found. In this case, the program searches for value = 2. Since, the index of 2 is 4(0 based indexing), the program prints 4.

and Answers.