1

Midterm Sample

Name: … Neptun code: …

In exercises 1-3, do not write code: Illustrate the algorithms as you saw them in the classroom. In exercises 4-5, try to write efficient code (structure diagrams).

1. Illustrate the operation of insertion sort on the ⟨2, 8, 1, 5, 4, 5’⟩ array. Present the last insertion in detail. (8p)
2. Illustrate the operation of merge sort on the array ⟨7, 9, 2, 8, 1, 3, 7’⟩. Present the key comparisons of the last merge. (9p)
3. Illustrate the operation of quicksort on the array ⟨7, 2, 4, 2’, 1, 9, 8⟩. Assume that the partition() function always chooses the second element as the pivot. (9p)
   • Present the subarrays computed by each call of partition(A, p, r) in turn. The pivot must be distinguished with a ’+’ prefix. Example: 4,2,+5,8.
4. Pointer H refers to the header of an increasingly sorted H1L. Write a function sorted_H1L_insert(H, x), which inserts a new element with key x into the list if the list does not contain x. If the list contains key x, the list remains unaltered. The list remains an increasingly sorted H1L. MT(n) ∈ Θ(n), where n is the list’s length. The algorithm must not make more than n iterations. (12p)
5. Pointer H refers to the header of a nonempty unsorted C2L. Write a function remove_C2L_max(H), which removes an element with a maximal key from the list and returns the address of the element removed. T(n) ∈ Θ(n) where n is the length of the list. (12p)
   • List modifications must be made only through the procedures unlink(q), precede(q, r), and follow(p, q).