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 wordt gebruikt voor een level-order-doorloop van een boom?

  1. AHashtabel
  2. BQueue
  3. CStack
  4. DPrioriteitswachtrij
2.Makkelijk

Wat is de bezettingsgraad (load factor) van een hashtabel?

  1. AHet aantal opgeslagen elementen gedeeld door het aantal buckets
  2. BHet aantal botsingen tot nu toe
  3. CHet aantal buckets gedeeld door de gemiddelde lengte van de opgeslagen sleutels
  4. DDe tijd die nodig is om de tabel van schijf te laden
3.Makkelijk

Hoeveel kanten heeft een boom met n knopen?

  1. An − 1
  2. Bn
  3. Cn + 1
  4. D2n
4.Gemiddeld

Wat is het doel van een sentinelknoop (dummyknoop) in een gekoppelde lijst?

  1. ADe code vereenvoudigen door speciale gevallen aan kop of staart weg te nemen
  2. BDe lijst gesorteerd maken
  3. CVoorkomen dat de lijst groeit voorbij een vast maximumaantal knopen
  4. DHet aantal elementen opslaan
5.Gemiddeld

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

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

Wat gebeurt er als een hashtabel rehasht nadat de load factor een drempel overschrijdt?

  1. AAlleen de botsende sleutels worden naar een nieuwe overloop-lijst aan het eind van de tabel verplaatst
  2. BEr wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd
  3. CDe oudste sleutels worden verwijderd om ruimte te maken
  4. DDe bestaande sleutels worden ter plaatse gesorteerd
7.Moeilijk

Welke bewerkingen ondersteunt een Fenwick-boom (binary indexed tree) over een array van n getallen in O(log n)?

  1. AElementen op elke positie invoegen
  2. BDe array sorteren en binair zoeken
  3. CDe mediaan vinden in O(1)
  4. DPrefixsomquery's en updates van één element
8.Moeilijk

Waarvoor wordt de union-findstructuur gebruikt in het algoritme van Kruskal voor de minimale opspannende boom?

  1. ADe beginknoop kiezen
  2. BTijdens het zoeken de huidige afstand van elke knoop tot de bron opslaan
  3. CDe kanten op gewicht sorteren
  4. DControleren of de twee eindpunten van een kant al verbonden zijn

Antwoordenblad

  1. 1. B · Queue
  2. 2. A · Het aantal opgeslagen elementen gedeeld door het aantal buckets
  3. 3. A · n − 1
  4. 4. A · De code vereenvoudigen door speciale gevallen aan kop of staart weg te nemen
  5. 5. A · De hoogten van de linker- en rechtersubboom verschillen hoogstens 1
  6. 6. B · Er wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd
  7. 7. D · Prefixsomquery's en updates van één element
  8. 8. D · Controleren of de twee eindpunten van een kant al verbonden zijn

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