Werkblad Datastructuren met antwoorden

Wat is een botsing (collision) in een hashtabel?

1. ADe tabel heeft geen geheugen meer
2. BTwee gelijke sleutels worden twee keer opgeslagen
3. CTwee verschillende sleutels worden op dezelfde index afgebeeld
4. DEen sleutel kan helemaal niet worden gehasht

Wat is een blad in een boom?

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

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

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

Een trie (prefixboom) is bijzonder efficiënt voor:

1. AKortste paden vinden
2. BZoeken op prefix, zoals automatisch aanvullen
3. CGetallen sorteren
4. DMatrices opslaan

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

1. AElke knoop is rood of zwart gekleurd
2. BDe hoogten van de linker- en rechtersubboom verschillen hoogstens 1
3. CAlle bladeren liggen op precies dezelfde diepte
4. DBeide subbomen van elke knoop bevatten precies hetzelfde aantal knopen

Wat geldt voor de adjacency matrix van een ongerichte graaf?

1. AZe is symmetrisch ten opzichte van de hoofddiagonaal
2. BHaar hoofddiagonaal bevat altijd enen
3. CZe is altijd bovendriehoeks
4. DElke rij heeft precies één 1

Een object wordt als sleutel in een hashmap opgeslagen, waarna een veld dat de hashfunctie gebruikt wordt gewijzigd. Wat is het waarschijnlijke gevolg?

1. AHet object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat
2. BDe map verplaatst de sleutel automatisch naar zijn nieuwe bucket
3. CEr verandert niets, omdat de hash van een sleutel maar één keer wordt berekend wanneer het programma start
4. DDe map geeft een fout op het moment dat het veld verandert

Welke garantie geven de regels van een rood-zwartboom over de hoogte van een boom met n sleutels?

1. ADe hoogte is hoogstens 2 log₂(n + 1)
2. BDe hoogte is hoogstens log₂ n + 1
3. CDe hoogte is hoogstens n / 2
4. DDe hoogte is precies log₂ n