Werkblad Datastructuren met antwoorden

Welke bewerking is O(1) voor een array maar O(n) voor een enkelvoudig gekoppelde lijst?

1. AHet kopelement verwijderen
2. BHet element op index i benaderen
3. CHet eerste element lezen
4. DInvoegen aan de kop

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

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

Wat is een cykel in een graaf?

1. AEen knoop zonder kanten
2. BEen pad dat elke knoop bezoekt
3. CEen pad dat begint en eindigt in dezelfde knoop
4. DEen kant met gewicht nul

Wat is de tijdcomplexiteit van het zoeken naar een sleutel in een gebalanceerde binaire zoekboom?

1. AO(1)
2. BO(n log n)
3. CO(n)
4. DO(log n)

Wat kost het invoegen van een element in het midden van een array met n elementen?

1. AO(n²), omdat elk element n keer verschuift
2. BO(1), omdat de index bekend is
3. CO(log n), vanwege binair zoeken
4. DO(n), omdat latere elementen moeten opschuiven

Waar staat in een binaire heap die in een array vanaf index 0 is opgeslagen de ouder van de knoop op index i?

1. AOp index 2i + 1
2. BOp index ⌊i / 2⌋ + 1
3. COp index i − 1
4. DOp index ⌊(i − 1) / 2⌋

Wat zijn, zonder union by rank of path compression, de kosten in het slechtste geval van één find in een union-findstructuur met n elementen?

1. AO(1)
2. BO(log n)
3. CO(α(n))
4. DO(n)

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

1. ASorteer de lijst en zoek naar duplicaten
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. DSla elke bezochte knoop op in een hash-set