CS计算机代考程序代写 data structure algorithm EECS281 Data Structures and Algorithms

EECS281 Data Structures and Algorithms
Sorting Questions for Midterm Review

1) The following are multiple choice questions. Only one answer is correct. Circle the correct
answer. Each problem is worth 2 pts.

For the best implementation of bubble sort discussed in class, an approximation of the number of
comparisons and exchanges to sort an array of size N is:
a) N2/4 comparisons, N2/4 exchanges b) N2/2 comparisons, N2/2 exchanges
c) N2/2 comparisons, N2/4 exchanges d) N2/4 comparisons, N2/2 exchanges
e) N2/2 comparisons, N exchanges

For the best implementation of selection sort discussed in class, an approximation of the number of
comparisons and exchanges to sort an array of size N is:
a) N2/4 comparisons, N2/4 exchanges b) N2/2 comparisons, N2/2 exchanges
c) N2/2 comparisons, N2/4 exchanges d) N2/4 comparisons, N2/2 exchanges
e) N2/2 comparisons, N exchanges

For the best implementation of insertion sort discussed in class, an approximation of the number of
comparisons and exchanges to sort an array of size N is:
a) N2/4 comparisons, N2/4 exchanges b) N2/2 comparisons, N2/2 exchanges
c) N2/2 comparisons, N2/4 exchanges d) N2/4 comparisons, N2/2 exchanges
e) N2/2 comparisons, N exchanges

For the implementation of quick sort discussed in class, the worst case complexity for sorting an array
of size N is:
a) O(1) b) O(logN) c) O(N) d) O(NlogN) e) O(N2) f) O(2N)

For the implementation of quick sort discussed in class, the average case complexity for sorting an
array of size N is:
a) O(1) b) O(logN) c) O(N) d) O(NlogN) e) O(N2) f) O(2N)

For the implementation of heap sort discussed in class, the worst case complexity for sorting an array
of size N is:
a) O(1) b) O(logN) c) O(N) d) O(NlogN) e) O(N2) f) O(2N)

For the implementation of a heap discussed in class, the worst case complexity for inserting a single
item into the heap of size N is:
a) O(1) b) O(logN) c) O(N) d) O(NlogN) e) O(N2) f) O(2N)

2) Assume the following pseudocode implementation of Partition and QuickSort:

Algorithm Partition(a, left, right)
Input: array a of distinct elements, integers left and right
Output: integer
p <- a[right], lhs <- left, rhs <- right-1 while lhs ≤ rhs do while lhs ≤ rhs and a[lhs] ≤ p do lhs = lhs + 1 while rhs ≥ lhs and a[rhs] ≥ p do rhs = rhs -1 if lhs < rhs then swap(a[lhs],a[rhs]) swap(a[lhs],a[right]) return lhs Algorithm QuickSort(a[], left, right) Input: array a of distinct elements, integers left and right Output: sorted array a if left ≥ right then return pivot <- Partition(a, left, right) QuickSort(a, left, pivot-1) QuickSort(a, pivot+1, right) Show the effect of QuickSort on the following array a. Show the array after each call to Partition and indicate the final placement of pivots. a = {13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21} • gray box indicates pivot placement • following solution assumes recursion down lhs and rhs subtrees proceeds concurrently Init 13 19 9 5 12 8 7 4 11 2 6 21 It1 13 19 9 5 12 8 7 4 11 2 6 21 It2 2 4 5 6 12 8 7 19 11 13 9 21 It3 2 4 5 6 7 8 9 19 11 13 12 21 It4 2 4 5 6 7 8 9 11 12 13 19 21 It5 2 4 5 6 7 8 9 11 12 13 19 21 Itn 2 4 5 6 7 8 9 11 12 13 19 21 3) Assume that Quicksort uses the last item in the list as the pivot (as described earlier): a) Give a list of 10 integers representing the worst-case scenario. Any example with already sorted data, e.g., a = {1,2,3,4,5,6,7,8,9,10} b) Give a list of 10 integers representing the best-case scenario. Any example with pivot as median of each partition, e.g., a = {2,1,5,4,3,7,8,10,9,6} Note this problem is difficult to show exact correct answer 4) Text, Problem C-10.10, Page 528. For simplicity, assume that each candidate receives a unique number of votes. The function description is as follows: Algorithm findPrez(S,n) Input: integer array S of size n, integer n Output: integer winner QuickSort(S, 0, n-1) //assume we use Quicksort found later in homework. Note QuickSort() is O(n2) worst case. Therefore, might want to use O(nlgn) best/avg/worst case sorting algorithm, like mergesort or heapsort. contender <- S[0] votes <- 1 maxvotes <- 1 for i <- 1 to n-1 do //O(n) if S[i] = contender then votes <- votes + 1 else if votes > maxvotes then
maxvotes <- votes winner <- contender contender <- S[i] votes <- 1 Idea is as follows: • sort S using O(nlgn) sort • find S[i] with most occurrences in sorted S