Werkblad Datastructuren met antwoorden

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 kan alleen getallen opslaan
3. CEen statische array geeft tragere toegang via de index
4. DEen dynamische array slaat zijn elementen op in gekoppelde knopen zodat hij element voor element kan groeien

Wat is een cykel in een graaf?

1. AEen pad dat elke knoop bezoekt
2. BEen pad dat begint en eindigt in dezelfde knoop
3. CEen kant met gewicht nul
4. DEen knoop zonder kanten

Wat wordt in een representatie als adjacency list (buurlijst) van een graaf per knoop opgeslagen?

1. AEen rij van V Booleaanse waarden
2. BHet kortste pad naar elke andere knoop
3. CHet totale aantal kanten in de graaf
4. DEen lijst van de buurknopen

Een knoop in een binaire zoekboom heeft een rechtersubboom. Waar staat zijn inorder-opvolger?

1. AAltijd zijn ouder
2. BDe meest rechtse knoop van zijn linkersubboom
3. CAltijd zijn rechterkind
4. DDe meest linkse knoop van zijn rechtersubboom

Hoe lang duurt het zoeken naar een woord met lengte L in een trie met een vast alfabet?

1. AO(L × n)
2. BO(n), waarbij n het aantal woorden is
3. CO(log n), waarbij n het aantal woorden is
4. DO(L), onafhankelijk van hoeveel woorden er zijn opgeslagen

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

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

De tijdcomplexiteit van decrease-key in een binaire heap (als de positie van het element bekend is) is:

1. AO(n log n)
2. BO(log n)
3. CO(n)
4. DO(1)

De sleutels 5, 3, 8, 1 worden in deze volgorde in een lege, op een array gebaseerde binaire min-heap ingevoegd. Wat is de uiteindelijke array?

1. A[3, 1, 8, 5]
2. B[1, 3, 5, 8]
3. C[1, 5, 8, 3]
4. D[1, 3, 8, 5]