西安电子科技大学软件学院算法导论上机题practice 1

We highly encourage being environment friendly and trying all problems on your own.

1． Implement exercise 2.3-7.

2． Implement priority queue.

3． Implement Quicksort and answer the following questions. (1) How many

comparisons will Quicksort do on a list of n elements that all have the same value? (2) What are the maximum and minimum number of comparisons will Quicksort do on a list of n elements, give an instance for maximum and minimum case respectively.

4． Give a divide and conquer algorithm for the following problem: you are given two

sorted lists of size m and n, and are allowed unit time access to the ith element of each list. Give an O(lg m + lgn) time algorithm for computing the kth largest element in the union of the two lists. (For simplicity, you can assume that the elements of the two lists are distinct).