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 is het meest geschikt voor de functie "ongedaan maken" (undo) in een teksteditor?

  1. AStapel (stack)
  2. BHash-set
  3. CGraaf
  4. DWachtrij (queue)
2.Makkelijk

Wat is een cykel in een graaf?

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

De diepte van een knoop in een boom is:

  1. AHet aantal knopen in zijn subboom
  2. BHet aantal kanten van de wortel tot die knoop
  3. CHet aantal kinderen van die knoop
  4. DHet aantal kanten van die knoop tot het diepste blad
4.Gemiddeld

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

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

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

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

Een knoop in een binaire zoekboom heeft een rechtersubboom. Waar staat zijn inorder-opvolger?

  1. AAltijd zijn ouder
  2. BDe meest rechtse knoop van zijn linkersubboom
  3. CAltijd zijn rechterkind
  4. DDe meest linkse knoop van zijn rechtersubboom
7.Moeilijk

Het verwijderen van een knoop met twee kinderen uit een binaire zoekboom gebeurt meestal door:

  1. AHem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen
  2. BHem te verwisselen met de wortel
  3. CDe hele subboom te verwijderen
  4. DDe deelboom eronder helemaal opnieuw op te bouwen en elke sleutel die erin zat opnieuw in te voegen
8.Moeilijk

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

  1. AO(1) 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(n) tijd en O(1) extra geheugen

Antwoordenblad

  1. 1. A · Stapel (stack)
  2. 2. D · Een pad dat begint en eindigt in dezelfde knoop
  3. 3. B · Het aantal kanten van de wortel tot die knoop
  4. 4. A · De hoogten van de linker- en rechtersubboom verschillen hoogstens 1
  5. 5. C · Verplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  6. 6. D · De meest linkse knoop van zijn rechtersubboom
  7. 7. A · Hem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen
  8. 8. D · O(n) tijd en O(1) extra geheugen

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