Datastructuren oefententamen
Tue Jun 24 00:05:27 CEST 2008

1a. Dit betekent dat er een constante c is en een constante n0, zodanig dat f(n) <= c * g(n), voor n >= n0. 

b. laat c gelijk zijn aan 6, en n0 gelijk aan 10. In dat geval is 
	f(n) <= c * n^2, voor n >= 10, en dus van orde O(n^2)
c. O(n^2), voor c=2 en n0 = 3, want:
 2n * i <= 2 * n^2 + 3
d. 10n log n = n^2

2a. Een binaire zoekboem bevat een waarde n, waarbij als linkerkind zich een boom bevindt met waarden < n, en als rechterkind zich een boom bevindt met waarden >= n.
b.

              5
         3        7
       2   4    6   8
      1              9
c. In-order traversal

d.
            1
                5
              2    8
                 6   9

e. Ja, voorbeeld zoals hierboven.

3a. Een heap is een binaire boom die voldoet aan de heap-eigenschap,
namelijk dat een element altijd kleiner of gelijk aan zijn kinderen is. De
wortel bevat dan het kleinste element.

b.
DATASTRUCTURE => ACDERSTU

            A
         D     C
        E S   R U
       T
c. O(n) = allemaal.

d. 
       1	1 mogelijkheid
     2   3	2 mogelijkheden (2 getallen, 2 mogelijke plaatsen)
   4  5 6	24 mogelijkheden (3 getallen, 4 mogelijke plaatsen)
------------------- *
 1 * 2 * 24 = 48 mogelijke heaps.

4a. Een binaire zoekboom met een hoogteverschil van maximaal 1 niveau tussen de elk willekeurig paar onderste bladen.

b. Er zijn verschillende mogelijkheden. Bijv. van klein naar groot.
Zolang 6 als root terecht komt zal de uiteindelijke boom zijn zoals in
het plaatje.

c. Een splay boom is een boom die het laatst gebruikte element (zij het
een zoek, toevoeg of verwijder operatie) tot wortel maakt dmv. rotaties.
Hierdoor zijn recentelijk gebruikte elementen gemiddeld sneller te vinden.

d. 39576, of 93576, of 39756, of 93756.

5a.
0: 10
1: 55 22 33
2: 12
3:
4:
5:
6:
7:
8:
9:
10: 42 20
11:

b.
0: 10
1: 33
2: 12
3: 22
4: 55
5:
6:
7:
8:
9:
10: 20
11: 42