Note, these answers are quite rough! Please get in touch if you need
more detail about one of the questions.

Q1.

For a 3, O(n log n)

For a 4, the insertions take O(m log m) time.
There are n membership tests and the tree will have m
elements so that part takes O(n log m) time.
The total is O((m+n) log m).

For a 5, using the complexity above, it goes faster
if you minimise m (the size of the tree).
So case b is faster.

Q2.

For a 3: sort the array, then add up the first k elements.

For a 4: use a max heap. The idea is the heap will
contain the k smallest elements we have seen so far.
Pseudocode:
  h = new max-heap
  for each x in array
    add x to h
    if the size of h is > k then
      delete max element from h
  sum all elements of h

Q3.

For a 3:
Use (e.g.) an AVL tree. new(), insert(), member() and delete()
just use the AVL tree operations. deleteLessThan(x) works like so:
  while the tree contains an element y less than x
    delete y
where to find an element less than x in a tree t you do like this:
  if t == null
    no element found
  else if t.value < x
    return t.value
  else
    recursively search in t.left

For a 4:
(It turned out this part of the question could only be answered by
Chalmers students. GU students got "upgraded" from G to VG as a result.)

Use a splay tree. new(), insert(), member() and delete() work as
before. deleteLessThan(x) works like so:
  Find the smallest element y >= x
  Use the splay operation to put y at the root
  Delete the left child of the root

Q4.

a.
I've marked the red nodes with [square brackets]:

                53
          
          37         [78]

       [37]       66      91

               [62][72]     [95]

There are two black nodes on each path from the root.

b.

It's quite a substantial change, you get:
                66
          
           53         78 

        37   62   72      91

       37   60             95

You can try for yourself by going to
http://people.ksp.sk/~kuko/bak/,
selecting Red-black tree and inserting the elements of the original
tree top-to-bottom left-to-right.

Q5.

data will contain {f, g, blank, blank, e}
front will be 4
rear will be 2

Q6.

a.
It prints out {0,1,3,3,3,4,5,5,6,7}.

b.
The function sorts the array (provided that all elements of the array
are between 0 and m-1).