This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Pancake Sort”.
1. What is the time complexity for a given pancake sort given it undergoes “n” flip operations?
a) O(n)
b) O(n2)
c) O(n3)
d) O(2n)
View Answer
Explanation: Most sorting algorithms try to sort making the least number of comparisons but in pancake sort we try to sort using as few reversals as possible. Because the total number of flip operations performed in a pancake sort is O(n), the overall time complexity is O(n2).
2. Which operation is most essential to the process of pancake sort?
a) Flip the given data
b) Find the largest of given data
c) Finding the least of given data
d) Inserting something into the given data
View Answer
Explanation: When we use pancake sort, we sort the array to find the largest, and then flip the array at that point to bring that value to the bottom of the pancake stack. The size of the array that we are dealing with is then reduced and the process continues. Flip operation is the most important function in the pancake sort technique.
3. There is one small error in the following flip routine. Find out which line it is on.
1 void flip(int arr[], int i) 2 { 3 int t, init = 0; 4 while (init < i) 5 { 6 t = arr[init]; 7 arr[i] = arr[init] ; 8 arr[i] = t; 9 init++; 10 i--; 11 } 12 }
a) Line 3
b) Line 5
c) Line 7
d) Line 9
View Answer
Explanation: After initialization of the array titled arr; for each while loop iteration of increasing init, we should make arr[init]=arr[i]. This makes sure that the changes will be made in order to flip the order of the array that was to be flipped. Here in line 7 it has been written in reverse and is incorrect.
4. How many flips does the simplest of pancake sorting techniques require?
a) 3n−3 flips
b) 2n-4 flips
c) 2n-3 flips
d) 3n-2 flips
View Answer
Explanation: The minimum number of flips required to sort any stack of n pancakes has been shown to lie between 1.087n and 1.636n. using average of that 1.36n and extracting that for values of n>1. We have 1.36, 2.72, 4.08 etc. This matches best with 2n-3 which is equal to 1, 3, 5, 7, 9, etc. An upper bound of 2n-3 comes by iteratively using the next largest element in its correct place using two flips.
5. Pancake Sorting appears in which of the following?
a) Frequency Scaling
b) Storage Virtualization
c) Parallel Processing
d) Neural Networking
View Answer
Explanation: Pancake Sorting finds application in educational use not to mention parallel processing networks by providing optimal routing algorithms between networks.
6. In addition to the pancake sorting problem, there is the case of the burnt pancake problem in which we are dealing with pancakes (discs) that are burnt on one side only. In this case it is taken that the burnt side must always end up _______
a) Faced down
b) Faced up
c) It doesn’t matter
d) Both sides are burnt
View Answer
Explanation: A varation of this pancake is with burnt pancakes. Here each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom. It is a more difficult version of the regular pancake problem.
7. In a computational complexity theory, a problem with decision making is said to be NP-complete when it is both in NP and NP-hard. What does NP mean?
a) Non Polynomial time
b) Non-deterministic Probabilistic
c) Non-deterministic Polynomial time
d) Non Probabilistic time
View Answer
Explanation: Although any given solution to an NP-complete problem can be validated quickly in polynomial time; there is no way to efficiently locate a solution to begin with. The unique characteristic of NP-complete problems is that no fast solution to them is known and hence NP-complete problems are said to be non-deterministic polynomial time.
8. When we realize a specific implementation of a pancake algorithm, every move when we find the greatest of the sized array and flipping can be modeled through __________
a) Combinations
b) Exponential functions
c) Logarithmic functions
d) Permutations
View Answer
Explanation: Here when we flipping the array or stack, we have to take utmost priority to preserve the order of the list so that that sorting doesnt become invalid. Hence we use permutations, we are ensuring that order matters.
9. The Pancake Problems (1975, 1979, 1973) did NOT involve which of the following people?
a) Bill Gates
b) Jacob Goodman
c) Christos Papadimitriou
d) John Goodman
View Answer
Explanation: (Jacob Goodman – 1975) What is the maximum number of flips needed to sort a permutation of [n] into ascending order?
(Bill Gates and Christos Papadimitriou – 1979) What is the maximum number of flips needed to sort a signed permutation of [n] into ascending order with all positive signs?
10. There is a one line error in the following routine. Find that line.
1. int Max(int a[], int n) 2. { 3. int mi, i; 4. for (mi = 0, i = 0; i < n; i++) 5. if (a[i] > a[mi]) 6. mi = i; 7. return mi; 8. }
a) Line 2
b) Line 4
c) Line 6
d) Line 5
View Answer
Explanation: The increment condition in the for loop declaration is incorrect. We should use ++i instead of i++.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Programming MCQs
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Check Computer Science Books
- Check Design and Analysis of Algorithms Books
