Datastructuren: oefenvragen met uitleg

1Wat een datastructuur is

Een datastructuur is een manier om gegevens in het geheugen te ordenen zodat bepaalde bewerkingen snel zijn: een item vinden, er een toevoegen, er een verwijderen.

Geen enkele structuur is overal snel in. Een structuur kiezen betekent kiezen welke bewerkingen goedkoop moeten zijn. De kosten ervan schrijf je in grote O, waarbij n het aantal items is.

De twee basisbouwstenen zijn de array en de gelinkte lijst.

Een array slaat zijn items in één blok geheugen op, na elkaar. De computer kan uitrekenen waar item i staat, dus het lezen van a[i] kost O(1). Vooraan invoegen betekent elk item opschuiven: O(n).

Een gelinkte lijst slaat elk item op in een knoop (node) met een pointer naar de volgende knoop. De laatste pointer is null. Invoegen aan de kop (h) verandert maar één pointer: O(1). Maar om item i te bereiken moet je i pointers volgen: O(n).

Een dubbel gelinkte lijst heeft ook een pointer naar de vorige knoop, zodat je in beide richtingen kunt lopen.

2Stacks en queues

Een stack (stapel) is als een stapel borden: je voegt alleen bovenaan toe en haalt alleen bovenaan weg. Het laatste item dat erin gaat, komt er als eerste uit: LIFO.

• push legt een item bovenop, pop haalt het bovenste item weg, peek leest het bovenste zonder het weg te halen. Alle drie zijn O(1).
• Toepassingen: de ongedaanmaken-functie van een editor, de aanroepstapel van een programma, controleren of haakjes in balans zijn, depth-first search.

Een queue (wachtrij) is als een rij bij de kassa: je sluit achteraan aan en vertrekt vooraan. Het eerste item dat erin gaat, komt er als eerste uit: FIFO.

• enqueue voegt achteraan toe, dequeue haalt vooraan weg. Beide zijn O(1).
• Toepassingen: printopdrachten, berichten die wachten om verwerkt te worden, breadth-first search.

Een deque (double-ended queue) laat toevoegen en weghalen aan beide uiteinden toe. Een prioriteitswachtrij haalt altijd eerst het item met de hoogste prioriteit weg; ze wordt meestal gebouwd als een heap.

3Bomen, heaps, hashtabellen en grafen

Een boom heeft één bovenste knoop, de wortel (root). Elke andere knoop heeft precies één ouder. Knopen zonder kinderen zijn bladeren. Een boom met n knopen heeft n − 1 takken.

In een binaire boom heeft elke knoop hooguit twee kinderen. Een binaire zoekboom (BST) voegt een regel toe: sleutels in de linkerdeelboom zijn kleiner dan de knoop, sleutels in de rechterdeelboom zijn groter.

Zoeken in een BST volgt één pad naar beneden, dus het kost O(hoogte). Een gebalanceerde boom (AVL, rood-zwart) houdt de hoogte dicht bij log₂ n. Sleutels die in gesorteerde volgorde worden ingevoegd, maken een keten met hoogte n.

Een heap is een binaire boom waarin elke ouder kleiner is dan zijn kinderen (min-heap) of groter (max-heap). Het minimum of maximum staat in de wortel, en invoegen en verwijderen kosten O(log n).

Een hashtabel slaat sleutel–waardeparen op. Een hashfunctie zet de sleutel om in een index, zodat invoegen en opzoeken gemiddeld O(1) kosten. Twee sleutels met dezelfde index vormen een botsing (collision), die je oplost met chaining (een lijst per plek) of open adressering (een andere plek proberen).

Een graaf heeft hoekpunten die met bogen (edges) verbonden zijn, die een richting of een gewicht kunnen hebben. Hij wordt opgeslagen als een aangrenzendheidsmatrix, O(V²) geheugen, of als aangrenzendheidslijsten, O(V + E).

4De methode stap voor stap

Vragen beschrijven vaak een taak en vragen welke structuur past, of vragen hoe een structuur eruitziet na enkele bewerkingen.

1. Zoek de bewerking die snel moet zijn: toegang op positie, op sleutel, het nieuwste item, het oudste item, het kleinste item, of een bereik.
2. Koppel die aan een structuur: index → array, sleutel → hashtabel, nieuwste → stack, oudste → queue, kleinste of grootste → heap, gesorteerde volgorde of bereiken → gebalanceerde zoekboom.
3. Controleer de kosten van de andere bewerkingen die de taak nodig heeft, in grote O.
4. Voer bij een traceervraag de bewerkingen een voor een uit en noteer de toestand na elke stap.
5. Controleer de eindtoestand aan de regel van de structuur: LIFO, FIFO, de BST-volgorde of de heap-volgorde.

5Een uitgewerkt voorbeeld

Volg elke stap. Probeer de volgende stap te voorspellen voordat je hem opent.

6Veelgemaakte fouten

• LIFO en FIFO door elkaar halen. Een stack geeft het nieuwste item terug, een queue het oudste.
• Denken dat een gelinkte lijst snelle toegang via index geeft. Je moet vanaf de kop lopen.
• Aannemen dat een BST altijd O(log n) is. Alleen een gebalanceerde boom is dat; gesorteerd invoegen geeft O(n).
• Botsingen in een hashtabel vergeten. O(1) is het gemiddelde, niet het slechtste geval.
• De doorlopen door elkaar halen. Preorder: knoop eerst. In-order: knoop in het midden. Postorder: knoop laatst.
• Een aangrenzendheidsmatrix gebruiken voor een grote ijle graaf. Dat verspilt O(V²) geheugen.

7Hoe tentamenvragen eruitzien

• Makkelijk: kernbegrippen en feiten. LIFO en FIFO, wat een knoop, wortel of blad is, de BST-regel, wat een hashfunctie doet.
• Gemiddeld: concepten toepassen. Welke structuur bij een taak past, het resultaat van push en pop of van BST-invoegingen, boomdoorlopen, een hashtabel met lineair zoeken, kosten in grote O.
• Moeilijk: gevallen en analyse. Gebalanceerde bomen, heaps in arrays, B-bomen, tries, union-find, Bloom-filters en ontwerpen zoals een LRU-cache.

Bij een heap die vanaf index 0 in een array is opgeslagen, staan de kinderen van index i op 2i + 1 en 2i + 2, en staat de ouder op ⌊(i − 1) / 2⌋.