Werkblad Datastructuren met antwoorden

Een graaf bestaat uit:

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

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

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

Wat doet de bewerking peek (of top) op een stack?

1. AGeeft het onderste element van de stack terug
2. BGeeft het bovenste element terug zonder het te verwijderen
3. CVerwijdert het bovenste element en geeft het terug
4. DVerwijdert alle elementen van de stack

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

Een queue wordt geïmplementeerd met twee stacks: push op een "in"-stack en pop van een "out"-stack, die vanuit "in" wordt bijgevuld als hij leeg is. Wat zijn de geamortiseerde kosten per bewerking?

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

In een binaire min-heap die in een array is opgeslagen (index begint bij 0), staan de kinderen van de knoop op index i op:

1. Ai + 1 en i + 2
2. B2i en 2i + 1
3. Ci/2 en i/2 + 1
4. D2i + 1 en 2i + 2

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

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

Welk probleem van linear probing vermindert double hashing vooral?

1. APrimaire clustering, waarbij lange reeksen bezette plaatsen ontstaan
2. BDe noodzaak van een hashfunctie
3. CDe O(n)-kosten van het lezen van de waarde van een sleutel
4. DDe noodzaak om sleutels in de tabel op te slaan