Question 1: Consider the pseudo-code below. Which sort algorithm is it? Indentation in the pseudo-code represents blocks of code, so imagine curly brackets around every indent level. Hint: the algorithm will not look exactly the same as shown in the slides, so you may want to trace the "code" on a simple list, like [ 4 1 3 2 ], to determine which algorithm it is.
void sort(T *array, int n)
{
for loop from i = 1 up to and including n-1
for loop from j = i down to and including 1
if array[j-1] > array[j]
swap array[j-1] and array[j]
else
break }
a) Selection sort
b) Insertion sort
c) Bubble sort
d) Merge sort
e) Quick sort
Question 2: Which sorting algorithm repeatedly splits the array in half until each part of the array only has one element? a) Selection sort
b) Insertion sort
c) Bubble sort
d) Merge sort
e) Quick sort
Question 3: Which sorting algorithm loops over the array, picks the smallest one, and puts it in the first slot, then repeats on the sub-array starting with the second element?
a) Selection sort
b) Insertion sort
c) Bubble sort
d) Merge sort
e) Quick sort
Question 4: Which sorting algorithm relies on a partitioning step to put small values on the left and big values on the right? a) Selection sort
b) Insertion sort
c) Bubble sort
d) Merge sort
e) Quick sort
Question 5: Which sorting algorithms are fastest (in big-O notation) on random data? a) Selection sort
b) Insertion sort
c) Bubble sort
d) Merge sort
e) Quick sort
Question 6: Which two sorting algorithms are fastest (in big-O notation) on already-sorted data? a) Selection sort
b) Insertion sort
c) Bubble sort
d) Merge sort
e) Quick sort
Question 7: If you are sorting 1,000,000 elements and your computer can process 1,000,000 instructions per second, how much time does merge sort save compared to selection sort? a) None; selection sort is actually faster than merge sort.
b) None; they take about the same amount of time.
c) A few seconds.
d) A few minutes.
e) A few days.
f) Hundreds of years.
Question 8: Which of the following options are true of array lists? (Select all that apply). In this question and the next, consider "fast" to refer to constant time O(1)rather than to linear time O(n) or slower. a) Array list getters are fast at the beginning of the list.
b) Array list getters are fast at the end of the list.
c) Array list getters are fast in the middle of the list.
d) Array list insert and remove at the beginning of the list are fast.
e) Array list insert and remove at the end of the list are fast.
f) Array list insert and remove in the middle of the list are fast.
g) Array list numElements is fast.
Question 9: Which of the following options are true of linked lists? (Select all that apply). Consider a standard linked list with no tail pointer or previous pointers. a) Linked list getters are fast at the beginning of the list.
b) Linked list getters are fast at the end of the list.
c) Linked list getters are fast in the middle of the list.
d) Linked list insert and remove at the beginning of the list are fast.
e) Linked list insert and remove at the end of the list are fast.
f) Linked list insert and remove in the middle of the list are fast.
g) Linked list numElements is fast.
Question 10: Consider the following function that uses the abstract List class. Based on how the list is used, which implementation (array list or linked list) would be a better choice? C++
void f(List &list)
{
list.insert(0, "Hello");
list.insert(1, "World");
list.insert(2, "!");
for(int i = 0; i < 1000000; i++)
cout << list.get(i % list.numElements()) << endl; }
a) Array list
b) Linked list
c) Either one is a good choice; neither will be significantly faster
d) Neither one, just instantiate the abstract list class
Question 11: Consider the following function that uses the abstract List class. Based on how the list is used, which implementation (array list or linked list) would be a better choice? C++
voidf(List&list)
{
for(inti=0;i<1000000;i++)
list.insert(0,i);}
a) Array list
b) Linked list
c) Either one is a good choice; neither will be significantly faster
d) Neither one, just instantiate the abstract list class