Werkblad Datastructuren met antwoorden

Wat bevat in een enkelvoudig gekoppelde lijst de next-pointer van de laatste knoop?

1. AHet adres van de vorige knoop
2. BNull (geen knoop)
3. CHet aantal knopen in de lijst
4. DHet adres van de eerste knoop

Wat is het belangrijkste verschil tussen een statische en een dynamische array?

1. AEen dynamische array kan groeien door naar een groter geheugenblok te verhuizen
2. BEen statische array geeft tragere toegang via de index
3. CEen statische array kan alleen getallen opslaan
4. DEen dynamische array slaat zijn elementen op in gekoppelde knopen zodat hij element voor element kan groeien

Welke bewerking is O(1) voor een array maar O(n) voor een enkelvoudig gekoppelde lijst?

1. AHet eerste element lezen
2. BHet element op index i benaderen
3. CInvoegen aan de kop
4. DHet kopelement verwijderen

Je hebt een verwijzing naar een knoop in het midden van een lijst. In welke lijst kun je die in O(1) verwijderen?

1. AEen enkelvoudig gekoppelde lijst
2. BEen dubbel gekoppelde lijst
3. CEen dynamische array
4. DEen gesorteerde array

Een binaire boom heeft wortel 1 met linkerkind 2 en rechterkind 3; knoop 2 heeft kinderen 4 (links) en 5 (rechts). Wat is de postorder-doorloop?

1. A5 4 3 2 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D4 5 2 3 1

Wat gebeurt er als een hashtabel rehasht nadat de load factor een drempel overschrijdt?

1. AAlleen de botsende sleutels worden naar een nieuwe overloop-lijst aan het eind van de tabel verplaatst
2. BDe bestaande sleutels worden ter plaatse gesorteerd
3. CDe oudste sleutels worden verwijderd om ruimte te maken
4. DEr wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd

Het algoritme van Kahn voor topologisch sorteren verwijdert herhaaldelijk knopen met ingraad 0. Welke structuur bevat die knopen?

1. AEen max-heap geordend op uitgraad
2. BEen adjacency matrix die bijhoudt welke knopen al zijn verwijderd
3. CEen stack van alle bezochte kanten
4. DEen queue (of een willekeurige verzameling) van knopen met ingraad 0

Wat is de looptijd van breadth-first search op een graaf met V knopen die als adjacency matrix is opgeslagen?

1. AO(V)
2. BO(V + E)
3. CO(V²)
4. DO(E log V)