Werkblad Datastructuren met antwoorden

Wat bevat in een enkelvoudig gekoppelde lijst de next-pointer van de laatste knoop?

1. AHet adres van de eerste knoop
2. BHet aantal knopen in de lijst
3. CNull (geen knoop)
4. DHet adres van de vorige knoop

Wat is de bezettingsgraad (load factor) van een hashtabel?

1. ADe tijd die nodig is om de tabel van schijf te laden
2. BHet aantal buckets gedeeld door de gemiddelde lengte van de opgeslagen sleutels
3. CHet aantal botsingen tot nu toe
4. DHet aantal opgeslagen elementen gedeeld door het aantal buckets

Wat definieert een binaire boom?

1. AElke knoop heeft precies twee kinderen
2. BElke knoop heeft hoogstens twee kinderen
3. CElke knoop slaat een binair getal op
4. DDe boom heeft precies twee niveaus

Welke datastructuur gebruikt een draaiend programma om actieve functieaanroepen en hun lokale variabelen bij te houden?

1. ADe wachtrij van het heapgeheugen
2. BDe call stack
3. CEen hashtabel van functies
4. DEen binaire zoekboom van frames

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

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

Wat is in het slechtste geval de hoogte van een binaire zoekboom met n knopen als de sleutels in gesorteerde volgorde worden ingevoegd?

1. A√n
2. B1
3. Clog₂ n
4. Dn (hij wordt een gekoppelde lijst)

Door het invoegen van een sleutel in een AVL-boom wordt de linkersubboom van een knoop te hoog, en de nieuwe sleutel kwam in de linkersubboom van zijn linkerkind (left-left-geval). Welke correctie wordt toegepast?

1. AHet opnieuw kleuren van de knoop en zijn kind
2. BEen linksrotatie bij het kind, dan een rechtsrotatie bij de knoop
3. CEen enkele linksrotatie bij de ongebalanceerde knoop
4. DEen enkele rechtsrotatie bij de ongebalanceerde knoop

Waarom zou een server zijn hashfunctie willekeurig kiezen uit een universele familie?

1. AOm het zeer onwaarschijnlijk te maken dat een aanvaller veel sleutels kan kiezen die allemaal botsen
2. BOm de hashtabel gesorteerd te maken
3. COm het vergroten van de tabel overbodig te maken
4. DOm te garanderen dat geen twee sleutels ooit botsen, welke sleutels een aanvaller ook stuurt