Werkblad Datastructuren met antwoorden

De diepte van een knoop in een boom is:

1. AHet aantal kanten van die knoop tot het diepste blad
2. BHet aantal kinderen van die knoop
3. CHet aantal knopen in zijn subboom
4. DHet aantal kanten van de wortel tot die knoop

Een graaf bestaat uit:

1. AAlleen sleutels en hashes
2. BAlleen een wortel en bladeren
3. CKnopen (vertices) verbonden door kanten
4. DRijen en kolommen

Welke datastructuur is het meest geschikt voor de functie "ongedaan maken" (undo) in een teksteditor?

1. AWachtrij (queue)
2. BHash-set
3. CGraaf
4. DStapel (stack)

Hoeveel geheugen gebruikt een adjacentiematrix voor een graaf met V knopen?

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

Hoeveel knopen heeft een perfecte binaire boom met hoogte h, waarbij de hoogte in kanten wordt geteld?

1. A2h + 1
2. Bh²
3. C2^h+1 − 1
4. D2^h

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 dynamische array
2. BEen gesorteerde array
3. CEen dubbel gekoppelde lijst
4. DEen enkelvoudig gekoppelde lijst

Je moet uit een stroom van n getallen de k kleinste waarden bewaren met O(k) geheugen. Welke aanpak werkt in O(n log k) tijd?

1. AEen gesorteerde array van alle n waarden
2. BEen FIFO-queue van de laatste k waarden
3. CEen max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt
4. DEen min-heap met alle n waarden, waaruit aan het eind de k kleinste worden gehaald

Hoe verbetert een radix tree (gecomprimeerde trie) een gewone trie?

1. AHij bewaart alleen de eerste letter van elk woord
2. BHij voegt ketens van knopen met één kind samen tot één kant met een string als label
3. CHij slaat elk woord op in een hashtabel bij de wortel in plaats van in aparte knopen
4. DHij sorteert de kinderen van elke knoop op frequentie