Data Structure教学课件（华南理工）Tutorial05 ans.pdfVIP

Data Structure (Semester 1, 2014-2015) Tutorial 05 - Answer Prepared by Dr. Patrick Chan Date: November-2014 1. Which of the following operations can be performed faster on sorted data than on unsorted data? i) Finding an item with a minimum value ii) Computing an average of values iii) Finding the median iv) Finding the value which appears most frequently in the data Answer: i) yes ii) no iii) yes iv) no 2. In out implementation of bubble sort, a sorted array was scanned bottom-up to bubble up the smallest element. Write a program which scans top-down to bubbles down the largest element. Answer: template class Elem, class Comp void bubsort(Elem A[], int n) { for (int i=0; in-1; i++) for (int j=0; jn-1-i; j++) if (Comp::gt(A[j], A[j+1])) swap(A, j, j+1); } 3. The cocktail shaker sort designed by Donald Knuth is a modification of bubble sort in which the direction of bubbling changes in each iteration. In first iteration, the smallest element is bubbled up; in the next, the largest is bubbled down; in the next, the second smallest is bubbled up; and so forth. Implement this new algorithm. Answer: template class Elem, class Comp void cocktailsort(Elem A[], int n) { for (int i=0; i(n-1)/2; i++) { for (int j=n-1; ji; j--) if (Comp::lt(A[j], A[j-1])) swap(A, j, j-1); for (int j=i+1; jn-1-i; j++) if (Comp::gt(A[j], A[j+1])) swap(A, j, j+1); } } Data Structure – Tutorial 5 1 4. Give a permutation