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

In een enkelvoudig gekoppelde lijst bevat elke knoop:

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

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

  1. AHet aantal kinderen van de wortel
  2. BHet aantal bladeren in de boom
  3. CHet totale aantal knopen in de boom, inclusief de wortel en elk blad
  4. DHet aantal kanten op het langste pad van de wortel naar een blad
3.Makkelijk

Wat zijn broer- of zusknopen (siblings) in een boom?

  1. AEen knoop en zijn ouder
  2. BKnopen zonder kinderen
  3. CKnopen die dezelfde ouder hebben
  4. DKnopen op dezelfde diepte in verschillende subbomen
4.Gemiddeld

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

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

Hoe lang duurt het zoeken naar een woord met lengte L in een trie met een vast alfabet?

  1. AO(L × n)
  2. BO(n), waarbij n het aantal woorden is
  3. CO(log n), waarbij n het aantal woorden is
  4. DO(L), onafhankelijk van hoeveel woorden er zijn opgeslagen
6.Gemiddeld

Hoe wordt een nieuw element in een binaire heap ingevoegd?

  1. APlaats het in de wortel en laat het omlaag zakken (sift down)
  2. BVoeg het op de gesorteerde positie in door alle grotere elementen één plaats naar rechts te verschuiven
  3. CPlaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
  4. DBouw de hele heap opnieuw op
7.Moeilijk

Een object wordt als sleutel in een hashmap opgeslagen, waarna een veld dat de hashfunctie gebruikt wordt gewijzigd. Wat is het waarschijnlijke gevolg?

  1. AHet object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat
  2. BDe map verplaatst de sleutel automatisch naar zijn nieuwe bucket
  3. CEr verandert niets, omdat de hash van een sleutel maar één keer wordt berekend wanneer het programma start
  4. DDe map geeft een fout op het moment dat het veld verandert
8.Moeilijk

De union-find-structuur (disjoint set) met union by rank en padcompressie heeft geamortiseerde kosten per bewerking van:

  1. APrecies O(log n)
  2. BO(n)
  3. CO(n²)
  4. DO(α(n)), de inverse Ackermann-functie, die in de praktijk constant is

Antwoordenblad

  1. 1. C · Data en een verwijzing naar de volgende knoop
  2. 2. D · Het aantal kanten op het langste pad van de wortel naar een blad
  3. 3. C · Knopen die dezelfde ouder hebben
  4. 4. C · De hoogten van de linker- en rechtersubboom verschillen hoogstens 1
  5. 5. D · O(L), onafhankelijk van hoeveel woorden er zijn opgeslagen
  6. 6. C · Plaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
  7. 7. A · Het object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat
  8. 8. D · O(α(n)), de inverse Ackermann-functie, die in de praktijk constant is

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