Werkblad Datastructuren met antwoorden

Hoe heet de queuebewerking die het element vooraan verwijdert?

1. AInsert
2. BDequeue
3. CPush
4. DEnqueue

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 botsing (collision) in een hashtabel?

1. ATwee gelijke sleutels worden twee keer opgeslagen
2. BEen sleutel kan helemaal niet worden gehasht
3. CDe tabel heeft geen geheugen meer
4. DTwee verschillende sleutels worden op dezelfde index afgebeeld

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

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

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

1. A4 5 2 3 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D5 4 3 2 1

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

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

Welk probleem van linear probing vermindert double hashing vooral?

1. ADe noodzaak van een hashfunctie
2. BPrimaire clustering, waarbij lange reeksen bezette plaatsen ontstaan
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

Hoe kun je met O(1) extra geheugen detecteren of een enkelvoudig gekoppelde lijst een cykel bevat?

1. ASla elke bezochte knoop op in een hash-set
2. BTel de knopen tot het aantal het lengteveld van de lijst overschrijdt
3. CVerplaats één pointer telkens één stap en een andere twee stappen en kijk of ze elkaar ontmoeten
4. DSorteer de lijst en zoek naar duplicaten