Werkblad Datastructuren met antwoorden

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

1. AHet aantal kanten op het langste pad van de wortel naar een blad
2. BHet totale aantal knopen in de boom, inclusief de wortel en elk blad
3. CHet aantal bladeren in de boom
4. DHet aantal kinderen van de wortel

Wat doet een hashfunctie in een hashtabel?

1. ATelt hoeveel sleutels er zijn opgeslagen
2. BVersleutelt de waarden in de tabel
3. CSorteert de sleutels in de tabel
4. DBeeldt een sleutel af op een index in de tabel

Wat is een blad in een boom?

1. ADe knoop met de grootste waarde
2. BEen knoop zonder kinderen
3. CEen knoop met precies één kind
4. DEen knoop zonder ouder

Welke datastructuur gebruikt diepte-eerst zoeken (DFS) in de iteratieve versie?

1. AAlleen een hashtabel
2. BEen queue
3. CEen stack
4. DEen heap

Een hashtabel van grootte 7 gebruikt h(k) = k mod 7 en linear probing. Waar wordt 17 opgeslagen nadat 10 is ingevoegd?

1. AIndex 0
2. BIndex 4
3. CIndex 6
4. DIndex 3

Welk abstract datatype gebruikt het algoritme van Dijkstra om de volgende te verwerken knoop te kiezen?

1. AEen stack
2. BEen min-prioriteitswachtrij
3. CEen set zonder ordening
4. DEen FIFO-queue

Een segmentboom (segment tree) wordt doorgaans gebruikt om:

1. ABereikquery's (zoals bereiksommen) en updates in O(log n) te beantwoorden
2. BDe kanten van een graaf op te slaan
3. CStrings alfabetisch te sorteren door elk voorvoegsel in een aparte boomknoop op te slaan
4. DEen stack te implementeren

Welke uitspraak over heapsort is juist?

1. AHet draait op elke invoer in O(n) tijd
2. BHet heeft een binaire zoekboom nodig als extra opslag, dus het gebruikt O(n) extra geheugen
3. CHet sorteert ter plaatse in O(n log n) in het slechtste geval, maar is niet stabiel
4. DHet is stabiel en heeft O(n) extra geheugen nodig