This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Rotation Array Operation”.
1. What will be the resulting array after rotating arr[]={1, 2, 3, 4, 5} by 2?
a) 2, 1, 3, 4, 5
b) 3, 4, 5, 1, 2
c) 4, 5, 1, 2, 3
d) 1, 2, 3, 5, 4
View Answer
Explanation: When the given array is rotated by 2 then the resulting array will be
Rotation 1: {2,3,4,5,1}
Rotation 2: {3,4,5,1,2}.
Thus, the final array is {3,4,5,1,2}.
2. What will be the output of the following code?
#include <iostream> using namespace std; int main() { int arr[] = {1,2,3,4,5,6}; int n = sizeof(arr)/sizeof(arr[0]); int d=4; int temp[10]; for(int i=0;i<d;i++) temp[i]=arr[i]; int j=0; for(int i=d;i<n;i++,j++) arr[j]=arr[i]; int k=0; for(int i=n-d;i<n;i++,k++) arr[i]=temp[k]; for(int i=0;i<n;i++) cout<<arr[i]<<" "; return 0; }
a) 5 6 1 2 3 4
b) 6 5 4 3 1 2
c) 3 4 5 6 1 2
d) error
View Answer
Explanation: The given code rotates the given array by 4. It does so by using an array temp[] which stores the first d elements and then shift them to the end of the array. So the output will be 5 6 1 2 3 4.
3. What will be the time complexity of the following code?
#include <iostream> using namespace std; int main() { int arr[] = {1,2,3,4,5,6}; int n = sizeof(arr)/sizeof(arr[0]); int d=4; int temp[10]; for(int i=0;i<d;i++) temp[i]=arr[i]; int j=0; for(int i=d;i<n;i++,j++) arr[j]=arr[i]; int k=0; for(int i=n-d;i<n;i++,k++) arr[i]=temp[k]; for(int i=0;i<n;i++) cout<<arr[i]<<" "; return 0; }
a) O(d)
b) O(n)
c) O(n2)
d) O(n*d)
View Answer
Explanation: The given code rotates an input array by d. The longest loop in the code takes n iterations so the time complexity will be O(n).
4. What will be the auxiliary space complexity of the following code?
#include <iostream> using namespace std; int main() { int arr[] = {1,2,3,4,5,6}; int n = sizeof(arr)/sizeof(arr[0]); int d=4; int temp[10]; for(int i=0;i<d;i++) temp[i]=arr[i]; int j=0; for(int i=d;i<n;i++,j++) arr[j]=arr[i]; int k=0; for(int i=n-d;i<n;i++,k++) arr[i]=temp[k]; for(int i=0;i<n;i++) cout<<arr[i]<<" "; return 0; }
a) O(1)
b) O(n)
c) O(d)
d) O(n*d)
View Answer
Explanation: The given code rotates an input array by d. It does so by using an auxiliary array temp[] which stores first d elements of the original array. So the auxiliary space complexity will be O(d).
5. What will be the output of the following code?
#include <bits/stdc++.h> using namespace std; void func1(int arr[], int n) { int k = arr[0], i; for (i = 0; i < n - 1; i++) arr[i] = arr[i + 1]; arr[i] = k; } void func(int arr[], int d, int n) { for (int i = 0; i < d; i++) func1(arr, n); } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; } int main() { int arr[] = { 1, 2, 3, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); func(arr, 3, n); printArray(arr, n); return 0; }
a) 4 5 1 2 3
b) 3 4 5 1 2
c) 5 4 3 1 2
d) error
View Answer
Explanation: The given code rotates the input array by 3. It does so by rotating the elements one by one until the desired rotation is achieved. So the output will be 4 5 1 2 3.
6. What will be the time complexity of the following code?
#include <bits/stdc++.h> using namespace std; void func1(int arr[], int n) { int k = arr[0], i; for (i = 0; i < n - 1; i++) arr[i] = arr[i + 1]; arr[i] = k; } void func(int arr[], int d, int n) { for (int i = 0; i < d; i++) func1(arr, n); } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; } int main() { int arr[] = { 1, 2, 3, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); int d = 3; func(arr, d, n); printArray(arr, n); return 0; }
a) O(n*d)
b) O(n)
c) O(d)
d) O(n2)
View Answer
Explanation: The given code rotates the input array by d. It does so by rotating the elements one by one until the desired rotation is achieved. Each element takes O(n) time for rotation and there are d such elements in the array. So the time complexity would be O(n*d).
7. What will be the auxiliary space complexity of the following code?
#include <bits/stdc++.h> using namespace std; void func1(int arr[], int n) { int k = arr[0], i; for (i = 0; i < n - 1; i++) arr[i] = arr[i + 1]; arr[i] = k; } void func(int arr[], int d, int n) { for (int i = 0; i < d; i++) func1(arr, n); } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; } int main() { int arr[] = { 1, 2, 3, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); int d = 3; func(arr, d, n); printArray(arr, n); return 0; }
a) O(1)
b) O(n)
c) O(d)
d) O(n*d)
View Answer
Explanation: The given code rotates the input array by d. It does so by rotating the elements one by one until the desired rotation is achieved. It does not require any auxiliary array for this purpose. So the auxiliary space complexity will be O(1).
8. To rotate an array by using the algorithm of rotating its elements one by one is an in place algorithm.
a) true
b) false
View Answer
Explanation: The auxiliary space requirement of the mentioned algorithm is O(1). So it qualifies to be an in place algorithm.
9. What will be the output of the following code?
#include <bits/stdc++.h> using namespace std; void func1(int arr[], int left, int right) { while (left < right) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } } void func(int arr[], int d, int n) { func1(arr, 0, d-1); func1(arr, d, n-1); func1(arr, 0, n-1); } void printArray(int arr[], int size) { for (int i = 0; i < size; i++) cout << arr[i] << " "; } int main() { int arr[] = {1, 2, 3, 4, 5}; int n = sizeof(arr)/sizeof(arr[0]); int d = 2; func(arr, d, n); printArray(arr, n); return 0; }
a) 3 2 1 4 5
b) 3 4 5 1 2
c) 5 4 3 2 1
d) error
View Answer
Explanation: The given code rotates the input array by 2. It does so by applying a reversal algorithm to different segments of the array. First d elements and the rest of the array is reversed individually. Then the whole array is reversed which gives us the desired rotated array. So the output will be 3 4 5 1 2.
10. What will be the auxiliary space complexity of the code to rotate an array by using the reversal algorithm (d = number of rotations)?
a) O(1)
b) O(n)
c) O(d)
d) O(n*d)
View Answer
Explanation: The reversal algorithm for rotating an array does not require any auxiliary space. So the auxiliary space complexity will be O(1).
11. Which of the following is the predefined function for array reversal in C++?
a) rotate()
b) arr_rotate()
c) array_rotate()
d) rot()
View Answer
Explanation: The predefined function for rotating an array is rotate() in C++. It is defined under the library algorithm and requires 3 arguments.
12. How many arguments are required by the predefined function rotate() in C++?
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: The predefined function for rotating an array is rotate() in C++ which comes under the library called an algorithm. It requires 3 arguments.
13. Predefined function rotate() in C++ is available under which header file?
a) math
b) stdio
c) stdlib
d) algorithm
View Answer
Explanation: The predefined function for rotating an array is rotate() in C++ which comes under the library called algorithm. It requires 3 arguments the first being the pointer to the starting index of the array and the last being the pointer to the last index of the array. The middle argument is the pointer to the element that becomes the first element in the rotated array.
14. Which of the following algorithm to rotate an array has the maximum time complexity?
a) rotate elements one by one
b) juggling algorithm
c) reversal algorithm
d) using a temporary array
View Answer
Explanation: The maximum time complexity is required by the algorithm that rotates elements one by one. It requires O(n*d) time.
15. What is the time complexity of the juggling algorithm to rotate an array?
a) O(1)
b) O(n)
c) O(d)
d) O(n*d)
View Answer
Explanation: Time complexity of juggling algorithm is O(n). Its auxiliary space complexity is O(1).
16. Reversal algorithm and juggling algorithm for array rotation have the same time complexity.
a) True
b) False
View Answer
Explanation: Time complexity of juggling algorithm is O(n) which like that of reversal algorithm. They also have the same space complexity.
Sanfoundry Global Education & Learning Series – Data Structure.
To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Practice Design & Analysis of Algorithms MCQ
- Check Programming Books
- Apply for Computer Science Internship
- Practice Programming MCQs
- Practice Computer Science MCQs
