Werkblad Datastructuren met antwoorden

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

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

Hoe worden de elementen van een array in het geheugen opgeslagen?

1. AIn één aaneengesloten blok, na elkaar
2. BIn een boom van geheugenpagina's
3. CVerspreid, verbonden door pointers
4. DOp willekeurige plaatsen gekozen door een hash

Wat zijn broer- of zusknopen (siblings) in een boom?

1. AEen knoop en zijn ouder
2. BKnopen die dezelfde ouder hebben
3. CKnopen op dezelfde diepte in verschillende subbomen
4. DKnopen zonder kinderen

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

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

Hoe werkt extract-min in een binaire min-heap?

1. AVerwijder het laatste element van de array
2. BZoek in alle bladeren naar het nieuwe minimum
3. CVerwijder de wortel en schuif alle elementen één plaats naar links
4. DVerplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)

Hoeveel geheugen gebruikt een adjacency list voor een graaf met V knopen en E kanten?

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

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 gesorteerde array die door verschuiven wordt bijgewerkt
3. CEen enkelvoudig gekoppelde lijst van de elementen in het venster
4. DEen deque met indices in afnemende volgorde van waarde

In de BST met wortel 50, linkersubboom 30 (kinderen 20, 40) en rechtersubboom 70 (kinderen 60, 80) wordt de wortel verwijderd met behulp van de inorder-opvolger. Welke sleutel wordt de nieuwe wortel?

1. A40
2. B60
3. C80
4. D70