Category: Data Structures & Algorithms Objective Questions

Data Structure Multiple Choice Questions on “Assembly Line Scheduling”.

1. Which of the following methods can be used to solve the assembly line scheduling problem?
a) Recursion
b) Brute force
c) Dynamic programming
d) All of the mentioned
Answer: d
Clarification: All of the above mentioned methods can be used to solve the assembly line scheduling problem.

2. What is the time complexity of the brute force algorithm used to solve the assembly line scheduling problem?
a) O(1)
b) O(n)
c) O(n²)
d) O(2ⁿ)
Answer: d
Clarification: In the brute force algorithm, all the possible ways are calculated which are of the order of 2ⁿ.

3. In the dynamic programming implementation of the assembly line scheduling problem, how many lookup tables are required?
a) 0
b) 1
c) 2
d) 3
Answer: c
Clarification: In the dynamic programming implementation of the assembly line scheduling problem, 2 lookup tables are required one for storing the minimum time and the other for storing the assembly line number.

4. Consider the following assembly line problem:

time_to_reach[2][3] = {{17, 2, 7}, {19, 4, 9}}
time_spent[2][4] = {{6, 5, 15, 7}, {5, 10, 11, 4}}
entry_time[2] = {8, 10}
exit_time[2] = {10, 7}
num_of_stations = 4

For the optimal solution which should be the starting assembly line?
a) Line 1
b) Line 2
c) All of the mentioned
d) None of the mentioned

Answer: b
Clarification: For the optimal solution, the starting assembly line is line 2.

5. Consider the following assembly line problem:

time_to_reach[2][3] = {{17, 2, 7}, {19, 4, 9}}
time_spent[2][4] = {{6, 5, 15, 7}, {5, 10, 11, 4}}
entry_time[2] = {8, 10}
exit_time[2] = {10, 7}
num_of_stations = 4

For the optimal solution, which should be the exit assembly line?
a) Line 1
b) Line 2
c) All of the mentioned
d) None of the mentioned

Answer: b
Clarification: For the optimal solution, the exit assembly line is line 2.

6. Consider the following assembly line problem:

time_to_reach[2][3] = {{17, 2, 7}, {19, 4, 9}}
time_spent[2][4] = {{6, 5, 15, 7}, {5, 10, 11, 4}}
entry_time[2] = {8, 10}
exit_time[2] = {10, 7}
num_of_stations = 4

What is the minimum time required to build the car chassis?
a) 40
b) 41
c) 42
d) 43
View Answer

Answer: d
Clarification: The minimum time required is 43.
The path is S2,1 -> S1,2 -> S2,3 -> S2,4, where Si,j : i = line number, j = station number

7. Consider the following code:

#include
int get_min(int a, int b)
{
     if(a<b)
        return a;
     return b;
}
int minimum_time_required(int reach[][3],int spent[][4], int *entry, int *exit, int n)
{
     int t1[n], t2[n],i;
     t1[0] = entry[0] + spent[0][0];
     t2[0] = entry[1] + spent[1][0];
     for(i = 1; i < n; i++)
     {
         t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]);
         __________;
     }
     return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]);
}

Which of the following lines should be inserted to complete the above code?
a) t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i])
b) t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+spent[1][i])
c) t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1])
d) none of the mentioned

Answer: a
Clarification: The line t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]) should be added to complete the above code.

8. What is the time complexity of the above dynamic programming implementation of the assembly line scheduling problem?
a) O(1)
b) O(n)
c) O(n²)
d) O(n³)
Answer: b
Clarification: The time complexity of the above dynamic programming implementation of the assembly line scheduling problem is O(n).

9. What is the space complexity of the above dynamic programming implementation of the assembly line scheduling problem?
a) O(1)
b) O(n)
c) O(n²)
d) O(n³)
Answer: b
Clarification: The space complexity of the above dynamic programming implementation of the assembly line scheduling problem is O(n).

10. What is the output of the following code?

#include
int get_min(int a, int b)
{
     if(a<b)
        return a;
     return b;
}
int minimum_time_required(int reach[][3],int spent[][4], int *entry, int *exit, int n)
{
     int t1[n], t2[n], i;
     t1[0] = entry[0] + spent[0][0];
     t2[0] = entry[1] + spent[1][0];
     for(i = 1; i < n; i++)
     {
         t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]);
         t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]);
     }
     return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]);
}
int main()
{
    int time_to_reach[][3] = {{6, 1, 5},
                           {2, 4, 7}};
    int time_spent[][4] = {{6, 5, 4, 7},
                        {5, 10, 2, 6}};
    int entry_time[2] = {5, 6};
    int exit_time[2] = {8, 9};
    int num_of_stations = 4;
    int ans = minimum_time_required(time_to_reach, time_spent, 
              entry_time, exit_time, num_of_stations);
    printf("%d",ans);
    return 0;
}

a) 32
b) 33
c) 34
d) 35

Answer: c
Clarification: The program prints the optimal time required to build the car chassis, which is 34.

11. What is the value stored in t1[2] when the following code is executed?

#include
int get_min(int a, int b)
{
     if(a<b)
        return a;
     return b;
}
int minimum_time_required(int reach[][3],int spent[][4], int *entry, int *exit, int n)
{
      int t1[n], t2[n],i;
      t1[0] = entry[0] + spent[0][0];
      t2[0] = entry[1] + spent[1][0];
      for(i = 1; i < n; i++)
      {
          t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]);
          t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]);
      }
    return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]);
}
int main()
{
     int time_to_reach[][3] = {{6, 1, 5},
                            {2, 4, 7}};
     int time_spent[][4] = {{6, 5, 4, 7},
                        {5, 10, 2, 6}};
     int entry_time[2] = {5, 6};
     int exit_time[2] = {8, 9};
     int num_of_stations = 4;
     int ans = minimum_time_required(time_to_reach, time_spent, 
               entry_time, exit_time, num_of_stations);
     printf("%d",ans);
     return 0;
}

a) 16
b) 18
c) 20
d) 22
Answer: c
Clarification: The value stored in t1[2] when the above code is executed is 20.

12. What is the value stored in t2[3] when the following code is executed?

#include
int get_min(int a, int b)
{
     if(a<b)
        return a;
     return b;
}
int minimum_time_required(int reach[][3],int spent[][4], int *entry, int *exit, int n)
{
     int t1[n], t2[n],i;
     t1[0] = entry[0] + spent[0][0];
     t2[0] = entry[1] + spent[1][0];
     for(i = 1; i < n; i++)
     {
         t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]);
         t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]);
     }
     return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]);
}
int main()
{
    int time_to_reach[][3] = {{6, 1, 5},
                           {2, 4, 7}};
    int time_spent[][4] = {{6, 5, 4, 7},
                        {5, 10, 2, 6}};
    int entry_time[2] = {5, 6};
    int exit_time[2] = {8, 9};
    int num_of_stations = 4;
    int ans = minimum_time_required(time_to_reach, time_spent, 
              entry_time, exit_time, num_of_stations);
    printf("%d",ans);
    return 0;
}

a) 19
b) 23
c) 25
d) 27

Answer: c
Clarification: The value stored in t2[3] when the above code is executed is 25.

13. What is the output of the following code?

#include
int get_min(int a, int b)
{
      if(a<b)
        return a;
      return b;
}
int minimum_time_required(int reach[][4],int spent[][5], int *entry, int *exit, int n)
{
      int t1[n], t2[n], i;
      t1[0] = entry[0] + spent[0][0];
      t2[0] = entry[1] + spent[1][0];
      for(i = 1; i < n; i++)
      {
          t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]);
          t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]);
      }
      return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]);
}
int main()
{
     int time_to_reach[][4] = {{16, 10, 5, 12},
                           {12, 4, 17, 8}};
     int time_spent[][5] = {{13, 5, 20, 19, 9},
                        {15, 10, 12, 16, 13}};
     int entry_time[2] = {12, 9};
     int exit_time[2] = {10, 13};
     int num_of_stations = 5;
     int ans = minimum_time_required(time_to_reach, time_spent, 
               entry_time, exit_time, num_of_stations);
     printf("%d",ans);
     return 0;
}

a) 62
b) 69
c) 75
d) 88

Answer: d
Clarification: The program prints the optimal time required to build the car chassis, which is 88.

and Answers.

Data Structures & Algorithms Multiple Choice Questions on “Hill Cipher”.

1. Hill cipher requires prerequisite knowledge of?
a) integration
b) differentiation
c) matrix algebra
d) differential equation
Answer: c
Clarification: Hill cipher uses matrix multiplication in order to encrypt the given plain text. So it requires prerequisite knowledge of matrix algebra.

2. Hill cipher is an example of ____________
a) mono-alphabetic cipher
b) substitution cipher
c) transposition cipher
d) additive cipher
Answer: b
Clarification: Hill cipher is a substitution cipher. It falls under the category of poly alphabetic cipher as it uses multiple substitutions at different positions in order to cipher the plain text.

3. Encryption in hill cipher is done using ______________
a) matrix multiplication
b) a 5×5 table
c) vigenere table
d) matrix inversion

Answer: a
Clarification: Encryption of plain text in playfair cipher is done using matrix multiplication. Then modulo 26 of the resulting matrix is taken so as to get the ciphered text.

4. What is poly graphic substitution cipher?
a) a substitution based cipher which uses multiple substitutions at different positions
b) a substitution based cipher which uses fixed substitution over entire plain text
c) a substitution based cipher in which substitution is performed over a block of letters
d) a transposition based cipher which uses fixed substitution over entire plain text

Answer: c
Clarification: Poly graphic cipher is a type of substitution cipher in which substitution is performed over a block of letters. Hill cipher is an example of poly graphic cipher.

5. Which of the following was the first poly graphic cipher to be able to operate on more than 3 letters at once?
a) autokey cipher
b) hill cipher
c) one time pad cipher
d) playfair cipher

Answer:b
Clarification: Poly graphic cipher is a type of substitution cipher in which substitution is performed over a block of letters. Hill cipher was the first poly graphic cipher to be able to operate on more than 3 letters at once.

6. Which of the following is hardest to break using frequency analysis?
a) Vigenere cipher
b) Hill cipher
c) Caesar cipher
d) Affine cipher
View Answer

Answer: b
Clarification: Out of the given options hill cipher is the hardest cipher to break using frequency analysis. Although it is quite vulnerable to other forms of attack.

7. Hill cipher is harder to crack than playfair cipher.
a) True
b) False

Answer: b
Clarification: Both hill cipher and playfair cipher are less vulnerable to frequency analysis. But hill cipher is quite vulnerable to other forms of attack and thus less secure than playfair cipher.

8. What will be the plain text corresponding to cipher text “YGQ“ if hill cipher is used with keyword as “GYBNQKURP”?
a) SECRET
b) WORLD
c) DOLLAR
d) HELLO
View Answer

Answer: a
Clarification: To decrypt the message we follow the reverse procedure. We first find the inverse of the keyword matrix then multiply it with cipher matrix.

9. What will be the size of a key matrix if the plain text is “SECRET”?
a) 1×6
b) 5×1
c) 6×1
d) 6×6
Answer: d
Clarification: Hill cipher uses a n x n matrix in order to cipher the plain text. In this case n=6 so a 6×6 matrix will be used.

10. A key matrix used for encryption in hill cipher must be?
a) invertible matrix
b) non invertible matrix
c) square matrix
d) rectangular matrix
Answer: a
Clarification: A key matrix used for encryption in hill cipher must be invertible matrix. Otherwise it will be impossible to decipher the message.

11. What will be the ciphered text if the plain text “SAN” is encrypted using hill cipher with keyword as “GYBNQKURP”?
a) RAJ
b) JAR
c) ARJ
d) AJR
Answer: a
Clarification: We first convert the keyword and plain text into their corresponding matrix respectively. Then we multiply those matrix and take modulo 26 of the resulting matrix to get the ciphered text.

and Answers.

This set of Data Structures & Algorithms Multiple Choice Questions on “Optimal Page Replacement Algorithm”.

1. __________ has the lowest fault rate of all the page replacement algorithms.
a) Optimal page replacement algorithm
b) LRU replacement algorithm
c) FIFO
d) Counting based

Answer: a
Clarification: Optimal page replacement algorithm has the lowest fault rate as it has the knowledge of all the pages beforehand.

2. Optimal page replacement algorithm is also called as __________
a) LIFO
b) NRU
c) Clairvoyant replacement algorithm
d) Page buffering

Answer: c
Clarification: Optimal page replacement algorithm is also called a Clairvoyant replacement algorithm or Belady’s optimal replacement algorithm.

3. In a optimal page replacement algorithm, when a page is to be replaced, which of the following pages is chosen?
a) Oldest page
b) Newest page
c) Frequently occurred page in the future
d) Not frequently occurred page in the future
Answer: d
Clarification: The page which doesn’t occur more frequently in the future is chosen to be replaced with the page in the frame.

4. A page that is not going to be used for the next 7 seconds will be swapped out over a page that is going to be used within the next 0.7 seconds.
a) True
b) False
Answer: a
Clarification: In an optimal page replacement algorithm, the page that is to be used later in the future is swapped out over a page that is to be used immediately.

5. Analysis of the optimal paging problem has been done through___________
a) Deterministic algorithm
b) Online algorithm
c) Euclid algorithm
d) Optimal algorithm

Answer: b
Clarification: Analysis of the optimal paging algorithm is done through an online algorithm. Efficiency is calculated through amortized analysis.

6. Optimal page replacement algorithm is implemented in __________
a) General-purpose operating system
b) Special-purpose operating system
c) In any kind of operating system
d) In Windows only

Answer: b
Clarification: Optimal page replacement algorithm is used in special-purpose operating system because it is impossible to compute time before which a page is used.

7. Optimal page replacement algorithm is said to satisfy __________
a) Online algorithm
b) Stack algorithm
c) Queue algorithm
d) Array algorithm

Answer: b
Clarification: Optimal page replacement algorithm is said to satisfy the stack algorithm. It is also called as inclusion property.

8. In a stack algorithm, the set of pages in a k-frame memory is always a subset of pages in a __________ frame memory.
a) k-1
b) k
c) k+1
d) k(k+1)

Answer: c
Clarification: Stack algorithm is satisfied if the set of pages in a k-frame memory is always a subset of pages in a k+1 frame memory.

9. When all software that runs on a system is known beforehand, optimal page replacement algorithm can be used in a general-purpose operating system.
a) True
b) False

Answer: a
Clarification: The algorithm can be implemented in a general-purpose algorithm if the software is known beforehand and if it is amenable to the static analysis of the memory.

10. Consider a reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 of frame size 3. Calculate the number of page faults using optimal page replacement algorithm.
a) 10
b) 9
c) 8
d) 7
Answer: b
Clarification: For the given string, the number of page faults using optimal page replacement algorithm is 9. It is solved in the given diagram.

11. Consider a reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 of frame size 4. Calculate the number of page faults using optimal page replacement algorithm.

a) 7
b) 9
c) 8
d) 6

Answer: c
Clarification: For the given reference string, the number of page faults using optimal page replacement algorithm is said to be 8. It is solved in the given diagram.

12. Consider a reference string 1,2,3,2,1,5,2,1,6,2,5,6,3,1,3,6,1,2,4,3 of frame size 3. Calculate the number of page faults using optimal page replacement algorithm.

a) 12
b) 16
c) 14
d) 15

Answer: c
Clarification: For the given reference string, the number of page faults using optimal page replacement algorithm is said to be 14.

Data Structures & Algorithms Multiple Choice Questions on “Jump Search”.

1. Jump search algorithm requires which of the following condition to be true?
a) array should be sorted
b) array should have not be sorted
c) array should have a less than 64 elements
d) array should be partially sorted
Answer: a
Clarification: Jump sort requires the input array to be sorted. The algorithm would fail to give the correct result if array is not sorted.

2. Jumps are made in the jump search algorithm until ___________
a) element having value less than that of the required element is found
b) element having value equal to the median of values of the array is found
c) element having value greater than that of the required element is found
d) middle element is found equal to the element being searched
Answer: c
Clarification: In jump search algorithm jumps are made until element having value greater than the value of element being searched is found. After this linear search is performed in backwards direction.

3. Which of the following step is taken after finding an element having value greater than the element being searched?
a) linear search takes place in the forward direction
b) linear search takes place in the backward direction
c) binary search takes place in the forward direction
d) binary search takes place in a backward direction
Answer: b
Clarification: First an element having value greater than the element being searched is found. After this linear search is performed in a backward direction.

4. How many jumps will be made in the worst case of jump search(let block jumped =k)?
a) n*k
b) n/k
c) k/n
d) n+k
Answer: b
Clarification: Worst case occurs when the value to be searched is in the last section of the array. So, in this case the number of jumps will be n/k.

5. What will be the maximum number of comparisons that can be made in jump search algorithm (assuming k to be blocks jumped)?
a) k
b) n/k
c) k-1
d) k-1
Answer: c
Clarification: Worst case occurs when the element being searched is present just after the element that has been compared while making the last jump. So, in this case k-1 comparisons will have to be made.

6. What is the value of jump taken for maximum efficiency while implementing jump search?
a) n/2
b) n²
c) n^1/2
d) log n

Answer: c
Clarification: Total number of comparisons required will be n/k + k-1 in worst case. This function will be minimum for k=n^1/2. So this value of jump will be the best for implementing jump search.

7. What is the auxiliary space requirement of the jump search?
a) O(n)
b) O(log n)
c) O(n^1/2)
d) O(1)

Answer: d
Clarification: Jump search does not require any additional space for searching the required element. Thus its auxiliary space requirement will be O(1).

8. Which of the following searching algorithm is fastest?
a) jump search
b) binary search
c) linear search
d) all are equally fast

Answer: b
Clarification: Binary search has the least time complexity (equal to log n) out of the given searching algorithms. This makes binary search preferable in most cases.

9. In which of the following case jump search will be preferred over binary search?
a) jumping backwards takes significantly more time than jumping forward
b) jumping forward takes significantly more time than jumping backwards
c) when the given array is very large in size
d) when the given array is very small in size

Answer: a
Clarification: Jump search only needs to jump backwards once, while a binary can jump backwards up to log n times. Thus jump search will be preferred over binary search if jumping backwards is expensive.

10. Best case of jump search will have time complexity of _________
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: a
Clarification: Best case of jump search will be when the first element of the array is the element that is being searched. In this case only one comparison will be required. Thus it will have a time complexity of O(1).

11. Which of the following code correctly represent jump search?
a)

int jumpSearch(int arr[], int x, int n) 
{ 
 
    int step = n*n; 
    int prev = 0; 
    while (arr[min(step, n)-1] < x) 
    { 
        prev = step; 
        step += sqrt(n); 
        if (prev >= n) 
            return -1; 
    } 
 
 
    while (arr[prev] < x) 
    { 
        prev++; 
 
 
        if (prev == min(step, n)) 
            return -1; 
    } 
 
    if (arr[prev] == x) 
        return prev; 
 
    return -1; 
}

b)

int jumpSearch(int arr[], int x, int n) 
{ 
 
    int step = sqrt(n); 
    int prev = 0; 
    while (arr[min(step, n)-1] < x) 
    { 
        prev = step; 
        step += sqrt(n); 
        if (prev >= n) 
            return -1; 
    } 
 
 
    while (arr[prev] < x) 
    { 
        prev++; 
 
 
        if (prev == min(step, n)) 
            return -1; 
    } 
 
    if (arr[prev] == x) 
        return prev; 
 
    return -1; 
}

c)

int jumpSearch(int arr[], int x, int n) 
{ 
 
    int step = sqrt(n); 
    int prev = 0; 
    while (arr[min(step, n)-1] < x) 
    { 
        prev = step; 
        step += sqrt(n); 
        if (prev == n) 
            return -1; 
    } 
 
 
    while (arr[prev] < x) 
    { 
        prev++; 
 
 
        if (prev == min(step, n)) 
            return -1; 
    } 
 
    if (arr[prev] == x) 
        return prev; 
 
    return -1; 
}

d)

int jumpSearch(int arr[], int x, int n) 
{ 
 
    int step = sqrt(n); 
    int prev = 0; 
    while (arr[min(step, n)-1] < x) 
    { 
        prev = step; 
        step += sqrt(n); 
        if (prev >= n) 
            return -1; 
    } 
 
 
    while (arr[prev] > x) 
    { 
        prev++; 
 
 
        if (prev == min(step, n)) 
            return -1; 
    } 
 
    if (arr[prev] == x) 
        return prev; 
 
    return -1; 
}

Answer: b
Clarification: The correct code first makes jumps until an element greater than the required element is found. Then linear search is performed in a backwards direction. If the element is not found then we return -1.

12. Jump search is worse than linear search in terms of time complexity.
a) True
b) False
Answer: b
Clarification: Linear search has a time complexity of O(n) and the time complexity of jump search is O(n^1/2). So jump search is better than linear search in terms of time complexity.

13. Jump search has a worst case time complexity of O(n).
a) True
b) False

Answer: b
Clarification: The time complexity of jump search is O(n^1/2) in worst and average case. It is due to the fact that size of optimal jump is n^1/2.

Data Structures & Algorithms Multiple Choice Questions on “Quicksort using Median of Three Partitioning”.

1. Quick sort uses which of the following algorithm to implement sorting?
a) backtracking
b) greedy algorithm
c) divide and conquer
d) dynamic programming
Answer: c
Clarification: Quick sort uses the technique of divide and conquer in order to sort a given array. It divides the array into two parts about the pivot and then applies quick sort to both the parts.

2. What is the median of three techniques in quick sort?
a) quick sort with random partitions
b) quick sort with random choice of pivot
c) choosing median element as pivot
d) choosing median of first, last and middle element as pivot

Answer: d
Clarification: In the median of three technique the median of first, last and middle element is chosen as the pivot. It is done so as to avoid the worst case of quick sort in which the time complexity shoots to O(n²).

3. What is the purpose of using a median of three quick sort over standard quick sort?
a) so as to avoid worst case time complexity
b) so as to avoid worst case space complexity
c) to improve accuracy of output
d) to improve average case time complexity

Answer: a
Clarification: Median of three quick sort helps in avoiding the worst case time complexity of O(n²) which occurs in case when the input array is already sorted. However, the average case and best case time complexities remain unaltered.

4. What is the auxiliary space complexity of a median of three quick sort?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: c
Clarification: Auxiliary space complexity of median of three quick sort is O(log n) which is used for storing call stack formed due to recursion. Note that the algorithms with space complexity as O(log n) also qualifies as in place algorithms as the value of log n is close to 1.

5. What is the average time complexity of the median of three quick sort?
a) O(n log n)
b) O(n²)
c) O(n² log n)
d) O(n log n²)

Answer: a
Clarification: The average case time complexity of median of three quick sort is the same as that of a standard quick sort as randomized quick sort only helps in preventing the worst case. It is equal to O(n log n).

6. Quick sort uses which of the following method to implement sorting?
a) merging
b) partitioning
c) selection
d) exchanging

Answer: b
Clarification: Quick sort makes partitions of the input array about the pivot in order to implement sorting. Thus its method of sorting is called partitioning.

7. Median of three quick sort is an in place sort.
a) true
b) false

Answer: a
Clarification: In-place algorithms require constant or very less auxiliary space. Median of three quick sort qualifies as an in-place sorting algorithm. It has a very low auxiliary space requirement of O(log n).

8. Median of three quick sort is a stable sort.
a) true
b) false

Answer: b
Clarification: Median of three quick sort like standard quick sort is also not a stable sorting algorithm. It is because the elements with the same values are not guaranteed to appear in the same relative order in the output sorted array.

9. What is the best case time complexity Median of three quick sort?
a) O(log n)
b) O(n log n)
c) O(n²)
d) O(n² log n)

Answer: b
Clarification: Best case time complexity is given in the case when there is equal partitioning of the array about the pivot. It is given by the relation T(n) = 2T(n/2) + n which gives the result O(n log n).

10. Which of the following function chooses a random index as the pivot?
a)

int Median(arr, left, right)
{
    int mid;
    mid = (left + right)/2
    if (arr[right] < arr[left]);
        Swap(arr, left, right); //to swap arr[left],arr[right]       
    if (arr[mid] < arr[left]);
        Swap(arr, mid, left);//to swap arr[left],arr[mid]
    if (arr[right] < arr[mid]);
        Swap(arr, right, mid);// to swap arr[right],arr[mid]
    return mid;
}

b)

int Median(arr, left, right)
{
    int mid;
    mid = (left + right)/2
    if (arr[right] > arr[left]);
        Swap(arr, left, right); //to swap arr[left],arr[right]       
    if (arr[mid] < arr[left]);
        Swap(arr, mid, left);//to swap arr[left],arr[mid]
    if (arr[right] < arr[mid]);
        Swap(arr, right, mid);// to swap arr[right],arr[mid]
    return mid;
}

c)

int Median(arr, left, right)
{
    int mid;
    mid = (left + right)/2
    if (arr[left] < arr[right]);
        Swap(arr, left, right); //to swap arr[left],arr[right]       
    if (arr[left] < arr[mid]);
        Swap(arr, mid, left);//to swap arr[left],arr[mid]
    if (arr[right] < arr[mid]);
        Swap(arr, right, mid);// to swap arr[right],arr[mid]
    return mid;
}

d)

int Median(arr, left, right)
{
    int mid;
    mid = (left + right)/2
    if (arr[right] < arr[left]);
        Swap(arr, left, right); //to swap arr[left],arr[right]       
    if (arr[left] < arr[mid]);
        Swap(arr, mid, left);//to swap arr[left],arr[mid]
    if (arr[mid] < arr[right]);
        Swap(arr, right, mid);// to swap arr[right],arr[mid]
    return mid;
}

Answer: a
Clarification: In the median of three quick sort the median of first, last and middle element is chosen. Then the chosen element is taken as a pivot. This helps in avoiding the worst case of O(n²).

11. What will be the pivot for the array arr={8,2,4,9} for making the first partition when a median of three quick sort is implemented?
a) 8
b) 2
c) 4
d) 9
Answer: a
Clarification: While making the first partition the first, last and middle elements will be 8, 9 and 2 respectively. Thus the median element will be 8.

contest