Werkblad Datastructuren met antwoorden

Welke datastructuur werkt volgens het principe "last in, first out" (LIFO)?

1. AGekoppelde lijst
2. BHashtabel
3. CWachtrij (queue)
4. DStapel (stack)

Wat is in een ongerichte graaf de graad van een knoop?

1. AHet aantal knopen in de graaf
2. BDe positie in de adjacency list
3. CHet aantal kanten dat ermee verbonden is
4. DDe lengte van het langste pad vanaf die knoop

Wat is de bezettingsgraad (load factor) van een hashtabel?

1. ADe tijd die nodig is om de tabel van schijf te laden
2. BHet aantal botsingen tot nu toe
3. CHet aantal buckets gedeeld door de gemiddelde lengte van de opgeslagen sleutels
4. DHet aantal opgeslagen elementen gedeeld door het aantal buckets

Welk abstract datatype gebruikt het algoritme van Dijkstra om de volgende te verwerken knoop te kiezen?

1. AEen min-prioriteitswachtrij
2. BEen set zonder ordening
3. CEen stack
4. DEen FIFO-queue

Wat is het doel van een sentinelknoop (dummyknoop) in een gekoppelde lijst?

1. AVoorkomen dat de lijst groeit voorbij een vast maximumaantal knopen
2. BDe lijst gesorteerd maken
3. CHet aantal elementen opslaan
4. DDe code vereenvoudigen door speciale gevallen aan kop of staart weg te nemen

AVL-bomen en rood-zwartbomen garanderen:

1. ADat sleutels in invoegvolgorde worden opgeslagen
2. BDat geen enkele knoop twee kinderen heeft
3. CEen hoogte van O(log n) door herbalancering
4. DZoeken in constante tijd in elk geval

Wat doet een splay tree na elke toegang?

1. AVerplaatst de benaderde knoop naar een blad
2. BBouwt de hele boom gebalanceerd opnieuw op
3. CKleurt de knopen op het zoekpad opnieuw
4. DRoteert de benaderde knoop omhoog naar de wortel

Met welke structuur bereken je het maximum van elk venster van grootte k in een array in totaal O(n)?

1. AEen min-heap die voor elk venster opnieuw wordt opgebouwd
2. BEen enkelvoudig gekoppelde lijst van de elementen in het venster
3. CEen deque met indices in afnemende volgorde van waarde
4. DEen gesorteerde array die door verschuiven wordt bijgewerkt