Werkblad Datastructuren met antwoorden

Wat slaat een map (dictionary) op?

1. AAlleen waarden in volgorde van invoegen
2. BParen van gelijke sleutels
3. CWaarden gesorteerd op grootte
4. DSleutel-waardeparen met unieke sleutels

De diepte van een knoop in een boom is:

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

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

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

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

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

Welke datastructuur wordt gebruikt om te controleren of de haakjes in "{[()]}" in balans zijn?

1. AEen hashtabel
2. BEen queue
3. CEen stack
4. DEen binaire zoekboom

Waarom is het doorlopen van een array in de praktijk vaak veel sneller dan het doorlopen van een gekoppelde lijst van dezelfde lengte?

1. AEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
2. BArrays gebruiken minder instructies om waarden te vergelijken
3. CArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
4. DGekoppelde lijsten slaan elementen altijd op schijf op

In een circulaire buffer kan front == rear zowel leeg als vol betekenen. Wat is een gangbare manier om ze te onderscheiden?

1. ASla front en rear op in dezelfde variabele
2. BMaak de buffer altijd leeg als front gelijk is aan rear, zodat de toestand leeg is
3. CHoud een apart aantal elementen bij, of laat altijd één plaats ongebruikt
4. DMaak de buffergrootte een macht van twee

Welk probleem van linear probing vermindert double hashing vooral?

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