Werkblad Datastructuren met antwoorden

In een enkelvoudig gekoppelde lijst bevat elke knoop:

1. AData en een index
2. BData en verwijzingen naar alle andere knopen
3. CData en een verwijzing naar de volgende knoop
4. DAlleen data

Waar vind je het kleinste element van een binaire min-heap?

1. AIn de wortel
2. BIn een willekeurig blad, dat moet worden gezocht
3. CIn het meest linkse blad
4. DOp de laatste positie in de array

Welke datastructuur werkt volgens het principe "last in, first out" (LIFO)?

1. AHashtabel
2. BWachtrij (queue)
3. CGekoppelde lijst
4. DStapel (stack)

Wat is de maximaal mogelijke load factor in een hashtabel met open addressing?

1. AEr is geen maximum
2. B2
3. C0,5
4. D1

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

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

Hoe wordt in een circulaire queue in een array met capaciteit n de volgende positie na index i berekend?

1. Ai + 1
2. B(i + 1) mod n
3. C2i + 1
4. D(i − 1) mod n

Hoe verbetert een radix tree (gecomprimeerde trie) een gewone trie?

1. AHij slaat elk woord op in een hashtabel bij de wortel in plaats van in aparte knopen
2. BHij sorteert de kinderen van elke knoop op frequentie
3. CHij voegt ketens van knopen met één kind samen tot één kant met een string als label
4. DHij bewaart alleen de eerste letter van elk woord

Welke uitspraak over heapsort is juist?

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