Werkblad Datastructuren met antwoorden

Gratis printbaar werkblad Datastructuren: 8 opgaven van makkelijk tot tentamenniveau, met antwoordenblad. Print het of sla het op als pdf.

Nieuw werkbladOnline oefenen met hints

Voor docenten: gratis te printen, kopiëren en in de les te gebruiken. Elk nieuw werkblad heeft nieuwe waarden en een eigen antwoordblad. Een link naar ExamProblems op je cursuspagina wordt gewaardeerd.

Naam: ____________________   Datum: ____________

1.Makkelijk

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

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

Hoe heet de queuebewerking die het element vooraan verwijdert?

  1. APush
  2. BInsert
  3. CEnqueue
  4. DDequeue
3.Makkelijk

Wat is het belangrijkste verschil tussen een statische en een dynamische array?

  1. AEen statische array geeft tragere toegang via de index
  2. BEen dynamische array kan groeien door naar een groter geheugenblok te verhuizen
  3. CEen dynamische array slaat zijn elementen op in gekoppelde knopen zodat hij element voor element kan groeien
  4. DEen statische array kan alleen getallen opslaan
4.Gemiddeld

Hoe werkt extract-min in een binaire min-heap?

  1. AZoek in alle bladeren naar het nieuwe minimum
  2. BVerwijder de wortel en schuif alle elementen één plaats naar links
  3. CVerplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  4. DVerwijder het laatste element van de array
5.Gemiddeld

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

  1. A1
  2. B√n
  3. Cn (hij wordt een gekoppelde lijst)
  4. Dlog₂ n
6.Gemiddeld

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

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

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

  1. ADe hoogte is hoogstens n / 2
  2. BDe hoogte is hoogstens log2 n + 1
  3. CDe hoogte is hoogstens 2 log2(n + 1)
  4. DDe hoogte is precies log2 n
8.Moeilijk

Wat zijn de tijd- en extra geheugenkosten van het ter plaatse omkeren van een enkelvoudig gekoppelde lijst?

  1. AO(n) tijd en O(1) extra geheugen
  2. BO(n) tijd en O(n) extra geheugen
  3. CO(n log n) tijd en O(1) extra geheugen
  4. DO(1) tijd en O(1) extra geheugen

Antwoordenblad

  1. 1. D · Null (geen knoop)
  2. 2. D · Dequeue
  3. 3. B · Een dynamische array kan groeien door naar een groter geheugenblok te verhuizen
  4. 4. C · Verplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  5. 5. C · n (hij wordt een gekoppelde lijst)
  6. 6. C · O(n), omdat latere elementen moeten opschuiven
  7. 7. C · De hoogte is hoogstens 2 log2(n + 1)
  8. 8. A · O(n) tijd en O(1) extra geheugen

Volledige stapsgewijze oplossingen: oefen dit onderwerp op examproblems.com.