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

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

  1. AHashtabel
  2. BGekoppelde lijst
  3. CStapel (stack)
  4. DWachtrij (queue)
2.Makkelijk

Welke bewerking is traag in een array maar snel aan de kop van een gekoppelde lijst?

  1. ADe lengte van een array met vaste grootte bepalen
  2. BInvoegen aan het begin
  3. CHet 5e element benaderen
  4. DHet laatste element via de index lezen
3.Makkelijk

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

  1. AHet element op index i benaderen
  2. BHet kopelement verwijderen
  3. CInvoegen aan de kop
  4. DHet eerste element lezen
4.Gemiddeld

Een binaire boom heeft wortel 1 met linkerkind 2 en rechterkind 3; knoop 2 heeft kinderen 4 (links) en 5 (rechts). Wat is de postorder-doorloop?

  1. A4 2 5 1 3
  2. B4 5 2 3 1
  3. C1 2 4 5 3
  4. D5 4 3 2 1
5.Gemiddeld

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

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

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

  1. AVerwijder de wortel en schuif alle elementen één plaats naar links
  2. BVerplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  3. CVerwijder het laatste element van de array
  4. DZoek in alle bladeren naar het nieuwe minimum
7.Moeilijk

Hoe lang duurt het zoeken naar een willekeurige sleutel in een binaire min-heap van n elementen?

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

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. AEen enkele linksrotatie bij de ongebalanceerde knoop
  2. BHet opnieuw kleuren van de knoop en zijn kind
  3. CEen enkele rechtsrotatie bij de ongebalanceerde knoop
  4. DEen linksrotatie bij het kind, dan een rechtsrotatie bij de knoop

Antwoordenblad

  1. 1. C · Stapel (stack)
  2. 2. B · Invoegen aan het begin
  3. 3. A · Het element op index i benaderen
  4. 4. B · 4 5 2 3 1
  5. 5. B · De hoogten van de linker- en rechtersubboom verschillen hoogstens 1
  6. 6. B · Verplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  7. 7. A · O(n)
  8. 8. C · Een enkele rechtsrotatie bij de ongebalanceerde knoop

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